3
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Typo? Isn't it $\rho^{n^2}$, rather than $\rho^{2^n}$? $\endgroup$ Jul 11, 2022 at 17:48
  • 1
    $\begingroup$ @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$. $\endgroup$ Jul 11, 2022 at 18:39
  • 1
    $\begingroup$ @FedericoPoloni, ah, well, hm, that seems plausible! :) $\endgroup$ Jul 11, 2022 at 18:56
  • $\begingroup$ @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). $\endgroup$
    – user21820
    Aug 10, 2022 at 9:58

1 Answer 1

4
$\begingroup$

“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$.

I guess an approach is to focus on the degree of what, which is how I keep the distinction clear for myself.

Since the same word is used for two different things, it's bound to cause confusion. I suggest this be made clear from the start and warn them not to get the two confused. So if iterative methods precede interpolation/integration/etc. — or vice versa — then begin by explaining that the students will have to keep two distinct definitions straight. One they will learn now, and one later. I would probably even say that one will be based on the degree of a polynomial and one on a power that appears in an inequality. I'd repeat this when we get to the second definition. The idea is from the start to help them to construct an accurate internal "concept map," if you will. If the student learns just the first definition thoroughly, then it will get in the way of learning the second.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.