Interpolation by Newton's method according to given tabular data. Newton's interpolation formulas
Send your good work in the knowledge base is simple. Use the form below
Students, graduate students, young scientists who use the knowledge base in their studies and work will be very grateful to you.
Posted on http://www.allbest.ru/
Moscow State University Instrumentation and Informatics Sergiev Posad Branch
Abstract on the topic:
Newton's interpolation formulas
Completed by: Brevchik Taisiya Yurievna
2nd year student of EF-2 group
1. Introduction
2. Newton's first interpolation formula
3. Newton's second interpolation formula
Conclusion
Bibliography
Introduction
Interpolation, interpolation - in computational mathematics, a way to find intermediate values of a quantity from an existing discrete set of known values.
Many of those who deal with scientific and engineering calculations often have to operate on sets of values obtained by empirical or random sampling. As a rule, on the basis of these sets, it is required to construct a function on which other obtained values could fall with high accuracy. Such a task is called approximation. Interpolation is a type of approximation in which the curve of the constructed function passes exactly through the available data points.
There is also a problem close to interpolation, which consists in approximating some complex function another, simpler function. If a certain function is too complex for productive calculations, you can try to calculate its value at several points, and build, that is, interpolate, a simpler function from them.
Of course, using a simplified function does not allow you to get the same exact results as the original function would give. But in some classes of problems, the gain in simplicity and speed of computations can outweigh the resulting error in the results.
We should also mention a completely different kind of mathematical interpolation, known as "operator interpolation".
The classic works on operator interpolation include the Riesz-Thorin theorem and the Marcinkiewicz theorem, which are the basis for many other works.
Consider a system of non-coinciding points () from some area. Let the values of the function be known only at these points:
The problem of interpolation is to find such a function from a given class of functions that
The points are called interpolation nodes, and their totality is called the interpolation grid.
The pairs are called data points or base points.
The difference between "adjacent" values is the step of the interpolation grid. It can be both variable and constant.
A function is an interpolating function or an interpolant.
1. Newton's first interpolation formula
1. Description of the task. Let the values for the equally spaced values of the independent variable be given for the function: , where - interpolation step. It is required to choose a polynomial of degree at most, taking the values at the points
Conditions (1) are equivalent to
Newton's interpolation polynomial looks like:
It is easy to see that polynomial (2) completely satisfies the requirements of the problem. Indeed, firstly, the degree of the polynomial is not higher, and secondly,
Note that at , formula (2) turns into a Taylor series for the function:
For practical use, Newton's interpolation formula (2) is usually written in a somewhat transformed form. To do this, we introduce a new variable according to the formula; then we get:
where represents number of steps needed to reach the point, starting from the point. This is the final look Newton's interpolation formula.
Formula (3) is advantageous to use to interpolate the function in the vicinity of the initial value , where is small in absolute value.
If an unlimited table of function values is given, then the number in the interpolation formula (3) can be any number. In practice, in this case, the number is chosen so that the difference is constant with a given degree of accuracy. Any table value of the argument can be taken as the initial value.
If the table of function values is finite, then the number is limited, namely: it cannot be greater than the number of function values reduced by one.
Note that when applying Newton's first interpolation formula, it is convenient to use a horizontal table of differences, since then desired values function differences are in the corresponding horizontal line of the table.
2. Example. Taking a step, construct a Newton interpolation polynomial for the function given by the table
The resulting polynomial makes it possible to predict. Sufficient accuracy is obtained when solving an interpolation problem, for example, . The accuracy drops when solving an extrapolation problem, for example, .
2. Newton's second interpolation formula
Newton's first interpolation formula is practically inconvenient for interpolating a function near the nodes of the table. In this case, it is usually used .
Task Description . Let we have a sequence of function values
for equidistant values of the argument, where is the interpolation step. We construct a polynomial of the following form:
or, using the generalized power, we get:
Then, when the equality is satisfied, we get
Let us substitute these values into formula (1). Then, finally, Newton's second interpolation formula looks like:
Let us introduce a more convenient notation for formula (2). Let then
Substituting these values into formula (2), we obtain:
This is the normal view Newton's second interpolation formula. For an approximate calculation of the values of the function, it is assumed:
Both the first and second Newton interpolation formulas can be used to extrapolate a function, i.e. to find function values for argument values that lie outside the table.
If and is close to, then it is advantageous to use Newton's first interpolation formula, and then. If and is close to, then it is more convenient to use Newton's second interpolation formula, moreover.
Thus Newton's first interpolation formula is commonly used for forward interpolation and extrapolating back, and Newton's second interpolation formula, on the contrary, for interpolation back and extrapolation forward.
Note that the extrapolation operation is, generally speaking, less accurate than the interpolation operation in the narrow sense of the word.
Example. Taking a step, construct a Newton interpolation polynomial for the function given by the table
Conclusion
interpolation newton extrapolation formula
In computational mathematics, interpolation of functions plays an essential role, i.e. construction of a given function of another (as a rule, simpler one), the values of which coincide with the values of the given function at a certain number of points. Moreover, interpolation has both practical and theoretical significance. In practice, the problem often arises of restoring continuous function according to its tabular values, for example, obtained in the course of some experiment. To calculate many functions, it turns out to be efficient to approximate them by polynomials or fractional rational functions. The theory of interpolation is used in the construction and study of quadrature formulas for numerical integration, to obtain methods for solving differential and integral equations.
Bibliography
1. V.V. Ivanov. Computer computing methods. Reference manual. Publishing house "Naukova Dumka". Kyiv. 1986.
2. N.S. Bakhvalov, N.P. Zhidkov, G.M. Kobelkov. Numerical methods. Publishing House "Laboratory of basic knowledge". 2003.
3. I.S. Berezin, N.P. Zhidkov. Calculation methods. Ed. FizMatLit. Moscow. 1962.
4. K. De Bor. Practical guide by splines. Publishing house "Radio and communication". Moscow. 1985.
5. J. Forsyth, M. Malcolm, K. Moler. Machine methods of mathematical calculations. Publishing house "Mir". Moscow. 1980.
Hosted on Allbest.ru
...Similar Documents
Application of the first and second Newton's interpolation formulas. Finding function values at points that are not tabular. Using Newton's formula for points that are not equidistant. Finding the value of a function using Aitken's interpolation scheme.
laboratory work, added 10/14/2013
Johann Carl Friedrich Gauss is the greatest mathematician of all time. Gaussian interpolation formulas that give an approximate expression for the function y=f(x) using interpolation. Areas of application of the Gauss formulas. The main disadvantages of Newton's interpolation formulas.
test, added 12/06/2014
Interpolation of a function at a point lying in the vicinity of the middle of the interval. Interpolation formulas of Gauss. Stirling's formula as the arithmetic mean of Gaussian interpolation formulas. Cubic spline functions as mathematical model thin rod.
presentation, added 04/18/2013
Continuous and point approximation. Interpolation polynomials of Lagrange and Newton. Global interpolation error, quadratic dependence. Least square method. Selection of empirical formulas. Piecewise constant and piecewise linear interpolation.
term paper, added 03/14/2014
Methods of chords and iterations, Newton's rule. Interpolation formulas of Lagrange, Newton and Hermite. Point quadratic approximation of a function. Numerical differentiation and integration. Numerical solution of ordinary differential equations.
course of lectures, added 02/11/2012
Implementation of interpolation using Newton's polynomial. Refinement of the value of the root on a given interval by three iterations and finding the calculation error. Application of the methods of Newton, Sampson and Euler in solving problems. Calculation of the derivative of a function.
control work, added 06/02/2011
In computational mathematics, the interpolation of functions plays an essential role. Lagrange formula. Interpolation according to the Aitken scheme. Newton's interpolation formulas for equidistant nodes. Newton's formula with divided differences. Spline interpolation.
control work, added 01/05/2011
Calculation of the derivative by its definition, using finite differences and based on Newton's first interpolation formula. Lagrange interpolation polynomials and their application in numerical differentiation. Runge-Kutta method (fourth order).
abstract, added 03/06/2011
Kіntsі vіznіtsі іrіznih order. Fallowing between the kіntsevy retailers and functions. Discrete and continuous analysis. Understanding about the division of retail. Newton's interpolation formula. Comparison of formulas of Lagrange and Newton. Interpolation for equal distance nodes.
test, added 02/06/2014
Finding Lagrange and Newton interpolation polynomials passing through four points of a given function, comparing their power representations. Solving the non-linear differential equation Euler's method. Solution of systems of algebraic equations.
A fairly common interpolation method is Newton's method. The interpolation polynomial for this method is:
P n (x) = a 0 + a 1 (x-x 0) + a 2 (x-x 0)(x-x 1) + ... + a n (x-x 0)(x-x 1)...(x-x n-1).
The problem is to find the coefficients a i of the polynomial P n (x). The coefficients are found from the equation:
P n (x i) = y i , i = 0, 1, ..., n,
allowing to write the system:
a 0 + a 1 (x 1 - x 0) = y 1;
a 0 + a 1 (x 2 - x 0) + a 2 (x 2 - x 0) (x 2 - x 1) = y 2;
- - - - - - - - - - - - - - - - - - - - - - - - - - - -
a 0 +... + a n (x n - x 0)(x n - x 1) ... (x n - x n-1) = y n ;
We use the finite difference method. If the nodes x i are given at regular intervals h, i.e.
x i+1 - x i = h,
then in the general case x i = x 0 + i×h, where i = 1, 2, ..., n. The last expression allows us to bring the equation to be solved to the form
y 1 \u003d a 0 + a 1 ×h;
y 2 = a 0 + a 1 (2h) + a 2 (2h)h;
- - - - - - - - - - - - - - - - - - -
y i = a 0 + a 1 ×i×h + a 2 ×i×h[(i-1)h] + ... + a i ×i!×h i ,
whence for the coefficients we obtain
where Dу 0 is the first finite difference.
Continuing the calculations, we get:
where D 2 y 0 is the second finite difference, which is the difference of the differences. The coefficient a i can be represented as:
Supplying the found values of the coefficients a i to the values for P n (x), we obtain the Newton interpolation polynomial:
Let's transform the formula, for which we introduce a new variable , where q is the number of steps required to reach the point x, moving from the point x 0 . After transformations we get:
The resulting formula is known as Newton's first interpolation formula, or Newton's formula for forward interpolation. It is advantageous to use it to interpolate the function y = f(x) in the vicinity of the initial value x – x 0 , where q is small in absolute value.
If we write the interpolation polynomial as:
then in a similar way, you can get the second Newton interpolation formula, or Newton's formula for interpolation "backward":
It is commonly used to interpolate a function near the end of a table.
When studying this topic, it is necessary to remember that interpolation polynomials coincide with given function f(x) at the interpolation nodes, and at other points, in the general case, will differ. The indicated error gives us the error of the method. The error of the interpolation method is determined by the residual term, which is the same for the Lagrange and Newton formulas and which allows us to obtain the following estimate for the absolute error:
|
If interpolation is carried out with the same step, then the formula for the remainder term is modified. In particular, when interpolating "forward" and "backward" according to Newton's formula, the expression for R(x) is somewhat different from each other.
Analyzing the resulting formula, it can be seen that the error R(x) is, up to a constant, the product of two factors, of which one, f (n+1) (x), where x lies inside , depends on the properties of the function f(x) and cannot be regulated, but the magnitude of the other,
determined solely by the choice of interpolation nodes.
If the arrangement of these nodes is unsuccessful, the upper bound of the module |R(x)| may be quite large. Therefore, the problem arises of the most rational choice of interpolation nodes x i (for a given number of nodes n) so that the polynomial P n+1 (x) has the smallest value.
Let the function y=f(x) be given on the segment , which is divided into n identical segments (the case of equidistant values of the argument). x=h=const. For each node x 0, x 1 =x 0 +h,..., x n =x 0 +n h, the values of the function are defined in the form: f(x 0)=y 0, f(x 1)=y 1,.. ., f(xn)=yn.
Finite differences of the first order y 0 = y 1 – y 0 y 1 = y 2 – y y n-1 = y n – y n-1. Finite differences of the second order 2 y 0 = y 1 – y 0 2 y 1 = y 2 – y y n-2 = y n-1 – y n-2 Finite differences of higher orders are defined similarly: k y 0 = k-1 y 1 – k-1 y 0 k y 1 = k-1 y 2 – k-1 y k y i = k-1 y i+1 – k-1 y i, i = 0,1,...,n-k.
Let the function y = f(x) be given values y i = f(x i) for equal values of independent variables: x n = x 0 +nh, where h is the interpolation step. It is necessary to find a polynomial P n (x) of degree not higher than n, which takes the following values at points (nodes) x i: P n (x i) = y i, i=0,...,n. We write the interpolating polynomial in the form:
The task of constructing a polynomial is reduced to determining the coefficients a i from the conditions: P n (x 0)=y 0 P n (x 1)=y P n (x n)=y n
Other coefficients can be found similarly. The general formula has the form. Substituting these expressions into the polynomial formula, we obtain: where x i,y i are interpolation nodes; x is the current variable; h is the difference between two interpolation nodes h is a constant value, i.e. interpolation nodes are equally spaced from each other.
A feature of interpolation was that the interpolating function strictly passes through the nodal points of the table, i.e. the calculated values coincided with the table values: y i =f(x i). This feature was due to the fact that the number of coefficients in the interpolating function (m) was equal to the number of table values (n)
4. An interpolating function cannot describe tabular data in which there are several points with the same argument value. This situation is possible if the same experiment is carried out several times with the same initial data. However, this is not a limitation for the use of approximation, where the condition is not set for the graph of the function to pass through each point.
Newton's second formula has similar properties with respect to the left side of the table. To construct it, a polynomial of the form is used:
P n (x)=a 0 + a 1 (x-x n) + a 2 (x-x n)(x-x n-1) + …+ a n (x-x n)(x-x n-1)…(x-x 1), (6.3 .3-8)
where a i , i = 0, 1, 2, …, n are coefficients independent of the interpolation nodes.
To determine the coefficients a i we will alternately substitute interpolation nodes in (6.3.3-8). When x \u003d x n P n (x n) \u003d y n, therefore, a 0 \u003d y n.
At x = x n -1 we have P n (x n -1) = y n -1 = a 0 + a 1 (x n -1 -x n) = y n + a 1 (x n -1 -x n), whence
Continuing the substitution, we obtain an expression for all coefficients of the polynomial (6.3.3-8) and write down Newton's second interpolation formula:
Entering the designation:
and, substituting x into (6.3.3-8), we obtain Newton's formula for backward interpolation:
Let's use this formula to calculate the value of the function given in Table 6.3.3-1 at the point x = 1.7.
The point x=1.7 is located at the end of the table. As interpolation nodes, we choose : x 3 \u003d 1.8, x 2 \u003d 1.6 and x 1 \u003d 1.4 :
Errors of Newton's interpolation formulas are determined by the ratio:
For Newton's first formula:
(6.3.3-11)
For Newton's second formula:
(6.3.3-12)
where is some intermediate value between interpolation nodes.
In practice, if the interpolated function y = f(x) is given tabular, assuming that D n +1 = const, and h is sufficiently small, approximate equalities are used:
(6.3.3-13)
Example 6.3.3-1. Calculate using the 1st and 2nd Newton formulas the value of the function given by the table of equidistant nodes at the point x=1.23.
The practical error is estimated by the ratio:
e 1 \u003d | P 2 (x) - P 1 (x) | \u003d | 0.206958-0.206335 | \u003d 0.000623.
Let's solve the same problem using Newton's 2nd formula. Let x n = 1.3; x n -1 = 1.2; x n -2 = 1.1.
The finite difference table looks like:
x | y | Dy | D2y |
1.1 1.2 1.3 | 0.095310 0.182322 0.262364 | 0.087012 0.080042 | -0.006970 |
Then:
6.3.4. Spline - Interpolation
AT last years a new branch of modern computational mathematics is intensively developing - the theory splines. Splines make it possible to effectively solve the problems of processing experimental dependencies between parameters that have a rather complex structure.
The methods of local interpolation discussed above are essentially the simplest splines of the first degree (for linear interpolation) and the second degree (for quadratic interpolation).
The widest practical use, due to their simplicity, found cubic splines. The main ideas of the theory of cubic splines were formed as a result of attempts to mathematically describe flexible laths made of elastic material (mechanical splines), which have long been used by draftsmen in cases where it became necessary to draw a sufficiently smooth curve through given points. It is known that a rail made of an elastic material, fixed at certain points and being in an equilibrium position, takes a form in which its energy is minimal. This fundamental property makes it possible to effectively use splines in solving practical problems of processing experimental information.
In the general case, for the function y = f(x) it is required to find an approximation y = S(x) in such a way that f(x i) = S(x i) at the points x = x i , and at the other points of the interval the values of the functions f(x) and S(x ) were close to each other. With a small number of experimental points, one of the methods for constructing interpolation polynomials can be used to solve the interpolation problem. However, with a large number of nodes, interpolation polynomials become practically unusable. This is due to the fact that the degree of the interpolation polynomial is only one less than number experimental values of functions. It is possible, of course, to divide the segment on which the function is defined into sections containing a small number of experimental points, and for each of them construct interpolation polynomials. However, in this case, the approximating function will have points where the derivative is not continuous, i.e., the graph of the function will contain “break” points.
Cubic splines do not have this shortcoming. Studies have shown that a flexible thin ruler between two nodes is described quite well by a cubic polynomial, and since it does not collapse, the approximating function must be at least continuously differentiable.
In this way, spline is a function that is an algebraic polynomial on each partial interval of interpolation, and is continuous along with several of its derivatives on the entire given interval.
Let the interpolated function f(x) be given by its values y i , at nodes x i,
(i = 0, 1,...,n). Denote the length of the partial segment as h i =x i -x i-1 ,
(i = 1, 2,...,n) .
We will look for a cubic spline on each of the partial segments [х i-1 ;х i ] in the form:
where - four unknown coefficients. It can be proved that the problem of finding a cubic spline has a unique solution.
We require that the values of S(x) at the nodes coincide with the table values of the function f(x):
(6.3.4-2)
The number of these equations (2n) is two times less than the number of unknown coefficients. In order to obtain additional conditions, we also require the continuity of the first and second derivatives of the spline at all points, including nodes. To do this, equate the left and right derivatives S "(x-0), S" (x + 0), S "(x-0), S" (x + 0) at the internal node x i .
We calculate the expressions for the derivatives S "(x), S" (x) by successive differentiation (6.3.4-1):
S "(x) \u003d b i + 2c i (x–x i-1) + 3d i (x–x i - l) 2, (6.3.4-4)
S""(x) = 2c i + 6d i (x–x i - l),(6.3.4-5)
find the right and left derivatives at the node:
S "(x i -0) \u003d b i + 2ch i + 2d i h i,
S "(x i +0) \u003d b i + 1, where i \u003d 1,2, ..., n -1 .
We do the same for the second derivative:
S "(x–0) \u003d 2c i + 6d i h i,
S "(x + 0) \u003d 2c i + 1.
Equating the left and right derivatives, we get:
b i +1 = b i +2c i h i +2d i h i 2 (6.3.4-6)
with i+1 = with i - + 3d i h i , where i = 0, 1,..., n–1. (6.3.4-7)
Equations (6.3.4-6), (6.3.4-7) give 2(n–1) more conditions. To obtain the missing equations, requirements are imposed on the behavior of the spline at the ends of the interpolation segment. If we require zero curvature of the spline at the ends of the interpolation segment (i.e., the equality of the second derivative to zero), then we get:
with i =0, c n +3d n h n = 0. (6.3.4-8)
Eliminating from equations (6.3.4-2) - (6.3.4-3) n unknowns a i , we obtain a system of equations:
(6.3.4-9)
where i=0, 1,...., n - 1.
System (6.3.4-9) consists of 3(n-1) equations. Having solved the system (6.3.4-9), we obtain the values of the unknowns b i , c i , d i , which determine the set of all formulas for the desired interpolation spline:
where i = 0,1,...,n–1.(6.3.4-10)
The program that implements the spline interpolation method is quite cumbersome, so we will restrict ourselves to discussing the solution of the problem of sine interpolation using splines using the functions of the pp packages. 6.3.6.
Newton's first interpolation formula is practically inconvenient for interpolating a function near the nodes of the table. In this case, it is usually used .
Task Description . Let we have a sequence of function values
for equidistant values of the argument, where is the interpolation step. We construct a polynomial of the following form:
or, using the generalized power, we get:
Then, when the equality is satisfied, we get
Let us substitute these values into formula (1). Then, finally, Newton's second interpolation formula looks like:
Let us introduce a more convenient notation for formula (2). Let then
Substituting these values into formula (2), we obtain:
This is the normal view Newton's second interpolation formula. For an approximate calculation of the values of the function, it is assumed:
Both the first and second Newton interpolation formulas can be used to extrapolate a function, i.e. to find function values for argument values that lie outside the table.
If and is close to, then it is advantageous to use Newton's first interpolation formula, and then. If and is close to, then it is more convenient to use Newton's second interpolation formula, moreover.
Thus Newton's first interpolation formula is commonly used for forward interpolation and extrapolating back, and Newton's second interpolation formula, on the contrary, for interpolation back and extrapolation forward.
Note that the extrapolation operation is, generally speaking, less accurate than the interpolation operation in the narrow sense of the word.
Example. Taking a step, construct a Newton interpolation polynomial for the function given by the table
Solution. We compile a table of differences (table 1). Since the differences of the third order are practically constant, in formula (3) we set Accepting, we will have:
This is the desired Newton interpolation polynomial.
Table 1
|
|
|
|