previous up next print clean
Next: HOUSEHOLDER TRANSFORMATIONS AND GOLUB'S Up: Data modeling by least Previous: WEIGHTS AND CONSTRAINTS

FEWER EQUATIONS THAN UNKNOWNS

What is one to do when one has fewer equations than unknowns: give up? Certainly not, just apply the principle of simplicity. Let us find the simplest solution which satisfies all the equations. This situation often arises. Suppose, after having made a finite number of measurements one is trying to determine a continuous function, for example, the mass density $\rho (r)$ as a function of depth in the earth. Then, in a computer $\rho (r)$ would be represented by $\rho (r)$ sampled at N depths $r_i, i = 1, \, 2, \, \ldots, \, N.$Then merely taking N large, one has more unknowns than equations.

One measure of simplicity is that the unknown function xi has minimum wiggliness. In other words minimize  
 \begin{displaymath}
E \eq \sum (x_i - x_{i-1})^2\end{displaymath} (42)

subject to satisfying exactly the observation or constraint equations  
 \begin{displaymath}
{\bf Gx} \eq {\bf 0}\end{displaymath} (43)

Another more popular measure of simplicity (which does not imply an ordering of the variables xi) is the minimization of  
 \begin{displaymath}
E \eq \sum^n_{i=1} {x_i}^2\end{displaymath} (44)

If we set out to minimize (44) without any constraints, x would satisfy the simultaneous equations

\begin{displaymath}
\left[
 \begin{array}
{llll}
 1 & & \multicolumn{2}{r}{\hbox...
 ...ft[
\begin{array}
{c}
 v \\  0 \\  0 \\  0 \end{array} \right] \end{displaymath} (45)

By inspection one sees the obvious result that xi = 0. Now let us include two constraint equations and, for definiteness, take three unknowns. The method of the previous section gives  
 \begin{displaymath}
\left[
 \begin{array}
{cccc}
 1 & & & \\  & 1 & & \\  & & 1 ...
 ...array}
{c}
 v \\  0 \\  0 \\  0 \\  0 \\  0 \end{array} \right]\end{displaymath} (46)

Equation (46) has a size equal to the number of variables plus the number of constraints. It may be solved numerically or it may be reduced to a matrix whose size is given by the number of constraints. Let us split up (46) into two equations:  
 \begin{displaymath}
\left[
 \begin{array}
{l}
 x_1 \\  x_2 \\  x_3 \end{array} \...
 ...eq \left[
 \begin{array}
{c}
 0 \\  0 \\  0 \end{array} \right]\end{displaymath} (47)
and  
 \begin{displaymath}
\qquad \left[
 \begin{array}
{lll}
 g_{11} & g_{12} & g_{13}...
 ...
\eq \left[
 \begin{array}
{c}
 d_1 \\  d_2 \end{array} \right]\end{displaymath} (48)

We abbreviate these equations by ${\bf x} + {\bf G}^T\lambda = {\bf 0}$and ${\bf Gx = d}$,Premultiply (47) by G,

\begin{displaymath}
\quad \quad {\bf Gx} + {\bf GG}^T{\bf \lambda} \eq {\bf 0} \end{displaymath}

insert (48)

\begin{displaymath}
\quad \quad {\bf d} \phantom{G} + {\bf GG}^T{\bf \lambda} \eq {\bf 0} \end{displaymath}

solve for ${\bf \lambda}$

\begin{displaymath}
\quad \quad {\bf \lambda} \eq -( {\bf GG}^T)^{-1} {\bf d} \end{displaymath}

put back into (47)

\begin{displaymath}
\quad \quad {\bf x} \eq {\bf G}^T ({\bf GG}^T)^{-1} {\bf d} \end{displaymath}

Written out in full this is  
 \begin{displaymath}
\left[
\begin{array}
{c}
 x_1 \\  x_2 \\  x_3 \end{array} \r...
 ...1} 
 \; \left[ 
 \begin{array}
{c}
 {\bf d} \end{array} \right]\end{displaymath} (49)

This is the final result, a minimum wiggliness solution ${\bf x}$which exactly satisfies an underdetermined set called the constraint equations.

EXERCISES:

  1. If wiggliness is defined by (42) instead of (44), what form does (49) take?
  2. Given the mass and moment of inertia of the earth, calculate mass density as a function of depth utilizing the principle of minimum wiggliness (49). What criticism do you have of this procedure? (HINT: An elegant solution uses integrals instead of infinite sums.)
  3. Use the techniques of this section on (40) to reduce the size of the matrices to be inverted.


previous up next print clean
Next: HOUSEHOLDER TRANSFORMATIONS AND GOLUB'S Up: Data modeling by least Previous: WEIGHTS AND CONSTRAINTS
Stanford Exploration Project
10/30/1997