Problem Find the polynomial that interpolates the data:
$$
\begin{array}{|c||c|c|}
\hline x & 3 & 7 \\
\hline y & 5 & -1
\end{array}
$$
So I have Newton's polynomials given by
$$
p_{0}(x)=c_{0}, \quad p_{i}(x)=p_{i-1}(x)+c_{i} \prod_{j=0}^{i-1}\left(x-x_{j}\right), \quad i=0, \ldots, n
$$
and the constants $c_i,i=0,…,n$ are given by
$$
c_{i}=\frac{\left(y_{i}-p_{i-1}\left(x_{i}\right)\right)}{\prod_{j=0}^{i-1}\left(x_{i}-x_{j}\right)}
$$
In general we have $n+1$ data points. In my case I have $n+1=2$ data points. The resulting polynomial form the interpolation will be of degree $n$, right?
Which part of this entire method is Newton's method for interpolation and which part is Horner's method for calculating the polynomials $p_i$ ?
Best Answer
As you stated, $p$ forms the Newton polynomial, which is just one way to write/find a polynomial interpolation.
Horner's method is a special way of writing polynomials which allows for more efficient evaluation. In the the particular case of Newton polynomials, one may write the solution in the form
$$c_0+(x-x_0)(c_1+(x-x_1)(c_2+\dots))$$
which allows one to avoid evaluating lots of products (repeated calculation of $(x-x_0)(x-x_1)(x-x_2)\dots$).