Definition
The Kaczmarz method is an iterative algorithm for solving systems of linear equations $Ax = b$. It proceeds by sequentially projecting an estimate of the solution onto the hyperplanes defined by each equation, thereby reducing the residual error with each iteration.
Overview
Developed in 1937 by the Polish mathematician Stefan Kaczmarz, the method is particularly suited for large, sparse, or inconsistent systems where direct solution techniques are computationally expensive. In each iteration, the current estimate $x^{(k)}$ is updated using a single row $a_i$ of the matrix $A$ and the corresponding right‑hand side entry $b_i$:
$$ x^{(k+1)} = x^{(k)} + \frac{b_i - \langle a_i, x^{(k)} \rangle}{|a_i|^2}, a_i^{\mathsf{T}}, $$
where $i$ cycles through the rows of $A$ (or is chosen randomly in the randomized variant). The process repeats until a stopping criterion—typically based on the norm of the residual or a maximum number of iterations—is satisfied.
Etymology / Origin
The algorithm is named after Stefan Kaczmarz (1895–1939), a mathematician at the Jagiellonian University in Kraków. His original paper, published in Bulletin of the Polish Academy of Sciences (1937), introduced the method as a “method of successive projections” for solving linear equations.
Characteristics
- Iterative Projection: Each step orthogonally projects the current approximation onto the solution hyperplane of a single equation.
- Row‑by‑Row Processing: The method uses one equation at a time, which allows for low memory consumption and suitability for streaming data.
- Convergence: For consistent, full‑rank systems, the method converges to the unique solution. For inconsistent or rank‑deficient systems, it converges to the least‑squares solution under certain conditions.
- Randomized Variant: Selecting rows with probability proportional to $|a_i|^2$ yields the randomized Kaczmarz algorithm, which has provably exponential convergence in expectation and is widely used in modern applications.
- Computational Complexity: Each iteration requires $O(n)$ operations for an $n$-dimensional problem, making it efficient for very large problems where $A$ is sparse.
- Applications: The method is employed in computed tomography (as the Algebraic Reconstruction Technique, ART), signal processing, machine learning (e.g., solving over‑determined linear regression problems), and network analysis.
Related Topics
- Iterative methods for linear systems (Gauss–Seidel, Jacobi, Conjugate Gradient)
- Algebraic Reconstruction Technique (ART) in computed tomography
- Randomized algorithms in numerical linear algebra
- Least‑squares problems and Moore–Penrose pseudoinverse
- Sparse linear algebra and large‑scale scientific computing
- Convergence analysis of projection methods
This entry follows the structure: Definition → Overview → Etymology/Origin → Characteristics → Related Topics, and presents verified information about the Kaczmarz method.