Editing Newton polynomial (section)

==Main idea==
Solving an interpolation problem leads to a problem in linear algebra where we have to solve a system of linear equations. Using a standard [[monomial basis]] for our interpolation polynomial we get the very complicated [[Vandermonde matrix]]. By choosing another basis, the Newton basis, we get a system of linear equations with a much simpler [[lower triangular matrix]] which can be solved faster.

For ''k''&nbsp;+&nbsp;1 data points we construct the Newton basis as

:<math>n_0(x) := 1 , \qquad n_j(x) := \prod_{i=0}^{j-1} (x - x_i) \qquad j=1,\ldots,k.</math>

Using these polynomials as a basis for <math>\Pi_k</math> we have to solve

:<math>\begin{bmatrix}
      1 &         & \ldots &        & 0  \\
      1 & x_1-x_0 &        &        &    \\
      1 & x_2-x_0 & (x_2-x_0)(x_2-x_1) &        & \vdots   \\
 \vdots & \vdots  &        & \ddots &    \\
      1 & x_k-x_0 & \ldots & \ldots & \prod_{j=0}^{k-1}(x_k - x_j)
\end{bmatrix}
\begin{bmatrix}     a_0 \\     \\     \vdots \\     \\     a_{k} \end{bmatrix} =
\begin{bmatrix}      y_0 \\  \\  \vdots \\ \\    y_{k} \end{bmatrix}</math>

to solve the polynomial interpolation problem.

This system of equations can be solved iteratively by solving

:<math> \sum_{i=0}^{j} a_{i} n_{i}(x_j) = y_j \qquad j = 0,\dots,k.</math>