↑ arvau

Wikipedia / Hermite interpolation

In numerical analysis, Hermite interpolation, named after Charles Hermite, is a method of polynomial interpolation, which generalizes Lagrange interpolation. Lagrange interpolation allows computing a polynomial of degree less than that takes the same value at given points as a given function. Instead, Hermite interpolation computes a polynomial of degree fewer than such that the polynomial and its first few derivatives have the same values at (fewer than .

Hermite's method of interpolation is closely related to the Newton's interpolation method, in that both can be derived from the calculation of divided differences. However, there are other methods for computing a Hermite interpolating polynomial. One can use linear algebra, by taking the coefficients of the interpolating polynomial as unknowns, and writing as linear equations the constraints that the interpolating polynomial must satisfy. For another method, see . For yet another method, see, which uses contour integration.

Statement of the problem

In the restricted formulation studied in , Hermite interpolation consists of computing a polynomial of degree as low as possible that matches an unknown function both in observed value, and the observed value of its first derivatives. This means that The resulting polynomial has a degree less than . (In a more general case, there is no need for to be a fixed value; that is, some points may have more known derivatives than others. In this case the resulting polynomial has a degree less than the number of data points.)

Let us consider a polynomial of degree less than with indeterminate coefficients; that is, the coefficients of are new variables. Then, by writing the constraints that the interpolating polynomial must satisfy, one gets a system of n(m + 1) linear equations in unknowns.

In general, such a system has exactly one solution. In, Charles Hermite used contour integration to prove that this is effectively the case here, and to find the unique solution, provided that the are pairwise different. The Hermite interpolation problem is a problem of linear algebra that has the coefficients of the interpolation polynomial as unknown variables and a confluent Vandermonde matrix as its matrix. The general methods of linear algebra, and specific methods for confluent Vandermonde matrices are often used for computing the interpolation polynomial. Another method is described below.

Using Chinese remainder theorem

Let be a positive integer, be nonnegative integers, and values that are real numbers or belong to any other field of characteristic zero. Hermite interpolation problem consists of finding a polynomial such that

for , where the are given values in the same field as the .

These conditions implies that the Taylor polynomial of of degree at is

In other words, the desired polynomial is congruent.

The Chinese remainder theorem for polynomials

arithmetic operations, or even faster with fast polynomial multiplication.

This approach does not work in positive characteristic, because of the denominators of the coefficients of the Taylor polynomial. The approach through divided differences, below, works in every characteristic.

Explicit basis construction

Similar to Lagrange interpolation, one can construct an explicit polynomial basis for Hermite interpolation using the Chinese Remainder Theorem.

:

Node polynomials

satisfying the modular system:

takes the form:

share no roots and are thus coprime, Bézout's identity such that:

:

can be computed together using the polynomial extended Euclidean algorithm is required for the construction, it can be computed alone using a half extended Euclidean algorithm variant.

By the polynomial remainder theorem, reducing this construction to standard Lagrange interpolation.

reduces to a constant scalar that can be computed directly in closed form:

Basis polynomials

as:

reduces to:

denotes the Kronecker delta.

:

.

Using divided differences

Simple case when all k=2

When using divided differences to calculate the Hermite polynomial of a function f, the first step is to copy each point m

Now, we create a divided differences table. All others are calculated normally.

A more general case when k>2

has k contains k. When creating the table, divided differences

etc.

A fast algorithm for the fully general case is given by Schneider and Werner. A slower but more numerically stable algorithm is given by Corless and Fillion.

Example

, we obtain the following data: by taking the coefficients from the diagonal of the divided difference table, and multiplying the k, as we would when generating a Newton polynomial.

Quintic Hermite interpolation

Error

Call the calculated polynomial H and original function f, the error function where c, Kst order is zero at each node, as it should be.

In the complex case, as described for example on p. 360 in,.

See also

References