Finding a polynomial that interpolates data (Newton's method with Horner's method)

Question

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$ ?

It is presented confusing, because I'm confused. I do not understand it. I think the problem is asking to find the interpolation polynomial using newton's method. What is horners form? — Sorry, Oct 22 '20 at 15:19
Alright, I can't see what that has to do with this problem. @moo — Sorry, Oct 22 '20 at 15:22

score 2 · Accepted Answer · answered Oct 22 '20 at 15:59

2

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$).

answered Oct 22 '20 at 15:59

Simply Beautiful Art

74,685

Okay. When finding the Newton polynomial, when should I stop the algorithm? – Sorry Oct 22 '20 at 16:01
You use the given points like you said. Or, to be more precise, you take a number of points that are near the area you would like to estimate best and ignore points farther away. – Simply Beautiful Art Oct 22 '20 at 16:03
From my problem the $p$ will be $p_1$, right? – Sorry Oct 22 '20 at 16:03
If you wish to use both points, then yes you will end up with $p_1$. – Simply Beautiful Art Oct 22 '20 at 16:04
oh! Now get it thanks! – Sorry Oct 22 '20 at 16:04
The resultat polynomial will $p=p_n$ will always have $\deg(p) \leq n$, right? – Sorry Oct 22 '20 at 16:06
If you have $n+1$ points, then the highest degree polynomial you can use is $p_n$. Like I pointed out in the comment above, you don't necessarily always want to use this, but you can. – Simply Beautiful Art Oct 22 '20 at 16:09
Okay, so if I use all $n+1$ points, then the polynomial $p=p_n$ will be of degree $n$, right? If a point is an outliner and I want to ignorer that, then I have $n$ points and the resulting polynomial will be $p=p_{n-1}$ and the degree of this will be $n-1$? Right? – Sorry Oct 22 '20 at 16:13
Degree of at most $n-1$ yes. – Simply Beautiful Art Oct 22 '20 at 16:14
I do not get, what it is at most $n-1$. Could you explain that? – Sorry Oct 22 '20 at 16:16
The degree depends on the last nonzero coefficient. If $c_n$ is nonzero then the degree is $n-1$, but otherwise... – Simply Beautiful Art Oct 22 '20 at 16:20
Right, right. I think I get it know. Thanks. – Sorry Oct 22 '20 at 16:22

Finding a polynomial that interpolates data (Newton's method with Horner's method)

1 Answers1