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:

“Women are taught that their main goal in life is to serve others—first men, and later, children. This prescription leads to enormous problems, for it is supposed to be carried out as if women did not have needs of their own, as if one could serve others without simultaneously attending to one’s own interests and desires. Carried to its “perfection,” it produces the martyr syndrome or the smothering wife and mother.”
—Jean Baker Miller (20th century)

“One way of getting an idea of our fellow-countrymen’s miseries is to go and look at their pleasures.”
—George Eliot [Mary Ann (or Marian)