MATH/APPM 4650
Class notes, April 6

Stability and convergence

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 w_i always bounded.

The easy way to check zero-stability is to do the following:

1. Write the equation in the form w_k+1 = a_m-1 w_k + a_m-2 w_k-1 + . . . + a₀ w_k+1-m.
2. Try a solution of the form w_i = λⁱ. Then λ has to satisfy the characteristic polynomial λ^m = a_m-1 λ^m-1 + a_m-2 λ^m-2 + . . . + a₀.
3. If any roots are strictly larger than 1 in absolute value (including complex roots), then there will be an exponentially growing solution.
   1. If λ is real and |λ|>1, then one solution is w_k = λ^k, and of course this grows exponentially (either always positive or alternating positive and negative).
   2. If λ is complex, i.e., λ = a+bi, then a-bi is also a solution of the characteristic polynomial. Then two solutions are w_i=(a²+b²)^k/2 cos(k arctan(b/a)
      and
      w_i=(a²+b²)^k/2 sin(k arctan(b/a) If a²+b² > 1, i.e., if |λ| > 1, then both these solutions tend to grow with k.
4. If any roots have absolute value equal to 1 but are repeated, there will be a polynomially growing solution.
   1. The solution of w_i+1=2rw_i-r²w_i-1, the characteristic polynomial is (λ-r)²=0, and the general solution is w_i = Arⁱ + Birⁱ for some constants A and B.
   2. For higher repeated roots, we get higher powers of i, but it works the same way.
   3. If the absolute value of r is less than one, these still decay. If it's equal to one, then the powers of i make the solutions grow (slowly).
5. If neither of these things happen, i.e., if all roots are less than or equal to one in absolute value, and the ones with absolute value equal to one are not repeated, we say the method satisfies the root condition. Then all solutions are bounded, and the method is zero-stable.

---

Definition: A difference scheme is called convergent if, for any time interval [a, b], with h=(b-a)/n, the sequence of approximations converges to the true solution:

Graphically this looks like the following:
  


The Lax equivalence theorem: A difference scheme for an ODE is convergent if and only if it is both consistent and zero-stable.

This is the fundamental theorem of difference scheme approximations.

In fact if one works hard, one can prove that solutions of the ODE exist just from understanding solutions of a consistent and stable difference scheme.

The proof requires either a lot of work or some more sophisticated techniques than we've been using.
But here's the basic idea of the proof:

1. Write w_k+1 - y(t_k+1) in terms of the errors w_k - y(t_k), . . ., w_k-m+1 - y(t_k-m+1).
2. Use the fact that the function is Lipschitz and the local truncation error looks like Mh^p to write the error formula as
3. For h small, the characteristic roots of this will be close to the roots of the usual characteristic roots. We write the solution as a combination of the homogeneous solution (in terms of the characteristic roots) and the particular solution (which is a multiple of Mh^p).
4. We want the homogeneous terms to shrink, leaving only the particular solution term (which goes to zero as n goes to infinity).

---

This sort of analysis becomes much more important when studying partial differential equations like u_t = u_xx. To do a difference scheme, we approximate    for small step sizes k and h, and the difference scheme is We can think of this as a matrix equation, and then we have to worry about the eigenvalues of this matrix for zero-stability.