Least Squares : Approximation of cubic polynomial

Question

I want to determine an approximation of a cubic polynomial that has at the points $$x_0=-2, \ x_1=-1, \ x_2=0 , \ x_3=3, \ x_4=3.5$$ the values $$y_0=-33, \ y_1=-20, \ y_2=-20.1, \ y_3=-4.3 , \ y_4=32.5$$ using the least squares method.

So we are looking for a cubic polynomial $p(x)$ such that $$\sum_{i=0}^4\left (p(x_i)-y_i\right )^2$$ is minimal, right?

Let $p(x)=a_3x^3+a_2x^2+a_1x+a_0$. Then we get the following sum:

$$\left (-8a_3+4a_2-2a_1+a_0+33\right )^2+\left (-a_3+a_2-a_1+a_0+20\right )^2+\left (a_0+20.1\right )^2+\left (27a_3+9a_2+3a_1+a_0+4.3\right )^2+\left (42.875a_3+12.25a_2+3.5a_1+a_0-32.5\right )^2$$

Now we want to calculate the values of $a_0, a_1, a_2, a_3$ such that this sum is minimal, right?

How could we do that? Could you give me a hint?

Answer 1

So you want to minimize $S = \sum_{i=0}^4\left (p(x_i)-y_i\right )^2 $ where $p(x) =\sum_{k=0}^3 a_kx^k $.

The parameters you want to find are the $a_k$. You need to differentiate $S$ with respect to each $a_k$ and set that expression equal to zero.

This will give you $4$ equations in the $4$ $a_k$s.

Here is a typical one:

$\begin{array}\\ \dfrac{\partial S}{\partial a_k} &=\dfrac{\partial }{\partial a_k}\sum_{i=0}^4\left( p(x_i)-y_i\right)^2\\ &=\sum_{i=0}^4 \dfrac{\partial }{\partial a_k}\left(p(x_i)-y_i\right)^2\\ &=\sum_{i=0}^4 2\dfrac{\partial }{\partial a_k}(p(x_i)-y_i)(p(x_i)-y_i)\\ &=\sum_{i=0}^4 2\dfrac{\partial }{\partial a_k}(\sum_{j=0}^3 a_jx_i^j)(p(x_i)-y_i)\\ &=\sum_{i=0}^4 2( x_i^k)(\sum_{j=0}^3 a_jx_i^j-y_i)\\ &=2(\sum_{j=0}^3 a_j\sum_{i=0}^4 x_i^{j+k}-\sum_{i=0}^4 x_i^ky_i)\\ \end{array} $

Setting $\dfrac{\partial S}{\partial a_k} = 0$, this gives $\sum_{j=0}^3 a_j\sum_{i=0}^4 x_i^{j+k} =\sum_{i=0}^4 x_i^ky_i $ for $k = 0$ to $3$.

These are the equations that determine the $a_j$.

Answer 2

To find the polynomial of order $k$ given $N$ observations ($x_i$, $y_i$) it reduces to solving the following set of linear equations:

\begin{eqnarray} \begin{bmatrix} N & \sum_{i=1}^{N} x_i & \cdots & \sum_{i=1}^{N} x_i^k \\ \sum_{i=1}^{N} x_i & \sum_{i=1}^{N} x_i^2 & \cdots & \sum_{i=1}^{N} x_i^{k+1} \\ \vdots & \vdots & \vdots & \vdots \\ \sum_{i=1}^{N} x_i^k & \sum_{i=1}^{N} x_i^{k+1} & \cdots & \sum_{i=1}^{N} x_i^{2k} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ \vdots \\ a_k \\ \end{bmatrix}= \begin{bmatrix} \sum_{i=1}^{N} y_i \\ \sum_{i=1}^{N} x_i y_i \\ \vdots \\ \sum_{i=1}^{N} x_i^k y_i \\ \end{bmatrix} \end{eqnarray}

One method to solve this is Cramer's Rule which allows us to solve the above equation of the form $Ma = b$ for $a_i$ as:

$$a_i = \frac{\mathrm{det}(M_i)}{\mathrm{det}(M)}$$

where where $M_{i}$ the matrix formed by replacing the $i$-th column of $M$ by the column vector $b$.

For your above observations we would be solving: \begin{equation} \begin{bmatrix} 5 & 3.5 & 26.25 & 60.875 \\ 3.5 & 26.25 & 60.875 & 248.0625 \\ 26.25 & 60.875 & 248.0625 & 735.21875 \\ 60.875 & 248.0625 & 735.21875 & 2632.265625 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \\ \end{bmatrix}= \begin{bmatrix} -44.9 \\ 186 \\ 207.425 \\ 1561.3375 \\ \end{bmatrix} \end{equation}

Using Cramer's rule for $a_0$ we have

\begin{equation} a_o = \frac{\mathrm{det} \begin{bmatrix} -44.9 & 3.5 & 26.25 & 60.875 \\ 186 & 26.25 & 60.875 & 248.0625 \\ 207.425 & 60.875 & 248.0625 & 735.21875 \\ 15613375 & 248.0625 & 735.21875 & 2632.265625 \end{bmatrix}}{\mathrm{det} \begin{bmatrix} 5 & 3.5 & 26.25 & 60.875 \\ 3.5 & 26.25 & 60.875 & 248.0625 \\ 26.25 & 60.875 & 248.0625 & 735.21875 \\ 60.875 & 248.0625 & 735.21875 & 2632.265625 \end{bmatrix}}\approx -23.0087 \end{equation}

Answer 3

In this case, you have the Vandermonde matrix

\begin{equation*} X = \left(\begin{array}{cccc} 1 & x_{0} & x_{0}^{2} & x_{0}^{3}\\ 1 & x_{1} & x_{1}^{2} & x_{1}^{3}\\ 1 & x_{2} & x_{2}^{2} & x_{2}^{3}\\ 1 & x_{3} & x_{3}^{2} & x_{3}^{3}\\ 1 & x_{4} & x_{4}^{2} & x_{4}^{3}\\ \end{array}\right) = \left(\begin{array}{cccc} 1 & -2 & 4 & -8\\ 1 & -1 & 1 & -1\\ 1 & 0 & 0 & 0\\ 1 & 3 & 9 & 27\\ 1 & 7/2 & 49/4 & 343/8 \end{array}\right). \end{equation*}

Therefore, the coefficients of the least-squares cubic polynomial are

\begin{align*} \left(\begin{array}{c} a_{0}\\ a_{1}\\ a_{2}\\ a_{3} \end{array}\right) = \left(X^{T}X\right)^{-1}X^{T}\left(\begin{array}{c} y_{0}\\ y_{1}\\ y_{2}\\ y_{3}\\ y_{4} \end{array}\right) = \left(\begin{array}{c} -20245488/879905\\ -129265907/10558860\\ -4898769/1759810\\ 620636/203055 \end{array}\right). \end{align*}