Newton Polynomial - Main Idea

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 + 1 data points we construct the Newton basis as

Using these polynomials as a basis for we have to solve

\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}

to solve the polynomial interpolation problem.

This system of equations can be solved recursively by solving

Read more about this topic:  Newton Polynomial

Famous quotes containing the words main and/or idea:

    “The Temptress has now been shown here—terrible. The story, Garbo, everything is extremely bad. It is no exaggeration to say that I was dreadful. I was tired, I couldn’t sleep and everything went wrong. But the main reason is, I suppose, that I’m no actress.”
    —Greta Garbo (1905–1990)

    “A CAUSE is an object precedent and contiguous to another, and so united with it that the idea of the one determines the mind to form the idea of the other, and the impression of the one to form a more lively idea of the other.”
    —David Hume (1711–1776)