Solving Systems of Linear Equations - Approximatemethods

Solving systems of linear equations - approximatemethods

Approximateiterative methods look for solutions by forming infinite sequencesof numbers, which, ifthey areconvergent, have limits equal tothe exact solutions of the system.

Method of consecutive approximations

This is an iteration method. Here the exact solution can be obtained as a limit of a set of consecutive approximations. Let there be given a SLAE (a system of linear algebraic equations)

(1), ,

and isthe searched solution.

The system (1) can be represented in the following way:

(2) , .

The formula (2) induces the iteration process

(3’),

or in an extended form:

from where we obtain the set of vectors

(4)

It is known from theory that the set (4) will be convergentto the root for anarbitraryinitial guess if any norm of the matrixB is smaller than 1, i.e. if at leastone of the following inequalities is fulfilled:

(5)a), b) , c) .

Here is called the sth norm (s=1,2,3) of the matrix B.

For the convergenceof the sequence of approximate solutionsto the exact solution , when , there holds the inequality

(6) .

By means of this formula there can be found a minimum number of iterations kin order to achieve the desired accuracy . For this purpose it is sufficient to solve the following inequality regarding k:

(7) .

Algorithm

1.Constructing of the matrix ,

2.Verification for convergence by means of formulas (5),

3.Finding of a minimum number of iterations by means of formulas (7),

4.Implementation of the obtained number of iterations using formulas (3).

Steps 3. and 4. can be replaced by the so called stop-criterion:

If , then with accuracy .

In a coordinate form:

If, for thenwith accuracy.

Example. By means of the method of consecutive approximations solve the system by making six iterations and work with accuracy. For initial guess approximation choose the zero vector, i. e. .

Solution:

1. .

2. Verification for convergence:

; ;

, i.e..

4. We calculate the consecutive iterations using formula (3’):

Fork=0we have:

.

For the second iteration we substitute these obtained values in the formula for k=1 and we find:

.

Do the following four iterations on your own. The results, which are rounded to the sixth digit after the decimal point, are entered in table 1. By the stop-criterion we can draw the conclusion that for k=6 the obtained accuracy is a little less than 0,001. This comparatively good speed of convergenceresults from the first norm of the matrixB, which is.

Table 1

How many iterations will be sufficient for calculating the solution of the same system with accuracy in the first norm?

Solution:Here we will apply step 3. from the algorithm. We have , from where. Alsoor and.

We solve the inequality (7) regarding kfor the first norm

We have:

.

We choose k=13.

Author: IliyaMakrelov,

PlovdivUniversity