Makalah Metode SOR [PDF]

Citation preview

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