Back to the on-screen lesson ·
The definition behind $|e_{n+1}| \le C|e_n|^{p}$: how to measure an order from a run, why order and rate are different, and why every statement it makes is local.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to define order and asymptotic constant, read an order off a table of errors or off the slope of a log-log plot, name the order of each familiar root finder, and say what the definition promises and what it does not.
You have run bisection, fixed-point iteration, Newton's method and the secant method, and you have seen that some of them add a digit a step and others double the digits. This lesson gives that observation a definition, and the definition then does work the observation could not.
The error $e_n$ is the distance from $x_n$ to the answer. A sequence converges with order $p$ and asymptotic constant $C$ when $|e_{n+1}| \le C|e_n|^{p}$ for large $n$; $p = 1$ is linear and needs $C < 1$, $p = 2$ is quadratic. Convergence is superlinear when $|e_{n+1}|/|e_n| \to 0$, which includes every order above one and some sequences of no particular order. Asymptotic means eventually, and it is the word the whole definition rests on.
A sequence converges with order $p$ when $|e_{n+1}| \le C|e_n|^{p}$ holds for all large $n$. Taking logarithms makes the content plain: $\log|e_{n+1}| = p\log|e_n| + \log C$, so the exponent of the error is multiplied by $p$ each step. Linear convergence multiplies it by one and adds $\log C$ — a fixed number of new digits per step, for ever. Quadratic convergence doubles the digits, so the last step of a run is worth more than everything before it. Two consequences are worth stating out loud. First, order and rate are different things: bisection and Newton's method at a double root are both linear with rate $\tfrac12$, and one of them costs a derivative. Second, the definition is local and asymptotic. It says what happens once the iteration is close; it does not say it will get close, it does not say how many steps that takes, and with $|e_n| > 1$ a high order makes things worse rather than better. An order of convergence says how fast the error shrinks once the iteration is near the answer. It says nothing about whether it gets there, nothing about how far away it starts, and nothing about the error after any particular step. Every theorem here is local until its hypothesis is checked. In practice the order is measured: plot $\log|e_{n+1}|$ against $\log|e_n|$ and fit a line, whose slope is $p$ and whose intercept is $\log C$.
Another way: steps
Another way: picture
Draw the correct digits against the step number. A linear method is a straight line, climbing by the same amount for ever. A quadratic method is a curve that hugs the axis for a long while and then goes almost vertical — flat, flat, flat, and then finished in three steps. Two such curves with different constants are the same shape shifted sideways, which is exactly what the constant does: it decides when the climb starts, never how steep it becomes.
A high order is read as a promise of speed from any starting point. It is a promise about the neighbourhood of the answer and nothing else. Newton's method of order two can cycle for ever, run off to infinity, or converge to a root nobody wanted, and none of that contradicts the theorem — every one of those runs simply never entered the region the theorem talks about. The second half of the mistake is quoting an order from two errors: the definition is about a limit, so a ratio that has not settled is a measurement of nothing.
Errors $10^{-1}$, $10^{-2}$, $10^{-4}$, $10^{-8}$: exponents $1, 2, 4, 8$.
Each doubles.
The ratio of consecutive exponents is $2$ and stays $2$: order two.
Settled, so it can be quoted.
Errors $0.5, 0.25, 0.125$: exponents rise by a fixed amount, so the ratio tends to $1$ — linear, rate $\tfrac12$.
Order one, and the constant matters.
Newton: order $2$, two evaluations a step — a function and a derivative.
Digits double per step.
Secant: order $\approx 1.618$, one evaluation a step, reusing the last.
Fewer digits per step.
Per evaluation: $1.618$ against $\sqrt2 \approx 1.414$ — the secant method wins the comparison that pays the bill.
Order is not efficiency.
The exponents are $2$, $6$ and $18$.
Each is three times the one before it.
So the order is $3$ — cubic, which is what Halley's method achieves at the cost of a second derivative per step.
Consecutive errors of an iteration are about $10^{-2}$ and then $10^{-6}$. What is the order of convergence?
Answer:
An iteration of order $2$ has error $10^{-1}$ now, with the constant close enough to $1$ to ignore. Give the exponent of the error after each of the next three steps, as a positive number.
| Step | Exponent of the error | |
|---|---|---|
| After one step | 1 | |
| After two steps | 2 | |
| After three steps | 3 |
Match each method to the order and rate it converges at, close to the answer.
| Linear, rate one half, whatever the function | Order two, with a constant built from $f''$ and $f'$ | Linear, rate one half, despite costing a derivative | Order about $1.618$: superlinear, and not quadratic | |
|---|---|---|---|---|
| Bisection | ||||
| Newton's method at a simple root | ||||
| Newton's method at a double root | ||||
| The secant method at a simple root |
Put these five behaviours in order, slowest first, by how the error eventually shrinks.
Number the steps in order (write the number in the box):
An iteration has order $4$. It is rewritten so that each new step performs two of the old ones. What is the order of the rewritten iteration?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
An iteration satisfies $e_{n+1} = 10^{-1}e_n^{2}$. The base-ten logarithm of $e_{n+1}$ is plotted against the base-ten logarithm of $e_n$. Give the slope and the intercept of the line that results.
the logarithm of each error against the logarithm of the one before it
Slope of the line:
Intercept of the line:
You can define and measure an order of convergence and separate it from the rate and from the cost of a step. Say in your own words why a quadratic method can be slower than bisection for the first twenty steps.
8. Your turn: the order of a sequence with errors $10^{-2}$, $10^{-6}$, $10^{-18}$, step 3