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:

“One of the main tasks of adolescence is to achieve an identity—not necessarily a knowledge of who we are, but a clarification of the range of what we might become, a set of self-references by which we can make sense of our responses, and justify our decisions and goals.”
—Terri Apter (20th century)

“At great periods you have always felt, deep within you, the temptation to commit suicide. You gave yourself to it; breached your own defenses. You were a child. The idea of suicide was a protest against life; by dying, you would escape this longing for death.”
—Cesare Pavese (1908–1950)