the order of convergence

The order of convergence measures how fast the error of an iterative process falls from one step to the next, as the iterates close in on the answer. If e_n = |x_n - x*| is the error at step n and it behaves like e_{n+1} approximately C times e_n^p as n grows, then p is the order of convergence and C the asymptotic constant. The bigger p is, the more violently the error collapses near the answer.

Three cases are worth naming. Order p = 1 with 0 < C < 1 is linear convergence: the error is multiplied by the same factor each step, so it falls geometrically and you gain a roughly constant number of digits per step — bisection (C = 1/2, one binary digit per step) is the model. Order p = 2 is quadratic convergence: the error squares each step, so the number of correct digits roughly doubles per step — Newton's method near a simple root is the famous example, racing from 3 to 6 to 12 correct digits in three steps. In between, superlinear convergence (faster than linear but not quite quadratic, like the secant method's golden order p approximately 1.618) is the common compromise.

Order of convergence matters because it tells you how many iterations you must pay for a given accuracy, and the difference is enormous: a quadratic method reaches machine precision in a handful of steps where a linear one might need dozens. But the order is a local, asymptotic promise — it describes behaviour only once you are already close to the answer. Newton is quadratic only near a simple root with a good initial guess; from a bad start it can diverge or cycle, and at a multiple root its order drops to linear. High order is no use if the iteration never gets close enough to enter its fast regime.