Perhitungan Nilai Eigen Individu

Metode Iterasi Invers dengan Pergeseran

Metode iterasi invers dengan pergeseran dirancang untuk menghitung nilai eigen spesifik yang mendekati tebakan awal. Algoritma ini menggunakan parameter pergeseran $\mu$ sebagai panduan pencarian menuju nilai eigen tertentu.

Bayangkan kamu mencari stasiun radio di tengah banyak frekuensi. Tanpa pergeseran, kamu mendengar semua stasiun sekaligus (tidak jelas). Dengan pergeseran, kamu mengarahkan dial ke frekuensi tertentu untuk mendapatkan satu stasiun yang jernih.

Algoritma dimulai dengan matriks $A \in \mathbb{R}^{n \times n}$ dan parameter pergeseran $\mu \in \mathbb{R}$ . Vektor awal $w_0 \in \mathbb{R}^n$ dinormalisasi menjadi $\hat{w}_0 := w_0/\|w_0\|$ dan iterasi dimulai dari $k := 0$ .

Dekomposisi LU dan Iterasi

Langkah pertama adalah menghitung dekomposisi LU dari matriks $A - \mu \cdot I$ . Dekomposisi ini dilakukan sekali di awal dan digunakan berulang dalam setiap iterasi untuk efisiensi komputasi.

w_{k+1} := (A - \mu \cdot I)^{-1} \cdot \hat{w}_k

Praktiknya, alih-alih menghitung invers matriks langsung, kita menyelesaikan sistem persamaan linear menggunakan dekomposisi LU

(A - \mu \cdot I) \cdot w_{k+1} = \hat{w}_k

Normalisasi dan Konvergensi

Setelah memperoleh $w_{k+1}$ , lakukan normalisasi untuk mencegah pertumbuhan tak terkendali

\hat{w}_{k+1} := w_{k+1}/\|w_{k+1}\|

Estimasi nilai eigen menggunakan rasio komponen vektor. Untuk indeks $j$ dengan $(\hat{w}_k)_j \neq 0$

\lambda := (w_{k+1})_j / (\hat{w}_k)_j

Iterasi berlanjut hingga memenuhi kriteria konvergensi $|1/\lambda - 1/\lambda_{\text{lama}}| \leq \text{toleransi}$ . Parameter toleransi adalah nilai ambang batas yang menentukan seberapa akurat hasil yang diinginkan, misalnya $10^{-6}$ untuk akurasi enam digit desimal.

Bayangkan seperti mengukur tinggi badan dengan penggaris. Toleransi menentukan seberapa presisi pengukuran yang kamu terima (apakah cukup akurat sampai centimeter, atau perlu sampai milimeter). Semakin kecil nilai toleransi, semakin akurat hasilnya, tetapi memerlukan lebih banyak iterasi.

Hasil akhir memberikan nilai eigen $1/\lambda + \mu$ dan vektor eigen $\hat{w}_k$ .

Metode von Mises untuk Nilai Eigen Dominan

Metode iterasi vektor von Mises menemukan nilai eigen dengan magnitudo terbesar (nilai eigen dominan). Algoritma ini menggunakan proses iterasi sederhana dengan perkalian matriks berulang.

Algoritma dimulai dengan vektor awal $w_0 \in \mathbb{R}^n$ yang dinormalisasi $\hat{w}_0 := w_0/\|w_0\|$ dan iterasi dimulai dari $k := 0$ .

Iterasi dan Konvergensi

Setiap iterasi melakukan dua operasi utama

w_{k+1} := A \cdot \hat{w}_k

\hat{w}_{k+1} := w_{k+1}/\|w_{k+1}\|

Estimasi nilai eigen menggunakan rasio komponen untuk indeks $j$ dengan $(\hat{w}_k)_j \neq 0$

\lambda := (w_{k+1})_j / (\hat{w}_k)_j

Iterasi berlanjut hingga $|\lambda - \lambda_{\text{lama}}| \leq \text{toleransi}$ . Nilai toleransi menentukan tingkat ketelitian yang dibutuhkan, biasanya berkisar antara $10^{-8}$ hingga $10^{-12}$ untuk perhitungan presisi tinggi. Hasil akhir adalah nilai eigen dominan $\lambda$ dan vektor eigen $\hat{w}_k$ .

Metode ini berhasil jika $|\lambda_1| > |\lambda_2|$ dan vektor awal $w_0$ memiliki komponen tidak nol dalam arah vektor eigen dominan. Dengan asumsi tersebut, iterasi konvergen ke nilai eigen dominan $\lambda_1$ dan vektor eigen terkait.

Teknik Mencari Nilai Eigen Terkecil

Untuk matriks yang dapat diinvertibel, terdapat hubungan penting antara nilai eigen matriks dan inversnya. Jika $A \cdot v_n = \lambda_n \cdot v_n$ , maka berlaku

A^{-1} \cdot v_n = \frac{1}{\lambda_n} \cdot v_n

Artinya, nilai eigen terkecil dari $A$ menjadi nilai eigen terbesar dari $A^{-1}$ . Dengan menerapkan iterasi vektor pada $A^{-1}$ , kita memperoleh nilai eigen terkecil dari matriks asli.

Praktiknya, setiap iterasi menyelesaikan sistem linear $A \cdot w_{k+1} = \hat{w}_k$ menggunakan dekomposisi LU, menghindari perhitungan invers eksplisit yang tidak efisien.