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 main facts in human life are five: birth, food, sleep, love and death.”
    —E.M. (Edward Morgan)

    “Thrift is an attractive idea until you get down to specifics.”
    —Mason Cooley (b. 1927)