SIMULTANEOUS LINEAR EQUATIONS

SIMULTANEOUS LINEAR EQUATIONS TOPIC: GAUSS-SEIDEL METHOD

2013/9/9

GAUSS-SEIDEL METHOD Adalah metode ITERASI Prosedur dasar: - Menyelesaikan tiap persamaan linier secara aljabar untuk xi - Membuat nilai asumsi solusi - Selesaikan untuk tiap xi dan ulangi - Gunakan perkiraan kesalahan relatif tiap akhir iterasi untuk mengecek apakah error sudah mencapai angka toleransi.

GAUSS-SEIDEL METHOD Kenapa? Untuk mengatasi round-off error (kesalahan pembulatan).

Metode eliminasi seperti Gaussian Elimination and LU Decomposition(*) rawan terhadap kesalahan pembulatan.

GAUSS-SEIDEL METHOD Algorithm Sistem persamaan linier

a11x1  a12x2  a13x3  ...  a1n xn  b1 a21x1  a22 x2  a23x3  ...  a2n xn  b2 . . .

. . .

an1x1  an 2 x2  an3 x3  ...  ann xn  bn

Kita mengubah sistem persamaan [A]{X}={B} untuk menyelesaikan x1 dengan persamaan pertama, menyelesaikan x2 dengan persamaan kedua, dan seterusnya.

GAUSS-SEIDEL METHOD Algorithm General Form of each equation n

c1   a1 j x j x1 

j 1 j 1

a11

cn 1  xn 1 

n

a

j 1 j  n 1

n 1, j

an 1,n 1 n

c n   a nj x j

n

c2   a2 j x j x2 

j 1 j2

a 22

xj

xn 

j 1 j n

a nn

MENJADI: Untuk sistem persamaan 3x3

b1  a12 x2  a13 x3 x1  a11 b2  a21x1  a23 x3 x2  a22 b3  a31x1  a32 x2 x3  a33

Now we can start the solution process by choosing guesses for the x’s. A simple way to obtain initial guesses is to assume that they are zero. These zeros can be substituted into x1equation to calculate a new x1=b1/a11.

BATAS AKHIR ITERASI New x1 is substituted to calculate x2 and x3. The procedure is repeated until the convergence criterion is satisfied:

a i 

x

baru i

lama i

x

baru i

x

100   diperkenankan

a 

approximation error, sering digunakan, seringkali disebut sebagai galat absolut.

t 

True error, kurang berarti.  digunakan Relative error, dalam prosentase

GAUSS-SEIDEL METHOD: EXAMPLE 1

Diketahui sistem persamaan

Initial Guess: asumsi nilai awal,

 25 5 1  x1  106.8   64 8 1  x   177.2     2   144 12 1  x 3  279.2

 x1  1   x    2  2    x3  5

GAUSS-SEIDEL METHOD: EXAMPLE 1 Tulis ulang untuk aplikasi Gauss-Seidel

 25 5 1  x1  106.8   64 8 1  x   177.2     2   144 12 1  x 3  279.2

106.8  5 x2  x3 x1  25 177.2  64 x1  x3 x2  8 279.2  144 x1  12 x2 x3  1

GAUSS-SEIDEL METHOD: EXAMPLE 1 Masukkan nilai perkiraan awal untuk selesaikan xi  x1  1   x    2  2    x3  5 Initial Guess

x1 

106.8  5(2)  (5)  3.6720 25

177.2  643.6720  5 x2   7.8510 8 279.2  1443.6720  12 7.8510 x3   155.36 1

GAUSS-SEIDEL METHOD: EXAMPLE 1 Finding the absolute relative approximate error

a

i

x inew  x iold  100 new xi

a 1 

3.6720  1.0000 x100  72.76% 3.6720

a 2 

 7.8510  2.0000 x100  125.47%  7.8510

a 3 

 155.36  5.0000 x100  103.22%  155.36

At the end of the first iteration

 a1   3.6720  a    7.8510  2    a3    155.36  The maximum absolute relative approximate error is 125.47%

GAUSS-SEIDEL METHOD: EXAMPLE 1 Iteration #2 Using

 a1   3.6720  a    7.8510  2    a3    155.36 

the values of ai are found:

106.8  5 7.8510  155.36 a1   12.056 25

from iteration #1

a2 

177.2  6412.056  155.36  54.882 8

279.2  14412.056  12 54.882 a3   798.34 1

GAUSS-SEIDEL METHOD: EXAMPLE 1 Hitung “the absolute relative approximate error” a 1 

12.056  3.6720 x100  69.542% 12.056

a 2 

 54.882   7.8510 x100  85.695%  54.882

a 3 

 798.34   155.36 x100  80.54%  798.34

Akhir iterasi kedua

 a1   12.056  a    54.882  2    a3   798.34 Galat absolut terbesar 85.695%

GAUSS-SEIDEL METHOD: EXAMPLE 1 Tersukan iterasi, kita dapatkan nilai berikut. Iteration

1 2 3 4 5 6

a1 3.672 12.056 47.182 193.33 800.53 3322.6

a 1 % 72.767 67.542 74.448 75.595 75.850 75.907

a2 -7.8510 -54.882 -255.51 -1093.4 -4577.2 -19049

a 2 % 125.47 85.695 78.521 76.632 76.112 75.971

! Lho, kok? – Error nya nggak berkurang?

a3 -155.36 -798.34 -3448.9 -14440 -60072 -249580

a 3 % 103.22 80.540 76.852 76.116 75.962 75.931

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

n

aii   aij j 1 j i

Untuk semua ‘i’ ;

DAN

aii   aij j 1 j i

Untuk minimal sebuah ‘i’

GAUSS-SEIDEL METHOD: PITFALL Diagonally dominant: Koefisien pada diagonal harus sama atau lebih besar 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?  2 5.81 34 A   45 43 1  123 16 1 

124 34 56  [ B]   23 53 5   96 33 129

GAUSS-SEIDEL METHOD: EXAMPLE 2 Sistem persamaan linier

12x1  3x 2 - 5x 3  1

x1  5x 2  3x 3  28 3x1  7x2  13x3  76

Matriks Koefisien nya adalah

12 3  5 A   1 5 3   3 7 13 

Dengan asumsi nilai awal

 x1  1  x   0   2    x3  1

Akan konvergen kah?

GAUSS-SEIDEL METHOD: EXAMPLE 2 Cek apakah matriks nya diagonally dominant 12 3  5 A   1 5 3   3 7 13 

a11  12  12  a12  a13  3   5  8

a22  5  5  a21  a23  1  3  4 a33  13  13  a31  a32  3  7  10

Benar. Seharusnya konvergen dengan Gauss-Siedel Method

GAUSS-SEIDEL METHOD: EXAMPLE 2 Tulis ulang

Asumsi nilai awal

12 3  5  a1   1   1 5 3  a   28    2    3 7 13  a3  76

1  3 x 2  5 x3 x1  12 28  x1  3x3 x2  5 76  3x1  7 x2 x3  13

 x1  1  x   0   2    x3  1

x1 

x2 

1  30  51  0.50000 12

28  0.5  31  4.9000 5

76  30.50000  74.9000 x3   3.0923 13

GAUSS-SEIDEL METHOD: EXAMPLE 2 The absolute relative approximate error

0.50000  1.0000 a 1  100  67.662% 0.50000

a a

2

3

4.9000  0  100  100.00% 4.9000 3.0923  1.0000  100  67.662% 3.0923

Galat absolut terbesar di akhir iterasi pertama adalah 100%

GAUSS-SEIDEL METHOD: EXAMPLE 2 Setelah iterasi #1  x1  0.5000  x   4.9000  2    x3  3.0923

Masukkan nilai x pada persamaan  x1  0.14679  x    3.7153   2    x3   3.8118 

x1 

1  34.9000  53.0923  0.14679 12

x2 

28  0.14679  33.0923  3.7153 5

x3 

76  30.14679  73.7153  3.8118 13

Setelah iterasi #2

GAUSS-SEIDEL METHOD: EXAMPLE 2 Galat absolut dari Iterasi #2 a 1 

0.14679  0.50000 100  240.62% 0.14679

a 2 

3.7153  4.9000 100  31.887% 3.7153

a 3 

3.8118  3.0923 100  18.876% 3.8118

Galat absolut maksimum 240.62%

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

GAUSS-SEIDEL METHOD: EXAMPLE 2 Ulangi iterasi, didapatkan… Iteration 1 2 3 4 5 6

a1 0.50000 0.14679 0.74275 0.94675 0.99177 0.99919

 x1  0.99919 Hasil akhir  x    3.0001   2    x3   4.0001 

a 1

a2

67.662 240.62 80.23 21.547 4.5394 0.74260

4.900 3.7153 3.1644 3.0281 3.0034 3.0001

a

a3 2

100.00 31.887 17.409 4.5012 0.82240 0.11000

3.0923 3.8118 3.9708 3.9971 4.0001 4.0001

a

3

67.662 18.876 4.0042 0.65798 0.07499 0.00000

 x1  1  Mendekati solusi sejati  x   3  2    x3  4

LATIHAN Sistem persamaan linier

3x1  7x2  13x3  76 x1  5x2  3x3  28  x1  1  x   0   2    x3  1

12x1  3x2 - 5x3  1 With an initial guess of

GAUSS-SEIDEL METHOD The Gauss-Seidel Method can still be used The coefficient matrix is not diagonally dominant

But this is the same set of equations used in example #2, which did converge.

 3 7 13  A   1 5 3  12 3  5 12 3  5 A   1 5 3   3 7 13 

If a system of linear equations is not diagonally dominant, check to see if rearranging the equations can form a diagonally dominant matrix.

GAUSS-SEIDEL METHOD Not every system of equations can be rearranged to have a diagonally dominant coefficient matrix. Observe the set of equations

x1  x2  x3  3 2 x1  3x2  4 x3  9

x1  7 x2  x3  9 Which equation(s) prevents this set of equation from having a diagonally dominant coefficient matrix?

GAUSS-SEIDEL METHOD

Summary -Advantages of the Gauss-Seidel Method -Algorithm for the Gauss-Seidel Method -Pitfalls of the Gauss-Seidel Method

GAUSS-SEIDEL METHOD

Questions?

METODE PENYELESAIAN • • • • •

Metode grafik Eliminasi Gauss Metode Gauss – Jourdan Metode Gauss – Seidel LU decomposition

LU DECOMPOSITION A=LU Ax=b LUx=b

Define Ux=y Ly=b

Solve y by forward substitution

Ux=y

Solve x by backward substitution

LU DECOMPOSITION BY GAUSSIAN ELIMINATION There are infinitely many different ways to decompose A. Most popular one: U=Gaussian eliminated matrix L=Multipliers used for elimination  1 m  2,1  m3,1 A   mn 1,1   mn ,1

0 1 m3, 2  mn 1, 2 mn , 2

0 0 1  mn 1,3 mn ,3

 0  0  0    1 mn , 4 

(1) 0 a11 0  0 0  0  0     0  1  0

(1) a12 ( 2) a22 0  0 0

(1) a13 ( 2) a23 ( 3) a33  0 0

    an( n1) n 1 0

a1(1n)   a2( 2n)  a3(3n)     an( n1) n   (n) ann 

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

NEXT: SOLUSI PERSAMAAN NON LINIER • Persamaan matematis yang sulit diselesaikan dengan “tangan”  analitis, sehingga diperlukan penyelesaian pendekatan  numerik • Metode Numerik: Teknik menyelesaikan masalah matematika dengan pengoperasian hitungan, umumnya mencakup sejumlah besar kalkulasi aritmetika yang sangat banyak dan menjenuhkan • Diselesaikan dengan algoritma (serangkaian perintah untuk menyelesaikan masalah), sehingga diperlukan bantuan komputer untuk melaksanakannya

SUMBER GALAT / ERROR • Kesalahan pemodelan contoh: penggunaan hukum Newton asumsi benda adalah partikel • Kesalahan bawaan contoh: kekeliruan dlm menyalin data salah membaca skala • Ketidaktepatan data • Kesalahan pemotongan / penyederhanaan persamaan(truncation error) • Kesalahan pembulatan (round-off error)

SOLUSI PERSAMAAN NON LINEAR 1)Metode Akolade (bracketing method) / Closed method

• Metode Bagi dua (Bisection Method) • Metode Regula Falsi (False Position Method) • Metode Grafik Kerugian: relatif lambat konvergen Keuntungan: selalu konvergen

SOLUSI PERSAMAAN NON LINEAR 2) Metode Terbuka Contoh: • Iterasi Titik-Tetap (Fix Point Iteration) • Metode Newton-Raphson • Metode Secant Keuntungan: cepat konvergen Kerugian: tidak selalu konvergen