Hence it follows that α ≈ | φ ′ (ξ) | (\displaystyle \alpha \approx |\varphi "(\xi)|). Thus, for the method to converge, it is sufficient that ∀ x ∈ [ a , b ] | φ ′ (x) | ≤ 1. (\displaystyle \forall x\in \quad |\varphi "(x)|\leq 1.)

General algorithm of successive approximations[ | ]

As applied to the general case of operator equations, this method is called method of successive approximations or simple iteration method. However, the equation can be transformed to the contraction mapping , which has the same root, in different ways. This gives rise to a number of particular methods that have both linear and higher convergence rates.

As applied to SLAU[ | ]

Consider the system:

( a 11 x 1 + … + a 1 n x n = b 1 … a n 1 x 1 + … + a n n x n = b n (\displaystyle \left\((\begin(array)(ccc)a_(11)x_(1)+ \ldots +a_(1n)x_(n)&=&b_(1)\\\ldots &&\\a_(n1)x_(1)+\ldots +a_(nn)x_(n)&=&b_(n) \end(array))\right.)

For it, the iterative calculation will look like this:

(x 1 x 2 ⋮ x n) i + 1 = (a 11 + 1 a 12 … a 1 n a 21 a 22 + 1 … a 2 n ⋮ ⋮ ⋱ ⋮ a n 1 a n 2 … a n n + 1) (x 1 x 2) ⋮ x n) i − (b 1 b 2 ⋮ b n) (\displaystyle \left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\end (array))\right)^(i+1)=\left((\begin(array)(cccc)a_(11)+1&a_(12)&\ldots &a_(1n)\\a_(21)&a_( 22)+1&\ldots &a_(2n)\\\vdots &\vdots &\ddots &\vdots \\a_(n1)&a_(n2)&\ldots &a_(nn)+1\end(array))\right )\left((\begin(array)(c)x_(1)\\x_(2)\\\vdots \\x_(n)\end(array))\right)^(i)-\left( (\begin(array)(c)b_(1)\\b_(2)\\\vdots \\b_(n)\end(array))\right))

The method will converge at a linear rate if ‖ a 11 + 1 … a 1 n ⋮ ⋱ ⋮ a n 1 … a n n + 1 ‖< 1 {\displaystyle \left\|{\begin{array}{ccc}a_{11}+1&\ldots &a_{1n}\\\vdots &\ddots &\vdots \\a_{n1}&\ldots &a_{nn}+1\end{array}}\right\|<1}

Double vertical bars mean some matrix norm.

Solution of the equation f(x)=0 by Newton's method, initial approximation: x 1 =a.

Newton's method (tangent method)[ | ]

One-dimensional case[ | ]

Optimizing the transformation of the original equation f (x) = 0 (\displaystyle f(x)=0) into contraction mapping x = φ (x) (\displaystyle x=\varphi (x)) allows you to get a method with a quadratic rate of convergence.

For the mapping to be most efficient, it is necessary that at the point of the next iteration x ∗ (\displaystyle x^(*)) carried out φ ′ (x ∗) = 0 (\displaystyle \varphi "(x^(*))=0). We will look for a solution to this equation in the form φ (x) = x + α (x) f (x) (\displaystyle \varphi (x)=x+\alpha (x)f(x)), then:

Let's use what f (x) = 0 (\displaystyle f(x)=0), and we get the final formula for α (x) (\displaystyle \alpha (x)):

With this in mind, the contraction function will take the form:

Then the algorithm for finding a numerical solution to the equation f (x) = 0 (\displaystyle f(x)=0) reduces to an iterative calculation procedure:

Iterative Methods

Iterative methods assume the implementation of the following three stages: construction of an iterative process converging to the exact solution for calculating successive approximations (i.e., constructing a sequence of vectors converging to the exact solution ; determination of the convergence criterion of this process, which allows determining the moment of achieving the required accuracy; study of the rate of convergence and optimization of the iterative process in order to reduce the number of operations required to achieve the required accuracy.

Iterative methods make it possible to obtain a solution with a predetermined accuracy, if the convergence of the method is proved. Iterative methods do not give a strictly exact solution, since it is achieved as a limit of a sequence of vectors. The direct method generally gives an exact solution, but due to rounding errors occurring on all computers, it cannot be reached, and a priori it is even difficult to assess how much this solution differs from the exact one. In connection with the above, iterative methods sometimes make it possible to obtain a solution with greater accuracy than direct ones.

Consider several iterative methods for solving linear equations.

Simple iteration method

In the simple iteration method, system (2.1) of linear algebraic equations ax = b is reduced to an equivalent system of the form

The solution of system (2.9) and, consequently, the solution of the original system (2.1) is sought as the limit of the sequence of vectors for :

k = 0, 1, 2,…,(2.10)

where is the initial approximation for the solution vector.

A sufficient condition for the convergence of the simple iteration method is determined by the following theorem.

THEOREM 1. If any norm of the matrix consistent with the considered norm of the vector is less than unity (), then the sequence in the simple iteration method converges to the exact solution of system (2.9) at a rate not less than the rate of a geometric progression with a denominator for any initial approximation .

PROOF. To prove the theorem, we introduce an error . Subtracting equality (2.10) from the relation, we obtain . Passing to the norms, we have

Note that the inequality from the previous expression is the consistency condition for the norm of the matrix and vector. If a , then for any initial error vector (or otherwise, for any initial vector ), the error rate tends to zero no slower than a geometric progression with the denominator .

If we choose the norm as the matrix norm or then to solve the question of the convergence of the simple iteration method, one can use the corollary from Theorem 1: the simple iteration method converges if one of the following conditions is satisfied for the matrix:

, i =1,2, …, n,

, j = 1, 2, …, n.(2.11)

The simplest and most common way to bring the system Ax=b to the form (2.9), convenient for iterations, is the selection of diagonal elements, with each i-th the equation is resolved with respect to i-th unknown:

, i = 1, 2, …, n, (2.12)

and the simple iteration method can be written as

The matrix then has the form

.

The element of this matrix can be written as where is the Kronecker symbol. In this case, a sufficient condition for the convergence of the simple iteration method can be formulated as the condition for the dominance of the diagonal elements of the matrix BUT, which follows from (2.11) and the notation of the matrix , i.e.

i = 1, 2, …, n.

We emphasize once again that the considered forms of the condition for the convergence of the iteration method are only sufficient. Their execution guarantees the convergence of the method, but their failure in the general case does not mean that the simple iteration method diverges. A necessary and sufficient condition for the convergence of the simple iteration method is the condition that the integer part (where is the maximum modulo eigenvalue of the matrix BUT); this condition is rarely used in computational practice.

Let us turn to the question of estimating the error of the solution. Of interest are two relations for estimating the error of the solution: the first relates the norm of the error to the norm of the difference of two successive approximations and can be used to estimate the error only in the process of calculations; the second relates the norm of the error to the norms of the vector of the initial approximation and the vector of the free term in system (2.9). The necessary relations are given by the following two theorems.

THEOREM 2. If any norm of the matrix consistent with the considered norm of the vector X

. (2.13)

PROOF. Let us subtract equality (2.10) from equality:

Subtracting from both parts the approximation value , we transform this ratio to the form

Passing to the norms, we get

Since, by the hypothesis of the theorem,

Using the relation from which it follows that finally we get:

THEOREM 3. If any norm is a matrix consistent with the considered norm of the vector X, less than one (), then the following error estimate takes place:

Let's make two remarks. First, relation (2.13) can be written as

which makes it possible to obtain an estimate of the error based on the results of the first two iterations. First, when using the iteration method, it is sometimes recommended to use the norm of the difference of two successive approximations as an estimate of the calculation error. It follows from the correlations for the error that this is not true in the general case. If the norm is close to unity, then the coefficient at can be quite large.

The errors of successive iterations are related by the relation

those. the error changes linearly at a step. The method is said to have linear convergence or first order convergence. However, the number of iterations required to achieve the required accuracy depends on the value and initial approximation of .

Thus, using the simple iteration method as an example, three stages of iterative methods are demonstrated: construction of a sequence of vectors generated by formula (1.10); determination of the convergence condition according to Theorem 1 and an estimate of the rate of convergence using Theorems 2 and 3.

Seidel method

The simple iteration method does not use the seemingly obvious possibility of improving the convergence of the iterative process - the immediate introduction of the newly calculated components of the vector into the calculation. This possibility is used in the iterative Seidel method. The iterative process for system (2.9) is carried out in this case according to the relation

i = 1, 2, …, n (2.14)

or for system (1.1)

Without going into details, we note that the Seidel iteration method often indeed leads to faster convergence than the simple iteration method. However, there are cases where the Seidel iteration method converges more slowly than the simple iteration method, and even cases where the simple iteration method converges but the Seidel iteration method diverges.

Note that the Seidel method converges, if matrix BUT positive definite and symmetrical.

Let us show that the Seidel iteration method is equivalent to some simple iteration method with a specially constructed matrix and vector in relation (2.10). To do this, we write the system (2.14) in the form Matrix (E-H) is a lower triangular matrix with diagonal elements equal to one. Therefore, the determinant of this matrix is ​​non-zero (equal to one) and it has an inverse matrix . Then

Comparing this relation with solution (2.10), we can conclude that the Seidel iteration method is indeed equivalent to the simple iteration method in the sense that, to establish the condition and the convergence criterion for the Seidel iteration method, one can use the theorems given for the simple iteration method, if we set The iterative process for system (2.12) can also be written in a more general form, namely

Let a system of n algebraic equations with n unknowns be given:

Simple iteration method algorithm:

Note that here and in what follows, the subscript denotes the corresponding component of the vector of unknowns, and the superscript denotes the iteration (approximation) number.

Then a cyclic mathematical process is formed, each cycle of which represents one iteration. As a result of each iteration, a new value of the vector of unknowns is obtained. To organize the iterative process, we write system (1) in the above form. In this case, the terms on the main diagonal are normalized and remain to the left of the equal sign, while the rest are transferred to the right side. Reduced system of equations looks like:

notice, that will never be reached, however, with each subsequent iteration, the vector of unknowns gets closer and closer to the exact solution.

12. The main iterative formula used in the simple iteration method for solving a nonlinear equation:

13. Criterion for stopping the iterative process in the simple iteration method for solving a nonlinear equation:

The iterative process ends if for each i-th component of the vector of unknowns the condition for achieving accuracy is satisfied.
notice, that exact solution in simple iteration method will never be reached, however, with each subsequent iteration, the vector of unknowns is getting closer and closer to the exact solution

14. Criteria for choosing the auxiliary function F(x) for the iteration segment of the interval :

When performing a math test for solving the simple iteration method, the convergence condition must first be checked. For the convergence of the method, it is necessary and sufficient that in the matrix A the absolute values ​​of all diagonal elements are greater than the sum of the modules of all other elements in the corresponding row:

Disadvantage of iterative methods This is a fairly stringent convergence condition, which is far from being satisfied for all systems of equations.

If the convergence condition is satisfied, then at the next stage it is necessary to set the initial approximation of the vector of unknowns, which is usually the zero vector:

15. The Gauss method used to solve systems of linear equations provides for:

The method is based on matrix transformation to triangular form. This is achieved by sequential elimination of the unknowns from the equations of the system.

The method of simple iteration, also called the method of successive approximation, is a mathematical algorithm for 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 a given function, as well as in solving systems of equations, both linear and non-linear.

Let us consider how this method is implemented when solving 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 of simple iterations is convergent.

2. The matrix of the original system does not always have diagonal dominance. In such cases, the system can be modified. 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) . The general formula in matrix form looks like this:

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.