John Halleck's Introduction to Survey Adjustment:


Least Squares by Observations

[*** GROSSLY UNDER CONSTRUCTION ***]

[*** This page currently has severe notation problems. ***] Inverse of A is sometimes A' and sometimes \A. (Yech... multiple sources of text.)

Table of Contents

Adjustment of Original Observations

Setup for a Linearized solution

The very first thing to do for an adjustment is to tie down at least one point of the survey. This is to keep the problem from being "singular". An intuitive justification for this is that you don't know where a loop is if you don't know where at least one point is.

One has a "geometry" matrix that states which original survey points you measured to get the shots (shots are called observations in most of the Least Squares literature).

As an example to get the feel of the setup, let's consider the following trivial survey:

   Point A, assumed to be at the origin.    (We'll call this Shot 0 [S0])
   A Shot from point A to point B,          (We'll call this Shot 1 [S1])
   A shot from point B to point C,          (We'll call this Shot 2 [S2])
   And a shot from point C back to point A. (We'll call this shot 3 [S3])

   Each shot will also have a (three dimensional) uncertainty that determines
   how much we need to weight it.  A shot's weight will be called Wx if the
   shot is Sx.  (I.E.  Shot 2 [S2] has a weight called Weight 2 [W2])

   For each shot we have some Distance, Azimuth, and Inclination that
   has already been reduced to a change in X, Y, and Z.
   We'll call those numbers the shot.
   All of our setups will be as matrices...

   The labeled (partitioned) matrix form of this problem will be:
           A   B   C
    S0  [  1   0   0 ]   [ A's Location ]   [ S0 ]
    S1  [ -1   1   0 ] * [ B's Location ] = [ S1 ]
    S2  [  0  -1   1 ]   [ C's Location ]   [ S2 ]
    S3  [  1   0  -1 ]                      [ S3 ]

    This just says (in matrix notation) that you get S0 from A's location,
    you get S1 by subtracting A's location from B's location, and that
    you get S2 by subtracting B's location from C's location, and that
    you get S3 by subtracting C's location from A's.

    We also have a (block partitioned) weight matrix that looks like:

    [ W0   0   0   0 ]
    [  0  W1   0   0 ]  and is called the full weight matrix.
    [  0   0  W2   0 ]
    [  0   0   0  W3 ]

Let us call that geometry matrix "A", the actual survey point locations "p", the measurements we took "s"(the shots), and the weight matrix "W". We got the weight matrix from the inverse of the covariance matrix "V". The problem can now be stated:: Ap = s. This problem is usually what the math sorts call an "over determined" system. (This means it is usually not consistent.) The "best" way to deal with this has been worked on for years by the math folk, and makes use of the weights to more or less vote on the solution.

Geek note: In most survey publications dealing with least squares, the shot matrix is called "f" and the point matrix is called "d", and you would see this set up as Ad = f. I thought p and s would be clearer here.

This problem is traditional solved by surveyors using a technique called "Normal Equations". This method has the advantages of being clear and having the individual steps have an easily explained meaning. My examples will all be done with this technique, because of it's ease.

Geek note: Numerical analysists and other mathematitions are often shocked that normal equations would be used to solve this problem. Their method of choice would be Orthoginalization methods (Householder reflections or Given's rotations, or various block reflector methods.) I'll continue here with Normal Equation solutions, following the tradition since Gauss. I'll also cover Orthogonalization Methods in a separate section for those wanting the traditional numerical analysis types

Any good survey book on least squares techniques will give you long and drawn out derivation of the usual solution. This usual method is called a "least squares" solution by normal equations. Without going into any details at all, the least squares problem is given by A'WAp = A'Ws. (where A' means matrix transpose of A) And the solution is therefore

   p = inverse(A'WA)A'Wf

Geek note: Most simplified derivations assume either no weight matrix, or just a diagonal weight matrix. However there are derivations with a full weight matrix assumed. The form is still A'WAp=A'Ws for a full weight matrix. I'm pointing this out because when I make the leap to three dimensions the weight matrix becomes a block diagonal matrix with width three instead of just a diagonal matrix. If it really had to be diagonal that step would be invalid.

In (A'WA)p = (A'W)s The (A'WA) part is called the "normal equations" of the the problem (which I will often refer to as "N"). All that is needed to solve the problem is to take the inverse of the (A'WA) matrix and multiply both sides of the equation by that inverse.

If a survey has shots that are not connected to the main section, then we call that a "floating shot" *IF* the survey that produced the matrix is has no "floating" shots, and at least one point is tied down, then one now has a properly set up survey problem.

*WARNING* The least squares setup, when you have floating, shots produces a junk solution. Any program using adjustment by observations that doesn't analyze its data enough to find floating shots is doomed.

Geek note: Some general (non-survey) least squares books will point out that the normal equations are a lot more poorly conditioned (unstable) than the underlying problem matrix. Survey least squares books will generally recommend methods with normal equations. This might be confusing to some people. What is going on here is that the normal equations derived from a survey problem is a very stable positive definite matrix, and can almost always be solved easily.

Geek note: Note that the weight matrices are symmetric, so W is symmetric in any dimensions. A'WA is therefore symmetric. (X'YX is symmetric if Y is symmetric

What does this "mean"?

The final bottom line solution to the least squares problem, by normal equations, is (See above)

p = inverse(A'WA)A'Wf    Which is of the form:

p = Sf   Where S is a (rather ugly) matrix.

This means that the final points are explicitly a (linear) combination of the shots. A given row of the S matrix says, in effect: "Take x amount of shot n, add y amount of shot m, ... and the result is the location of the point."

The amount of a given shot may be all of it, or any part of it.

Symbolic Examples of Setup and solution

Almost everyone I know works better if there are some examples. However, I find most full blown Least Squares examples have massive matrices of numbers. I will give the examples symbolicly since I believe that that makes the structure of the problem stand out better.

We will have an origin for the survey given by "SO" (capital letter O), and some shots given by S1, S2, S3, and so on. Each shot will be measuring between actual points in the cave given by P1, P2, P2... The corresponding weights for the shots will be W1, W2, W3, and so on. (The weight for the one point we tied down will be given by WO.)

The A matrix will have a row for each shot, and a column for each actual point we were measuring (including any origin we introduced). The d matrix is a column with each element being one of the unknown survey points. The f matrix in a column with each element being what we observed for the shot.

Let us start with a survey that has only one shot (in addition to the point we tied down). This is a very degenerate example, but I think it helps to show what is really going on here.

Example

From       To       Data
*          P1        ... Some coordinates, lets call them SO
P1         P2        ... (Lets call it S1)

We will tie P0 down by just saying it is located at SO. in matrix form this is the dot product:

[ 1 0 ] [ P1 ]  = P1 + O = 0
        [ P2 ]

Note that the [omitted] data in the survey is the connection between P1 and P2. Looked at as a change between the points, the XYZ change is just P2 minus P1. In matrix form we do this by the Dot product of

[ -1 1 ] [ P1 ] = S1
         [ P2 ]
Which is
 -P1 +P2        = S1    (Or P2-P1 = S1)

As we form the problem matrix, each row has a 1 for the "to" point, and a -1 for the from point, and zeros everywhere else. This makes a matrix with MUCH more structure than the average Least Squares problem. A great many wonderful things can be done with the extra structure that this gives the matrices.

We have two points, so each row of the problem matrix will have two entries. We have two shots (counting tying a point down as a shot) so we will have two rows in the matrix.

The underlying problem is now: (I've taken the liberty of labeling the matrix)

                 A           p      =    s

                P1  P2       P           S
set origin   [   1   0  ] [ P1 ]    =  [ SO ]
shot 1       [  -1   1  ] [ P2 ]       [ S1 ]

This system is actually not over determined, and could be solved by traditional techniques. The solution is

[ P1 ] = [ 1 0 ] [ S0 ] = [ SO      ]
[ P2 ]   [ 1 1 ] [ S1 ]   [ SO + S1 ]

(Just premultiplying both sides by inverse(A))

That said, we will now hit this problem with the full normal equation form of the Least Squares technique, so that one can see what is going on.

The normal equations form of the weighted problem is:

(     A'        W         A     )   p     = (     A'        W     )    s

( [ 1  -1 ] [ WO  0 ] [  1  0 ] ) [ P1 ]  = ( [ 1  -1 ] [ WO  0 ] ) [ SO ]
( [ 0   1 ] [  0 W1 ] [ -1  1 ] ) [ P2 ]    ( [ 0   1 ] [  0 W1 ] ) [ S1 ]

  which reduces to:

[ WO+W1  -W1 ] [ P1 ]  = [ W0  -W1 ] [ S0 ]
[   -W1  +W1 ] [ P2 ]    [  0  +W1 ] [ S1 ]

which is properly labeled as:
        P1   P2     P         S1   S0     S
P1 [ WO+W1  -W1 ] [ P1 ]  = [ W0  -W1 ] [ S0 ]
P2 [   -W1  +W1 ] [ P2 ]    [  0   W1 ] [ S1 ]

The solution to this exercise can be found, and comes out to be:

Points = (Shot solution) *  Shots  = final points
( Inverse of the normal equations was: [ W0'  W0'     ] )
                                       [ W0'  W0'+W1' ]

[ P1 ] =         [ 1 0 ] *  [ SO ] = [ S0    ]
[ P2 ]           [ 1 1 ]    [ S1 ]   [ S0+S1 ]
(Note that all the weights canceled.)

[ 1 0 ] says that P1 is all of Shot 0 and none of Shot 1
[ 1 1 ] says that P2 is all of Shot 0 plus all of Shot 1

We have shown that weights can massively cancel. And, more importantly we have given an example of a much more general rule. In the absence of loops, the adjusted shot lengths of the survey are the original shot lengths.

Specificly, since a least squares adjustment is (in some sense) the "closest consistent system", if least squares is handed a consistent system the adjustment doesn't change anything.

Example to show a trivial loop

Now we can move on to a survey that actually needs adjustment. We'll start with our previous survey, and send in a crew that also surveys from point one to point two. The survey is

From to   data
*   P1    SO   # Tie down an origin for the survey.
P1  P2    S1
P1  P2    S2

We still have two points, so each row will still have two entries. We now have three shots (Counting tying down a point as a shot), so the problem matrix will have three rows.

The problem is:

(Matrix form)    A          p    =     s

Expanded form:
                P1  P2    Points     Shots
set origin   [   1   0  ] [ P1 ]     [ SO ]
shot 1       [  -1   1  ] [ P2 ]  =  [ S1 ]
shot 2       [  -1   1  ]            [ S2 ]

Geek note: If we didn't pin one point down, then the problem matrix would have only been

[ -1  1 ]  <= That matrix doesn't have an inverse, so that problem
[ -1  1 ]     really doesn't have a solution.

We are going to need A'W which is:

[  1  -1  -1 ] [ WO   0   0 ]  = [ W0  -W1  -W2 ]
[  0   1   1 ] [  0  W1   0 ]    [  0   W1   W2 ]
               [  0   0  W2 ]

The structure of this matrix should look very familiar in terms of the actual survey. (If not, compare it to the transpose of the "A" matrix.)

Now all we have to do to solve the least squares problem is to premultiply both sides of the matrix equation by A'W:

[ W0 -W1 -W2 ] [  1  0 ] [ P1 ] = [ W0  -W1  -W2 ] [ SO ]
[  0  W1  W2 ] [ -1  1 ] [ P2 ]   [  0   W1   W2 ] [ S1 ]
               [ -1  1 ]                           [ S2 ]

Which multiplies out to:

[ WO+W1+W2  -W1-W2 ] [ P1 ] = [ WO  -W1  -W2 ] [ SO ]
[   -W1-W2   W1+W2 ] [ P2 ]   [  0   W1   W2 ] [ S1 ]
                                               [ S2 ]

The structure of the right hand side should look familiar in terms of A'W. (Hint: compare it to the transpose of matrix A) The structure of the Normal Equations on the left hand size is more subtle, and it is more obvious if we put the labels back on the matrix

         P1       P2
P1 [  WO+W1+W2  -W1-W2 ]
P2 [    -W1-W2   W1+W2 ]

LeRoy Eide, and most probably others, proved that the diagonal for the survey problem (at position Px,Px) is the sum of all the weights of the shots that include point x, plus the weight of the conditions that tie the point down, if any. Any off diagonal element at Px,Py is the negative of the sum of the weights of all the shots that connect points x and y. (This is not a hard fact to prove.)

Geek Note: Proof hint: Consider the outer product form of this matrix multiply instead of the usual inner product form. Note that each row has at most 2 non-zero entries.

Geek Note: Since the weight matrix has to be symmetrical, and the normal equations are the result of the form A'WA, the normal equations have to be symmetrical. The matrix is also positive definite, assuming the weights are. [ And they had better be... ]

The solution to the problem is now

Points =  (Solution in terms of shots) * Shots       = final solution as points
       =  (Inverse of normal equations * A') * shots = final solution as points

The inverse of the normal equations is:
[  W0'   W0'          ]
[  W0'   W0'+(W1+W2)' ]

(Using \A to mean Inverse of A)

[ P1 ] = [ W0'  W0'           ]  [ W0  -W1  -W2 ] [ SO ]
[ P2 ]   [ W0'  W0'+ (W1+W2)' ]  [  0   W1   W2 ] [ S1 ]
                                                  [ S3 ]
=
[ P1 ] = [ W0'W0  -W0'W1+W0'W1             -W0'W2+W0'W2            ] [ SO ]
[ P2 ]   [ W0'W0  -W0'W1+(W0'+(W1+W2)')W1  -W0'W2+(W0'+(W1+W2)')W2 ] [ S1 ]
                                                                     [ S3 ]
=
[ P1 ] = [ 1        0           0     ] [ SO ]
[ P2 ]   [ 1   (W1+W2)'W1  (W1+W2)'W2 ] [ S1 ]
                                        [ S3 ]

Observe that the elements in the solution matrix are just a distribution by weights, and the final results are just a weighted average. Shot SO didn't appear in a loop, and so it just has weight 1. Only shots in a loop had final weights that were not zero and not one.

Observe that the corrected points are just what you would get adding up the corrected shots to that point by any route.

The output of a least squares adjustment is the nearest consistent survey to the one given, where a survey is called consistent if any path you now take to a point in the survey gives the same result.

Example to show connectivity issues

Ok, Let's try a bigger (but still simple) example.

From To    Data
*    P1    SO  # Origin.                Shot zero
P1   P2    S1  # Simple traverse        Shot one
P2   P3    S2                           Shot two
P3   P4    S3                           Shot three
P3   P2    S4  # A single shot redone.  Shot four

We now have four points, so our rows will have four entries. We now have 5 shots (Counting tying down a point as a shot), so the matrix will have five rows.

Our problem is now:

(Matrix form)    A                p     =    s
Expanded form:
               P1  P2  P3  P4   Points     Shots
set origin   [  1   0   0   0 ] [ P1 ]     [ SO ]
shot 1       [ -1   1   0   0 ] [ P2 ]  =  [ S1 ]
shot 2       [  0  -1   1   0 ] [ P3 ]     [ S2 ]
shot 3       [  0   0  -1   1 ] [ P4 ]     [ S3 ]
shot 4       [  0   1  -1   0 ]            [ S4 ]

Note that shot four is in the reverse direction of shot two, so the signs on the numbers are reversed. But it is still the exact same pattern, since the "to" position has a 1, and the "from" position has a -1, and the other positions have zeros.

The Least Squares solution is now found by multiplying both sides by A'W, giving A'WAd = A'Wf, which is (Arranged for readability):

A'W is just:
[ 1 -1  0  0  0 ]   [ WO  0  0  0  0 ]   [ W0 -W1   0   0   0 ]
[ 0  1 -1  0  1 ] * [  0 W1  0  0  0 ] = [  0 +W1 -W2   0  W4 ]
[ 0  0  1 -1 -1 ]   [  0  0 W2  0  0 ]   [  0   0  W2 -W3 -W4 ]
[ 0  0  0  1  0 ]   [  0  0  0 W3  0 ]   [  0   0   0 +W3   0 ]
                    [  0  0  0  0 W4 ]

So premultiplying both sizes by A'W gives:

[ WO+W1  -W1             0       0 ] [ P1 ]   [ W0  -W1    0    0    0 ] [ SO ]
[   -W1  +W1+W2+W4   -W2 -W4     0 ] [ P2 ] = [  0   W1  -W2    0   W4 ] [ S1 ]
[     0     -W2-W4  +W2+W3+W4  -W3 ] [ P3 ]   [  0    0   W2  -W3  -W4 ] [ S2 ]
[     0     0          -W3     +W3 ] [ P4 ]   [  0    0    0   W3    0 ] [ S3 ]
                                                                         [ S4 ]

When we solve this, we get:

Points =  (Solution in terms of shots)          * shots
Points =  (Inverse of normal equation * A' * W) * shots

Inverse of Normal equations:
[ W0'  W0'      W0'               W0'                  ]
[ W0'  W0'+W1'  W0'+W1'           W0'+W1'              ]
[ W0'  W0'+W1'  W0'+W1'+(W2+W4)'  W0'+W1'+(W2+W4)'     ]
[ W0'  W0'+W1'  W0'+W1'+(W2+W4)'  W0'+W1'+(W2+W4)'+W3' ]

(Using \A to mean Inverse of A)

[ P1 ]   [  1    0     0         0         0     ] [ SO ]
[ P2 ] = [  1    1     0         0         0     ] [ S1 ]
[ P3 ]   [  1    1   \(W2+W4)W2  0   -\(W2+W4)W4 ] [ S2 ]
[ P4 ]   [  1    1   \(W2+W4)W2  1   -\(W2+W4)W4 ] [ S3 ]
                                                   [ S4 ]
Which equals:
[P1]   [ SO                                     ]
[P2] = [ SO + S1                                ]
[P3]   [ SO + S1 + \(W2+W4)(W2*S2 - W4*S4)      ]
[P4]   [ SO + S1 + \(W2+W4)(W2*S2 - W4*S4) + S3 ]

Note that the solution is (once again) some regular sums, and some weighted sums. (Because the shot S4 is in the opposite direction of shot S2, it as a negative in the solution.)

What has happened here? All shots not involved in any sort of loop just reduced to themselves. This is a general rule. A smart program could pull off everything other than loops, reduce what's left, and put those shots back on.

The shots that were involved in loops became weighted averages of the shots in the loop. (With careful attention to signs.)

If we had combined shows 2 and 4 into a single shot of the appropriate weight, we would have had a much simpler adjustment. It is possible for an intelligent program to do this kind of processing in advance.

Example to show a basic loop

Ok, we've seen a degenerate loop, how about a real one?

From To  Data
*    P1  S0
P1   P2  S1
P2   P3  S2
P3   P1  S3

We now have three points, so our rows will have three entries. We now have 4 shots (Counting tying down a point as a shot), so the matrix will have 4 rows.

Our problem is now:

(Matrix form)    A            p    =     s

Expanded form:
               P1  P2  P3     Points     Shots
set origin   [  1   0   0 ]   [ P1 ]     [ SO ]
shot 1       [ -1   1   0 ] * [ P2 ]  =  [ S1 ]
shot 2       [  0  -1   1 ]   [ P3 ]     [ S2 ]
shot 3       [  1   0  -1 ]              [ S3 ]

Note that shot four is in the reverse direction of shot two, so the signs on the numbers are reversed. But it is still the exact same pattern, since the "to" position has a 1, and the "from" position has a -1, and the other positions have zeros.

The Least Squares solution is now found by multiplying both sides by A'W, giving A'WAd = A'Wf, which is (Arranged for readability):

A'W is just:
[ 1 -1  0  1 ]   [ WO  0  0   0 ]   [ W0 -W1   0 +W3 ]
[ 0  1 -1  0 ] * [  0 W1  0   0 ] = [  0 +W1 -W2   0 ]
[ 0  0  1 -1 ]   [  0  0 W2   0 ]   [  0   0  W2 -W3 ]
                 [  0  0  0  W3 ]

So premultiply of both sides gives (Rearranged to make structure obvious):
[ W0+W1+W3   -W1         -W3 ] [ P1 ] = [ W0  -W1    0   W3 ] [ S0 ]
[   -W1       W1+W2   -W2    ] [ P2 ]   [  0   W1  -W2    0 ] [ S1 ]
[      -W3      -W2   +W2+W3 ] [ P3 ]   [  0    0   W2  -W3 ] [ S2 ]
                                                              [ S3 ]

The solution is now just:

[ P1 ]   [ 1     0            0            0       ] [ S0 ]
[ P2 ] = [ 1  W1(W3+W2)/u  -W2*W3/u  -W3*W2/u      ] [ S1 ]
[ P3 ]   [ 1  W1*W2/u       W1*W2/u  -W3(W1+W2)/u  ] [ S2 ]
                                                     [ S3 ]
(Where "u" is: W1*W3 + W1*W2 + W3*W2 )

From point of view of point 2: There are two paths to point two. There is a direct path from 1 to 2, and there is a path from 1 to 3 to 2. The indirect path is -S2-S3 (It is in the opposite direction of the 1-2 shot, so it is negative) and the weight for that indirect path is

V2+V3 = 1/(1/W2+1/W3) = 1/( (W2+W3)/(W2*W3) )
                      = W2*W3 / (W2+W3)
Lets call these SS and WS for the moment.

We should  expect the location of point 2 to be the weighted average
of these two routes.  That would be:

P2 = S0 + (W1*S1 + WS*WW)/(W1+WS)

which would expand out to be:
P2 = S0 + (W1*S1 + (W2*W3/(W2+W3))*(-S2-S3))/(W1 + W2*W3/(W2+W3))
=>
P2 = S0 + (W1*S1 - (W2*W3/(W2+W3))*(S2+S3))/(W1 + W2*W3/(W2+W3))

Which reduces to:
P2 = S0 +
   ((W1*S1*(W2+W3) - W2*W3(S2+S3))/(W2+W3)) / ((W1*(W2+W3)+ W2*W3)/(W2+W3))
and that reduces to
P2 = S0 +
   ((W1*S1*(W2+W3) - W2*W3(S2+S3))/(W2+W3) )*(S2+S3) / ((W1*(W2+W3)+ W2*W3)/(W2+W3))

P2 = S0 +
   (W1*S1*(W2+W3) - W2*W3(S2+S3)) / (W1(W2+W3)+W2*W3)

P2 = S0 +
   (W1*S1*(W2+W3) - W2*W3(S2+S3)) / (W1*W2+W1*W3+W2*W3)

(The denominator here should be familiar as the "u" in the matrix solution.)
P2 = S0 + (W1*S1*(W2+W3) - W2*W3(S2+S3)) / u
P2 = S0 + (W1*(W2+W3)*S1 - W2*W3*S2 - W2*W3*S3)) / u

So... P2 =

  1           * S0
+ W1(W2+W3)/u * S1
- W2*W3/u     * S2
- W2*W3       * S3

  Which is EXACTLY the solution given by the Least Squares solution.

From point of view of point 3: There is a direct path from 1 to 3 and there is a path from 1 to 2 to 3.

The same arguments as above give that weighting, and it also comes out EXACTLY the weighting of the least squares solution.

Notes:

The least squares solution is an appropriately weighed average of the shots on the routes that get to each point.

Paths to a point can always be collapsed to an appropriate virtual shot with the right values and weights. (There are programs that form the least squares solution by only such operations without ever explicitly forming the matrix.)

Example to show a basic network

Ok, now we send our surveyors out and get a few more shots.

(Matrix form)    A             p     =    s

Expanded form:
                P1  P2  P3     Points     Shots
set origin   [   1   0   0 ]   [ P1 ]     [ SO ]
shot 1       [  -1   1   0 ] * [ P2 ]  =  [ S1 ]
shot 2       [  -1   1   0 ]   [ P3 ]     [ S2 ]
shot 3       [  -1   0   1 ]              [ S3 ]
shot 4       [   0   1  -1 ]              [ S4 ]

(We have added a shot from point 1 to point 3, and from point 3 to point 2.)

A'W now becomes:

[  1 -1 -1 -1  0 ]   [ WO  0  0  0  0 ]   [  WO -W1 -W2 -W3   0 ]
[  0  1  1  0  1 ] * [  0 W1  0  0  0 ] = [   0  W1  W2   0  W4 ]
[  0  0  0  1 -1 ]   [  0  0 W2  0  0 ]   [   0   0   0  W3 -W4 ]
                     [  0  0  0 W3  0 ]
                     [  0  0  0  0 W4 ]

Premultiplying both sides by that now gives:

[ W0+W1+W2+W3    -W1-W2       -W3    ] [ P1 ]   [ WO -W1 -W2 -W3   0 ] [ SO ]
[   -W1-W2       +W1+W2+W4       -W4 ] [ P2 ] = [  0  W1  W2   0  W4 ] [ S1 ]
[         -W3          -W4    +W3+W4 ] [ P3 ]   [  0   0   0  W3 -W4 ] [ S2 ]
                                                                       [ S3 ]
                                                                       [ S4 ]

The structure obvious in the previous example should be even clearer here.

The Solution to the problem is now:

[*** Under construction, this answer hasn't been checked ***]
Points = (Solution in terms of shots)................................. * shots

[ P1 ]   [  1      0        0         0                     0          ] [ S0 ]
[ P2 ] = [  1   W1*w34/u  W2*w34/u  W3*W4/u               W4*W3/u      ] [ S1 ]
[ P3 ]   [  1   W1*W4/u   W2*W4/u   W3(w12+W4)/(u*w12)   -W4*(W1+W2)/u ] [ S2 ]
                                                                         [ S3 ]
Where u = (W1+W3)(W3+W4) + W3*W4                                         [ S4 ]
    w12 = (W1+W2)
    w34 = (W3+W4)

Side note... What is the meaning of u term that is showing up all over?

First lets consider the shot made up of shots 3 and 4 together. (Since there is nothing else attached except for the end points, we can consider this as one single shot with the right weight.)

In terms of variance this is just 1/(V3+V4). This is the weight that the collection of shots V3+V4 would have. If one is used to working in terms of weights, then the weight of the two shots together is going to be 1/(1/W3+1/W4) [I hate working in terms of weights] which is 1/(W4/(W3*W4)+W3/(W3*W4)) which is 1/((W4+W3)/(W3*W4)) which is the infamous W3*W4/(W3+W4).

We could consider S3+S4 to be a single shot (SS) with a single weight (WS), and see the structure of the solution a bit better.

One can now observe that the distance between P1 and P2 is the weighted average between all the unique ways of getting from one to the other. With S3 and S4 folded to SS, the survey now has three shots connecting P1 and P2, and the solution is the simple weighted sum.

(W1*S1 + W2*S2 + WS*SS) / (W1 + W2 + WS)

which expands out to:

(W1*S1 + W2*S2 + (W3*W4/(W3+W4))(S3+S4)) / ( W1 + W2 + W3*W4/(W3+W4))

Which simplifies to the usual flavor of solution

  ( (W3+W4)(W1*S1+W2*S2) + W3*W4(S3+S4) ) / ((W3+W4)(W1+W2)+W3*W4)

falls out of computer algebra programs but has no intuitive value for me.
But note that this is where the denominator of the solution came from.

Collapsing Traverses

In the previous examples, we saw how a traverse that has no non-trivial junctions behaved in the least squares solution as if it were a single shot with appropriate weighting.

If you take the view that the least squares adjustment is just a weighted average of all of the (unique, non-trivial, non-redundant) paths between two points, then it is easy to justify this.

Any path is going to either include all of the traverse, or it is going to include none of it. The data value for the traverse is just going to be the sum of data values [Be careful of signs if the there are shots in the traverse going in different directions]. The (co)variance of the combined traverse is just going to be the sums of the covariances of the shots that make it up. (If you really want to view things in terms of weights instead, then the weight of the traverse is going to be the inverse of the sum of the inverses of the weights of the traverse.)

If a collection of shots ties two points together, then the collection can always be replaced by a virtual shot of appropriate value and weight.

Distributing weights

If we tie down BOTH ends of a simple traverse we get an interesting result.

[... Example, showing shot oriented view ...]

Doesn't that look a lot like the chapter on distributing by weights?

[...]

The bottom line here is if a traverse has its end points tied down, the least squares final solution is going to be the same as a weighted distribution, if none of the internal points of the traverse are junction points.

Tradeoffs

It is hard to get a feel for the tradeoff's in which method to use, unless one has some actual numbers. The numbers depend on the caves themselves, but we can come up with some idea by comparing the numbers from an actual cave.

I will use the rough numbers for Little Brush Creek Cave in Utah, as they were some years ago. The cave had about 2500 survey shots, but there were only about 20 or so loops in the survey.

A least squares Adjustment by Observations is the most popular least squares method in cave survey programs. Such an adjustment would end up solving a matrix problem with a matrix about 2500 by 2500 with roughly 62500 elements in it. However the rows of the matrix averaged having only a little more than THREE non-zero elements in each row. In addition, the structure of the matrix make it ideal for matrix solution methods such as Givens rotations, or sparse Choleski Factorization.

A least squares Adjustment by Conditions for the same data would form a problem matrix only about 20 by 20. That matrix would have been mostly filled in.

Most people have an intuition that a setup that only deals with a 20 x 20 problem matrix is better than one that has to deal with a 2500 x 2500 problem matrix. Whether or not the larger (almost empty) matrix is "easier" to solve depends on which tools one has around.

Another factor that comes into play is that the techniques that produce the the smallest problem matrix, need to know the most about the geometry of the survey. Adjustment by conditions needs to know what shots form loops. Adjustment by observations only needs to know what surveys are "floating".


Go to ...


This page is http://www.cc.utah.edu/~nahaj/cave/survey/intro/leastsquares-observations.html
© Copyright 2000 by John Halleck, All Rights Reserved.
This snapshot was last modified on January 24th, 2001