Tight Convergence Bounds for the Classical Kaczmarz Method

Runbo Yu, Jelena Diakonikolas

The classical method of Kaczmarz, introduced in 1937, is a textbook iterative method for solving linear systems $Ax=b.$ Despite its widespread use, particularly in the context o…