Biasanya kita mencari nilai-nilai eigen matriks persegi \(A\) sebagai akar-akar polinom karakteristik \(\det(A-\lambda I) = 0\) dan vektor-vektor eigen terkait sebagai ruang nol \(\nul(A-\lambda I)\text{.}\) Sayangnya, pendekatan ini tidak praktis ketika kita bekerja dengan matriks besar. Pertama, mencari polinom karakteristik matriks besar memerlukan komputasi yang cukup banyak, demikian pula mencari akar-akar polinom tersebut. Kedua, pencarian ruang nol matriks singular menghadapi masalah numerik, seperti yang akan kita lihat dalam aktivitas pendahuluan.
Oleh karena itu, kita akan menelaah suatu teknik yang disebut metode pangkat untuk mencari hampiran numerik bagi nilai-nilai eigen dan vektor-vektor eigen suatu matriks persegi.
Misalkan \(A = \left[\begin{array}{rr}
0.8 \amp 0.4 \\
0.2 \amp 0.6 \\
\end{array}\right]
\text{.}\) Jelaskan bagaimana kita mengetahui bahwa \(1\) merupakan nilai eigen \(A\text{,}\) kemudian jelaskan mengapa komputasi Sage berikut tidak benar.
Misalkan \(\xvec_0 = \twovec{1}{0}\) dan kita mendefinisikan barisan \(\xvec_{k+1} = A\xvec_k\text{;}\) dengan kata lain, \(\xvec_{k} = A^k\xvec_0\text{.}\) Apa yang terjadi pada \(\xvec_k\) ketika \(k\) makin besar?
Tujuan kita adalah mencari suatu teknik yang menghasilkan hampiran numerik bagi nilai-nilai eigen dan vektor-vektor eigen terkait suatu matriks \(A\text{.}\) Kita mulai dengan mencari nilai eigen yang memiliki nilai absolut terbesar, yang disebut nilai eigen dominan. Dua contoh berikut memperagakan teknik ini.
Mari kita mulai dengan matriks stokastik positif \(A=\left[\begin{array}{rr}
0.7 \amp 0.6 \\
0.3 \amp 0.4 \\
\end{array}\right]
\text{.}\) Kita telah cukup banyak mempelajari jenis matriks ini dalam Subbab 4.5; secara khusus, kita melihat bahwa setiap rantai Markov akan konvergen menuju vektor keadaan tunak yang unik. Mari kita nyatakan kembali pernyataan ini menggunakan vektor-vektor eigen \(A\text{.}\)
Matriks ini memiliki nilai-nilai eigen \(\lambda_1 = 1\) dan \(\lambda_2 =0.1\text{,}\) sehingga nilai eigen dominannya adalah \(\lambda_1 = 1\text{.}\) Vektor-vektor eigen terkait adalah \(\vvec_1 = \twovec{2}{1}\) dan \(\vvec_2 = \twovec{-1}{1}\text{.}\) Misalkan kita mulai dengan vektor
dan seterusnya. Perhatikan bahwa pangkat \(0.1^k\) menjadi makin kecil ketika \(k\) membesar, sehingga \(\xvec_k\approx
\frac13\vvec_1\) ketika \(k\) besar. Dengan demikian, vektor-vektor \(\xvec_k\) makin mendekati suatu vektor dalam ruang eigen \(E_1\text{,}\) yaitu ruang eigen yang terkait dengan nilai eigen dominan. Jika kita tidak mengetahui vektor eigen \(\vvec_1\text{,}\) kita dapat menggunakan rantai Markov dengan cara ini untuk mencari suatu vektor basis bagi \(E_1\text{;}\) seperti yang dilihat dalam Subbab 4.5, pada dasarnya beginilah cara kerja algoritma PageRank Google.
Sekarang, mari kita perhatikan matriks \(A = \left[\begin{array}{rr}
2 \amp 1 \\ 1 \amp 2 \\ \end{array}\right] \text{,}\) yang memiliki yang memiliki nilai-nilai eigen \(\lambda_1=3\) dan \(\lambda_2 = 1\text{.}\) Nilai eigen dominannya adalah \(\lambda_1=3\text{,}\) sedangkan vektor-vektor eigen terkait adalah \(\vvec_1 = \twovec{1}{1}\) dan \(\vvec_{2} = \twovec{-1}{1}\text{.}\) Sekali lagi, mulailah dengan vektor \(\xvec_0 = \twovec{1}{0}=\frac12 \vvec_1 -
\frac12 \vvec_2\text{,}\) sehingga
Seperti yang ditunjukkan gambar, vektor-vektor \(\xvec_k\) diregangkan dengan faktor \(3\) pada arah \(\vvec_1\) dan tidak diregangkan sama sekali pada arah \(\vvec_2\text{.}\) Akibatnya, vektor-vektor \(\xvec_k\) menjadi makin panjang, tetapi arahnya makin mendekati arah vektor eigen \(\vvec_1=\twovec{1}{1}\) yang terkait dengan nilai eigen dominan.
Terdapat kisi koordinat baku \(1\times1\) beserta sepasang sumbu koordinat. Jendela tampilan membentang secara horizontal dan vertikal dari \(-1\) hingga \(8\text{.}\) Ditampilkan vektor \(\xvec_0=\twovec10\text{,}\)\(\xvec_1=\twovec21\text{,}\)\(\xvec_2=\twovec54\text{,}\) dan \(\xvec_3=\twovec{14}{13}\text{.}\) Vektor terakhir \(\xvec_3\) hampir searah dengan vektor eigen \(\vvec_1=\twovec11\) dan memanjang keluar dari sisi kanan diagram, yang menunjukkan bahwa panjangnya besar.
Untuk mencari vektor eigen yang terkait dengan nilai eigen dominan, kita mencegah panjang vektor-vektor \(\xvec_k\) bertambah tanpa batas dengan mengalikannya dengan konstanta penskalaan yang sesuai. Berikut salah satu caranya. Untuk vektor \(\xvec_k\text{,}\) kita tentukan komponen yang memiliki nilai absolut terbesar dan menyebutnya \(m_k\text{.}\) Selanjutnya, kita definisikan \(\overline{\xvec}_k = \frac{1}{m_k} \xvec_k\text{,}\) sehingga komponen \(\overline{\xvec}_k\) yang memiliki nilai absolut terbesar adalah \(1\text{.}\)
Sebagai contoh, jika kita mulai dengan \(\xvec_0 = \twovec{1}{0}\text{,}\) kita memperoleh \(\xvec_1 = A\xvec_{0} =
\twovec{2}{1}\text{.}\) Komponen \(\xvec_1\) yang memiliki nilai absolut terbesar adalah \(m_1=2\text{,}\) sehingga kita mengalikannya dengan \(\frac{1}{m_1} = \frac12\) untuk memperoleh \(\overline{\xvec}_1 = \twovec{1}{\frac12}\text{.}\) Selanjutnya, \(\xvec_2 = A\overline{\xvec}_1 =
\twovec{\frac52}{2}\text{.}\) Sekarang komponen dengan nilai absolut terbesar adalah \(m_2=\frac52\text{,}\) sehingga kita mengalikannya dengan \(\frac25\) untuk memperoleh \(\overline{\xvec}_2 = \twovec{1}{\frac45}\text{.}\)
Barisan vektor \(\overline{\xvec}_k\) yang dihasilkan ditampilkan pada gambar. Perhatikan bagaimana vektor-vektor \(\overline{\xvec}_k\) kini mendekati vektor eigen \(\vvec_1\text{,}\) yang memberi kita cara untuk mencari vektor eigen \(\vvec=\twovec{1}{1}\text{.}\) Inilah metode pangkat untuk mencari vektor eigen yang terkait dengan nilai eigen dominan suatu matriks.
Terdapat kisi koordinat dan sepasang sumbu koordinat, beserta persegi yang titik-titik sudutnya adalah \((1,1)\text{,}\)\((-1,1)\text{,}\)\((-1,-1)\text{,}\) dan \((1,-1)\text{.}\) Vektor \(\xvec_0=\twovec10\) ditampilkan dengan ujungnya terletak pada persegi. Selanjutnya, \(\overline{\xvec}_1=\twovec{1}{1/2}\) dan \(\overline{\xvec}_2=\twovec{1}{4/5}\) ditampilkan dengan ujung masing-masing pada persegi. Vektor \(\overline{\xvec}_3\) juga ditampilkan untuk menunjukkan bahwa vektor-vektor ini mendekati vektor eigen \(\vvec_1=\twovec11\text{.}\)
Mari kita mulai dengan memperhatikan matriks \(A = \left[\begin{array}{rr}
0.5 \amp 0.2 \\
0.4 \amp 0.7 \\
\end{array}\right]\) dan vektor awal \(\xvec_0 = \twovec{1}{0}\text{.}\)
Tentukan \(m_1\text{,}\) yaitu komponen \(\xvec_1\) yang memiliki nilai absolut terbesar. Kemudian bentuk \(\overline{\xvec}_1 = \frac 1{m_1} \xvec_1\text{.}\) Perhatikan bahwa komponen \(\overline{\xvec}_1\) yang memiliki nilai absolut terbesar adalah \(1\text{.}\)
Tentukan vektor \(\xvec_2 = A\overline{\xvec}_1\text{.}\) Tentukan komponen \(m_2\) dari \(\xvec_2\) yang memiliki nilai absolut terbesar. Kemudian bentuk \(\overline{\xvec}_2 = \frac1{m_2}\xvec_2\) untuk memperoleh vektor yang komponen dengan nilai absolut terbesarnya adalah \(1\text{.}\)
Sel Sage berikut mendefinisikan fungsi yang menerapkan metode pangkat. Definisikan matriks \(A\) dan vektor awal \(\xvec_0\) di bawah ini. Perintah power(A, x0, N) akan mencetak pengali \(m\) dan vektor-vektor \(\overline{\xvec}_k\) untuk \(N\) langkah metode pangkat.
Sekarang perhatikan matriks \(A=\left[\begin{array}{rr}
-5.1 \amp 5.7 \\
-3.8 \amp 4.4 \\
\end{array}\right]
\text{.}\) Gunakan metode pangkat untuk mencari nilai eigen dominan \(A\) dan suatu vektor eigen terkait.
Perhatikan bahwa metode pangkat tidak hanya memberi kita vektor eigen \(\vvec\text{,}\) tetapi juga nilai eigen terkait. Seperti dalam aktivitas tersebut, perhatikan matriks \(A=\left[\begin{array}{rr}
-5.1 \amp 5.7 \\
-3.8 \amp 4.4 \\
\end{array}\right]
\text{,}\) yang memiliki vektor eigen \(\vvec=\twovec{3}{2}\text{.}\) Komponen pertama memiliki nilai absolut terbesar, sehingga kita mengalikan vektor itu dengan \(\frac13\) untuk memperoleh \(\overline{\vvec}=\twovec{1}{\frac23}\text{.}\) Ketika kita mengalikannya dengan \(A\text{,}\) kita memperoleh \(A\overline{\vvec} = \twovec{-1.30}{-0.86}\text{.}\) Perhatikan bahwa komponen pertama masih memiliki nilai absolut terbesar, sehingga pengali \(m=-1.3\) merupakan nilai eigen \(\lambda\) yang terkait dengan vektor eigen tersebut. Ini memperagakan fakta bahwa pengali-pengali \(m_k\) mendekati nilai eigen \(\lambda\) yang memiliki nilai absolut terbesar.
Perhatikan bahwa metode pangkat mengharuskan kita memilih vektor awal \(\xvec_0\text{.}\) Untuk sebagian besar pilihan, metode ini akan menemukan nilai eigen yang memiliki nilai absolut terbesar. Namun, pilihan \(\xvec_0\) yang kurang menguntungkan mungkin gagal menemukannya. Misalnya, jika pada contoh di atas kita memilih \(\xvec_0 = \vvec_2\text{,}\) vektor-vektor dalam barisan \(\xvec_k = A^k\xvec_0=\lambda_2^k\vvec_2\) tidak akan mendeteksi vektor eigen \(\vvec_1\text{.}\) Meskipun demikian, biasanya tebakan awal \(\xvec_0\) memiliki suatu kontribusi dari \(\vvec_1\) yang memungkinkan kita menemukannya.
Metode pangkat sebagaimana disajikan di sini akan gagal untuk matriks-matriks tertentu yang kurang menguntungkan. Hal ini ditelaah dalam Latihan 5.2.5.5, bersama dengan suatu cara untuk menyempurnakan metode pangkat agar dapat digunakan pada semua matriks.
Metode pangkat memberikan teknik untuk mencari nilai eigen dominan suatu matriks. Kita dapat memodifikasi metode ini agar juga dapat mencari nilai-nilai eigen lainnya.
Kunci untuk mencari nilai eigen \(A\) yang memiliki nilai absolut terkecil adalah mengamati bahwa vektor-vektor eigen \(A\) sama dengan vektor-vektor eigen \(A^{-1}\text{.}\)
Jika \(\vvec\) merupakan vektor eigen \(A\) dengan nilai eigen terkait \(\lambda\text{,}\) jelaskan mengapa \(\vvec\) merupakan vektor eigen \(A^{-1}\) dengan nilai eigen terkait \(\lambda^{-1}\text{.}\)
Jika kita menerapkan metode pangkat pada \(A^{-1}\text{,}\) kita mulai dengan suatu vektor awal \(\xvec_0\) dan menghasilkan barisan \(\xvec_{k+1} = A^{-1}\xvec_k\text{.}\) Namun, menghitung \(A^{-1}\) tidak efisien secara komputasi, sehingga sebagai gantinya kita menyelesaikan persamaan \(A\xvec_{k+1} = \xvec_k\text{.}\) Jelaskan mengapa faktorisasi \(LU\) dari \(A\) berguna untuk menerapkan metode pangkat pada \(A^{-1}\text{.}\)
Sel Sage berikut mendefinisikan perintah inverse_power yang menerapkan metode pangkat pada \(A^{-1}\text{.}\) Artinya, inverse_power(A, x0, N) mencetak vektor-vektor \(\xvec_k\text{,}\) dengan \(\xvec_{k+1} = A^{-1}\xvec_k\text{,}\) serta pengali-pengali \(\frac{1}{m_k}\) yang menghampiri nilai eigen \(A\text{.}\) Gunakan perintah tersebut untuk mencari nilai eigen dari \(A=\left[\begin{array}{rr}
-5.1 \amp 5.7 \\
-3.8 \amp 4.4 \\
\end{array}\right]\) yang memiliki nilai absolut terkecil.
Metode pangkat invers hanya dapat digunakan jika \(A\) invertibel. Jika \(A\) tidak invertibel, berapakah nilai eigennya yang memiliki nilai absolut terkecil?
Gunakan metode pangkat dan metode pangkat invers untuk mencari nilai-nilai eigen dan vektor-vektor eigen terkait dari matriks \(A = \left[\begin{array}{rr}
-0.23 \amp -2.33 \\
-1.16 \amp 1.08 \\
\end{array}\right]
\text{.}\)
Dengan metode pangkat dan metode pangkat invers, kini kita dapat mencari nilai-nilai eigen matriks \(A\) yang memiliki nilai absolut terbesar dan terkecil. Dengan satu modifikasi lagi, kita dapat mencari semua nilai eigen \(A\text{.}\)
Ingatlah bahwa nilai absolut suatu bilangan menunjukkan jarak bilangan tersebut dari \(0\) pada garis bilangan real. Oleh karena itu, kita dapat memandang metode pangkat invers sebagai metode yang menunjukkan nilai eigen terdekat dengan \(0\text{.}\)
Jika \(\vvec\) merupakan vektor eigen \(A\) dengan nilai eigen terkait \(\lambda\text{,}\) jelaskan mengapa \(\vvec\) merupakan vektor eigen \(A - sI\text{,}\) dengan \(s\) suatu skalar.
Perhatikan matriks \(A = \left[\begin{array}{rrrr}
3.6 \amp 1.6 \amp 4.0 \amp 7.6 \\
1.6 \amp 2.2 \amp 4.4 \amp 4.1 \\
3.9 \amp 4.3 \amp 9.0 \amp 0.6 \\
7.6 \amp 4.1 \amp 0.6 \amp 5.0 \\
\end{array}\right]
\text{.}\) Jika kita menggunakan metode pangkat dan metode pangkat invers, kita memperoleh dua nilai eigen, \(\lambda_1=16.35\) dan \(\lambda_2=0.75\text{.}\) Dengan melihat nilai-nilai eigen ini pada garis bilangan, kita mengetahui bahwa nilai-nilai eigen lainnya berada dalam rentang antara \(-\lambda_1\) dan \(\lambda_1\text{,}\) sebagaimana diarsir pada Gambar 5.2.3.
Garis bilangan horizontal yang menyatakan nilai dari \(-20\) hingga \(20\text{.}\) Garis-garis vertikal digambar pada nilai \(\lambda_1=16.35\) dan \(\lambda_2=0.75\text{.}\) Daerah di antara kedua garis vertikal ini diarsir untuk menunjukkan bahwa nilai-nilai eigen lainnya mungkin berada di dalamnya. Daerah dari \(-\lambda_1=-16.35\) hingga \(-\lambda_2=-0.75\) juga diarsir untuk menunjukkan bahwa nilai-nilai eigen mungkin berada di daerah ini.
Sel Sage berikut memuat fungsi find_closest_eigenvalue(A, s, x, N) yang menerapkan \(N\) langkah metode pangkat invers dengan menggunakan matriks \(A-sI\) dan vektor awal \(x\text{.}\) Fungsi ini mencetak hampiran nilai eigen \(A\) yang terdekat dengan \(s\) beserta vektor eigen terkait. Dengan mencoba berbagai nilai \(s\) di dalam daerah-daerah yang diarsir pada garis bilangan dalam Gambar 5.2.3, carilah dua nilai eigen lainnya dari \(A\text{.}\)
Terdapat beberapa pembatasan pada matriks yang dapat dikenai teknik ini karena kita telah mengasumsikan bahwa nilai-nilai eigen \(A\) real dan berbeda. Jika \(A\) memiliki nilai eigen berulang atau kompleks, teknik ini perlu dimodifikasi, seperti yang ditelaah dalam beberapa latihan.
Kita telah menelaah metode pangkat sebagai alat untuk menghampiri nilai-nilai eigen dan vektor-vektor eigen suatu matriks secara numerik.
Setelah memilih vektor awal \(\xvec_0\text{,}\) kita mendefinisikan barisan \(\xvec_{k+1}=A\xvec_k\text{.}\) Ketika \(k\) membesar, arah vektor-vektor \(\xvec_k\) menghampiri dengan saksama arah ruang eigen yang bersesuaian dengan nilai eigen \(\lambda_1\) yang memiliki nilai absolut terbesar.
Kita menormalisasi vektor-vektor \(\xvec_k\) dengan mengalikannya dengan \(\frac{1}{m_k}\text{,}\) dengan \(m_k\) komponen yang memiliki nilai absolut terbesar. Dengan cara ini, vektor-vektor \(\overline{\xvec}_k\) mendekati suatu vektor eigen yang terkait dengan \(\lambda_1\text{,}\) sedangkan pengali-pengali \(m_k\) mendekati nilai eigen \(\lambda_1\text{.}\)
Untuk mencari nilai eigen yang terdekat dengan suatu bilangan \(s\text{,}\) kita menerapkan metode pangkat dengan menggunakan matriks \((A-sI)^{-1}\text{.}\)
Sel Sage ini memuat perintah power, inverse_power, dan find_closest_eigenvalue yang telah kita kembangkan dalam bagian ini. Setelah sel ini dievaluasi, perintah-perintah tersebut akan tersedia dalam setiap sel lain pada halaman ini.
Gunakan perintah power, inverse_power, dan find_closest_eigenvalue untuk menghampiri nilai-nilai eigen beserta vektor-vektor eigen terkait dari matriks-matriks berikut.
Deskripsikan apa yang terjadi jika kita menerapkan metode pangkat dan metode pangkat invers dengan menggunakan vektor awal \(\xvec_0 = \twovec{1}{0}\text{.}\)
Kita telah melihat bahwa matriks \(A = \left[\begin{array}{rr}
1 \amp 2 \\
2 \amp 1 \\
\end{array}\right]\) memiliki nilai-nilai eigen \(\lambda_1 = 3\) dan \(\lambda_2=-1\text{,}\) serta vektor-vektor eigen terkait \(\vvec_1 = \twovec{1}{1}\) dan \(\vvec_2=\twovec{-1}{1}\text{.}\)
Deskripsikan apa yang terjadi ketika kita menerapkan metode pangkat invers dengan menggunakan vektor awal \(\xvec_0 = \twovec{1}{0}\text{.}\)
Misalkan \(A\) merupakan matriks \(2\times2\) dengan nilai-nilai eigen \(4\) dan \(-3\text{,}\) sedangkan \(B\) merupakan matriks \(2\times2\) dengan nilai-nilai eigen \(4\) dan \(1\text{.}\) Jika kita menerapkan metode pangkat untuk mencari nilai eigen dominan kedua matriks ini sampai tingkat ketelitian yang sama, matriks manakah yang memerlukan lebih banyak langkah dalam algoritma? Jelaskan jawaban Anda.
Misalkan kita menerapkan metode pangkat pada matriks \(A\) dengan vektor awal \(\xvec_0\) dan memperoleh nilai eigen \(\lambda=3\) beserta vektor eigen \(\vvec\text{.}\) Misalkan kemudian kita menerapkan metode pangkat sekali lagi dengan vektor awal yang berbeda dan memperoleh nilai eigen yang sama, \(\lambda=3\text{,}\) tetapi dengan vektor eigen berbeda \(\wvec\text{.}\) Apa yang dapat kita simpulkan mengenai matriks \(A\) dalam kasus ini?
Metode pangkat yang telah kita kembangkan hanya dapat digunakan jika matriks memiliki nilai-nilai eigen real. Misalkan \(A\) merupakan matriks \(2\times2\) yang memiliki nilai eigen kompleks \(\lambda = 2+3i\text{.}\) Apa yang akan terjadi jika kita menerapkan metode pangkat pada \(A\text{?}\)
