Section CF  Curve Fitting

From A First Course in Linear Algebra
Version 2.99
© 2004.
Licensed under the GNU Free Documentation License.
http://linear.ups.edu/

This Section is Incomplete

Given two points in the plane, there is a unique line through them. Given three points in the plane, and not in a line, there is a unique parabola through them. Given four points in the plane, there is a unique polynomial, of degree 3 or less, passing through them. And so on. We can prove this result, and give a procedure for finding the polynomial with the help of Vandermonde matrices (Section VM).

Theorem IP
Interpolating Polynomial
Suppose (xiyi)1≤i≤n+1  is a set of n+1 points in the plane where the x-coordinates are all different. Then there is a unique polynomial of degree n or less, p(x), such that p(xi)=yi, 1≤i≤n+1. □

Proof   Write p(x)=a0+a1x+a2x2+⋯+anxn. To meet the conclusion of the theorem, we desire,

This is a system of n+1 linear equations in the n+1 variables a0a1a2…an. The vector of constants in this system is the vector containing the y-coordinates of the points. More importantly, the coefficient matrix is a Vandermonde matrix (Definition VM) built from the x-coordinates x1x2x3…xn+1. Since we have required that these scalars all be different, Theorem NVM tells us that the coefficient matrix is nonsingular and Theorem NMUS says the solution for the coefficients of the polynomial exists, and is unique. As a practical matter, Theorem SNCM provides an expression for the solution. ■

Example PTFP
Polynomial through five points
Suppose we have the following 5 points in the plane and we wish to pass a degree 4 polynomial through them.

The required system of equations has a coefficient matrix that is the Vandermonde matrix where row i is successive powers of xi

A =        1 1 1 1 1 −3 −1 2 3 6 9 1 4 9 36 −27 −1 8 27 216 81 1 16 81 1296            

Theorem NMUS provides a solution as

        a0 a1 a2 a3 a4           =A−1        276 16 31 144 2319          =         −115 0 5108 −154 1540 914 −73 −156 121 −1168 910 43 −41 −112 160 −21 −31 7217 118 −172 142 184 −11756 −1756 1756                   276 16 31 144 2319          =        3 −4 5 −2 2            

So the polynomial is p(x)=3−4x+5x2−2x3+2x4. ⊠

The unique polynomial passing through a set of points is known as the interpolating polynomial and it has many uses. Unfortunately, when confronted with data from an experiment the situation may not be so simple or clear cut. Read on.

Subsection DF: Data Fitting

Suppose that we have n real variables, x1x2x3…xn, that we can measure in an experiment. We believe that these variables combine, in a linear fashion, to equal another real variable, y. In other words, we have reason to believe from our understanding of the experiment, that

where the scalars a1a2a3…an are not known to us, but are instead desirable. We would call this our model of the situation. Then we run the experiment m times, collecting sets of values for the variables of the experiment. For run number k we might denote these values as yk, xk1, xk2, xk3, …, xkn. If we substitute these values into the model equation, we get m linear equations in the unknown coefficients a1a2a3…an. If m=n, then we have a square coefficient matrix of the system which might happen to be nonsingular and there would be a unique solution.

However, more likely mn (the more data we collect, the greater our confidence in the results) and the resulting system is inconsistent. It may be that our model is only an approximate understanding of the relationship between the xi and y, or our measurements are not completely accurate. Still we would like to understand the situation we are studying, and would like some best answer for a1a2a3…an.

Let y denote the vector with yi=yi , 1≤i≤m, let a denote the vector with aj=aj , 1≤j≤n, and let X denote the m×n matrix with Xij=xij , 1≤i≤m, 1≤j≤n. Then the model equation, evaluated with each run of the experiment, translates to Xa=y. With the presumption that this system has no solution, we can try to minimize the difference between the two side of the equation y−Xa. As a vector, it is hard to imagine what the minimum might be, so we instead minimize the square of its norm

S=y−Xaty−Xa  

To keep the logical flow accurate, we will define the minimizing value and then give the proof that it behaves as desired.

Definition LSS
Least Squares Solution
Given the equation Xa=y, where X is an m×n matrix of rank n, the least squares solution for a is XtX−1Xty . △

Theorem LSMR
Least Squares Minimizes Residuals
Suppose that X is an m×n matrix of rank n. The least squares solution of Xa=y, a′=XtX−1Xty , minimizes the expression

S=y−Xaty−Xa  

Proof   We begin by finding the critical points of S. In preparation, let Xj denote column j of X, for 1≤j≤n and compute partial derivatives with respect to aj, 1≤j≤n. A matrix product of the form xty is a sum of products, so a derivative is a sum of applications of the product rule,

∂∂ajS =∂∂ajy−Xaty−Xa =∑mi=1∂∂ajy−Xaiy−Xai+y−Xai∂∂ajy−Xai =2∑mi=1∂∂ajy−Xaiy−Xai =2∑mi=1∂∂ajyi−∑nk=1Xikaky−Xai =2∑mi=1−Xijy−Xai =−2Xjty−Xa  

The first partial derivatives will allow us to find critical points, while second partial derivatives will be needed to confirm that a critical point will yield a minimum. Return to the next-to-last expression for the first partial derivative of S,

∂∂aℓajS =∂∂aℓ2∑mi=1−Xijy−Xai =−2∑mi=1∂∂aℓXijy−Xai =−2∑mi=1Xij∂∂aℓyi−∑nk=1Xikak =−2∑mi=1Xij−Xiℓ =2∑mi=1XijXiℓ =2∑mi=1XtjiXiℓ =2XtXjℓ  

For 1≤j≤n, set ∂∂ajS=0. This results in the n scalar equations

XjtXa =Xjty 1≤j≤n  

These n vector equations can be summarized in the single vector equation,

XtX is an n×n matrix and since we have assumed that X has rank n, XtX will also have rank n. Since XtX is invertible, we have a critical point at

a′=XtX−1Xty  

Is this lone critical point really a minimum? The matrix of second partial derivatives is constant, and a positive multiple of XtX. Theorem CPSM tells us that this matrix is positive semi-definite. In an advanced course on multivariable calculus, it is shown that a minimum occurs exactly where the matrix of second partial derivatives is positive semi-definite. You may have seen this in the two-variable case, where a check on the positive semi-definiteness is disguised with a determinant of the 2×2 matrix of second partial derivatives. ■

Subsection EXC: Exercises

T20 Theorem IP constructs a unique polynomial through a set of n+1 points in the plane, (xiyi)1≤i≤n+1 , where the x-coordinates are all different. Prove that the expression below is the same polynomial and include an explanation of the necessity of the hypothesis that the x-coordinates are all different.

This is known as the Lagrange form of the interpolating polynomial.  
Contributed by Robert Beezer