next up previous [pdf]

Next: Preconditioner with a starting Up: Preconditioning Previous: Preconditioning

PRECONDITIONED DATA FITTING

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:

$\displaystyle \bold m \quad =\quad \bold S \bold p$ (3)

where $ \bold m$ is the map we seek, columns of the matrix $ \bold S$ are ``shapes'' 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 see later that invert-ability is helpful. Inserting the trial solution $ \bold m = \bold S\bold p$ into $ \bold 0\approx\bold F\bold m -\bold d$ gives:
$\displaystyle \bold 0 \quad$ $\displaystyle \approx$ $\displaystyle \quad \bold F \bold m  - \bold d$ (4)
$\displaystyle \bold 0 \quad$ $\displaystyle \approx$ $\displaystyle \quad \bold F \bold S \bold p  - \bold d$ (5)

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\T$ , we have iterative application of $ \bold F \bold S$ and $ \bold S\T\bold F\T$ .

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 tall rectangular matrix reduces the number of adjustable parameters, changes the solution, gets it quicker, but lowers resolution.



Subsections
next up previous [pdf]

Next: Preconditioner with a starting Up: Preconditioning Previous: Preconditioning

2015-05-07