# Show convergence of an algorithm within $m$ steps

I am trying to show that the following algorithm outputs the solution to the problem $$Ax=b$$.

Assumptions $$A$$ is symmetric positive definite of size $$n \times n$$ with $$m$$ distinct eigenvalues. The eigenvalues are known but their respective eigenvectors and the number of times each eigenvector is repeated is not known.

then

\begin{align} \text{for } &i = 0,\dots, m\\ &r_i = b - Ax_i\\ &x_{i+1} = x_i + \frac{1}{\lambda_i}r_i\\ \text{end} \end{align}

this algorithm should converge in $$m$$ steps

What I have done so far:

My aim has been to show that $$||x-x_m|| = 0$$ which in term will show that $$x-x_m = 0$$, which will complete our proof.

\begin{align} e_m &= x - x_m\\ &= x - x_{m-1} + x_m -x_{m-1}\\ &= e_{n-1} + \frac{1}{\lambda_{n-1}}r_{n-1}\\ & = e_0 + \sum_{i=1} ^{m-1} \frac{1}{\lambda_{i}}r_{i} \end{align}

At this point I tried taking the norm but that does not get me anywhere, I think I am missing something. I would appreciate some ideas and guidance.

• I'm assuming that the eigenvalues are $\lambda_1, \ldots, \lambda_m$, and the the index $i$ in the loop should go from $1$ to $m$ rather than $0$ to $m$. You DO have to say what $v$, $r_i$ and $x_1$ are, or it's tough to make sense of things. Regardless, the algorithm terminates in $m$ steps because the loop has only $m$ iterations. Did you mean something more useful than that? Also: is $A$ an $m \times m$ matrix? If so, and if e-vals are distinct, then every vector $x$ can be written as a linear combination of the associated eigenvectors, which are all orthogonal. – John Hughes Apr 23 at 20:15
• My previous comment has a short form: You should spend the effort to make your question meaningful, or you should not expect others to spend any effort answering it. – John Hughes Apr 23 at 20:16
• Convergence to what ??? Your question is horribly incomplete. – Yves Daoust Apr 23 at 20:18
• This is a question from this cs.cmu.edu/~quake-papers/painless-conjugate-gradient.pdf where this is exercise 2 (a), I have worked out the the other parts as (b), (c) etc as they are more numerical while this is an analytical. – Kori Apr 23 at 23:54

We can express the initial error $$e_0$$ as a linear combination of eigenvectors $$v_j$$ corresponding to the eigenvalues $$\lambda_j$$: $$e_0=\sum_{j=1}^mc_jv_j.$$ It does not matter that the eigenvalues can be repeated. There is always some eigenvector $$v_j$$ which we can take from the eigenspace of $$\lambda_j$$ to make the linear combination.
The initial residual $$r_0$$ is then $$r_0=Ae_0=\sum_{j=1}^mc_j\lambda_jv_j.$$
Now for the error $$e_1$$, we have $$e_1=e_0-\frac{1}{\lambda_1}r_0 =\sum_{j=1}^mc_jv_j-\frac{1}{\lambda_1}\sum_{j=1}^mc_j\lambda_jv_j =\sum_{j=2}^m c_j\frac{\lambda_j}{\lambda_1}v_j=\sum_{j=2}^m\tilde{c}_j v_j.$$ Note that the component corresponding to $$v_1$$ disappeared.
In this way, you can show that $$e_i$$ has no component in the eigenspaces corresponding to the eigenvalues $$\lambda_1,\ldots,\lambda_i$$ and hence $$e_m$$ is zero.
• Side note to OP: "There is always some eigenvector..." is the (first) place in this computation where the symmetry of $A$ is used. Are there any others? Where does positive definiteness come in? – John Hughes May 20 at 20:40