Saturday, July 14, 2012

Iteration termination (limit) and convergence in Newton-Raphson iteration

In any iterative solver, there are many stopping (termination) methods to stop iteration loop because the solver is not going to iterate forever.

Iteration loop will stop in the following cases:

§  Solution is obtained: It is a waste of time and resources to iterate further after the solution is known.

§  Maximum number of iterations reached with no solution obtained: you tell the solver previously to iterate for 1000 times – for example- that if the solution is not obtained within those iterations then stop iteration loop and output a message  “Convergence is not obtained” or “ No solution found”

§  Maximum iteration time elapsed with no solution obtained: in this case you tell the solver to stop iteration after a certain time is elapsed (say 1 minute) if the solution is not obtained. In this case also, messages “Convergence is not obtained” or “No solution found” can be displayed.

So …, how to check if the current value of the variable x is the solution or not? There are two methods I’ve implemented (maybe there are another methods, I don’t know):

§  Absolute residual error: you tell the solver if the error of the residual is less than or equal certain value (say 0.001, which is the reasonable error for you), then the current value of the variable x is the solution.

§  Variable x convergence criteria: it may be used when you set an absolute error value that can not be obtained in iteration due to round off error. So, you tell the solver if the value of x is obtained for many times successively (say 100 times), then consider this value as a solution.