Convergence Rate

Definition

The convergence rate (or rate of convergence) quantifies how quickly a sequence, series, or iterative algorithm approaches its final limit. It measures the speed at which the error—the difference between the current approximation and the true value—shrinks toward zero as the number of iterations increases.

$\lim_{n \to \infty} \frac{|x_{n+1} - L|}{|x_n - L|^q} = \mu$ How to read: The limit as n approaches infinity of the absolute error at step n plus 1 divided by the absolute error at step n raised to the power q equals mu. Meaning / when to use: This formula defines the order of convergence $q$ and the asymptotic error constant $\mu$. It is used to evaluate the efficiency of numerical methods; higher $q$ means much faster convergence.

Why It Matters

In computational mathematics and machine learning, determining the correct answer is only half the battle; getting there quickly using limited processing power is the other half. The convergence rate dictates the efficiency of an algorithm. A linear rate might require thousands of iterations to achieve a given precision, whereas a quadratic rate (like in Newton’s Method) might achieve it in five. Poor convergence rates lead to excessive computational cost and time.

Core Concepts

• Linear Convergence ($q=1$): The error shrinks by a constant fraction at each step. (e.g., Bisection method).
• Superlinear Convergence ($q > 1$): The sequence converges faster than any linear sequence, but not necessarily quadratic.
• Quadratic Convergence ($q=2$): The number of correct decimal places roughly doubles with each iteration. Highly desirable in optimization algorithms.
• Trade-offs: Algorithms with faster convergence rates (like Newton-Raphson) often require more complex calculations per step (like computing derivatives) and may require a starting guess very close to the true root.

Connected Concepts

• Convergence
• Divergence
• Error Analysis
• Order Of Growth
• Dynamic Systems