One of these days it was necessary to write a program that calculates the root-mean-square approximation of a function given in a table, according to a power basis - by the method least squares. I’ll make a reservation right away that I didn’t consider the trigonometric basis and I won’t take it in this article. At the end of the article, you can find the source code for the C# program.

Theory

Let the values ​​of the approximated function f(x) given in N+1 nodes f(x 0), ..., f(x N). The approximating function will be chosen from some parametric family F(x, c), where c = (c 0 , ..., c n) T- parameter vector, N > n.

The fundamental difference between the root-mean-square approximation problem and the interpolation problem is that the number of nodes exceeds the number of parameters. AT this case almost always there is no such vector of parameters for which the values ​​of the approximating function would coincide with the values ​​of the approximated function at all nodes.

In this case, the approximation problem is posed as the problem of finding such a vector of parameters c = (c 0 , ..., c n) T, at which the values ​​of the approximating function would deviate as little as possible from the values ​​of the approximated function F(x, c) across all nodes.

Graphically, the problem can be represented as follows

Let us write the criterion for the root-mean-square approximation for the least-squares method:
J(c) = √ (Σ i=0 N 2) →min

The root expression is quadratic function with respect to the coefficients of the approximating polynomial. It is continuous and differentiable in c 0 , ..., c n. Obviously, its minimum is at the point where all partial derivatives are equal to zero. Equating the partial derivatives to zero, we obtain a system of linear algebraic equations with respect to the unknown (desired) coefficients of the polynomial of the best approximation.

The least squares method can be applied to various parametric functions, but often in engineering practice polynomials in some linearly independent basis are used as an approximating function ( φ k(x), k=0,...,n}:
F(x, c)= Σ k=0 n [ c k φ k(x)] .

In this case, the system of linear algebraic equations for determining the coefficients will have quite certain kind:

…

For this system to have a unique solution, it is necessary and sufficient that the determinant of the matrix A (Gram's determinant) be different from zero. In order for the system to have a unique solution, it is necessary and sufficient that the system of basis functions φ k(x), k=0,...,n was linearly independent on the set of approximation nodes.

This article considers the root-mean-square approximation by polynomials in a power basis ( φ k(x) = x k , k=0,...,n}.

Example

Now let's move on to an example. Required to withdraw empirical formula for the given tabular dependence f(x), using the least squares method.

x	0,75	1,50	2,25	3,00	3,75
y	2,50	1,20	1,12	2,25	4,28

Let us take as an approximating function
y = F(x) = c 0 + c 1 x + c 2 x 2, that is, n=2, N=4

The system of equations for determining the coefficients:
a 00 c 0 + a 01 c 1 +… + a 0n c n = b 0
a 10 c 0 + a 11 c 1 +… + a 1n c n = b 1
…
a n0 c 0 + a n1 c 1 +… + a nn c n = b n

a kj = Σ i=0 N [φ k (x i)φ j (x i) ], b j = Σ i=0 N

The coefficients are calculated by the formulas:
a 00 = N + 1 = 5, a 01 = Σ i=0 N x i = 11.25, a 02 = Σ i=0 N x i 2 = 30.94
a 10 = Σ i=0 N x i = 11.25, a 11 = Σ i=0 N x i 2 = 30.94, a 12 = Σ i=0 N x i 3 = 94.92
a 20 = Σ i=0 N x i 2 = 30.94, a 21 = Σ i=0 N x i 3 = 94.92, a 22 = Σ i=0 N x i 4 = 303.76
b 0 = Σ i=0 N y i = 11.25, b 1 = Σ i=0 N x i y i = 29, b 2 = Σ i=0 N x i 2 y i = 90.21

We solve the system of equations and obtain the following values ​​of the coefficients:
c 0 \u003d 4.822, c 1 \u003d -3.882, c 2 \u003d 0.999

Thus
y = 4.8 - 3.9x + x2

Graph of the resulting function

Implementation in C#

And now let's move on to how to write code that would build such a matrix. And here, it turns out, everything is quite simple:
private double[,] MakeSystem(double[,] xyTable, int basis) ( double[,] matrix = new double; for (int i = 0; i< basis; i++) { for (int j = 0; j < basis; j++) { matrix = 0; } } for (int i = 0; i < basis; i++) { for (int j = 0; j < basis; j++) { double sumA = 0, sumB = 0; for (int k = 0; k < xyTable.Length / 2; k++) { sumA += Math.Pow(xyTable, i) * Math.Pow(xyTable, j); sumB += xyTable * Math.Pow(xyTable, i); } matrix = sumA; matrix = sumB; } } return matrix; }
At the input, the function receives a table of function values ​​- a matrix, the first column of which contains x values, the second, respectively, y, as well as the value of the power basis.

First, memory is allocated for the matrix, in which the coefficients for solving the system will be written linear equations. Then, in fact, we compose a matrix - in sumA the values ​​of the coefficients aij are written, in sumB - bi, all according to the formula indicated above in the theoretical part.

To solve the compiled system of linear algebraic equations in my program, the Gauss method is used. The archive with the project can be downloaded

Often the values ​​of the interpolated function u, u2 , ..., yn are determined from the experiment with some errors, so it is unreasonable to use the exact approximation at the interpolation nodes. In this case, it is more natural to approximate the function not by points, but by average, i.e., in one of the L p norms.

Space 1 p - set of functions d(x), defined on the segment [a, b] and modulo integrable with p-th degree, if the norm is defined

Convergence in such a norm is called convergence in average. The space 1,2 is called the Hilbert space, and the convergence in it is rms.

Let the function Ax) and the set of functions φ(x) from some linear normed space be given. In the context of the problem of interpolation, approximation, and approximation, the following two problems can be formulated.

First task is an approximation with a given accuracy, i.e., according to a given e find a φ(x) such that the inequality |[Ax) - φ(x)|| G..

Second task is a search the best approximation i.e., the search for a function φ*(x) that satisfies the relation:

Define without proof sufficient condition existence of the best approximation. To do this, in the linear space of functions, we choose a set parametrized by the expression

where the set of functions φ[(x), ..., φn(x) will be assumed to be linearly independent.

It can be shown that in any normed space for linear approximation(2.16) the best approximation exists, although it is unique in every linear space.

Let us consider the Hilbert space LzCp) of real square-integrable functions with weight p(x) > 0 on [ , where the scalar product ( g,h) determined by

formula:

Substituting the linear combination (2.16) into the best approximation condition, we find

Equating to zero the derivatives with respect to the coefficients (D, k= 1, ..., П, we obtain a system of linear equations

The determinant of the system of equations (2.17) is called the Gram determinant. Gram's determinant is nonzero, since it is assumed that the system of functions φ[(x), ..., φn(x) is linearly independent.

Thus, the best approximation exists and is unique. To obtain it, it is necessary to solve the system of equations (2.17). If the system of functions φ1(x), ..., φn(x) is orthogonalized, i.e., (φ/, φ,) = sy, where SCH,ij = 1, ..., P, then the system of equations can be solved in the form:

The coefficients found according to (2.18) Q, ..., th p are called the coefficients of the generalized Fourier series.

If a set of functions φ t (X), ..., φ "(x), ... forms a complete system, then by virtue of Parseval's equality for Π -» with the norm of error decreases indefinitely. This means that the best approximation converges rms to Dx) with any given accuracy.

We note that the search for the coefficients of the best approximation by solving the system of equations (2.17) is practically unrealizable, since as the order of the Gram matrix increases, its determinant rapidly tends to zero, and the matrix becomes ill-conditioned. Solving a system of linear equations with such a matrix will lead to a significant loss of accuracy. Let's check it out.

Let as a system of functions φ„ i =1, ..., П, degrees are chosen, i.e. φ* = X 1 ", 1 = 1, ..., P, then, assuming the segment as an approximation segment, we find the Gram matrix

The Gram matrix of the form (2.19) is also called the Hilbert matrix. This is classic example the so-called ill-conditioned matrix.

Using MATLAB, we calculate the determinant of the Hilbert matrix in the form (2.19) for some first values P. Listing 2.5 shows the code for the corresponding program.

Listing 23

% Calculate the determinant of Hilbert matrices % clear the workspace clear all;

%choose maximum value order of the Hilbert matrix ptah =6;

%build a loop to generate %Hilbert matrices and calculate their determinants

for n = 1: nmax d(n)=det(hi I b(n)); end

%display the values ​​of the determinants %of the Hilbert matrices

f o g ta t short end

After working out the code in Listing 2.5, the Hilbert matrix determinant values ​​for the first six matrices should appear in the MATLAB command window. The table below shows the corresponding numerical values ​​of the matrix orders (n) and their determinants (d). The table clearly shows how quickly the determinant of the Hilbert matrix tends to zero as the order increases and, starting from orders 5 and 6, becomes unacceptably small.

Table of values ​​of the determinant of Hilbert matrices

Numerical orthogonalization of the system of functions φ, i = 1, ..., П also leads to a noticeable loss of accuracy, therefore, in order to take into account big number terms in expansion (2.16), it is necessary either to carry out orthogonalization analytically, i.e., exactly, or to use a ready-made system of orthogonal functions.

If during interpolation, degrees are usually used as a system of basis functions, then during approximation, on average, polynomials that are orthogonal with a given weight are chosen as basis functions. The most common of these are the Jacobi polynomials, a special case of which are the Legendre and Chebyshev polynomials. Lagsrr and Hermite polynomials are also used. More details about these polynomials can be found, for example, in the appendix Orthogonal polynomials books.

3. RMS approximation of the function

3.1 Statement of the problem

Develop an algorithm scheme and write a program in Turbo Pascal 7.0 to perform root-mean-square approximation of a function given in nodes.

3.2 Mathematical formulation of the problem

Let there be a set of functions belonging to the linear space of functions. By closeness on average of the interpolated and interpolating functions, we mean the result of estimating the integral

, (3.1)

where is the weight function.

This approximation is called root mean square.

3.3 Review of existing numerical methods for solving the problem

The problem of root-mean-square approximation arises in many areas applied research, for example, when statistical processing experimental data using regression analysis, when estimating model parameters, in filtering tasks, etc.

When the level of uncertainty in setting the approximated function f(x i), i=1..m, is large enough, which is typical for the processing of experimental data, it makes no sense to demand that the interpolation conditions be met; moreover, the number of points for specifying the function f(x i) is often quite large. All this makes the use of interpolation unpromising due to the poor conditionality of the high-dimensional problem and the problems of convergence of the interpolation process.

One of the simplest and therefore widely used approximating functions is the algebraic polynomial

The root-mean-square approximation method provides the construction of the polynomial Pn(x) based on the minimization of the value

The considered approximation method minimizes the root-mean-square deviation of the approximating polynomial from the approximated function, but does not guarantee against significant local errors. To prevent this possibility, polynomials of the best uniform approximation are used.

in the space of parameters a 0 , a 1 ,...,a n. Exist different approaches to solving the problem of minimizing the function D(a). The simplest of them leads to the need to solve normal system linear algebraic equations

However, even for n > 5, the matrix of such a system turns out to be so ill-conditioned that the values ​​of a j obtained from (3.4) turn out to be of little use for calculating P n (x). Therefore, if it is necessary to construct polynomials of the best mean-square approximation, more high degrees other algorithms are used, for example, the singular value decomposition method.

3.4 Numerical method problem solving

Two issues can be considered:

1 - choose a function so that the inequality is fulfilled

2 - find the best approximation, i.e. such a function that the relation

. (3.6)

We expand the function in terms of a system of linearly independent functions:

. (3.7)

In what follows, to shorten the notation, we will use the definition dot product in function space :

.

Substituting (3.7) into condition (3.6), we obtain

Differentiating this expression with respect to and equating the derivatives to zero, we obtain

. (3.8)

The determinant of this system is the Gram determinant of functions. By virtue of their linear independence this determinant is not equal to zero. Therefore, from system (3.8) one can find the coefficients defining the function according to (3.6) and minimizing the integral of the error . Thus, the best root-mean-square approximation exists and it is unique.

When using an orthonormal system of functions, system (3.8) simplifies:

,

those. are the Fourier coefficients, and the best approximation is the Fourier series terminated at some term.

It is proved that in any linearly normed space under a linear approximation of the form (3.4) the best approximation exists, although it may not be unique.

In cases where the functions are not orthogonal, at , the Gram determinant decreases, approaching zero. Then the system becomes ill-conditioned and its solution gives a large error. In this situation, usually no more than five or six terms are taken in the sum (3.7).

The most commonly used polynomials are Legendre, Chebyshev, Laguerre, Hermite, orthogonal with a given weight.

Consider special case when it is necessary to find the best approximation of a function given in a table. For real functions defined on a finite set of points, the scalar product is defined by the formula

, (3.9)

where is the number of specified nodes.

The condition for the best root-mean-square approximation is written as follows:

. (3.10)

Assuming , where , and substituting this polynomial into (3.10), we arrive at system (3.8), in which the scalar products are calculated according to (3.9). The described approximation procedure is called the method of least squares.

The most common version of the least squares method corresponds to the case power type functions , i.e. , and .

The system of equations (3.8) then takes the form

, , (3.11)

Form more high level abstractions and generalizations than that which traditional teaching has been oriented towards." Hence, traditional forms learning fails to raise mathematical thinking junior schoolchildren to a higher level. How does non-traditional education solve this problem? What properties of mathematical thinking does the solution develop non-standard tasks? In-...

network built on the basis of various topologies. Software application systems designed for professional activity manager, includes: · system software; basic packages of applied programs; · means of network support of computers in local and global networks; application programming systems; test software. ...

In order to smooth out discrete functions Altman, and thereby introduce the idea of ​​continuity into the theory, the root-mean-square integral approximation by a polynomial of different degrees was used.

It is known that a sequence of interpolation polynomials over equidistant nodes does not necessarily converge to a function, even if the function is infinitely differentiable. For the approximated function, with the help of a suitable arrangement of nodes, it is possible to reduce the degree of the polynomial. . The structure of the Altman functions is such that it is more convenient to use the approximation of the function not by means of interpolation, but by constructing the best root-mean-square approximation in a normalized linear space. Consider the basic concepts and information in constructing the best approximation. Approximation and optimization problems are posed in linear normed spaces.

Metric and linear normed spaces

To the most broad concepts mathematics refer to "set" and "mapping". The concept of "set", "set", "collection", "family", "system", "class" in non-strict set theory are considered synonyms.

The term "operator" is identical to the term "mapping". The terms "operation", "function", "functional", "measure" are special cases of the concept "mapping".

The terms "structure", "space" in the axiomatic construction mathematical theories also acquired a fundamental importance. Mathematical structures include set-theoretic structures (ordered and partially ordered sets); abstract algebraic structures (semigroups, groups, rings, division rings, fields, algebras, lattices); differential structures(external differential forms, fiber spaces) , , , , , , .

A structure is understood as a finite set consisting of sets of a carrier (main set), a numerical field (auxiliary set), and a mapping defined on the elements of the carrier and numbers of the field. If the carrier is taken as a set complex numbers, then it plays the role of both the main and auxiliary sets. The term "structure" is identical to the concept of "space".

To define a space, it is first of all necessary to define a carrier set with its elements (points), denoted by Latin and Greek letters

Sets of real (or complex) elements can act as a carrier: numbers; vectors, ; Matrices, ; Sequences, ; Functions

Sets can also act as carrier elements: real axis, plane, three-dimensional (and multidimensional) space, permutations, movements; abstract sets.

Definition. A metric space is a structure forming a triple, where the mapping is non-negative actual function of two arguments for any x and y from M and satisfying three axioms.

• 1 - non-negativity; , at.
• 2- - symmetry;
• 3- - axiom of reflexivity.

where are the distances between the elements.

In a metric space, a metric is specified and the concept of the proximity of two elements from the support set is formed.

Definition. A real linear (vector) space is a structure where mapping is the additive operation of adding elements belonging to it, and mapping is the operation of multiplying a number by an element from.

The operation means that for any two elements, the third element is uniquely defined, called their sum and denoted by, and the following axioms hold.

commutative property.

Associative property.

There is a special element in B, denoted by such that it holds for any.

for any exists, such that.

The element is called opposite to and is denoted by.

The operation means that for any element and any number, an element is defined, denoted by and the axioms are fulfilled:

An element (points) of a linear space is also called a vector. Axioms 1 - 4 define a group (additive), called a module and representing a structure.

If an operation in a structure does not obey any axioms, then such a structure is called a groupoid. This structure is extremely poor; it does not contain any axiom of associativity, then the structure is called a monoid (semigroup).

In the structure, with the help of mapping and axioms 1-8, the property of linearity is set.

So, the linear space is a group module, in the structure of which one more operation is added - multiplication of the support elements by a number with 4 axioms. If instead of an operation, along with one more group operation of multiplication of elements with 4 axioms, and postulate the axiom of distributivity, then a structure called a field arises.

Definition. A linear normed space is a structure in which the mapping satisfies the following axioms:

• 1. And then and only then, when.
• 2. , .
• 3. , .

And so in just 11 axioms.

For example, if the field structure real numbers, where - real numbers, add a module that has all three norm properties, then the field of real numbers becomes a normed space

There are two common ways to introduce the norm: either by explicitly specifying the interval form of the homogeneously convex functional , , or by specifying the scalar product , .

Let, then the form of the functional can be given countless ways by changing the value:

• 1. , .
• 2. , .

………………..

…………….

The second common way of accepting the assignment is that another mapping is introduced into the structure of the space (a function of two arguments, usually denoted by and called the scalar product).

Definition. Euclidean space is a structure in which the scalar product contains the norm and satisfies the axioms:

• 4. , and if and only if

In Euclidean space, the norm is generated by the formula

It follows from properties 1 - 4 of the scalar product that all axioms of the norm are satisfied. If the scalar product is in the form, then the norm will be calculated by the formula

The space norm cannot be specified using the scalar product , .

In spaces with a scalar product, such qualities appear that are absent in linear normed spaces (orthogonality of elements, parallelogram equality, the Pythagorean theorem, Apollonius's identity, Ptolemy's inequality. The introduction of a scalar product gives ways to more effective solution approximation problems.

Definition. An infinite sequence of elements in a linear normed space is said to be norm-converging (simply convergent or having a limit in) if there exists such an element that for any there is a number depending on such that for

Definition. A sequence of elements in is called fundamental if for any there is a number depending on that any and are satisfied (Trenogin Kolmogorov, Kantorovich, p. 48)

Definition. A Banach space is a structure in which any fundamental sequence converges in norm.

Definition. A Hilbert space is a structure in which any fundamental sequence converges in the norm generated by the scalar product.

Quadratic approximation

If the scatter plot looks like a parabola, then we are looking for an empirical formula in the form square trinomial. Suppose the approaching curve is like a parabola, symmetrical about the y-axis. Then the parabola will take a simpler form

(4.4)

Let's take a semi-quadratic coordinate system. This is such a coordinate system, in which the scale is quadratic along the abscissa, i.e. the division values ​​are plotted according to the expression, here m- scale in some unit of length, for example, in cm.

A linear scale is plotted along the y-axis in accordance with the expression

We put experimental points on this coordinate system. If the points of this graph are located approximately in a straight line, then this confirms our assumption that the dependence y from x is well expressed by a function of the form (4.4). To find the coefficients a and b you can now apply one of the methods discussed above: the stretched thread method, the selected points method, or the average method.

Tight thread method applies in the same way as for a linear function.

Selected points method we can apply like this. On a rectilinear graph, take two points (far from each other). We denote the coordinates of these points and ( x, y). Then we can write

From the reduced system of two equations, we find a and b and substitute them into formula (4.4) and obtain the final form of the empirical formula.

May or may not build rectilinear graph, and take the numbers , ( x,y) directly from the table. However, the formula obtained with this choice of points will be less accurate.

The process of converting a curved graph to a straight line is called flattening.

Medium method. It is applied in the same way as in the case of linear dependence. We divide the experimental points into two groups with the same (or almost the same) number of points in each group. Equality (4.4) can be rewritten as

(4.5)

We find the sum of residuals for the points of the first group and equate to zero. We do the same for the points of the second group. We get two equations with unknowns a and b. Solving the system of equations, we find a and b.

Note that when applying this method, it is not required to build an approximating straight line. dot plot in a semiquadratic coordinate system is needed only to check that a function of the form (4.4) is suitable for an empirical formula.

Example. When studying the effect of temperature on the course of the chronometer, the following results were obtained:

z	-20	-15,4	-9,0	-5,4	-0,6	+4,8	+9,4
	2,6	2,01	1,34	1,08	0,94	1,06	1,25

In this case, we are not interested in the temperature itself, but in its deviation from . Therefore, we take as an argument , where t- temperature in degrees Celsius of the usual scale.

Having plotted the corresponding points on the Cartesian coordinate system, we notice that a parabola with an axis parallel to the y-axis can be taken as an approximating curve (Fig. 4). Let's take a semi-quadratic coordinate system and plot experimental points on it. We see that these points fit well enough on a straight line. So the empirical formula

can be searched in the form (4.4).

Let's define the coefficients a and b by the average method. To do this, we divide the experimental points into two groups: in the first group - the first three points, in the second - the remaining four points. Using equality (4.5) we find the sum of residuals for each group and equate each sum to zero.