simple iteration method, also called the method of successive approximations - a mathematical algorithm for finding the values of the unknown quantities by gradually clarify it.The essence of this method is that, as the name implies, are gradually expressing an initial approximation of the subsequent ones, are becoming more refined results.This method is used to find the value of a variable in a given function, and solving systems of equations, both linear and non-linear.
Consider how this method is implemented in the solution of linear systems.Method of simple iteration algorithm is as follows:
1. Check the condition of convergence in the original matrix.The theorem of convergence if the initial matrix system has a diagonal dominance (ie, each row of the main diagonal elements must be greater in magnitude than the sum of diagonal elements of the side of the module), the method of simple iteration - convergent.
2. The matrix of the original system is not always the diagonal dominance.In such cases, the system can convert.The equations that satisfy the convergence condition is left intact, but with unsatisfying make linear combinations, iemultiply, subtract, add up the equations together to get the desired result.
If the resulting system in the main diagonal coefficients are uncomfortable, then to both sides of this equation is added terms of the form ci * xi, signs which must coincide with the signs of the diagonal elements.
3. Convert the resulting system to normal view:
x- = β- + α * x-
This can be done in many ways, for example: from the first equation express x1 through other unknown from vtorogo- x2 fromtretego- x3 etc.At the same time we use the formula:
αij = - (aij / aii)
i = bi / aii
should again ensure that the system of normal type corresponds to the convergence condition:
Σ (j = 1) | αij | ≤ 1,while i = 1,2, ... n
4. Start to use, in fact, the method of successive approximations.
x (0) - initial approximation, we express through x (1), followed by x (1) express x (2).The general formula of a matrix form looks like this:
x (n) = β- + α * x (n-1)
calculate until we reach the desired accuracy:
max | xi (k) -xi (k + 1) ≤ ε
So, let's look at the practice of the method of simple iteration.Example:
solve linear systems:
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, whether dominated by the diagonal elements of the module.
We see that the convergence condition satisfies only the third equation.The first and second convert to the first equation we add the second:
7,6x1 + 0.6x2 + 2.4x3 = 3
subtract the first from the third:
-2,7x1 + 4.2x2 + 1.2x3 = 2
We transformed the originalsystem equivalent:
7,6x1 + 0.6x2 + 2.4x3 = 3
-2,7x1 + 4.2x2 + 1.2x3 = 2
1.8x1 + 2.5x2 + 4.7x3 = 4
now give the system to 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 iteration process:
0.0789 + 0.3158 = 0,3947 ≤ 1
0.6429 + 0.2857 = 0.9286 ≤ 1
0.383+ 0.5319 = 0.9149 ≤ 1, ie,the condition is met.
0,3947
initial approximation x (0) = 0,4762
0,8511
Substitute these values into the equation of normal form, we get the following values:
0,08835
x (1) = 0,486793
0, 446,639
substitute new values, we get:
0,215243
x (2) = 0,405396
0,558336
continue to calculate until the moment has not yet come close to the values that meet specified conditions.
0,18813
x (7) = 0,441091
0,544319
0,188002
x (8) = 0,44164
0,544428
verify the correctness of the results:
45 * 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
results obtained by substituting the values found in the original equation, fully satisfy the equation.
As we can see, the method of simple iteration gives a fairly accurate results, but for the solution of this equation we had to spend a lot of time and do cumbersome calculations.
