Lanczos finds the largest eigenvalue three times

Lanczos is for the extreme eigenvalues of a symmetric matrix too big to diagonalize, when all you can do with it is multiply a vector by it. From one starting vector $q_0$ it builds an orthonormal basis $q_0,q_1,\dots$ of the Krylov space, the span of $q_0,A{q}_0,A^2{q}_0,\dots$. In that basis $A$ is tridiagonal, and each new vector needs only the two before it:

The eigenvalues of the small tridiagonal matrix $T$ (the $\alpha$ on its diagonal, the $\beta$ beside it) are the Ritz values, and the largest and smallest of them converge to the largest and smallest eigenvalues of $A$ after far fewer steps than $A$ has rows.

The three-term formula is where the trouble is. It makes $q_{j+1}$ orthogonal to $q_j$ and $q_{j-1}$ by construction, and to every earlier vector only because, in exact arithmetic, those overlaps are zero anyway. In floating point they are not zero, and nothing removes them.

The numpy twin of this program, with the same matrix and starting vector, is posts/refs/lanczos-loses-orthogonality.py; its output is beside it.

Sixty steps, twice

The cell runs Lanczos twice from the same $q_0$. The plain run is the three-term formula above. The other run, after the formula, subtracts from $w$ its component along every basis vector so far, $w\leftarrow w-q_i(q_i\cdot w)$ for $i=0,\dots ,j$: full reorthogonalization. That costs $j$ extra dot products at step $j$, so $O(N{k}^2)$ over $k$ steps where plain Lanczos costs $O(Nk)$ beyond the products with $A$, and it needs every vector kept in memory.

At each step the cell records three things: the Ritz values (the eigenvalues of $T$ so far, from eig_sym), the largest overlap of the new vector with any earlier one, and how much of the new vector lies along $u$, the eigenvector of $A$ for the eigenvalue 4.

Where the lost orthogonality goes

The figure shows the size of each new basis vector's component along $u$, the eigenvector for 4. In both runs it first falls, geometrically: $A$ stretches the $u$ direction the most, so the Krylov space captures it early, and once it is in the space the new vectors, orthogonal to the space, have nothing left along it. By step 13 the largest Ritz value equals 4 to rounding, and at step 14 the plain run's component along $u$ reaches its lowest value, $2\times 10^{-8}$ ($1.8\times 10^{-8}$ in numpy: from here on the two programs agree on when things happen and how big they get, not on the last digits).

From there the two runs split. With reorthogonalization the component keeps falling to rounding, below $10^{-16}$, and stays. In the plain run the rounding errors of each step leave a little of $u$ in the new vector, nothing subtracts it, and $A$ amplifies it at every later step, for the same reason it amplified $u$ in the first place. The component grows back to order one by step 24. The basis then contains $u$ a second time, the Ritz values converge to 4 a second time, and the component falls again, only to grow back near step 46. The overlap of new vectors with old ones, in the second figure, rises in step with it. (Where the reorthogonalized component comes out exactly 0, the first figure draws it at $10^{-18}$.)

Ghosts

Each time $u$ comes back, the plain run finds the eigenvalue 4 again. The figure follows the three largest Ritz values step by step. With reorthogonalization they settle at 4, at 3, and just under 1, the top of the bulk: the three largest eigenvalues of $A$. In the plain run the second and then the third also go to 4. After 60 steps the plain run has three Ritz values within $10^{-8}$ of 4, and the matrix has 4 once. The copies are called ghosts. They are not wrong in the sense of pointing at a number that is not an eigenvalue; they are wrong about multiplicity, and meanwhile the steps spent on them are not spent on the 3 and the bulk.

Full reorthogonalization is the fix used here. It is also the most expensive one; selective reorthogonalization (against converged Ritz vectors only) costs less, and restarted Lanczos, as in ARPACK, keeps full reorthogonalization affordable by keeping the basis short.