knt linier eq
Post on 03-Apr-2018
234 Views
Preview:
TRANSCRIPT
-
7/27/2019 KNT Linier Eq
1/114
KOMPUTASI NUMERIK
TERAPAN (KNT) - TK-091356
Sistem Persamaan Linear
-
7/27/2019 KNT Linier Eq
2/114
Sistem Persamaan Linier
Sistem persamaan aljabar linier sering timbul pada
perumusan persoalan di berbagai bidang.
Contoh bidang teknik kimia : Stok bahan untuk suatu industri kimia,
Neraca massa pada tiap-tiap plate (stage) kolom
absorpsi,
Optimasi proses-proses
Penyelesaian persamaan differensial parsial, dan banyak
lagi pemakaian yang lain
-
7/27/2019 KNT Linier Eq
3/114
Stok bahan untuk suatu industri kimia,
Neraca massa pada tiap-tiap plate (stage) kolom
absorpsi,
Optimasi proses-proses
Penyelesaian persamaan differensial parsial, dan banyak
lagi pemakaian yang lain
-
7/27/2019 KNT Linier Eq
4/114
Sistem Persamaan Linier
Pada kuliah sebelumnya kita fokus pada
persoalan mencari nilai x yang memenuhi
persamaan tunggal f(x) = 0
Sekarang kita akan membahas kasus
penentuan nilai-nilai x1, x2, .....xn, yang
secara simultan memenuhi suatu setpersamaan linier
-
7/27/2019 KNT Linier Eq
5/114
Sistem Persamaan Linier
Persamaan simultanf1(x1, x2, .....xn) = 0
f2(x1, x2, .....xn) = 0
.............f3(x1, x2, .....xn) = 0
Set Persamaan Linier
a11x1 + a12x2 +...... a1nxn =c1
a21x1 + a22x2 +...... a2nxn =c2..........
an1x1 + an2x2 +...... annxn =cn
-
7/27/2019 KNT Linier Eq
6/114
Matrix
Set elemen horizontal disebut baris (row)
Set elemen vertikal disebut kolom (column)
Indeks pertama menunjukan nomor baris
Indeks kedua menunjukan nomor kolom
A
a a a a
a a a a
a a a a
n
n
m m m mn
11 12 13 1
21 22 23 2
1 2 3
...
...
. . . ....
-
7/27/2019 KNT Linier Eq
7/114
mnmmm
n
n
aaaa
aaaa
aaaa
A
.......
...
...
321
2232221
1131211
Matrix memiliki m baris dan n kolom.
Disebut matrix dimensi m cross n (m x n)
note
subscript
Matrix
-
7/27/2019 KNT Linier Eq
8/114
A
a a a a
a a a a
a a a a
n
n
m m m mn
11 12 13 1
21 22 23 2
1 2 3
...
...
. . . .
...
row 2
column 3
Catatan skema yangkonsisten dengan
subskrip yang
menunjukkan baris,
kolom
Matrix
-
7/27/2019 KNT Linier Eq
9/114
Vektor baris : m = 1
Vektor kolom : n=1 Matrix square : m = n
B b b bn 1 2 .......
C
c
c
cm
1
2
.
.
Aa a a
a a a
a a a
11 12 13
21 22 23
31 32 33
Matrix
-
7/27/2019 KNT Linier Eq
10/114
Aa a a
a a a
a a a
11 12 13
21 22 23
31 32 33
Matrix dengan diagonal terdiri dari elemen-elemen :a11 a22 a33
Matrix simetris
Matrix diagonal
Matrix identitas (identity)
Matrix segitiga atas (upper triangular)
Matrix segitiga bawah (lower triangular)
Banded matrix
upper
lowerbandwitdth
elemen diagonal 1 dan nol yang lain
Matrix
-
7/27/2019 KNT Linier Eq
11/114
Matrix Simetris
A
5 1 21 3 7
2 7 8
aij = aji untuk semua i danj
-
7/27/2019 KNT Linier Eq
12/114
Matrix Diagonal
A
a
a
a
a
11
22
33
44
0 0 0
0 0 0
0 0 0
0 0 0
Square matrix dengan semua elemen diluar
main diagonal adalah zero
-
7/27/2019 KNT Linier Eq
13/114
Matrix Identity
A
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
Simbol [I] digunakan untuk menunjukan matrix identitas.
Matrix diagonal semua elemen main diagonal adalah 1 dan
elemen-elemen yang lain bernilai zero
-
7/27/2019 KNT Linier Eq
14/114
Upper Triangle Matrix
Aa a a
a a
a
11 12 13
22 23
33
0
0 0
Elemen-elemen dibawah main diagonal adalah zero
-
7/27/2019 KNT Linier Eq
15/114
Lower Triangular Matrix
A
5 0 0
1 3 0
2 7 8
Semua elemen diatas main diagonal adalah
zero
-
7/27/2019 KNT Linier Eq
16/114
Banded Matrix
Aa aa a a
a a a
a a
11 12
21 22 23
32 33 34
43 44
0 00
0
0 0
Semua elemen adalah zero kecuali elemen-elemen
band yang berpusat pada main diagonal
-
7/27/2019 KNT Linier Eq
17/114
Aturan Operasi Matrix
Penjumlahan/Pengurangan
aij + bij = cij
Penjumlahan/Pengurangan : komutatif
[A] + [B] = [B] + [A]
Penjumlahan/Pengurangan : asosiatif
[A] + ([B]+[C]) = ([A] +[B]) + [C]
-
7/27/2019 KNT Linier Eq
18/114
Aturan Operasi Matrix
Perkalian matrix [A] dgn skalar g sama denganperkalian setiap elemen [A] dengan g
B g A
ga ga ga
ga ga ga
ga ga ga
n
n
m m mn
11 12 1
21 22 2
1 2
. . .
. . .
. . . . . .
. . . . . .
. . . . . .
. . .
-
7/27/2019 KNT Linier Eq
19/114
Aturan Operasi Matrix
Perkalian dua buah matrix dinyatakan sbg
[C] = [A][B]
n = dimensi kolom [A]
n = dimensi baris [B]
c a bij ik kjk
N
1
Harus sama
Syarat :
-
7/27/2019 KNT Linier Eq
20/114
Cara sederhana untuk cek apakah
perkalian matrix bisa atau tidak
[A] m x n [B] n x k = [C] m x k
Dimensi interior
harus sama
Dimensi eksterior sesuai dengan
dimensi matrix yang dihasilkan
-
7/27/2019 KNT Linier Eq
21/114
Perkalian Matrix
Perkalian matriks bersifat asosiatif
([A][B])[C] = [A]([B][C])
Perkalian matriks bersifat distributif([A] + [B])[C] = [A][C] + [B][C]
Perkalian umumnya tidak komutatif
[A][B] [B][A]
-
7/27/2019 KNT Linier Eq
22/114
Matrix Inverse [A]
IAAAA 11
-
7/27/2019 KNT Linier Eq
23/114
Transpose [A] :
A
a a a
a a a
a a a
t
m
m
n n mn
11 21 1
12 22 2
1 2
. . .
. . .
. . . . . .
. . . . . .
. . . . . .
. . .
Refleksi A thd main diagonal
Baris A menjadi kolom AT
Kolom A menjadibaris A
T
Matrix : Transpose [A]
http://en.wikipedia.org/wiki/Main_diagonalhttp://en.wikipedia.org/wiki/Main_diagonal -
7/27/2019 KNT Linier Eq
24/114
Determinants
Ditulis sebagai det A or |A|
Untuk matrix 2 x 2
bcaddc
ba
-
7/27/2019 KNT Linier Eq
25/114
Determinants
Ada beberapa skema yang digunakan untuk menghitung
determinant suatu matrix
gunakan minordan cofactors matrix
Minor : minor dari sebuah entry aij adalah determinant dari
submatrix yg diperoleh penghapusan baris ke-i dan kolom ke-j
Cofactor: cofactor dari entry aijdari matrix A (n x n) adalah
perkalian (-1)i+j dan minor dari aij
-
7/27/2019 KNT Linier Eq
26/114
minor of aa a aa a a
a a a
32
11 12 13
21 22 23
31 32 33
Minor : minor dari sebuah entry aij adalah determinant dari
submatrix yg diperoleh penghapusan baris ke-i dan kolom ke-j
Contoh : minor dari a32untuk matrix 3x3 :
Untuk elemen
a32 baris ke-iadalah baris 3
-
7/27/2019 KNT Linier Eq
27/114
minor of a
a a a
a a a
a a a
32
11 12 13
21 22 23
31 32 33
Untuk elemen a32 kolom ke-j adalah kolom 2
Minor : minor dari sebuah entry aij adalah determinant dari
submatrix yg diperoleh penghapusan baris ke-i dan kolom ke-j
Contoh : minor dari a32untuk matrix 3x3 :
-
7/27/2019 KNT Linier Eq
28/114
minor of a
a a a
a a a
a a a
32
11 12 13
21 22 23
31 32 33
minor of a
a a a
a a a
a a a
a a
a aa a a a32
11 12 13
21 22 23
31 32 33
11 13
21 23
11 23 13 21
Minor : minor dari sebuah entry aij adalah determinant dari
submatrix yg diperoleh penghapusan baris ke-i dan kolom ke-j
Contoh : minor dari a32untuk matrix 3x3 :
-
7/27/2019 KNT Linier Eq
29/114
-
7/27/2019 KNT Linier Eq
30/114
minor of aa a aa a a
a a a
a a
a aa a a a31
11 12 13
21 22 23
31 32 33
12 13
22 23
12 23 22 13
Cofactor : Aij, cofactor dari entry aij dari matrix A (n x n) adalah
perkalian dari (-1)i+j dan minoraij
Misal hitung A31untuk matrix 3x3
Pertama hitung minor a31
-
7/27/2019 KNT Linier Eq
31/114
A a a a a313 1
12 23 22 131
minor of aa a aa a a
a a a
a a
a aa a a a31
11 12 13
21 22 23
31 32 33
12 13
22 23
12 23 22 13
Cofactor : Aij, cofactor dari entry aij dari matrix A (n x n) adalah
perkalian dari (-1)i+j dan minoraij
Misal hitung A31untuk matrix 3x3
Pertama hitung minor a31
-
7/27/2019 KNT Linier Eq
32/114
Minordan cofactordigunakan untuk menghitung determinant dari
suatu matrix.
Misal matrix n x n diekspan disekitar baris ke-i
ininiiii AaAaAaA ......2211
Ekspansi disekitar kolom ke-j
njnjjjjj AaAaAaA ......2211
(untuk setiap satu nilai i)
(untuk setiap satu nilaij)
-
7/27/2019 KNT Linier Eq
33/114
D
a a a
a a aa a a
a
a a
a a a
a a
a a a
a a
a a
11 12 13
21 22 23
31 32 33
11
22 23
32 33
12
21 23
31 33
13
21 22
31 32
322232211331
3123332112
21
1322231211
11
1
11det
aaaaa
aaaaaaaaaa
-
7/27/2019 KNT Linier Eq
34/114
Hitung determinan matrix 3x3 dibawah.pertama, hitung menggunakan baris ke-1.
Kemudian coba menggunakan baris ke-2n.
516
234
971
Contoh
-
7/27/2019 KNT Linier Eq
35/114
Sifat-sifat Determinan
det A = det AT
Bila semua entry dari baris dan kolom
adalah zero, maka det A = 0
Bila dua rows or two kolom adalah identik,
maka det A = 0
-
7/27/2019 KNT Linier Eq
36/114
Bagaimana merepresentasikan suatu
sistem persamaan linier kedalam matrix
[A]{X} = {C}
dimana {X} dan {C} adalah vektor kolom
-
7/27/2019 KNT Linier Eq
37/114
44.0
67.0
01.0
5.03.01.0
9.115.0
152.03.0
}{}{
44.05.03.01.0
67.09.15.0
01.052.03.0
3
2
1
321
321
321
x
x
x
CXA
xxx
xxx
xxx
-
7/27/2019 KNT Linier Eq
38/114
Metode Grafik
2 Persamaan, 2 Tak Diketahui
a x a x c
a x a x c
x
a
a
x
c
a
x
a
a
x
c
a
11 1 12 2 1
21 1 22 2 2
2
11
121
1
12
2
21
22
1
2
22
x2
x1
( x1, x2 )
-
7/27/2019 KNT Linier Eq
39/114
3 2 18
2 2
32
9
1
21
1 2
1 2
2 1
2 1
x x
x x
x x
x x
x2
x1
( 4 , 3 )
3
2
2
1
9
1
Cek: 3(4) + 2(3) = 12 + 6 = 18
-
7/27/2019 KNT Linier Eq
40/114
Bagaimana kita tahu apakah sistem ini ill-
condition.
bila determinan adalah zero, slopes adalah
identical a x a x c
a x a x c
11 1 12 2 1
21 1 22 2 2
Susun ulang persamaan-persamaan ini shg kita memiliki
versi alternatif dalam bentuk garis lurus
Misal :x2 = (slope) x1 + intercept
Mulailah dengan mempertimbangkan sistem dimana
slopenya adalah identik
-
7/27/2019 KNT Linier Eq
41/114
xa
a
xc
a
xa
ax
c
a
211
12
11
12
221
22
12
22
Bila slope hampir sama (ill-conditioned)
a
a
a
a
a a a a
a a a a
11
12
21
22
11 22 21 12
11 22 21 12 0
a a
a aA
11 12
21 22
det
Bukankah ini determinan?
-
7/27/2019 KNT Linier Eq
42/114
Bila determinan adalah zero slopes adalah sama.Ini dapat diartikan :
- Tidak ada solusi
- Solusi banyak tak terbatas (infinite number
of solutions)
Bila determinant mendekati zero, system dikatakan ill-
conditioned.
Jadi sepertinya kita harus menggunakan cek determinansistem sebelum perhitungan lebih lanjut dilakukan.
-
7/27/2019 KNT Linier Eq
43/114
Contoh
Tentukan apakah matrix berikut dalam kondisi ill-conditioned.
12
22
5.22.19
7.42.37
2
1
x
x
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
44/114
PENYELESAIAN SISTIM PERSAMAAN
PERSAMAANSISTIM PERSAMAAN-PERSAMAAN LINEAR
Bila diketahui satu sistem persamaan aljabar linier sembarang, adatiga kemungkinan hal yang terjadi, yaitu :
1. Sistem mempunyai jawab yang unik (uniq ue).
x + 2 y = 6
x + y = 1 x = -4 dan y = 5Penyelesaian
2. Sistem tak mempun yai jawaban sebagai con toh :
2x + 4y = 12
x + 2y = 10
3. Sistem mempunyai tak berhin gga jawaban.
x + y = 12x + 2y = 2
Dua garis berpotongan
Dua garis sejajar
Dua garis berimpit
Determinan matriks koefisien = 0
Determinan matriks koefisien = 0
Syarat sistim mempunyai satu jawaban unik: determinan matriks koefisien 0
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
45/114
SISTIM PERSAMAAN-PERSAMAAN LINEAR
PENYELESAIAN SISTIM PERSAMAAN
PERSAMAAN
a11 x1 + a12 x2 + ........... + a1n xn = c1
a21 x1 + a22 x2 + ........... + a2n xn = c2
an1 x1 + an2 x2 + ........... + ann xn = cn
cxA
nnnnnn
n
n
n
aaaaa
aaaaa
aaaaa
aaaaa
A
..........
..............................................
..............................................
............
...........
..........
4321
334333231
224232221
114131211
nx
x
x
x
x
.
.
3
2
1
nc
c
c
c
c
.
.
3
2
1
-
7/27/2019 KNT Linier Eq
46/114
Metode Matrix
Gauss elimination
Matrix inversion
Gauss Seidel
LU decomposition
Aa a a
a a a
a a a
11 12 13
21 22 23
31 32 33
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
47/114
PENYELESAIAN SISTIM PERSAMAAN
PERSAMAAN
SISTIM PERSAMAAN-PERSAMAAN LINEAR
METODA-METODA:
METODA LANGSUNG: ELIMINASI GAUSS
GAUSS YORDAN
LU-DECOMPOSITION
MATRIXS INVERSION
METODA TAK LANGSUNG: YACOBI
GAUSS-SEIDEL
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
48/114
PENYELESAIAN SISTIM PERSAMAAN-
PERSAMAANSISTIM PERSAMAAN-PERSAMAAN LINEAR
Metoda Eliminasi Gauss
nnnnnnnn
nn
nn
nn
nn
cxaxaxaxaxa
cxaxaxaxaxa
cxaxaxaxaxa
cxaxaxaxaxa
cxaxaxaxaxa
...................................
..............................................................................................................
..............................................................................................................
..............................................................................................................
...................................
..................................
...................................
..................................
44332211
44444343242141
33434333232131
22424323222121
11414313212111
Ada dua tahap: Tahap Eliminasi dan Tahap Substitusi Kembali
Tahap Eliminasi
Terdiri dari n-1 langkah eliminasi dengan tujuan eliminasi x1, x2, ., xn-1
berturut-turut dari sistim persamaan-persamaan berikut.
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
49/114
PENYELESAIAN SISTIM PERSAMAAN
PERSAMAANSISTIM PERSAMAAN-PERSAMAAN LINEAR
)1()1(
4
)1(
43
)1(
32
)1(
2
)1(
4
)1(
44
)1(
443
)1(
432
)1(
42
)1(
3
)1(
34
)1(
343
)1(
332
)1(
32
)1(2
)1(24
)1(243
)1(232
)1(22
11414313212111
...................................
..............................................................................................................
..............................................................................................................
..............................................................................................................
...................................
..................................
...................................
..................................
nnnnnnn
nn
nn
nn
nn
cxaxaxaxa
cxaxaxaxa
cxaxaxaxa
cxaxaxaxa
cxaxaxaxaxa
Metoda Eliminasi GaussLangkah Eliminasi ke-1: Eliminasi x1 dari persamaan 2 sampai dengan n, caranya, kurangkan
persamaan (i) dengan persamaan (1) dikalikan ai1/a11, i= 2,..,n
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
50/114
PENYELESAIAN SISTIM PERSAMAAN
PERSAMAANSISTIM PERSAMAAN-PERSAMAAN LINEAR
)2()2(
4
)2(
43
)2(
3
)2(
4
)2(
44
)2(
443
)2(
43
)2(
3
)2(
34
)2(
343
)2(
33
)1(
2
)1(
24
)1(
243
)1(
232
)1(
22
11414313212111
...................................
..............................................................................................................
..............................................................................................................
..............................................................................................................
...................................
..................................
...................................
..................................
nnnnnn
nn
nn
nn
nn
cxaxaxa
cxaxaxa
cxaxaxa
cxaxaxaxa
cxaxaxaxaxa
Metoda Eliminasi GaussLangkah Eliminasi ke-2: Eliminasi x2 dari persamaan 3 sampai dengan n, caranya, kurangkan
persamaan (i) dengan persamaan (2) dikalikan ai2/a22, i= 3,..,n
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
51/114
PERSAMAANSISTIM PERSAMAAN-PERSAMAAN LINEAR
)1()1(
)2(
1
)2(
,11
)2(
1,1
)3(
4
)3(
44
)3(
44
)2(
3
)2(
34
)2(
343
)2(
33
)1(
2
)1(
24
)1(
243
)1(
232
)1(
22
11414313212111
..............................................................................................................
..............................................................................................................
...................................
.....................................................................
..................................
n
nn
n
nn
n
nn
n
nnn
n
nn
nn
nn
nn
nn
cxa
cxaxa
cxaxa
cxaxaxacxaxaxaxa
cxaxaxaxaxa
Metoda Eliminasi GaussLangkah Eliminasi ke-(n-1):
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
52/114
PENYELESAIAN SISTIM PERSAMAAN
PERSAMAAN
SISTIM PERSAMAAN-PERSAMAAN LINEAR
)1(
)1()1(
)1()(
rrr
r
rj
r
irrij
rij
aaaaa
)1(
)1()1(
)1()(
rrr
r
ir
r
rri
ri
aaccc
Metoda Eliminasi Gauss
Formula Umum Eliminasi
r =1,2,., n-1.
i = r+1, ., n.
j = r+1, .., n
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
53/114
PENYELESAIAN SISTIM PERSAMAAN-
PERSAMAAN
Tahap Substitusi Kembali
1........,,2,1,/
...................................................
..................................................
/
/
)1(
1
)1()1(
)2(
1,1
)2(
,1
)2(
11
)1()1(
nnjaxacx
axacx
acx
j
jj
n
ji
i
j
ji
j
jj
n
nnn
n
nn
n
nn
n
nn
n
nn
SISTIM PERSAMAAN-PERSAMAAN LINEAR
Metoda Eliminasi Gauss
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
54/114
PENYELESAIAN SISTIM PERSAMAAN
PERSAMAANSISTIM PERSAMAAN-PERSAMAAN LINEAR
i=1,N;
Pertukaran Baris
Start
Jumlah Persamaan, N
Baca aij
i=1,N;
Baca ci
r=1, N-1
i=r+1, N
j=r+1, N
aij=aij-air.arj/arr
ci=ci-cr.air/arr
xn=cn/ann
j=1,N-1;
i=N-j; Jum=0
k=i+1,N
Jum=Jum+aik.xk
xi=(ci-Jum)/aii
i=1,N
Cetak
End
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
55/114
PERSAMAANSISTIM PERSAMAAN-PERSAMAAN LINEAR
y
y
y
T
T
T
P=r+1L=r
L=PP=P+1 |aPr|>|aLr|
P=N
m=r
Temp=armarm=aLm
aLm=Temp
P=P+1
n=N
Temp=crcr=cL
cL=Temp
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
56/114
PENYELESAIAN SISTIM PERSAMAAN
PERSAMAANSISTIM PERSAMAAN-PERSAMAAN LINEAR
Contoh soal 3-1 :Cari x1 , x2 , dan x3 dari persamaan berikut dengan cara Eliminasi Gauss.
3 x1 - x2 + 2 x3 = 12
x1 + 2 x2 + 3 x3 = 11
2 x1 - 2 x2 - x3 = 2
Penyelesaian :
13
23
13
12
2:1-2-2
11:321
12:21-3BB
BB
27
43
6-:3
7-
3
4-0
7:3
7
3
70
12:21-3
BB
2-:1-00
7:3
7
3
70
12:21-3
2
73
7
3
7
1223
3
32
321
x
xx
xxx
33/22112
13
7/2
3
77
2
1
2
3
x
x
x
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
57/114
PENYELESAIAN SISTIM PERSAMAAN
PERSAMAANSISTIM PERSAMAAN-PERSAMAAN LINEAR
Metoda ini pada dasarnya mirip dengan metoda Eliminasi -Gauss,
perbedaannya hanya tahap Eliminasi dan tahap substitusi kembali
dilaksanakan bersamaan.
METODA GAUSS YORDAN
Algoritma :1). Untuk i = 1 s/d N laksanakan :
aij = aij / aii
akj = akj - aki . aij
ck
= ck
- aki
. ci
j = 1, 2, n
k= 1, 2, n
2). xi = ci , i = 1, 2, ....... n.
PENYELESAIAN SISTIM PERSAMAAN-
-
7/27/2019 KNT Linier Eq
58/114
PENYELESAIAN SISTIM PERSAMAAN
PERSAMAANSISTIM PERSAMAAN-PERSAMAAN LINEAR
Metoda Gauss Yordan juga bisa dinyatakan dalam bentuk OperasiMatrix seperti contoh berikut,
Contoh 3-2 :
Selesaikan sistim perssamaan berikut dengan metoda Gauss - Yordan,
2 x2 + x4 = 02 x1 + 2 x2 + 3 x3 + 2 x4 = -2
4 x1 - 3 x2 + + x4 = -7
6 x1 + x2 - 6 x3 - 5 x4 = 6
6:5-6-16
7-:103-4
2-:2322
0:1020
Penyelesaian
0:1020
7-:103-4
2-:2322
6:5-6-16
0:1020
11-:13/3411/3-0
4-:11/355/30
1:5/6-1-1/61B1 B2
B1/6
B2 B1*2
B3 B1*4
-
7/27/2019 KNT Linier Eq
59/114
Cramers Rule
Tidak efisien untuk menyelesaikan
persamaan linier yang besar
Berguna untuk menjelaskan beberapa
masalah yang terkait dengan penyelesaian
persamaan linier.
bxAb
bb
x
xx
aaa
aaaaaa
3
2
1
3
2
1
333231
232221
131211
-
7/27/2019 KNT Linier Eq
60/114
Cramers Rule
Untuk menyelesaikanxitempatkan {b}
dalam kolom ke-i
x
A
b a a
b a a
b a a
x
A
a b a
a b a
a b a
1
1 12 13
2 22 23
3 32 33
2
11 1 13
21 2 23
13 3 33
1 1
-
7/27/2019 KNT Linier Eq
61/114
xA
b a a
b a a
b a a
xA
a b a
a b a
a b a
xA
a a b
a a b
a a b
1
1 12 13
2 22 23
3 32 33
2
11 1 13
21 2 23
13 3 33
3
11 12 1
21 22 2
13 32 3
1 1
1
Cramers Rule
Untuk menyelesaikanxi
tempatkan {b} dalam
kolom ke-i
-
7/27/2019 KNT Linier Eq
62/114
Cramers Rule
33231
22221
11211
3
33331
23221
13111
2
33323
23222
13121
1
1
11
baa
baa
baa
Ax
aba
aba
aba
Ax
aab
aab
aab
Ax
Untuk menyelesaikanxi
tempatkan {b} dalam
kolom ke-i
-
7/27/2019 KNT Linier Eq
63/114
Use Gauss Elimination to solve the following set
of linear equations
3 13 50
2 6 45
4 8 4
2 3
1 2 3
1 3
x x
x x x
x x
EXAMPLE
(solution in notes)
-
7/27/2019 KNT Linier Eq
64/114
3 13 50
2 6 45
4 8 4
2 3
1 2 3
1 3
x x
x x x
x x
SOLUTION
First write in matrix form, employing short handpresented in class.
0 3 13 50
2 6 1 454 0 8 4
We will clearly run into
problems of division
by zero.
Use partial pivoting
-
7/27/2019 KNT Linier Eq
65/114
0 3 13 50
2 6 1 454 0 8 4
Pivot with equation
with largest an1
-
7/27/2019 KNT Linier Eq
66/114
0 3 13 50
2 6 1 454 0 8 4
4 0 8 4
2 6 1 45
0 3 13 50
-
7/27/2019 KNT Linier Eq
67/114
0 3 13 50
2 6 1 454 0 8 4
4 0 8 4
2 6 1 45
0 3 13 50
4 0 8 40 6 3 43
0 3 13 50
Begin developingupper triangular matrix
-
7/27/2019 KNT Linier Eq
68/114
4 0 8 4
0 6 3 43
0 3 13 50
4 0 8 4
0 6 3 43
0 0 14 5 285
285
14 51966
43 3 1966
68149
4 8 1966
42 931
3 8149 13 1966 50
3 2
1
. .
.
..
..
..
. .
x x
x
CHECK
okay...end of
problem
-
7/27/2019 KNT Linier Eq
69/114
GAUSS-JORDAN
Variation of Gauss elimination
Primary motive for introducing this method is that
it provides and simple and convenient method for
computing the matrix inverse.
When an unknown is eliminated, it is eliminatedfrom all other equations, rather than just the
subsequent one
-
7/27/2019 KNT Linier Eq
70/114
GAUSS-JORDAN
All rows are normalized by dividing them by their
pivot elements
Elimination step results in and identity matrix
rather than an UT matrix
Aa a a
a a
a
11 12 13
22 23
33
0
0 0 A
1 0 0 0
0 1 0 0
0 0 1 0
0 0 0 1
-
7/27/2019 KNT Linier Eq
71/114
1 0 00 1 0
0 0 1
1
1
2
3
1
2 2
3 3
||
|
cc
c
x c
x c
x c
n
n
n
n
n
n
Graphical depiction of Gauss-Jordan
a a a ca a a c
a a a c
c
cc
n
n
n
11 12 13 1
21 22 23 2
31 32 33 3
2
3
1 0 0
0 1 00 0 1
1
||
|
|
||
' ' '
' ' ' '
-
7/27/2019 KNT Linier Eq
72/114
Matrix Inversion
[A] [A] -1 = [A]-1 [A] = I
One application of the inverse is to solve
several systems differing only by {c}
[A]{x} = {c}
[A]-1[A] {x} = [A]-1{c}
[I]{x}={x}= [A]-1{c}
One quick method to compute the inverse isto augment [A] with [I] instead of {c}
-
7/27/2019 KNT Linier Eq
73/114
Graphical Depiction of the Gauss-Jordan
Method with Matrix Inversion
A I
a a a
a a a
a a a
a a a
a a a
a a a
I A
11 12 13
21 22 23
31 32 33
11
1
12
1
13
1
21
1
22
1
23
1
311
321
331
1
1 0 0
0 1 0
0 0 1
1 0 0
0 1 0
0 0 1
Note: the superscript
-1 denotes thatthe original values
have been converted
to the matrix inverse,
not 1/aij
-
7/27/2019 KNT Linier Eq
74/114
LU Decomposition Methods
Elimination methods
Gauss eliminationGauss Jordan
LU Decomposition Methods
-
7/27/2019 KNT Linier Eq
75/114
Naive LU Decomposition
[A]{x}={c}
Suppose this can be rearranged as an upper
triangular matrix with 1s on the diagonal
[U]{x}={d}
[A]{x}-{c}=0 [U]{x}-{d}=0
Assume that a lower triangular matrix existsthat has the property
[L]{[U]{x}-{d}}= [A]{x}-{c}
-
7/27/2019 KNT Linier Eq
76/114
Naive LU Decomposition
[L]{[U]{x}-{d}}= [A]{x}-{c}
Then from the rules of matrix multiplication
[L][U]=[A] [L]{d}={c}
[L][U]=[A] is referred to as the LU
decomposition of [A]. After it isaccomplished, solutions can be obtained
very efficiently by a two-step substitution
procedure
-
7/27/2019 KNT Linier Eq
77/114
Consider how Gauss elimination can be
formulated as an LU decomposition
U is a direct product of forward
elimination step if each row is scaled bythe diagonal
Ua a
a
1
0 1
0 0 1
12 13
23
-
7/27/2019 KNT Linier Eq
78/114
Although not as apparent, the matrix [L] is also
produced during the step. This can be readily
illustrated for a three-equation system
a a a
a a a
a a a
x
x
x
c
c
c
11 12 13
21 22 23
31 32 33
1
2
3
1
2
3
The first step is to multiply row 1 by the factor
fa
a21
21
11
Subtracting the result from the second row eliminates a21
-
7/27/2019 KNT Linier Eq
79/114
a a a
a a a
a a a
x
x
x
c
c
c
11 12 13
21 22 23
31 32 33
1
2
3
1
2
3
Similarly, row 1 is multiplied by
fa
a31
31
11
The result is subtracted from the third row to eliminate a31In the final step for a 3 x 3 system is to multiply the modified
row by
fa
a32
32
22
'
'Subtract the results from the third
row to eliminate a32
-
7/27/2019 KNT Linier Eq
80/114
The values f21, f31, f32 are in fact the elements
of an [L] matrix
L ff f
1 0 0
1 0
1
21
31 32
CONSIDER HOW THIS RELATES TO THE
LU DECOMPOSITION METHOD TO SOLVEFOR {X}
-
7/27/2019 KNT Linier Eq
81/114
[A] {x} = {c}
[U][L]
[L] {d} = {c}
{d}
[U]{x}={d} {x}
-
7/27/2019 KNT Linier Eq
82/114
Crout Decomposition
Gauss elimination method involves two
major steps
forward elimination
back substitution
Efforts in improvement focused on
development of improved elimination
methods One such method is Crout decomposition
-
7/27/2019 KNT Linier Eq
83/114
Crout Decomposition
Represents and efficient algorithm for decomposing [A]
into [L] and [U]
l
l l
l l l
u u
u
a a a
a a a
a a a
11
21 22
31 32 33
12 13
23
11 12 13
21 22 23
31 32 33
0 0
0
1
0 1
0 0 1
-
7/27/2019 KNT Linier Eq
84/114
l
l l
l l l
u u
u
a a a
a a a
a a a
11
21 22
31 32 33
12 13
23
11 12 13
21 22 23
31 32 33
0 0
0
1
0 1
0 0 1
Recall the rules of matrix multiplication.
The first step is to multiply the rows of [L] by the
first column of [U]
a l la la l
11 11 11
21 21
31 31
1 0 0 0 0
Thus the first
column of [A]is the first column
of [L]
-
7/27/2019 KNT Linier Eq
85/114
l
l l
l l l
u u
u
a a a
a a a
a a a
11
21 22
31 32 33
12 13
23
11 12 13
21 22 23
31 32 33
0 0
0
1
0 1
0 0 1
Next we multiply the first row of [L] by the column
of [U] to get
l a
l u a
l u a
11 11
11 12 12
11 13 13
-
7/27/2019 KNT Linier Eq
86/114
l a
l u al u a
u
a
l
ua
l
ua
lfor j nj
j
11 11
11 12 12
11 13 13
12
12
11
1313
11
1
1
11
2 3
, ,.....
l
l ll l l
u u
u
a a a
a a aa a a
11
21 22
31 32 33
12 13
23
11 12 13
21 22 23
31 32 33
0 0
0
1
0 10 0 1
Once the first row of [U] is established
the operation can be represented concisely
-
7/27/2019 KNT Linier Eq
87/114
l a for i n
u al
for j n
For j n
l a l u for i j j n
u
a l u
lfor k j j n
l a l u
i il
jj
ij ij ik kjk
j
jk
jk ji ik
i
j
jj
nn nn nk kn
k
n
1
11
11
1
1
1
1
1
1
1 2
2 3
2 3 1
1
1 2
, ,.....,
, , .....
, ......
, ,.....
, ....
-
7/27/2019 KNT Linier Eq
88/114
The Substitution Step
[L]{[U]{x}-{d}}= [A]{x}-{c}
[L][U]=[A]
[L]{d}={c}
[U]{x}={d}
Recall our earlier graphical depiction of the
LU decomposition method
-
7/27/2019 KNT Linier Eq
89/114
[A] {x} = {c}
[U][L]
[L] {d} = {c}
{d}
[U]{x}={d} {x}
-
7/27/2019 KNT Linier Eq
90/114
dc
l
d
c l d
l
for i n
Back substitution recall U x d
x d
x d u x for i n n n
i
i ij j
j
i
ii
n n
i i ij j
j i
n
11
11
1
1
1
2 3
1 2
, ,......
, ,.....
P t d t tif th
-
7/27/2019 KNT Linier Eq
91/114
Parameters used to quantify the
dimensions of a banded system.
BW = band width
HBW = half band width
BW
HBW
Diagonal
Thomas Algorithm
-
7/27/2019 KNT Linier Eq
92/114
Thomas Algorithm
As with conventional LU decomposition methods, thealgorithm consist of three steps
- decomposition
- forward substitution
- back substitution
Want a scheme to reduce the large inefficient use of
storage involved with banded matrices
Consider the following tridiagonal system
-
7/27/2019 KNT Linier Eq
93/114
a a
a a a
a a a
a a aa a
x
x
x
x
c
c
c
c
n n n n n n
n n nn n n
11 12
21 22 23
32 33 34
1 2 1 1 1
1
1
2
3
1
2
3
. . .
. . .
. . .
.
.
.
.
.
.
.
., , ,
,
Note how this tridiagonal system require the storage of a large
number of zero values.
-
7/27/2019 KNT Linier Eq
94/114
f g
e f g
e f g
e f g
e f
e
e
e
f
f
f
f
g
g
g
n n n
n n n n
1 1
2 2 2
3 3 3
1 1 1
2
3
1
2
3
1
2
3
0
0
. . .
. . .
. . .
.
.
.
.
.
.
.
.
.
.
.
.
Note that we have changed our notation of as to e,f,g
In addition we have changed our notation of cs to r
-
7/27/2019 KNT Linier Eq
95/114
0
0
0
0
2
3
1
2
3
1
2
3
12 13
21 22 23
31 32 33
1 2
e
e
e
f
f
f
f
g
g
g
b b
b b b
b b b
b bn n n n
.
.
.
.
.
.
.
.
.
.
.
.
. . .
. . .
. . .
. . .
Storage is even further reduced if the matrix is banded and
symmetric. Only elements on the diagonal and in the upper
half need be stored.
Storage can
be accomplishedby either storage
as vector (e,f,g)
or as a compact
matrix [B]
-
7/27/2019 KNT Linier Eq
96/114
Gauss Seidel Method
An iterative approach
Continue until we converge within some pre-
specified tolerance of error
Round off is no longer an issue, since you
control the level of error that is acceptable
Fundamentally different from Gauss eliminationthis is an approximate, iterative method
particularly good for large number of equations
-
7/27/2019 KNT Linier Eq
97/114
Gauss-Seidel Method
If the diagonal elements are all nonzero, the
first equation can be solved for x1
Solve the second equation for x2, etc.
x c a x a x a xa
n n1
1 12 2 13 3 1
11
To assure that you understand this, write the equation for x2
-
7/27/2019 KNT Linier Eq
98/114
x
c a x a x a x
a
xc a x a x a x
a
x c a x a x a xa
x c a x a x a xa
n n
n n
n n
nn n n nn n
nn
1
1 12 2 13 3 1
11
2
2 21 1 23 3 2
22
3
3 31 1 32 2 3
33
1 1 3 2 1 1
G S id l M th d
-
7/27/2019 KNT Linier Eq
99/114
Gauss-Seidel Method
Start the solution process by guessingvalues of x
A simple way to obtain initial guesses is to
assume that they are all zero Calculate new values of xi starting with
x1 = c1/a11
Progressively substitute through theequations
Repeat until tolerance is reached
-
7/27/2019 KNT Linier Eq
100/114
x c a x a x a
x c a x a x ax c a x a x a
x c a a a
c
a x
x c a x a a x
x c a x a x a x
1 1 12 2 13 3 11
2 2 21 1 23 3 22
3 3 31 1 32 2 33
1 1 12 13 11
1
11 1
2 2 21 1 23 22 2
3 3 31 1 32 2 33 3
0 0
0
/
//
/ '
' / '
' ' / '
-
7/27/2019 KNT Linier Eq
101/114
Given the following augmented matrix,complete one iteration of the Gauss
Seidel method.
2 3 1 2
4 1 2 2
3 2 1 1
EXAMPLE
G S id l M th d
-
7/27/2019 KNT Linier Eq
102/114
Gauss-Seidel Method
convergence criterion a i
i
j
i
j
i
j s
x x
x,
1
100
as in previous iterative procedures in finding the roots,we consider the present and previous estimates.
As with the open methods we studied previously with one
point iterations
1. The method can diverge
2. May converge very slowly
C i i f
-
7/27/2019 KNT Linier Eq
103/114
Convergence criteria for two
linear equations
u x xc
a
a
ax
v x xc
a
a
ax
consider the partial derivatives of u and v
u
x
u
x
a
a
v
x
a
a
v
x
1 21
11
12
11
2
1 22
22
21
22
2
1 2
12
11
1
21
22 2
0
0
,
,
Convergence criteria for two
-
7/27/2019 KNT Linier Eq
104/114
Convergence criteria for two
linear equations
u x xc
a
a
ax
v x x ca aa x
consider the partial derivatives of u and v
u
x
u
x
a
a
v
x
a
a
v
x
1 21
11
12
11
2
1 2 2
22
21
22
1
1 2
12
11
1
21
22 2
0
0
,
,
Class question:
where do these
formulas come from?
Convergence criteria for two linear
-
7/27/2019 KNT Linier Eq
105/114
Convergence criteria for two linear
equations cont.
u
x
v
x
uy
vy
1
1
Criteria for convergence
where presented earlier
in class materialfor nonlinear equations.
Noting that x = x1 and
y = x2
Substituting the previous equation:
Convergence criteria for two linear
-
7/27/2019 KNT Linier Eq
106/114
Convergence criteria for two linear
equations cont.
a
a
a
a
21
22
12
11
1 1
This is stating that the absolute values of the slopes must
be less than unity to ensure convergence.
Extended to n equations:
a a where j n excluding j iii ij 1,
Convergence criteria for two linear
-
7/27/2019 KNT Linier Eq
107/114
Convergence criteria for two linear
equations cont.
a a where j n excluding j iii ij 1,
This condition is sufficient but not necessary; for convergence.
When met, the matrix is said to be diagonally dominant.
-
7/27/2019 KNT Linier Eq
108/114
x2
x1
Review the concepts
of divergence andconvergence by graphically
illustrating Gauss-Seidel
for two linear equations
u x x
v x x
:
:
11 13 286
11 9 99
1 2
1 2
-
7/27/2019 KNT Linier Eq
109/114
x2
x1
Note: we are converging
on the solution
v x x
u x x
:
:
11 9 99
11 13 286
1 2
1 2
-
7/27/2019 KNT Linier Eq
110/114
x2
x1
Change the order of
the equations: i.e. change
direction of initialestimates
This solution is diverging!
u x x
v x x
:
:
11 13 286
11 9 99
1 2
1 2
I f C
-
7/27/2019 KNT Linier Eq
111/114
Improvement of Convergence
Using Relaxation
This is a modification that will enhance slow convergence.
After each new value of x is computed, calculate a new valuebased on a weighted average of the present and previous
iteration.
x x xinew
inew
iold
1
Improvement of Convergence Using
-
7/27/2019 KNT Linier Eq
112/114
Improvement of Convergence Using
Relaxation
if = 1unmodified
if 0 < < 1 underrelaxationnonconvergent systems may converge
hasten convergence by dampening out oscillations
if 1< < 2 overrelaxation
extra weight is placed on the present value
assumption that new value is moving to the correct
solution by too slowly
x x xinew inew iold 1
-
7/27/2019 KNT Linier Eq
113/114
Jacobi Iteration
Iterative like Gauss Seidel
Gauss-Seidel immediately uses the value of
xi in the next equation to predict x i+1 Jacobi calculates all new values of xis to
calculate a set of new xi values
Graphical depiction of difference between Gauss-Seidel and Jacobi
-
7/27/2019 KNT Linier Eq
114/114
FIRST ITERATION
x c a x a x a x c a x a x a
x c a x a x a x c a x a x a
x c a x a x a x c a x a x a
SECOND ITERATION
x c a x a x a x c a x a x a
x c a x a x a x c a x
1 1 12 2 13 3 11 1 1 12 2 13 3 11
2 2 21 1 23 3 22 2 2 21 1 23 3 22
3 3 31 1 32 2 33 3 3 31 1 32 2 33
1 1 12 2 13 3 11 1 1 12 2 13 3 11
2 2 21 1 23 3 22 2 2 21 1
/ /
/ /
/ /
/ /
/
a x a23 3 22/
/ /
top related