METODE PANGKAT BALIK TERGESER UNTUK MENCARI NILAI EIGEN DAN VEKTOR EIGEN

METODE PANGKAT BALIK TERGESER UNTUK MENCARI NILAI EIGEN DAN VEKTOR EIGEN Sangadji 1 ABSTRACT Article discusses the shifted power method as the extension of the power method. The shifted power method also requires a good starting approximation for obtaining an eigen value and then iteration is used to obtain an exact solution. It assumes that the eigen values are real and distinct. Cases involving complex eigen values, multiple eigen values, or the presence of two eigen values with the same magnitude will cause computational difficulties and require more advanced method. Keywords: shifted inverse power method, inverse power method, power method

ABSTRAK Artikel membahas metode pangkat balik tergeser sebagai perluasan metode pangkat. Metode pangkat balik tergeser juga memerlukan pendekatan awal yang baik untuk mendapatkan suatu nilai eigen, dan kemudian iterasi digunakan untuk mendapatkan solusi eksak. Diasumsikan, bahwa nilai eigen adalah real dan berlainan. Kasus yang melibatkan nilai eigen yang kompleks, nilai eigen multipel, atau adanya dua nilai eigen yang nilai mutlaknya sama akan berakibat timbulnya kesulitan dalam komputasi, dan memerlukan metode yang lebih maju. Kata kunci: metode pangkat balik tergeser, metode pangkat balik, metode pangkat

1

Staf Peneliti PPIN BATAN, Kompleks PUSPIPTEK Serpong Jurusan Matematika, Fakultas Sains dan Teknologi, Universitas Bina Nusantara, Jl. K.H. Syahdan No. 9 Palmerah, Jakarta Barat 11480, [email protected]

Metode Pangkat Balik Tergeser … (Sangadji)

75

PENDAHULUAN Misalkan matriks bujur sangkar A mempunyai nilai eigen dominan λ dan misalkan terdapat tepat satu vektor eigen ternormalisir V yang bersesuaian dengan λ . Pasangan λ , V itu dapat diperoleh dengan prosedur iteratif berikut yang disebut metode pangkat. Dimulai dengan vektor

X 0 = (1,1, K,1) . T

(1)

Bentuk barisan {X k } secara rekursif menggunakan

Yk = AX k , X k +1 =

1 c k +1

(2)

Yk ,

(3)

dan c k +1 adalah koordinat terbesar dari Yk . Bila terdapat lebih dari satu, pilih koordinat dengan urutan terkecil. Barisan {X k } dan {c k }akan konvergen berturut-turut ke

V dan λ :

lim X k = V dan lim c k = λ . k →∞

(4)

k →∞

Contoh Gunakan metode pangkat untuk memperoleh nilai eigen dan vektor eigen yang dominan untuk matriks bujur sangkar ⎡ 0 11 − 5 A = ⎢⎢− 2 17 − 7 ⎢⎣− 4 26 − 10

Solusi

⎤ ⎥ ⎥ ⎥⎦

Dimulai dengan X 0 = (1,1,1) dan gunakan formula pada persamaan (2) untuk membentuk T

barisan vektor {X k }dan konstanta {c k } . Iterasi pertama menghasilkan ⎡ 0 11 − 5 ⎢− 2 17 − 7 ⎢ ⎢⎣− 4 26 − 10

⎤ ⎡1⎤ ⎡ 6 ⎤ ⎡1 / 2 ⎤ ⎥ ⎢1⎥ = ⎢ 8 ⎥ = 12 ⎢2 / 3⎥ = c X . ⎥⎢ ⎥ ⎢ ⎥ ⎢ ⎥ 1 1 ⎥⎦ ⎢⎣1⎥⎦ ⎢⎣ 12⎥⎦ ⎢⎣ 1 ⎥⎦

Iterasi kedua menghasilkan ⎡ 0 11 − 5 ⎢− 2 17 − 7 ⎢ ⎢⎣− 4 26 − 10

⎡7 / 16⎤ ⎤ ⎡1 / 2 ⎤ ⎡ 7 / 3 ⎤ ⎥ ⎢2 / 3⎥ = ⎢ 10 / 3⎥ = 16 ⎢5 / 8 ⎥ = c X . 2 2 ⎥ ⎥ 3 ⎢ ⎥ ⎢ ⎥⎢ ⎢⎣ 1 ⎥⎦ ⎥⎦ ⎢⎣ 1 ⎥⎦ ⎢⎣16 / 3 ⎥⎦

Iterasi menghasilkan barisan {X k } di mana X k vektor ternormalisir. ⎡85 / 212 ⎤ ⎡127 / 316⎤ ⎡21/ 52 ⎤ ⎡31/ 76⎤ ⎡7 / 16⎤ ⎡5 / 12 ⎤ ⎡1 / 2 ⎤ 318 ⎢ 158 ⎢ 78 ⎢ 38 ⎢ 9⎢ 16 ⎢ ⎥ ⎥ ⎥ ⎥ ⎥ ⎥ ⎢ 191/ 318⎥⎥,K 95 / 158 ⎥, 5 / 8 , 11/ 18⎥, ⎢23 / 38⎥, ⎢47 / 78⎥, 12 2 / 3 , ⎥ 2⎢ ⎢ ⎥ 3⎢ 79 ⎢ 39 ⎢ 19 9 ⎥⎦ ⎢⎣ 1 ⎥⎦ ⎢⎣ 1 ⎢⎣ 1 ⎥⎦ ⎢⎣ 1 ⎥⎦ ⎢⎣ 1 ⎥⎦ ⎢⎣ 1 ⎥⎦ ⎢⎣ 1 ⎥⎦

Barisan vektor tersebut konvergen ke V = (2 / 3, 3 / 5,1) , dan barisan konstanta konvergen ke λ = 4 (lihat Tabel 1). Dapat diperlihatkan bahwa laju konvergensi adalah linear. T

76

Jurnal Mat Stat, Vol. 9 No. 1 Januari 2009: 75-82

Penelitian Relevan Beberapa penelitian yang telah dilakukan untuk topik tersebut, antara lain berjudul “Controllability of the Real Shifted Inverse Power Iteration” oleh Uwe Helmke, Fabian Wirth (2000).

TEOREMA METODE PANGKAT Andaikan bahwa matriks A bertipe n x n mempunyai n nilai eigen λ1 , λ2 , K, λn yang berlainan yang diurutkan menurun dalam nilai mutlaknya, yaitu:

λ1 > λ 2 ≥ λ 3 ≥ L ≥ λ n .

(5)

Bila X 0 dipilih yang sesuai maka barisan

{X

k

(

= x1( k ) , x 2( k ) , K , x n( k )

) } dan {c } yang dibentuk secara rekursif dengan T

k

Yk = AX k , 1

dan

X k +1 =

dan

ck +1 = y (jk )

c k +1

(6)

Yk ,

(7)

(k )

dan y j

{ }

= max y i( k ) 1≤ i ≤ n

(8)

akan konvergen berturut-turut ke vektor eigen dominan V1 dan nilai eigen λ1 . , yaitu (Bartle, Robert G. and Sherbert, Donald R. 2000)

lim X k = V1 dan lim c k = λ1 . k →∞

(9)

k →∞

METODE PANGKAT BALIK TERGESER Metode itu memerlukan pendekatan awal yang baik untuk mendapatkan nilai eigen dan kemudian dengan iterasi digunakan untuk mendapatkan solusi eksak. Metode lain, misalnya metode QL dan metode Given dipakai untuk mencari pendekatan awal. Metode pangkat balik tergeser berdasarkan tiga hasil berikut. Teorema 1 (Nilai eigen yang digeser) Misalkan λ dan V adalah pasangan nilai eigen dan vektor eigen matriks bujur sangkar A. Bila α konstanta sembarang maka λ − α , V merupakan pasangan nilai eigen dan vektor eigen matriks bujur sangkar A − α I . Teorema 2 (Nilai eigen balik) Misalkan λ dan V adalah pasangan nilai eigen dan vektor eigen matriks bujur sangkar A. Bila λ ≠ 0, maka 1 / λ , V merupakan pasangan nilai eigen dan vektor eigen matriks bujur sangkar A −1 .

Metode Pangkat Balik Tergeser … (Sangadji)

77

Teorema 3 Misalkan λ dan V adalah pasangan nilai eigen dan vektor eigen matriks bujur sangkar A. Bila α ≠ λ , maka 1 /(λ − α ), V merupakan pasangan nilai eigen dan vektor eigen matriks bujur sangkar ( A − α I ) −1 . ( Kreyszig, 1999)

TEOREMA METODE PANGKAT BALIK TERGESER Andaikan bahwa matriks A bertipe n x n punya nilai eigen yang berlainan

λ1 , λ 2 ,K, λn dan pandang nilai eigen λ j . maka konstanta α dapat dipilih sedemikian sehingga μ1 = 1 /(λ j − α ) merupakan nilai eigen dominan matriks ( A − α I ) −1 . Lebih jauh, bila X 0 dipilih

{

(

yang sesuai maka barisan X k = x1( k ) , x 2( k ) , K , x n( k )

) } dan {c }yang dibentuk secara rekursif dengan T

k

Yk = ( A − α I ) X k −1

1

(10)

dan

X k +1 =

dan

ck +1 = x (jk ) dan x (jk ) = max xi( k )

c k +1

Yk

(11)

1≤ i ≤ n

{ }

(12)

akan konvergen ke pasangan μ1 , V j dominan matriks ( A − α I ) . Akhirnya, nilai eigen yang sesuai −1

untuk matriks A diberikan dengan perhitungan

λj =

1

μ1

+ α.

(13)

Bukti Tanpa mengurangi atau kehilangan keumuman, diasumsikan bahwa λ1 < λ 2 < L < λ n . Pilih

satu bilangan α (α ≠ λ ) yang lebih dekat ke λ j daripada nilai eigen yang lain, yaitu

λ j − α < λi − α untuk setiap i = 1, 2, K , j − 1, j + 1, K , n.

(

(14)

)

Menurut Teorema 3, 1 / λ j − α , V j adalah pasangan nilai eigen dan vektor eigen matriks

(A − α I)

−1

. Persamaan (5) berakibat 1 / λi − α < λ j − α

untuk

setiap

i≠ j

sehingga

μ1 = 1 / (λ j − α ) adalah nilai eigen dominan matriks ( A − α I )−1 . Metode pangkat balik tergeser

menggunakan modifikasi metode pangkat untuk menentukan pasangan nilai eigen dan vektor eigen μ1 , V j . Kemudian perhitungan λ j = (1 / μ1 ) + α menghasilkan nilai eigen dari matriks A yang diinginkan (Fitzpatrick, Patrick. M. 1996).

78

Jurnal Mat Stat, Vol. 9 No. 1 Januari 2009: 75-82

Contoh Gunakan metode pangkat balik tergeser untuk mendapatkan pasangan nilai eigen dan vektor eigen matriks ⎡ 0 A = ⎢⎢ − 2 ⎢⎣ − 4

11 17 26

−5 −7 − 10

⎤ ⎥. ⎥ ⎥⎦

Manfaatkan fakta bahwa nilai eigen A adalah λ1 = 4, λ2 = 2, dan λ3 = 1 dan pilih satu α yang sesuai dan vektor awal untuk setiap kasus.

Solusi Kasus 1:

Untuk nilai eigen λ1 = 4, ambil α = 4.2 dan vektor awal X 0 = (1,1,1) . Pertama, bentuk matriks T

A − 4.2 I , komputasikan solusi untuk ⎡ − 4.2 ⎢ −2 ⎢ ⎣⎢ − 4

−5 −7 − 14.2

11 12.8 26

⎡1⎤ ⎤ ⎥ Y = X = ⎢1⎥. 0 ⎢⎥ ⎥ 0 ⎢⎣1⎥⎦ ⎦⎥

dan dapatkan vektor Y0 = (− 9.545454545,−14.09090909,−23.18181818) . Kemudian komputasikan T

c1 = −23.18181818 dan X 1 = (0.4117647059 , 0.6078431373 ,1)T . Iterasi menghasilkan nilai pada Tabel 1. Barisan {c k } konvergen ke μ1 = −5 yang merupakan nilai eigen dominan matriks ( A − 4.2 I ) −1 , dan

{X k }

konvergen ke V = ⎛⎜ 2 , 3 ,1⎞⎟ . Nilai eigen λ1 dari A diberikn dengan 1 T

⎝5 5 ⎠

komputasi

λ1 = 1 / μ1 + α = 1 /(−5) + 4.2 = −0.2 + 4.2 = 4. Tabel 1 (diambil dari Numerical Methods for Mathematics, Science, and Engineering, hlm. 556. Second Edition. Prentice-Hall International, Inc. Englewood Cliffs, New Jersey. Mathews, John H. 1992) Metode pangkat balik tergeser untuk matriks ( A − 4.2 I ) −1 dalam contoh tersebut. Konvergensi ke T

vektor V1 = ⎛⎜ 2 , 3 ,1⎞⎟ dan μ1 = −5 . ⎝5 5 ⎠

(A−α I)−1 Xk =

ck+1 Xk+1

( A − α I ) −1 X 0 = −23.18181818(0.4117647059,0.6078431373,1)

= c1 X1

T

( A − α I ) −1 X 1 =

− 5.356506239 (0.4009983361,0.6006655574 ,1) = c 2 X 2 T

( A − α I ) −1 X 2 = −5.030252609(0.4000902120, 0.6000601413,1) = c3 X 3 T

( A − α I ) −1 X 3 = −5.002733697(0.4000081966,0.6000054644,1) = c 4 X 4 T

( A − α I ) −1 X 4 = −5.000248382(0.400007451,0.600004967,1) = c5 X 5 T

Metode Pangkat Balik Tergeser … (Sangadji)

79

( A − α I ) −1 X 5 = −5.000022579(0.000000677,0.600000452,1) = c6 X 6 T

( A − α I ) −1 X 6 = − 5.000002053(0.400000062,0.600000041,1) = c7 X 7 T

( A − α I ) −1 X 7 = −5.000000187(0.400000006,0.600000004,1) = c8 X 8 T

( A − α I ) −1 X 8 = −5.00000017(0.400000001,0.600000000,1) = c9 X 9 T

Kasus 2:

Untuk nilai eigen λ2 = 2, ambil α = 2.1 dan vektor awal X 0 = (1,1,1) . Pertama, bentuk matriks T

A − 2.1 I , komputasikan solusi untuk ⎡ ⎢ ⎢ ⎢⎣

− 2 .1 −2 −4

11 14 .9 26

−5 −7 − 12 .1

⎤ ⎡1⎤ ⎥ Y = X = ⎢1⎥ . 0 ⎥ 0 ⎢ ⎥ ⎥⎦ ⎢⎣1⎥⎦

dan dapatkan vektor Y0 = (11.05263158, 21.57894737, 42.63157895) . Kemudian komputasikan T

c1 = 42.63157895 dan X1 = (0.2592592593, 0.5061728395,1)T . Iterasi menghasilkan nilai pada Tabel 2. Nilai eigen dari ( A − 2.1 I ) −1 dominan adalah μ1 = −10 dan pasangan nilai eigen dan T

vektor eigen dari A adalah λ2 =

1 ⎛1 1 ⎞ + 2.1 = −0.1 + 2.1 = 2 dan V2 = ⎜ , ,1⎟ . − 10 ⎝4 2 ⎠

Tabel 2 (diambil dari Numerical Methods for Mathematics, Science, and Engineering, hlm. 557. Second Edition. Prentice-Hall International, Inc. Englewood Cliffs, New Jersey. Mathews, John H. 1992 ) Metode pangkat balik tergeser untuk matriks ( A − 2.1 I ) −1 dalam contoh tersebut. Konvergensi ke

⎛1 1 ⎞ ⎝4 2 ⎠

T

eigen vektor dominan V = ⎜ , ,1⎟ dan μ1 = −10. .

( A − α I ) −1 X k =

c k +1 X k +1

( A − α I ) −1 X 0 = 42.63157895(0.2592592593,0.5061728395,1) . = c1 X1 T

( A − α I ) −1 X1 = − 9.350227420 (0.2494788047 ,0.4996525365,1) = c 2 X 2 T

( A − α I ) −1 X 2 = −10.03657511(0.2500273314,0.5000182209,1) = c3 X 3 T

( A − α I ) −1 X 3 = −9.998082009(0.2499985612,0.49990408,1) = c 4 X 4 T

( A − α I ) −1 X 4 = −10.00010097 (0.2500000757 ,0.5999990505,1) = c 4 X 4 T

( A − α I ) −1 X 5 = −9.9999994686(0.2499999960,0.4999999973,1) = c6 X 6 T

( A − α I ) −1 X 6 = − 10.000000028(0.2500000002,0.5000000001,1) = c7 X 7 T

80

Jurnal Mat Stat, Vol. 9 No. 1 Januari 2009: 75-82

Kasus 3:

Untuk nilai eigen λ3 = 1, ambil α = 0.875 dan vektor awal X 0 = (0,1,1) . Iterasi menghasilkan nilai T

yang diberikan pada Tabel 3. Nilai eigen dari matriks ( A + 0.875 I ) −1 yang dominan adalah

μ1 = −10

dan

pasangan

nilai

eigen

dan

vektor

eigen

dari

matriks

A

adalah

T

1 ⎛1 1 ⎞ + 0.875 = 0.125 + 0.875 = 1 dan V3 = ⎜ , ,1⎟ . Barisan {X k } vektor dengan vektor 8 ⎝2 2 ⎠ T awal (0,1,1) konvergen dalam tujuh iterasi.

λ3 =

Tabel 3 (diambil dari Numerical Methods for Mathematics, Science, and Engineering, hlm. 557. Second Edition. Prentice-Hall International, Inc. Englewood Cliffs, New Jersey. Mathews, John H. 1992).

Metode pangkat balik tergeser untuk matriks ( A + 0.875 I ) −1 dalam Contoh. Konvergensi ke vektor T

⎛1 1 ⎞ eigen dominan V = ⎜ , ,1⎟ dan nilai eigen μ1 = 8 . ⎝2 2 ⎠ ( A − α I ) −1 X k =

c k +1 X k +1

( A − α I ) −1 X 0 = −30.4000000000 (0.5052631579, 0.4947368421,1) . = c1 X1 T

( A − α I ) −1 X1 = 8.404210526 (0.5002004008,0.4997995992 ,1) = c 2 X 2 T

( A − α I ) −1 X 2 = 8.015390782(0.500000006,0.49999199904,1) = c3 X 3 T

( A − α I ) −1 X 3 = 8.000614449(0.5000003200, 0.4999996800,1) = c 4 X 4 T

( A − α I ) −1 X 4 = 8.000024576 (0.5000000128 ,0.4999999872 ,1) = c 4 X 4 T

( A − α I ) −1 X 5 = 8.000000983(0.500000005,0.4999999995,1) = c6 X 6 T

( A − α I ) −1 X 6 = 8.000000039(0.0.5000000000,0.5000000000,1) = c7 X 7 T

Yk = AX k ,

PENUTUP Metode pangkat balik tergeser merupakan perluasan dari metode pangkat yang menyatakan bila matriks bujur sangkar A mempunyai nilai eigen dominan λ dan misalkan terdapat tepat satu vektor eigen ternormalisir V yang bersesuaian dengan λ . Pasangan λ , V itu dapat diperoleh dengan prosedur iteratif berikut yang disebut metode pangkat. Dimulai dengan vektor

X 0 = (1,1,K,1) . T

Bentuk barisan {X k } secara rekursif menggunakan

Yk = AX k

dan

X k +1 =

1 c k +1

Yk ,

Metode Pangkat Balik Tergeser … (Sangadji)

81

dan c k +1 adalah koordinat terbesar dari Yk . Bila terdapat lebih dari satu, pilih koordinat dengan urutan terkecil. Barisan {X k } dan {c k }akan konvergen berturut-turut ke V dan

λ..

Metode pangkat balik tergeser menyatakan bila matriks A bertipe n x n punya nilai eigen yang berlainan λ1 , λ 2 , K , λn . Maka konstanta α dapat dipilih sedemikian sehingga μ1 = 1 /(λ j − α ) merupakan nilai eigen dominan matriks ( A − α I ) −1 . Lebih jauh, bila X 0 dipilih yang sesuai maka barisan X k = x1( k ) , x 2( k ) , K , x n( k )

{

) } dan {c }yang dibentuk secara rekursif dengan

Yk = ( A − α I ) X k

X k +1 =

(

−1

dan

T

k

1 c k +1

{ } akan

Yk dan c k +1 = x (jk ) dan x (jk ) = max x (jk ) 1≤ j ≤ n

konvergen ke pasangan μ1 , V j dominan matriks ( A − α I ) . Nilai eigen yang sesuai untuk matriks A −1

diberikan dengan perhitungan λ j =

1

μ1

+ α.

DAFTAR PUSTAKA Bartle, R.G. & Sherbert, D. R. (2000). Introduction to real analysis. Third Edition. John Wiley & Sons, Inc. Fitzpatrick, P. M. (1996). Advanced calculus. Boston: PWS Publishing Company. Kreyszig, E. (1999). Advanced engineering mathematics. Eight Edition. New York: John Wiley and Sons Inc. Mathews, J. H. (1992). Numerical methods for mathematics, science, and engineering. Second Edition. Englewood Cliffs, New Jersey: Prentice-Hall International, Inc.

82

Jurnal Mat Stat, Vol. 9 No. 1 Januari 2009: 75-82