Natural cubic spline. Cubic splines

In industrial manufacturing, such as shipbuilding, automobile manufacturing, and aircraft manufacturing, the final shape at or near scale is determined through the finishing process.

Automation of this process represented significant interest for computer graphics. The shape of the mathematical spline follows the contour of the physical spline (Fig. 5-4), i.e. a flexible wooden or plastic ruler passing through certain points. Lead weights are used to change the shape of the spline. By changing their number and location, they try to make the resulting curve smoother, more beautiful and “pleasant to the eye.”

If we consider a physical spline as a thin flexible strip, its shape (deflection) is determined by the Euler equation (5-2) for the moment of bending along the strip:

where is Young's modulus, which depends on the properties of the rack material, is the moment of inertia, determined by the shape of the curve, and is the radius of curvature.

For small deviations the radius is approximately equal to

,

where the prime denotes the derivative with respect to the distance along the staff, and is the deflection of the staff. Euler's equation takes the form

Let the weights act as simple supports, then the bending moment between them changes linearly. Substituting into the Euler equation, we get

and after double integration

Thus, the shape of the spline is given by a cubic polynomial.

IN general case a mathematical spline is a piecewise polynomial of degree with a continuous derivative of the degree at the connecting points of the segments. For example, a cubic spline has second-order continuity at its connection points. Piecewise splines from polynomials of low order are very convenient for interpolating curves, since they do not require large computational costs and do not cause numerical deviations characteristic of polynomials high order. Similar to physical splines, a series of cubic segments are typically used, with each segment passing through two points. A cubic spline is also convenient because it is a curve of the smallest order, allowing inflection points and bending in space.

The equation of one parametric spline segment is:

, , (5-1)

where and are the parameter values ​​at the beginning and end of the segment. - vector to any point of the segment. is a vector-valued function, where the three components are Cartesian coordinates vector.

Rice. 5-5 One segment of a cubic spline.

Each component has a form similar to , i.e.

, ,

, ,

, .

The constant coefficients are calculated based on the four boundary conditions for the spline segment. Let's write equation (5-1) in the form

Let and be the vectors of the ends of the segment (see Fig. 5-5). Let also and , the derivatives with respect to , be tangent vectors at the ends of the segment. Differentiating equation (5-1), we get

, . (5-3)

Let's write down the result

, . (5-4)

Let us assume, without loss of generality, that , and apply the boundary conditions

We get four equations for the unknowns:

, (5-6b)

, (5-6c)

. (5-6d)

Solutions for and have the form:

(5-7a)

. (5-7b)

The quantities , , and define the cubic spline segment. Obviously, the shape of a segment depends on the position and tangent vectors at the ends of the segment. Next, note that the results contain the parameter value at the end of the segment. Since each endpoint and tangent vector has three components, the parametric equation of a cubic space curve depends on the twelve vector components and the value of the parameter at the end of the segment.

Substituting equations (5-6) and (5-7) into (5-1), we obtain the equation for one segment of a cubic spline:

. (5-8)

This is an equation for one segment. To get the entire curve, you need to connect many segments. In Fig. 5-6 show two adjacent segments. If the vectors , , , tangent vectors , , and the values ​​of the parameters , , are known, then the shape of each segment is determined from equation (5-8). However, it is unlikely that the tangent vector at the connection point is known. Fortunately, it can be derived from the continuity condition.

Recall that a piecewise degree spline has degree continuity at its join points; the continuity of a cubic spline is two. To do this, the second derivative or curvature of the line must be continuous. Differentiating equation (5-1) twice, we get

, . (5-9)

Rice. 5-6 Two piecewise cubic spline segments.

For the first piece of the spline, the parameter varies within . Let's substitute into equation (5-9):

.

For the second section of the spline, the parameter changes in the range. Let's substitute into equation (5-9) the value at the beginning of the second section

Equating the results obtained and using equations (5-6a,b) and (5-7a), we obtain

.

The left side of this equation represents the curvature at the end of the first segment, and the right side represents the curvature at the beginning of the second. Multiply by and group the terms:

This determines , the unknown tangent vector at the connection point. Note that the final equation again contains parameter values ​​at the ends of the segments and .

The resulting formula can be generalized for points, and for segments of a cubic spline, second-order continuity can be obtained at the connection points.

Rice. 5-7 Designations for the set of piecewise cubic spline segments.

The generalized equation for any two adjacent spline segments and in the notation of Fig. 5-7 looks like:

(5-11)

for the first segment and

(5-12)

for the second, since for each segment the parameter begins to change from zero, for the first and for the second - .

Equating second derivatives at joining points for any adjacent segments, , gives overall result, equivalent to equation (5-10),

from which the tangent vector is determined at the connection points of any two segments and .

Recursive use of equation (5-13) for all segments of the spline generates tangent vector equations , . IN matrix form:

(5-14)

The matrix is ​​non-square, since there are only equations for vectors, and it cannot be inverted to obtain a solution for . If we assume that the tangent vectors at the ends of the curve and are known, the problem is resolved. Now the matrix looks like

(5-15)

where the matrix is ​​square and invertible. Note also that it is tridiagonal, which reduces the computational costs of its inversion. Further, the matrix is ​​diagonally dominant. It follows that she has only decision:

. (5-16)

If we know , then it is easy to determine the coefficients for each spline segment. Generalizing equations (5-6)-(5-11), we get

,

.

Since and is vector quantities, then they are also vector; if they have components, then they also have these components.

In matrix form, the equation of any spline segment is:

. (5-17)

Let it be required to specify a cubic spline passing through the points , with tangent vectors at the ends and . From equation (5-16) we find the internal tangent vectors , . Then, from equation (5-17) with the known coordinates of the ends of each segment and the tangent vectors, , , are determined for each segment. Final generalization of equation (5-1)

, , , (5-18)

used to calculate a spline segment.

In matrix form, equation (5-18) looks like this:

, . (5-19)

Substituting equation (5-17) and rearranging the terms, we get

, , , (5-20)

, (5-21a)

, (5-21b)

, (5-21s)

, (5-21d)

are called weight functions.

Rice. 5-8 Cubic spline weighting functions for

Using these definitions, we write equation (5-20) in matrix form

where is the matrix of the weight function

contains geometric information. As will be seen from what follows, equations like (5-22), i.e. a weighting function matrix multiplied by a matrix of geometric conditions, often used to describe curves and surfaces.

From equation (5-21) it is clear that each weight function is of third order. Any point on a cubic spline segment is a weighted sum of endpoints and tangent vectors. The coefficients act as weighting functions. In Fig. 5-8 are shown for . From the figure it is clear that and , i.e. the curve passes through the point vector. Similarly and, i.e. the curve also passes through the point vector. Next, we note the symmetry of and , and and . Actually . Finally, let's pay attention to the relative order of , , and . The significant difference in magnitude suggests that, in general, the position of the endpoints has a greater influence than the tangent vectors.

Recall that a piecewise cubic spline is defined by points, tangent vectors and parameter values, i.e., at the ends of all segments. The choice affects the smoothness of the curve.

The continuity of the second derivative at the internal connection points does not in itself ensure the smoothness of the curve in the sense of minimal curvature along it. By selecting appropriate values, it is possible to minimize the coefficients for each segment and achieve greater smoothness of the curve. Typically these additional calculations are not required. For practical purposes, more than simple methods, like those discussed here.

One calculation method is to set parameter values equal lengths chords between adjacent points. At the same time, the quality of the curve meets the requirements of most applied problems. Another method is to normalize the variation by taking equal to one for each spline segment. This choice simplifies the calculations (see Section 5-4). As can be seen from the above equations, any choice results in different coefficients and hence different curves passing through given points.

Let's look at an example.

Let's consider the problem of drawing smooth curves along given boundary points, or the interpolation problem. Since any number of smooth curves can be drawn through two points, to solve this problem it is necessary to limit the class of functions that will determine the desired curve. Mathematical splines are functions used to approximate curves. Their important property is ease of calculation. In practice, splines of the form of third-degree polynomials are often used. With their help, it is quite convenient to draw curves that intuitively correspond to the human subjective concept of smoothness. The term “spline” comes from the English spline, which means a flexible strip of steel that was used by draftsmen to draw smooth curves, for example, to construct the contours of ships or airplanes.

Let's first consider a spline function for plotting a function of one variable. Let a sequence of points , , and , be given on the plane. Let us define the required function and set two conditions:

1) The function must pass through all given points: , .

2) The function must be twice continuously differentiable, that is, have a continuous second derivative on the entire interval.

On each of the segments, we will look for our function in the form of a third-degree polynomial:

.

Rice. 40. Spline function.

The task of constructing a polynomial comes down to finding the coefficients. Since for each of the segments it is necessary to find 4 coefficients, the total number of required coefficients will be . To find all the coefficients, we determine the corresponding number of equations. The first equations are obtained from the conditions for the coincidence of the function values ​​at the internal nodes , . The following equations we obtain similarly from the conditions for the coincidence of the values ​​of the first and second derivatives at the internal nodes. Together with the first condition we obtain the equations. The missing two equations can be obtained by specifying the values ​​of the first derivatives at the end points of the segment. This way boundary conditions can be specified.

Let's move on to more difficult case– setting curves in three-dimensional space. In the case of a functional specification of a curve, ambiguity is possible in the case of self-intersections and inconvenience when the values ​​of the derivatives are equal. In view of this, we will look for a function in parametric form. Let be an independent parameter such that . We call a cubic parametric spline the following system equations:

The coordinates of points on the curve are described by the vector , and the three derivatives specify the coordinates of the corresponding tangent vector at the point. For example, for the coordinate:

.

One way to specify a parametric cubic spline is to specify the coordinates of the initial and end points, as well as the tangent vectors in them. This way of specifying is called the Hermite form. Let us denote the end points and , and the tangent vectors at them and . The indices were chosen in this way taking into account the further presentation.

We will solve the problem of finding the four coefficients, since for the remaining two equations the coefficients are found in a similar way. Let's write down the condition for constructing a spline:

Let's rewrite the expression for vector form:

.

Let us denote the vector string and a vector column of coefficients, then .

From (*) it follows that , . For tangents ,

From here we get the vector-matrix equation:

.

This system can be solved by finding inverse matrix size .

.

Here is a Hermitian matrix, - geometric vector Ermita. Let's substitute the expression to find: . Similarly for other coordinates: , .

Let us write out explicit formulas for calculating the coordinates of spline points. Since , then multiplying from the right by , we get:

.

The four functions in parentheses are called conjugation functions.

The shape of a curve given in Hermite form can be easily changed if we take into account that the direction of the tangent vector is given by starting direction, and the module of the tangent vector specifies the degree of elongation of the curve in the direction of this vector, as shown in Fig. 41.

Rice. 41. Parametric spline in Hermite form. The elongation of the curve to the right is ensured by the fact that .

Let's consider the Bezier form, which differs from the Hermite form in the way of specifying boundary conditions, namely, instead of vectors, points (and the corresponding radius vectors) and are introduced, as shown in Fig. 42, such that the conditions are met: And .

Rice. 42. Parametric spline in Bezier form.

The transition from the Hermite form to the Bezier form is carried out by the transformation:

, (*)

where is the geometric Bezier vector. Substituting this into the expression for , we get

A useful property of Bezier splines is that the curve always lies inside the convex hull formed by the quadrilateral. This property can be proven using the fact that in the expression (*) the coefficients take values ​​from 0 to 1 and their sum is equal to one.

Note that the matrix is ​​of the form

- called the Bezier matrix.

Bibliography

1. Newman, Sproull, Fundamentals of Interactive Computer Graphics, M. Mir, 1976.

2. Angel Y. Practical Introduction in computer graphics, Radio and Communications, 1984.

3. A. Van-Dam, J. Foley, Fundamentals of Interactive Computer Graphics, vol. 1-2, M. Mir, 1985.

4. E.V. Zhikin, A.V.Boreskov, Computer graphics. Dynamics, realistic images, M., Dialog-MEPhI, 1995, 1997.

5. L. Ammeral, Machine graphics in the C language, in 4 volumes, Sol. System, 1992.

6. The computer gains intelligence. Per. from English Ed. V.L. Stefanyuk, M. Mir, 1990.

7. Rogers, algorithmic foundations of computer graphics. M. Mir, 1989.

8. Grice, Graphic tools of personal computers, M., Mir, 1980.

9. Rogers, Adams, Mathematical Basics machine graphics, M. Mechanical engineering, 1985.

10. Giloy, Interactive computer graphics, M., Mir, 1981.

11. F. Preparata, M. Sheimos, Computational geometry: Introduction, M. Mir, 1989.

12. A. Fox, M. Pratt, Computational Geometry, M., Mir, 1982.

13. A.B. Boreskov, E.V. Shikina, G.E. Shikina, Computer graphics: first acquaintance, Ed. E.V. Shikina, M., Finance and Statistics, 1996.

14. A.V. Frolov, G.V. Frolov, GDI graphical interface in MS WINDOWS, Moscow, Dialogue-MEPhI Publishing House, 1994.

15. Michael Laszlo, Computational Geometry and computer graphics in C++, Moscow, Binom, 1997.

16. Yu. Tikhomirov, Programming three-dimensional graphics, St. Petersburg: BHV-St. Petersburg, 1999.

17. A. Khonich, How to create a three-dimensional game yourself. M.: MIKROART, 1996.

18. M. Marov, 3D Studio MAX 2.5: reference book - St. Petersburg: “Peter”, 1999. – 672 p.

19. A. La Mote, D. Ratcliffe and others. Secrets of game programming / Translated from English. – St. Petersburg: Peter, 1995. – 720 p.

20. N. Thompson, Secrets of programming three-dimensional graphics for Windows 95. Translation from English. – St. Petersburg: Peter, 1997. – 352 p.

* In this definition, when replacing, say, the Oz axis with the Ox axis, the remaining axes are replaced according to the rule of cyclic permutation, that is, Oy will be replaced by Oz, and Ox will be replaced by Oy. There can be three cyclic permutations: (x,y,z)®(y,z,x)®(z,x,y).

*More strict definition homogeneous coordinates is given in section linear algebra"Projective spaces".

POINT POINT DESCRIPTION OF SURFACES.

The method consists in specifying a surface with a set of points belonging to it. Consequently, the image quality with this method depends on the number of points and their location.

Point-by-point description used in cases where the surface is very complex and does not have smoothness, and a detailed representation geometric features important for practice.

Example: Soil areas on other planets, shapes celestial bodies, information about which was obtained as a result of satellite imagery. Microobjects taken using electron microscopes.

Initial information about point-wise described objects is presented in the form of a matrix 3D coordinates points.

Splines are smooth (having several continuous derivatives) piecewise polynomial functions that can be used to represent functions given big amount values ​​and for which approximation by a single polynomial is not applicable. Since splines are smooth, economical and easy to work with, they are used in constructing arbitrary functions for:

o curve modeling;

o data approximation using curves;

o performing functional approximations;

o solving functional equations.

Let's consider the problem of drawing smooth curves along given boundary points, or the interpolation problem. Since any number of smooth curves can be drawn through two points, to solve this problem it is necessary to limit the class of functions that will determine the desired curve. Mathematical splines are functions used to approximate curves. Their important property is ease of calculation. In practice, splines of the form of third-degree polynomials are often used. With their help, it is quite convenient to draw curves that intuitively correspond to the human subjective concept of smoothness. The term “spline” comes from the English spline, which means a flexible strip of steel that was used by draftsmen to draw smooth curves, for example, to construct the contours of ships or airplanes.

Let's first consider a spline function for plotting a function of one variable. Let a sequence of points , be given on the plane, and . Let us define the required function and set two conditions:

1) The function must pass through all points: , ;

2) The function must be twice continuously differentiable, that is, have a continuous second derivative on the entire interval.

On each of the segments , , we will look for our function in the form of a third-degree polynomial:

.

Spline function

The task of constructing a polynomial comes down to finding the coefficients. Since for each of the segments it is necessary to find 4 coefficients, the total number of required coefficients will be . To find all the coefficients, we determine the corresponding number of equations. The first equations are obtained from the conditions for the coincidence of the function values ​​at the internal nodes ,. The following equations are obtained similarly from the conditions for the coincidence of the values ​​of the first and second derivatives at the internal nodes. Together with the first condition we obtain the equations. The missing two equations can be obtained by specifying the values ​​of the first derivatives at the end points of the segment. This way boundary conditions can be specified.

Let's move on to a more complex case - defining curves in three-dimensional space. In the case of a functional specification of a curve, ambiguity is possible in the case of self-intersections and inconvenience when the values ​​of the derivatives are equal. In view of this, we will look for the function in parametric form. Let be an independent parameter such that . Let us call the following system of equations a cubic parametric spline:

The coordinates of points on the curve are described by the vector, and the three derivatives specify the coordinates of the corresponding tangent vector at the point. For example, for the coordinate:

One way to specify a parametric cubic spline is to specify the coordinates of the start and end points, as well as the tangent vectors at them. This way of specifying is called the Hermite form. Let us denote the end points and , and the tangent vectors at them and . The indices were chosen in this way taking into account the further presentation.

We will solve the problem of finding the four coefficients, since for the remaining two equations the coefficients are found in a similar way. Let's write down the condition for constructing a spline:

Let's rewrite the expression for in vector form:

.

Let us denote the row vector and the column vector of the coefficients, then .

From (*) it follows that, . For tangents ,

From here we get the vector-matrix equation:

.

This system is solved by finding the inverse matrix of size .

.

Here is the Hermitian matrix, and is the geometric Hermite vector. Let's substitute the expression to find: . Similarly for other coordinates: , .

Curves and surfaces found in practical problems, often have quite complex shape, which does not allow universal analytical task in general with the help elementary functions. Therefore, they are assembled from relatively simple smooth fragments - segments (curves) or cuts (surfaces), each of which can be quite satisfactorily described using elementary functions of one or two variables. In this case, it is quite natural to require that smooth functions that are used to construct partial curves or surfaces should be of a similar nature, for example, they should be polynomials to the same degree. And in order for the resulting curve or surface to be sufficiently smooth, you need to be especially careful where the corresponding fragments join. The degree of polynomials is chosen from simple geometric considerations and, as a rule, is small. To smoothly change the tangent along the entire composite curve, it is enough to describe the joined curves using polynomials of the third degree, cubic polynomials. The coefficients of such polynomials can always be chosen so that the curvature of the corresponding composite curve is continuous. Cubic splines, which arise when solving one-dimensional problems, can be adapted to the construction of fragments of composite surfaces. And here bicubic splines appear quite naturally, described using polynomials of the third degree in each of the two variables. Working with such splines requires a significantly larger amount of calculations. But right organized process will allow us to take into account continuously growing opportunities computer technology V maximum degree. Spline functions Let on the segment, that is, Remark. The index (t) of the numbers a^ indicates this. that the set of coefficients that determines the function 5(x) on each partial segment D is different. On each of the segments D1, the spline 5(x) is a polynomial of degree p and is determined on this segment by p + 1 coefficient. Total partial segments - then. This means that in order to completely determine the spline, it is necessary to find (p + 1)then numbers. Condition) means the continuity of the function 5(x) and its derivatives at all internal nodes of the grid w. The number of such nodes is m - 1. Thus, to find the coefficients of all polynomials, p(m - 1) conditions (equations) are obtained. For full definition the spline is missing (conditions (equations). The choice of additional conditions is determined by the nature of the problem under consideration, and sometimes simply by the user’s desire. SPLINE THEORY examples of solutions Interpolation and smoothing problems are most often considered when it is necessary to construct one or another spline from a given array of points on plane B interpolation problems require that the spline graph pass through points, which imposes m + 1 additional conditions (equations) on its coefficients. The remaining p - 1 conditions (equations) for unambiguous construction of the spline are most often specified in the form of the values ​​of the lower derivatives of the spline at the ends of the segment under consideration [. a, 6] - boundary (boundary) conditions. The ability to choose different boundary conditions allows you to construct splines with a variety of properties. In smoothing problems, the spline is constructed so that its graph passes near the points (i" "Y"), * = 0, 1,..., t, and not through them. The measure of this closeness can be defined in different ways, which leads to a significant variety of smoothing splines. The described options for choosing when constructing spline functions do not exhaust all their diversity. And if initially only piecewise polynomial spline functions were considered, then as the scope of their applications expanded, splines began to appear, “glued together” from other elementary functions. Interpolation cubic splines Statement of the interpolation problem Let a grid w be given on the segment [a, 6). Consider a set of numbers Problem. Construct a smooth function on the segment (a, 6] that takes the given values ​​at the grid nodes, that is, Note: The formulated interpolation problem is to restore smooth function, given in a table (Fig. 2). It is clear that such a problem has many various solutions. Overlaying on a constructed function additional conditions, the necessary unambiguity can be achieved. In applications, there is often a need to approximate a function given analytically using a function with prescribed sufficient good properties. For example, in cases where calculating the values ​​of a given function /(x) at points of the segment [a, 6] is associated with significant difficulties and/or the given function /(x) does not have the required smoothness, it is convenient to use another function that approximates quite well would have a given function and would be devoid of its noted disadvantages. Function interpolation problem. Construct on the interval [a, 6] a smooth function a(x), coinciding at the grid nodes w with given function/(X). Definition of an interpolating cubic spline An interpolating cubic spline S(x) on a mesh w is a function that 1) on each of the segments is a polynomial of the third degree, 2) is twice continuously differentiable on the segment [a, b], that is, belongs to class C2[ a, 6], and 3) satisfies the conditions. On each of the segments, the spline S(x) is a polynomial of the third degree and is determined on this segment by four coefficients. The total number of segments is m. This means that in order to completely define the spline, it is necessary to find 4m numbers. The condition means the continuity of the function S(x) and its derivatives S"(x) and 5"(x) at all internal grid nodes w. The number of such nodes is m - 1. Thus, to find the coefficients of all polynomials, another 3(m - 1) conditions (equations) are obtained. Together with conditions (2), conditions (equations) are obtained. Boundary (edge) conditions Two missing conditions are specified in the form of restrictions on the values ​​of the spline and/or its derivatives at the ends of the interval [a, 6]. When constructing an interpolating cubic spline, the following four types of boundary conditions are most often used. A. Boundary conditions of the 1st type. - at the ends of the interval [a, b] the values ​​of the first derivative of the desired function are specified. B. Boundary conditions of the 2nd type. - at the ends of the interval (a, 6) the values ​​of the second derivative of the desired function are specified. B. Boundary conditions of the 3rd type. are called periodic. It is natural to require the fulfillment of these conditions in cases where the interpolated function is periodic with period T = b-a. D. Boundary conditions of the 4th type. require special comment. A comment. At internal sepsi nodes, the third derivative of the function S(x), generally speaking, is discontinuous. However, the number of discontinuities of the third derivative can be reduced using conditions of the 4th type. In this case, the constructed spline will be continuously differentiable three times on intervals. Construction of an interpolating cubic spline Let us describe a method for calculating the coefficients of a cubic spline, in which the number of quantities to be determined is equal. On each of the intervals, the interpolation spline function is searched for in the following form. Here SPLINE THEORY examples of solutions and numbers are solutions to a system of linear algebraic equations, the form of which depends on the type of boundary conditions. For boundary conditions of types 1 and 2, this system has the following form where Coefficients depend on the choice of boundary conditions. Boundary conditions of the 1st type: Boundary conditions of the 2nd type: In the case of boundary conditions of the 3rd type, the system for determining numbers is written as follows: Number of unknowns in latest system is equal to mn, since it follows from the periodicity conditions that po = nm. For boundary conditions of the 4th type, the system for determining numbers has the form where Based on the solution found to the system, the numbers po and n can be determined using formulas. Important note. Matrices of all three linear algebraic systems are diagonally dominant matrices. The matrices are not singular, and therefore each of these systems has a unique solution. Theorem. An interpolating cubic spline that satisfies conditions (2) and a boundary condition of one of the four types listed above exists and is unique. Thus, to construct an interpolating cubic spline means to find its coefficients. When the spline coefficients are found, the value of the spline S(x) in arbitrary point segment [a, b] can be found in formula (3). However, for practical calculations it is more suitable next algorithm finding the value 5(g). Let x 6 [x", First, the values ​​of A and B are calculated using the formulas and then the value 5(x) is found: The use of this algorithm significantly reduces the computational costs of determining the value. Tips for the user The choice of boundary (edge) conditions and interpolation nodes allows to a certain extent control the properties of interpolation splines. A. Selection of boundary (edge) conditions. The choice of boundary conditions is one of central problems when interpolating functions. It becomes especially important in the case when it is necessary to ensure high accuracy of approximation of the function f(x) by spline 5(g) near the ends of the segment [a, 6). The boundary values ​​have a noticeable influence on the behavior of the spline 5(g) near points a and b, and this influence quickly weakens as one moves away from them. The choice of boundary conditions is often determined by the presence additional information on the behavior of the approximated function f(x). If the values ​​of the first derivative f"(x) are known at the ends of the segment (a, 6), then it is natural to use boundary conditions of the 1st type. If the values ​​of the second derivative f"(x) are known at the ends of the segment [a, 6], then it is natural use boundary conditions of type 2. If there is a choice between boundary conditions of types 1 and 2, then preference should be given to conditions of type 1. If f(x) - periodic function, then we should stop at the boundary conditions of the 3rd type. In case there is no additional information there is no information about the behavior of the approximated function; the so-called natural boundary conditions are often used. However, it should be borne in mind that with such a choice of boundary conditions, the accuracy of approximation of the function f(x) by the spline S(x) near the ends of the segment (a, ft] sharply decreases. Sometimes they are used boundary conditions of the 1st or 2nd type, but not with exact values the corresponding derivatives, and with their difference approximations. The accuracy of this approach is low. Practical experience of calculations shows that in the situation under consideration, the most appropriate is the choice of boundary conditions of the 4th type. B. Selection of interpolation nodes. If the third derivative f""(x) of the function has a discontinuity at some points of the segment [a, b], then to improve the quality of approximation these points should be included in the number of interpolation nodes. If the second derivative /"(x) is discontinuous, then in order to avoid oscillation of the spline near the discontinuity points, it is necessary to take special measures. Typically, interpolation nodes are chosen so that the discontinuity points of the second derivative fall inside the interval \xif), such that. The value a can be chosen through a numerical experiment (often it is enough to set a = 0.01). There is a set of recipes for overcoming the difficulties that arise when the first derivative f"(x) is discontinuous. As one of the simplest, we can suggest this: divide the approximation segment into intervals where the derivative is continuous, and construct a spline on each of these intervals. Selecting an interpolation function (pros and cons) Approach 1. Lagrange interpolation polynomial For a given array SPLINE THEORY examples of solutions (Fig. 3) interpolation polynomial Lagrange is determined by the formula. It is advisable to consider the properties of the Lagrange interpolation polynomial from two opposite positions, discussing the main advantages separately from the disadvantages. The main advantages of the 1st approach: 1) the graph of the Lagrange interpolation polynomial passes through each point of the array, 2) the constructed function is easily described (the number of coefficients of the Lagrange interpolation polynomial on the grid to be determined is equal to m + 1), 3) the constructed function has continuous derivatives of any order, 4) the interpolation polynomial is uniquely determined by the given array. The main disadvantages of the 1st approach: 1) the degree of the Lagrange interpolation polynomial depends on the number of grid nodes, and the larger this number, the higher the degree of the interpolation polynomial and, therefore, the more calculations required, 2) changing at least one point in the array requires a complete recalculation of the coefficients of the Lagrange interpolation polynomial, 3) addition new point into the array increases the degree of the Lagrange interpolation polynomial by one and also leads to a complete recalculation of its coefficients, 4) with unlimited mesh refinement, the degree of the Lagrange interpolation polynomial increases indefinitely. The behavior of the Lagrange interpolation polynomial with unlimited mesh refinement generally requires special attention. Comments A. On Approximation continuous function polynomial. It is known (Weierstrass, 1885) that any continuous (and even more so smooth) function on an interval can be approximated as well as desired on this interval by a polynomial. Let us describe this fact in the language of formulas. Let f(x) be a function continuous on the interval [a, 6]. Then for any e > 0 there is a polynomial Р„(x) such that for any x from the interval [a, 6] the inequality will be satisfied (Fig. 4) Note that polynomials of even the same degree that approximate the function f(x) with the specified accuracy , there are infinitely many. Let us construct a grid w on the segment [a, 6]. It is clear that its nodes, generally speaking, do not coincide with the intersection points of the graphs of the polynomial Pn(x) and the function f(x) (Fig. 5). Therefore, for the given mesh, the polynomial Pn(x) is not interpolation. When a continuous function is approximated by a Jla-gracz interpolating polynomial, its graph not only does not have to be close to the graph of the function f(x) at each point of the segment [a, b), but can deviate from this function as much as desired. Let's give two examples. Example 1 (Rung, 1901). With an unlimited increase in the number of nodes for the function on the segment [-1, 1], the limit equality is satisfied (Fig. 6) Example 2 (Beristein, 1912). A sequence of Lagrange interpolation polynomials constructed on uniform grids for the continuous function /(x) = |x| on a segment with an increasing number of nodes, m does not tend to the function /(x) (Fig. 7). Approach 2. Piecewise linear interpolation If the smoothness of the interpolated function is abandoned, the ratio between the number of advantages and the number of disadvantages can be noticeably changed towards the former. Let's construct a piecewise linear function by sequentially connecting points (xit y) with straight line segments (Fig. 8). The main advantages of the 2nd approach: 1) the graph of a piecewise linear function passes through each point of the array, 2) the constructed function is easily described (the number of corresponding coefficients to be determined linear functions for the grid (1) is equal to 2m), 3) given the array, the constructed function is uniquely defined, 4) the degree of the polynomials used to describe the interpolation function does not depend on the number of grid nodes (equal to 1), 5) changing one point in the array requires the calculation of four numbers (coefficients of two straight links emanating from a new point), 6) addition additional point into the array requires the calculation of four coefficients. The piecewise linear function also behaves quite well when refining the mesh. The main disadvantage of the 2nd approach: the approximating piecewise linear function is not smooth: the first derivatives suffer a discontinuity at the grid nodes (interpolation ears). Approach 3. Spline interpolation The proposed approaches can be combined so that the number of listed advantages of both approaches is preserved while simultaneously reducing the number of disadvantages. This can be done by constructing a smooth interpolation spline function of degree p. The main advantages of the 3rd approach: 1) the graph of the constructed function passes through each point of the array, 2) the constructed function is relatively easy to describe (the number of coefficients of the corresponding polynomials to be determined for the grid (1) is equal to 3) the constructed function is uniquely defined by the given array, 4) the degree polynomials does not depend on the number of grid nodes and, therefore, does not change as it increases, 5) the constructed function has continuous derivatives up to order p - 1 inclusive, 6) the constructed function has good approximation properties. Brief information. The proposed name - spline - is not accidental - the smooth piecewise polynomial functions we introduced and drawing splines are closely related. Let us consider a flexible ideally thin ruler passing through the reference points of the array located on the (x, y) plane. According to the Bernoulli-Euler law, the linearized equation of a curved ruler has the form where S(x) is the bending, M(x) is the bending moment that varies linearly from support to support, E1 is the rigidity of the ruler. The function S(x), which describes the formula lines, is a polynomial of the third degree between each and two adjacent points of the array (supports) and is twice continuously differentiable over the entire interval (a, 6). A comment. 06 interpolation of a continuous function Unlike Lagrange interpolation polynomials, a sequence of interpolation cubic splines on a uniform mesh always converges to the interpolated continuous function, and as the differential properties of this function improve, the speed of convergence increases. Example. For a function, a cubic spline on a grid with the number of nodes m = 6 gives an approximation error of the same order as the interpolation polynomial Ls(z), and on a grid with the number of nodes m = 21 this error is so small that on the scale of an ordinary book drawing it is simply not can be shown (Fig. 10) (the interpolation polynomial 1>2o(r) gives in this case an error of about 10,000 J). Properties of an interpolation cubic spline A. Alproximation properties of a cubic spline. The approximation properties of the interpolation spline depend on the smoothness of the function f(x) - the higher the smoothness of the interpolated function, the higher the order of approximation and, when refining the mesh, the higher the speed of convergence. If the interpolated function f(x) is continuous on the interval If the interpolated function f(x) has a continuous first derivative on the interval [a, 6], that is interpolation spline, satisfying boundary conditions of the 1st or 3rd type, then for h O we have In this case, not only the spline converges to the interpolated function, but also the derivative of the spline converges to the derivative of this function. If the spline S(x) approximates the function f(x) on the segment [a, b], and its first and second derivatives approximate functions B, respectively. Extremal property of a cubic spline. The interpolating cubic spline has one more useful property. Consider the following example. example. Construct a function /(x) that minimizes the functional on a class of functions from the space C2, the graphs of which pass through the points of the array. Among all the functions passing through the reference points (x;, /(x,)) and belonging to the specified space, it is the cubic spline 5( x), satisfying the boundary conditions, delivers an extremum (minimum) to the functional. Remark 1. Often this extremal property is taken as the definition of an interpolating cubic spline. Remark 2. It is interesting to note that the interpolating cubic spline has the extremal property described above on a very wide class of functions, namely, on the class |o, 5]. 1.2. Smoothing cubic splines About the formulation of the smoothing problem Let a grid and a set of numbers be given Commentary on the initial data In practice, one often has to deal with the case when the values ​​of y in the array are specified with some error. In fact, this means that for each an interval is specified and any number from this interval can be taken as the value of y, . It is convenient to interpret the values ​​of y, for example, as the results of measurements of some function y(x) at given values variables x containing random error. When solving the problem of restoring a function from such “experimental” values, it is hardly advisable to use interpolation, since the interpolation function will obediently reproduce bizarre oscillations caused by a random component in the array (y,). A more natural approach is based on a smoothing procedure designed to somehow reduce the element of randomness in the measurement results. Usually in such problems it is required to find a function whose values ​​for x = x, * = 0, 1,.... m would fall into the appropriate intervals and which, in addition, would have fairly good properties. For example, it would have continuous first and second derivatives, or its graph would not be too strongly curved, that is, it would not have strong oscillations. A problem of this kind also arises when, given a given (exactly) array, it is necessary to construct a function that does not pass through given points, but near them and, moreover, changes quite smoothly. In other words, the required function seemed to smooth the given array, rather than interpolate it. Let a grid w and two sets of numbers be given. SPLINE THEORY examples of solution Problem. Construct a smooth function on the segment [a, A] whose values ​​at the grid nodes u differ from the numbers y by the given values. The formulated smoothing problem is restoration smooth function specified in a table. It is clear that such a problem has many different solutions. By imposing additional conditions on the constructed function, the necessary unambiguity can be achieved. Definition of a smoothing cubic spline A smoothing cubic spline S(x) on a grid w is a function that 1) on each of the segments is a polynomial of the third degree, 2) is twice continuously differentiable on the segment [a, 6], that is, belongs to class C2 [a , b], 3) provides a minimum to the functional where - given numbers, 4) satisfies the boundary conditions of one of the three types indicated below. Boundary (edge) conditions Boundary conditions are specified in the form of restrictions on the values ​​of the spline and its derivatives at the boundary nodes of the grid w. A. Type 1 boundary conditions. - at the ends of the interval [a, b) the values ​​of the first derivative of the desired function are specified. Type 2 boundary conditions. - the second derivatives of the desired function at the ends of the interval (a, b] are equal to zero. B. Boundary conditions of the 3rd type are called periodic. Theorem. Cubic spline S(x), minimizing functional (4) and satisfying the boundary conditions of one of the above three types, is uniquely defined. Definition. A cubic spline that minimizes the functional J(f) and satisfies the boundary conditions of the i-type is called a smoothing spline of the i-type. Remark. this segment by four coefficients. The total number of segments is m. This means that in order to completely determine the spline, it is necessary to find 4m numbers. The condition means the continuity of the function 5(ag) and its derivatives in all internal nodes of the grid o ". The number of such nodes is m - 1. Thus, to calculate the coefficients of all polynomials, we obtain 3(m - 1) conditions (equations). the function is searched for in the following form. Here, the numbers and are the solution to a system of linear algebraic equations, the form of which depends on the type of boundary conditions. Let us first describe how the values ​​n* are found. For boundary conditions of types 1 and 2, the system linear equations to determine the values ​​Hi is written in the following form where known numbers). The coefficients depend on the choice of boundary conditions. Boundary conditions of the 1st type: Boundary conditions of the 2nd type: In the case of boundary conditions of the 3rd type, the system for determining numbers is written as follows: and all coefficients are calculated according to formulas (5) (values ​​with indices k and m + k are considered equal : Important* note: The matrices of the systems are not degenerate and therefore each of these systems has a unique solution. If the numbers n, - are found, then the quantities are easily determined by the formulas where In the case of periodic boundary conditions, the choice of the coefficients is the choice of the weighting coefficients p, -, included. in functional (4), allows you to control the properties of smoothing splines to a certain extent. passed through the point (x^, Vk), then the weighting factor p\ corresponding to it should be set equal to zero. In practical calculations, the most important thing is the choice of values ​​pi - Let D, be the error in measuring the value y. Then it is natural to require that the smoothing spline satisfy the condition or, which is the same. In the simplest case, the weighting coefficients pi can be specified, for example, in the form - where c is some sufficiently small constant. However, this choice of weights p does not allow the use of a “corridor” due to errors in the values ​​y, -. A more rational, but also more labor-intensive algorithm for determining p values ​​may look like this. If the values ​​are found at the fc-th iteration, then it is assumed that where e is a small number that is selected experimentally taking into account the bit grid of the computer, the values ​​of D, and the accuracy of solving the system of linear algebraic equations. If at the fc-th iteration at point i, condition (6) is violated, then the last formula will ensure a decrease in the corresponding weight coefficient p,. If then at the next iteration an increase in p leads to more full use “corridor” (6) and, ultimately, a more smoothly changing spline. A little theory A. Justification of formulas for calculating the coefficients of an interpolation cubic spline. Let us introduce the notation where m, are currently unknown quantities. Their number is equal to m + 1. A spline written in the form where satisfies the interpolation conditions and is continuous on the entire interval [a, b\: putting it in the formula, we obtain, respectively. In addition, it has a continuous first derivative on the interval [a, 6]: By differentiating relation (7) and putting it, we obtain the corresponding actually. Let us show that the numbers m can be chosen so that the spline function (7) has a continuous second derivative on the interval [a, 6]. Let's calculate the second derivative of the spline on the interval: At the point x, - 0 (at t = 1) we have Let's calculate the second derivative of the spline on the interval At the point we have From the condition of continuity of the second derivative at the internal nodes of the grid a; we obtain m - 1 relation where Adding to these m - 1 equations two more, which follow from the boundary conditions, we obtain a system of m + 1 linear algebraic equations with m + I unknown miy i = 0, 1... , m. The system of equations for calculating the values ​​of rsh in the case of boundary conditions of the 1st and 2nd types has the form where (boundary conditions of the 1st type), (boundary conditions of the 2nd type). For periodic boundary conditions (type 3 boundary conditions), the mesh o; extend by one more node and assume Then the system for determining the values ​​of σ* will have the form continuity at the second and (th - !)-th grid nodes. We have From the last two relations we obtain the missing two equations that correspond to the boundary conditions of the 4th type: Eliminating the unknown goo from the equations, and the unknown pc from the equations, as a result we obtain a system of equations. Note that the number of unknowns in this system is th - I. 6. Justification of the formulas for calculating the efficiency of a smoothing subichess spline. Let us introduce the notation where Zi and nj are currently unknown quantities. Their number is 2m + 2. The spline function written in the form is continuous over the entire interval 8), had a continuous first derivative on the interval [a, 6]. Let us calculate the first derivative of the spline S(x) on the interval: At the point x^ - 0 (at t = 1) we have Let us calculate the first derivative of the spline 5(x) on the interval: At the point we have From the condition of continuity of the first derivative of the spline at the internal nodes of the mesh and --> we obtain the m - 1 relation. This relationship is conveniently written in matrix form. The following notation is used. In addition, the spline on the interval [a, 6) has a continuous second derivative: by differentiating relation (8) and putting it, we obtain, respectively. Moreover, the matrix relation is obtained from the condition for the minimum of the functional (4). We have The last two matrix equalities can be considered as a linear system of 2m + 2 linear algebraic equations for 2m + 2 unknowns. Replacing column r in the first equality with its expression obtained from relation (9), we arrive at the matrix equation SPLINE THEORY examples of solutions for determining column M. This equation has a unique solution due to the fact that the matrix A + 6HRH7 is always non-degenerate. Having found it, we can easily identify the city of Eamsshine. The elements of the threadmagolal matrices A and H are determined only by the grid parameters and (with steps hi) and do not depend on the values ​​of y^. Linear space of cubic spline functions The set of cubic splines constructed on the segment [a, 6) along the mesh wcra+l node is linear space dimensions m + 3: 1) the sum of two cubic splines constructed on the mesh u>, and the product of a cubic spline constructed on the mesh u>, by arbitrary number more secretly, they are cubic splines constructed on this mesh, 2) any cubic spline constructed on the mesh and from a node is completely determined by the m + 1 value of the values ​​y" at these nodes and two boundary conditions- just + 3 parameters. By choosing a basis in this space consisting of m + 3 linearly independent splines, we can write an arbitrary cubic spline a(x) as a linear combination of them in a unique way. Comment. This type of spline assignment is widespread in computing practice. Particularly convenient is a database consisting of so-called cubic B-splines (basic, or fundamental, splines). The use of D-splines can significantly reduce the requirements for computer memory. L-splines. A B-spline of zero degree, constructed on the number line along the grid w, is called a fork function. B-spline of degree k ^ I, built on the number line on the grid u, is determined by means of the recurrent formula Graphs of B-splines of the first B, -1 "(g) and the second in\7\x) degrees are presented in Fig. 11 and 12, respectively. A B-spline of arbitrary degree k can be different from zero only on a certain segment (defined by k + 2 nodes). B, -3* (i) was different from zero on the segment y, -+2]. We present the formula for a cubic spline of the third degree for the case of a uniform mesh (with step A). ​​In other cases, we have a typical graph. cubic B-spline shown in Fig. 13. Loans*. function a) is twice continuously differentiable on an interval, that is, it belongs to the class C2[a, "), k b) is different from zero only on four consecutive intervals (Let us supplement the grid w with auxiliary nodes taken completely arbitrarily. Using the extended grid w* we can construct a family of m + 3 cubic B-splines: This family forms a basis in the space of cubic splines on the segment (a, b]. Thus, an arbitrary cubic spline S(z), constructed on the segment |b, 6] grid o; from + 1 nodes , can be represented on this segment in the form of a linear combination. The conditions of the problem determine the coefficients ft of this expansion uniquely... In the case where the values ​​y* of the function at the grid nodes and the values ​​y o and Vm of the first derivative of the function at the ends of the mesh are given" (problem). interpolations with boundary conditions of the first kind), these coefficients are calculated from a system of the following form After exclusion quantities b-i and &m+i, we obtain a linear system with unknowns 5q, ..., bm and a three-dimensional matrix. The condition ensures diagonal dominance and, therefore, the possibility of using the sweep method to resolve it. 3MMCHMY 1. Linear systems Similar types arise when considering other interpolation problems. Zmmchnm* 2. In comparison with the algorithms described in section 1.1, the use of R-spline in * interpolation problems allows us to reduce* the amount of stored information, that is, to significantly reduce the requirements for computer memory, although it leads to an increase in the number of operations. Construction of spline curves using spline functions Above, we considered arrays whose points were numbered so that their abscissas formed a strictly increasing sequence. For example, the case shown in Fig. 14 when different points array of identical abscissas was not allowed. This circumstance determined both the choice of the class of approximating curves (traffic functions) and the method of their construction. However, the method proposed above makes it possible to quite successfully construct an interpolation curve in the more general case, when the numbering of the array points and their location on the plane, as a rule, are not related (Fig. 15). Moreover, when setting the task of constructing an interpolation curve, we can consider the given array to be non-planar, that is, it is clear that to solve this common task it is necessary to significantly expand the class of admissible curves, including closed curves, curves with self-intersection points, and spatial curves. It is convenient to describe such curves using parametric equations We will demand it. in addition, the functions must have sufficient smoothness, for example, they belong to the class C1 [a, /0] or the class To find the parametric equations of a curve that sequentially passes through all points of the array, proceed as follows. 1st step. On an arbitrary segment)