# Recurrence Relation for Iterative Solution of Ax=b

$_nx$ represents the nth iteration.

## Homework Statement

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

## Homework 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$

## 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?

\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*}