0

We choose the iterative method $$\vec{u}^{i+1} = Q\vec{u}^i + \vec{s}$$ with $\vec{u}^0 = 0$ to solve $A\vec{u} = \vec{f}$.

I want to proof that for $\vec{u}^i$ the following holds: $$ \vec{u}^i = (I - Q^i)A^{-1}\vec{f} $$ Under certain assumptions. Also, we can then determine $\vec{s}$.

I have tried to validate this equation, but to no luck. I think I'm missing an obvious identity.

Phoenix_10
  • 107
  • Your question does not make sense as long as you don't define $Q$ nor $Q^i$. –  Oct 26 '20 at 17:12

1 Answers1

1

To achieve your goal I believe that you first have to assume that the iterative method is consistent, i.e. that the true solution $\vec{u}$ is a fixed point of the iteration: $$ \vec{u} = Q \vec{u} + \vec{s}, $$ or equivalently $$ \vec{s} = (I - Q) \vec{u} = (I - Q) A^{-1} \vec{f}, $$ which provides an expression for $\vec{s}$ as requested.

Now, given $\vec{u}^0 = 0$ it follows that \begin{align*} \vec{u}^1 &= \vec{s}, \\ \vec{u}^2 &= (I + Q) \vec{s}, \\ \vec{u}^3 &= (I + Q + Q^2) \vec{s}, \\ \vdots \\ \vec{u}^i &= \left ( \sum_{j=0}^{i-1} Q^j \right) \vec{s}. \\ \end{align*} At this point it will be necessary to assume that $Q$ satisfies $\rho(Q) < 1$, where $\rho(Q)$ denotes the spectral radius of $Q$. If so, then the above sum can be expressed as $(I-Q^i)(I-Q)^{-1}$ and we have $$ \vec{u}^i = (I-Q^i)(I-Q)^{-1} \vec{s} = (I-Q^i) A^{-1} \vec{f} $$ as desired.

Note that the two assumptions (consistency and spectral radius smaller than one) are necessary and sufficient conditions for the method to be convergent.

ekkilop
  • 2,278