Kaczmarz method

The based on the work of the Polish mathematician Stefan Kaczmarz Kaczmarz method is the iterative solution of linear systems of equations of the form Ax = b, where A is a separable and may over defined matrix, b is the given solution and x is the desired solution vector. It is an iterative algorithm that has found its way into, among other things, computed tomography and digital signal processing.

In contrast to most other iterative solution method such as the Gauss-Seidel method, the algorithm only requires a Kaczmarz invertible, but not positive definite, the matrix A. For this reason, the method for virtually all applications be used without problems although techniques for specific problems can be much faster. However, a randomized version of the Kaczmarz method shows much better convergence in the case of overdetermined systems of equations than other iterative solution process.

The original algorithm

Given a real or complex m × n matrix A ( m> = n) of full rank, and a vector b. The following iteration formula improved with each run, the approximation to the solution x of the equation Ax = b:

, where

Th row of the matrix transpose of A meant - Here with the i.

The start value can be chosen randomly, but should, if a simple estimate with respect to the solution can be taken to be chosen as close to the solution.

Randomized algorithm

As mentioned above, there is a variant of the method, the overdetermined system of equations converge much faster in the case. In this case, better convergence is achieved not only for solving highly overdetermined systems of equations, but also for example when solving systems with 10% more equations than unknowns. To this end, ( the name of the method therefore ) must, in the above iteration equation that i do not depend on k, but randomly be selected. The likelihood of a given I is proportional to, for each iteration.

Swell

  • S. Kaczmarz: Przyblizone rozwiazywanie ukladów równan liniowych. - Approximate resolution of systems of linear equations. Bulletin International de l' Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Series A, Sciences Mathématiques, pp. 355-357, 1937. ( Note: This article is very common with the incorrect page numbers 335-357 cited. )
  • T. Strohmer, R. Vershynin: A randomized Kaczmarz algorithm with exponential convergence, J. Fourier Anal. Appl. 15 ( 1), 262-278, 2009
  • W. Hackbusch: Iterative solution of large sparse systems of equations Teubner Study Books, 1993, pp. 202-203

Itemization

  • Algorithm
  • Numerical linear algebra
  • Signal processing
459535
de