Algoritma Lanczos
Algoritma

Algoritma ini memerlukan sebuah matriks Hermite  A berukuran  n\times n, dan secara opsional sebuah bilangan  m yang menyatakan banyak iterasi yang diinginkan. Jika nilai  m tidak ditentukan, umumnya diambil  m=n. Sebenarnya, algoritma tidak memerlukan akses ke matriks secara eksplisit, melainkan sebuah fungsi  v\mapsto Av yang menghasilkan produk perkalian matriks dengan vektor. Fungsi ini dipanggil paling banyak  m kali. Pada proses iterasi, algoritma rentan terhadap ketidakstabilan numerik. Ketika dieksekusi dalam aritmatika non-eksak (non-exact arithmetic), pertimbangan-pertimbangan tambahan harus diambil untuk memastikan validitas hasil (dijelaskan di bagian selanjutnya). Di akhir iterasi, algoritma akan menghasilkan sebuah matriks ortonormal  V berukuran  n\times m dan sebuah matriks simetrik real tridiagonal  T=V^{*}AV berukuran  m\times m. Dalam kasus  m=n, maka  V akan berupa matriks uniter, dan matriks  A=VTV^{*}.
Pada prinsipnya ada empat cara untuk menulis prosedur iterasi. Paige dan karya-karya lainnya menunjukkan bahwa urutan operasi berikut adalah yang paling stabil secara numerik.:
Anggap  v_{1}\in \mathbb {C} ^{n} sebagai sebarang vektor dengan norma Euklidean  1
Langkah awal iterasi yang disingkat:
Tetapkan  w_{1}'=Av_{1}.
Tetapkan  \alpha _{1}=w_{1}'^{*}v_{1}.
Tetapkan  w_{1}=w_{1}'-\alpha _{1}v_{1}
Untuk nilai j=2,\dots ,m , lakukan:
Tetapkan  \beta _{j}=\|w_{j-1}\| (juga sebuah norma Euklidean).
Jika  \beta _{j}\neq 0, tetapkan nilai   v_{j}=w_{j-1}/\beta _{j}. Namun jika  \beta _{j}=0, pilih  v_{j} sebagai sebarang vektor bernorma Euclidean  1 yang ortogonal dengan semua vektor  v_{1},\dots ,v_{j-1}.
Tetapkan  w_{j}'=Av_{j}.
Tetapkan  \alpha _{j}=w_{j}'^{*}v_{j}.
Tetapkan  w_{j}=w_{j}'-\alpha _{j}v_{j}-\beta _{j}v_{j-1}.
Bentuk matriks  V dengan menyusun  v_{1},\dots ,v_{m} sebagai kolom-kolomnya; dan bentuk matriks T={\begin{pmatrix}\alpha _{1}&\beta _{2}&&&&0\\\beta _{2}&\alpha _{2}&\beta _{3}&&&\\&\beta _{3}&\alpha _{3}&\ddots &&\\&&\ddots &\ddots &\beta _{m-1}&\\&&&\beta _{m-1}&\alpha _{m-1}&\beta _{m}\\0&&&&\beta _{m}&\alpha _{m}\\\end{pmatrix}}
Catatan:  Av_{j}=w_{j}'=\beta _{j+1}v_{j+1}+\alpha _{j}v_{j}+\beta _{j}v_{j-1} untuk  1<j<m.
Dalam praktiknya vektor awal  v_{1} dapat dianggap sebagai argumen input tambahan dari prosedur; sedangkan  \beta _{j}=0 dan indikator-indikator galat numerik dapat diikutsertakan sebagai tambahan kondisi penghentian iterasi.
Tanpa menghitung perkalian matriks-vektor, setiap iterasi melakukan  O(n) operasi aritmetika. Perkalian matriks-vektor sendiri dapat dilakukan dalam  O(dn) operasi aritmetika, dengan  d menyatakan rata-rata jumlah elemen bukan nol dalam sebuah baris. Dengan demikian, algoritma Lanczos memiliki total kompleksitas sebesar  O(dmn), atau  O(dn^{2}) dalam kasus  m=n; hal ini membuatnya bisa sangat cepat untuk matriks rongga. Skema-skema untuk meningkatkan stabilitas numerik biasanya dibandingkan dengan kinerja tinggi ini.
Vektor  v_{j} disebut dengan vektor Lanczos. Vektor  w_{j}' tidak digunakan setelah nilai  w_{j} dihitung, dan vektor  w_{j} tidak digunakan setelah  v_{j+1} dihitung. Hal ini memungkinkan untuk menggunakan penyimpanan yang sama untuk ketiga vektor tersebut. Begitu juga jika kita hanya ingin mencari matriks tridiagonal  T, proses iterasi tidak memerlukan  v_{j-1} setelah menghitung  w_{j}; meskipun beberapa skema untuk meningkatkan stabilitas numerik akan membutuhkan vektor ini nantinya. Terkadang vektor-vektor Lanczos yang berikutnya dihitung ulang dari  v_{1} jika diperlukan.