Why are polynomials used

Original source http://www.apm.tuwien.ac.at/~ernst/eis/k1___004.htm

1.1.1 Interpolation

To n + 1 given support points (all xi different) there is exactly one polynomial with degree ngoing through all the points.

The ci are the coefficients. If cn 0 is called n Degree of Polynomial and cn highest coefficient. Polynomials have the advantage that they themselves and all of their derivatives are continuous. For example, there are the following methods for calculating the coefficients from the support points:

System of equations:
By inserting the point coordinates of the n + 1 support points you get a linear system of equations with n +1 equations for the n + 1 unknown c0 , c1 , ...., cn .

For i = 0, 1, ....., n
  1. Lagrange's idea:
This procedure decomposes the polynomial p(x) into a sum of n + 1 polynomials n-th degree, where the i-th polynomial through the point P.i goes and at all other support points xj ( j = 0 , ...., n; j i) Has zeros. To do this, one defines the Lagrange factors L.i (x) these are polynomials n-th degree with the following characteristics:
L.i (xi) = 1
L.i (xj) = 0 for j i

The formula for the Lagrange factors is:

The interpolation polynomial you are looking for is immediately obtained from this

Divided differences according to Newton:



The question arises, however, whether interpolation (using high-degree polynomials) can actually be used sensibly in practice. Polynomials are probably continuous and continuously differentiable; but are they always nice and smooth, as is desirable in computer graphics?

WeierstraƟ's approximation theorem:

Every continuous function can be approximated with arbitrary precision in a finite interval using a polynomial. (The higher the degree of the polynomial, the better one can approximate.)
In theory, any good approximation with polynomials is possible for every continuous function, but problems often arise in practice; Interpolation polynomials are very prone to Overshoot.

Stanchion (approx. 1900):

A continuous function f(x) With x [from] should be represented by a polynomial n-th degree pn(x) can be approximated. To do this, one chooses n + 1 equidistant support points in the interval [from] and computes the interpolation polynomial. Attempts are made to improve the quality of the approximation by increasing the number of support points. Runge has shown that the interpolation polynomial pn(x) For n not always against the function f(x) converges. This also applies to very simple ones f (x) :

With x [-5, 5]

The overshoot is increasing with n Always stronger.
You can get a graphic representation again with Ipax II.

Interpolation using a polynomial therefore has several serious disadvantages:

  • Overshoot can occur, which means that the curve is not smooth.
  • If there are many support points, the degree of the polynomial is very high. High-degree polynomials can be sensitive to minor changes in the data (coordinates of the support points).
  • The computational effort increases sharply with the number of support points.
An alternative to using a continuous high degree interpolation polynomial is that piece by piece Interpolation by low-degree polynomials. Special procedures of this kind, e.g. natural splines or B-spline curves, are discussed in detail later.