Jacobi method

This article covers the procedure for solving systems of linear equations. For the procedure of the same name for the calculation of eigenvalues, see Jacobi procedure (eigenvalues) .

In numerical mathematics , the Jacobi method , also called total step method , is an algorithm for the approximate solution of linear systems of equations . Like the Gauss-Seidel method and the SOR method , it is a special splitting method . It is named after Carl Gustav Jacob Jacobi .

The method was developed because the Gaussian elimination method represents an exact solution, but is very prone to calculation errors . An iterative approach typically does not have this disadvantage.

Description of the procedure

A linear system of equations with variables and equations is given. ${\displaystyle n}$ ${\displaystyle n}$

${\displaystyle {\begin{matrix}a_{11}\cdot x_{1}+\dotsb +a_{1n}\cdot x_{n}&=&b_{1}\\a_{21}\cdot x_{1}+\dotsb +a_{2n}\cdot x_{n}&=&b_{2}\\&\vdots &\\a_{n1}\cdot x_{1}+\dotsb +a_{nn}\cdot x_{n}&=&b_{n}\\\end{matrix}}}$

To solve this, the -th equation is solved for the -th variable , ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle x_{i}}$

${\displaystyle x_{i}^{(m+1)}:={\frac {1}{a_{ii}}}\left(b_{i}-\sum _{j\not =i}a_{ij}\cdot x_{j}^{(m)}\right),\,i=1,\dotsc ,n}$

and iteratively repeats this replacement, starting from a start vector . As a condition for the feasibility it results that the diagonal elements have to be different from zero. Since the calculation of a component of the closest approximation is independent of the other components, the method, in contrast to the Gauss-Seidel method , is suitable for use on parallel computers. ${\displaystyle x^{(0)}}$ ${\displaystyle a_{ii}}$

The algorithm in pseudocode is:

Gegeben Startvektor  ${\displaystyle x^{\text{alt}}}$
für  ${\displaystyle m=1,\dotsc }$ bis Erfüllung eines Abbruchkriteriums
   ${\displaystyle x=b}$
  für  ${\displaystyle i=1}$ bis  ${\displaystyle n}$
       für  ${\displaystyle j=1}$ bis  ${\displaystyle n}$
         falls  ${\displaystyle j\not =i}$
             ${\displaystyle x_{i}=x_{i}-a_{ij}x_{j}^{\text{alt}}}$;
       ende
        ${\displaystyle x_{i}=x_{i}/a_{ii}}$;
  ende
   ${\displaystyle x^{\text{alt}}=x;}$
ende

The arbitrary initial assignment of the variable vector was assumed as the input variable of the algorithm, the approximate solution is the vectorial return variable.

In the case of sparsely populated matrices , the effort of the process per iteration is significantly reduced.

Description in matrix notation

The matrix of the linear system of equations is broken down into a diagonal matrix , a strict lower triangular matrix and a strict upper triangular matrix , so that: ${\displaystyle A}$ ${\displaystyle A\cdot x=b}$ ${\displaystyle D}$ ${\displaystyle L}$ ${\displaystyle U}$

${\displaystyle A=L+D+U}$.

The above component-wise iteration rule can then be represented for the complete vector as follows:

${\displaystyle x^{(m+1)}=D^{-1}\left(b-\left(L+U\right)x^{(m)}\right)}$.

Usually for embedding as a preconditioner in other iterative methods such as Krylow's subspace method , the preconditioner is written as a matrix , with an approximation to which a linear system of equations can be solved favorably . It applies to the Jacobi method . For the residual is just the approximate solution. The relationship follows immediately: ${\displaystyle M}$ ${\displaystyle M}$ ${\displaystyle A^{-1}}$ ${\displaystyle M^{-1}\cdot u=v}$ ${\displaystyle u}$ ${\displaystyle M=D^{-1}}$ ${\displaystyle r^{(m)}=b-A\cdot x^{(m)}}$ ${\displaystyle x^{(m+1)}-x^{(m)}}$ ${\displaystyle M=D^{-1}}$

${\displaystyle x^{(m+1)}=D^{-1}\cdot \left(b-\left(L+D+U\right)\cdot x^{(m)}+D\cdot x^{(m)}\right)=D^{-1}\cdot r^{(m)}+x^{(m)}}$,

${\displaystyle x^{(m+1)}-x^{(m)}=D^{-1}\cdot r^{(m)}}$.

Convergence study

As with all splitting methods, convergence is investigated using Banach's fixed point theorem . The method converges when the spectral radius of the iteration matrix is smaller than one. This arises in particular when the system matrix is strictly diagonally dominant or, more generally, irreducibly diagonally dominant . ${\displaystyle D^{-1}(D-A)}$ ${\displaystyle A}$

Extension to nonlinear systems of equations

The idea of ​​the Jacobi method can be extended to nonlinear systems of equations with a multi-dimensional nonlinear function . As in the linear case, in the -th step the -th equation is solved with respect to the -th variable, using the previous approximate value for the other variables: ${\displaystyle f(x)=g}$ ${\displaystyle f}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$

For until fulfillment of a termination criterion ${\displaystyle k=1,\dotsc }$

For : ${\displaystyle i=1,\dotsc ,n}$

Dissolve after . ${\displaystyle f_{i}(x_{1}^{k},\dotsc ,x_{i-1}^{k},x_{i}^{k+1},x_{i+1}^{k},\dotsc ,x_{n}^{k})=g_{i}}$ ${\displaystyle x_{i}^{k+1}}$

Here, solving is usually to be understood as the application of a further iterative method to solve non-linear equations. In order to distinguish this method from the Jacobi method for systems of linear equations, the Jacobi process is often used . The convergence of the process follows from Banach's Fixed Point Theorem again as linear.

literature

• A. Meister: Numerics of linear systems of equations , 2nd edition, Vieweg 2005, ISBN 3528131357
• R. Barrett et al .: Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods , 2nd Edition, SIAM Philadelphia, 1994
• Plato, Robert: Numerical Mathematics Compact . Vieweg, 2004, ISBN 3-528-13153-5 , pp. 262 .
• WC Rheinboldt: Methods for Solving Systems of Nonlinear Equations , 2nd edition, SIAM, 1998, ISBN 089871415X

Web links

• Eric W. Weisstein et al. "Jacobi Method" MathWorld
• Total and single step method or Jacobi and Gauss-Seidel method for N = 3 (pdf; 91 kB) Jacobi and Gauss-Seidel method explained in an understandable way, including Matlab programs.