PRECONDITIONING THE REGULARIZATION

The basic formulation of a geophysical estimation problem consists of setting up two goals, one for data fitting, and the other for model shaping. With two goals, preconditioning is somewhat different. The two goals may be written as:

$$\begin{eqnarray} \bold 0 &\approx& \bold F \bold m - \bold d \\ \bold 0 &\approx& \bold A \bold m\end{eqnarray}$$ (4) (5)

which defines two residuals, a so-called ``data residual'' and a ``model residual'' that are usually minimized by conjugate-gradient, least-squares methods.

To fix ideas, let us examine a toy example. The data and the first three rows of the matrix below are random numbers truncated to integers. The model roughening operator $\bold A$is a first differencing operator times 100.

d(m)     F(m,n)                                            iter  Norm
---     ------------------------------------------------   ---- -----------
 41.    -55. -90. -24. -13. -73.  61. -27. -19.  23. -55.     1 20.00396538
 33.      8. -86.  72.  87. -41.  -3. -29.  29. -66.  50.     2 12.14780140
-58.     84. -49.  80.  44. -52. -51.   8.  86.  77.  50.     3  8.94393635
  0.    100.   0.   0.   0.   0.   0.   0.   0.   0.   0.     4  6.04517126
  0.   -100. 100.   0.   0.   0.   0.   0.   0.   0.   0.     5  2.64737511
  0.      0.-100. 100.   0.   0.   0.   0.   0.   0.   0.     6  0.79238468
  0.      0.   0.-100. 100.   0.   0.   0.   0.   0.   0.     7  0.46083349
  0.      0.   0.   0.-100. 100.   0.   0.   0.   0.   0.     8  0.08301232
  0.      0.   0.   0.   0.-100. 100.   0.   0.   0.   0.     9  0.00542009
  0.      0.   0.   0.   0.   0.-100. 100.   0.   0.   0.    10  0.00000565
  0.      0.   0.   0.   0.   0.   0.-100. 100.   0.   0.    11  0.00000026
  0.      0.   0.   0.   0.   0.   0.   0.-100. 100.   0.    12  0.00000012
  0.      0.   0.   0.   0.   0.   0.   0.   0.-100. 100.    13  0.00000000

Notice at the tenth iteration, the residual suddenly plunges 4 significant digits. Since there are ten unknowns and the matrix is obviously full-rank, conjugate-gradient theory tells us to expect the exact solution at the tenth iteration. This is the first miracle of conjugate gradients. (The residual actually does not drop to zero. What is printed in the Norm column is the square root of the sum of the squares of the residual components at the iter-th iteration minus that at the last interation.)

 

• The second miracle of conjugate gradients
• Importance of scaling
• Statistical interpretation
• The preconditioned solver