## Rate of Convergence

**Rate of Convergence:**

Here, the speed at which a convergent sequence approaches its limit is called the rate of convergence. This concept is of practical importance if we deal with a sequence of successive approximations for an iterative method, as then typically fewer iterations are needed to yield a useful approximation if the rate of convergence is higher.

**Convergence of A Sequence:**

A sequence < x_{n} > is said to be converges to α if for every ε > 0 there is an integer m > 0 such that if n > m then |x_{n} − α| < ε . The number α is called the limit of the sequence and we sometimes write x_{n} → c.

**Convergence Speed for Iterative Methods:**

Let < x_{n} > be sequence of successive approximations of a root x = α of the equation f (x) = 0. Then the sequence < x_{n} > is said to be converges to α with order q if

where μ > 0. Constant m is called the rate of convergence.

Particularly, if |x_{n 1} − α| = μ|x_{n} − α|, n ≥ 0, 0 < μ < 1, then convergence is called linear or of first order. Convergence with order 2 is called quadratic convergence, and convergence with order 3 is called cubic convergence.

**Examples**: Find one of the real root of f (x) ≡ x^{6} − x − 1 = 0 accurate to within ε = 0.001.

**Solution**: We consider the interval [1,2], choose a = 1, b = 2; then f (a) = −1, f (b) = 61. This shows that condition 16.3 is satified for this interval. Now we may apply algorithm B1 to B3.

**Iterations:1
**

Move to next step, decide new interval

f (a). f (c) = (−1).(8.8906) = − 8.8906 < 0

This shows new interval [a, c] is valid interval. i.e. replace b = c. Now a = 1 and b = 1.5

**Iterations:2**

b − c = 0.25 > ε

Move to next step, decide new interval

f (a). f (c) = (−1).(1.5647) = −1.5647 < 0

This shows new interval [a, c] again, is a valid interval. i.e. replace b = c. Now a = 1 and b = 1.25 Note after 10th iteration b−c < ε . Stop iteration process at this step. Hence final approximated root is 1.1338.