Kaczmarz method

Kaczmarz method

The Kaczmarz method, based on the work of Polish Professor Stefan Kaczmarz, is a method for solving linear systems of equations Ax = b. It is an iterative algorithm that has found many applications ranging from computer tomography to digital signal processing.

The method needs, unlike most other linear iterative solvers, not a positive definite but only an invertible matrix A. Therefore it can be used in almost all applications (although most other iterative solvers are for special cases much faster than the Kaczmarz method).

Recently, a randomized version of the Kaczmarz method for overdetermined linear systems that converges at an exponential rate was introduced by Thomas Strohmer and Roman Vershynin. This new solver's rate does not depend on the number of equations in the system and outperforms all previously known methods on extremely overdetermined systems. Even for moderately overdetermined systems, numerical simulations reveal that the algorithm can converge faster than the conjugate gradient algorithm.

The basic (non randomized) algorithm

Given a full rank real or complex m x n matrix A (n ≤ m) and a real or complex vector b, the following iteration computes a better approximation of the equations solution x:

x_{k+1} = x_{k} + frac{b_{i} - langle a_{i},x_{k} angle}{lVert a_{i} Vert^2} a_{i}^* where i equiv k pmod m + 1

The initial value of x is not important for convergence, although it's better if an appropriate value is chosen.The formulae above gives a simple iteration routine. A complete iteration requires m simple iterations.

The new randomized algorithm

It can be shown (see "A randomized solver for linear systems with exponential convergence" Thomas Strohmer and Roman Vershynin [http://www.math.ucdavis.edu/~vershynin/papers/linear-system-solver.pdf] ) that the above algorithm runs significantly faster if i is chosen at random (with probability proportional to lVert a_{i} Vert ^2 for each simple iteration.

References

*S. Kaczmarz. "Angenäherte Auflösung von Systemen linearer Gleichungen". Bull. Internat. Acad. Polon.Sci. Lettres A, pages 335-357, 1937.
* Thomas Strohmer and Roman Vershynin, "A randomized solver for linear systems with exponential convergence" [http://www.math.ucdavis.edu/~vershynin/papers/linear-system-solver.pdf]
*W. Hackbusch "Iterative Lösung großer schwachbesetzter Gleichungssysteme" Teubner Studienbücher, 1993, pages 202-203

NOT!


Wikimedia Foundation. 2010.

Игры ⚽ Поможем решить контрольную работу

Look at other dictionaries:

  • Stefan Kaczmarz — (born 1895 in Lviv (Lemberg), Galicia, Austria Hungary (now Ukraine) 1940) was a Polish mathematician. His Kaczmarz Method provided the basis for many modern imaging technologies, including the CAT scan.Kaczmarz was an adjunct professor of… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Algebraic Reconstruction Technique — The Algebraic Reconstruction Technique (ART) is an iterative algorithm for the reconstruction of a two dimensional image from one dimensional input data (a sinogram), used in Computed Tomography scanning. In numerical linear algebra the method is …   Wikipedia

  • List of mathematics articles (K) — NOTOC K K approximation of k hitting set K ary tree K core K edge connected graph K equivalence K factor error K finite K function K homology K means algorithm K medoids K minimum spanning tree K Poincaré algebra K Poincaré group K set (geometry) …   Wikipedia

Share the article and excerpts

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