How to minimize the Rayleigh quotient to find the smallest eigenvalue during Lanczos iteration?

Solution 1:

Suppose $Q$ is the orthonormal Krylov basis and $T$ is the corresponding tridiagonal matrix. Then $Q^TQ=I$ and $Q^TAQ = T$.

Any vector in Kyrlov subspace can be written $Q c$, where $c$ gives the coefficients for a linear combination of the column of $Q$. Thus, $$ \min_{x\in\mathcal{K}} \frac{x^TAx}{x^Tx} = \min_{c\in\mathbb{R}^k} \frac{(Qc)^TA(Qc)}{(Qc)^T(Qc)} = \min_{c\in\mathbb{R}^k} \frac{c^T(Q^TAQ)c}{c^T(Q^TQ)c} = \min_{c\in\mathbb{R}^k} \frac{c^TTc}{c^Tc}. $$ But the rightmost expression is simply the smallest eigenvalue of $T$. The same approach holds for the large eigenvector.