Example 3. Given the polynomial $P(x)=x^{3}-2 x^{2}+3 x+1$. Known are its

$$
x_{0}=0, \quad x_{1}=1, \quad x_{2}=2, \quad x_{3}=3:
$$

$P(0)=1, \quad P(1)=3, \quad P(2)=7, P(3)=19$. Find the values of the polynomial at $x_{k}=k \quad(k=4,5,6,7,8,9,10)$.
Solution. We construct a table of differences of various orders (Table 15.4).

Table 15.4

Table 15.5

| $x$ | $y$ | $\Delta y$ | $\Delta^{2} y$ | $\Delta^{3} y$ |
| :---: | :---: | :---: | :---: | :---: |
| 0 | 1 | 2 |  |  |
| 1 | 3 | 4 | 2 | 6 |
| 2 | 7 | 12 | 8 |  |
| 3 | 19 |  |  |  |
|  |  |  |  |  |


| $x$ | $y$ | $\Delta y$ | $\Delta^{2} y$ | $\Delta^{3} y$ |
| :---: | :---: | :---: | :---: | :---: |
| 0 | 1 | 2 |  |  |
| 1 | 3 | 4 | 2 | 6 |
| 2 | 7 | 12 | 8 | 6 |
| 3 | 19 | 26 | 14 |  |
| 4 | 45 |  |  |  |

Since for a polynomial of the third degree, the third-order differences are constant, this table can be continued, starting from the last column. We write the next digit 6 in the $\Delta^{3} y$ column; adding this number to the number 8, we get 14 - the new number in the $\Delta^{2} y$ column; similarly, we get the number $26=14+12$ in the $\Delta y$ column and the value $y_{4}=P(4)=45$ (Table 15.5).

Continuing this process, we obtain a new table (Table 15.6).

Table 15.6

| $x$ | $y$ | $\Delta y$ | $\Delta^{2} y$ | $\Delta^{3} y$ |
| :---: | :---: | :---: | :---: | :---: |
| 0 | 1 | 2 |  |  |
| 1 | 3 | 4 | 2 |  |
| 2 | 7 | 12 | 8 | 6 |
| 3 | 19 | 26 | 14 | 6 |
| 4 | 45 | 46 | 20 | 6 |
| 5 | 91 | 72 | 26 | 6 |
| 6 | 163 | 104 | 32 | 6 |
| 7 | 267 | 142 | 38 | 6 |
| 8 | 409 | 186 | 44 | 6 |
| 9 | 595 | 236 | 50 | 6 |
| 10 | 831 |  |  |  |

Therefore, the required values of the polynomial are: $P(5)=91, P(6)=163, P(7)=267, P(8)=409, P(9)=595, P(10)=831$.

## Problems

Find the differences of various orders:
1.

| $k$ | 0 | 1 | 2 |
| :---: | :---: | :---: | :---: |
| $x_{k}$ | -1 | 1 | 2 |
| $y_{k}$ | 10 | 6 | 13 |

2. | $k$ | 0 | 1 | 2 |
| :---: | :---: | :---: | :---: |
| $x_{k}$ | -2 | -1 | 1 |
| $y_{k}$ | 12 | 6 | 0 |
3. 

| $k$ | 0 | 1 | 2 | 3 | 4 | 5 |
| :---: | :---: | :---: | :---: | :---: | :---: | :---: |
| $x_{k}$ | -3 | -2 | -1 | 0 | 1 | 2 |
| $y_{k}$ | -9 | -16 | -3 | 6 | 11 | 36 |

Find the divided differences of various orders:

4. 

| $k$ | 0 | 1 | 2 |
| :---: | :---: | :---: | :---: |
| $x_{k}$ | 2 | 4 | 5 |
| $y_{k}$ | 1 | 15 | 28 |

5. | $k$ | 0 | 1 | 2 |
| :---: | :---: | :---: | :---: |
| $x_{k}$ | 1 | 2 | 3 |
| $y_{k}$ | -4 | -7 | -16 |
6. 

| $k$ | 0 | 1 | 2 | 3 | 4 |
| :---: | :---: | :---: | :---: | :---: | :---: |
| $x_{k}$ | -2 | -1 | 0 | 1 | 2 |
| $y_{k}$ | -16 | -3 | 6 | 11 | 36 |

7. Given the polynomial $P(x)=2 x^{2}-5 x+7$ and its values: $P(0)=7$, $P(1)=4, P(2)=5$. Find the values of $P(k)$, where $k=2,3, \ldots, 10$.
8. Given the polynomial $P(x)=2 x^{3}-4 x^{2}-6 x+15$ and its values: $P(0)=15, P(1)=7, P(2)=3, P(3)=15, P(4)=55$. Find its values for $x=5,6, \ldots, 10$.
9. Given the polynomial $P(x)=x^{4}-x^{3}+x^{2}-x+3$ and its values: $P(0)=3, P(1)=3, P(2)=13, P(3)=63, P(4)=207$. Find its values for $x=5,6, \ldots, 10$.

## § 15.3. Newton's Interpolation Polynomial

Newton's interpolation polynomial is a polynomial

$$
\begin{aligned}
& P(x)=y_{0}+\left(x-x_{0}\right) f\left(x_{0}, x_{1}\right)+\left(x-x_{0}\right)\left(x-x_{1}\right) f\left(x_{0}, x_{1}, x_{2}\right)+\ldots \\
& \ldots+\left(x-x_{0}\right)\left(x-x_{1}\right) \ldots\left(x-x_{n-1}\right) f\left(x_{0}, x_{1}, \ldots, x_{n}\right)
\end{aligned}
$$

where $f\left(x_{0}, x_{1}\right), f\left(x_{0}, x_{1}, x_{2}\right), \ldots, f\left(x_{0}, x_{1}, \ldots, x_{n}\right)$ are the divided differences of various orders. This polynomial satisfies the conditions $y_{k}=f\left(x_{k}\right)=P_{n}\left(x_{k}\right)(k=0,1,2, \ldots, n)$.

Newton's interpolation formula is the formula

$$
\begin{aligned}
& f(x) \approx y_{0}+\left(x-x_{0}\right) f\left(x_{0}, x_{1}\right)+\left(x-x_{0}\right)\left(x-x_{1}\right) f\left(x_{0}, x_{1}, x_{2}\right)+\ldots \\
& \ldots+\left(x-x_{0}\right)\left(x-x_{1}\right) \ldots\left(x-x_{n-1}\right) f\left(x_{0}, x_{1}, x_{2}, \ldots, x_{n}\right)
\end{aligned}
$$

Remark 1. Since each $k$-th term of Newton's polynomial depends only on the $k$ first interpolation nodes and the values of the function at these nodes, adding new nodes only adds new terms to formula (15.14) without changing the original terms. This is a significant advantage of Newton's polynomial over Lagrange's polynomial.

Remark 2. Due to the uniqueness of the interpolation polynomial of degree $n$, Newton's interpolation polynomial can be transformed into Lagrange's interpolation polynomial and vice versa by rearranging the terms.

In the case of equally spaced interpolation nodes ($x_{1}=x_{0}+h, x_{2}=x_{0}+2 h, \ldots, x_{n}=x_{0}+n h$), from formula (15.15) with the consideration of equalities (15.11) - (15.13), we obtain Newton's interpolation formula for "forward interpolation":

$$
\begin{aligned}
f(x) \approx & y_{0}+\frac{\Delta y_{0}}{h}\left(x-x_{0}\right)+\frac{\Delta^{2} y_{0}}{2!h^{2}}\left(x-x_{0}\right)\left(x-x_{1}\right)+ \\
& +\frac{\Delta^{3} y_{0}}{3!h