Perhitungan Numerik Nilai Eigen

Metode untuk Satu Nilai Eigen atau Spektrum Lengkap

Pasangan eigen dari matriks persegi $A$ memenuhi

Av=\lambda v,\qquad v\ne0

Untuk matriks simbolik berukuran kecil, kita dapat menyelesaikan $\det(A-\lambda I)=0$ . Perangkat lunak numerik biasanya $tidak membentuk polinomial karakteristik$ karena koefisiennya dapat peka terhadap pembulatan. Jika hanya sebagian spektrum matriks besar dan jarang yang dibutuhkan, metode Krylov memakai perkalian matriks dengan vektor tanpa membentuk polinomial tersebut. Algoritma untuk seluruh spektrum matriks padat memakai faktorisasi matriks.

Bagian spektrum yang perlu dihitung dan struktur matriks menentukan algoritma yang sesuai:

Iterasi pangkat memperkirakan satu nilai eigen dengan nilai mutlak terbesar.
Iterasi invers bergeser menargetkan nilai eigen di dekat pergeseran yang dipilih.
Algoritma $\mathrm{QR}$ menghitung spektrum lengkap matriks padat.
Metode Lanczos dan Arnoldi menargetkan sebagian kecil spektrum matriks jarang berukuran besar.

Iterasi Pangkat

Rumus berikut memakai matriks dan iterasi real. Untuk vektor iterasi kompleks, ganti transpos pada hasil bagi Rayleigh dengan transpos konjugat. Jika $z_k=0$ , vektor tidak dapat dinormalkan. Periksa apakah vektor sebelumnya adalah vektor eigen untuk nilai nol.

Pilih vektor awal tak nol $q_0$ lalu normalkan. Ulangi

z_k=Aq_{k-1}

Skalar $\mu_k$ adalah hasil bagi Rayleigh. Untuk matriks yang dapat didiagonalisasi dengan $satu magnitudo dominan$ ,

|\lambda_1|>|\lambda_2|\ge\cdots\ge|\lambda_n|

Jika ketaksamaan di atas berlaku dan vektor awal memiliki komponen tak nol pada arah eigen dominan, $q_k$ akan mendekati arah eigen dominan. Galat asimtotiknya umumnya menyusut sebanding dengan

\left|\frac{\lambda_2}{\lambda_1}\right|^k

Iterasi pangkat dapat gagal dalam dua keadaan. Beberapa nilai eigen dengan magnitudo dominan yang sama dapat mencegah konvergensi ke satu vektor. Koefisien nol pada arah dominan dalam basis eigen mencegah konvergensi ke arah itu. Pada matriks simetris, syarat ini setara dengan vektor awal yang ortogonal terhadap vektor eigen dominan. Pada matriks nonnormal, basis eigen belum tentu ortogonal, sehingga koefisien harus diperiksa dalam basis tersebut.

Berhenti Berdasarkan Residual

Jangan berhenti hanya karena dua perkiraan nilai eigen yang berurutan tampak serupa. Periksa residual pasangan eigen

r_k=Aq_k-\mu_kq_k

Syarat yang memperhitungkan skala adalah

\|r_k\|_2\le \tau\bigl(\|A\|_2+|\mu_k|\bigr)

Pada syarat ini, $\tau$ adalah toleransi yang diminta. Residual kecil memastikan $pasangan hasil hitung hampir memenuhi persamaan eigen$ , tetapi tidak dengan sendirinya menunjukkan nilai eigen terdekat mana yang ditemukan.

Contoh Iterasi Pangkat

Perhatikan

A=\begin{pmatrix}2&1\\1&2\end{pmatrix}

Langkah pertama menghasilkan

z_1=Aq_0=\begin{pmatrix}2\\1\end{pmatrix}

Langkah kedua menghasilkan

q_2=\frac{1}{\sqrt{41}}\begin{pmatrix}5\\4\end{pmatrix}

Vektor $q_k$ dan perkiraan nilai eigen $\mu_k$ mendekati

q_*=\frac{1}{\sqrt2}\begin{pmatrix}1\\1\end{pmatrix},\qquad \lambda_*=3

Nilai eigen lainnya adalah $1$ , sehingga $faktor konvergensi$ yang diharapkan adalah $|1/3|$ per iterasi setelah memasuki keadaan asimtotik.

Iterasi	Estimasi Rayleigh	Norma residual
1	$14/5$	$3/5$
2	$122/41$	$9/41$

Iterasi Invers

Pilih pergeseran yang $bukan nilai eigen$ . Konvergensi ke satu arah eigen memerlukan satu nilai eigen yang paling dekat secara unik dan koefisien awal tak nol pada arah basis eigennya. Jarak yang sama dapat mencegah konvergensi ke satu arah. Bergeser

Iterasi pangkat mengutamakan magnitudo terbesar. Untuk menargetkan nilai eigen di dekat pergeseran $\sigma$ , ulangi

(A-\sigma I)z_k=q_{k-1}

Nilai eigen $(A-\sigma I)^{-1}$ adalah $1/(\lambda_i-\sigma)$ , sehingga nilai eigen yang paling dekat dengan $\sigma$ menjadi dominan. Jangan pernah membentuk invers secara eksplisit. $Faktorkan$ $A-\sigma I$ dan selesaikan sistem linear pada setiap iterasi. Pergeseran tetap memungkinkan faktorisasinya digunakan kembali.

Jika $\sigma$ sangat dekat dengan suatu nilai eigen, sistem bergeser tersebut berkondisi buruk. Karena itu, selesaikan sistem linearnya dengan akurat dan $periksa residual pasangan eigen$ .

Algoritma QR untuk Spektrum Lengkap

Mulai dengan $A_0=A$ . Pada iterasi $k$ , hitung

A_k=Q_kR_k

Setiap langkah merupakan $transformasi kesebangunan ortogonal$ , sehingga nilai eigen tetap sama. Dalam perangkat lunak numerik, algoritma $\mathrm{QR}$ terlebih dahulu mereduksi matriks padat ke bentuk Hessenberg, memakai pergeseran, dan memisahkan blok yang telah konvergen. Untuk matriks real tak simetris, hasil akhirnya biasanya berupa bentuk Schur real dengan blok diagonal $1\times1$ dan $2\times2$ . Matriks simetris direduksi ke bentuk tridiagonal dan berkonvergensi ke matriks diagonal.

Memilih Metode yang Tepat

Tujuan dan struktur matriks	Metode yang sesuai	Pemeriksaan penting
Satu pasangan eigen dominan	Iterasi pangkat	magnitudo dominan unik dan komponen awal tak nol
Pasangan eigen di dekat $\sigma$	Iterasi invers bergeser	penyelesaian stabil dengan $A-\sigma I$
Beberapa pasangan eigen ekstrem dari matriks simetris jarang berukuran besar	Lanczos	hilangnya ortogonalitas dan residual
Beberapa pasangan eigen dari matriks tak simetris jarang berukuran besar	Arnoldi	ukuran subruang, pengulangan awal, dan residual
Spektrum lengkap matriks padat	$\mathrm{QR}$ bergeser menuju bentuk Schur	blok diagonal atau kuasidiagonal yang telah konvergen

Uji penerimaan akhir selalu mengikuti pasangan eigen yang diminta: $periksa residual$ , pertahankan pasangan konjugat kompleks untuk matriks real, dan jangan menyatakan vektor eigen sudah akurat hanya karena perkiraan nilai eigennya telah stabil.