Interpolation

The interpolation solve the problems of finding the analytical expression of a function g (x) which serves to bring another function f (x) for x in a range [a, b]. Problems like this appear in theory and practice with great frequency ; sometimes because an analytical expression for the function f (x) is not known, but isolated values ​​f (x1), f (x2), …, f (xn) of the same and it is necessary to have an analytical expression that allow, albeit roughly, to evaluate the function at other values ​​of x; at other times the algebraic algorithm In order to calculate f (x), although it is known, it is so complicated that we prefer to find a function g (x) of a simpler class and use it instead of f (x), even knowing that an error is being made.

Summary

[ hide ]

  • 1 Basic Concepts
  • 2 Polynomial Interpolation
  • 3 Splines
    • 1 Cubic Spline
    • 2 Applications
  • 4 Sources

Basic concepts

The image shows the different values ​​that a function takes , in the example it happens with the aim of finding a relationship between the weight and the height of a certain population sector, a sample of 100 individuals from the group is randomly selected and we obtain for each person i, their weight (pi) and their height (ti). By plotting these measurements on a pt axis system, a point diagram like the one shown in the figure is obtained. We want to find a formula that allows us to establish a relationship between the weight p and the height t of the individuals in the group.

If we know the values ​​that the function f (x) takes at the n + 1 different points x0, x1, …, xn, the interpolation problem consists of finding a function g (x) whose values ​​can be calculated for any x in an interval containing x0, x1, …, xn, such that:

g (x0) = f (x0)
g (x1) = f (x1)
g (xn) = f (xn)

The numbers x0, x1, …, xn are often called points or node of interpolation . If x is not an interpolation node, the real number g (x) is called an interpolated value. The phrase extrapolated value is often used to refer to g (x) when x is greater than the largest interpolation node or less than the smallest of them. The function g (x) is called the interpolator function and must be simple enough to make it easy and quick to evaluate it at the desired points; For this reason, it is most common to use small-degree polynomials for this purpose.

Functional approximation

The difference between the interpolated function and the interpolator is called an interpolation error and is denoted R (x), that is:

R (x) = error (g (x)) = f (x) – g (x)

The interpolation error depends on x; it is zero if x is an interpolation node and generally increases as x is further from the nodes. In particular, the interpolation error is usually much larger (in absolute value) in extrapolation than interpolation cases.

 

Polynomial interpolation

When the interpolating function is a polynomial, the interpolation is called a polynomial. If the set {x0, x1, …, xn} of interpolation nodes is assumed to be known, for which the images of the function f are known: yi = f (xi)
i = 0, 1, …, n
There are three fundamental problems related to polynomial interpolation: Is there any polynomial p (x) such that p (xi) = yi for i = 0, 1, …, n?

  1. a) Existence: b) Uniqueness: If such a polynomial exists, will it be unique? c) Construction: If the interpolating polynomial exists and it is unique, how to find it?

Given n + 1 different interpolation nodes: x0, x1, …, xn of a function f, then: If m <n It cannot be ensured that in Pm there is some polynomial that interpolates the function. If m> n In Pm there are cubic expressions that have infinite polynomials that interpolate the function If m = n There exists in Pm one and only one polynomial that interpolates the function.

Splines

In very general terms, a spline function is a piecewise polynomial function that is continuous and has continuous derivatives up to a certain order. In addition to the conditions of continuity and smoothness, the spline must satisfy some other conditions appropriate to the problem to be solved: go through a set of points on the graph of f (x) (interpolator spline), approximate a set of experimental points (best fit spline), meet certain aesthetic requirements and also in terms of value at some control points (graphic design problems), etc. To achieve all these conditions, the splinecontains a set of parameters whose values ​​are chosen so that all desired conditions are satisfied. To refine ideas, suppose a set of n + 1 numbers in increasing order {x0, x1, …, xn} and using polynomials of degree k, then the spline s (x) is a function of the form:

where pi (x) (i = 1, 2, …, n) represents a polynomial of degree k. As a polynomial of degree k has k + 1 coefficients, the spline as a whole has n (k + 1) coefficients and will be able to satisfy the same number of conditions as long as they do not contain contradictions that make them incompatible. The fact that s (x) must be continuous at all interior nodes {x1, x2, …, xn – 1} already represent n – 1 conditions. To achieve that the spline also has several continuous derivatives, it is necessary to take a degree k high enough so that the number of parameters allows satisfying all the required conditions. Given the limited interest of this text, here we will only consider the spline as an interpolation function and formed by polynomials of degree less than or equal to 3, that is, the interpolating cubic spline.

Cubic Spline

This type of interpolation has been shown to have great finesse and is even used for computer-aided design, for example, of typefaces. This interpolation is called a segmental interpolation or spline interpolation. The main idea is that instead of using a single polynomial to interpolate all the data, you can use segments of polynomials between coordinate pairs of data and link each one appropriately to fit the data. It is worth noting that among all the ways to fit data, cubic splinesThey have turned out to be the most suitable for any type of application. Thus, it can be informally said that a spline function is made up of several polynomials, each defined in an interval and that are joined together under certain conditions of continuity.

For a large set of points it is not very useful to calculate the interpolating polynomial that passes through these points, since it tends to have large oscillations. More advisable is to do a sequential interpolation of low degree on smaller subsets of the total points, thus defining a piecewise function.

The most useful and widely used piece interpolation in various fields such as design, computer graphics, economics, etc., is the one made by three degree polynomials called tracers or cubic splines that are defined in each of the sub intervals (xk, xk +1) defined by the abscissa of the points (xi, yi) to interpolate.

The idea is to construct these cubic polynomials in such a way that any two of them defined in contiguous intervals (xk −1, xk) and (xk, xk +1), both coincide in xk not only as a function but also in its first and second derived , so that there is smoothness in the points of coincidence (xk, yk) of both graphs. In each sub interval (xi-1, xi). • s (x) has a continuous derivative up to order k-1 in (xo, xn).

Applications

Engineering and Design (CAD / CAM, CNC’s) frequency Aeronautical and Automotive Geology Economics Signal and image processing (Pattern recognition, image recovery) Robotics Medicine (Hearing aids, brain maps) Meteorology (Climate maps, flood detection, .. .

 

Leave a Comment