Splitting process

This article deals with the splitting technique of numerical mathematics. This is to be distinguished from splitting procedures in tax and duty law such as the German spouse splitting .

In numerical mathematics , splitting methods are iterative methods for solving linear systems of equations with a matrix and right-hand side.In contrast to direct methods , starting from a starting approximation , one approaches the desired solution step by step and terminates if the accuracy is high enough. ${\displaystyle Ax=b}$ ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle b\in \mathbb {C} ^{n}.}$

description

The method results from splitting the system matrix with an invertible matrix . ${\displaystyle A=B+(A-B)}$ ${\displaystyle B\in \mathbb {C} ^{n\times n}}$

${\displaystyle Ax=b\Leftrightarrow B^{-1}(B+(A-B))x=B^{-1}b.}$

The fixed point equation is obtained from this

${\displaystyle x=B^{-1}(B-A)x+B^{-1}b}$.

With , where denotes the identity matrix , the fixed point iteration results ${\displaystyle M=B^{-1}(B-A)=I-B^{-1}A}$ ${\displaystyle I}$

1. Choose a starting vector . ${\displaystyle x_{0}\in \mathbb {C} ^{n}}$
2. Set . ${\displaystyle x_{k}=Mx_{k-1}+B^{-1}b=(I-B^{-1}A)x_{k-1}+B^{-1}b}$

The iteration can be terminated if the norm of the residual falls below a given error limit . The method converges precisely when the spectral radius of the matrix is less than 1. With the help of Banach's fixed point theorem , the linear speed of convergence also follows the entire process class. The smaller the spectral radius, the faster the method converges. If and only differ slightly, the perturbation lemma can be used to show that the spectral radius is also small. This results in a contrast between fast convergence ( approximates very well) and low costs per iteration ( can easily be inverted). Overall, these methods are too slow for many practical problems. However, because of their ease of use, they are good preconditioners . In addition, many splitting processes are suitable as smoothers in a multi-grid process. ${\displaystyle r_{k}=b-Ax_{k}}$ ${\displaystyle M}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle M}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle B}$

Examples

• Jacobi method : is the main diagonal of . ${\displaystyle B=\operatorname {diag} (A)}$ ${\displaystyle A}$
• Richardson method : with one parameter . ${\displaystyle B=\tau \cdot I}$ ${\displaystyle \tau }$
• Gauss-Seidel method : the lower left triangular matrix + main diagonal. ${\displaystyle B=D+L}$
• Others are the SOR procedure and SSOR. ${\displaystyle B=(1/\omega )D+L}$
• a way of iterative refinement for the Gaussian elimination method : . ${\displaystyle B=LR}$

Modifications

A distinction is made between stationary processes with a constant iteration matrix and unsteady processes, where the matrices may depend on the index . ${\displaystyle M}$ ${\displaystyle i}$

literature

• A. Meister: Numerics of linear systems of equations , 2nd edition, Vieweg 2005, ISBN 3528131357