# Recurrence Relation for Iterative Solution of Ax=b

1. Jun 16, 2011

### Kidnapster

$_nx$ represents the nth iteration.

1. The problem statement, all variables and given/known data

Show that ${_{n+2}}x = _nx + M^{-1}(b-A{_nx})$

2. Relevant equations

${_{n+1}}x = _nx + M_1^{-1}(b-A{_nx})$
${_{n+2}}x = {_{n+1}}x + M_2^{-1}(b-A{_{n+1}x})$
$M = M_1(M_1+M_2-A)^{-1}M_2$

3. The attempt at a solution

I tried was adding the two equations, which gives $_{n+2}x = M_2^{-1}(b-A{_{n+1}x}) + _nx + M_1^{-1}(b-A{_nx})$. But $M_2^{-1}(b-A{_{n+1}}x)$ devolves into a huge mess once I expand it. Subtraction is less helpful, as you are left without any $_nx$. Directly substituting for $_{n+1}x$ in the second equation is even less helpful, as you are left with a huge mess of terms that can't really be factored. What am I missing?

2. Jun 17, 2011

### Kidnapster

Never mind, figured it out. Here's my solution:

\begin{align*} {_{n+1}x} &= {_nx} + M_1^{-1}(b-A_nx)\\ {_{n+2}x} &= {_{n+1}x} + M_1^{-1}(b-A_{n+1}x) \\ {_{n+2}x} &= {_nx} + M_1^{-1}(b-A_nx) + M_2^{-1}(b-A[{_nx} + M_1^{-1}(b-A_nx)])\\ {_{n+2}x} &= {_nx} + M_1^{-1}b - M_1^{-1}A_nx + M_2^{-1}b-M_2^{-1}A_nx - M_2^{-1}AM_1^{-1}b + M_2^{-1}AM_1^{-1}A_nx \\ {_{n+2}x} &= {_nx} + M_1^{-1}(b-A_nx) + M_2^{-1}(b-A_nx) - M_2^{-1}AM_1^{-1}(b-A_nx) \\ {_{n+2}x} &= {_nx} + M_1^{-1}(M_1+M_2-A)M_2^{-1}(b-A_nx) \end{align*}