[METHODS] Data fitting and polynomial interpolation

Fit a straight line by least squares

For real data $(t_i,y_i)\in\mathbb R^2$ , form

M= \begin{pmatrix} t_1&1\\ t_2&1\\ \vdots&\vdots\\ t_n&1 \end{pmatrix}, \qquad Y= \begin{pmatrix} y_1\\y_2\\\vdots\\y_n \end{pmatrix}.

If at least two input values are distinct, the least-squares straight-line fit $y=mt+c$ has the unique coefficient vector

\begin{pmatrix}m\\c\end{pmatrix} =(M^{\mathsf T}M)^{-1}M^{\mathsf T}Y.

For a candidate line $y=mt+c$ , the vector of predicted values at the inputs is

M\begin{pmatrix}m\\c\end{pmatrix}.

The columns of $M$ contain the sampled values of $t$ and $1$ , so multiplying them by $m$ and $c$ produces the line's predicted values. The line need not pass through every data point.

The fitted value vector $M\binom{m}{c}$ lies in the column space

\operatorname{col}(M)=\operatorname{span}\left\{ \begin{pmatrix}t_1\\\vdots\\t_n\end{pmatrix}, \begin{pmatrix}1\\\vdots\\1\end{pmatrix} \right\}.

Least squares chooses $m$ and $c$ to minimise the sum of squared vertical errors

E(m,c)=\sum_{i=1}^n(y_i-mt_i-c)^2 =\left\|Y-M\begin{pmatrix}m\\c\end{pmatrix}\right\|^2,

where $\|\cdot\|$ is the usual Euclidean norm on $\mathbb R^n$ . The problem is therefore to find the point of $\operatorname{col}(M)$ closest to $Y$ ; the formula in the statement is the coordinate calculation for that projection.

At a minimum, differentiating with respect to $m$ and $c$ gives

\sum_{i=1}^n t_i(y_i-mt_i-c)=0, \qquad \sum_{i=1}^n(y_i-mt_i-c)=0.

These are exactly the two entries of

M^{\mathsf T}\left(Y-M\binom{m}{c}\right)=0, \qquad M^{\mathsf T}M\binom{m}{c}=M^{\mathsf T}Y.

Thus the residual

Y-M\binom{m}{c}

is perpendicular to both columns of $M$ , hence to their span. If $x_*$ solves the normal equations and $x$ is any other coefficient vector, this perpendicularity gives

\|Y-Mx\|^2=\|Y-Mx_*\|^2+\|M(x-x_*)\|^2.

So $Mx_*$ is the closest model vector to $Y$ .

When two input values are distinct, $at_i+b=0$ for every $i$ forces $a=b=0$ , so the columns of $M$ are independent. Hence $M^{\mathsf T}M$ is invertible and the minimising coefficient vector is unique. Multiplying the normal equations by $(M^{\mathsf T}M)^{-1}$ gives the coefficient formula in the statement.

[1]:Polynomial interpolation
[2]:A least-squares line

Interpolate in the standard polynomial basis

To find the coordinate vector of the interpolating polynomial in $B=(1,t,\ldots,t^{n-1})$ :

Form the Vandermonde matrix

A= \begin{pmatrix} 1&t_1&t_1^2&\cdots&t_1^{n-1}\\ 1&t_2&t_2^2&\cdots&t_2^{n-1}\\ \vdots&\vdots&\vdots&&\vdots\\ 1&t_n&t_n^2&\cdots&t_n^{n-1} \end{pmatrix}

and the data vector $y=(y_1,\ldots,y_n)^T$ . 2. Solve

Ax=y.

Read the solution

x= \begin{pmatrix} a_0\\a_1\\\vdots\\a_{n-1} \end{pmatrix} =[f]_B

as the coordinates of the interpolating polynomial.

The $i$ th row imposes the condition $f(t_i)=y_i$ . Because the inputs are distinct, these conditions determine exactly one coordinate vector.

Interpolate in the Lagrange basis

For data $(t_j,y_j)$ , construct the Lagrange polynomials and set

f(t)=\sum_{j=1}^n y_j\ell_j(t).

Then $f(t_i)=y_i$ for every $i$ , which gives the interpolating polynomial.

The data values are the coordinates in the Lagrange basis, while $a_0,\ldots,a_{n-1}$ are the coordinates of the same polynomial in the standard basis:

[f]_L= \begin{pmatrix} y_1\\\vdots\\y_n \end{pmatrix}, \qquad [f]_B= \begin{pmatrix} a_0\\\vdots\\a_{n-1} \end{pmatrix}.

The coordinate vector changes with the basis; the polynomial $f$ does not.

Methods from Data fitting and polynomial interpolation

Fit a straight line by least squares

Interpolate in the standard polynomial basis

Interpolate in the Lagrange basis

On this page