knt linier eq

7/27/2019 KNT Linier Eq

1/114

KOMPUTASI NUMERIK

TERAPAN (KNT) - TK-091356

Sistem Persamaan Linear


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


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


4/114


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


5/114


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


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/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


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


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


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


11/114

Matrix Simetris

A

5 1 21 3 7

2 7 8

aij = aji untuk semua i danj


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


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


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


15/114

Lower Triangular Matrix

A

5 0 0

1 3 0

2 7 8

Semua elemen diatas main diagonal adalah

zero


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


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]


18/114


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

. . .

. . .

. . . . . .

. . . . . .

. . . . . .

. . .


19/114


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 :


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


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]


22/114

Matrix Inverse [A]

IAAAA 11


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


24/114

Determinants

Ditulis sebagai det A or |A|

Untuk matrix 2 x 2

bcaddc

ba


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


26/114

minor of aa a aa a a

a a a

32

11 12 13

21 22 23

31 32 33



Contoh : minor dari a32untuk matrix 3x3 :

Untuk elemen

a32 baris ke-iadalah baris 3


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





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





29/114


30/114


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


31/114

A a a a a313 1

12 23 22 131


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


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)


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


34/114

Hitung determinan matrix 3x3 dibawah.pertama, hitung menggunakan baris ke-1.

Kemudian coba menggunakan baris ke-2n.

516

234

971

Contoh


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


36/114

Bagaimana merepresentasikan suatu

sistem persamaan linier kedalam matrix

[A]{X} = {C}

dimana {X} dan {C} adalah vektor kolom


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


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 )


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


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


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?


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.


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-


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



45/114

SISTIM PERSAMAAN-PERSAMAAN LINEAR


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


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



47/114


PERSAMAAN


METODA-METODA:

METODA LANGSUNG: ELIMINASI GAUSS

GAUSS YORDAN

LU-DECOMPOSITION

MATRIXS INVERSION

METODA TAK LANGSUNG: YACOBI

GAUSS-SEIDEL



48/114



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.



49/114



)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



50/114



)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



51/114


)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):



52/114


PERSAMAAN


)1(

)1()1(

)1()(

rrr

r

rj

r

irrij

rij

aaaaa

)1(

)1()1(

)1()(

rrr

r

ir

r

rri

ri

aaccc


Formula Umum Eliminasi

r =1,2,., n-1.

i = r+1, ., n.

j = r+1, .., n



53/114


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





54/114



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



55/114


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



56/114



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



57/114



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.



58/114



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


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


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


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


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


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)


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


65/114

0 3 13 50

2 6 1 454 0 8 4

Pivot with equation

with largest an1


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


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


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


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


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


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

||

|

|

||

' ' '

' ' ' '


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}


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


74/114

LU Decomposition Methods

Elimination methods

Gauss eliminationGauss Jordan

LU Decomposition Methods


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}


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


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


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


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


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}


81/114

[A] {x} = {c}

[U][L]

[L] {d} = {c}

{d}

[U]{x}={d} {x}


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


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


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]


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


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


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

, ,.....,

, , .....

, ......

, ,.....

, ....


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


89/114

[A] {x} = {c}

[U][L]

[L] {d} = {c}

{d}

[U]{x}={d} {x}


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


91/114

Parameters used to quantify the

dimensions of a banded system.

BW = band width

HBW = half band width

BW

HBW

Diagonal

Thomas Algorithm


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


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.


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


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]


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


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


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


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


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

/

//

/ '

' / '

' ' / '


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


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


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

,

,



104/114


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


105/114


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:



106/114


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,



107/114


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.


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


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


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


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


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


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


114/114

FIRST ITERATION

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

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/

/ /

knt linier eq

Documents