NILAI SOLUSI PENDEKATAN SISTEM LINEAR SKALA BESAR MENGGUNAKAN GMRES Ismail bin Mohd1, Mustafa bin Mamat2, Yosza bin Dasril3, Fudziah Ismail4 dan Farikhin5 1, 2 Jabatan Matematika, Fakulti Sains dan Teknologi, Universiti Malaysia Terengganu 3 Jabatan Industrial Electrics, Faculty of Electrics & Comp Engineering, Universiti Teknikal Malaysia Melaka 4 Jabatan Matematika, Fakulti Sains, Universiti Putra Malaysia 5 Jurusan Matematika, FMIPA UNDIP Semarang Indonesia, e-mail :
[email protected]
Abstract. Many engineering process require the solution of linear system of the form Ax = b , n
where A is a n × n nonsingular real matrix, b ∈ R , and vector x is solution of the linear system. There are two methods for solving large scale linear system which are full orthogonalization method (FOM) and Generalized minimal residual (GMRES). GMRES is most popular method to solve large scale linear equations. In this paper, we proven that GMRES preserved the magnitude of approximations solution of linear system. Keywords: Linear System, GMRES, Krylov Subspace and Algorithm Arnoldi.
1. PENDAHULUAN Sistem linear Ax = b banyak digunakan untuk mencari solusi pendekatan dalam bidang sains dan rekayasa. Solusi sistem linear skala besar dapat menggunakan ruang bagian Krylov. Golan [3] membahas tentang ruang bagian Krylov. Secara garis besar, metode berdasarkan ruang bagian Krylov dikelompokkan dalam dua metode. Metode pertama disebut Full Orthogonalization Method (FOM). Metode kedua disebut Generalized Minimal Residual (GMRES). Metode pertama diusulkan pertama kali oleh Saad, sedangkan metode kedua diusulkan pertama kali oleh Saad dan Schultz ([1],[2],[7]). Metode GMRES merupakan metode iterative yang populer untuk menyelesaikan sistem linear skala besar. Berbagai varian dari metode GMRES memperlihatkan peningkatan kinerja GMRES dalam hal kecepatan komputasi dan penggunaan memori. Kecepatan komputasi metode GMRES dibahas secara detail oleh Essai, Ayachour, Najafi dan Zareamoghaddam, dan Roube & Sadkane ([1], [2], [7], [6]). Dalam tulisan ini diperlihatkan bahwa perubahan norma atau hasil kali dalam
(inner product) tidak mempengaruhi nilai solusi pendekatan yang dihasilkan. 2. RUANG BAGIAN KRYLOV Diberikan A matriks n × n yang entri-entrinya bilangan real dan v ∈ R n . Ruang bagian yang dibangun oleh vektor-
{
}
vektor v , Av , A 2 v ,..., A m−1v dinamakan ruang bagian Krylov (Krylov subspace). Untuk penyerdahanaan, ruang bagian ditulis dengan v , Av , A 2 v ,..., A m−1v K m ( A, v ) . Bila dicermati, ruang bagian Krylov K m ( A, v ) adalah koleksi vektor
{
}
x ∈ R n sedemikian sehingga x = p ( A)v , dengan p (x) polinomial berderejat kurang dari atau sama dengan m − 1 . Dimensi ruang Krylov K m ( A, v ) dapat dikatakan sebagai ukuran sejauh mana vektor v terhadap vektor-vektor eigen matriks A (Ayachour, 2003). Beberapa sifat ruang bagian Krylov disajikan seperti di bawah ini. Untuk bukti lengkapnya dapat dilihat dalam [3] dan [7]. • Ruang K m ( A, v ) invarian terhadap matriks A . 106
Ismail bin Mohd1, Mustafa bin Mamat2, Yosza bin Dasril3, Fudziah Ismail4 dan Farikhin5 (Nilai Solusi ...)
Dimensi K m ( A, v ) sama dengan m jika dan hanya jika derajat polinomial minimal untuk matriks A lebih besar m −1. Hubungan antara ruang Krylov dengan sistem persamaan linear dijelaskan dalam teorema berikut.
•
Teorema 1 Diberikan sistem persamaan linear tak homogen Ax = b , dengan A ∈ R m×m non-singular dan derajat matriks polinomial minimalnya sama dengan m. Jika z solusi Ax = b maka z ∈ K m ( A, b )
Bukti Menurut Teorema Cayley-Hamilton, didapat Am + a1 Am−1 + a2 Am−2 + ...+ am−1 A+ am I m = θ ⇔ A m −1 + a1 A m − 2 + ... + a m −1 I m + a m A −1 = θ ⇔ A −1 = −
1 A m −1 + a1 A m −2 + ... + a m −1 I m am
(
)
Diketahui z = A −1b maka 1 (A m−1b + a1 A m−2 b + ... + a m−1b ) z=− am sehingga z ∈ K m ( A, b ) .
■
Teorema 2 Diketahui K m ( A, v ) ruang bagian Krylov maka terdapat kumpulan vektor {v1 , v 2 ,..., v m } yang merupakan basis K m ( A, v ) . Bukti Tanpa mengurangi umumnya persoalan dapat dianggap v1 = 1. Dibentuk vektor-vektor seperti pada proses Gram-Schimdt sebagai berikut. • v1 = v1 ,
•
v2 =
w2 w2
,
w2 = Av1 − < Av1 , v1 > v1
107
dengan
•
v3 =
w3 w3
,
dengan
w3 = Av 2 − < Av1 , v1 > v1 − < Av 2 , v 2 > v 2
•
vm =
wm wm
,
dengan m −1
wm = Av m −1 − Σ < Av j , v j > v j . j =1
Koleksi vektor {v1 , v 2 ,..., v m } saling asing dan v j = 1 untuk j = 1,2,3,..., m . Perhatikan vektor {v1 , v2 ,..., vm } , diperoleh hubungan • v1 = p0 ( A)v1 , dengan p 0 ( x) = 1 , • v 2 = p1 ( A)v1 , dengan p1 ( x) polinomial berderajat 1, • v3 = p 2 ( A)v1 , dengan p 2 ( x) polinomial berderajat 2, • v m = p m−1 ( A)v1 , dengan p m−1 ( x ) polinomial berderajat m − 1 . Jika x ∈ K m ( A, v1 ) maka x = p( A)v1 , untuk suatu polinomial p( x) dan derajat Oleh karena itu, p ( x) ≤ m − 1 . x ∈ K m ( A, v ) dapat ditulis sebagai kombinasi linear dari {v1 , v 2 ,..., v m } . Jadi {v1 , v 2 ,..., v m } merentang ruang K m ( A, v ) .
Perhatikan kembali rekontruksi kumpulan vektor {v1 , v 2 ,..., v m } dalam teorema 2. Proses mencari vektor-vektor v1 , v 2 ,..., dan v m dinamakan algoritma Arnoldi. Algoritma Arnoldi. ([4], [5]) 1. Inisialisasi. Dipilih vektor v1 = 1. 2. Proses iterasi. Untuk j = 1, 2, 3, ..., m dihitung hi , j = Avi , v j , i = 1, 2, 3, ..., j. j
w j = Av j − ∑ hi , j vi , h j +1, j = w j , i =1
dan v j +1 =
wj h j +1, j
.
Jurnal Matematika Vol. 11, No.3, Desember 2008:106-110
Dibentuk matriks Hessenberg m× m h2,m h2,1 h2,2 h2,m −1 h3,2 h3,m −1 h3,m , Hm = hm,m−1 hm,m hm +1,m dengan entri-entri di bawah diagonal utama matriks H m sama dengan nol. Dibentuk juga matriks Vm = [v1 , v 2 , , v m ] berukuran n × m . Hubungan antara matriks H m dan Vm ditulis dalam teorema berikut. Teorema 3 Misalkan H m dan Vm dua matriks seperti
dalam uraian sebelumnya.
x m ∈ x0 + K m ( A, ro ) , b − Ax m =
dengan b − Ax .
min x∈x0 + K m ( A, r0 )
Algoritma GMRES. 1. Pilih input x0 , m dan ε . Kemudian
hitung r0 = b − Ax0 . 2. Hitung α = r0
2
dan v1 =
r0
α
.
3. Konstruksikan basis ortonomal seperti pada algoritma Arnoldi yang menggunakan hasil kali dalam (inner product) , .
y m = min α e1 − H m y
4. Hitung
y∈R m
2
dengan e1 = (1,0,0...,0) ∈ R m +1 , x m = Vm y m + xo , dan
w Jika H m = , Hm
rm = b − Ax m .
dengan w = ( h1,1 , h 2,1 , , hm ,1 ) , maka: (a). H m = VmT AVm ,
5. Jika
(b). AVk = Vk +1 H k ,
rm
2
r0
2
≤ ε , maka proses berhenti
= I k , dengan I k matriks identitas. Untuk bukti lengkap Teorema 3, dapat dilihat dalam referensi ([1], [3], [5]]
dan x m adalah solusi pendekatan yang dicari. Jika tidak, maka x0 = x m dan r0 = rm . Kemudian kembali ke 2.
3. METODE GMRES Diberikan sistem linear skala besar Ax = b , dengan x dan b vektor yang termuat dalam R n . Misalkan x0 vektor
Pada umumnya, norm yang digunakan pada algoritma Arnoldi atau GMRES menggunakan definisi
(c).
VkT Vk
n
inisial dan x = x0 + z , dengan z ∈ R . Sistem linear berubah menjadi Az = r0 , dengan r0 = b − Ax0 residual vektor. Berdasarkan ruang bagian Krylov, beberapa metode dibuat untuk mencari solusi pendekatan sistem linear Az = r0 . Saad dan Schultz mengusulkan suatu metode untuk menyelesaikan sistem linear Az = r0 . Metode ini dinamakan Generalized Minimal Residual (GMRES) ([1],[2], [5]). Metode GMRES adalah metode untuk mencari vektor
x
2
= x12 + x 2 2 + ... + x n 2
x ∈ Rn .
Definisi suatu norm matriks erat hubungannya dengan jumlah iterasi untuk mencari solusi pendekatan. Algoritma GMRES dimodifikasi untuk meningkatkan kinerjanya, dengan cara mengganti norm x
2
dengan norm x
D
=
x T Dx , dengan
d1,1 d 2, 2 D= d n −1,n −1 matriks diagonal dan d i ,i > 0
d n ,n
108
Ismail bin Mohd1, Mustafa bin Mamat2, Yosza bin Dasril3, Fudziah Ismail4 dan Farikhin5 (Nilai Solusi ...)
Norma
x
T
D
digunakan
= x Dx
untuk membuat koleksi vektor ortonormal seperti dalam algoritma Arnoldi. Pembatasan d i ,i > 0 dimaksudkan agar definisi hasilkali dalam
x, y
D
= y T Dx
well-defined ([1], [2], [[5]). Lebih lanjut, Essai memberikan syarat untuk pemilihan entri diagonal utama matriks D harus memenuhi n=
d12,1
+ d 22,2
+ + d n2,n
(r0 )i
d i ,i =
r0
dan
(Essai, 1998). Najafi &
2
Teorema 4 Diketahui {v1 , v 2 ,..., v m } vektor-vektor yang dihasilkan dari proses algoritma Arnoldi yang menggunakan hasilkali dalam D
= y T Dx . Jika hasilkali dalam T
x , y E = y Ex , dengan E = αD , maka ~ x m = x m , di mana ~ x m solusi pendekatan yang menggunakan x , y Bukti
{
E
= y T Ex .
}
Karena
T
E
= y Ex .
E = αD ,
v0
,
dan
v1 = α v1
dan
v1 =
v0 E
v v1 = 0 v0 D
maka
w1 = α w1 . Oleh karena itu,
109
v2
1 α
vm
] (1)
~ dan hi, j = Av i , v j
= v j T (αD )v i E
T
vj v (αD ) i = α α = v j T Dv i = A v i , v j
D
(2) ~ Jika H m matriks Hessenberg yang terkait dengan hasilkali dalam , E dan ~ ~ hi, j = hi, j , maka H m = H m , sehingga ~ w ~ Hm = ~ H m w = H m (3) = Hm . Dari hasil (1), (2) dan (3) diperoleh ~ ~ x m = x0 + Vm ~y m = x0 + = xm .
(
1 V α m
)( α y ) m
■
Teorema 4 memperlihatkan bahwa perubahan penggunaan hasilkali dalam (inner product) tidak mempengaruhi solusi pendekatan yang dihasilkan.
Misalkan v1 , v 2 ,, v m vektor-vektor yang dihasilkan dari proses algoritma Arnoldi yang menggunakan hasilkali dalam x , y
=
1 v 1 α 1 α 1 V , α m
]
= hi , j .
Zareamoghaddam memodifikasi algoritma GMRES dengan cara memilih entri diagonal utama matriks D yang berbeda. Entri-entri ini diambil 0.5 < d i ,i < 1.5 secara random [5].
x, y
[ =[
~ Vm = v1 v 2 v m
i = 1, 2, 3, ..., n.
4. KESIMPULAN Perubahan norma yang digunakan dalam metode GMRES tidak mempengaruhi nilai solusi pendekatan yang dihasilkan. Oleh karenanya, untuk meningkatkan kinerja metode GMRES dapat dimungkinkan dengan memodifikasi nilai-nilai diagonal utama matriks D yang digunakan dalam penghitungan proses Arnoldi.
Jurnal Matematika Vol. 11, No.3, Desember 2008:106-110
5. UCAPAN TERIMA KASIH Penulis mengucapkan terima kasih kepada Universiti Malaysia Terengganu (UMT) Malaysia yang telah memberikan bantuan finansial penelitian ini melalui Skim Kewangan Siswazah (Postgraduate Financial Scheme) 2008. 6. DAFTAR PUSTAKA [1] Ayachour, E. H. (2003), A Fast Implementation for GMRES Method, Journal of Computation and Applied, Vol. 159 : 269 – 283. [2] Essai, A. (1998), Weighted FOM and GMRES for Solving Nonsymmetric Linear System, Numerical Method, Vol. 18 : 277 – 292.
[3] Golan, J. S. (2007), The Linear Algebra, Springer, Netherland. [4] Heoyuni , M. and Sadok, H. (1998), On a Variable Smoothing Procedure for Krylov Subspace Methods, Linear Algebra and Its Applications Vol. 268 : 131 – 149. [5] Najafi, H. S. and Zareamoghaddam (2007), A New Computational GMRES Methods, Applied Mathematics and Computation, Article in Press. [6] Roube, M. and Sadkane, M. (2006), Exact and Inexact Breakdown in the Block GMRES, Linear Algebra and Its Applications Vol.419 : 265 – 285. [7] Saad, Y. (1992), Numerical Methods for Large Eigenvalue Problems, Manchester University Press (monograph series), UK.
110