Dr.Eng. Agus S. Muntohar Department of Civil Engineering

Pertemuan ke ke--7 Persamaan Linier Simultan 25 Oktober 2012

Metode Iterasi GaussGauss-Siedel Dr.Eng. Agus S. Muntohar Department of Civil Engineering

Metode Gauss Gauss--Seidel • Merupakan metode iterasi. iterasi. • Prosedur umum: umum: - Selesaikan secara aljabar variabel tidak diketahui xi masing--masing persamaan linier masing - Asumsikan suatu nilai awal pada setiap penyelesaian - Selesaikan masingmasing-masing xi dan ulangi - Hitung nilai mutlak dari kesalahan perkiraan relatif setelah masingmasing-masing iterasi sehingga kurang dari nilai toleransi. toleransi. Dr.Eng. Agus S. Muntohar Department of Civil Engineering

2

1

Metode Gauss Gauss--Seidel • Metode GaussGauss-Seidel Method membolehkan pengguna untuk mengkontrol round round--off error. error. • Metode eliminasi seperti Eliminasi Gauss dan Dekompoisi LU rentan terhadap round round--off error. error. • Juga, Juga, bila bentuk dari masalah dapat dipahami, dipahami, dapat ditentukan nilai perkiraan awal yang lebih dekat,, sehingga menghemat waktu iterasi. dekat iterasi. Dr.Eng. Agus S. Muntohar Department of Civil Engineering

3

Metode Gauss Gauss--Seidel: Algoritma • n persamaan dan n bilangan tak diketahui: diketahui:

a11 x1 + a12 x2 + a13 x3 + ... + a1n xn = b1 a21 x1 + a22 x2 + a23 x3 + ... + a2n xn = b2 . . .

. . .

an1 x1 + an 2 x2 + an 3 x3 + ... + ann xn = bn

• Jika element diagonal tidak nol nol,, tuliskan kembali masingmasingmasing persamaan untuk menyelesaikan bilangan yang tak diketahui.. diketahui • Misal: Misal: – Persamaan ke ke--1, untuk menyelesaian x1, dst.. – Persamaan ke ke--2, untuk menyelesaikan x2, dst Dr.Eng. Agus S. Muntohar Department of Civil Engineering

4

Metode Gauss Gauss--Seidel: Algoritma • Tulis kembali persamaan: persamaan: x1 =

c1 − a12 x 2 − a13 x3 …… − a1n x n a11

Dari persamaan ke- 1

c2 − a21 x1 − a23 x3 …… − a2 n xn a22

Dari persamaan ke-2

x2 =

⋮ xn −1 = xn =

⋮

⋮

cn −1 − an −1,1 x1 − an −1, 2 x2 …… − an −1,n − 2 xn − 2 − an −1,n xn

Dari persamaan ke(n-1)

an −1,n −1

cn − an1 x1 − an 2 x2 − …… − an ,n −1 xn −1

Dari persamaan ke- n

ann Dr.Eng. Agus S. Muntohar Department of Civil Engineering

5

Metode Gauss Gauss--Seidel: Algoritma • Bentuk umum persamaan yaitu yaitu:: n

n

c1 − ∑ a1 j x j x1 =

cn −1 −

j =1 j ≠1

xn −1 =

a11

∑a

n −1, j

xj

j =1 j ≠ n −1

an −1,n −1 n

n

c n − ∑ a nj x j

j =1 j ≠2

j =1 j≠n

c2 − ∑ a2 j x j x2 =

a 22

xn = Dr.Eng. Agus S. Muntohar Department of Civil Engineering

a nn 6

Metode Gauss Gauss--Seidel: Algoritma • Bentuk umum untuk sembarang baris keke-‘i’ ‘i’ n

ci − ∑ aij x j xi =

j =1 j ≠i

aii

, i = 1,2, …, n.

Bagaimana dan dimana persamaan ini dapat digunakan?

Dr.Eng. Agus S. Muntohar Department of Civil Engineering

7

Metode Gauss Gauss--Seidel • Selesaikan bilangan yang tidak diketahui. diketahui. • Asumsikan suatu nilai perkiraan untuk [X]  x1  x   2  ⋮     xn-1   xn 

• Gunakan persamaan yang telah ditulis ulang untuk menyelesaiakn masing--masing nilai xi. masing • Penting Penting:: – Gunakan nilai terbaru xi untuk setiap iterasi persamaan berikutnya. berikutnya.


8

Metode GaussGauss-Seidel • Hitung nilai absolut dari kesalahan relatif (|ε (|εa|):

∈a i

xinew − xiold = ×100 new xi

• Kapan jawaban akan diperoleh? – Hentikan iterasi bila nilai |εa| kurang dari nilai kesalahan yang ditoleransikan untuk semua bilangan tidak diketahui tersebut.


9

Metode Gauss Gauss--Seidel: Contoh 1 Kecepatan dorong sutau roket untuk tiga waktu berbeda adalah : Table 1 Velocity vs. Time data.

Time, t (s) Kecepatan, v (m/s) 5 8 12

106.8 177.2 279.2

Data kecepatan pada Tabel 1 dapat didekati dengan persamaan polinomial berikut :

v (t ) = a1t 2 + a2t + a3 , 5 ≤ t ≤ 12. Dr.Eng. Agus S. Muntohar Department of Civil Engineering

10

Metode Gauss Gauss--Seidel: Contoh 1 1. Tuliskan persamaan dalam bentuk matriks: t12 2 t 2 t32 

t1 1  a1   v1   t 2 1 a2  = v2  t3 1  a3  v3 

2. Sistem persamaan menjadi:

 25 5 1  a1  106.8   64 8 1 a  = 177.2     2   144 12 1  a3  279.2

3. Perkirakan nilai awal:  a1  1 a  = 2  2    a3  5


11

Metode Gauss Gauss--Seidel: Contoh 1 Tulis ulang persamaan:

 25 5 1  a1  106.8   64 8 1 a  = 177.2     2   144 12 1  a3  279.2

a1 =

106.8 − 5a 2 − a 3 25

a2 =

177.2 − 64a1 − a 3 8

a3 =

279.2 − 144a1 − 12a 2 1


12

Metode Gauss Gauss--Seidel: Contoh 1 Gunakan nilai perkiraan awal untuk menghitung ai Nilai awal:

a1 =

 a1  1  a  =  2  2    a3  5

a2 = a3 =

106.8 − 5( 2) − (5) = 3.6720 25

177.2 − 64(3.6720 ) − (5) = −7.8510 8

279.2 − 144(3.6720 ) − 12(− 7.8510 ) = −155.36 1

Untuk menghitung a2, berapa banyak nilai perkiraan awal yang diperlukan? Dr.Eng. Agus S. Muntohar Department of Civil Engineering

13

Metode Gauss Gauss--Seidel: Contoh 1 Hitung nilai absolut dari kesalahan perkiraan relatif ∈a i

xinew − xiold = × 100 xinew

Hasil iterasi ke-1 :  a1   3.6720  a  = − 7.8510  2    a3   − 155.36 

3.6720 − 1.0000 ∈a 1 = 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

Nilai terbesar |εa| adalah 125.47%


14

Metode Gauss Gauss--Seidel: Contoh 1  a1   3.6720      Gunakan hasil dari iterasi ke-1: a 2  = − 7.8510  a3   − 155.36 

Iterasi ke-2

Diperoleh nilai ai : a1 =

106.8 − 5(− 7.8510 ) − 155.36 = 12.056 25

a2 = a3 =

177.2 − 64(12.056 ) − 155.36 = −54.882 8

279.2 − 144(12.056 ) − 12(− 54.882 ) = −798.34 1


15

Metode Gauss Gauss--Seidel: Contoh 1 Hitung nilai absolut dari kesalahan perkiraan relatif pada iterasi ke-2 ∈a 1 =

∈a 2 =

∈a 3 =

12.056 − 3.6720 x100 = 69.543% 12.056

Hasil iterasi ke-2 :

 a1   12.056  a  =  − 54.882  2    a3  − 798.54

− 54.882 − (− 7.8510 ) x100 = 85.695% − 54.882

− 798.34 − (− 155.36 ) x100 = 80.540% − 798.34

Nilai terbesar |εa| adalah 85.695%


16

Metode Gauss Gauss--Seidel: Contoh 1 Hasil beberapa kali iterasi adalah sebagai berikut: Iterasi

a1 3.6720 12.056 47.182 193.33 800.53 3322.6

1 2 3 4 5 6

∈a 1 %

a2

∈a 2 %

a3

72.767 69.543 74.447 75.595 75.850 75.906

−7.8510 −54.882 −255.51 255.51 −1093.4 −4577.2 −19049

125.47 85.695 78.521 76.632 76.112 75.972

−155.36 −798.34 −3448.9 3448.9 −14440 −60072 −249580

∈a 3 % 103.22 80.540 76.852 76.116 75.963 75.931

Catatan– Nilai kesalahan relatif tidak banyak berkurang pada setiap iterasi, termasuk pula tidak konvergen pada nilai sebenarnya.

 a 1  0.29048 a  =  19.690   2   a 3   1.0857 


17

Gauss--Seidel Method: Kelemahan Gauss Apa yang menyebabkan salah ? Walaupun penghitungan dilakukan dengan benar, hasilnya belum konvergen. Contoh 1 menunjukkan kelemahan dari Metode Gauss-Siedel: tidak semua sistem persamaan menghasilkan jawaban yang konvergen.

Apakah solusinya? Satu dari sistem persamaan selalu konvergen dimana koefisien matriks adalah dominan diagonal, yaitu jika [A] dalam [A] [X] = [C] memenuhi kondisi : n

n

aii ≥ ∑ aij j =1 j ≠i

Untuk semua ‘i’ dan

aii > ∑ aij


j =1 j ≠i

paling tidak untuk ke-‘i’ 18

Metode Gauss Gauss--Seidel: Contoh 2 Diberikan persamaan berikut: 12 x1 + 3 x2 - 5 x3 = 1

x1 + 5 x2 + 3x3 = 28 3x1 + 7 x2 + 13x3 = 76

Gunakan nilai perkiraan awal untuk iterasi ke-1 :  x1  1  x  = 0   2    x3  1

Koefisien matriksnya adalah : 12 3 − 5 [A] =  1 5 3   3 7 13 

Apakah Metode GaussSiedel akan memberikan hasil yang konvergen? Dr.Eng. Agus S. Muntohar Department of Civil Engineering

20

Metode Gauss Gauss--Seidel: Contoh 2 Cek apakah koefisien matriks dominan diagonal. 12 3 − 5 [A] =  1 5 3   3 7 13 

a11 = 12 = 12 ≥ a12 + a13 = 3 + − 5 = 8

a 22 = 5 = 5 ≥ a 21 + a 23 = 1 + 3 = 4 a33 = 13 = 13 ≥ a31 + a32 = 3 + 7 = 10

Semua koefisien matriks tidak sama, dan salah satu baris bernilai lebih besar. Oleh karen itu: Penyelesaian dengan Metode GaussSiedel akan konvergen. Dr.Eng. Agus S. Muntohar Department of Civil Engineering

21

Metode Gauss Gauss--Seidel: Contoh 2 Tulis kembali persamaan: 12 3 − 5  a1   1   1 5 3  a  = 28    2    3 7 13   a3  76

 x  = 0   2    x3  1

1 − 3 x 2 + 5 x3 12 28 − x1 − 3 x3 x2 = 5 x1 =

x3 =

76 − 3 x1 − 7 x 2 13

Dengan nilai awal, lakukan  x1  1 iterasi ke-1:

x3 =

x1 =

1 − 3(0 ) + 5(1) = 0.50000 12

x2 =

28 − (0.5) − 3(1) = 4.9000 5

76 − 3(0.50000 ) − 7(4.9000 ) = 3.0923 13


22

Metode Gauss Gauss--Seidel: Contoh 2 Nilai absolut kesalahan relatif:

∈a 1 =

0.50000 − 1.0000 × 100 = 100.00% 0.50000

∈a 2 =

4.9000 − 0 × 100 = 100.00% 4.9000

∈a 3 =

3.0923 − 1.0000 × 100 = 67.662% 3.0923

Nilai terbesar dari kesalahan relatif adalah 100% Dr.Eng. Agus S. Muntohar Department of Civil Engineering

23

Metode Gauss Gauss--Seidel: Contoh 2  x1  0.5000  x  = 4.9000   2   x3  3.0923

Hasil iterasi ke-1

Substitusi nilai x ke persamaan : 1 − 3(4.9000 ) + 5(3.0923) x1 = = 0.14679 12 x2 =

28 − (0.14679 ) − 3(3.0923) = 3.7153 5

x3 =

76 − 3(0.14679 ) − 7(4.900 ) = 3.8118 13

Hasil Iterasi ke-2  x1  0.14679  x  =  3.7153   2    x3   3.8118 


24

Metode Gauss Gauss--Seidel: Contoh 2 Nilai absolut dari kesalahan relatif pada Iterasi ke-2 ∈a 1 =

0.14679 − 0.50000 × 100 = 240.61% 0.14679

∈a 2 =

3.7153 − 4.9000 × 100 = 31.889% 3.7153

∈a 3 =

3.8118 − 3.0923 × 100 = 18.874% 3.8118

Nilai terbesar dari kesalahan relatif adalah 240.61%, yaitu lebih besar dari hasil Iterasi ke-1. Apakah ini bermasalah? Dr.Eng. Agus S. Muntohar Department of Civil Engineering

25

Metode Gauss Gauss--Seidel: Contoh 2 Lanjutkan Iterasi dan diperoleh hasil: Iterasi

a1

1 2 3 4 5 6

0.50000 0.14679 0.74275 0.94675 0.99177 0.99919

∈a 1 % 100.00 240.61 80.236 21.546 4.5391 0.74307

Hasil akhir Iterasi :  x1  0.99919  x  =  3.0001   2    x3   4.0001 

a2

∈a 2 %

a3

4.9000 3.7153 3.1644 3.0281 3.0034 3.0001

100.00 31.889 17.408 4.4996 0.82499 0.10856

3.0923 3.8118 3.9708 3.9971 4.0001 4.0001

∈a 3 % 67.662 18.876 4.0042 0.65772 0.074383 0.00101

Hasil penyelesaian eksak .


 x1  1  x  =  3  2    x3  4

26

Dr.Eng. Agus S. Muntohar Department of Civil Engineering

Recommend Documents