Hermiteinterpolation

In numerical mathematics is the Hermiteinterpolation (named after Charles Hermite ) interpolation method for a polynomial that takes into account also leads to the interpolating function.

• 4.1 Pseudocode

Preparation

Motivation

A result for the classical polynomial interpolation states that equidistant nodes - ie, the same distance between the known function values ​​- leads to an exponential increase in the condition number of the polynomial, so its error increases dramatically.

Since equidistant measurement points in practice but in practice, sometimes unavoidable, are, one needs an interpolation method which produces only small errors for this case. One approach is the spline interpolation, in which the area in which a function to be interpolated, divided by a grid and performing a polynomial in each of the resulting intervals.

If you select this the " naive " Newtonian approach, the derivatives of the interpolated at the grid points do not necessarily coincide - hence the interpolated at these points is generally not ( continuously ) differentiable. It does not have to " corners " as in the example on the right, remain. It could happen, for example, that the interpolated approach on two adjacent intervals "from above" the grid point and so actually a - vividly - " peak " arises.

Because this behavior is obviously undesirable, you tried to make the transitions smooth, by addition to the function values ​​at the grid points still requires as many derivatives as known and the interpolation polynomials are chosen so that the derivatives match at the common point. In practice, it is sufficient to equate the first derivative to obtain a "smooth" looking graph.

This challenge is analogous to the problem in the classical polynomial interpolation to solve writing. As an example, consider the task

We define

The equation system is thus

Solve for bringing the desired coefficients.

This approach has the disadvantage that it is in the class of complexity and is therefore slow. It would be desirable to be able to take the Newton basis of the classical polynomial interpolation. However, this approach eliminates coincident sampling points, and is therefore not applicable without modification. Therefore, we extended it to the Hermitian interpolation.

Hermite Genocchi formula

The Hermite Genocchi formula forms the basis of Hermiteinterpolation. It provides an integral representation for the divided differences of the Newton algorithm of polynomial:

With the k-dimensional unit simplex

We prove this identity by induction.

In contrast to the divided differences emerged in the integral in this formula is not a quotient of the difference between two support points on - mathematically, it is thus possible to use confluent ( coincident ) interpolation points. If you compare the formula as

Represents, this identity can be easily proved.

Obviously, one can consider derivatives in the interpolation thus by repeated use of support points.

So the following theorem is valid:

Hermiteinterpolation

Let and be real reference points. Then satisfies the polynomial

The interpolation conditions

Furthermore, this solution is unique.

Error estimate

For the error of the Hermiteinterpolierten applies after the error in the Taylor expansion of the upper bound

In the event of the grille

Applies:

Calculation of the interpolated

For the practical calculation of the interpolated using as before the scheme of divided differences.

In the case, rather than the formula used there

Be calculated.

Note that some further rearrangements are necessary. In the following,:

• Instead one has to compute the divided difference
• If somewhere in the recursion, we calculate instead
• In all cases in which the formula is used in the original Neville Aitken scheme replaced by any one.

Pseudocode

The pseudo code illustrates how to compute the generalized form of divided differences. Lists are believed indicated below as from 1.

← xvals support points yvals ← function values ​​f (x ) and possibly multiple leads for values ​​of x zvals ← { f ( xvals [i ] ) |. i ∈ 1 # xvals } for i ← # xvals .. 1 do    for j ← i. # xvals do      if i = j then        [xi .. xj ] f ← zvals [i ]      else if xvals [i ] = xvals [j ] then        index ← index of the first occurrence of xvals [i ] in xvals        [xi .. xj ] f ← yvals [j - i index] / ( j -i)!      else        [xi .. xj ] ← f ( [xi 1 .. xj ] f - [ xi .. xj- 1] f ) / ( xvals [j ] - xvals [i]) history

First published his research on the Hermite Hermiteinterpolation 1878: Sur la formule d' interpolation Lagrange, Journal for Pure and Applied Mathematics, Volume 84, page 70-79