Editing Arnoldi iteration (section)

==Properties of the Arnoldi iteration==

Let ''Q''<sub>''n''</sub> denote the ''m''-by-''n'' matrix formed by the first ''n'' Arnoldi vectors ''q''<sub>1</sub>, ''q''<sub>2</sub>, ..., ''q''<sub>''n''</sub>, and let ''H''<sub>''n''</sub> be the (upper [[Hessenberg matrix|Hessenberg]]) matrix formed by the numbers ''h''<sub>''j'',''k''</sub> computed by the algorithm:
:<math> H_n = Q_n^* A Q_n. </math>

The orthogonalization method has to be specifically chosen such that the lower Arnoldi/Krylov components are removed from higher Krylov vectors. As <math> A q_i </math> can be expressed in terms of ''q''<sub>1</sub>, ..., ''q''<sub>''i''+1</sub> by construction, they are orthogonal to ''q''<sub>''i''+2</sub>, ..., ''q''<sub>''n''</sub>, 

We then have

:<math> H_n = \begin{bmatrix}
   h_{1,1} & h_{1,2} & h_{1,3} & \cdots  & h_{1,n} \\
   h_{2,1} & h_{2,2} & h_{2,3} & \cdots  & h_{2,n} \\
   0       & h_{3,2} & h_{3,3} & \cdots  & h_{3,n} \\
   \vdots  & \ddots  & \ddots  & \ddots  & \vdots  \\
   0       & \cdots  & 0     & h_{n,n-1} & h_{n,n}
\end{bmatrix}. </math>

The matrix ''H''<sub>''n''</sub> can be viewed as ''A'' in the subspace <math>\mathcal{K}_n</math> with the Arnoldi vectors as an orthogonal basis; ''A'' is orthogonally projected onto <math>\mathcal{K}_n</math>.  The matrix ''H''<sub>''n''</sub> can be characterized by the following optimality condition. The [[characteristic polynomial]] of ''H''<sub>''n''</sub> minimizes ||''p''(''A'')''q''<sub>1</sub>||<sub>2</sub> among all [[monic polynomial]]s of degree ''n''. This optimality problem has a unique solution if and only if the Arnoldi iteration does not break down.

The relation between the ''Q'' matrices in subsequent iterations is given by
:<math> A Q_n = Q_{n+1} \tilde{H}_n </math>
where
:<math> \tilde{H}_n = \begin{bmatrix}
   h_{1,1} & h_{1,2} & h_{1,3} & \cdots  & h_{1,n} \\
   h_{2,1} & h_{2,2} & h_{2,3} & \cdots  & h_{2,n} \\
   0       & h_{3,2} & h_{3,3} & \cdots  & h_{3,n} \\
   \vdots  & \ddots  & \ddots  & \ddots  & \vdots  \\
   \vdots  &         & 0       & h_{n,n-1} & h_{n,n} \\
   0       & \cdots  & \cdots  & 0       & h_{n+1,n}
\end{bmatrix} </math>
is an (''n''+1)-by-''n'' matrix formed by adding an extra row to ''H''<sub>''n''</sub>.