Simple iteration method with optimal parameter. Iterative methods for solving the slough

The simple iteration method, also called the method successive approximation, - this is mathematical algorithm finding the value of an unknown quantity by gradually refining it. The essence of this method is that, as the name implies, gradually expressing the subsequent ones from the initial approximation, they get more and more refined results. This method is used to find the value of a variable in given function, as well as in solving systems of equations, both linear and non-linear.

Consider how this method is realized when solving the SLAE. The simple iteration method has the following algorithm:

1. Verification of the convergence condition in the original matrix. Convergence theorem: if the original matrix of the system has diagonal dominance (i.e., in each row, the elements of the main diagonal must be greater in modulus than the sum of the elements of the secondary diagonals in modulo), then the method simple iterations- converging.

2. The matrix of the original system does not always have diagonal dominance. In such cases, the system can be converted. Equations that satisfy the convergence condition are left untouched, and with those that do not, they form linear combinations, i.e. multiply, subtract, add equations to each other until the desired result is obtained.

If in the resulting system there are inconvenient coefficients on the main diagonal, then terms of the form c i *x i are added to both parts of such an equation, the signs of which must coincide with the signs of the diagonal elements.

3. Transformation of the resulting system to the normal form:

x - =β - +α*x -

This can be done in many ways, for example, as follows: from the first equation, express x 1 in terms of other unknowns, from the second - x 2, from the third - x 3, etc. Here we use the formulas:

α ij = -(a ij / a ii)

i = b i /a ii
You should again make sure that the resulting system of normal form satisfies the convergence condition:

∑ (j=1) |α ij |≤ 1, while i= 1,2,...n

4. We begin to apply, in fact, the method of successive approximations itself.

x (0) - initial approximation, we express through it x (1) , then through x (1) we express x (2) . General formula a matrix form looks like that:

x (n) = β - +α*x (n-1)

We calculate until we reach the required accuracy:

max |x i (k)-x i (k+1) ≤ ε

So, let's look at the simple iteration method in practice. Example:
Solve SLAE:

4.5x1-1.7x2+3.5x3=2
3.1x1+2.3x2-1.1x3=1
1.8x1+2.5x2+4.7x3=4 with accuracy ε=10 -3

Let's see if the diagonal elements predominate modulo.

We see that only the third equation satisfies the convergence condition. We transform the first and second equations, add the second to the first equation:

7.6x1+0.6x2+2.4x3=3

Subtract the first from the third:

2.7x1+4.2x2+1.2x3=2

We have converted the original system into an equivalent one:

7.6x1+0.6x2+2.4x3=3
-2.7x1+4.2x2+1.2x3=2
1.8x1+2.5x2+4.7x3=4

Now let's bring the system back to normal:

x1=0.3947-0.0789x2-0.3158x3
x2=0.4762+0.6429x1-0.2857x3
x3= 0.8511-0.383x1-0.5319x2

We check the convergence of the iterative process:

0.0789+0.3158=0,3947 ≤ 1
0.6429+0.2857=0.9286 ≤ 1
0.383+ 0.5319= 0.9149 ≤ 1 , i.e. the condition is met.

0,3947
Initial guess x(0) = 0.4762
0,8511

Substituting these values ​​into the normal form equation, we obtain the following values:

0,08835
x(1) = 0.486793
0,446639

Substituting new values, we get:

0,215243
x(2) = 0.405396
0,558336

We continue the calculations until we get closer to the values ​​that satisfy the given condition.

x(7) = 0.441091

Let's check the correctness of the obtained results:

4,5*0,1880 -1.7*0,441+3.5*0,544=2,0003
3.1*0.1880+2.3*0.441-1.1x*0.544=0.9987
1.8*0,1880+2.5*0,441+4.7*0,544=3,9977

The results obtained by substituting the found values ​​into the original equations fully satisfy the conditions of the equation.

As we can see, the simple iteration method gives quite accurate results, however, to solve this equation, we had to spend a lot of time and do cumbersome calculations.

Consider linear algebraic equations

Let's spend a few equivalent transformations. We multiply both parts of the system by the same scalar factor, then we add a vector to the right and left parts of the system. The system of equations can now be written in a form convenient for iterations:

(2.15)

Now let us construct a sequence of approximations to the solution of the system. We choose an arbitrary vector - the initial approximation to the solution. Most often, it is simply assumed to be a zero vector. Most likely, the initial approximation does not satisfy (2.15) and, consequently, the original system. When it is substituted into the original equation, a discrepancy arises. Calculating the discrepancy, using (2.15), we can refine the approximation to the solution, assuming that

According to the first approximation, the discrepancy is calculated again, the process continues. In the course of iteration, we obtain an equivalent formulation of the method called simple iteration method, is as follows. Solution (2.15) is found as the limit of the sequence approximations, the terms of which are connected by a recursive relation (it is equivalent to the one given above, the residual vector is excluded from the notation):

(2.16)

(or any arbitrary vector). If the limit of such a sequence exists, then one speaks of convergence iterative process to the solution of SLAE .

There are other forms of writing the iteration method, such as

For , the last formula corresponds to the one-parameter iterative process discussed above simple iteration method. For , - n -step explicit iterative process, for , - simple iteration method without iteration parameter. In case when , iterative method called implicit- for calculation next approximation To solve it, you will have to solve a (usually simpler than the original) system of linear equations.

Theorem ( sufficient condition convergence simple iteration method). The iterative process (2.16) converges to the solution of the SLAE at the rate geometric progression when the condition is met:

Proof.

Let be the exact solution of system (2). Subtracting from (2.16)-(2.15), we obtain , or, denoting the error , we obtain the equation for the evolution of the error The chain of inequalities is valid: , where

It follows from this that when

From inequality one can obtain an estimate of the number of iterations required to achieve accuracy, i.e. to satisfy the condition This estimate has the form

Theorem (convergence criterion simple iteration method (no proof)). Let SLAE (2.15) have a unique solution. Then for the convergence of the iterative process (2.16) it is necessary and sufficient that all eigenvalues matrices by absolute value were less than one.

Compare in quantity arithmetic operations direct and iterative methods. The Gaussian method without choosing the principal element requires

Arithmetic operations; simple iteration method (2.16) , where i is the number of approximations required to achieve the given accuracy. So, for I< n/3 метод итераций становится предпочтительнее. В real tasks, basically, in addition, iterative methods can be made more efficient by changing the iteration parameters. In some cases iterative methods turn out to be more stable with respect to the accumulation of rounding errors than straight lines.

Lecture Iterative methods for solving a system of algebraic linear equations.

Convergence condition of the iterative process. Jacobi method. Seidel method

Simple iteration method

The system of linear algebraic equations is considered

To apply iterative methods, the system must be reduced to an equivalent form

Then, the initial approximation to the solution of the system of equations is chosen, and a sequence of approximations to the root is found.

For the iterative process to converge, it is sufficient that the condition
(matrix norm). The termination criterion for iterations depends on the applied iterative method.

Jacobi method .

The simplest way to bring the system to a form convenient for iteration is as follows:

From the first equation of the system, we express the unknown x 1 , from the second equation of the system we express x 2 , etc.

As a result, we obtain a system of equations with matrix B, in which zero elements are on the main diagonal, and the remaining elements are calculated by the formulas:

The components of the vector d are calculated by the formulas:

The calculation formula of the simple iteration method is:

or in coordinate notation looks like this:

The criterion for the termination of iterations in the Jacobi method has the form:

If a
, then a simpler criterion for terminating iterations can be applied

Example 1 Solution of a system of linear equations by the Jacobi method.

Let the system of equations be given:

It is required to find a solution to the system with accuracy

We bring the system to a form convenient for iteration:

We choose an initial approximation, for example,

is the vector of the right side.

Then the first iteration looks like this:

The following approximations to the solution are obtained similarly.

Find the norm of the matrix B.

We will use the norm

Since the sum of the modules of the elements in each row is 0.2, then
, so the criterion for terminating iterations in this problem is

Let us calculate the norms of the differences of vectors:

Because
the specified accuracy is reached at the fourth iteration.

Answer: x 1 = 1.102, x 2 = 0.991, x 3 = 1.0 1 1

Seidel method .

The method can be considered as a modification of the Jacobi method. The main idea is that when calculating the next (n+1)-th approximation to the unknown x i at i>1 use already found (n+1)- approaching the unknown x 1 ,x 2 , ...,x i - 1 , not n th approximation, as in the Jacobi method.

The calculation formula of the method in the coordinate-wise notation looks like this:

The convergence conditions and the termination criterion for iterations can be taken the same as in the Jacobi method.

Example 2 Solving systems of linear equations by the Seidel method.

Consider in parallel the solution of 3 systems of equations:

We bring the systems to a form convenient for iterations:

Note that the convergence condition
performed only for the first system. We calculate 3 first approximations to the solution in each case.

1st system:

The exact solution will be the values: x 1 = 1.4, x 2 = 0.2 . The iterative process converges.

2nd system:

It can be seen that the iterative process diverges.

Exact solution x 1 = 1, x 2 = 0.2 .

3rd system:

It can be seen that the iterative process looped.

Exact solution x 1 = 1, x 2 = 2 .

Let the matrix of the system of equations A be symmetric and positive definite. Then, for any choice of the initial approximation, the Seidel method converges. Additional conditions on the smallness of the norm of some matrix are not imposed here.

Simple iteration method.

If A is a symmetric and positive definite matrix, then the system of equations is often reduced to an equivalent form:

x=x-τ(A x- b), τ is an iterative parameter.

The calculation formula of the simple iteration method in this case is:

x (n+1) =x n- τ (A x (n) - b).

and the parameter τ > 0 is chosen so that, if possible, the minimum value

Let λ min and λ max be the minimum and maximum eigenvalues ​​of the matrix A. The optimal choice is the parameter

In this case
accepts minimum value equal to:

Example 3 Solving systems of linear equations by simple iteration. (in MathCAD)

Let the system of equations Ax = b

To build an iterative process find our own numbers of matrix A:

- uses a built-in function to find eigenvalues.

Calculate the iterative parameter and check the convergence condition

The convergence condition is satisfied.

Let's take the initial approximation - the vector x0, set the accuracy to 0.001 and find the initial approximations using the program below:

Exact solution

Comment. If the program returns the matrix rez, then you can view all the iterations found.

1. Let a segment be known that contains one root of the equation f(x) = 0. The function f is a continuously differentiable function on this segment (f(x)нC 1 ). If these conditions are met, the simple iteration method can be used.

2. Based on the function f(x), a function j(x) is constructed that satisfies three conditions: it must be continuously differentiable (j(x)нC 1 ), such that the equation x = j(x) is equivalent to the equation f(x)=0; should also translate segment into yourself.

We will say that the function j ( x ) translates the segment [ a , b ] into itself if for any x Î [ a , b ], y = j ( x ) also belongs[ a , b ] ( y Î [ a , b ]).

The third condition is imposed on the function j(x):

Method formula: x n +1 = j(xn).

3. When these three conditions are met, for any initial approximation x 0 н sequence of iterations x n +1 = j(x n) converges to the root of the equation: x = j(x) on the segment ().

As a rule, as x 0 one of the ends is selected.

,

where e is the specified accuracy

Number x n +1 under the condition of stopping the iterative process is approximate value of the root of the equation f(x) = 0 on the segment , found by the method of simple iteration with accuracy e .

Build an algorithm for refining the root of the equation: x 3 + 5x - 1 = 0 on the segment by simple iteration with accuracy e .

1. Function f(x) = x 3 +5x-1 is continuously differentiable on a segment containing one equation root.

2. The greatest difficulty in the simple iteration method is the construction of a function j(x) that satisfies all the conditions:

Consider: .

Equation x = j 1 (x) is equivalent to the equation f(x) = 0, but the function j 1 (x) is not continuously differentiable on the interval .

Rice. 2.4. Graph of function j 2 (x)

On the other hand, therefore, . Hence: is a continuously differentiable function. Note that the equation: x = j 2 (x) is equivalent to the equation f(x) = 0 . From the graph (Fig. 2.4) it can be seen that the function j 2 (x) translates the segment into itself.

The condition that the function j(x) transforms the segment into itself can be reformulated as follows: let be the domain of the function j(x), and be the domain of j(x).

If the segment belongs to the segment , then the function j(x) takes the segment into itself.

, .

All conditions for the function j(x) are satisfied.

Formula of the iterative process: x n +1 = j 2(xn).

3. Initial approximation: x 0 = 0.

4. Condition for stopping the iterative process:

Rice. 2.5. geometric sense simple iteration method

.

When this condition is met, x n +1 – approximate value of the root on the segment, found by simple iteration with accuracy e. On fig. 2.5. the application of the simple iteration method is illustrated.

Convergence theorem and error estimate

Let the segment contains one root of the equation x = j(x), function j(x ) is continuously differentiable on the segment , translates the segment into itself, and the condition:

.

Then for any initial approximation x 0 О subsequence converges to the root of the equation y = j(x ) on the segment and the error estimate:

.

Stability of the simple iteration method. Under the conditions of the convergence theorem, the algorithm of the simple iteration method is stable.

The complexity of the simple iteration method. The amount of computer memory required to implement the simple iteration method is negligible. At each step, you need to store x n , x n +1 , q and e.

Let us estimate the number of arithmetic operations required to implement the simple iteration method. Let us write an estimate for the number n 0 = n 0 (e) such that, for all n ³ n 0, the following inequality holds:

It follows from this estimate that the closer q is to unity, the slower the method converges.

Comment. Does not exist general rule constructing j(x) from f(x) in such a way that all the conditions of the convergence theorem are satisfied. The following approach is often used: the function j is chosen as the function j(x) = x + k × f(x), where k – constant.

When programming a simple iteration method, stopping an iterative process often requires two conditions to be met simultaneously:

and .

All other iterative methods that we will consider are special cases of the simple iteration method. For example, when Newton's method is a special case of the simple iteration method.

In this section, we consider a stationary iteration process when the matrix and iteration parameter do not depend on the index , and prove the following theorem on sufficient conditions for its convergence.

Samarsky's theorem

Let is a self-adjoint positive definite matrix:

,
,

is a positive definite matrix, - positive number:

,
.

Then for any choice of zero approximation an iterative process that is defined by the recursive formula , converges to the solution of the original system.

Before proceeding to the proof of the theorem, let us discuss in more detail its main requirement, the positive definiteness of the matrix
. This requirement can be rewritten as:

,
,
.

i.e., in particular, it assumes that the matrix is positive definite. In addition, the inequality determines the interval in which the parameter can change :

.

After these remarks, we proceed to the proof of the theorem. Let us express from the ratio through :

and substitute into the recurrent formula for the iterative sequence. As a result, we get:

.

The difference between the iterative formula and is that it is homogeneous.

Matrix is positive definite. Therefore, it is non-degenerate and has an inverse
. With her help recurrence relation can be resolved regarding
:

, so
.

Multiplying both sides of the equality on the left by the matrix , we obtain one more recurrence relation

.

Consider the sequence of positive functionals:

.

Let us compose a similar expression for
and transform it using recurrent formulas and:

From the self-adjointness of the matrix and the formulas follow

As a result, the formula takes the form:

Thus, the sequence of functionals subject to the condition
forms a monotonically non-increasing sequence bounded from below by zero

.

,

where
is a strictly positive constant. As a result, according to and we will have

From this inequality and the convergence of the sequence of functionals follows that
at
. In its turn
, so

The theorem has been proven.

1. Simple iteration method.

This name was given to the method in which, as a matrix the identity matrix is ​​chosen:
, and the iterative parameter assumed to be independent of the iteration number . In other words, the simple iteration method is an explicit stationary method when the next iteration
is calculated by the recursive formula

We will assume that the matrix satisfies the condition of Samarskii's theorem,
, then the formula that determines the boundary of the interval of convergence with respect to the iterative parameter , takes the form

.

Let
- orthonormal basis of eigenvectors of the operator corresponding to the matrix . By positive definiteness, all its eigenvalues ​​are positive. Let's consider them numbered in descending order:

Let's decompose the vector
according to the basis of eigenvectors

As a result, it follows from the formula that the simple iteration method converges for any belonging to the interval

.

We will build a further study of the simple iteration method on a specific analysis of the recursive formula. Let us introduce the transition operator matrix

,

and rewrite the formula as

.

At the same time, the error
will satisfy a similar recurrence relation, only homogeneous

.

Let us prove two lemmas that allow us to more fully investigate the conditions for the convergence of the simple iteration method.

Lemma 1

Let the operator that generates the matrix , has an eigenvector with eigenvalue , then the transition operator generated by the matrix , also has an eigenvector , but with own value

.

The proof is elementary. It is carried out by direct verification

For a self-adjoint matrix matrix is also self-adjoint. Therefore, its norm is determined by the largest eigenvalue in absolute value
:

.

Lemma 2

For the simple iteration method to converge to the solution of the system for any choice of initial approximation, it is necessary and sufficient that all eigenvalues ​​of the transition operator were modulo less than one:

,

Adequacy. The condition means that the norm of the matrix , according to, will be less than unity:
. As a result, we get

At
.

Need. Let us assume that among the eigenvalues found at least one , which does not satisfy the condition of the lemma, i.e.,

.

Let us choose the zero term of the iterative sequence in the form
, where solution of the system, then the zero term of the error sequence will coincide with the eigenvector jump operator :
. As a result recurrent formula for the following members of the sequence of errors will take the form:

,
.

i.e.
. The necessity of fulfilling the inequality for all eigenvalues for the convergence of the simple iteration method is proved.

Lemma 2 defines the program for further investigation of the convergence of the simple iteration method: it is necessary to set the range of parameter variation under which all eigenvalues ​​satisfy the inequality. It's easy to do. On fig. 1 shows graphs of decreasing linear functions
. They all come from the same point
,
and go down due to negative coefficients at , and the fastest decreasing function
. When it takes on meaning
, the condition for it ceases to be fulfilled:

, at
.

Found value is the boundary of the convergence interval of the simple iteration method

.

We already know this inequality. It was obtained earlier from Samarskii's theorem as a sufficient condition for convergence. An additional analysis based on Lemma 2 allows us to refine the result. Now we have established that the membership of the iteration parameter interval is a necessary and sufficient condition for the convergence of the simple iteration method.

Let us turn to the study of the rate of convergence of the method. An estimate of the error shows that it decreases according to the law of a geometric progression with a denominator

.

Consider Fig. 2, which will help us analyze this formula. It is similar to Fig. 1, only it shows graphs of non-functions
, and their modules. At small all eigenvalues
are positive, and the largest of them is
, which decreases with increasing at the lowest speed. However, passing through the dot
eigenvalue
, changing sign, becomes negative. As a result, now its modulus with an increase does not decrease, but increases
approaching the limiting value of unity.

Find on the segment
point , in which the decreasing function
compared with an increasing function
. It is determined by the equation

which gives

.

As a result, we get:

Its smallest value is the matrix norm reaches at
:

.

The formula shows that for an ill-conditioned matrix, even with the optimal choice of the iteration parameter
matrix norm is close to unity, so that the convergence of the simple iteration method turns out to be slow in this case.

In conclusion, we note that the formula that determines the boundary of the convergence interval , and the formula for the optimal value of the iterative parameter are primarily of theoretical interest. Usually, when solving SLAE, the largest and smallest characteristic numbers of the matrix are unknown, so calculate the quantities and not possible in advance. As a result, the iterative parameter often it is necessary to select directly in the process of calculations by trial and error.

Task 2.

Consider a system of two equations with two unknowns

and construct an approximate solution for it using the simple iteration method.

Let us immediately write the solution of the system

,
,

to then be able to compare it with the members of the iterative sequence.

Let us turn to the solution of the system by the method of simple iteration. The matrix of the system has the form

.

It is self-adjoint and positive definite, since

Let us compose the characteristic equation for the matrix and find its roots:

,

,

They can be used to determine the boundary of the convergence interval and the optimal value of the iteration parameter :

,
.

To construct an iterative sequence, we choose some value of the iterative parameter on the convergence interval, for example,
. In this case, the recurrent formula for the terms of the iterative sequence takes the form:

, where

Take the simplest initial approximation
and write out the first few terms of the iterative sequence , calculating for each of them the discrepancy
. As a result, we get:

,
,
,

,
,
,

,
,
,

,
,
.

The norm of residuals, although slowly, but decreases, which indicates the convergence of the process. The same can be seen from the comparison of the terms of the iterative sequence with the solution of the system. Slow convergence is due to poor conditionality of the matrix :

.