Connection between Arnoldi and polynomials of A

The vectors in span($Q_k$) have a special interpretation. Any vector in the span of $Q_k$ can be written as a polynomial of $A$ times $q_1.$

$$\begin{array}{c}{Q}_{k}y=\sum _{i=1}^k{y}_i{q}_i=\sum _{i=1}^k{z}_i{A}^{i-1}{q}_1\\ Q_{k}y=p_{k-1}(A)q_1\end{array}$$

Polynomials of $A$ can be used to interpret the convergence of Arnoldi. Arnoldi is a process that finds a polynomial $p$ such that $p(A)$ is small in some appropriate sense.

Making $p(A)$ small may start to make sense if we go back to the characteristic polynomial. Recall the definition:

$$p_A(z)=\det (zI-A)$$

Then:

$$p_A(A)=0$$

We provide a proof for cases where $A$ is diagonalizable.

Proof: Assume that $A$ is diagonalizable.

$$\begin{array}{c}A=X\Lambda X^{-1}\\ p(A)=Xp(\Lambda )X^{-1}\\ [p(\Lambda ){]}_{ii}=p({\lambda }_i)\end{array}$$

Since $p_A(\Lambda )=0,$ we get

$$p_A(A)=0$$

$\square$

Making $p(A)$ small §

Let’s explore in what sense Arnoldi makes $p(A)$ small. Here is the optimality condition statement:

Arnoldi builds a $p_k(A)$ such that $\Vert p_k(A)q_1{\Vert }_2$ is minimum.

This leads to approximate eigenvalues.

Recall that we approximate the eigenvalues of $A$ using $H_k$. This is equivalent to computing the roots of the characteristic polynomial of $H_k$:

$$p_k(z)=\det (zI-H_k)$$

Theorem: $p_k(z)=\det (zI-H_k)$ minimizes

$$\Vert p_k(A)q_1{\Vert }_2$$

among all monic polynomials of degree $k$:

$$p(z)=z^k+c_{k-1}{z}^{k-1}+\cdots +c_0$$

Why is this result relevant for eigenvalue approximation?

Here is the sketch of an argument.

$$\begin{array}{c}{p}_k(A)q_1=X{p}_k(\Lambda )X^{-1}{q}_1\\ p_k(\Lambda )=\left[\begin{array}{cccc}{\prod }_{i=1}^k({\lambda }_1-{\mu }_i)& & & \\ & {\prod }_{i=1}^k({\lambda }_2-{\mu }_i)& & \\ & & \ddots & \\ & & & {\prod }_{i=1}^k({\lambda }_n-{\mu }_i)\end{array}\right]\end{array}$$

So

$$p_k(A)\text{ small }\iff |{\lambda }_p-{\mu }_i|\text{ small.}$$

But making this statement more precise is difficult for unsymmetric $A$.