Recurrence Relation for Iterative Solution of Ax=b

[Kidnapster]

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

 

[Kidnapster]

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

<br /> \begin{align*}<br /> {_{n+1}x} &amp;= {_nx} + M_1^{-1}(b-A_nx)\\<br /> {_{n+2}x} &amp;= {_{n+1}x} + M_1^{-1}(b-A_{n+1}x) \\<br /> {_{n+2}x} &amp;= {_nx} + M_1^{-1}(b-A_nx) + M_2^{-1}(b-A[{_nx} + M_1^{-1}(b-A_nx)])\\<br /> {_{n+2}x} &amp;= {_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 \\<br /> {_{n+2}x} &amp;= {_nx} + M_1^{-1}(b-A_nx) + M_2^{-1}(b-A_nx) - M_2^{-1}AM_1^{-1}(b-A_nx) \\<br /> {_{n+2}x} &amp;= {_nx} + M_1^{-1}(M_1+M_2-A)M_2^{-1}(b-A_nx)<br /> \end{align*}<br /> <br />