Geometry & Linear Algebra
Lines in the plane and Least Squares Method - A Uniqueness Problem
|
Part I. Lines in the plane and Least Squares Solution - Glimpse on theory
A very compact form to express a system of linear equations
is to use matrix language adopted from Linear Algebra. We introduce the
coefficient matrix A = (aij)m×n, the column vector
b for the right side known numbers and the column x for the unknowns.
Then the system looks like
|
|
æ
ç
ç
ç
ç
ç
è
|
|
ö
÷
÷
÷
÷
÷
ø
|
|
æ
ç
ç
ç
ç
ç
è
|
|
ö
÷
÷
÷
÷
÷
ø
|
= |
æ
ç
ç
ç
ç
ç
è
|
|
ö
÷
÷
÷
÷
÷
ø
|
|
|
and briefly
If we have more equations than unknowns, we usually do not get any answer to the problem at all.
The same way, a general matrix equation Ax = b may not have solutions,
but also, often there are infinitely many solutions.
But if the matrix A Î Rm×n is of ''full rank'',
which means that all the columns of A are linearly independent (libre),
then the normal equation
has a unique solution
which is called the Least Squares Solution to the matrix equation Ax = b.
This solution of the normal equation is the unique vector x0, for which the residual
Ax - b has minimum norm ||Ax0 - b||.
Immediate application
Solve
Solution. There is no solution. However there might be some convenient answer.
Let A be the coefficient matrix.
Then the normal equation has the form
|
|
| | | |
| |
|
æ
ç
è
|
|
ö
÷
ø
|
|
æ
ç
ç
ç
è
|
|
ö
÷
÷
÷
ø
|
|
æ
ç
è
|
|
ö
÷
ø
|
|
| | |
| | | |
| | | |
|
|
|
The Least Squares solution to Ax = b is
|
|
æ
ç
è
|
|
ö
÷
ø
|
= |
æ
ç
ç
ç
ç
ç
è
|
|
ö
÷
÷
÷
÷
÷
ø
|
= |
æ
ç
è
|
|
ö
÷
ø
|
|
|
Unfortunately, it turns out that if we use a different representation of the lines, we get different solutions!
For example, if we take
we have exactly the same plane lines, but
the Least Squares solution would be
|
|
æ
ç
è
|
|
ö
÷
ø
|
= |
æ
ç
ç
ç
ç
ç
è
|
|
ö
÷
÷
÷
÷
÷
ø
|
= |
æ
ç
è
|
|
ö
÷
ø
|
|
|
The dynamical pictures (''sketches'') below allow us to experiment the problem in a visual way.
Part II. Lines in the plane and Least Squares Solution - Experiments
Now we shall do some experiments on overdetermined systems of two-unknown linear equations
and the Least Squares Method on finding a "compromise" solution.
We see very concretely that uniqueness problems raise when we try to combine linear algebra
tools and geometry.
The geometrical representations of the linear equations
ai1x1 + ai2x2 = bi
as lines in the plane. Remember that this could be written in Linear Algebra language as
matrix equation
Ax = b
where x is the vector of the unknowns xi.
1. Solutions for systems of three equations
|
|
In this Sketch you can make parallel moves for the lines by dragging with the computer mouse the
points
P1,
Q1 and
R1.
You can turn the lines around with the points
P2,
Q2 and
R2.
Also you can multiply the equations by numbers a, b tai c.
Try all the buttons in the Sketch.
The point x is the least squares solution of the equations on the screen.
Move the line P1P2 by moving the points P1 and P2.
Move the other lines too.
Reset when you want.
Problems
1. Explain why x0 is moving, though the lines do not move when you change a, b or c
(push Scale eqs first).
2. How is x0 moving when you vary a from -infinity to +infinity?
Answer the same question for b and c.
3. What is the curve described by x0 when P2 is describing a circle and all other given points
are fixed?
|
Puzzle 1
|
|
Puzzle 1 Problem
Try to find the least squares solution x0
of the system of the equations for the lines in the Sketch.
Give the coordinates of x0:
|
Puzzle 2
|
|
Puzzle 2 Problem
Try to find the least squares solution x0
of the system of the equations for the lines in the Sketch.
Give the coordinates of x0:
|
Puzzle 3
|
|
Puzzle 3 Problem
Try to find the least squares solution x0
of the system of the equations for the lines in the Sketch.
Give the coordinates of x0:
|
Puzzle 4
|
|
Puzzle 4 Problem
Here you can move one of the lines by dragging the points
P1 and
P2.
Try to find such equations for the first line so that
the Least Squares Solution x0 is the given black
point x0'.
Give your equations:
Are there many different solutions?
|
Puzzle 5
|
|
Puzzle 5 Problem
Here you can move two of the lines by dragging the points
P1, P2, Q1 and
Q2.
Try to find such positions for the lines that
the Least Squares Solution x0 is the given black
point x0'.
Are there many different solutions?
|
Puzzle 6
|
|
Puzzle 6 Problem
Here you can move all the lines.
Try to find such positions for the lines that
- the Least Squares Solution x0 is the given black
point x0' and
- turning lines does not make the solution move.
Are there many different solutions?
What can you say about this (or these) solutions?
|
3. Solutions for systems of four equations
|
|
In this Sketch you can make parallel moves for the lines by dragging with the computer mouse the
points
P1,
Q1,
R1 and
S1.
You can turn the lines around with the points
P2,
Q2,
R2 and
S2
Also you can multiply the equations by numbers a, b, c and d.
Try all the buttons in the Sketch.
Problem
Describe all possible positions of x0 for the 4 given lines
when a, b, c and d belong to R3.
|
III Normalizing the Least Squares Solution of lines
1. Description of the problem
Let
a1, b1, c1, k1,
a2, b2, c2, k2,
a3, b3, c3, k3,
be real numbers such that
|
a12 + b12 = a22 + b22 = a32 + b32 = 1. |
|
We call d1, d2 and d3 the straight lines of equations
Note that in the Java Sketches the scaling numbers k1, k2 and k3 are denoted by a, b and c.
The lines form a triangle of vertices S1 = d2Çd3, S2 = d3Çd1 and S3 = d1Çd2,
see Figure 1.
We define
|
x = |
æ
ç
è
|
|
ö
÷
ø
|
, c = |
æ
ç
ç
ç
è
|
|
ö
÷
÷
÷
ø
|
, A = |
æ
ç
ç
ç
è
|
|
ö
÷
÷
÷
ø
|
|
|
The matrix equation Ax = C has in general no solution. The least squares solution
x0
of the normal equation
is such that
|
F(x) = F(x1,x2) = ||A x - c||2 = (xT AT - cT)(Ax - c) |
|
is minimum for x = x0.
We denote by d(x,L) the distance from the point x to line L.
If one computes F(x) one gets:
|
F(x) = k12 (d(x,d1))2+k22 (d(x,d2))2+k32 (d(x,d3))2 |
|
I Case k1 = k2 = k3
The function to be minimized is
|
F(x) = (d(x,d1))2+(d(x,d2))2+(d(x,d3))2 |
|
Let us call l1 = S2 S3, l2 = S3 S1 and l3 = S1 S2,
the lengths of the sides of the triangle defined by the lines d1, d2 and d3.
The point x0 such that F(x) is minimum for x = x0
is the barycenter of S1, S2 and S3 with masses l12, l22 and l32:
|
x0 = |
l12
l12+l22+l32
|
S1+ |
l22
l12+l22+l32
|
S2+ |
l32
l12+l22+l32
|
S3 |
|
Problems
1.
If the triangle defined by the lines d1, d2 and d3 is isosceles (let us say S1 S2 = S1 S3),
on what line do you expect to find x0 (see Figure 2) ?
|
|
Figure 2: Isosceles triangle
|
2.
If the triangle is equilateral where is x0?
3.
The distances of x0 to the sides of the triangle are proportional to the lengths of the
corresponding sides to a certain power r:
|
|
d(x0,d1)
l1r
|
= |
d(x0,d2)
l2r
|
= |
d(x0,d3)
l3r
|
|
|
Guess what is the value of r?
Note: If r = -1, the point x0 would be the center of gravity;
if r = 0, the point x0 would be the center of the inner circle.
4.
If the triangle is rectangular, e.g. d2 ^d3, on what line do you find x0
(see Figure 3) ?
|
|
Figure 3: Rectangular triangle
|
|
|
H K2
S1 S3
|
= |
H K3
S2 S1
|
since the triangles are similar |
|
IV Geometrical construction of LSQ-solution for three lines
1. Step by step construction from the point A
|
|
You can move the lines by dragging the intersections A, B and C.
With the Sketch control button you can see step by step:
- the point C1 and the line parallel to line CA at distance |AC|
- the point B1 and the line parallel to line AB at distance |AB|
- the intersecting point O1 and the line joining it to A
|
2. stage of the construction: from the point B
|
|
You can move the lines by dragging the intersections A, B and C.
With the Sketch control button you can show and hide the three steps:
- the point A2 and the line parallel to line AB at distance |AB|
- the point C2 and the line parallel to line BC at distance |BC|
- the intersecting point O2 and the line joining it to B
|
3. stage of the construction: from the point C
|
|
You can move the lines by dragging the intersections A, B and C.
With the Sketch control button you can show and hide the three steps:
- the point A3 and the line parallel to line CA at distance |CA|
- the point B3 and the line parallel to line BC at distance |BC|
- the intersecting point O3 and the line joining it to C
|
4. All constructions from A, B and C
|
|
You can move the lines by dragging the intersections A, B and C.
Here you can see the intersection of the first two lines and
then check whether also the third will fit.
|
Symmedian
|
|
You can move the lines by dragging the intersections A, B and C.
Problems
The intersection of BC with Ax0 (or AO1)
is denoted by P.
1. Show that b2 PB = c2 PC,
where b = CA and c = AB.
2. Show that AP is a symmedian of the triangle ABC, that is the image of the median
in the reflection along the inner bisector shown on the picture.
3. Are the three symmedians of a triangle concurrent?
|
Martti.Pesonen@Joensuu.Fi 2003
