Krylov subspace methosd are among the most widely used class of algorithms for solving Ax=b when A is a very large-sparse matrix.
These methods work by constructing the Krylov subspace
Kk(A,b):=span{b,Ab,…,Ak−1b}.
This page focuses on the Lanczos method for matrix function approximation (Lanczos-FA) used to approximate A−1b.
The Lanczos-FA iterate is defined as
lank(1/x):=∥b∥2Qf(T)e1,
where Q=[q1,…,qk] is an orthonormal basis for Kk(A,b) such that span{q1,…,qj}=Kj(A,b) for all j≤k, and T:=QTAQ.
Positive definite systems
In the case that A is positive definite, then the Lanczos-FA iterate is equivalent to the well-known conjugate gradient algorithm.
The simplest proof of this amounts to showing the Lanczos-FA iterate satisfies the same optimality property as CG.
Proof.
An arbitrary vector in Kk(A,b) can be written Qc for some x∈Rk.
Thus,
x∈Kk(A,b)min∥A−1b−x∥A=c∈Rkmin∥A−1b−Qc∥A.=c∈Rkmin∥A1/2(A−1b−Qc)∥2.=c∈Rkmin∥A−1/2b−A1/2Qc∥2.
Writing the solution to the normal equations, we find that the above equations are minimized for
c=((A1/2Q)T(A1/2Q))−1(A1/2Q)T(A−1/2b)=(QTAQ)−1QTb=∥b∥2T−1e1.
Thus, we have solution
x=Qc=∥b∥2QT−1e1=lank(1/x).
This proves the theorem.□
This optimality property allows us to derive a number of prior bounds for the convergence of Lanczos-FA (and equivalently CG).
Indefinite systems
If A is not positive definite, T may have an eigenvalue at or near to zero and the error of the Lanczos-FA approximation to A−1b can be arbitrarily large.
The MINRES iterates are defined as
y^k:=y∈Kk(A,b)argmin∥b−Ay∥2=y∈Kk(A,b)argmin∥A−1b−y∥A2.
Define the residual vectors
rk:=b−Alank(1/x),rkM:=b−Ay^k,
and note that the MINRES residual norms are non-increasing due to the optimality of the MINRES iterates.
In [1], it is shown that the CG residual norms are near the MINRES residual norms at iterations where MINRES makes good progress.
More precisely, the algorithms are related by
∥rk∥2=1−(∥rkM∥2/∥rk−1M∥2)2∥rkM∥2.
The following theorem represents a strengthening of the bounds in Appendix A of [2].
To the best of our knowledge, the result is new.
Theorem.For every k, there exists k∗≤k such that∥b−Alank∗(1/x)∥2≤(ek+k1)deg(p)<kmin∥b−Ap(A)b∥2.
Proof.
If k=0, the theorem is trivially true.
Fix k>0.
If e∥rkM∥2>∥b∥2, then the theorem holds as e≤(ek+1/k).
Assume e∥rkM∥2≤∥r0M∥2=∥b∥2 so that there exists an integer k′∈(0,k] such that
∥rk′M∥2≥e∥rkM∥2≥∥rk′+1M∥2.
We then have that
∥rk′M∥2∥rk′+1M∥2⋅∥rk′+1M∥2∥rk′+2M∥2⋯∥rk−1M∥2∥rkM∥2=∥rk′M∥2∥rkM∥2≤e1.
Thus, there exists an integer k∗∈(k′,k] such that
∥rk∗−1M∥2∥rk∗M∥2≤(e1)1/(k−k′)≤(e1)1/k.
Since the MINRES residual norms are non-increasing, ∥rk∗M∥2≤∥rk′+1M∥2≤e∥rkM∥2.
Thus,
∥rk∗∥2=1−(∥rk∗M∥2/∥rk∗−1M∥2)2∥rk∗M∥2≤1−(1/e)2/ke∥rkM∥2.
It can be verified that
ek≤1−(1/e)1/ke≤ek+k1.
Thus, we find that
∥b−Alank∗(1/x)∥2=∥rk∗∥2≤(ek+k1)∥rkM∥2.
The result follows from the optimality of the MINRES iterates. □
References
1. Cullum, J.; Greenbaum, A. Relations Between Galerkin and Norm-Minimizing Iterative Methods for Solving Linear Systems. SIAM Journal on Matrix Analysis and Applications1996, 17, 223–247, doi:10.1137/S0895479893246765.
2. Chen, T.; Greenbaum, A.; Musco, C.; Musco, C. Error Bounds for Lanczos-Based Matrix Function Approximation. SIAM Journal on Matrix Analysis and Applications2022, 43, 787–811, doi:10.1137/21m1427784.