The simple iteration method, also called the sequential approximation method, 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 obtain more and more precise results. This method is used to find the value of a variable in a given function, as well as when solving systems of equations, both linear and non-linear.
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 a diagonal prevalence (i.e., in each row the elements of the main diagonal must be larger in absolute value than the sum of the elements of the side diagonals in absolute value), then the simple iteration method is convergent.
2. The matrix of the original system does not always have a diagonal prevalence. In such cases, the system can be transformed. Equations satisfying the convergence condition are left untouched, and with unsatisfying, they are linear combinations, i.e. multiply, subtract, add equations to each other to obtain the desired result.
If the resulting system has inconvenient coefficients on the main diagonal, then terms of i * x i are added to both sides of this equation , the signs of which must coincide with the signs of diagonal elements.
3. Converting the resulting system to normal view:
x - = β - + α * x -
This can be done in a variety of ways, for example, as follows: from the first equation express x 1 through other unknowns, from the second x 2 , from the third x 3 , etc. In this case, 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 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 itself.
x ( 0) is the initial approximation, we express x ( 1) through it, then we express x ( 2) through x ( 1 ) . 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 take a look at the simple iteration method in practice. Example:
Solve 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 prevail modulo.
We see that only the third equation satisfies the convergence condition. We transform the first and second, 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 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 we bring the system to its normal form:
x1 = 0.3947-0.0789x2-0.3158x3
x2 = 0.4762 + 0.6429x1-0.2857x3
x3 = 0.8511-0.383x1-0.5319x2
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.3947
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 (1) = 0.486793
0.446639
Substitute new values, we get:
0.215243
x (2) = 0.405396
0,558336
We continue the calculation until we get closer to the values satisfying the given condition.
0.18813
x (7) = 0.441091
0.544319
0.188002
x (8) = 0.44164
0,544428
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 found values in the original equations completely satisfy the conditions of the equation.
As we can see, the simple iteration method gives fairly accurate results, but to solve this equation we had to spend a lot of time and do cumbersome calculations.