Order of convergence

Level UniversityDifficulty ★★★★★Concept⌖ Open in the map

What is it?

How fast the error $e_k = |x_k - x^\ast|$ shrinks: linear ( $e_{k+1} \approx c\,e_k$ , a fixed number of digits per step), quadratic ( $e_{k+1} \approx c\,e_k^2$ , digits double each step). Bisection is linear; Newton is quadratic.

Formulas

$\lim_{k\to\infty}\frac{e_{k+1}}{e_k^{\,p}} = C \in (0, \infty)$
convergence of order $p$

Where it shows up in computing

Scientific computing★★★★★fundamentalScientific computing and algorithms
The order of a method decides how many iterations (and how much compute) an accurate answer costs.

Where it shows up in AI

Gradient descent★★★★★frequentAI and machine learning
On strongly convex problems GD converges linearly, at a rate set by the condition number $L/\mu$ .

Where is it used?

Computing topics reachable from here, through the chain of ideas that leads to them:

This page has the essentials. A fuller treatment (intuition, formal definition, worked example) is on the way.

What is it?

Formulas

Where it shows up in computing

Where it shows up in AI

Where is it used?

λ Scientific computing and algorithms

ℒ AI and machine learning

⇄ Optimization and systems