You get a bonus - 1 coin for daily activity. Now you have 1 coin

3. Approximation of functions

Lecture



Local interpolation:
Piece-constant interpolation
Piecewise Linear Interpolation
Cubic interpolation spline
Global interpolation:
Polynom lagrange
Selection of empirical formulas
Least square method

Approximate - it means "to replace approximately." Suppose we know the values ​​of some function at given points. It is required to find the intermediate values ​​of this function. This is the so-called function recovery problem. In addition, when performing calculations, it is convenient to replace complex functions with algebraic polynomials or other elementary functions that are rather simply calculated ( the function approximation problem ).

Statement of the interpolation problem

On the interval [a, b] the points x i , i = 0, 1, ..., N; a ≤ x i ≤ b, and the values ​​of the unknown function at these points are f i , i = 0, 1, ...., N. It is required to find the function F (x) that takes the same values ​​of f i at points x i . Points 3. Approximation of functions are called interpolation nodes , and the conditions F (x i ) = f i . - interpolation conditions . Moreover, we look for F (x) only on the segment [a, b]. If it is necessary to find a function outside the segment, then this is an extrapolation problem. For now, we will only consider interpolation tasks.

The task has many solutions, since through given points ( x i , f i ), i = 0, 1, ..., N, one can draw infinitely many curves, each of which will be a graph of a function for which all the interpolation conditions are satisfied. For practice, the important case is the approximation of a function by polynomials, i.e. 3. Approximation of functions .

All interpolation methods can be divided into local and global . In the case of local interpolation at each interval [ x i– 1 , x i ] built a separate polynomial. In the case of global interpolation, a single polynomial is found over the entire interval [ a, b ] . In this case, the desired polynomial is called an interpolation polynomial .

Local interpolation

Piece-constant interpolation

On each segment 3. Approximation of functions the interpolation polynomial is equal to a constant, namely, the left or right value of the function.

For left piecewise linear interpolation 3. Approximation of functions i.e.

3. Approximation of functions

For the right piecewise linear interpolation 3. Approximation of functions i.e.

3. Approximation of functions

It is easy to understand that the interpolation conditions are satisfied. The constructed function is discontinuous), which limits its application. For the left piecewise linear interpolation, we have a graphical representation:

3. Approximation of functions

Piecewise Linear Interpolation

At each interval [ x i – 1 , x i ] function is linear 3. Approximation of functions . The values ​​of the coefficients are found from the fulfillment of the interpolation conditions at the ends of the segment: 3. Approximation of functions . We obtain the system of equations: 3. Approximation of functions , where do we find 3. Approximation of functions 3. Approximation of functions . Therefore, the function F (z) can be written in the form:

3. Approximation of functions i.e.

3. Approximation of functions

Or F(x) = k i * (x - x i-1 ) + f i-1 ,
k i = (f i - f i-1 ) / (x i - x i-1 ), x i-1 ≤ x ≤ x i , i=1,2,...,N-1
F(x) = k i * (x - x i-1 ) + f i-1 ,
k i = (f i - f i-1 ) / (x i - x i-1 ), x i-1 ≤ x ≤ x i , i=1,2,...,N-1

When using linear interpolation, you must first determine the interval in which the value of x falls, and then substitute it into the formula.

The resulting function will be continuous, but the derivative will be discontinuous at each interpolation node. The error of such interpolation will be less than in the case of piecewise – constant interpolation. An illustration of the piecewise linear interpolation is shown in the figure.

3. Approximation of functions

Example: Some function values ​​are given:

x 0 2 3 3.5
f -one 0.2 0.5 0.8

It is required to find the value of the function at z = 1 and z = 3.2 by piecewise – constant and piecewise – linear interpolation.

Decision. Point z = 1 belongs to the first local segment [0, 2], i.e. 3. Approximation of functions and, therefore, according to the formulas of the left piecewise – constant interpolation F (1) = f 0 = - 1 , according to the formulas of the right piecewise – interpolation constant F (1) = f 1 = 0.2 . We use the piecewise linear interpolation formulas:

3. Approximation of functions 3. Approximation of functions .

The point z = 3.2 belongs to the third interval [3, 3.5], i.e. 3. Approximation of functions and, therefore, according to the formulas of the left piecewise - constant interpolation F (3.2) = 3. Approximation of functions = 0.5, according to the formulas of the right piecewise - constant interpolation F (3.2) = 3. Approximation of functions = 0.8. We use the piecewise linear interpolation formulas:

3. Approximation of functions 3. Approximation of functions

Cubic interpolation spline

The word spline (the English word "spline") means a flexible ruler used to draw smooth curves through given points on a plane. The shape of this universal piece on each segment is described by a cubic parabola. Splines are widely used in engineering applications, in particular, in computer graphics. So, on each i –th segment [ x i –1 , x i ] , i = 1, 2, ..., N, the solution will be sought in the form of a third degree polynomial:

S i ( x ) = a i + b i ( x – x i ) + c i ( x - x i ) 2/2 + d i ( x – x i ) 3/6

Unknown coefficients a i , b i , c i , d i , i = 1, 2, ..., N, we find from:

• interpolation conditions: S i ( x i ) = f i , i = 1, 2, ..., N ; S 1 ( x 0 ) = f 0 ,

• continuity of the function S i ( x i– 1 ) = S i– 1 ( x i –1 ) , i = 2, 3, ..., N,

• continuity of the first and second derivative:

S / i ( x i– 1 ) = S / i– 1 ( x i –1 ) , S // i ( x i –1 ) = S // i –1 ( x i –1 ) , i = 2, 3, ..., N.

Considering that 3. Approximation of functions , to determine 4 N unknowns, we obtain a system of 4 N –2 equations:

a i = f i , i = 1, 2, ..., N,

b i h i - c i h i 2/2 + d i h i 3/6 = f i - f i –1 , i = 1, 2, ..., N,

b i - b i – 1 = c i h i - d i h i 2/2 , i = 2, 3, ..., N,

d i h i = c i - c i– 1 , i = 2, 3, ..., N.

where h i = x i - x i– 1 . The missing two equations are derived from additional conditions: S // ( a ) = S // ( b ) = 0. It can be shown that in this case 3. Approximation of functions . The unknowns b i , d i can be excluded from the system by obtaining a system of N + 1 linear equations (SLAE) for determining the coefficients c i :

c 0 = 0 , c N = 0,

h i c i –1 + 2 ( h i + h i +1 ) c i + h i +1 c i +1 = 6 3. Approximation of functions , i = 1, 2, ..., N –1 . (one)

After that, the coefficients b i , d i are calculated :

3. Approximation of functions , i = 1, 2, ..., N. (2)

In the case of grid constant h i = h this the system of equations is simplified.

3. Approximation of functions

This SLAU has a three-diagonal matrix and is solved by the sweep method.

Coefficients 3. Approximation of functions are determined from the formulas:

3. Approximation of functions

To calculate the value of S ( x ) at an arbitrary point of the segment z ∈ [ a, b ], it is necessary to solve the system of equations for the coefficients c i , i = 1,2, ..., N –1 , then find all the coefficients b i , d i . Further, it is necessary to determine which interval [ x i 0 , x i 0–1 ] falls on this point, and, knowing the number i 0 , calculate the value of the spline and its derivatives at the point z

S ( z ) = a i 0 + b i 0 ( z – x i 0 ) + c i 0 ( z – x i 0 ) 2/2 + d i 0 ( z – x i 0 ) 3/6

S / ( z ) = b i 0 + c i 0 ( z – x i 0 ) + d i 0 ( z – x i 0 ) 2/2 , S // ( z ) = c i 0 + d i 0 ( z – x i 0 ) .

Example.

x 0 f 0

x 1 f 1

x 2 f 2

x 3 f 3

x 4 f 4

x

0

¼

1/2

3/4

one

f

one

2

one

0

one

It is required to calculate the values ​​of the function at points 0.25 and 0.8, using spline interpolation.

In our case: h i = 1/4, 3. Approximation of functions .

We write the system of equations to determine 3. Approximation of functions :

3. Approximation of functions

Solving this system of linear equations, we get: 3. Approximation of functions .

3. Approximation of functions

Consider the point 0.25, which belongs to the first segment, i.e. 3. Approximation of functions . Therefore, we get 3. Approximation of functions

Consider point 0.8, which belongs to the fourth segment, i.e. 3. Approximation of functions .

Consequently, 3. Approximation of functions

Global interpolation

In the case of global interpolation, a single polynomial is found over the entire interval [ a, b ], i.e. a polynomial is constructed, which is used to interpolate the function f (x) over the entire interval of variation of the argument x. We will look for the interpolating function in the form of a polynomial (polynomial) of m –th power P m ( x ) = a 0 + a 1 x + a 2 x 2 + a 3 x 3 +… + a m x m . What should be the degree of the polynomial in order to satisfy all interpolation conditions? Suppose that two points are given: ( x 0 , f 0 ) and ( x 1 , f 1 ), i.e. N = 1. A single straight line can be drawn through these points, i.e. the interpolating function is the first degree polynomial P 1 ( x ) = a 0 + a 1 x. Through three points (N = 2) one can draw a parabola P 2 ( x ) = a 0 + a 1 x + a 2 x 2 , etc. Reasoning in this way, we can assume that the desired polynomial must have degree N.

In order to prove this, we write out the system of equations for the coefficients. The equations of the system are the interpolation conditions in for each x = x i :

3. Approximation of functions

This system is linear with respect to the desired coefficients a 0 , a 1 , a 2 , ..., a N. It is known that SLAE has a solution if its determinant is non-zero. The determinant of this system

3. Approximation of functions

bears the name of the determinant of Vandermond . From the course of mathematical analysis it is known that it is non-zero if x k x m (i.e., all interpolation nodes are different). Thus, it is proved that the system has a solution.

We showed that to find the coefficients
a 0 , a 1 , a 2 , ..., a N need to solve SLAE, which is a difficult task. But there is another way to construct a polynomial of the Nth degree, which does not require solving such a system.

Polynom lagrange

The solution is sought in the form 3. Approximation of functions where l i ( z ) - basic polynomials N of degree for which the condition is satisfied: 3. Approximation of functions . Make sure that if such polynomials are constructed, then L N ( x) will satisfy the interpolation conditions:

3. Approximation of functions .

How to build basic polynomials ? Define

3. Approximation of functions , i = 0, 1, ..., N.

Easy to understand that

3. Approximation of functions , etc.

The function l i ( z ) is a polynomial of the Nth degree of z and for it the conditions of "basicity" are satisfied:

3. Approximation of functions = 0, i k ;, i.e. k = 1, ..., i-1 or k = i + 1, ..., N.

3. Approximation of functions .

Thus, we managed to solve the problem of constructing an N – th degree interpolating polynomial, and for this we need not solve the SLAE. Polynomial Lagrange can be written in the form of a compact formula: 3. Approximation of functions . The error of this formula can be estimated if the original function g ( x ) has derivatives up to the N + 1 order:

3. Approximation of functions .

From this formula it follows that the accuracy of the method depends on the properties of the function g ( x ) , as well as on the location of the interpolation nodes and the point z. As the calculated experiments show, the Lagrange polynomial has a small error for small values ​​of N <20 . For larger N, the error begins to increase, which indicates that the Lagrange method does not converge (that is, its error does not decrease with increasing N ).

Consider special cases. Let N = 1, i.e. values ​​of the function are given only at two points. Then the base polynomials are:

3. Approximation of functions 3. Approximation of functions i.e. we obtain formulas of piecewise linear interpolation.

Let N = 2. Then: 3. Approximation of functions

3. Approximation of functions

As a result, we obtained the formulas of the so-called quadratic or parabolic interpolation.

Example: Some function values ​​are given:

x 0 2 3 3.5
f -one 0.2 0.5 0.8

It is required to find the value of the function at z = 1, using the Lgrange interpolation polynomial. For this case, N = 3, i.e. Lagrange polynomial has a third order. Calculate the values ​​of the basis polynomials at z = 1 :

3. Approximation of functions

3. Approximation of functions

Selection of empirical formulas

When interpolating functions, we used the condition of equality of the values ​​of the interpolation polynomial and this function at the interpolation nodes. If the initial data are obtained as a result of experimental measurements, then the exact match requirement is not necessary, since the data are not obtained accurately. In these cases, you can only require approximate fulfillment of the interpolation 3. Approximation of functions . This condition means that the interpolating function F ( x) passes not exactly through the given points, but in some of their neighborhoods, for example, as shown in Fig.

3. Approximation of functions

Then they talk about the selection of empirical formulas . The construction of an empirical formula consists of two stages6 the selection of the form of this formula 3. Approximation of functions containing unknown parameters 3. Approximation of functions , and the definition of the best in some sense of these parameters. The form of the formula is sometimes known from physical considerations (for elastic media, the relationship between stress and strain) or selected from geometrical considerations: the experimental points are plotted and the general form of the dependence is approximately guessed by comparing the curve obtained with the well-known functions. Success here is largely determined by the experience and intuition of the researcher.

For practice, the important case is the approximation of a function by polynomials, i.e. 3. Approximation of functions .

After the type of empirical dependence is chosen, the degree of closeness to the empirical data is determined using the minimum of the sum of squared deviations of the calculated and experimental data.

Least square method

Let for the initial data x i , f i , i = 1 , ..., N (numbering is better to start with unity), the type of empirical dependence is chosen: 3. Approximation of functions with unknown coefficients 3. Approximation of functions . We write the sum of the squares of the deviations between the empirical calculated values ​​and the given experimental data:

3. Approximation of functions .

Options 3. Approximation of functions we will find from the condition of the minimum function 3. Approximation of functions . This is the least squares method (least squares).

It is known that at the minimum point all partial derivatives of 3. Approximation of functions by 3. Approximation of functions are zero:

3. Approximation of functions (one)

Consider the use of OLS for a particular case that is widely used in practice. As an empirical function, consider the polynomial

3. Approximation of functions 3. Approximation of functions .

Formula (1) to determine the sum of squared deviations will take the form:

3. Approximation of functions (2)

Calculate the derivatives:

3. Approximation of functions

Equating these expressions to zero and collecting coefficients for unknown 3. Approximation of functions , we obtain the following system of linear equations:

3. Approximation of functions

This system of equations is called normal. Solving this system of linear equations, we obtain the coefficients 3. Approximation of functions .

In the case of a first-order polynomial, m = 1, i.e. 3. Approximation of functions , the system of normal equations takes the form:

3. Approximation of functions

When m = 2, we have:

3. Approximation of functions

As a rule, choose several empirical dependencies. According to the OLS, the coefficients of these dependencies are found and among them they find the best by the minimum amount of deviations.

Example. The coordinates of the points are given:

x

-five

-3.5

-2

1.5

3.25

five

f

0.5

1.2

1.4

1.6

1.7

1.5

those. N = 6. It is required to find empirical dependencies: linear 3. Approximation of functions quadratic 3. Approximation of functions hyperbolic 3. Approximation of functions according to the OLS method and choose among them the best by the smallest sum of squared deviations.

The system of normal equations for linear dependence:

3. Approximation of functions

Given that N = 6, 3. Approximation of functions get

3. Approximation of functions

Solving a system of linear equations, we get 3. Approximation of functions . Therefore, the linear relationship is: 3. Approximation of functions .

Calculate the sum of the squares of deviations: 3. Approximation of functions .

Consider the quadratic dependence. The system of normal equations is

3. Approximation of functions

Find the uncounted amounts: 3. Approximation of functions

3. Approximation of functions

Solving SLAU, we get 3. Approximation of functions

Therefore, the quadratic dependence has the form: 3. Approximation of functions .

Calculate the sum of the squares of deviations: 3. Approximation of functions .

We write out the system of normal equations for hyperbolic dependence. According to the MNC, we find the sum of squared deviations:

3. Approximation of functions . We make the system of normal equations:

3. Approximation of functions

Or

3. Approximation of functions

Considering that 3. Approximation of functions get

3. Approximation of functions

Sum of squared deviations: 3. Approximation of functions

Of the three dependencies, we choose the best, i.e. quadratic.


Comments


To leave a comment
If you have any suggestion, idea, thanks or comment, feel free to write. We really value feedback and are glad to hear your opinion.
To reply

Numerical methods

Terms: Numerical methods