Franklin's Notes


Arnoldi iteration

Arnoldi iteration is a technique for computing the eigenvalues of a matrix $A$ by reducing it to a Hessenberg matrix $H$ with the same eigenvalues. While reducing $A$ to Hessenberg form, modified Gram-Schmidt is used to calculate the orthogonal projectors $Q$ onto the Krylov spaces .

In the process of computing the factorization $AQ=QH$, the sequence of matrices $Q_n,H_n,\tilde H_n$ are calculated, where and $q_i$ is the ith orthonormal vector computed using modified Gram-Schmidt. With these matrices, we have that Taking the nth column of the matrices on both sides yields the equality From this equality, we can solve for $q_{n+1}$. As it happens, $q_{n+1}$ is the next Krylov vector $A^n b$, but orthonormalized with respect to the previous basis vectors ${q_1,q_2,\cdots,q_n}$. Solving for $q_{n+1}$ this way is a much more well-conditioned way of obtaining a basis for the Krylov space $\mathcal K_{n+1}$, since the usual basis ${b,Ab,\cdots,A^n b}$ is terribly conditioned.

The compact Arnoldi algorithm is as follows:

1. Let $b$ be an arbitrary initial guess.
2. Let $q_1=b/\lVert b\rVert_2$.
3. For $n=1,2,\cdots$:
1. Let $v=Aq_n$.
2. For $j=1,2,\cdots,n$:
1. Let $h_{jn} = q_j^\ast v$.
2. Let $v=v-h_{jn}q_j$. (This is the Gram-Schmidt step.)
3. Let $h_{n+1,n}=\lVert v\rVert_2$.
4. Let $q_{n+1}=v/h_{n+1,n}$.

linear-algebra

matrices

numerical-analysis

back to home page