Lesson Note On Solving the least squares problem

Solving the least squares problemEdit

The minimum of the sum of squares is found by setting the gradient to zero. 

Since the model contains m parameters, there are m gradient equations:

${\displaystyle {\frac {\partial S}{\partial \beta _{j}}}=2\sum _{i}r_{i}{\frac {\partial r_{i}}{\partial \beta _{j}}}=0,\ j=1,\ldots ,m,}$

and since ${\displaystyle r_{i}=y_{i}-f(x_{i},{\boldsymbol {\beta }})}$, the gradient equations become

${\displaystyle -2\sum _{i}r_{i}{\frac {\partial f(x_{i},{\boldsymbol {\beta }})}{\partial \beta _{j}}}=0,\ j=1,\ldots ,m.}$

The gradient equations apply to all least squares problems. 

Each particular problem requires particular expressions for the model and 

its partial derivatives.

Linear least squaresEdit

A regression model is a linear one when the model comprises a linear combination 

of the parameters, i.e.,

${\displaystyle f(x,\beta )=\sum _{j=1}^{m}\beta _{j}\phi _{j}(x),}$

where the function ${\displaystyle \phi _{j}}$ is a function of ${\displaystyle x}$.

Letting

${\displaystyle X_{ij}={\frac {\partial f(x_{i},{\boldsymbol {\beta }})}{\partial \beta _{j}}}=\phi _{j}(x_{i}),}$

we can then see that in that case the least square estimate (or estimator, 

in the context of a random sample), ${\displaystyle {\boldsymbol {\beta }}}$ is given by

${\displaystyle {\boldsymbol {\hat {\beta }}}=(X^{T}X)^{-1}X^{T}{\boldsymbol {y}}.}$

For a derivation of this estimate see Linear least squares (mathematics).

Non-linear least squaresEdit

There is, in some cases, a closed-form solution to a non-linear least squares problem – 

but in general there is not. In the case of no closed-form solution, numerical algorithms 

are used to find the value of the parameters ${\displaystyle \beta }$ that minimizes the objective. 

Most algorithms involve choosing initial values for the parameters. Then, 

the parameters are refined iteratively, that is, the values are obtained by successive 

approximation:

${\displaystyle {\beta _{j}}^{k+1}={\beta _{j}}^{k}+\Delta \beta _{j},}$

where a superscript k is an iteration number, and the vector of increments ${\displaystyle \Delta \beta _{j}}$ 

is called the shift vector. In some commonly used algorithms, at each iteration the 

model may be linearized by approximation to a first-order Taylor series expansion

 about ${\displaystyle {\boldsymbol {\beta }}^{k}}$:

${\displaystyle {\begin{aligned}f(x_{i},{\boldsymbol {\beta }})&=f^{k}(x_{i},{\boldsymbol {\beta }})+\sum _{j}{\frac {\partial f(x_{i},{\boldsymbol {\beta }})}{\partial \beta _{j}}}\left(\beta _{j}-{\beta _{j}}^{k}\right)\\&=f^{k}(x_{i},{\boldsymbol {\beta }})+\sum _{j}J_{ij}\,\Delta \beta _{j}.\end{aligned}}}$

The Jacobian J is a function of constants, the independent variable and the parameters, 

so it changes from one iteration to the next. The residuals are given by

${\displaystyle r_{i}=y_{i}-f^{k}(x_{i},{\boldsymbol {\beta }})-\sum _{k=1}^{m}J_{ik}\,\Delta \beta _{k}=\Delta y_{i}-\sum _{j=1}^{m}J_{ij}\,\Delta \beta _{j}.}$

To minimize the sum of squares of ${\displaystyle r_{i}}$, the gradient equation is set to zero and solved for

 ${\displaystyle \Delta \beta _{j}}$:

${\displaystyle -2\sum _{i=1}^{n}J_{ij}\left(\Delta y_{i}-\sum _{k=1}^{m}J_{ik}\,\Delta \beta _{k}\right)=0,}$

which, on rearrangement, become m simultaneous linear equations, 

the normal equations:

${\displaystyle \sum _{i=1}^{n}\sum _{k=1}^{m}J_{ij}J_{ik}\,\Delta \beta _{k}=\sum _{i=1}^{n}J_{ij}\,\Delta y_{i}\qquad (j=1,\ldots ,m).}$

The normal equations are written in matrix notation as

${\displaystyle \mathbf {(J^{T}J)\,\Delta {\boldsymbol {\beta }}=J^{T}\,\Delta y} .\,}$

These are the defining equations of the Gauss–Newton algorithm.

Solving spherical triangles

Solving spherical triangles Edit The general spherical triangle is fully determined by three of its six characteristics (3 sides and 3 angles). Note that the sides a, b, c of a spherical triangle are measured by angular rather than linear units, based on the corresponding central angles. The solution of triangles for non-Euclidean spherical geometry has some differences from the planar case. For example, the sum of the three angles α + β + γ depends on the triangle. In addition, there are no unequal similar triangles, and so the problem of constructing a triangle with specified three angles has a unique solution. The basic relations used to solve a problem are similar to those of the planar case: see Law of cosines (spherical) and Law of sines (spherical). Among other relationships that may be useful are the half-side formula and Napier's analogies:[7] {\displaystyle \tan {\frac {c}{2}}\cos {\frac {\alpha -\beta }{2}}=\tan {\frac {a+b}{2}}\cos {\frac {\alpha +\beta }{2}}} {\displaystyle \tan {\frac {c}{2}}\sin {\frac {\alpha -\beta }{2}}=\tan {\frac {a-b}{2}}\sin {\frac {\alpha +\beta }{2}}} {\displaystyle \cot {\frac {\gamma }{2}}\cos {\frac {a-b}{2}}=\tan {\frac {\alpha +\beta }{2}}\cos {\frac {a+b}{2}}} {\displaystyle \cot {\frac {\gamma }{2}}\sin {\frac {a-b}{2}}=\tan {\frac {\alpha -\beta }{2}}\sin {\frac {a+b}{2}}.}  Three sides given Three sides given (spherical SSS) Edit Known: the sides a, b, c (in angular units). The triangle's angles are computed from the spherical law of cosines: {\displaystyle \alpha =\arccos \left({\frac {\cos a-\cos b\ \cos c}{\sin b\ \sin c}}\right),} {\displaystyle \beta =\arccos \left({\frac {\cos b-\cos c\ \cos a}{\sin c\ \sin a}}\right),} {\displaystyle \gamma =\arccos \left({\frac {\cos c-\cos a\ \cos b}{\sin a\ \sin b}}\right).}  Two sides and the included angle given Two sides and the included angle given (spherical SAS) Edit Known: the sides a, b and the angle γ between them. The side c can be found from the law of cosines: {\displaystyle c=\arccos \left(\cos a\cos b+\sin a\sin b\cos \gamma \right).} The angles α', β can be calculated as above, or by using Napier's analogies: {\displaystyle \alpha =\arctan \ {\frac {2\sin a}{\tan({\frac {\gamma }{2}})\sin(b+a)+\cot({\frac {\gamma }{2}})\sin(b-a)}},} {\displaystyle \beta =\arctan \ {\frac {2\sin b}{\tan({\frac {\gamma }{2}})\sin(a+b)+\cot({\frac {\gamma }{2}})\sin(a-b)}}.} This problem arises in the navigation problem of finding the great circle between two points on the earth specified by their latitude and longitude; in this application, it is important to use formulas which are not susceptible to round-off errors. For this purpose, the following formulas (which may be derived using vector algebra) can be used: {\displaystyle {\begin{aligned}c&=\arctan {\frac {\sqrt {(\sin a\cos b-\cos a\sin b\cos \gamma )^{2}+(\sin b\sin \gamma )^{2}}}{\cos a\cos b+\sin a\sin b\cos \gamma }},\\\alpha &=\arctan {\frac {\sin a\sin \gamma }{\sin b\cos a-\cos b\sin a\cos \gamma }},\\\beta &=\arctan {\frac {\sin b\sin \gamma }{\sin a\cos b-\cos a\sin b\cos \gamma }},\end{aligned}}} where the signs of the numerators and denominators in these expressions should be used to determine the quadrant of the arctangent.  Two sides and a non-included angle given Two sides and non-included angle given (spherical SSA) Edit This problem is not solvable in all cases; a solution is guaranteed to be unique only if the side length adjacent to the angle is shorter than the other side length. Known: the sides b, c and the angle β not between them. A solution exists if the following condition holds: {\displaystyle b>\arcsin(\sin c\,\sin \beta ).} The angle γ can be found from the spherical law of sines: {\displaystyle \gamma =\arcsin \left({\frac {\sin c\,\sin \beta }{\sin b}}\right).} As for the plane case, if b < c then there are two solutions: γ and 180° - γ. We can find other characteristics by using Napier's analogies: {\displaystyle a=2\arctan \left[\tan \left({\tfrac {1}{2}}(b-c)\right){\frac {\sin \left({\tfrac {1}{2}}(\beta +\gamma )\right)}{\sin \left({\tfrac {1}{2}}(\beta -\gamma )\right)}}\right],} {\displaystyle \alpha =2\operatorname {arccot} \left[\tan \left({\tfrac {1}{2}}(\beta -\gamma )\right){\frac {\sin \left({\tfrac {1}{2}}(b+c)\right)}{\sin \left({\tfrac {1}{2}}(b-c)\right)}}\right].}  One side and two adjacent angles given A side and two adjacent angles given (spherical ASA) Edit
Three angles given (spherical AAA)Edit

Known: the angles α, β, γ. From the law of cosines we infer:

{\displaystyle a=\arccos \left({\frac {\cos \alpha +\cos \beta \cos \gamma }{\sin \beta \sin \gamma }}\right),}{\displaystyle b=\arccos \left({\frac {\cos \beta +\cos \gamma \cos \alpha }{\sin \gamma \sin \alpha }}\right),}{\displaystyle c=\arccos \left({\frac {\cos \gamma +\cos \alpha \cos \beta }{\sin \alpha \sin \beta }}\right).}

Solving right-angled spherical trianglesEdit

The above algorithms become much simpler if one of the angles of a triangle (for example, the angle C) is the right angle. Such a spherical triangle is fully defined by its two elements, and the other three can be calculated usingNapier's Pentagon or the following relations.

{\displaystyle \sin a=\sin c\cdot \sin A} (from the Law of sines (spherical)){\displaystyle \tan a=\sin b\cdot \tan A}{\displaystyle \cos c=\cos a\cdot \cos b} (from the law of cosines (spherical)){\displaystyle \tan b=\tan c\cdot \cos A}{\displaystyle \cos A=\cos a\cdot \sin B} (also from the law of cosines){\displaystyle \cos c=\cot A\cdot \cot B}

Some applicationsEdit

TriangulationEdit

Distance measurement by triangulation

Main article: Triangulation

If one wants to measure the distance dfrom shore to a remote ship via triangulation, one marks on the shore two points with known distance lbetween them (the baseline). Let α, β be the angles between the baseline and the direction to the ship.

From the formulae above (ASA case) one can define the length of the triangle height:

{\displaystyle d={\frac {\sin \alpha \,\sin \beta }{\sin(\alpha +\beta )}}\,l={\frac {\tan \alpha \,\tan \beta }{\tan \alpha +\tan \beta }}\,l.}

This method is used in cabotage. The angles α, β are defined by observation of familiar landmarks from the ship.

How to measure a mountain's height

As another example, if one wants to measure the height h of a mountain or a high building, the angles α, β from two ground points to the top are specified. Let l be the distance between these points. From the same ASA case formulas we obtain:

{\displaystyle h={\frac {\sin \alpha \,\sin \beta }{\sin(\beta -\alpha )}}\,l={\frac {\tan \alpha \,\tan \beta }{\tan \beta -\tan \alpha }}\,l.}

The distance between two points on the globeEdit

Main article: Great-circle distance

To calculate the distance between two points on the globe,

Point A: latitude λ_A, longitude L_A, andPoint B: latitude λ_B, longitude L_B

we consider the spherical triangle ABC, where C is the North Pole. Some characteristics are:

{\displaystyle a=90^{\mathrm {o} }-\lambda _{\mathrm {B} },\,}{\displaystyle b=90^{\mathrm {o} }-\lambda _{\mathrm {A} },\,}{\displaystyle \gamma =L_{\mathrm {A} }-L_{\mathrm {B} }.\,}

If two sides and the included angle given, we obtain from the formulas

{\displaystyle \mathrm {AB} =R\arccos \left[\sin \lambda _{\mathrm {A} }\,\sin \lambda _{\mathrm {B} }+\cos \lambda _{\mathrm {A} }\,\cos \lambda _{\mathrm {B} }\,\cos \left(L_{\mathrm {A} }-L_{\mathrm {B} }\right)\right].}

Here R is the Earth's radius.

Lesson Note On Leica Total Station – Surveying from a Known Point

Leica Total Station – Surveying from a Known Point

When the total station is set up and level over the known point it will require another known point to help calculate the coordinate reference system that the unknown measurements will be measured with. That is to say that the total station will be able to know the angular relation between the easting, northing and elevation of itself and the Easting northing and elevation of the second known point (often referred to as the back sight). Then all of the angles and distances measurements calculated and computed with the laser will be translated into the same east, northing and elevation coordinate space as well.

Create a Measure Job File

From the main menu, select Meas job management by pressing the number 1 on the keypad (from the Main Menu).  The measure job created will be the file that your measured points in your survey will be recorded

.

Next press F2 to open the Create new job menu.

Leave all settings at default and enter a new job nameby using the letters on the keypad.

The F6 key (NUM) will switch the key pad between numbers and letters.  Note it may take some practice to get used to this switching back and forth.

After the new file name has been entered press F1 to continue.

Next ensure that the job file that you have just created is highlighted and select CONT again by selecting F1from the keypad.

Create a Data Job File

The data job is where the known or fixed points are stored (the Data job file can be the same as the measure job file but often it is good survey practise to keep these two files separate).

Steps followed for creating a data job file are very similar to those mentioned above for creating a measure job.

From the main menu, select data job management by pressing the number 2 on the keypad.

Next press F2 to open the Create new job menu (and provide a file name like you did above) or select an existing data job file if one exists. Then press F1 to continue.

If it is a new data job file then you will need to input values for the known points.

Select the FNC key from the bottom grey keypad.

Select menu item 5 Data view and Edit

On the next screen select Input from the function key options by pressing the F3 key.

Enter the name of the point id of the known point you wish to create.

Enter the known Easting, Northing and Elevation values for this point.

Press REC to accept the value of the point id

Repeat the steps to enter all the known points that you wish to use in your survey and then use the ESC key until you reach the main menu again.

Select your Codelist

From the main menu, select codelist management by pressing the number 3 on the keypad.

Select the name of the code list you created earlier with the Leica Survey Office software and uploaded to the memory card. Then press F1 to continue.

Record Backsight Locations

From the Main Menu select Setup from the bottom of the screen by pressing F5.

In the Job settings menu you should see the name of your measure job, data job, and code list. If either looks incorrect than go back and select them again using the instructions from the start of this manual.

Select QSET (quickset) from the bottom of the menu using F4.

For the Station Id enter the point id of the known point for the surveying monument that you have the total station set up upon.

Next enter the Backs. Id to select the backsight point id

Enter the instrument height of the total station that you recorded previously in the initial setup.

Enter the base height of the reflector poles used to collect the various points during the survey.  The number to enter here will be the value found above the grasp of the reflector pole. A height of 2 meters is common height for reflector poles in most surveys but sometimes there is a need to use different height values.

Aim the total station instrument towards the survey prism with the and press F2 on the key pad which selects DIST. Ensure that the range pole is vertical and plumb by centering the bubble on the pole. This will allow the Total Station to compute the delta of what you told it where it was and where it is based on the reading of shooting the pole.

Take note of the delta horizontal distance on the screen. Anything under 2cm is considered an acceptable value. Once accuracy under 2cm is achieved hit CONT by pressing F4 on the key pad.  The unit will now know spatially where it is located and surveying of the unknown points can commence.

The screen should now have an option MEAS appear in the lower right corner of the screen, this is an indication that you can now shoot to any unknown point with the reflector. Press the F6 function key to enter into the measure and Record menu. Here you can point and aim at the reflector, enter the point Id value and then press theF3 function key to record the coordinate values of that point. The total station will increment the point ids taken automatically, or you can change the values manually each time.

Tip: Remember to adjust the height of reflector on this screen if the height of the reflector unit is adjusted during the survey.

To finishing surveying simply press ESC until the screen is back to the main menu. Press both the ON button and the left arrow button at the same time to shut down the unit.

Tip: How to adjust the view of the Total Station
Use the “sight” on the total station to roughly point the Total station at the reflector.  Then use the knobs to fine tune the view at the reflector target.  Use the focus on the lens to ensure a clear and focused view of the target and that the cross hairs are centered on the center of the target.

SOLUTION ON PHOTOGRAMMETRY PROBLEMS PART 1

Examples

1) The scale of an aerial photograph is 1 cm = 100 m. The photograph size is 20cm x 20cm. Determine the number of photographs required to cover an area of 100 sq. km if the longitudinal lap is 60% and the side lap is 30%.

Solution.

Here                l = 20 cm  ;  w = 20 cm  ;  P₁ = 0.60 ; P_w = 0.30

                         

 The actual ground length covered by each photograph is

                        L = (1 – P_l) sl = (1- 0.6) 100 x 20 = 800 m = 0.8 km

Actual ground width covered by each photograph is

                        W = (1 – P_w) sw = (1 – 0.3) 100 x 20 = 1400 m = 1.4 km

 Net ground area covered by each photograph is

                        a = L x W = 0.8 x 1.4 = 1.12 sq. km

hence number of photographs required is

                       

2) The scale of an aerial photograph is 1cm = 100 m. The photograph size is 20cm x 20xm. Determine the number of photograph required to cover an area 10 km x 10km, if the longitudinal lap is 60% and the side lap is 30%.

Solution

Here                L₁ = 10 km  ; L₂ = 10 km

  Number of photographs in each strip is given by

           

Number of flight lines required is given by

           

Hence number of photographs required will be           

The spacing of the flight lines would be 10/9 = 1.11 km and not 1.4 as calculated theoretically in the previous example.