Lanczos largest Ritz values obey a Chebyshev start-angle bound, including degenerate branches

If exact Lanczos runs through step $m$ without breakdown, [F1], [F2], and [F7] give an orthonormal basis $Q_m$ of $K_m$ and a symmetric compression $H_m=Q_m^{\mathsf{T}}A{Q}_m$. By [F3], each eigenpair of $H_m$ lifts to an exact Ritz pair of $A$; by [F4], the largest eigenvalue of $H_m$ is the maximum Rayleigh quotient on $K_m$, namely ${\theta }_m$. If Lanczos breaks down earlier, no step-$m$ basis or Ritz assertion is used; ${\theta }_m$ remains defined directly by the Rayleigh–Ritz formula in the Statement.

Assume $r<n$. By [F4], choose an orthonormal eigenbasis of $A$ whose first $r$ vectors span the range of $P$. If $Pb=0$, then $b$ is orthogonal to that eigenspace. For every integer $j\ge 0$ and every top eigenvector $u$, symmetry gives $u^{\mathsf{T}}{A}^{j}b=(A^{j}u{)}^{\mathsf{T}}b={\lambda }_1^j{u}^{\mathsf{T}}b=0$. Thus every vector in $K_m$ lies in the orthogonal complement of the top eigenspace, where all Rayleigh quotients are at most ${\lambda }_{r+1}$; this proves branch 1.

If $r=n$, every eigenvalue is ${\lambda }_1$, so [F4] gives $A={\lambda }_{1}I$. Every nonzero $x\in K_m$ then has Rayleigh quotient ${\lambda }_1$, proving the stated dimension-one/full-multiplicity branch.

Assume $Pb\mathrm{\ne }0$ and ${\lambda }_{r+1}>{\lambda }_n$. Apply [F5] with $a={\lambda }_1$, $b={\lambda }_{r+1}$, $c={\lambda }_n$, and $k=m-1$ to obtain a polynomial $p_{m-1}$ of degree at most $m-1$ with $p_{m-1}({\lambda }_1)=1$ and $\mathrm{\mid }{p}_{m-1}(t)\mathrm{\mid }\le {\delta }_m$ on $[{\lambda }_n,{\lambda }_{r+1}]$, where ${\delta }_m:=1\mathrm{/}{T}_{m-1}(1+2({\lambda }_1-{\lambda }_{r+1})\mathrm{/}({\lambda }_{r+1}-{\lambda }_n))$. By [F7], $x:=p_{m-1}(A)b$ belongs to $K_m$, and spectral decomposition gives $Px=Pb$ and $\mathrm{\parallel }(I-P)x{\mathrm{\parallel }}_2\le {\delta }_m\mathrm{\parallel }(I-P)b{\mathrm{\parallel }}_2$.

Assume $Pb\mathrm{\ne }0$ and ${\lambda }_{r+1}={\lambda }_n$. The spectral decomposition gives $A={\lambda }_{n}I+({\lambda }_1-{\lambda }_n)P$. Hence $Ab={\lambda }_{n}b+({\lambda }_1-{\lambda }_n)Pb$, so [F7] gives $Pb\in K_2$ and it has Rayleigh quotient ${\lambda }_1$; this proves ${\theta }_m={\lambda }_1$ for $m\ge 2$. For $m=1$, [F7] gives $K_1=\mathrm{span}\{b\}$, and the same decomposition gives the displayed exact formula for ${\lambda }_1-{\theta }_1$.

Finally, assume $r<n$, $Pb\mathrm{\ne }0$, and exact Lanczos breaks down at column $d$. For $d>1$, no breakdown occurs at columns $j<d$. Starting from $q_1=b\mathrm{/}\mathrm{\parallel }b{\mathrm{\parallel }}_2$, inductively suppose $q_1,\dots ,q_j$ form an orthonormal basis of $K_j$. By the exact Arnoldi definition [F1, F6], the residual $w_j=A{q}_j-{\sum }_{i=1}^j{h}_{ij}{q}_i$ lies in $K_{j+1}$, is orthogonal to $K_j$, and is nonzero for $j<d$; hence its normalized vector $q_{j+1}$ lies in $K_{j+1}\setminus K_j$. Since $K_{j+1}$ is generated by $j+1$ vectors, $q_1,\dots ,q_{j+1}$ form a basis of $K_{j+1}$. Thus $q_1,\dots ,q_d$ form a basis of $K_d$. For $d=1$, $q_1$ directly spans $K_1$. Each $A{q}_j\in K_d$ for $j<d$, and $A{q}_d\in K_d$ because its orthogonalized residual $w_d$ is zero. Hence $A{K}_d\subseteq K_d$, and [F7] plus induction gives $K_m=K_d$ for $m\ge d$.

In the eigenbasis of [F4], write $x=Px+(I-P)x$. The two components are orthogonal, $A(Px)={\lambda }_{1}Px$, and all eigenvalues on the second component lie in $[{\lambda }_n,{\lambda }_{r+1}]$. Therefore ${\lambda }_1-\frac{x^{\mathsf{T}}Ax}{x^{\mathsf{T}}x}=\frac{{\sum }_{j>r}({\lambda }_1-{\lambda }_j)x_j^2}{\mathrm{\parallel }Px{\mathrm{\parallel }}_2^2+\mathrm{\parallel }(I-P)x{\mathrm{\parallel }}_2^2}\le ({\lambda }_1-{\lambda }_n)\frac{\mathrm{\parallel }(I-P)x{\mathrm{\parallel }}_2^2}{\mathrm{\parallel }Pb{\mathrm{\parallel }}_2^2}\le ({\lambda }_1-{\lambda }_n){\delta }_m^2{\tau }^2\mathrm{.}$ Since ${\theta }_m$ is the maximum Rayleigh quotient on $K_m$, it is at least the quotient of this nonzero $x$ and at most ${\lambda }_1$. This proves branch 2, including $m=1$ because $T_0=1$.

Let ${\mu }_1={\lambda }_1,{\mu }_2,\dots ,{\mu }_s$ be the distinct eigenvalues of $A$. Since $r<n$, $s\ge 2$ and the denominators below are nonzero. Define $p(t):={\prod }_{i=2}^s\frac{t-{\mu }_i}{{\lambda }_1-{\mu }_i}\mathrm{.}$ Then $p({\lambda }_1)=1$ and $p({\mu }_i)=0$ for $i\ge 2$. On the orthonormal eigenbasis from [F4], $p(A)$ therefore acts as the identity on the ${\lambda }_1$-eigenspace and as zero on every other eigenspace, so $p(A)=P$. Since $A{K}_d\subseteq K_d$ and $b\in K_d$, every power of $A$ applied to $b$ lies in $K_d$, whence $Pb=p(A)b\in K_d$. The nonzero vector $Pb$ has Rayleigh quotient ${\lambda }_1$, while no quotient can exceed ${\lambda }_1$; thus ${\theta }_d={\lambda }_1$ and the exact-breakdown branch follows.