What is a simple definition of Lanczos iteration that is understandable?

Question

I have seen that Lanczos's Algorithm can be used to tri-diagonalize a matrix but all of the definitions I have seen of it have been very complicated to understand.

Answer 1

The Lanczos algorithm is an example of a Krylov subspace method, which are usually used to find a few of the "most important" (largest) eigenvalues of some matrix $A$ and their corresponding eigenvalues.

The idea is to pick a random vector $b$ and look at the sequence of subspaces $ \mathcal{K}_p(A,b) := \langle b, Ab, A^2 b, ... , A^p b \rangle$. Repeated applications of the matrix "amplify" the components of the vector corresponding to the largest eigenvalues, so by the time that $\mathcal{K}_p(A,b) = \mathcal{K}_{p+1}(A,b)$, that subspace will contain eigenvectors corresponding to large eigenvalues.

The Lanczos algorithm itself is based on this idea, but it orthogonalizes the new vectors with Gram-Schmidt, and it also requires that the input matrix be Hermitian, which allows a simpler computation of some steps. And instead of giving the largest eigenvalues/vectors directly, it outputs a simple (tridiagonal) matrix whose largest eigenvalues (and corresponding eigenvectors) are the same as for A.

The Lanczos algorithm wikipedia page for has a pretty good rundown of the motivation and derivation behind the algorithm.