METODE ITERASI KSOR UNTUK MENYELESAIKAN SISTEM PERSAMAAN LINEAR Adek Putri Syafriani1∗ , Syamsudhuha 2 , Zulkarnain2 1
Mahasiswa Program Studi S1 Matematika 2 Dosen Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Riau Kampus Binawidya Pekanbaru (28293), Indonesia ∗
[email protected]
ABSTRACT This article discusses the iterative method for solving a system of linear equations using KSOR method, which is the modification of Successive over Relaxation (SOR) method. The main difference between KSOR method and SOR method is lying on the value of relaxation parameter allowed. Furthermore, using two systems of linear equations with different sizes, the comparisons between the KSOR method, GaussSeidel method and Successive over-Relaxation (SOR) method are carried out. The results show that KSOR method is better than Gauss-Seidel method and comparable than Successive over Relaxation (SOR) method. Keywords: KSOR method, Gauss-Seidel method, Succesive over Relaxation (SOR) method. ABSTRAK Artikel ini membahas metode iterasi untuk menyelesaikan sistem persamaan linear dengan menggunakan metode iterasi KSOR, yang merupakan pengembangan dari metode Succesive over Relaxation (SOR). Perbedaan utama metode KSOR dengan SOR adalah pada parameter relakasasi yang diizinkan. Selanjutnya dilakukan perbandingan komputasi antara metode KSOR, metode Gauss-Seidel dan metode Succesive over Relaxation (SOR) melalui dua contoh sistem persamaan dengan ukuran berbeda. Hasilnya menunjukkan metode KSOR lebih baik dari metode Gauss-Seidel dan sebanding metode Succesive over Relaxation (SOR). Kata kunci: Metode KSOR, metode Gauss-Seidel, metode Succesive over Relaxation (SOR). 1. PENDAHULUAN Suatu sistem persamaan linear terdiri atas sejumlah berhingga persamaan linear dalam sejumlah variabel. Menyelesaikan suatu sistem persamaan linear adalah mencari nilai-nilai variabel-variabel tersebut yang memenuhi semua persamaan linear Repository FMIPA
1
yang diberikan. Sistem persamaan linear dapat dinyatakan dalam bentuk perkalian matriks Ax = b. (1) Metode iterasi merupakan salah satu metode yang digunakan untuk menyelesaikan sistem persamaan linear pada persamaan (1), dengan A ∈ Rm×m , b ∈ Rm dan x ∈ Rm merupakan vektor yang belum diketahui. Beberapa metode iterasi untuk mendefinisikan persamaan (1) yang telah dikenal diantaranya adalah metode Jacobi [1, h. 450] , metode Gauss-Seidel[1, h. 454], dan metode Succesive over Relaxation (SOR)[1, h. 462]. Suatu hal yang dinilai dari suatu metode iterasi adalah seberapa cepat barisan yang dihasilkan metode iterasi tersebut konvergen. Beberapa pengembangan dari metode iterasi telah dilakukan untuk mendapatkan metode yang konvergen lebih cepat. Metode SOR merupakan metode iterasi relaksasi yang digunakan untuk menyelesaikan sistem persamaan linear tertentu dengan menggunakan parameter relaksasi ω pada interval (0, 2). Namun parameter relaksasi yang digunakan dalam metode tersebut hanya terbatas pada interval (0, 2). Dalam artikel ini dibahas sebuah metode baru hasil pengembangan dari Metode SOR yang diperkenalkan oleh I.K Youssef [4] yaitu metode KSOR yang menggunakan parameter relaksasi ω ∗ ∈ R − [−2, 0]. Pembahasan dimulai dari metode Gauss-Seidel dan metode SOR dibagian dua. Kemudian dibagian tiga dibahas metode KSOR yang merupakan bentuk modifikasi dari metode SOR. Diakhir pembahasan akan disajikan perbandingan numerik dari metode yang dikemukakan. 2. METODE GAUSS-SEIDEL DAN METODE SOR Misalkan A, M, N adalah matriks nonsingular. Sedemikian sehingga A = M − N. Sehingga persamaan (1) dapat ditulis menjadi Ax = b, (M − N )x = b, M x = N x + b.
(2)
Karena M nonsingular, maka dari persamaan (2) diperoleh x = M −1 N x + M −1 b.
(3)
Dengan memisalkan T = M −1 N dan c = M −1 b, maka persamaan (3) dapat ditulis menjadi x = T x + c. (4)
Repository FMIPA
2
Kemudian untuk suatu tebakan awal x(0) ∈ Rm dengan menggunakan persamaan (4) diperoleh x(1) dimana x(1) = T x(0) + c. Secara umum, untuk tebakan awal x(0) diperoleh x(k) = T x(k−1) + c. k = 1, 2, . . . , . Misalkan A dipisahkan menjadi A = D − L − U , dimana D adalah matriks diagonal, L adalah matriks segitiga bawah dan U adalah matriks segitiga atas. Metode Gauss-Seidel diperoleh dengan mengambil M = D − L dan N = U , sedemikian hingga T = (D − L)−1 U , sehingga dengan demikian dari persamaan (2) diperoleh (D − L)x(k) = U x(k−1) + b, x(k) = (D − L)−1 U x(k−1) + (D − L)−1 b,
(5)
dan persamaan (5) dapat ditulis menjadi x(k) = T x(k−1) + c, dimana
T = (D − L)−1 U,
dan
c = (D − L)−1 b.
Dengan mengambil tebakan awal x(0) ∈ Rm solusi hampiran metode Gauss-Seidel dapat dinyatakan dengan persamaan: [ i−1 ] m ∑ ∑ 1 (k) (k) (k−1) xi = − aij xj − aij xj + bi . aii j=1 j=i+1 Kekonvergenan metode Gauss-Seidel dimana matriks A adalah diagonal dominan dapat dilihat dari teorema berikut Teorema 1 [2, h. 189] Jika A adalah diagonal dominan, maka metode Gauss-Seidel konvergen untuk semua tebakan awal. Bukti. Dapat dilihat pada[2, h. 189]. Adapun pada metode SOR diperoleh metode iterasi (D − ωL)x(k) = [(1 − ω)D + ωU ] x(k−1) + ωb, sehingga xSOR = (D − ωL)−1 [(1 − ω)D + ωU ] x(k−1) + ω(D − ωL)−1 b, (k)
Repository FMIPA
3
dimana
TSOR = (D − ωL)−1 [(1 − ω)D + ωU ] ,
dan cSOR = ω(D − ωL)−1 b. Solusi hampiran pada metode SOR dapat dinyatakan dalam bentuk persamaan: ] [ m i−1 ∑ ∑ ω (k−1) (k) (k−1) (k) . aij xj xi SOR = (1 − ω)xi + bi − aij xj − aii j=i+1 j=1 Ketika nilai ω terletak pada interval 0 < ω < 1, metode tersebut disebut metode relaksasi bawah (under- relaxation method ), disaat 1 < ω metode tersebut dikatakan metode relaksasi atas (over- relaxation method ), dan saat ω = 1 maka metode ini akan kembali menjadi metode iterasi Gauss-Seidel. Kekonvergenan metode SOR dapat dilihat pada Teorema 2 dan Teorema 3 berikut Teorema 2 (Kahan)[1, h. 465] Jika aii ̸= 0, untuk setiap i = 1, 2, . . . , n, maka ρ(TSOR) ≥ |ω − 1| . Hal ini mengakibatkan bahwa metode SOR konvergen hanya jika 0 < ω < 2. Bukti. Dapat dilihat pada[3, h. 122]. Teorema 3 (Ostrowski-Reich) Jika A suatu matriks definite positif dan 0 < ω < 2, maka metode SOR konvergen untuk setiap vektor approksimasi x(0) . Bukti. Dapat dilihat pada[3, h. 123]. 3. METODE KSOR Ide dasar dari metode KSOR adalah transformasi parameter ω pada metode SOR ω menjadi ω ∗ pada metode KSOR, dimana ω ∗ = (1−ω) . Metode KSOR diperkenalkan sebagai bentuk baru dari metode iterasi SOR, dengan memperluas domain dari interval parameter relaksasi dan sensitifitas disekitar nilai optimum dari parameter relaksasi yang meningkat[5]. Berbeda dengan interval parameter ω ∈ [0, 2] pada metode SOR, pada metode iterasi KSOR interval parameter ω ∗ diperluas menjadi ω ∗ ∈ R − [−2, 0] . Bentuk dasar persamaan pada metode KSOR dapat dinyatakan sebagai x(k) KSOR = x(k−1) + ω ∗ (xGS − xKSOR ) (k)
(k)
= x(k−1) + ω ∗ xGS − ωxKSOR (k)
(k)
(1 + ω ∗ )xKSOR = x(k−1) + ω ∗ xGS , (k)
Repository FMIPA
(k)
4
selanjutnya [
(1 + ω ∗ )xi
(k)
(k)
xi
KSOR
ω∗ (k−1) = xi + aii
1 = (1 + ω ∗ )
(
[
( bi −
ω∗ (k−1) xi + aii
i−1 ∑
(k)
aij xj −
j=1
( bi −
m ∑
)] (k−1)
aij xj
,
j=i+1
i−1 ∑
(k)
aij xj −
j=1
m ∑
)]) (k−1)
aij xj
,
j=i+1
yang merupakan solusi hampiran metode KSOR untuk setiap i = 1, 2, . . . , n, ω ∗ ∈ R − [−2, 0], dimana TKSOR = ((1 + ω ∗ )D − ω ∗ L)−1 (D + ω ∗ U ), dan cKSOR = ((1 + ω ∗ )D − ω ∗ L)−1 (ω ∗ b). Metode iterasi KSOR dapat ditulis menjadi xKSOR = ((1 + ω ∗ )D − ω ∗ L)−1 (D + ω ∗ U )x(k−1) + ((1 + ω ∗ )D − ω ∗ L)−1 (ω ∗ b). (k)
Kekonvergenan metode KSOR dapat dilihat dari Teorema 4 berikut ini. Teorema 4 Misalkan A ∈ Rm×m dengan aii ̸= 0. Maka ρ(TKSOR ) ≥
1 . |1 + ω ∗ |
Oleh karena itu metode KSOR konvergen untuk setiap ω ∗ ∈ R − [−2, 0]. Bukti. Untuk setiap ω ∗ ̸= −1, diperoleh det(TKSOR ) = det(((1 + ω ∗ )D − ω ∗ L)−1 (D + ω ∗ U )) = det((1 + ω ∗ )D − ω ∗ L)−1 det(D + ω ∗ U ) 1 = det(D + ω ∗ U ) det((1 + ω ∗ )D − ω ∗ L) 1 det(D + ω ∗ U ) = ∗ det((1 + ω )D) 1 = det(D + ω ∗ U ) ∗ (1 + ω )m det D 1 = det (D)−1 det(D + ω ∗ U ) (1 + ω ∗ )m 1 det(I + ω ∗ (D)−1 U ) = (1 + ω ∗ )m m ∏ det(TKSOR ) = βj , j=1
Repository FMIPA
5
dengan βj adalah nilai eigen dari matriks iterasi TKSOR . Selanjutnya, karena m ∏ 1 ≤ max |βj |m , βj = |det(TKSOR )| = m ∗ (1 + ω ) j=1
sehingga karena max |βj | = ρ(TKSOR ) maka ρ(TKSOR ) ≥
1 . |1 + ω ∗ |
selanjutnya metode iterasi KSOR akan konvergen jika ρ(TKSOR ) < 1, yaitu 1 (1+ω∗ ) < 1 yang dipenuhi oleh ω ∗ ∈ R − [−2, 0]. 4. UJI KOMPUTASI Pada bagian ini akan dilakukan uji komputasi untuk membandingkan metode GaussSeidel, metode SOR dan metode KSOR menggunakan program pada Matlab R2010a untuk menyelesaikan sistem persamaan linear. Contoh 1 Tentukan solusi dari sistem persamaan linear berikut dengan menggunakan metode Gauss-Seidel, metode SOR dan metode KSOR 4 −1 −1 0 2 −1 4 0 −1 2 A= , b = −1 0 2 4 −1 0 −1 −1 4 2 Solusi. Dalam menentukan solusi numerik dari ketiga metode tersebut di atas, akan digunakan tebakan awal x(0) = 0, dan nilai toleransi 1.0 × 10−6 , hasil komputasi dari ketiga metode tersebut dapat dilihat pada Tabel 1 Tabel 1: Perbandingan Hasil Komputasi dari Beberapa Metode Iterasi GS Iterasi
12
Error
5.36e − 007
Repository FMIPA
ω 0.2 1 1.07 1.10 1.95
SOR Iterasi Error 132 9.18e − 007 12 5.36e − 007 8 4.42e − 007 7 9.83e − 007 288 9.09e − 007
ω∗ −35000 −13 −14 1 2
KSOR Iterasi Error 12 5.35e − 007 8 6.60e − 008 7 3.85e − 007 44 8.40e − 007 29 7.37e − 007
6
Tabel 1 menunjukkan bahwa metode Gauss-Seidel memerlukan 12 iterasi dengan error = 5.36e − 007. Sementara itu, pada metode SOR solusi tercepat diperoleh dengan menggunakan ω = 1.10 yaitu 7 iterasi dengan nilai error = 9.83e − 007. Selanjutnya pada metode KSOR, dengan menggunakan nilai parameter relaksasi ω ∗ = −14, metode ini menghasilkan solusi tercepat pada iterasi ke-7 dengan error = 3.85e − 007. 0.16
1.2
1
0.14 0.13
0.8 ρ(T)
ω*=−14.9200
0.15
ω=1.0718
ρ(T) 0.6
0.12 0.11 0.1
0.4
0.09 0.2
0.08
ρ(T)=0.0718 0
0
0.5
1
1.5
ρ(T)=0.0718 2 ω
(a)
−20
−18
−16
−14
−12
−10 ω*
(b)
Gambar 1: Grafik parameter relaksasi optimum terhadap nilai spektral radius: (a) metode SOR dan (b) metode KSOR.
Contoh 2 [1, h. 724] Tentukan solusi numerik untuk masalah nilai batas persamaan Poisson berikut ∂ 2u ∂ 2u + = −(cos(x − y) + cos(x − y)), ∂x2 ∂y 2
0 < x < π, 0 < y <
π ; 2
(6)
dengan syarat batas π u(π, y) = − cos y, 0 ≤ y ≤ ; 2 π u(x, 0) = cos x, u(x, ) = 0, 0 ≤ x ≤ π; 2
u(0, y) = cos y,
kemudian bandingkan hasilnya dengan solusi eksak u(x, y) = cos x cos y. Solusi. Untuk menentukan solusi numerik pada persamaan Poisson pada contoh 2 diatas akan digunakan x(0) = 0 dan nilai toleransi 1.0 × 10−6 dan membandingkan solusi numeriknya pada metode Gauss-Seidel, metode SOR dan metode KSOR. Dengan menggunakan diskritisasi metode Finite Difference[1, h. 717] pada per-
Repository FMIPA
7
samaan 6 diperoleh sistem persamaan linear Ax = b dengan 1.54 0.15 0 −0.62 0 0 0 0 0 −0.15 1.54 −0.15 0 −0.62 0 0 0 0 0 −0.15 1.54 0 0 −0.62 0 0 0 −0.62 0 0 1.54 −0.15 0 −0.62 0 0 −0.62 0 −0.15 1.54 −0.15 0 −0.62 0 A= 0 , 0 0 −0.62 0 −0.15 1.54 0 0 −0.62 0 0 0 −0.62 0 0 1.54 −0.15 0 0 0 0 0 −0.62 0 −0.15 1.54 −0.15 0 0 0 0 0 −0.62 0 −0.15 1.54 b=
[
0.70 0.00 −0.70 0.20 0.00 −0.20 0.11 0.00 −0.11
]T
.
Spektral radius dari Matrik Iterasi KSOR
Spektral radius dari Matrik Iterasi SOR 0.23
1.1 1
ω*=−6.820000
0.22
0.9
ω=1.180000
0.8
konvergen 10 iterasi
konvergen 9 iterasi
0.21
0.7 ρ(T)
0.6
ρ(T)
0.2
0.5 0.19
0.4 0.3
0.1
0.18
ρ(T)=0.180000
0.2
ρ(T)=0.171821 0
0.5
(a)
1
1.5
2 ω
0.17 −7
−6.8
−6.6
−6.4
−6.2
−6 ω*
(b)
Gambar 2: Grafik parameter relaksasi optimum terhadap nilai spektral radius untuk persoalan Poisson untuk matriks ukuran 9 × 9: (a) metode SOR dan (b) metode KSOR. Dari Gambar 2 tersebut terlihat bahwa untuk ukuran matriks 9 × 9 bila menggunakan parameter relaksasi optimum terhadap nilai spektral radius, terlihat bahwa metode SOR memerlukan iterasi sedikit lebih cepat yaitu dengan 9 iterasi bila dibandingkan dengan metode KSOR yang memerlukan 10 iterasi. Perbandingan hasil komputasi yang diperoleh dari ketiga metode tersebut dapat dilihat pada Tabel 2 dan Tabel 3 berikut.
Repository FMIPA
8
Tabel 2: Perbandingan Hasil Komputasi Contoh 3.2 dengan Metode Gauss-Seidel untuk beberapa ukuran matriks Ukuran Matriks 9×9 49 × 49 121 × 121 529 × 529
GS Iterasi 18 53 92 226
Error 6.33e − 007 9.02e − 007 9.52e − 007 9.98e − 007
Tabel 3: Perbandingan Hasil Komputasi Contoh 3.2 dengan Metode SOR dan Metode KSOR untuk beberapa ukuran matriks Ukuran Matriks 9×9 49 × 49 121 × 121 529 × 529
ω 1.20 1.55 1.60 1.75
SOR Iterasi Error 10 8.34e − 007 24 5.87e − 007 28 6.14e − 007 49 7.55e − 007
ω∗ −6.5 −3 −2.7 −2.7
KSOR Iterasi Error 9 3.38e − 007 22 5.32e − 007 27 5.99e − 007 64 9.42e − 007
Tabel 2 dan Tabel 3 menunjukkan perbandingan hasil komputasi metode GaussSeidel, metode SOR dan metode KSOR pada beberapa ukuran matriks koefisien A yang diperoleh dari penggunaan metode Finite Difference pada persamaan (6). Ukuran matriks yang dibandingkan adalah ukuran 9 × 9, 49 × 49, 121 × 121, dan matriks ukuran 529 × 529 untuk beberapa nilai parameter relaksasi yang berbeda pada metode SOR dan KSOR. Dari Gambar 3 berikut terlihat bahwa dengan menggunakan metode SOR dan KSOR, tidak terdapat perbedaan yang signifikan antara grafik solusi hampiran Poisson dan grafik solusi eksak.
Repository FMIPA
9
Grafik solusi hampiran dari Persoalan Poisson
Grafik solusi eksak
1
1
0.8
0.8
0.6
0.6
0.4
0.4
0.2
0.2
0
0
−0.2
−0.2
−0.4
−0.4
−0.6
−0.6
−0.8 −1 0
−0.8 1 0.5
1
1.5
(a)
2
2.5
3
0
−1 0
1 0.5
1
1.5
2
2.5
3
0
(b)
Gambar 3: Grafik solusi dari persoalan Poisson: (a) solusi hampiran Poisson dan (b) solusi eksak, untuk matriks ukuran 49 × 49. Berdasarkan pembahasan yang telah dikemukakan, dapat disimpulkan bahwa dengan menggunakan parameter relaksasi yang tepat secara umum metode KSOR dapat memberikan solusi tercepat bila dibandingkan dengan metode Gauss-Seidel. Selanjutnya bila dibandingkan dengan metode SOR, metode KSOR secara umum memberikan solusi yang tidak terlalu jauh berbeda, karena untuk kasus matriks dengan ukuran tertentu metode KSOR bisa memberikan solusi sedikit lebih cepat, sama, atau lebih lambat bila dibandingkan denga metode SOR. Dengan demikian pemilihan nilai parameter relaksasi yang digunakan dapat memberikan pengaruh dalam mempercepat konvergensi. Dalam hal ini bila dibandingkan dengan metode Gauss-Seidel, metode KSOR memerlukan iterasi yang jauh lebih sedikit. Akan tetapi bila dibandingkan dengan metode SOR, metode KSOR tidak memiliki perbedaan yang terlalu signifikan. DAFTAR PUSTAKA [1] Burden, R.L. & J. D. Faires. 2011. Numerical Analysis, 9th Ed. Brooks/Cole, Boston. [2] Kincaid, D. & Chenew, W. 1991. Numerical Analysis,Mathematics of Scientific Computing., Brooks/Cole, Pacific Grove, California. [3] Ortega, J.M. 1990. Numerical Analysis a Second Course., Academic Press, Inc, New York. [4] Youssef, I.K. 2012. On The Succesive Overrelaxation Method. Journal of Mathematics and Statistics., 8(2): 176-184. [5] Youssef, I.K. & Ibrahim. R.A, 2013. Boundary Value Problem, Fredholm Integral Equations, SOR and KSOR Methods. Life Science Journal., 10(2): 304312.
Repository FMIPA
10