Menghitung Semua Nilai Eigen dengan Iterasi QR

Perubahan Basis Berulang yang Mempertahankan Nilai Eigen

Algoritma $\mathrm{QR}$ menghitung seluruh nilai eigen matriks persegi melalui perubahan basis yang berulang. Setiap langkah menghasilkan $matriks serupa$ , sehingga nilai eigennya tetap sama. Tujuan iterasi adalah memperoleh bentuk diagonal atau bentuk Schur. Konvergensi memerlukan pemilihan strategi pergeseran dan deflasi yang sesuai. Nilai eigen kemudian diperoleh dari elemen diagonal atau blok kecil pada diagonal.

Versi di bawah adalah iterasi $\mathrm{QR}$ tanpa geseran. Algoritma nilai eigen yang dipakai dalam perangkat lunak numerik juga menggunakan geseran, mereduksi matriks ke bentuk Hessenberg, dan memisahkan blok yang sudah konvergen agar proses perhitungan menjadi lebih cepat dan andal.

Satu Iterasi QR

Untuk uji deflasi berikut, terlebih dahulu ubah matriks melalui keserupaan uniter ke $bentuk Hessenberg atas$ , yaitu semua entri di bawah subdiagonal pertama nol. Mulai iterasi dari matriks tersebut. Contoh 2×2 di bawah sudah memenuhi syarat ini.

Mulai dengan $A_0=A$ .
Faktorkan matriks saat ini menjadi faktor uniter atau ortogonal $Q_k$ dan faktor segitiga atas $R_k$ :

$A_k=Q_kR_k$
Balik urutan kedua faktor untuk memperoleh iterasi berikutnya:

$A_{k+1}=R_kQ_k$
Ulangi faktorisasi dan perkalian terbalik tersebut. Elemen subdiagonal yang sangat kecil dibandingkan elemen diagonal di sekitarnya dapat ditetapkan menjadi nol. Pemisahan yang disebut $deflasi$ ini mengisolasi nilai eigen atau blok yang sudah konvergen.

$\begin{aligned} &|(A_k)_{j+1,j}| \\ &\leq \tau\left(|(A_k)_{j,j}|+|(A_k)_{j+1,j+1}|\right) \end{aligned}$

Di sini $\tau$ adalah toleransi yang disesuaikan dengan presisi numerik dan skala masalah. Perubahan kecil pada diagonal saja belum cukup sebagai kriteria berhenti karena elemen di bawah diagonal mungkin masih bernilai signifikan.

Mengapa Nilai Eigen Tidak Berubah

Karena $Q_k$ bersifat uniter, $Q_k^{*}Q_k=I$ . Dengan menyubstitusikan $R_k=Q_k^{*}A_k$ ke dalam perkalian terbalik, kita memperoleh

A_{k+1}=R_kQ_k

Jadi, $A_{k+1}$ serupa secara uniter dengan $A_k$ . $Matriks serupa memiliki polinom karakteristik$ dan nilai eigen yang sama. Setiap langkah $\mathrm{QR}$ menuliskan transformasi linear yang sama dalam koordinat baru.

Bentuk Hasil Konvergensi

Bentuk akhir bergantung pada jenis matriks dan $sistem bilangan$ yang digunakan.

Matriks	Bentuk konvergen	Cara membaca nilai eigen
Real simetris atau kompleks Hermitian	Matriks diagonal	Elemen diagonal adalah nilai eigen real
Kompleks umum	Bentuk Schur segitiga atas	Elemen diagonal adalah nilai eigen
Real umum	Bentuk Schur real kuasi-segitiga atas	Setiap blok $1\times1$ memberi satu nilai eigen real. Setiap blok $2\times2$ memberi sepasang nilai eigen kompleks konjugat

Nilai eigen dapat muncul dalam urutan apa pun. Nilai yang berulang dan susunan khusus perlu ditangani terpisah karena syarat urutan nilai mutlak yang ketat tidak mencakup keduanya.

Iterasi tanpa geseran $tidak selalu berkonvergensi ke bentuk tersebut$ . Sebagai contoh, matriks simetris berikut memiliki faktorisasi $Q=C$ dan $R=I$ , sehingga iterasi berikutnya tidak berubah:

C=\begin{pmatrix}0&1\\1&0\end{pmatrix},\qquad C=CI,\qquad RQ=IC=C

Nilai eigennya 1 dan −1. Magnitudo yang sama menjelaskan kebutuhan geseran yang sesuai serta pemeriksaan konvergensi dalam algoritma numerik.

Contoh Kerja Matriks Simetris

Perhatikan matriks simetris

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

Satu faktorisasi $\mathrm{QR}$ dan perkalian terbalik menghasilkan

\begin{aligned} &Q_0=\frac{1}{\sqrt5}\begin{pmatrix}2&-1\\1&2\end{pmatrix}, \\ &R_0=\begin{pmatrix}\sqrt5&\frac4{\sqrt5}\\0&\frac3{\sqrt5}\end{pmatrix} \end{aligned}

$Besar elemen di luar diagonal$ sudah turun dari $1$ menjadi $3/5$ . Iterasi berikutnya mendorong kedua elemen di luar diagonal menuju nol:

A_k\longrightarrow\begin{pmatrix}3&0\\0&1\end{pmatrix}

Diagonal hasil limit memuat nilai eigen $3$ dan $1$ . Setiap hasil iterasi serupa dengan $A_0$ , sehingga kedua nilai tersebut memang milik matriks semula.