PERBANDINGAN METODE GAUSS-SEIDEL PREKONDISI DAN METODE SOR UNTUK MENDAPATKAN SOLUSI SISTEM PERSAMAAN LINEAR Merintan Afrina S Mahasiswa Program Studi S1 Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Riau Kampus Bina Widya Pekanbaru 28293, Indonesia
[email protected]
ABSTRACT This paper discusses the preconditioner for solving the linear system Ax = b, where A is of the form M -matrix. The paper review of Li-ying Sun [Journal of Computational and Applied Mathematics, 181(2005), 336 − 341]. Numerically that the improving modified Gauss-Seidel method, which was referred to as the IMGS method, the spectral radius of the preconditioned IMGS method is smaller than that of the SOR method and Gauss-Seidel method. Numerical simulation using some size of A show that the convergence rate of IMGS method can be increased using the preconditioner. Keywords: M -matrix, spectral radius, SOR iterative method, regular splitting ABSTRAK Skripsi ini membahas prekondisi untuk menyelesaikan sistem persamaan linear Ax = b, dengan A berbentuk M -matriks, yang merupakan review dari artikel Liying Sun [Journal of Computational and Applied Mathematics, 181(2005), 336−341]. Secara numerik ditunjukkan bahwa spektral radius metode Gauss-Seidel prekondisi lebih kecil dari metode SOR dan metode iterasi Gauss-Seidel. Dari contoh komputasi dengan ukuran matriks A bervariasi terlihat bahwa kecepatan konvergensi metode Gauss-Seidel meningkat dengan menggunakan prekondisi dibandingkan tanpa menggunakan prekondisi. Kata kunci: M -matriks, spektral radius, metode iterasi SOR, regular splitting
1
1. PENDAHULUAN Sebuah Sistem Persamaan Linear (SPL) dapat ditulis dalam bentuk persamaan matriks Ax = b,
(1)
dengan matriks koefisien A ∈ Rn×n dan vektor x, b ∈ Rn . Apabila matriks A nonsingular maka solusi eksak dari SPL (1) adalah x = A−1 b. Untuk menyelesaikan SPL (1) dapat menggunakan dua metode yaitu metode langsung dan metode iterasi. Adapun metode langsung dapat dilakukan dengan menggunakan metode eliminasi Gauss dan metode faktorisasi LU. Sedangkan metode iterasi dengan menggunakan metode Gauss-Seidel dan metode SOR (Successive Over Relaxation). Dalam penerapannya, konvergensi metode Gauss-Seidel sangat lambat dibandingkan dengan metode SOR, bila matriks A berkondisi buruk. Untuk mengatasi ini diperlukannya suatu teknik untuk mempercepat konvergensi metode Gauss-Seidel yaitu menggunakan prekondisi, sehingga persamaan (1) menjadi P Ax = P b,
(2)
dengan P ∈ Rn×n adalah matriks prekondisi yang nonsingular. Pembahasan disini merupakan review artikel yang berjudul ”A Comparison Theorem for The SOR Iterative Method”[11]. Pembahasan dimulai dengan menyajikan metode Gauss-Seidel dan metode SOR. Kemudian dilanjutkan dengan metode prekondisi dibagian 2. Dibagian 3 didiskusikan metode Gauss-Seidel prekondisi untuk M -matriks, dan diakhiri dengan uji komputasi dibagian 4. 2. METODE GAUSS-SEIDEL DAN METODE SOR 2.1 Metode Iterasi Dasar Misalkan matriks A adalah matriks nonsingular dan semua elemen diagonalnya tidak sama nol. Untuk mencari solusi SPL (1) dengan menggunakan metode iterasi, matriks A dapat dipisah menjadi A = M −N dengan M adalah matriks nonsingular, sehingga persamaan (1) dapat ditulis menjadi M x = N x + b,
(3)
x = M −1 N x + M −1 b.
(4)
atau
Dari persamaan (4) dapat dibentuk metode iterasi jika diberikan tebakan awal x ∈ Rn adalah (0)
x(k) = M −1 N x(k−1) + M −1 b,
k = 1, 2, . . . .
(5)
Persamaan (5) juga dapat ditulis menjadi x(k) = T x(k−1) + c,
(6)
dengan T = M −1 N dan c = M −1 b. 2
Definisi 1 (Spektral Radius) [4, h.446] Misalkan A = (aij ) adalah matriks nonsingular berukuran n × n, dengan nilai eigen λi adalah (1 ≤ i ≤ n) maka ρ(A) = max |λi |, 1≤i≤n
adalah spektral radius untuk A. Lema 2 [4, h.457] Jika spektral radius dari T memenuhi ρ(T ) < 1, maka nilai (I − T )−1 ada dan −1
(I − T )
2
= I + T + T + ... =
∞ ∑
T j.
j=0
Teorema 3 [4, h. 457] Untuk tebakan awal x(0) ∈ Rn maka barisan x(k) pada persamaan (6) konvergen ke solusi SPL (1) jika dan hanya jika ρ(T ) < 1. Persamaan (6) merupakan metode iterasi dasar untuk mencari solusi SPL. Persamaan (6) dikatakan konvergen jika x(k) → x ketika k → ∞. Hal ini diperoleh jika spektral radiusnya dari matriks T lebih kecil dari 1 atau ρ(T ) < 1. 2.2 Metode Gauss-Seidel dan metode SOR Untuk keperluan lain, matriks A juga dapat dipisah menjadi A = D − L − U dengan D adalah matriks diagonal, L adalah segitiga bawah kuat, dan U adalah matriks segitiga atas kuat. Pada metode Gauss-Seidel dipisah A = M −N dengan M = D−L dan N = U . Dengan mensubstitusikan M dan N ke persamaan (6) diperoleh x(k) = (D − L)−1 U x(k−1) + (D − L)−1 b,
k = 1, 2, . . . .
(7)
Persamaan (7) merupakan metode Gauss-Seidel untuk mencari solusi SPL (1). Pada metode SOR dipisah A = D − L − U , dengan M = (D − ωL) dan N = [(1 − ω)D + ωU ]. Dengan mensubstitusikan M dan N ke persamaan (6) diperoleh x(k) = (D − ωL)−1 [(1 − ω)D + ωU ]x(k−1) + ω(D − ωL)−1 b,
k = 0, 1, 2, . . . . (8)
Persamaan (8) merupakan metode SOR untuk mencari solusi SPL (1). Konvergensi metode Gauss-Seidel dan metode SOR untuk SPL (1) dengan matriks diagonal dominan kuat diberikan teorema berikut. Teorema 4 [8, h. 189] Jika A adalah matriks diagonal dominan kuat, maka metode iterasi Gauss-Seidel konvergen untuk tebakan awal x(0) ∈ Rn ke solusi SPL (1). Lema 5 [11, h. 231] Misalkan A = M − N adalah M -splitting dari A, maka ρ(M −1 N ) < 1 jika dan hanya jika A adalah M -matriks nonsingular. Teorema 6 [12, h. 91] Misalkan suatu matriks A = (aij ) nonsingular yang berukuran n × n dengan aij ≤ 0, untuk i ̸= j, A−1 ≥ 0 dengan 0 adalah matriks nol, maka matriks A disebut M -matriks. 3
Teorema 7 [13, h. 337] Suatu matriks A=(aij ) dengan aij ≤ 0 untuk i ̸= j dan aii = 1, maka matriks A disebut Z-matriks. Teorema 8 [11, h. 338] Misalkan matriks A adalah Z-matriks, maka pernyataan berikut ekuivalen sama yang lain (1) A adalah M -matriks nonsingular, (2) Semua submatrik utama dari A adalah M -matriks nonsingular, (3) Semua minor utama adalah positive. 2.3 Metode Prekondisi Baik atau buruknya kondisi suatu matriks ditentukan oleh bilangan kondisi dari suatu matriks. Definisi 9 [1, h.182] Bilangan kondisi dari matriks A nonsingular yang relatif terhadap ∥A∥∞ adalah
cond(A) = ∥A∥∞ A−1 ∞ . Definisi 10 [10, h. 357] Suatu matriks A disebut berkondisi buruk jika perubahan yang relatif kecil dalam elemen-elemennya dapat menyebabkan perubahan yang relatif besar dalam penyelesaian terhadap solusi Ax = b. Matriks A berkondisi baik jika perubahan relatif kecil dalam elemen-elemennya mengakibatkan terjadinya perubahan yang relatif kecil dalam solusi Ax = b. Untuk bilangan kondisi mendekati 1 maka matriks A berkondisi baik. Sebaliknya, jika bilangan kondisi lebih besar dari 1 maka matriks A berkondisi buruk. Dalam menyelesaikan SPL (1) dengan matriks A berkondisi buruk dapat menggunakan metode prekondisi P Ax = P b, dengan P A ∈ Rn×n dan x, P b ∈ Rn . Apabila bilangan kondisi cond(P A) < cond(A), maka konvergensi metode prekondisi lebih cepat dibandingkan dengan tanpa menggunakan prekondisi. [1, h.182] Pada tahun 1997 Kohno et al., [9] menggunakan prekondisi I + Sα yang dinotasikan dengan P untuk mencari solusi SPL (1) dengan I adalah matriks identitas dan 0 −α1 a12 0 ··· 0 0 0 −α2 a23 · · · 0 .. .. .. .. ... (9) Sα = . . . . . 0 0 0 · · · −αn−1 an−1,n 0 0 0 0 0 Sehingga bentuk matriks prekondisi adalah 1 −α1 a12 0 ··· 0 0 1 −α a · · · 0 2 23 .. . .. . . .. .. .. P = I + Sα = . . 0 0 0 1 −αn−1 an−1,n 0 0 0 0 1
.
(10)
4
3. METODE GAUSS-SEIDEL PREKONDISI Pandang SPL Ax = b, dengan matriks koefisien A ∈ Rn×n yang berukuran M matriks. Bila A berkondisi buruk maka digunakan metode Gauss-Seidel prekondisi dengan matriks prekondisi [9] yang digunakan adalah P = I + Sα , dengan
Sα =
0 −α1 a12 0 ··· 0 0 0 −α2 a23 · · · 0 .. .. .. .. ... . . . . 0 0 0 · · · −αn−1 an−1,n 0 0 0 0 0
(11) .
(12)
Dengan mengalikan kedua ruas dari kiri persamaan (1) dengan P pada persamaan (11) P Ax = P b, (I + Sα )Ax = (I + Sα )b, Aα x = bα ,
(13)
Aα = (I + Sα )A, bα = (I + Sα )b.
(14) (15)
dengan
Matriks koefisien Aα pada persamaan (13), dapat dinyatakan dengan Aα Aα Aα Aα
= (I + Sα )A, = (I + Sα )(I − L − U ), = I − L − U + Sα − Sα L − Sα U, = I − L − Sα L − (U − Sα + Sα U ).
(16)
Sehingga matriks iterasi dari metode Gauss-Seidel dapat ditulis menjadi Tα = (I − L − Sα L)−1 (U − Sα + Sα U ),
(17)
Mα = (I − L − Sα L), Nα = (U − Sα + Sα U ).
(18) (19)
dengan
Sehingga dengan menerapkan splitting dari matriks Aα ke persamaan (13) diperoleh (Mα − Nα )x = bα Mα x = Nα x + bα .
(20) 5
Karena Mα adalah matriks nonsingular, maka Mα memiliki invers sehingga persamaan (20) menjadi x = Mα−1 Nα x + Mα−1 bα .
(21)
Seperti metode iterasi sebelumnya, dari persamaan (21) dapat dibentuk metode iterasi jika diberikan tebakan awal x(0) ∈ Rn sehingga diperoleh x(k) = Mα−1 Nα x(k−1) + Mα−1 bα ,
k = 1, 2, . . . .
(22)
Persamaan (22) merupakan metode iterasi Gauss-Seidel prekondisi untuk mencari solusi SPL (1). Pada persamaan (22) juga dapat dituliskan dalam bentuk x(k) = Tα x(k−1) + c,
(23)
dengan Tα = Mα−1 Nα dan c = Mα−1 bα . Teorema 11 [13, h. 232] Misalkan A = (aij ) ∈ Rn×n dan A = I − L − U , dengan U adalah matriks nonnegative dan L adalah matriks segitiga bawah nonnegative. Maka untuk setiap αi ∈ (0.1], i = 1, 2, . . . , n − 1, ρ(Tα ) < 1 jika ρ(TM GS ) < 1. ρ(Tα ) ≤ ρ(TM GS ) < 1. Sehingga jika A adalah irreducible, maka ρ(Tα ) ≤ ρ(TM GS ) untuk αi ∈ (0.1]. Bukti. Aα = (I + Sα )A, = (I + Sα )(I − L − U ), = (I + Sα )(I − L) − (I + Sα )U, Aα = Mα − Nα , dengan Mα = (I + Sα )(I − L), Nα = (I + Sα )U, misalkan Eα = I − (I + Sα )L, Fα = U − Sα + Sα U. Jika L adalah matriks matriks segitiga bawah kuat nonnegative, I − L adalah M -matriks nonsingular, maka A = (I−L)−U adalah M -splitting. Aα juga merupakan M -matriks nonsingular, dan Eα adalah Z-matriks segitiga bawah Maka Aα = Eα − Fα merupakan M -splitting pada nonsingular Aα dari, ρ(Tα ) < 1.
6
Misalkan A−1 ≥ 0 dan Aα = Mα − Nα = Eα − Fα maka Nα ≥ Fα dengan Lema 5 bahwa ρ(Tα ) < 1 Mα−1 Nα = (I − L)−1 U ≥ 0, diperoleh ρ(Mα−1 Nα ) = ρ((I − L)−1 U ) = ρ(TM GS ) < 1, ρ(A−1 Nα ) ≤ ρ(A−1 Fα ), ρ(A−1 Nα ) ρ(A−1 Fα ) −1 ρ(Mα Nα ) = ≤ = ρ(Eα−1 Fα ). −1 −1 1 + ρ(A Nα ) 1 + ρ(A Fα ) Maka ρ(Eα−1 Fα ) ≤ ρ(Mα−1 Nα ) < 1. Sehingga ρ(Tα ) < 1 terbukti. 4. UJI KOMPUTASI Contoh 1 [4, h. 723] Tentukan solusi numerik untuk masalah nilai batas persamaan Poisson ∂ 2u ∂ 2u + = 4 0 < x < 1, 0 < y < 2; (24) ∂x2 ∂y 2 dengan syarat batas u(x, 0) = x2 ,
u(x, 2) = (x − 2)2 ,
0 ≤ x ≤ 1;
u(0, y) = y 2 ,
u(1, y) = (y − 1)2 ,
0 ≤ y ≤ 2,
dengan solusi eksak u(x, y) = (x − y)2 . Solusi. Solusi numerik dari persamaan (24) terlebih dahulu dengan menggunakan proses diskritisasi dengan metode Beda Hingga [4, h. 717] maka diperoleh ∂2u wi−1,j − 2wi,j + k 2 wi+1,j ≈ , ∂x2 h2
(25)
∂ 2u wi,j−1 − 2wi,j + wi,j+1 ≈ , ∂y 2 k2
(26)
dengan wi,j ≈ u(xi , yj ). Selanjutnya, dengan mensubstitusikan persamaan (25) dan persamaan (26), ke persamaan (24) diperoleh −k 2 wi−1,j + 2(k 2 + h2 )wi,j − k 2 wi+1,j − h2 wi,j−1 − h2 wi,j+1 = −4h2 k 2
(27)
untuk i = 1, 2, 3 dan j = 1, 2, 3.
7
Tabel 1: Hasil Spektral Radius (MGS), (MSOR), (MGSP) Ukuran Matriks 4×4 4×4 4×4 9×9 9×9 9×9
Metode MGS MSOR MGSP MGS MSOR MGSP
Iterasi 10 9 6 18 10 8
ω
α
1.15 0.8 1.20 1.85
ρ(T ) 0.3086 0.1500 0.0755 0.1953 0.2000 0.0198
∥x(k) − x(k−1) ∥∞ 7.8e − 07 2.9473e − 07 9.5e − 07 7.4e − 07 7.2393e − 07 6.6e − 07
Dapat dilihat pada Tabel 1, bahwa perbandingan spektral radius dari metode Gauss-Seidel (MGS), metode SOR (MSOR), dan metode Gauss-Seidel prekondisi (MGSP) dengan parameter α dan ω yang berbeda. Dapat juga dilihat bahwa ρ(TM GSP ) < ρ(TM S0R ) < ρ(TM GS ) < 1, dengan semakin besar nilai α, maka banyak iterasinya semakin berkurang dan spektral radiusnya mendekati nilai sebenarnya. Oleh karena itu, metode Gauss-Seidel prekondisi (MGSP) relatif lebih cepat iterasinya daripada metode Gauss-Seidel (MGS) dan Metode SOR (MSOR). Adapun solusi dari persoalan Poisson Finite Difference seperti pada Gambar 1 Grafik solusi dari Persoalan Poisson
4
3
2
1
0 2 1.5
1 0.8
1
0.6 0.4
0.5 0
0.2 0
Gambar 1: Grafik solusi dari persoalan Poisson
8
10
10
MGS MGSP MSOR
0
−2
eror
10
2
10
10
10
−4
−6
−8
0
5
10
15
20
iterasi
Gambar 2: Grafik konvergensi dari GS, IMGS, SOR
Dapat dilihat Gambar 2 dari ketiga konvergensi metode MGS, MSOR dan MGSP, pada sumbu absis adalah menunjukkan nilai eror, dan sumbu ordinat menunjukkan banyak iterasi. Maka dengan menggunakan metode Gauss-Seidel konvergen dengan ukuran matriks n = 4 dan tebakan awal x(0) ∈ Rn banyak iterasinya 18. Dengan metode SOR konvergen dengan ukuran matriks n = 4, ω = 1.20 dan tebakan awal x(0) ∈ Rn banyak iterasinya 10. Dengan metode MGSP konvergen dengan ukuran matriks n = 4, α = 1.85 dan tebakan awal x(0) ∈ Rn banyak iterasinya 8. Maka dapat disimpulkan dengan menggunakan metode Gauss-Seidel prekondisi (MGSP) relatif lebih cepat konvergen daripada metode SOR (MSOR) dan metode Gauss-Seidel (MGS). 5. KESIMPULAN Berdasarkan pembahasan yang telah dikemukakan sebelumnya, bahwa untuk menyelesaikan SPL (1) dengan A adalah M -Matriks, dengan matriks A berkondisi buruk, maka metode yang tepat untuk mempercepat konvergensi iterasi metode Gauss-Seidel yaitu dengan menggunakan metode Prekondisi pada persamaan (11) tersebut ke SPL (1). Semakin besar nilai α, maka banyak iterasinya akan semakin sedikit dan nilai eror mendekati nilai sebenarnya. Keunggulan dari metode Gauss-Seidel prekondisi daripada metode Gauss-Seidel dan metode SOR dapat dilihat dari uji komputasi. Membandingkan jumlah iterasi dan spektral radius terlihat bahwa metode Gauss-Seidel prekondisi relatif lebih cepat konvergen dengan ρ(TM GS ) < ρ(TM SOR ) < ρ(TM GSP ) < 1. Sehingga dapat disimpulkan bahwa metode Gauss-Seidel prekondisi lebih unggul daripada metode Gauss-Seidel dan metode SOR. 9
Ucapan Terima Kasih Ucapan terima kasih diberikan kepada Dr. Syamsudhuha, M.Sc. dan ibu Dra. Asli Sirait, M.Si. yang telah membimbing dan memberikan arahan dalam penulisan artikel ini. DAFTAR PUSTAKA [1] G. Allaire dan S. M. Kaber, Numerical Linear Algebra, Springer, New York, 2008. [2] H. Anton, Aljabar Linear Elementer, Edisi kelima. Terj. dari Elementary Linear Algebra, Fifth Ed., oleh S. Pantur, Penerbit Erlangga, Jakarta, 1987. [3] A. Berman dan R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, SIAM, Philadelphia, 1994. [4] R. L. Burden dan J. D. Faires, Numerical Analysis, Ninth Ed., Brooks Cole, New York, 2010. [5] L. Elsner, Comparisons of weak regular splittings and multisplitting methods, Numer., Math., 56 (1989), 283-289. [6] M. Imran, Modul Kuliah Aljabar Linear Numerik: Solusi Persamaan Linear, Jurusan Matematika FMIPA UNRI, Pekanbaru, 2010. [7] E. Issacson, dan H. B. Keller. Analysis of Numerical Methods, Dover Publication, Inc, New York, 1966. [8] D. Kincaid dan W. Cheney, Numerical Analysis Mathematics of Scientific Computing, Brooks Cole, Publishing Company, California, 1991. [9] T. Kohno et al., Improving the modified iterative method for Z-matrices, Applied Linear Algebra, 267 (1997), 113-123. [10] S. J. Leon, Aljabar Linear dan Aplikasinya, Edisi kelima. Terj. dari Linear Algebra with Application, Fifth Ed., oleh A. Bondan, Penerbit Erlangga, Jakarta, 2001. [11] Li-ying. Sun, A comparison theorem for the SOR iterative method, Applied Linear Algebra, 181 (2005), 336-341. [12] R. S. Varga, Matrix Iterative Analysis, Prentice-hall, Englewood Cliffs, New York, 1962. [13] W. Wenli dan W. Sun, Modified Gauss-Seidel methods and Jacobi type methods for Z-matrices, Applied Linear Algebra, 317 (2000), 227-240.
10
