Numerical Analysis/Newton form exercise

1. Using the Newton form, find the interpolating polynomial passing through the points $(x_0,y_0)=(9,9)$, $(x_1,y_1)=(5,7)$, $(x_2,y_2)=(3,7)$, and $(x_3,y_3)=(7,1)$.

Solution:

To find the four coefficients, we can use the divided differences.

$\begin{array}{ccccc}{x}_i& y_i& [y_0,y_1]& [y_0,y_1,y_2]& [y_0,y_1,y_2,y_3]\\ 9& 9& & \\ & & \frac{7-9}{5-9}=\frac{1}{2}& \\ 5& 7& & \frac{\frac{0-1}{2}}{3-9}=\frac{1}{12}\\ & & \frac{7-7}{3-5}=0& & \frac{\frac{-3}{4}-\frac{1}{12}}{7-9}=\frac{5}{12}\\ 3& 7& & \frac{\frac{-3}{2}-0}{7-5}=\frac{-3}{4}\\ & & \frac{1-7}{7-3}=\frac{-3}{2}& \\ 7& 1& & \end{array}$

Thus, the four coefficients are $x_0$ and the upper diagonal of the calculated divided differences.

Using the Newton Forward Divided Difference formula, we find the polynomial is

$p_3(x)=[y_0]+[y_0,y_1](x-x_0)+[y_0,y_1,y_2](x-x_0)(x-x_1)+[y_0,y_1,y_2,y_3](x-x_0)(x-x_1)(x-x_2).$

$p_3(x)=9+\frac{1}{2}(x-9)+\frac{1}{12}(x-9)(x-5)+\frac{5}{12}(x-9)(x-5)(x-3).$

$p_3(x)=\frac{5}{12}{x}^3-7x^2+\frac{427}{12}x-48$.

 

2. Find the interpolating polynomial passing through the four points given in the exercise above as well as through the point $(x_4,y_4)=(4,2)$

Solution:

To find the new coefficient, we can simply add the new point to the end and calculate $[y_0,y_1,y_2,y_3,y_4]$.

$\begin{array}{cccccc}{x}_i& y_i& [y_0,y_1]& [y_0,y_1,y_2]& [y_0,y_1,y_2,y_3]& [y_0,y_1,y_2,y_3,y_4]\\ 9& 9& & \\ & & \frac{1}{2}& \\ 5& 7& & \frac{1}{12}\\ & & 0& & \frac{5}{12}\\ 3& 7& & \frac{-3}{4}& & \frac{\frac{-23}{12}-\frac{5}{12}}{4-9}=\frac{17}{15}\\ & & \frac{-3}{2}& & \frac{\frac{7}{6}-\frac{-3}{4}}{4-5}=\frac{-23}{12}\\ 7& 1& & \frac{\frac{-1}{3}-0}{\frac{-3}{2}}=\frac{7}{6}\\ & & \frac{2-1}{4-7}=\frac{-1}{3}& \\ 4& 2& & \end{array}$

Thus, we find the polynomial $p_4$ is

$p_4(x)=p_3+[y_0,y_1,y_2,y_3,y_4](x-x_0)(x-x_1)(x-x_2)(x-x_3).$

$p_3(x)=\frac{5}{12}{x}^3-7x^2+\frac{427}{12}x-48+\frac{17}{15}(x-9)(x-5)(x-3)(x-7).$

$p_3(x)=\frac{7}{15}{x}^4-\frac{647}{60}{x}^3+\frac{1337}{15}{x}^2-\frac{18697}{60}x+393$.