Understanding newton interpolating polynomial

I understand what a Newton Interpolating Polynomial is and what it accomplishes, but I'm not exactly sure how it accomplishes it.
I'm not looking for a proof of why it works, just a layman explanation of how it is calculated, preferably with an example.

A lot like this question but instead of Lagrange Interpolating Polynomial it's about Newton's Interpolating Polynomial.

Answer

Polynomial interpolation amounts to solving a system of linear equations. Let's explain what that means: if you have some polynomials $p_1,\dots,p_n$ and want to interpolate the data $(x_1,y_1),\dots,(x_n,y_n)$, the interpolation problem says: find numbers $c_1,\dots,c_n$ so that

$$c_1 p_1(x_1) + c_2 p_2(x_1) + \dots + c_n p_n(x_1) = y_1 \\ c_1 p_1(x_2) + c_2 p_2(x_2) + \dots + c_n p_n(x_2) = y_2 \\ \vdots \\ c_1 p_1(x_n) + c_2 p_2(x_n) + \dots + c_n p_n(x_n) = y_n.$$

Thus, we can pick and choose the polynomials $p$ that we want to use to find these $c$s. Good choices will make this system of linear equations easy to solve. In Lagrange interpolation, you choose polynomials $\ell_k$ which vanish at all but one node and are equal to $1$ at the remaining node. Then the system just becomes $c_1=y_1,c_2=y_2$, etc.

In Newton interpolation we make the system a little bit harder to solve. Specifically, we have $p_1$ which is constant, $p_2$ which vanishes at $x_1$, $p_3$ which vanishes at $x_1$ and $x_2$, and so forth. This idea is fairly similar to Lagrange interpolation: once we've chosen an interpolant for the first $k$ points, we want every change we make to leave those $k$ points alone.

With this choice, the system above becomes

$$\begin{align} c_1 p_1(x_1)= y_1 \\ c_1 p_1(x_2) + c_2 p_2(x_2) = y_2 \\ c_1 p_1(x_3) + c_2 p_2(x_3) + c_3 p_3(x_3) = y_3 \\ \vdots \\ c_1 p_1(x_n) + \dots + c_n p_n(x_n) = y_n. \end{align}$$

This system is triangular, whereas the Lagrange system is diagonal. But it is still pretty easy to solve: we read off $c_1=\frac{y_1}{p_1(x_1)}$, then we plug that into the second equation and solve for $c_2$, then we plug those results into the third equation and solve for $c_3$, etc.

The only remaining thing is to choose these polynomials. But that's not difficult: just pick the simplest polynomials that vanish at $x_1,\dots,x_{k-1}$, namely $p_1=1$, $p_k=(x-x_1)\dots(x-x_{k-1})$ for $k \geq 2$.

An example: you want to interpolate $(1,2),(3,4),(6,10)$. You have $p_1=1,p_2=x-1,p_3=(x-1)(x-3)$. Your first equation says:

$$c_1=2.$$

Your second equation says

$$c_1 + c_2 \cdot 2 = 4.$$

Plug in what $c_1$ is:

$$2 + 2c_2 = 4$$

so $c_2=1$. Your third equation says

$$c_1 + c_2 \cdot 5 + c_3 \cdot 15 = 10.$$

Plug in what you know:

$$2 + 5 + 15c_3 = 10$$

so $c_3=\frac{1}{5}$. Thus your interpolant is $2+(x-1)+\frac{1}{5}(x-1)(x-3)$.