Wednesday, June 22, 2011

Another reason for linear convergence of Newton's method

It's well-known that Newton's method has quadratic convergence if the function is well-behaved and the initial guess is close to the solution. However, sometimes we only get linear (slow) convergence.

One possible reason is that the derivative f' is singular at the solution x*. Here singular means f'=0 in 1D case or f' is a singular matrix in higher dimensions. In the 1D case, we can still get quadratic convergence if we use the iteration $$\triangle x = -m f(x_n)/f'(x_n)$$ with m equal to the multiplicity of the root x*.

Another possible reason is that there is a bug in the computation of the right-hand-side $$f(x_n)$$. If there is a deviance of $$O(h)$$, Newton's method will also converge linearly.