the Least- Squares method
Introduction
This article describes an application of linear algebra,
to calculate the best fitting polynomial through a set of points.
Graphics-Explorer uses this method.
Look at the picture right:
you see the points (x
1
,y
1
)....(x
5
,y
5
).
Requested is the best fitting polynomial degree 2,
through these points.
"Best fitting" means in this case : the sum of the squares
of the deviations must be minimal.
Dotted lines show the deviations in the picture right.
the Least Squares method
Given are the points
(x
1
,y
1
) , (x
2
,y
2
)...(x
n
, y
n
)
Requested:
a polynomial, degree m,
y = c
0
+ c
1
x + c
2
x
2
+ ... + c
m
x
m
through these points with minimal deviations.
If the polynomial exactly crosses all points, if m+1 = n, than:
y
1
= c
0
+ c
1
x
1
+ c
2
x
1
2
+ ... + c
m
x
1
m
y
2
= c
0
+ c
1
x
2
+ c
2
x
2
2
+ ... + c
m
x
2
m
.............
.............
y
n
= c
0
+ c
1
x
n
+ c
2
x
n
2
+ ... + c
m
x
n
m
written as matrix:
y
1
y
2
...
...
y
n
=
1
x
1
1
x
1
2
...
x
1
m
1
x
2
1
x
2
2
...
x
2
m
..
..
..
..
..
..
..
..
..
..
1
x
n
1
x
n
2
...
x
n
m
c
0
c
1
..
..
c
m
or shorter:
y
= M .
c
If the polynomial does not exactly cross the points, there will be a difference vector:
y
- M .
c
The norm of this difference vector is the sum of all squared deviations.
So we look for the values of
c
, making ||
y
- M .
c
|| minimal.
This will be the case if the difference vector is perpendicular to the column space of M.
The inner product equals zero in this case.
(M
c
)
t
(
y
- M
c
) = 0
(
c
t
M
t
) (
y
- M
c
= 0
c
t
( M
t
(
y
- M
c
)) = 0
c
t
( M
t
y
- M
t
M
c
) = 0
so:
M
t
y
- M
t
M
c
= 0
c
= (M
t
M)
-1
M
t
y
Remarks
1.
M
t
means the matrix M, reflected in the main diagonal.
If
M =
2
0
3
1
5
8
than
M
t
=
2
1
0
5
3
8
2.
rule:
( A B)
t
= B
t
A
t
3.
The inner product of two vectors
a
and
b
may be written as
a
t
.
b
Example
Find the least-squares line through
points (0,1) (1,3) (2,4) en (3,4)
M
=
1
0
1
1
1
2
1
3
M
t
=
1
1
1
1
0
1
2
3
M
t
M =
4
6
6
14
(M
t
M)
−1
= 0 . 1
7
−3
−3
2
c = 0 .
1
7
−3
−3
2
1
1
1
1
0
1
2
3
1
3
4
4
=
1.5
1
The line therefore is y = 1.5 + x
OneStat
The line therefore is y = 1.5 + x