# How to differentiate the two notions of convergence order?

In the context of iterative methods for equations and linear systems, one usually says that "linear convergence / order 1" is when the error $$err$$ goes to zero with the number of iterations $$n$$ as $$err \sim \rho^n$$ for a certain $$\rho<1$$ (e.g., fixed-point method, Jacobi method for linear systems), and "quadratic convergence / order 2" is $$err \sim \rho^{2^n}$$ (e.g., the Newton method for a simple zero).

On the other hand, in the context of numerical quadrature and methods for ODEs, one usually says that "order 1" is $$err \sim \frac{1}{n}$$, when $$n$$ is the number of subdivision points, usually equispaced; (e.g., the explicit/implicit Euler's method), and "order 2" is $$err \sim \frac{1}{n^2}$$ (e.g., trapezoidal rule).

These two incompatible definitions are also discussed, for instance, on Wikipedia.

What is a good way to differentiate them in teaching to prevent confusion? If possible I would like to avoid introducing non-standard terminology. This is in the context of an undergraduate course in numerical methods.

• Typo? Isn't it $\rho^{n^2}$, rather than $\rho^{2^n}$? Commented Jul 11, 2022 at 17:48
• @paulgarrett No, I believe $\rho^{2^n}$ is correct, since at each step the error is squared. For instance the sequence $1/2, 1/4, 1/16, 1/256$ fits the definition with $\rho=1/2$. Commented Jul 11, 2022 at 18:39
• @FedericoPoloni, ah, well, hm, that seems plausible! :) Commented Jul 11, 2022 at 18:56
• @paulgarrett: For example here is a proof for Newton-Raphson approximation, with the precise conditions for quadratic convergence, which is doubly-exponential (exponential in the number of digits of precision). Commented Aug 10, 2022 at 9:58

“Order” usually means the degree of something. What that something is varies with the subject. Standard integration/differentiation methods are not iterative, so the iterative definition of “order” cannot be applied; the term order in this case is usually connected with the order of the Taylor series approximation or the order of a polynomial interpolant. In iteration, order is the degree relating successive errors: $$E_{n+1}\le C\,(E_n)^p$$ for order $$p$$.
Another source of confusion can be seen in the comments. Order $$2$$ in iterative methods leads to an exponential decrease in error (as a function of the number of steps $$n$$): Taking $$C=1$$ for convenience, $$E_n \le (E_{n-1})^2 \le ((E_{n-2})^2)^2 \le (((E_{n-3})^2)^2)^2 \le \cdots \le (E_0)^{2^n} \,.$$ One often thinks order $$2$$ is polynomial, not exponential. This should probably be emphasized, too, when introducing order in iterative methods.