Back to the on-screen lesson ·
Why a multistep method has roots that have nothing to do with the equation, what keeps them quiet, the equivalence theorem that follows, and the ceiling it puts on accuracy.
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 write a method's first characteristic polynomial and find its roots, apply the root condition, state and prove the Dahlquist equivalence theorem, distinguish zero-stability from absolute stability, and quote the barrier on the order of a zero-stable method.
You know that a one-step method converges when it is consistent and its increment function is Lipschitz, and you know what absolute stability is. A multistep method needs a different condition in place of the Lipschitz one, because it carries several previous values forward and they can interfere.
A linear multistep method is $\sum_{j} \alpha_j y_{n+j} = h\sum_j \beta_j f_{n+j}$. Its first characteristic polynomial is $\rho(\zeta) = \sum_j \alpha_j\zeta^{j}$. The root condition asks that every root of $\rho$ lie inside or on the unit circle, with any on the circle simple; a method satisfying it is zero-stable. A root other than the principal root $\zeta = 1$ is parasitic.
A $k$-step method is a difference equation of order $k$ standing in for a differential equation of order one. That mismatch is the whole subject of this lesson: the difference equation has $k$ solutions and only one of them is approximating anything. Setting $h = 0$ leaves $\sum_j \alpha_j y_{n+j} = 0$, whose solutions are built from the roots of the first characteristic polynomial $\rho$. Consistency forces $\rho(1) = 0$, and that root is the principal one, the one doing the integrating. The others are parasitic, and the root condition is the demand that they stay quiet: every root inside or on the unit circle, with any on it simple. A root outside means a starting error multiplied by its size at every step, so the computed solution is destroyed in a few dozen steps however small $h$ is — shrinking the step makes it worse, since the growth is per step. Dahlquist's equivalence theorem then says:
> consistent $+$ zero-stable $\iff$ convergent,
with the order of convergence equal to the order of consistency. That factorises an impossible check into two easy ones: a Taylor expansion, and the roots of a polynomial. And it comes with a price, the first barrier: a zero-stable $k$-step method has order at most $k + 1$, or $k + 2$ for even $k$ — far short of the $2k$ that counting coefficients suggests, because every attempt to reach higher pushes a root outside the circle.
Another way: steps
Another way: picture
Draw the unit circle with the roots of $\rho$ marked. One is always at $+1$, on the boundary, and it is the one integrating the equation. The others should be huddled near the origin; a root at $-1$ is allowed but sits on the edge and never decays; a root outside is a number the starting error is multiplied by, over and over, until nothing else in the answer is visible.
Zero-stability is confused with absolute stability, and the two are different questions about different limits. Absolute stability asks whether a particular step size on a particular decay rate keeps the computed solution from growing; zero-stability asks whether the method's own difference equation is well behaved when $h$ is zero. A method can be absolutely stable on a wide region and fail the root condition, in which case it converges to nothing. The practical signature is the one that catches people out: a method failing the root condition gets worse as the step is reduced, which is the opposite of every other error in this course.
$y_{n+1} = y_{n-1} + 2hf_n$ gives $\rho(\zeta) = \zeta^{2} - 1$.
Roots $\pm 1$.
Both on the circle, both simple: zero-stable, so it converges.
The condition is satisfied.
But the parasitic root never decays, and on $y' = -y$ the computed solution eventually oscillates while the true one has vanished.
Marginal stability, in practice.
$y_{n+1} = -4y_n + 5y_{n-1} + h(4f_n + 2f_{n-1})$: order three from two steps, the barrier's maximum.
Consistent, and highly accurate per step.
$\rho(\zeta) = \zeta^{2} + 4\zeta - 5 = (\zeta - 1)(\zeta + 5)$: a root at $-5$.
The root condition fails.
Errors are multiplied by five each step; twenty steps multiply them by $10^{14}$.
Accurate and useless.
$\rho(1) = 1 - \tfrac32 + \tfrac12 = 0$, so it is consistent as far as $\rho$ is concerned.
Dividing out: $(\zeta - 1)(\zeta - \tfrac12)$.
The other root is $\tfrac12$, strictly inside the circle: zero-stable, and the parasitic solution decays by half each step rather than lingering.
A two-step method has first characteristic polynomial $\rho(\zeta) = \zeta^{2} + 3\zeta - 4$. Apart from $\zeta = 1$, what is its root?
Answer:
Each polynomial below has $\zeta = 1$ as a root. Give the other root of $\zeta^{2} - \zeta$, of $\zeta^{2} - \left(1 + \tfrac{1}{3}\right)\zeta + \tfrac{1}{3}$, and of $\zeta^{2} + 2\zeta - 3$. Give fractions where they are not whole.
| Constant term | The other root | |
|---|---|---|
| $\zeta^{2} - \zeta$ | 0 | |
| $\zeta^{2} - (1 + 1/3)\zeta + 1/3$ | 1/3 | |
| $\zeta^{2} + 2\zeta - 3$ | -3 |
Build the argument that a consistent, zero-stable linear multistep method of order $p$ converges with global error $O(h^{p})$.
This task has no paper form; do it on a device.
Match each multistep method to what its first characteristic polynomial does.
| Roots $1$ and $0$: zero-stable automatically | Zero-stable up to six steps and not beyond | Roots $1$ and $-1$: stable, but only marginally | A root of size five: errors grow by that factor each step | |
|---|---|---|---|---|
| Any Adams method | ||||
| The backward differentiation formulas | ||||
| The explicit midpoint rule | ||||
| Dahlquist's third-order two-step method |
Dahlquist's first barrier says a zero-stable $k$-step method has order at most $k + 1$, or $k + 2$ when $k$ is even. What is the highest order available to a zero-stable method with $k = 4$ steps?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Select every statement that is true of the root condition on the first characteristic polynomial.
This task has no paper form; do it on a device.
You can test a multistep method for zero-stability and state the equivalence theorem. Say in your own words why a method that fails the root condition gets worse as the step is reduced.
8. Your turn: is the two-step method with $\rho(\zeta) = \zeta^{2} - \tfrac32\zeta + \tfrac12$ zero-stable?, step 3