slide03s

7/23/2019 Slide03S

1/36

2013/9/9

T O P I C : G A U S S - S E I D E L M E T H O D

SIMULTANEOUS LINEAR EQUATIONS

7/23/2019 Slide03S

2/36

GAUSS-SEIDEL METHOD

Adalah metode ITERASI

Prosedur dasar:

- Menyelesaikan tiap persamaan linier secara aljabar untuk xi

- Membuat nilai asumsi solusi

- Selesaikan untuk tiap xidan ulangi

- Gunakan perkiraan kesalahan relatif tiap akhir iterasi untukmengecek apakah error sudah mencapai angka toleransi.

7/23/2019 Slide03S

3/36

GAUSS-SEIDEL METHOD

Kenapa?

Untuk mengatasi round-off error(kesalahan pembulatan).

Metode eliminasi seperti Gaussian Elimination and LU

Decomposition(*) rawan terhadap kesalahan pembulatan.

7/23/2019 Slide03S

4/36

GAUSS-SEIDEL METHOD

AlgorithmSistem persamaan linier

11313212111 ... bxaxaxaxa nn

2323222121 ... bxaxaxaxa n2n

nnnnnnn bxaxaxaxa ...332211

. .

. .

. . Kita mengubah sistempersamaan [A]{X}={B}untuk menyelesaikanx1

dengan persamaanpertama, menyelesaikanx2 dengan persamaankedua, dan seterusnya.

7/23/2019 Slide03S

5/36

GAUSS-SEIDEL METHOD

AlgorithmGeneral Form of each equation

11

11

11

1a

xac

x

n

jj

jj

22

21

22

2a

xac

x

j

n

jj

j

1,1

11

,11

1

nn

n

njj

jjnn

na

xac

x

nn

n

njj

jnjn

na

xac

x

1

7/23/2019 Slide03S

6/36

MENJADI:

33

2321313

3

22

3231212

2

11

3132121

1

a

xaxabx

a

xaxab

x

a

xaxabx

Now we can start the solution process bychoosing guesses for the xs. A simple way toobtain initial guesses is to assume that they arezero. These zeros can be substituted into

x1equation to calculate a newx1=b1/a11.

Untuk sistempersamaan 3x3

7/23/2019 Slide03S

7/36

7/23/2019 Slide03S

8/36

BATAS AKHIR ITERASI

New x1is substituted to calculate x2and x3. The procedure isrepeated until the convergence criterion is satisfied:

kandiperkenanbaru

i

lama

i

baru

i

ia x

xx 100

t

a

approximation error, sering digunakan, seringkali

disebut sebagai galata

bsolut.

True error, kurang berarti. digunakan Relative error,

dalam prosentase

7/23/2019 Slide03S

9/36

GAUSS-SEIDEL METHOD: EXAMPLE 1

2.279

2.177

8.106

x

x

x

112144

1864

1525

3

2

1

Diketahui sistem persamaan

Initial Guess: asumsi nilai awal,

5

2

1

3

2

1

x

x

x

7/23/2019 Slide03S

10/36


2.279

2.177

8.106

x

x

x

112144

1864

1525

3

2

1

Tulis ulang untuk aplikasi

Gauss-Seidel

25

58.106 321

xxx

8

642.177 312

xxx

1

121442.279 213

xxx

7/23/2019 Slide03S

11/36


Masukkan nilai perkiraan awal untuk selesaikan xi

5

2

1

3

2

1

x

x

x

6720.325

)5()2(58.1061

x

8510.7

8

56720.3642.1772

x

36.155

1

8510.7126720.31442.279

3

xInitial Guess

7/23/2019 Slide03S

12/36


36.155

8510.7

6720.3

3

2

1

a

a

a

100x

xxnew

i

old

i

new

i

ia

%76.72100x6720.3

0000.16720.31

a

%47.125100x8510.7

0000.28510.72

a

%22.103100x36.155

0000.536.1553

a

Finding the absolute relative approximate error

At the end of the first iteration

The maximum absolute

relative approximate error is

125.47%

7/23/2019 Slide03S

13/36


36.155

8510.7

6720.3

3

2

1

a

a

a

Iteration #2Using

056.1225

36.1558510.758.1061

a

882.54

8

36.155056.12642.1772

a

34.798

1

882.5412056.121442.2793

a

from iteration #1

the values of aiare found:

7/23/2019 Slide03S

14/36


Hitung the absolute relative approximate error

%542.69100x056.12

6720.3056.121

a

%695.85100x

882.54

8510.7882.542

a

%54.80100x34.79836.15534.7983 a

Akhir iterasi kedua

34.798

882.54

056.12

3

2

1

a

a

a

Galat absolut terbesar

85.695%

7/23/2019 Slide03S

15/36


Tersukan iterasi, kita dapatkan nilai berikut.

Iteration a1 a2 a3

1

2

3

4

5

6

3.672

12.056

47.182

193.33

800.53

3322.6

72.767

67.542

74.448

75.595

75.850

75.907

-7.8510

-54.882

-255.51

-1093.4

-4577.2

-19049

125.47

85.695

78.521

76.632

76.112

75.971

-155.36

-798.34

-3448.9

-14440

-60072

-249580

103.22

80.540

76.852

76.116

75.962

75.931

%1a

%2a

%3

a

! Lho, kok?Error nya nggak berkurang?

7/23/2019 Slide03S

16/36

GAUSS-SEIDEL METHOD: PITFALL

Salahnya dimana?

Contoh tadi mengilustrasikan kemungkinan kesalahan pada

Gauss-Siedel method: tidak semua sistem persamaan akan

konvergen.Is there a fix?

One class of system of equations always converges: One with a

diagonally dominant coefficient matrix.

Diagonally dominant: [A] in [A] [X] = [C] is diagonally dominant

if:

n

jj

ijaa

i1

ii

n

ijj

ijii aa1

Untuk semua i ; DAN Untuk minimal

sebuah i

7/23/2019 Slide03S

17/36

GAUSS-SEIDEL METHOD: PITFALL

116123

14345

3481.52

A

1293396

55323

5634124

][

B

Diagonally dominant: Koefisien pada diagonal harus sama atau lebihbesar dari jumlah semua koefisien pada baris itu, dan minimal satu baris

harus memiliki diagonal yang lebih besar dari jumlah koefisien pada

baris itu.

Manakah matriks yang diagonally dominant?

7/23/2019 Slide03S

18/36


Sistem persamaan linier

15x-3x12x 321

283x5xx 321

7613x7x3x 321

1

0

1

3

2

1

x

x

x

Dengan asumsi nilai awal

Matriks Koefisien nya

adalah

1373351

5312

A

Akan konvergen kah?

7/23/2019 Slide03S

19/36


1373

351

5312

A

Cek apakah matriks nya diagonally dominant

43155 232122 aaa

10731313 323133 aaa

8531212 131211 aaa

Benar. Seharusnya konvergen dengan Gauss-Siedel Method

7/23/2019 Slide03S

20/36


76

28

1

1373

351

5312

3

2

1

a

a

a

1

0

1

3

2

1

x

x

x

Tulis ulang

12

531 321

xxx

5

328 312

xxx

13

7376 213

xxx

Asumsi nilai awal

50000.0

12

150311

x

9000.4

5

135.028

2

x

0923.3

13

9000.4750000.03763

x

7/23/2019 Slide03S

21/36


The absolute relative approximate error

%662.6710050000.0

0000.150000.01a

%00.1001009000.4

09000.42a

%662.671000923.3

0000.10923.33a

Galat absolut terbesar di akhir iterasi pertama adalah 100%

7/23/2019 Slide03S

22/36


8118.3

7153.3

14679.0

3

2

1

x

x

x

0923.3

9000.4

5000.0

3

2

1

x

x

x

Setelah iterasi #1

14679.0

12

0923.359000.4311

x

7153.35

0923.3314679.0282 x

8118.3

13

7153.3714679.03763

x

Masukkan nilai x pada persamaan Setelah iterasi #2

7/23/2019 Slide03S

23/36


Galat absolut dari Iterasi #2

%62.24010014679.0

50000.014679.01

a

%887.311007153.3

9000.47153.32 a

%876.181008118.3

0923.38118.33

a

Galat absolut maksimum 240.62%

Lebih besar dari iterasi #1. Is this a problem?

7/23/2019 Slide03S

24/36


Ulangi iterasi, didapatkan

1a

2a

3a

Iteration a1 a2 a3

1

23

4

5

6

0.50000

0.146790.74275

0.94675

0.99177

0.99919

67.662

240.6280.23

21.547

4.5394

0.74260

4.900

3.71533.1644

3.0281

3.0034

3.0001

100.00

31.88717.409

4.5012

0.82240

0.11000

3.0923

3.81183.9708

3.9971

4.0001

4.0001

67.662

18.8764.0042

0.65798

0.07499

0.00000

4

3

1

3

2

1

x

x

x

0001.4

0001.3

99919.0

3

2

1

x

x

x

Hasil akhir Mendekati solusi sejati

7/23/2019 Slide03S

25/36

LATIHAN

1

0

1

3

2

1

x

x

x

Sistem persamaan linier

7613x7x3x321

283x5xx 321

15x-3x12x 321 With an initial guess of

7/23/2019 Slide03S

26/36

GAUSS-SEIDEL METHOD

1373

351

5312

A

The Gauss-Seidel Method can still be used

The coefficient matrix is not

diagonally dominant

5312

351

1373

A

But this is the same set of

equations used in example #2,

which did converge.

If a system of linear equations is not diagonally dominant, check to see if

rearranging the equations can form a diagonally dominant matrix.

7/23/2019 Slide03S

27/36

GAUSS-SEIDEL METHOD

Not every system of equations can be rearranged to have a

diagonally dominant coefficient matrix.

Observe the set of equations

3321 xxx

9432 321 xxx

97 321 xxx

Which equation(s) prevents this set of equation from having a

diagonally dominant coefficient matrix?

7/23/2019 Slide03S

28/36

GAUSS-SEIDEL METHOD

Summary

-Advantages of the Gauss-Seidel Method

-Algorithm for the Gauss-Seidel Method

-Pitfalls of the Gauss-Seidel Method

7/23/2019 Slide03S

29/36

GAUSS-SEIDEL METHOD

Questions?

7/23/2019 Slide03S

30/36

METODE PENYELESAIAN

Metode grafik

Eliminasi Gauss

Metode GaussJourdan

Metode GaussSeidel LU decomposition

7/23/2019 Slide03S

31/36

LU DECOMPOSITION

A=LU

Ax=bLUx=b

Define Ux=yLy=b Solve y by forward substitution

Ux=y Solve x by backward substitution

7/23/2019 Slide03S

32/36

LU DECOMPOSITION BY GAUSSIAN

ELIMINATION

)(

)(

1

)(

11

)3(

3

)3(

33

)2(

2

)2(

23

)2(

22

)1(

1

)1(

13

)1(

12

)1(

11

4,3,2,1,

3,12,11,1

2,31,3

1,2

0000

000

00

0

1

1

0

001

000100001

n

nn

n

nn

n

nn

n

n

n

nnnn

nnn

a

aa

aa

aaaaaaa

mmmm

mmm

mm

m

A

Compact storage:The diagonal entries of L matrix are all 1s,they dont need to be stored. LU is stored in a single matrix.

There are infinitely many different ways to decompose A.Most popular one: U=Gaussian eliminated matrix

L=Multipliers used for elimination

7/23/2019 Slide03S

33/36

NEXT: SOLUSI PERSAMAAN NON

LINIER

Persamaan matematis yang sulit diselesaikandengan tangananalitis, sehingga diperlukanpenyelesaian pendekatannumerik

Metode Numerik: Teknik menyelesaikan masalahmatematika dengan pengoperasian hitungan,umumnya mencakup sejumlah besar kalkulasiaritmetika yang sangat banyak dan menjenuhkan

Diselesaikan dengan algoritma (serangkaianperintah untuk menyelesaikan masalah), sehinggadiperlukan bantuan komputer untukmelaksanakannya

7/23/2019 Slide03S

34/36

SUMBER GALAT / ERROR

Kesalahan pemodelan

contoh: penggunaan hukum Newton

asumsi benda adalah partikel

Kesalahan bawaancontoh: kekeliruan dlm menyalin data

salah membaca skala

Ketidaktepatan data

Kesalahan pemotongan / penyederhanaanpersamaan(truncation error)

Kesalahan pembulatan (round-off error)

7/23/2019 Slide03S

35/36

SOLUSI PERSAMAAN NON

LINEAR1)Metode Akolade (bracketing method)/ Closed method

Metode Bagi dua (Bisection Method)Metode Regula Falsi (False Position

Method)

Metode Grafik

Keuntungan: selalu konvergen

Kerugian: relatif lambat konvergen

7/23/2019 Slide03S

36/36

SOLUSI PERSAMAAN NON

LINEAR2) Metode Terbuka

Contoh: Iterasi Titik-Tetap (Fix Point Iteration)

Metode Newton-RaphsonMetode Secant

Keuntungan: cepat konvergen

Kerugian: tidak selalu konvergen

slide03s

Documents