Derivation of the calculation formula for the simple iteration method. Simple iteration method

By analogy with (2.1), system (5.1) can be represented in the following equivalent form:

where g(x) is an iterative vector function of the vector argument. Systems of nonlinear equations often arise directly in the form (5.2) (for example, in numerical schemes for differential equations); in this case, no additional effort is required to transform equations (5.1) into system (5.2). If we continue the analogy with the simple iteration method for one equation, then the iteration process based on equation (5.2) can be organized as follows:

• 1) some initial vector x ((,) e 5 o (x 0, A)(it is assumed that x* e 5„(x 0, A));
• 2) subsequent approximations are calculated using the formula

then the iteration process is completed and

As before, we need to find out under what conditions

Let's discuss this issue by performing a simple analysis. First we introduce the error of the ith approximation as e(^ = x(i) - x*. Then we can write

Let us substitute these expressions into (5.3) and expand g(x* + e (/i)) in powers e(k> in the neighborhood of x* as a function of the vector argument (assuming that all partial derivatives of the function g(x) are continuous). Taking into account also that x* = g(x*), we get

or in matrix form

B = (bnm)= I (x*)1 - iteration matrix.

If the error rate ||е®|| is small enough, then the second term on the right side of expression (5.4) can be neglected, and then it coincides with expression (2.16). Consequently, the condition for the convergence of the iterative process (5.3) near the exact solution is described by Theorem 3.1.

Convergence of the simple iteration method. Necessary and sufficient condition for the convergence of the iterative process (5.3):

and a sufficient condition:

These conditions are of theoretical rather than practical significance, since we do not know x'. By analogy with (1.11), we obtain a condition that can be useful. Let x* e 5 o (x 0, A) and the Jacobian matrix for the function g(x)

exists for all x e S n (x 0 , a) (note that C(x*) = B). If the elements of the matrix C(x) satisfy the inequality

for all x e 5„(x 0, A), then the sufficient condition (5.5) is also satisfied for any matrix norm.

Example 5.1 (simple iteration method) Consider the following system of equations:

One possibility to represent this system in equivalent form (5.2) is to express X from the first equation and x 2 from the second equation:

Then the iteration scheme has the form

The exact solution is x* e 5„((2, 2), 1). Let's choose the initial vector x (0) = (2,2) and ? p = CT 5. The calculation results are presented in table. 5.1.

Table 5.1

These results show that the convergence is quite slow. In order to obtain a quantitative characteristic of convergence, we carry out a simple analysis, considering x (1/) to be an exact solution. The Jacobian matrix C(x) for our iterative function has the form

then matrix B is approximately estimated as

It is easy to check that neither condition (5.5) nor condition (5.6) are satisfied, but convergence takes place, since 5(B) ~ 0.8.

It is often possible to speed up the convergence of the simple iteration method by slightly changing the calculation process. The idea of ​​this modification is very simple: to calculate P th vector components x (A+1) can be used not only (t = n,..., N), but also the already calculated components of the next approximation vector x k^ (/= 1,P - 1). Thus, the modified simple iteration method can be represented as the following iteration scheme:

If the approximations generated by the iterative process (5.3) converge, then the iterative process (5.8) tends to converge faster due to more complete use of information.

Example 5.2 (modified simple iteration method) The modified simple iteration for system (5.7) is represented as

As before, we choose the initial vector x (0) = (2, 2) and g r = = 10 -5. The calculation results are presented in table. 5.2.

Table 5.2

I The big change in the order of calculations led to a halving of the number of iterations, and therefore a halving of the number of operations.

Let's replace the original equation with an equivalent one and build iterations according to the rule . Thus, the simple iteration method is a one-step iterative process. In order to start this process, you need to know the initial approximation. Let us find out the conditions for the convergence of the method and the choice of the initial approximation.

Ticket#29

Seidel method

The Seidel method (sometimes called the Gauss-Seidel method) is a modification of the simple iteration method, which consists in the fact that when calculating the next approximation x (k+1) (see formulas (1.13), (1.14)) its already obtained components x 1 ( k+1) , ...,x i - 1 (k+1) are immediately used to calculate x i (k+1) .

In coordinate notation form, the Seidel method has the form:

X 1 (k+1) = c 11 x 1 (k) + c 12 x 2 (k) + ... + c 1n-1 x n-1 (k) + c 1n x n (k) + d 1
x 2 (k+1) = c 21 x 1 (k+1) + c 22 x 2 (k) + ... + c 2n-1 x n-1 (k) + c 2n x n (k) + d 2
...
x n (k+1) = c n1 x 1 (k+1) + c n2 x 2 (k+1) + ... + c nn-1 x n-1 (k+1) + c nn x n (k ) + dn
where x (0) is some initial approximation to the solution.

Thus, the i-th component of the (k+1)-th approximation is calculated by the formula

The condition for the end of the Seidel iterative process when the accuracy ε is achieved in a simplified form has the form:

|| x (k+1) - x (k) || ≤ ε.

Ticket#30

Passing method

To solve systems A x = b with a tridiagonal matrix, the sweep method is most often used, which is an adaptation of the Gauss method to this case.

Let's write the system of equations

d 1 x 1 + e 1 x 2 = b 1
c 2 x 1 + d 2 x 2 + e 2 x 3 = b 2
c 3 x 2 + d 3 x 3 + e 3 x 4 = b 3
... ... ...
c n-1 x n-2 + d n-1 x n-1 + e n-1 x n = b n-1
c n x n-1 + d n x n = b n

in matrix form: A x = b where

A=

Let us write down the formulas of the sweep method in the order of their application.

1. Direct stroke of the sweep method (calculation of auxiliary quantities):

2. Reverse the sweep method (finding a solution):

Ticket No. 31

Simple iteration method

The essence of the simple iteration method is to move from the equation

f(x)= 0 (*)

to the equivalent equation

x=φ(x). (**)

This transition can be accomplished in different ways, depending on the type f(x). For example, you can put

φ(x) = x+bf(x),(***)

Where b= const, while the roots of the original equation will not change.

If the initial approximation to the root is known x 0, then the new approximation

x 1=φx(0),

those. general scheme of the iterative process:

x k+1=φ(x k).(****)

The simplest criterion for ending the process

|x k +1 -x k |<ε.

Convergence criterion simple iteration method:

if near the root | φ/(x)| < 1, то итерации сходятся. Если указанное условие справедливо для любого x, then the iterations converge for any initial approximation.

Let's explore the choice of constant b from the point of view of ensuring maximum convergence speed. In accordance with the convergence criterion, the highest speed of convergence is provided when |φ / (x)| = 0. At the same time, based on (***), b = –1/f / (x), and the iteration formula (****) goes into x i =x i-1 -f(x i-1)/f/ (x i-1).- those. into the formula of Newton's method. Thus, Newton's method is a special case of the simple iteration method, providing the highest speed of convergence of all possible options for choosing a function φ(x).

Ticket#32

Newton's method

The main idea of ​​the method is as follows: an initial approximation is specified near the hypothetical root, after which a tangent to the function under study is constructed at the approximation point, for which the intersection with the abscissa axis is found. This point is taken as the next approximation. And so on until the required accuracy is achieved.

Let be a real-valued function defined on an interval and differentiable on it. Then the formula for iterative approximation calculus can be derived as follows:

where α is the angle of inclination of the tangent at the point.

Therefore, the required expression for has the form:

Ticket#33

Golden ratio method
The golden ratio method allows you to eliminate intervals by calculating only one function value at each iteration. As a result of the two considered values ​​of the function, the interval is determined that should be used in the future. This interval will contain one of the previous points and the next point placed symmetrically to it. The point divides the interval into two parts so that the ratio of the whole to the larger part is equal to the ratio of the larger part to the smaller, i.e. equal to the so-called “golden ratio”.

Dividing the interval into unequal parts allows you to find an even more effective method. Let us calculate the function at the ends of the segment [ a,b] and put a=x 1 , b=x 2. Let us also calculate the function at two interior points x 3 , x 4 . Let's compare all four values ​​of the function and choose the smallest among them. Let, for example, the smallest turn out to be f(x 3). Obviously, the minimum must be in one of the segments adjacent to it. Therefore the segment [ x 4 ,b] can be discarded and leave the segment .

The first step has been taken. On the segment, you again need to select two internal points, calculate the function values ​​​​at them and at the ends and take the next step. But at the previous step of calculations, we already found the function at the ends of the new segment and at one of its internal points x 4 . Therefore, it is enough to select one more point inside x 5 determine the value of the function in it and make the necessary comparisons. This quadruples the amount of computation required per process step. What is the best way to place points? Each time the remaining segment is divided into three parts and then one of the outer segments is discarded.
Let us denote the initial uncertainty interval by D.

Since in the general case any of the segments can be discarded X 1, X 3 or X 4, X 2 then select the points X 3 And X 4 so that the lengths of these segments are the same:

x 3 -x 1 =x 4 -x 2.

After discarding, we get a new length uncertainty interval D′.
Let us denote the relation D/D′ with the letter φ:

that is, let us set , where is the next uncertainty interval. But

equal in length to the segment discarded at the previous stage, that is

Therefore we get:

.
This leads to the equation or, equivalently
.

The positive root of this equation gives

.

Ticket#34

interpolation of functions, i.e. Using a given function, constructing another (usually simpler) function whose values ​​coincide with the values ​​of the given function at a certain number of points. Moreover, interpolation has both practical and theoretical significance.

Numerical solution of equations and their systems consists in approximate determination of the roots of an equation or system of equations and is used in cases where the exact solution method is unknown or labor-intensive.

Formulation of the problem[ | ]

Let's consider methods for numerically solving equations and systems of equations:

( f 1 (x 1 , x 2 , … , x n) = 0 … f n (x 1 , x 2 , … , x n) = 0 (\displaystyle \left\((\begin(array)(lcr)f_(1 )(x_(1),x_(2),\ldots ,x_(n))&=&0\\\ldots &&\\f_(n)(x_(1),x_(2),\ldots ,x_( n))&=&0\end(array))\right.)

Numerical methods for solving equations[ | ]

Let's show how you can solve the original system of equations without resorting to optimization methods. If our system is a SLAE, it is advisable to resort to methods such as the Gaussian method or the Richardson method. However, we will still proceed from the assumption that the form of the function is unknown to us, and we will use one of the iterative methods of numerical solution. Among the wide variety of these, we will choose one of the most famous - Newton's method. This method, in turn, is based on the principle of compressive mapping. Therefore, the essence of the latter will be outlined first.

Compressive mapping[ | ]

Let's define the terminology:

The function is said to perform compressive mapping on if

Then the following main theorem is valid:

It follows from the last point of the theorem that the convergence rate of any method based on contraction mappings is no less than linear.

Let us explain the meaning of the parameter α (\displaystyle \alpha ) for the case of one variable. According to Lagrange's theorem we have: