Jacobi method

Jacobi method

The Jacobi method is an algorithm in linear algebra for determining the solutions of a system of linear equations with largest absolute values in each row and column dominated by the diagonal element. Each diagonal element is solved for, and an approximate value plugged in. The process is then iterated until it converges. This algorithm is a stripped-down version of the Jacobi transformation method of matrix diagonalization. The method is named after German mathematician Carl Gustav Jakob Jacobi.

We seek the solution to set of linear equations, written in matrix terms as

: A x = b., Let A = D+left({L + U} ight), where D, L, and U represent the diagonal, lower triangular, and upper triangular parts of the coefficient matrix A. Then the equation above can be rephrased as:: D x+left({L + U} ight)x = b.
Moreover, : x = D^{ - 1} left [b -left({L + U} ight)x ight] ,
if a_{ii} eq 0 for each i.By iterative rule, the definition of the Jacobi method can be expressed as : : x^{(k+1)} = D^{ - 1} left [b-left({L + U} ight)x^{(k)} ight] ,
where k is the iteration count. Often an element-based approach is used:: x^{(k+1)}_i = frac{1}{a_{ii left(b_i -sum_{j e i}a_{ij}x^{(k)}_j ight),, i=1,2,ldots,n.

Note that the computation of x^{(k+1)}_i requires each element in x^{(k)}, except itself. Then, unlike in the Gauss–Seidel method, we can't overwrite x^{(k)}_i, with x^{(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 amount of storage is two vectors of size n, and explicit copying will need to take place.

Algorithm

Choose an initial guess x^{0} to the solution
: for k := 1 step 1 until 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} x_j^{(k-1)} :::: end if::: end (j-loop)
::: x_i^{(k)} = left( {b_i - sigma } ight)} over {a_{ii} :: end (i-loop):: check if convergence is reached: end (k-loop)

Convergence

The method will always converge if the matrix "A" is strictly or irreducibly diagonally dominant. Strict row diagonal dominance means that for each row, the absolute value of the diagonal term is greater than the sum of absolute values of other terms:

:left | a_{ii} ight | > sum_{i e j} {left | a_{ij} ight .

The Jacobi method sometimes converges even if this condition is not satisfied. It is necessary, however, that the diagonal terms in the matrix are greater (in magnitude) than the other terms.

ee also

*Gauss–Seidel method

External links

*CFDWiki|name=Jacobi_method
* [http://www.math-linux.com/spip.php?article49 Jacobi Method from www.math-linux.com]
* [http://mathworld.wolfram.com/JacobiMethod.html Jacobi Method at Math World]
* [http://math.fullerton.edu/mathews/n2003/GaussSeidelMod.html Module for Jacobi and Gauss–Seidel Iteration]
* [http://pagerank.suchmaschinen-doktor.de/matrix-inversion.html Numerical matrix inversion]


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Jacobi — may refer to:People with the surname Jacobi: *Jacobi (surname)Other: * Jacobi Medical Center, New York * Jacobi sum, a type of character sum in mathematics * Jacobi method, a method for diagonalization of matrices in mathematics * Jacobi… …   Wikipedia

  • Jacobi eigenvalue algorithm — The Jacobi eigenvalue algorithm is a numerical procedure for the calculation of all eigenvalues and eigenvectors of a real symmetric matrix. Description Let varphi in mathbb{R}, , 1 le k < l le n and let J(varphi, k, l) denote the n imes n matrix …   Wikipedia

  • Jacobi-Verfahren — In der numerischen Mathematik ist das Jacobi Verfahren, auch Gesamtschrittverfahren genannt, ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen Ax = b. Es ist, wie das Gauß Seidel Verfahren und das SOR Verfahren, ein… …   Deutsch Wikipedia

  • Method of quantum characteristics — In quantum mechanics, quantum characteristics are phase space trajectories that arise in the deformation quantization through the Weyl Wigner transform of Heisenberg operators of canonical coordinates and momenta. These trajectories obey the… …   Wikipedia

  • Carl Gustav Jacob Jacobi — Carl Jacobi Carl Gustav Jacob Jacobi Born December 10, 1804(1804 …   Wikipedia

  • Método de Jacobi — En análisis numérico el método de Jacobi es un método iterativo, usado para resolver sistemas de ecuaciones lineales del tipo Ax = b. El algoritmo toma su nombre del matemático alemán Carl Gustav Jakob Jacobi. El método de Jacobi consiste en usar …   Wikipedia Español

  • Relaxation method — In numerical mathematics, the relaxation method is a method for obtaining numerical approximations to the solutions of systems of equations, including certain types of elliptic partial differential equations, in particular Laplace s equation and… …   Wikipedia

  • Gauss–Seidel method — The Gauss–Seidel method is a technique used to solve a linear system of equations. The method is named after the German mathematicians Carl Friedrich Gauss and Philipp Ludwig von Seidel. The method is an improved version of the Jacobi method. It… …   Wikipedia

  • Durand–Kerner method — In numerical analysis, the Durand–Kerner method established 1960–66 and named after E. Durand and Immo Kerner, also called the method of Weierstrass, established 1859–91 and named after Karl Weierstrass, is a root finding algorithm for… …   Wikipedia

  • Iterative method — In computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”