Thu Dec 2 23:37:22, 2010
Define a quadratic polynomial
> h := x -> 5*x^2 + 4*x + 3 :
and define three distinct points
> x1 := -2 : x2 := -1 : x3 := 1 :
Evaluate h() at these three points
> y1 := h(x1) = 15;
y2 := h(x2) = 4;
y3 := h(x3) = 12;
and let Qj := (xj, yj).
What is the 3-topped poly which is least-squares--closest
to data-points {Q1,Q2,Q3}? Why, it is h itself, since h is 3-topped.
## ================================================================ ##
Let's do the computation from the "Least Squares and matrices" pamphlet.
An abstract Vandermonde matrix looks like
> K := 3 : A := VandermondeMatrix(, 4,K);
[1 x1 x1^2]
[1 x2 x2^2]
A = [1 x3 x3^2]
[1 x4 x4^2]
In our case, we have N=3 points, with values -2,-1,1 for x1,x2,x3. Thus
> K := 3 : A := VandermondeMatrix(, 3,K); Q := <>;
[1 -2 4] [15]
A = [1 -1 1] , Q = [ 4]
[1 1 1] [12]
> adjointA := Tpose(A) : M := adjointA . A ; InvM := MI(M) :
Col := adjointA . Q ;
[ 3 -2 6] [ 31]
M := [-2 6 -8] , Col = [-22]
[ 6 -8 18] [ 76]
We now compute the coefficients of c0 + c1*x + c2*x^2,
our closest 3-topped polynomial to be
> c0c1c2 := InvM . Col ; [3]
c0c1c2 = [4]
[5]
Lo and behold! -these are indeed the coeffs of h.
================
Let's play the game again, but with different values for the sample-points.
> x1 := 12 : x2 := -31: x3 := 17:
y1 := h(x1) = 771; y2 := h(x2) = 4684; y3 := h(x3) = 1516;
> A := VandermondeMatrix(, 3,K); adjointA := Tpose(A):
M := adjointA . A; InvM := MI(M):
[1 12 144] [ 3 -2 1394]
A = [1 -31 961] , M = [ -2 1394 -23150]
[1 17 289] [1394 -23150 1027778]
> Q := <>; Col := adjointA . Q ;
[ 771] [ 6971]
Q = [4684] , Col = [ -110180]
[1516] [ 5050472]
At these new points, we compute the coefficients of d0 + d1*x + d2*x^2,
our closest 3-topped polynomial to be
> d0d1d2 := MI(M) . Col ; [3]
d0d1d2 = [4]
[5]
Again, we get the coefficients of h.
## ================================================================ ##
Here are the four data-points from the quiz Q13.
> x1 := -2 : x2 := -1 : x3 := 1 : x4 := 2 :
> y1 := 0 : y2 := 0 : y3 := 0 : y4 := 1 :
> Q := <>; [0]
[0]
Q := [0]
[1]
First we fit a 2-topped poly, a line, as in the quiz.
> K := 2 : A := VandermondeMatrix(, 4,K); adjointA := Tpose(A) :
[1 -2]
[1 -1]
A := [1 1]
[1 2]
> M := adjointA . A; InvM := MI(M): Col := adjointA . Q ; c0c1 := InvM . Col;
M := [4 0] , Col := [1] , c0c1 := [1/4]
[0 10] [2] [1/5]
Now we fit a 3-topped poly.
> K := 3 : A := VandermondeMatrix(, 4,K); adjointA := Tpose(A) :
[1 -2 4]
[1 -1 1]
A := [1 1 1]
[1 2 4]
> M := adjointA . A; InvM := MI(M): Col := adjointA . Q; c0c1c2 := InvM . Col;
[ 4 0 10] [1] [-1/6]
M := [ 0 10 0] , Col := [2] , c0c1c2 := [ 1/5]
[10 0 34] [4] [ 1/6]
Lastly, let's use a 4-topped poly.
> K := 4 : A := VandermondeMatrix(, 4,K); adjointA := Tpose(A) :
[1 -2 4 -8]
[1 -1 1 -1]
A := [1 1 1 1]
[1 2 4 8]
> M := adjointA . A; InvM := MI(M): Col := adjointA . Q; c0c1c2c3 := InvM . Col;
[ 4 0 10 0] [1] [ -1/6 ]
[ 0 10 0 34] [2] [ -1/12]
M := [10 0 34 0] , Col := [4] , c0c1c2c3 := [ 1/6 ]
[ 0 34 0 130] [8] [ 1/12]
==== Now let's compute the squared-distance for each fit ====
> polyt := c0c1[1,1] + c0c1[2,1]*t : h2 := unapply(polyt, t);
h2 := t -> 1/4 + 1/5 t
> Dist2 := (y1 - h2(x1))^2 + (y2 - h2(x2))^2 + (y3 - h2(x3))^2 + (y4 - h2(x4))^2 ;
Dist2 := 7/20
> polyt := c0c1c2[1,1] + c0c1c2[2,1]*t + c0c1c2[3,1]*t^2 : h3 := unapply(polyt, t) ;
2
h3 := t -> - 1/6 + 1/5 t + 1/6 t
> Dist3 := (y1 - h3(x1))^2 + (y2 - h3(x2))^2 + (y3 - h3(x3))^2 + (y4 - h3(x4))^2 ;
Dist3 := 1/10
> polyt := c0c1c2c3[1,1] + c0c1c2c3[2,1]*t + c0c1c2c3[3,1]*t^2 + c0c1c2c3[4,1]*t^3 :
h4 := unapply(polyt, t) ;
2 3
h4 := t -> - 1/6 - 1/12 t + 1/6 t + 1/12 t
> Dist4 := (y1 - h4(x1))^2 + (y2 - h4(x2))^2 + (y3 - h4(x3))^2 + (y4 - h4(x4))^2 ;
Dist4 := 0
So the cubic passes through all four data-points, as expected.
## ================================================================ ##