next up previous
Next: 2.3.2 Jacobi Relaxation Up: 2.3 Iterative Methods Previous: 2.3 Iterative Methods


2.3.1 Iterative Improvement

Let $\mbox{$\bf x$}$ be the exact solution of $\mbox{${\bf A}$} \cdot \mbox{$\bf x$}=\mbox{$\bf b$}$,
and let $\mbox{$\bf x$}\,'$ be an inaccurate (or estimated) solution vector, such that $
\mbox{$\bf x$} \equiv \mbox{$\bf x$}\,' + \delta \, \mbox{$\bf x$}\, .
$

Inserting this into the given equation we find
$\displaystyle \mbox{${\bf A}$} \cdot \delta \, \mbox{$\bf x$}$ $\textstyle =$ $\displaystyle \mbox{$\bf b$} - \mbox{${\bf A}$} \cdot \mbox{$\bf x$}\,'
\, \equiv \, \mbox{$\bf c$}$  

which may be solved for $\delta \mbox{$\bf x$}$. (Use double precision!)




EXAMPLE:

\begin{displaymath}
\mbox{${\bf A}$}=
\mbox{$\left( \begin{array}{cc}1&2\\ \vspa...
...egin{array}{r} -3 \\ \vspace{-9 pt}\\ 4 \end{array} \right)$}
\end{displaymath}

From

\begin{displaymath}
\mbox{${\bf A}$} \cdot \delta \, \mbox{$\bf x$} = \mbox{$\le...
...egin{array}{r} -2 \\ \vspace{-9 pt}\\ -5 \end{array} \right)$}
\end{displaymath}

we find, using the decomposition

\begin{displaymath}
\mbox{${\bf L}$}= \mbox{$\left( \begin{array}{cc}1&0\\ \vspa...
...egin{array}{cc}1&2\\ \vspace{-9pt}\\ 0&-2\end{array} \right)$}
\end{displaymath}

the correction vector

\begin{displaymath}
\delta \, \mbox{$\bf x$}=
\left( \begin{array}{c}-1\\ -\frac...
...}=
\left( \begin{array}{c}-4\\ \frac{7}{2}\end{array} \right)
\end{displaymath}





Now interpret the improvement equation as an iterative formula:
$\displaystyle \mbox{${\bf A}$} \cdot \left( \mbox{$\bf x$}_{k+1}-\mbox{$\bf x$}_{k}\right)$ $\textstyle =$ $\displaystyle \mbox{$\bf b$}
-\mbox{${\bf A}$} \cdot \mbox{$\bf x$}_{k}$  

Replace $\mbox{${\bf A}$}$ on the left hand side by an easily invertible matrix $\mbox{${\bf B}$}$ close to $\mbox{${\bf A}$}$:
$\displaystyle \mbox{${\bf B}$} \cdot \left( \mbox{$\bf x$}_{k+1}-\mbox{$\bf x$}_{k}\right)$ $\textstyle =$ $\displaystyle \mbox{$\bf b$}
-\mbox{${\bf A}$} \cdot \mbox{$\bf x$}_{k}$  

or
$\displaystyle \mbox{$\bf x$}_{k+1}$ $\textstyle =$ $\displaystyle \mbox{${\bf B}$}^{-1} \cdot \mbox{$\bf b$} +\mbox{${\bf B}$}^{-1} \cdot
\left[ \mbox{${\bf B}$}-\mbox{${\bf A}$}\right] \cdot \mbox{$\bf x$}_{k}$  

This procedure converges to the solution of $\mbox{${\bf A}$} \cdot \mbox{$\bf x$}=\mbox{$\bf b$}$ if $\vert\mbox{$\bf x$}_{k+1}-\mbox{$\bf x$}_{k}\vert$ $<\vert\mbox{$\bf x$}_{k}-\mbox{$\bf x$}_{k-1}\vert$. This is the case if all eigenvalues of the matrix $
\mbox{${\bf B}$}^{-1}\cdot\left[ \mbox{${\bf B}$}-\mbox{${\bf A}$}\right]
$ are situated within the unit circle.


next up previous
Next: 2.3.2 Jacobi Relaxation Up: 2.3 Iterative Methods Previous: 2.3 Iterative Methods
Franz J. Vesely Oct 2005
See also:
"Computational Physics - An Introduction," Kluwer-Plenum 2001