MATH/APPM 4650
Class notes, April 3
Stability
We saw before that Euler's method converges to the actual solution of the differential equation.
We worked out the full solution of the difference equation for the error.
So as h goes to zero, wN converges to y(T).
Since then we've only worked with local truncation error. That is, we've looked at the new
error produced at each step, rather than the cumulative error (which is what we're really concerned about).
However, every method we've worked with has looked the same:
wi+1 = wi + h[ . . . ]
So knowing how to prove the cumulative error for Euler, together with knowing the local truncation error,
means we can get a global error estimate for any of these methods, in the same way.
This proves that the Runge-Kutta methods, the Adams-Bashforth/Moulton methods, and the Taylor methods all converge
to the actual solution of the differential equation.
Things get more complicated once we start allowing other types of methods.
Example:
Simpson's method for differential equations is
It is an implicit method which has local truncation error O(h4).
Compare to the very similar two-step Adams-Moulton method, which is
This is an implicit method with local truncation error O(h3).
Aside from a slight difference in the coefficients, the major difference is that Adams-Moulton
bases the new answer on a correction to wi, and Adams-Bashforth bases
it on a correction to wi-1
Example:
This is a two-step explicit method. The local truncation error is O(h3). Better
than the two-step Adams-Bashforth method, which has LTE O(h2).
But it's a terrible method! Why?
Let's try it on something simple: y' = -y, y(0)=1, h=0.2.
Then
wi+1 = -3.2 wi + 5.4 wi-1.
We get
| time |
actual |
Euler |
this one |
0.0 |
1.0000 |
1.0000 |
1.0000 |
| 0.2 |
0.8187 |
0.8000 |
0.8187 |
| 0.4 |
0.6703 |
0.6400 |
0.6701 |
| 0.6 |
0.5488 |
0.5120 |
0.5497 |
| 0.8 |
0.4493 |
0.4096 |
0.4438 |
| 1.0 |
0.3678 |
0.3277 |
0.3986 |
| 1.2 |
0.3012 |
0.2621 |
0.1283 |
| 1.4 |
0.2466 |
0.2097 |
1.2177 |
| 1.6 |
0.2019 |
0.1678 |
-5.2549 |
| 1.8 |
0.1653 |
0.1342 |
30.8248 |
| 2.0 |
0.1353 |
0.1074 |
-172.1316 |
Ouch! Notice I started with the exact value for y(0.2) = e-0.2, since this is a multistep method that needs two values to get started.
It's initially good, then goes horribly, horribly wrong for no apparent reason.
Why?
You might guess it's because h is too large and that the scheme would do better if we shrank it. (The fact that it's doing well early on suggests this.)
But that's not it.
As a clue, notice what happens if we try to solve the simplest differential equation, y' = 0.
Then the difference scheme is
wi+1 = -4wi + 5wi-1.
If w0 = 1 and w1 = 1+δ, then
w2 = 1-4δ, w3 = 1+21δ, w4 = 1-104δ, etc.
Clearly a small roundoff error in the first term (which is inevitable) will lead to a growing error.
In fact if we assume an exponentially growing solution wi = λi, then we get an equation for λ:
λi+1 = -4 λi + 5λi-1,
λ2 = -4λ + 5.
Thus λ=1 or λ=-5.
The general solution is wi = A + B (-5)i. If there is no roundoff, then the B term will be zero and the solution will be fine. If there is any roundoff, it will blow up exponentially.
Lesson: We can detect the influence of roundoff by looking at the difference scheme for the equation y'=0.
Definitions:
-
A difference method for a differential equation is consistent if the local truncation error
converges to zero for every i as h approaches zero.
In other words, the LTE is O(h) or better.
- A difference method for a differential equation is zero-stable if the solution for y' = 0 has wi always bounded.
The easy way to check zero-stability is to do the following:
- Write the equation in the form
wi+1 = am-1 wi + am-2 wi-1 + . . . + a0 wi+1-m.
- Try a solution of the form wi = λi. Then λ has to satisfy the characteristic polynomial
λm = am-1 λm-1 + am-2 λm-2 + . . . + a0.
- If any roots are strictly larger than 1 in absolute value (including complex roots), then there will be an exponentially growing solution. If any roots have absolute value equal to 1 but are repeated, there will be a polynomially growing solution.
- If neither of these things happen, we say the method satisfies the root condition. Then all solutions are bounded, and the method is zero-stable.