The simple iteration method for solving systems of linear equations (SLAE)

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 gradual refinement. The essence of this method is that, as the name implies, gradually developing from the initial approximation the subsequent ones receive more and more refined results. This method is used to find the value of a variable in a given function, as well as for solving systems of equations, both linear and nonlinear.

Let us consider how this method is implemented in solving SLAE. The simple iteration method has the following algorithm:

1. Verification of the fulfillment of the convergence condition in the original matrix. Convergence theorem: if the initial matrix of the system has a diagonal predominance (ie, in each line the elements of the main diagonal should be larger in modulus than the sum of the elements of the side diagonals modulo), then the simple iteration method is convergent.

2. The matrix of the original system does not always have a diagonal predominance. In such cases, the system can be converted. Equations that satisfy the convergence condition are left untouched, and with non-satisfying make up linear combinations, i.e. Multiply, subtract, add the equations to each other until the desired result is obtained.

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

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

X ^- = β ^- + α * x ^-

This can be done in a variety of ways, for example: from the first equation, express x ₁ through other unknowns, from the second x ₂ , from the third x ₃ , etc. We use the following formulas:

Α _ij = - (a _ij / a _ii)

_I = b _i / a _ii
It is again necessary to verify that the resulting system of normal form corresponds to the condition of convergence:

Σ (j = 1) | α _ij | ≤ 1, with i = 1,2, ... n

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

X ^{( 0)} is the initial approximation, we express x ^{( 1)} through it, then we express x ^{( 2)} by x ^{( t )} . The general formula in the matrix form looks like this:

X ^(N) = β ^- + α * x ^(n-1)

We calculate until we achieve the required accuracy:

Max | x _i (k) -x _i (k + 1) ≤ ε

So, let's analyze in practice the method of simple iteration. Example:
Decide SLAU:

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

Let's see if the diagonal elements predominate in modulus.

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

7.6x1 + 0.6x2 + 2.4x3 = 3

From the third we subtract the first:

-2.7x1 + 4.2x2 + 1.2x3 = 2

We have transformed 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 we bring the system to a normal form:

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 satisfied.

0.3957
The initial approximation x ^{( 0)} = 0.4762
0,8511

We substitute these values into the equation of the normal form, we obtain the following values:

0.08835
X ⁽¹⁾ = 0.486793
0,446639

Substituting new values, we get:

0.215243
X ⁽²⁾ = 0.405396
0.558336

Continue the calculations until the moment we approach the values that satisfy the given condition.

0,18813

X ⁽⁷⁾ = 0.441091

0.544319

0,188002

X ⁽⁸⁾ = 0.44164

0.544428

Let's check the correctness of the 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 values found in the initial equations completely satisfy the conditions of the equation.

As we see, the simple iteration method yields fairly accurate results, but to solve this equation we had to spend a lot of time and do a lot of cumbersome calculations.