.The methods used in lhe previous Steps for solving systems of linear equations are termed direct methods. If a direct method is used, and round-off and other errors do not arise, an exact solution is reached after a finite number of arithmetic operations. In general, of course, round-off errors do arise; and when large systems are being solved by direct methods, the growing errors can become so large as to render the results obtained quite unacceptable.
Iterative methods provide an alternative approach. Recall that an iterative method starts with an approximate solution and uses it by means of a recurrence formula to provide another approximate solution; by repeated application of the formula, a sequence of solutions is obtained which (under suitable conditions) converges to the exact solution. Iterative methods have the advantages of simplicity of operation and ease of implementation on computers, and they are relatively insensitive to propagation of errors; they would be used in preference to direct methods for solving linear systems involving several hundred variables, particularly, if many of the coefficients were zero. Systems of over 100 000 variables have been successfully solved on computers by iterative methods, whereas systems of 10 000 or more variables are difficult or impossible to solve by direct methods.
This text will only present one iterative method for linear equations, due to Gauss and improved by Seidel. We shall use this method to solve the system
.
It is suitable for implementation on computers(PSEUDO CODE)
The first step is to solve the first equation for x1, the second for x2, and the third for x3 when the system becomes:
.
An initial solution is now assumed; we shall use xl = 0, x2 = 0 and x3 = 0. Inserting these values into the right-hand side of Equation (1) yields xl = 1.3. This value for xl is used immediately together with the remainder of the initial solution (i.e., x2 = 0 and x3 = 0) in the right-hand side of Equation (2) and yields x2 =1.3 - 0.2 x 1.3 - 0 = 1.04. Finally, the values xl = 1.3 and x2 = 1.04 are inserted into Equation (3) to yield x3 = 0.936. This second approximate solution (1.3, 1.04, 0.936) completes the first iteration.
Beginning with this second approximation, we repeat the process to obtain a third approximation, etc. Under certain conditions relating to the coefficients of the system, this sequence will converge to the exact solution.
We can set up recurrence relations which show clearly how the iterative process proceeds. Denoting the k-th and k+1-th approximations by (x(k)1, x(k)2, x(k)3) and (x(k+1)1, x(k+1)2, x(k+1)3), respectively, we find
.
We begin with the starting vector x(0) = (x(0)1, (x(0)2, (x(0)3) all components of which are 0, and then apply these relations repeatedly in the order (1)', (2)' and (3)'. Note that, when we insert values for xl, x2 and x3 into the right-hand sides, we always use the most recent estimates found for each unknown.
The sequence of solutions produced by the iterative process for the above numerical example are shown in the table:
.
The student should check that the exact solution for this system is (1,1,1). It is seen that the Gauss-Seidel solutions are rapidly approaching these values; in other words, the method is converging.
Naturlly, in practice, the exact solution is unknown. It is customary to end the iterative procedure as soon as the differences between the x(k+1) and x(k) values are suitably small. 0ne stopping rule is to end the iteration when
.
becomes less than a prescribed small number (usually chosen according to the accuracy of the machine on which the calculations are carried out).
The question of convergence with a given system of equations is crucial. As in the above example, the Gauss-Seidel method may quickly lead to a solution very close to the exact one; on the other hand, it may converge too slowly to be of practical use, or it may produce a sequence which diverges from the exact solution. The reader is referred to more advanced texts (such as Conte and de Boor ( 1980)) for treatments of this question.
In order to improve the chance (and rate) of convergence, the system of equations should be rearranged before applying the iterative method, so that, as far as possible, each leading-diagonal coefficient is larger (in absolute value) than any other in its row.
a)
x - y + z =
-7,
20x + 3y - 2z = 51,
2x + 8y + 4z = 25.
Remember to rearrange! Compute the value of Sk to 5 D after each iteration.
b)
| 10x | - | y | = | 1 | ||||||||||||
| -x | + | 10y | - | z | = | 1 | ||||||||||
| - | y | + | 10z | - | w | = | 1 | |||||||||
| - | z | + | 10w | = | 1 |