If the sequence defined by the numerical method converges, we can ask what the rate of convergence is. With this aim, we define the order of convergence of a sequence :
Definition (Order of convergence). A sequence converges to with order if
is the order of convergence of the numerical method that has generated the sequence . The constant is called rate of convergence. If and is between 0 and 1, the convergence is said to be linear convergence.Under the linear convergence condition,if , the sequence is said to converge superlinearly and if , then the sequence is said to converge sublinearly.
represents the error at step . In general, with a numerical method, we do a finite number of iterations and for this reason we seek only an approximation of the true root . In particular, we can define a tolerance such that if ,we can stop the iteration and conclude that is the approximation of the true root.
Suppose that the sequence converges to with order 2, where the constant , and suppose that the initial error . Consider a tolerance , then we can find the approximation of the true root by using the definition of convergence.Hence,
which is greater than the tolerance, so we should keep going until the error is less than the tolerance. We can get
which is also greater than the tolerance, thus we should do the iteration to calculate
which is still larger than the tolerance. Similarly,
which is less than the tolerance. Therefore, we can stop here and can conclude that is the approximation of the true root.