On Convergence Rates of Root-Seeking Methods

[ttw]

Very often, the converge rate is asymptotic. It holds either for very large N or for a guess close enough. Newton's method often converges linearly until the result is much closer to one root than the other; then it becomes quadratic.

A few "better" estimates are available. For example, one can use a Gauss-Seidel relaxation for linear equations or (with even number of elements) a Red-Black relaxation. The Red-Black has the same asymptotic convergence rate as the Gauss-Seidel but a better average rate. Thus is converges more quickly at the beginning.

For those unfamiliar with Red-Black: If the matrix represents a diffusion process, one can treat an even number of points as being colored like a checkerboard. The red sites depend only on themselves and the black sites and vice versa. By alternately solving for the red sites in terms of the black and vice versa, one gets quicker convergence.