Jacobi method

From CFD-Wiki

(Difference between revisions)

Jump to: navigation, search

Revision as of 23:21, 13 February 2006

Introduction

We seek the solution to set of linear equations:

$A \phi = b$

In matrix terms, the definition of the Jacobi method can be expressed as :

$\phi^{(k+1)} = D^{ - 1} \left[\left( {L + U} \right)\phi^{(k)} + b\right]$

where $D$ , $L$ , and $U$ represent the diagonal, lower triangular, and upper triangular parts of the coefficient matrix $A$ and $k$ is the iteration count. This matrix expression is mainly of academic interest, and is not used to program the method. Rather, an element-based approach is used:

$\phi^{(k+1)}_i = \frac{1}{a_{ii}} \left(b_i -\sum_{j\ne i}a_{ij}\phi^{(k)}_j\right),\, i=1,2,\ldots,n.$

Note that the computation of $\phi^{(k+1)}_i$ requires each element in $\phi^{(k)}$ except itself. Then, unlike in the Gauss-Seidel method, we can't overwrite $\phi^{(k)}_i$ with $\phi^{(k+1)}_i$ , as that value will be needed by the rest of the computation. This is the most meaningful difference between the Jacobi and Gauss-Seidel methods. The minimum ammount of storage is two vectors of size $n$ , and explicit copying will need to take place.

Algorithm

Chose an initial guess $\phi^{0}$ to the solution

for k := 1 step 1 untill convergence do

for i := 1 step until n do

$\sigma = 0$

for j := 1 step until n do

if j != i then

$\sigma = \sigma + a_{ij} \phi_j^{(k-1)}$

end if

end (j-loop)

$\phi_i^{(k)} = {{\left( {b_i - \sigma } \right)} \over {a_{ii} }}$

end (i-loop)

check if convergence is reached

end (k-loop)

Convergence

It is proven that if the absolute value of the diagonal term is always greater than the sum of the absolute values of other term in the row:

$\left | a_{ii} \right | > \sum_{i \ne j} {\left | a_{ij} \right |}$

then the method always converge.

Usually, but not always, the method converges even if this condition is not satisfied, but the diagonal terms in the matrix are greater by the absolute values than the other terms.

External link

Wikipedia article

@@ Line 32: / Line 32: @@
 ::   check if convergence is reached
 :    end (k-loop)
+==Convergence==
+It is proven that if the absolute value of the diagonal term is always greater than the sum of the absolute values of other term in the row:
+:<math>\left | a_{ii} \right | > \sum_{i \ne j} {\left | a_{ij} \right |} </math>
+then the method always converge.
+Usually, but not always, the method converges even if this condition is not satisfied, but the diagonal terms in the matrix are greater by the absolute values than the other terms.
+==External link==
+*[http://en.wikipedia.org/wiki/Jacobi_method Wikipedia article]

Jacobi method

From CFD-Wiki

Revision as of 23:21, 13 February 2006

Contents

Introduction

Algorithm

Convergence

External link

Views

My wiki

wiki navigation

wiki search

wiki toolbox