Preconditioning

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:

 (3)

where is the map we seek, columns of the matrix are shapes'' we like and coefficients in are unknown coefficients to select amounts of the favored shapes. The variables are often called the preconditioned variables.'' It is not necessary that be an invertible matrix, but we see later that invert-ability is helpful. Inserting the trial solution into gives:
 (4) (5)

We pass the operator to our iterative solver. After finding the best fitting , we merely evaluate 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 and , we have iterative application of and .

Our hope is that the number of iterations decreases, because we are clever or because we have been lucky in our choice of . Hopefully, the extra work of the preconditioner operator is not large compared to . If we should be so lucky that , then we get the solution immediately. Obviously we would try any guess with . Where I have known such matrices, I have often found that convergence is accelerated, but not by much. Sometimes, it is worth using for a while in the beginning; but later, it is cheaper and faster to use only . A practitioner might regard the guess of as prior information, like the guess of the initial model .

For a square matrix , the use of a preconditioner should not change the ultimate solution. Taking to be a tall rectangular matrix reduces the number of adjustable parameters, changes the solution, gets it quicker, but lowers resolution.

Subsections
 Preconditioning

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

2015-05-07