next up previous print clean
Next: Preconditioner with a starting Up: Preconditioning Previous: Preconditioning


Iterative methods (like conjugate-directions) can sometimes be accelerated by a change of variables. The simplest change of variable is called a ``trial solution''. Formally, we write the solution as
\bold m \quad =\quad\bold S \bold p\end{displaymath} (1)
where $\bold m$ is the map we seek, columns of the matrix $\bold S$ are ``shapes'' that we like, and coefficients in $\bold p$ are unknown coefficients to select amounts of the favored shapes. The variables $\bold p$ are often called the ``preconditioned variables''. It is not necessary that $\bold S$ be an invertible matrix, but we'll see later that invertibility is helpful. Take this trial solution and insert it into a typical fitting goal
\bold 0 \quad\approx\quad \bold F \bold m \ -\ \bold d\end{displaymath} (2)
and get
\bold 0 \quad\approx\quad \bold F \bold S \bold p \ -\ \bold d\end{displaymath} (3)
We pass the operator $\bold F \bold S$ to our iterative solver. After finding the best fitting $\bold p$,we merely evaluate $ \bold m = \bold S \bold p$to get the solution to the original problem.

We hope this change of variables has saved effort. For each iteration, there is a little more work: Instead of the iterative application of $\bold F$ and $\bold F'$we have iterative application of $\bold F \bold S$ and $\bold S'\bold F'$.Our hope is that the number of iterations decreases because we are clever, or because we have been lucky in our choice of $\bold S$.Hopefully, the extra work of the preconditioner operator $\bold S$is not large compared to $\bold F$.If we should be so lucky that $\bold S= \bold F^{-1}$,then we get the solution immediately. Obviously we would try any guess with $\bold S\approx \bold F^{-1}$.Where I have known such $\bold S$ matrices, I have often found that convergence is accelerated, but not by much. Sometimes it is worth using $\bold F \bold S$ for a while in the beginning, but later it is cheaper and faster to use only $\bold F$.A practitioner might regard the guess of $\bold S$as prior information, like the guess of the initial model $\bold m_0$.

For a square matrix $\bold S$,the use of a preconditioner should not change the ultimate solution. Taking $\bold S$ to be a wide rectangular matrix, reduces the number of adjustable parameters, changes the solution, gets it quicker, but lower resolution.