0

In the book Numerical recipes in C, equation (2.5.10) reads as $$ x_{n+1}-x_{n}=B_0(b-A x_n) $$ could someone give a hint how this is derived?

From my side, I could only understand the following.
The problem is to find improved solutions to $$ Ax=b $$ where $A$ is a square matrix.
Now suppose $B_0$ is an approximation to $A^{-1}$ and then define residule matrix $$ id-B_0A=R $$ which implies $$ B_0A=id-R $$ and $$ A^{-1}=(id-R)^{-1}B_0. $$ Moreover define $$ B_n=(id+R+....+R^n)B_0 $$ to be refined approximation to $A^{-1}$ compared to $B_0$, further, define $x_n=B_nb$. Then

Q1: I have a hard time to get why equation (2.5.10), i.e. $x_{n+1}-x_{n}=B_0(b-A x_n)$ in the book holds. Here $x_n$ is defined to be $B_nb$, so to make the definition consistent, $x_{n+1}=B_{n+1}b$ should hold?

Q2: Is there some high level theory to explain the idea here (e.g. with abstract algebra)?

Comment to Q1: let $x_n=x+\delta_n$. Then $$ Ax_n=b+A\delta_n, $$ therefore $$ \delta_n=A^{-1}(Ax_n-b). $$ This implies $$ x=x_n-A^{-1}(Ax_n-b). $$ Attempted answer to Q1: an attempt aimed at the derivation of (2.5.10) I tried was the following $$ \begin{align} x_{n+1}-x_n&=(B_{n+1}-B_n)b=R^{n+1}B_0b\\ &\Updownarrow\\ Ax_n&=AB_nb\\ &\Updownarrow\\ B_nA=(1+...+R^n)B_0A&=(1+...+R^n)(1-R)=1-R^{n+1}& \end{align} $$

sunxd
  • 121

2 Answers2

5

The link you gave appears to be broken. In any case, hopefully your book should prove or at least quote the idea behind (that you are asking in Q2), which is the Neumann series. So maybe you need to check the preceding pages. Once that is clear, you just need an “approximate inverse of $A$”, that is any $B_0$ such that $R:=I-B_0A $ has operator norm or at least spectral radius less than $1$. Then $I-R$ is invertible (therefore so are both $A$ and $B_0$, as $B_0A=I-R$) and $\sum_{k=0}^n R^k$ converges to $(I-R)^{-1}$, which is $(B_0A)^{-1}=A^{-1} B_0^{-1} $, so $B_n:= \big(\sum_{k=0}^n R^k\big)B_0$ converges to $(I-R)^{-1}B_0=A^{-1}$ and $B_nb$ converges to $x=A^{-1}b.$

Pietro Majer
  • 275
3

The equation defines $x_{n+1}$. You want to read it as $x_{n+1} = x_n + B_0(b - Ax_n)$. The question is whether the sequence $x_n$ thus defined will converge to $x$ the solution of $Ax=b$.

  • $x_n$ is defined to be $B_nb$, so to make the definition consistent, $x_{n+1}=B_{n+1}b$ should hold? – sunxd Sep 05 '23 at 07:56
  • also, is there any way to show $x_{n+1}=x_n+B_0(b-Ax_n)$ converges to $A^{-1}b$? – sunxd Sep 05 '23 at 07:57