Recurrence Relation for Iterative Solution of Ax=b

  • Thread starter Kidnapster
  • Start date
  • #1
[itex] _nx [/itex] represents the nth iteration.

Homework Statement



Show that [itex] {_{n+2}}x = _nx + M^{-1}(b-A{_nx}) [/itex]

Homework Equations



[itex] {_{n+1}}x = _nx + M_1^{-1}(b-A{_nx}) [/itex]
[itex] {_{n+2}}x = {_{n+1}}x + M_2^{-1}(b-A{_{n+1}x}) [/itex]
[itex] M = M_1(M_1+M_2-A)^{-1}M_2 [/itex]

The Attempt at a Solution



I tried was adding the two equations, which gives [itex] _{n+2}x = M_2^{-1}(b-A{_{n+1}x}) + _nx + M_1^{-1}(b-A{_nx}) [/itex]. But [itex] M_2^{-1}(b-A{_{n+1}}x) [/itex] devolves into a huge mess once I expand it. Subtraction is less helpful, as you are left without any [itex] _nx [/itex]. Directly substituting for [itex]_{n+1}x [/itex] 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?
 

Answers and Replies

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

[tex]
\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*}

[/tex]
 

Related Threads on Recurrence Relation for Iterative Solution of Ax=b

Replies
7
Views
791
Replies
5
Views
786
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
0
Views
3K
  • Last Post
Replies
5
Views
1K
Top