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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- error in the method of false position
- graph clustering using the heat kernel and spectral geometry
- iterative solution of linear equations
- package modules and corresponding functions
- atlantic international university bachelor master
- from back analysis to run out prediction a case study in
- qr factorization in
Related searches
- solution of linear system calculator
- solving systems of linear equations calculator
- solutions of linear equations calculator
- solving systems of linear equations by substitution
- system of linear equations by substitution calculator
- solving systems of linear equations worksheet
- applications of linear equations calculator
- solve systems of linear equations calculator
- systems of linear equations word problem
- system of linear equations word problem pdf
- applications of linear equations examples
- systems of linear equations examples