Lanczos算法

Lanczos算法是一種將對稱矩陣通過正交相似變換變成對稱三對角矩陣的算法，以20世紀匈牙利數學家Cornelius Lanczos命名。

概述

Lanczos算法實際上是Arnoldi算法對於對稱矩陣的特殊形式，可套用於對稱矩陣線性方程組求解的Krylov子空間方法以及對稱矩陣的特徵值問題。

算法

Lanczos算法

給定對稱矩陣A;

選取單位向量v_1;

設定v_0為零向量;

設定b_0=0;

for i=1:m

a_i=(Av_i,v_i);

b_i=||Av_i-a_iv_i-b_{i-1}v_{i-1}||;

b_i v_{i+1} = Av_i - a_i v_i - b_{i-1}v_{i-1};

end

由上述Lanczos算法得：V'AV=T,

其中V=[v_1,...,v_m], T=tridiag(b,a,b), a=[a_1,...,a_m], b=[b_1,...,b_m].

matlab實現程式

A代表任意一個需要三對角化的矩陣，b是任意一個向量，且b的行數與A的列數相同因為要用到v = A*q;

nmax是你想要得到的矩陣的大小，例如nmax=12，最後得到12*12的三對角矩陣。

結果輸出的是一個三對角矩陣

輸入形式為： lanczos([1 2 3;4 5 6;7 8 9],[1;1;1],12);

function T = lanczos(A, b, nmax)

m = size(A,1);

beta(1) = 0;

qprev = zeros(m, 1);

q = b / norm(b);

for n = 1:nmax

v = A*q;

alpha(n) = q' * v;

v = v - beta(n) * qprev - alpha(n) * q;

beta(n+1) = norm(v);

qprev = q;

q = v / beta(n+1);

end

beta = beta(2:end-1);

T = diag(alpha) + diag(beta,1) + diag(beta,-1);