19 0 770 KB
METODE ITERASI SOR Disusun untuk Memenuhi Tugas Mata Kuliah Analisis Numerik Dosen Pengampu: Dr. Sri Andayani, M.Kom
Oleh Kelompok V: Indra Kusuma Wijayanti Annisa Nur Arifah
18709251046 18709251058
PROGRAM STUDI PENDIDIKAN MATEMATIKA PASCASARJANA UNIVERSITAS NEGERI YOGYAKARTA 2019
METODE ITERASI SOR A. Pendahuluan Untuk menyelesaikan suatu sistem persamaan linier π΄π₯ = π, dipunyai pilihan antara metode langsung atau metode iterasi. Contoh dari metode langsung yaitu metode invers, eliminasi Gauss, dan dekomposisi LU. Metode iterasi mempunyai kelebihan dalam hal kemurahan memori dan waktu CPU. Metode ini dimulai dari penentuan nilai awal vektor π₯0 sebagai suatu penyelesaian awal untuk π₯. Suatu klas besar dari metode iterasi dapat didefinisikan sebagai berikut. Sistem π΄π₯ = π dituliskan menjadi ππ₯ = (π β π΄) π₯ + π untuk suatu matriks Q yang berorde sama dengan A. Selanjutnya dideβ¦nisikan suatu skema iterasi ke-k: ππ₯ (π) = (π β π΄) π₯(π β 1) + π; π = 1, 2, β¦ ..
(4.1)
untuk x(0) adalah suatu tebakan awal. Diasumsikan bahwa Q adalah non-singular, sehingga skema iterasi menghasilkan suatu barisan tunggal vektor-vektor {x(k)}. Terdapat beberapa metode iterasi seperti iterasi Jacobi, iterasi Gauss-Seidel, dan iterasi SOR. Pada makalah ini, pembahasan akan difokuskan pada metode iterasi SOR. B. Metode SOR Berikutnya diperhatikan suatu metode mempercepat konvergensi dari metode iterasi. Dipilih 1
π = ππ· +πΏ dengan π adalah suatu faktor skala, maka iterasi (4.1) menjadi 1
1
(π π· + πΏ) π₯ (π) = (π π· + πΏ β π΄) π₯ (πβ1) + π 1
1
(π π· + πΏ) π₯ (π) = {(π β 1) π· β π} π₯ (πβ1) + π 1
1
π·π₯ (π) = βπΏπ₯ (π) + {(π β 1) π· β π} π₯ (πβ1) + π π 1
π·π₯ (π) = βππΏπ₯ (π) + π {(π β 1) π· β π} π₯ (πβ1) + ππ 1
π₯ (π) = βππΏπ₯ (π) π· β1 + ππ·β1 {(π β 1) π· β π} π₯ (πβ1) + ππ· β1 π
1
π₯ (π) = βππΏπ₯ (π) π· β1 + ππ·β1 (π β 1) π·π₯ (πβ1) β πππ·β1 π₯ (πβ1) + ππ· β1 π 1
π₯ (π) = βππΏπ₯ (π) π· β1 + (π. π β π) π₯ (πβ1) β πππ·β1 π₯ (πβ1) + ππ·β1 π π₯ (π) = βππΏπ₯ (π) π· β1 + (1 β π)π₯ (πβ1) β πππ·β1 π₯ (πβ1) + ππ· β1 π π₯ (π) = (1 β π)π₯ (πβ1) + ππ·β1 (π β πΏπ₯ (π) β ππ₯ (πβ1) ) untuk π = 1, 2, 3, β¦ secara jelas, ini diproses dengan cara: (π)
= (1 β π)π₯ (πβ1) + ππ·β1 (π β πΏπ₯ (π) β ππ₯ (πβ1) )
(π)
= (1 β π)π₯π
π₯π π₯π
(πβ1)
π
(π)
+ π (ππ β βπβ1 π=1 πππ π₯π ππ
(πβ1)
β βππ=π+1 πππ π₯π
)
untuk π = 1, 2, β¦ . , π dan diasumsikan bahwa untuk langkah keβπ komponen-komponen (π) π₯π , 1 β€ π β€ π β 1 sudah diketahui. Jika π > 1 maka faktor koreksinya lebih besar daripada koreksi normal. Hal ini berguna jika iterasi Gauss Seidel bergerak secara monoton, yakni semakin menuju ke penyelesaian esak dalam satu arah. Oleh karena itu, metode ini disebut Successive Over-relaxation (SOR). Nilai π yang optimal (paling mempercepat kekonvergenan) berada pada selang 1.1 β€ π β€ 1.9 untuk metode SOR. C. Algoritma Metode SOR Algoritma menyelesaikan sistem persamaan linier dengan metode SOR adalah sebagai berikut. 1. Tentukan nilai toleransi eror π 2. Tentukan nilai π 3. Nyatakan π₯1 dalam π₯2 , π₯3 , β¦.. π dari SPL (1), π₯2 dalam π₯1 , π₯3 , β¦., π₯π dari SPL (2), sampai π₯π dalam π₯1 , π₯2 , β¦β¦. π₯πβ1 dari SPL ke-n. 4. Tentukan nilai hampiran penyelesaian awal π₯2 , π₯3 , β¦ , π₯π . Misal nilai hampiran awal π₯2 , π₯3 , β¦ , π₯π dinotasikan π₯2 0 , π₯3 0 , β¦ , π₯π 0 5. Subtitusikan π₯2 0 , π₯3 0 , β¦ , π₯π 0 ke SPL (1) untuk memperoleh nilai π₯1 , π₯1 dinamakan π₯11 6. Subtitusikan π₯11 , π₯3 0 , β¦ , π₯π 0 ke SPL (2) untuk memperoleh nilai π₯2 , π₯2 dinamakan π₯21 7. Subtitusikan π₯11 , π₯21 , β¦ , π₯(πβ1)1 ke SPL (π) untuk memperoleh nilai π₯π , π₯π dinamakan π₯π 1 8. Iterasi ke-1 selesai dengan diperolehnya π₯11 , π₯21 , β¦ , π₯(πβ1)1 , π₯π 1 9. Subtitusikan π₯21 , β¦ , π₯(πβ1)1 , π₯π1 ke SPL (1,2, β¦ , π) untuk memperoleh nilai π₯1 , π₯2 , π₯π kemudian kita notasikan π₯1 2 , π₯2 2 , β¦ , π₯(πβ1) 2 , π₯π 2
10. Iterasi ke-2 selesai dengan diperolehnya π₯1 2 , π₯2 2 , β¦ , π₯(πβ1) 2 , π₯π 2 11. Iterasi berhenti pada iterasi ke-k, jika |π₯π π β π₯π π+1 | < π 12. Jadi, hampiran penyelesaian sistem persamaan liniernya adalah (π₯1 π+1 , π₯2 π+1 , β¦ , π₯π π+1 ) D. Contoh Penerapan Metode Iterasi SOR Selesaikan sistem persamaan linear di bawah ini menggunakan metode SOR! 10π₯1 β π₯2 + 2π₯3 = 6 β¦β¦β¦β¦β¦.(1) βπ₯1 + 11π₯2 β π₯3 + 3π₯4 = 25 β¦...(2) 2π₯1 β π₯2 + 10π₯3 β π₯4 = β11 β¦β¦(3) 3π₯2 β π₯3 + 8π₯4 = 15 β¦β¦β¦β¦β¦.(4) Penyelesaian Kita tetapkan π = 0.001, π = 1.1 dan π₯0 = 0, proses perhitungan secara manual adalah sebagai berikut. Iterasi 1 Nyatakan π₯1 dalam π₯2 , π₯3 , dan π₯4 dari SPL (1) 1.1
π₯1 π = (1 β 1.1)π₯1 πβ1 + 10 (6 + π₯2 π β 2π₯3 πβ1 ) π₯1 π = β0.1π₯1 πβ1 + 0.11(6 + π₯2 π β 2π₯3 πβ1 ) π₯1 π = β0.1π₯1 πβ1 + 0.11π₯2 π β 0.22π₯3 πβ1 + 0.66 π₯11 = 0.66 Nyatakan π₯2 dalam π₯1 , π₯3 , dan π₯4 dari SPL (2) 1.1
π₯2 π = (1 β 1.1)π₯2 πβ1 + 11 (25 + π₯1 π + π₯3 πβ1 β 3π₯4 πβ1 ) π₯2 π = β0.1π₯2 πβ1 + 0.1(25 + π₯1 π + π₯3 πβ1 β 3π₯4 πβ1 ) π₯2 π = β0.1π₯2 πβ1 + 0.25 + 0.1π₯1 π + 0.1π₯3 πβ1 β 0.3π₯4 πβ1
π₯21 = 2.5 + 0.1 Γ 0.66 = 2.5 + 0.066 = 2.566 Nyatakan π₯3 dalam π₯1 , π₯2 , dan π₯4 dari SPL (3) 1.1
π₯3 π = (1 β 1.1)π₯3 πβ1 + 10 (β11 β 2π₯1 π + π₯2 πβ1 + π₯4 πβ1 ) π₯3 π = β0.1π₯3 πβ1 + 0.11(β11 β 2π₯1 π + π₯2 πβ1 + π₯4 πβ1 ) π₯3 π = β0.1π₯3 πβ1 β 1.21 β 0.22π₯1 π + 0.11π₯2 πβ1 + 0.11π₯4 πβ1 π₯31 = β1.21 β 0.22(0.66) + 0.11(2.566) = β1.3552 + 0.28226 = β1.0729 Nyatakan π₯4 dalam π₯1 , π₯2 , dan π₯3 dari SPL (4) π₯4 π = (1 β 1.1)π₯4 πβ1 +
1.1 8
(15 β 3π₯2 π + π₯3 )
π₯4 π = β0.1π₯4 πβ1 + 0.1375(15 β 3π₯2 π + π₯3 ) π₯4 π = β0.1π₯4 πβ1 + 2.0625 β 0.4125π₯2 π + 0.1375π₯3 ) π₯41 = 2.0625 β 0.4125(2.566) + 0.1375(β1.0729) = 2.0625 β 1.058 β 0.1475 = 0.857 Iterasi 1 selesai dengan (0.66; 2.566; β1.0729; 0.857)
hasil
(π₯1 ; π₯2 ; π₯3 ; π₯4 ) = (π₯11 ; π₯21 ; π₯31 ; π₯41 ) =
Iterasi 2 π₯1π = β0,1π₯1πβ1 + 0.11π₯2πβ1 β 0.22π₯3πβ1 + 0,66 π₯12 = β0.1(0.66) + 0.11(2.566) β 0.22(β1.0729) + 0,66 π₯12 = β0.066 + 0.2823 + 0.2360 + 0.66 = 1.1123
π₯2π = β0,1π₯2πβ1 + 2.5 + 0.1π₯1π + 0.1π₯3πβ1 β 0.3π₯4πβ1 π₯22 = β0,1(2.566) + 2.5 + 0.1(1.1123) + 0.1(β1.0729) β 0.3(0.857) π₯22 = β0.2566 + 2.5 + 0.1123 β 0.10729 β 0.2571 = 1.99024
π₯3π = β0,1π₯3πβ1 β 1.21 β 0.22π₯1π + 0.11π₯2π + 0.11π₯4πβ1 π₯32 = β0,1(β1,0729) β 1.21 β 0.22(1.1123) + 0.11(1.99024) + 0.11(0.857) π₯32 = 0.10729 β 1.21 β 0.2447 + 0.2189 + 0.09427 = β1.03424
π₯4π = β0,1π₯4πβ1 + 2.0625 β 0.4125π₯2π + 0.1375π₯3π π₯42 = β0,1(0.857) + 2.0625 β 0.4125(1.99024) + 0.1375(β1.03424) π₯42 = β0.0857 + 2.0625 β 0.8209 β 0.1422 = 1.0137 Iterasi 2 selesai dengan hasil (π₯12 ; π₯22 ; π₯32 ; π₯42 ) = (1.1123; 1.99024; β1.03424; 1.0137) Bandingkan iterasi (1) dan (2) jika |π₯ππ β π₯ππ+1 | > 0.001 maka lanjutkan iterasi |0.66 β 1.1123| = 0.45 > 0.001 |2.566 β 1.99024| = 0.57 > 0.001 |(β1.0729) β (β1.03424)| = 0.038 > 0.001 |0.857 β 1.0137| = 0.1567 > 0.001
Iterasi 3 π₯1π = β0,1π₯1πβ1 + 0.11π₯2πβ1 β 0.22π₯3πβ1 + 0,66 π₯13 = β0,1(1.1123) + 0.11(1.99024) β 0.22(β1.03424) + 0,66 = 0.9952
π₯2π = β0,1π₯2πβ1 + 2.5 + 0.1π₯1π + 0.1π₯3πβ1 β 0.3π₯4πβ1 π₯23 = β0,1(1.99024) + 2.5 + 0.1(0.9952) + 0.1(β1.03424) β 0.3(1.0137) = 1.992986
π₯3π = β0,1π₯3πβ1 β 1.21 β 0.22π₯1π + 0.11π₯2π + 0.11π₯4πβ1 π₯33 = β0,1(β1.03424) β 1.21 β 0.22(0.9952) + 0.11(1.9929) + 0.11(1.0137) = β0.994769
π₯4π = β0,1π₯4πβ1 + 2.0625 β 0.4125π₯2π + 0.1375π₯3π π₯43 = β0,1(1.0137) + 2.0625 β 0.4125(1.9929) + 0.1375(β0.9947) = 1.002254 Iterasi 3 selesai dengan hasil (π₯13 ; π₯23 ; π₯33 ; π₯43 ) = (0.9952; 1.992986 ; β0.994769; 1.002254) Bandingkan iterasi (2) dan (3) jika |π₯ππ β π₯ππ+1 | > 0.001 maka lanjutkan iterasi |1.1123 β 0.9952| = 0.1171 > 0.001 |1.99024 β 1.992986| = 0.002 > 0.001
|(β1.03424) β (β0.994769)| = 0.039 > 0.001 |1.0137 β 1.002254| = 0.0114 > 0.01
Iterasi 4 π₯1π = β0,1π₯1πβ1 + 0.11π₯2πβ1 β 0.22π₯3πβ1 + 0,66 π₯14 = β0,1(0.9952) + 0.11(1.992986) β 0.22(β0.994769) + 0,66 = 0.99856
π₯2π = β0,1π₯2πβ1 + 2.5 + 0.1π₯1π + 0.1π₯3πβ1 β 0.3π₯4πβ1 π₯24 = β0,1(1.992986) + 2.5 + 0.1(0.99856) + 0.1(β0.994769) β 0.3(1.002254) = 2.0004
π₯3π = β0,1π₯3πβ1 β 1.21 β 0.22π₯1π + 0.11π₯2π + 0.11π₯4πβ1 π₯34 = β0,1(β0.994769) β 1.21 β 0.22(0.99856) + 0.11(2.0004) + 0.11(1.002254) = β0.99991
π₯4π = β0,1π₯4πβ1 + 2.0625 β 0.4125π₯2π + 0.1375π₯3π π₯43 = β0,1(1.002254) + 2.0625 β 0.4125(2.0004) + 0.1375(β0.99991) = 0.99962 Iterasi 4 selesai dengan hasil (π₯13 ; π₯23 ; π₯33 ; π₯43 ) = (0.99856 ; 2.0004 ; β0.99991; 0.99962) Bandingkan iterasi (3) dan (4) jika |π₯ππ β π₯ππ+1 | > 0.001 maka lanjutkan iterasi |0.9952 β 0.99856| = 0.003 > 0.001 |1.992986 β 2.0004| = 0.007 > 0.001 |(β0.994769) β (β0.99991)| = 0.005 > 0.001 |1.002254 β 0.99962| = 0.002 > 0.01
Iterasi 5 π₯1π = β0,1π₯1πβ1 + 0.11π₯2πβ1 β 0.22π₯3πβ1 + 0,66 π₯15 = β0,1(0.99856 ) + 0.11(2.0004) β 0.22(β0.99991) + 0,66 = 1.00017
π₯2π = β0,1π₯2πβ1 + 2.5 + 0.1π₯1π + 0.1π₯3πβ1 β 0.3π₯4πβ1 π₯25 = β0,1(2.0004) + 2.5 + 0.1(1.00017 ) + 0.1(β0.99991) β 0.3(0.99962) = 2.00010
π₯3π = β0,1π₯3πβ1 β 1.21 β 0.22π₯1π + 0.11π₯2π + 0.11π₯4πβ1 π₯35 = β0,1(β0.99991) β 1.21 β 0.22(1.00017) + 0.11(2.00010 ) + 0.11(0.99962) = β1.00008
π₯4π = β0,1π₯4πβ1 + 2.0625 β 0.4125π₯2π + 0.1375π₯3π π₯45 = β0,1(0.99962) + 2.0625 β 0.4125(2.00010 ) + 0.1375(β1.00008 ) = 1.000038 Iterasi 5 selesai dengan hasil (π₯15 ; π₯25 ; π₯35 ; π₯45 ) = (1.00017 ; 2.0001 ; β1.00008 ; 1.000038) Bandingkan iterasi (4) dan (5) jika |π₯ππ β π₯ππ+1 | > 0.001 maka lanjutkan iterasi |0.99856 β 1.00017| = 0.001 = 0.001 |2.0004 β 2.0001| = 0.0003 < 0.001 |(β0.99991) β (β1.00008)| = 0.0001 < 0.001 |0.99962 β 1.000038 | = 0.0004 < 0.001 Karena ada |π₯ππ β π₯ππ+1 | < 0.001, makaperhitungan berhenti pada iterasi ke 5. Jadi, hampiran penyelesaian SPLnya adalah (1.00017 ; 2.00010 ; β1.00008 ; 1.000038). E. Perhitungan dengan Matlab Script Matlab function [hasil]=sor(A,b,X0,w,tol) L=triu(A',1)'; c=size(A); D=eye(c).*A; U=triu(A,1); I=eye(c); E=inv(D); hasil=[0 X0']; k=1; M1=w*E*L;
M2=w*E*b; M3=w*E*U; X=inv(I+M1)*(M2+((1-w)*I-M3)*X0); while max(X-X0)>tol, hasil=[hasil;k X']; X0=X; k=k+1; X=inv(I+M1)*(M2+((1-w)*I-M3)*X0); End >>
A=[10 -1 2 0; -1 11 -1 3; 2 -1 10 -1; 0 3 -1 8];
>> b=[6;25;-11;15]; >> X0=[0 0 0 0]'; >> hasil=it_sor(A,b,X0,1.1,0.001) hasil =
0.00000
0.00000
0.00000
0.00000
0.00000
1.00000
0.66000
2.56600
-1.07294
0.85650
2.00000
1.11231
1.99039
-1.03426
1.01361
3.00000
0.99525
1.99298
-0.99480
1.00225
4.00000
0.99856
2.00040
-0.99991
0.99962
5.00000
1.00017
2.00010
-1.00008
0.99999