Kaczmarz Row Projection Trace

The Kaczmarz method is an iterative algorithm for solving systems of linear equations. It operates by successively projecting the current guess for the solution onto the hyperplanes defined by each equation in the system. Starting from an initial guess, typically the origin, the method updates the position by calculating the orthogonal projection onto the next row's line.

Worked Example

Consider a consistent system defined by A=[[1,0],[1,1]] and b=[1,2]. We start at the initial guess x_0=(0,0). Here is the step-by-step projection:

Step 1 (row 0): a_0=[1,0], b_0=1.
x_1 = x_0 + (1 - (1*0 + 0*0)) / (1^2 + 0^2) * [1,0] = [1,0]
Step 2 (row 1): a_1=[1,1], b_1=2.
x_2 = x_1 + (2 - (1*1 + 1*0)) / (1^2 + 1^2) * [1,1] = [1,0] + (2-1)/2 * [1,1] = [1.5, 0.5]

The path moves from (0,0) to (1,0) and then to (1.5, 0.5). Further iterations will continually project closer to the true intersection at (1,1).

Experiment

Open the Kaczmarz Row Projection Trace module to interact with this concept:

Select the Consistent option from the System control.
Set Steps to 4 to watch the algorithm converge geometrically to the Unique intersection.
Switch the Order control to Reverse and set Steps to 2 to see a different path to the exact same Unique intersection at (1, 1).
Change the System to Inconsistent and set Steps to 2 to observe the points endlessly cycle between parallel lines with a final status of Inconsistent parallel rows.

Limitations

The Kaczmarz method is fundamentally a row-action projection. For consistent systems, it converges to a solution. However, for inconsistent systems, cyclic projection does not converge to a single least-squares point; instead, it settles into a limit cycle, bouncing endlessly between the non-intersecting row hyperplanes. Randomized selection can avoid cyclic traps in some contexts, but does not fix the fundamental offset.

References

For a rigorous analysis of randomized variations and their expected convergence rates on overdetermined systems, see the seminal paper Randomized Kaczmarz method.

Kaczmarz Row Projection Trace