Iterative Solution of Linear Equations



Iterative Solution of Linear Equations

Preface to the existing class notes

At the risk of mixing notation a little I want to discuss the general form of iterative methods a general level. We are trying to solve a linear system Ax=b, in a situation where cost of direct solution for matrix A is prohibitive. One approach starts by writing A as the sum of two matrices A=E+F. With E chosen so that a linear system in the form Ey=c can be solved easily by direct means. Now we rearrange the original linear equation to the form:

Ex = b - Fx

Introduce a series of approximations to the solution x starting with an initial guess x(0) and proceeding to the latest available approximation x(j). The next approximation is obtained from the equation:

E x(j+1) = b - F x(j)

or

x(j+1) = E-1 (b - F x(j)).

Understand that we never actually generate the inverse of E, just solve the equation for x(j+1).

To understand convergence properties of this iteration introduce the residual r(j) = b - A x(j). Using this definition and the definition of the iteration, we get the useful expression:

r(j+1) = FE-1 r(j),

or

r(j) = (FE-1)j r(j).

If you know something about linear algebra this tells you that the absolute values of eigenvalues of FE-1 should be less than one.

Another approach is to choose a matrix M such that the product of M-1 and A is close to the identity matrix and the solution of an equation like My=c can be obtained without too much effort. The revised problem can be cast either in the form

M-1Ax = M-1b

Or

AM-1 y = b where x =

Beginning of normal ME540 Notes

a) Introduction

i) Procedure – general

1) Assume initial values for the variable field

2) Use the nodal finite difference equations one at a time or in groups to obtain an improved value for the variables. Repeat the procedure until a converged solution is obtained.

ii) Advantages

Iterative methods are used because:

Requires less computer storage.

Is reasonably computational fast.

There is, however, no guarantee that a converged solution can be obtained.

iii) Symbols to be used

[pic]exact solution of differential equation

[pic]exact solution of finite difference equations

[pic]computer solution to finite difference equations

iv) Convergence

The solution is said to be converged when

Limit [pic]

[pic]

where j is an index for the iteration number.

b) Procedure – details

i) Rearrange coefficient matrix

Solution required H[pic]

Modify H matrix by taking each equation and dividing it by diagonal coefficient to form a “C” matrix

[pic] , [pic]

New Expression

[pic]

The C Matrix will have all its diagonal elements with the value 1.

ii) Iterative set of equations

[pic]initial value of variable

for calculation

[pic]

residual [pic]

Introduce identity matrix, I

[pic]

Add [pic]to both sides of [pic]

[pic]to [pic]

Transpose [pic] and let [pic] on the right hand

side be [pic]

[pic]

[pic]

[pic]

Thus [pic] or [pic]

The iterative equation can be expressed as

[pic]

[pic]

C = I - B

Introduce a lower (L) and upper (U) matrix

[pic]

[pic]

[pic]

This is known as the Jacobi method

Example

Iterative equation for node 5

[pic]

iii) Error propagation and convergence

1) Error propagation

known [pic]

[pic]

Introduce computational error

[pic]

Note [pic]

So [pic]

[pic]

Back substitute to obtain

[pic]

Indicating that errors are propagated in an identical manner

To the propagation of [pic]

2) Convergence

Limit [pic]

[pic]

residual [pic]

Convergence checks

L2 Norm [pic]

Limit [pic] (with machine accuracy)

[pic]

Other tests

Maximum

(Local) [pic]

Maximum

(Global) [pic]

or [pic]

Will the iterative solution selected converge?

Error propagation

[pic]

To answer this question we look at the characteristics roots of

the B matrix.

[pic] Latent root of “B” matrix

[pic] vector such that the equality is satisfied

Re-arranging

[pic]

Non-trivial solution [pic]

[pic]

Expand as a polynomial

[pic]

The characteristic root are the [pic]’s

(Eigenvalues)

Maximum root [pic]is called the spectral radius of the matrix [pic]

The polynomial will converge to zero if:

[pic] ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download