Lanczosmetoder

Lanczosmetoderna är en familj av iterativa algoritmer för beräkning av extremvärden och associerade vektorer hos stora sparsamma matriser. De är uppkallade efter Cornelius Lanczos och används när direkta diagonaliseringsmetoder är orealistiska på grund av minnes- eller beräkningskostnad.

Grundidén är att bygga Krylovrummet K_k(A, v1) = span{v1, Av1, A^2v1, ..., A^{k-1}v1} och med Lanczos-iterationerna producera en liten tridiagonal matris T_k. Om A är Hermitian (eller symmetrisk) är T_k real och symmetrisk. Värdena av T_k:s egenvärden kallas Ritzvärden och ger goda approximationer till ett antal extremvärden av A; därigenom kan man få de största eller lägsta egenvärdena med relativt få dimensioner.

Huvudanvändningar är alltså eigenvärdesproblem för stora sparsamma matriser och lösning av linjära system Av=b när A är symmetrisk positivt definit. I det fallet är Lanczosprocessen nära kopplad till konjugerad gradientmetoden: CG används som ett speciellt fall av Lanczos för SPD-matriser, och andra varianter som MINRES används för mer generella symmetriska matriser.

Det finns varianter för icke-symmetriska matriser, bland annat Bi-Lanczos och Golub-Kahan-bidiagonalization för singulärvärdesproblem. Numeriskt kan Lanczosvectorernas ortogonalitet försämras i finite precision, vilket leder till spökeigenvärden och minskat välstånd. Återorthogonalisering (full eller partiell/partial reorthogonalization) är en vanlig motåtgärd, oftast med ökad kostnad.

Användningar och programvara: Lanczosmetoder är centrala i programvara för stor skals eigenvärdesberäkning (till exempel implicit restarted Lanczos i ARPACK). De används i teknik, fysik och modellering där effektiva stora sparsamma eigenvärdesberäkningar krävs.