Kaczmarz Method
This application consists of two iterative solvers for the system of linear equations $Ax=b$, where \[ A = \left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{array}\right],\qquad x = \left[\begin{array}{c} x_1 \\ x_2 \\ \vdots \\ x_n \end{array}\right],\qquad b = \left[\begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array}\right] \] The first solves the problem using Kaczmarz method. For $k=0,1,2,\ldots$ compute: \[ x^{k+1} = x^k + \frac{b_i-\langle A_i,x^k\rangle}{\left\Vert A_i\right\Vert^2}A_i \] where $i= k\bmod{n}$ and $A_i$ is the $i$th row of $A$. The calculation stops when $k=1000$ or $\|b-Ax_k\| < 10^{-8}$ which in the latter case $x_k$ is the solution of the problem.
The second solver uses PLSS-Kaczmarz method to solve the problem. This method should find the solution within $n$ iterations, see [1] for the detail of the method.
References
- Brust, Johannes J. and Saunders, Michael A. (2023), PLSS: A Projected Linear Systems Solver, SIAM Journal on Scientific Computing, vol. 45, pp. A1012–A1037.
- Kaczmarz, Stefan (1937), Angenäherte Auflösung von Systemen linearer Gleichungen, Bulletin International de l'Académie Polonaise des Sciences et des Lettres. Classe des Sciences Mathématiques et Naturelles. Série A, Sciences Mathématiques, vol. 35, pp. 355–357.
- Tewarson, R. P. (1969), Projection Methods for Solving Sparse Linear Systems, The Computer Journal, vol. 12, pp. 77–80.
Input Data
See Input Data for how to enter data to a matrix and a vector of real numbers. The solving method is either 1 or 2 for Kaczmarz method and PLSS-Kaczmarz method, respectively, the default is 2.