Polynomial Interpolation - Constructing The Interpolation Polynomial

Constructing The Interpolation Polynomial

Suppose that the interpolation polynomial is in the form

The statement that p interpolates the data points means that

If we substitute equation (1) in here, we get a system of linear equations in the coefficients . The system in matrix-vector form reads

\begin{bmatrix} x_0^n & x_0^{n-1} & x_0^{n-2} & \ldots & x_0 & 1 \\ x_1^n & x_1^{n-1} & x_1^{n-2} & \ldots & x_1 & 1 \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ x_n^n & x_n^{n-1} & x_n^{n-2} & \ldots & x_n & 1 \end{bmatrix} \begin{bmatrix} a_n \\ a_{n-1} \\ \vdots \\ a_0 \end{bmatrix} = \begin{bmatrix} y_0 \\ y_1 \\ \vdots \\ y_n \end{bmatrix}.

We have to solve this system for to construct the interpolant The matrix on the left is commonly referred to as a Vandermonde matrix.

The condition number of the Vandermonde matrix may be large, causing large errors when computing the coefficients if the system of equations is solved using Gaussian elimination.

Several authors have therefore proposed algorithms which exploit the structure of the Vandermonde matrix to compute numerically stable solutions in operations instead of the required by Gaussian elimination. These methods rely on constructing first a Newton interpolation of the polynomial and then converting it to the monomial form above.

Read more about this topic:  Polynomial Interpolation

Famous quotes containing the words constructing the and/or constructing:

    “The very hope of experimental philosophy, its expectation of constructing the sciences into a true philosophy of nature, is based on induction, or, if you please, the a priori presumption, that physical causation is universal; that the constitution of nature is written in its actual manifestations, and needs only to be deciphered by experimental and inductive research; that it is not a latent invisible writing, to be brought out by the magic of mental anticipation or metaphysical mediation.”
    —Chauncey Wright (1830–1875)

    “The very hope of experimental philosophy, its expectation of constructing the sciences into a true philosophy of nature, is based on induction, or, if you please, the a priori presumption, that physical causation is universal; that the constitution of nature is written in its actual manifestations, and needs only to be deciphered by experimental and inductive research; that it is not a latent invisible writing, to be brought out by the magic of mental anticipation or metaphysical mediation.”
    —Chauncey Wright (1830–1875)