Numerical Analysis/stability of Multistep methods

For multistep methods, the problems involved with consistence, convergence and stability are complicated because of the number of approximations involved at each step. In the one step method, the approximation depends only on the previous approximation , whereas the multistep methods use at least two of the previous approximations, and the usual method that are employed involve more.

Stable Multistep Method

edit

Characteristic polynominals

edit

For the multistep method:

 ,
 ,

the polynominal

  ,

is called the characteristic polynominal of the above mutistep method.

The stability of a multistep method with respect to round-off error is dictated by the magnitudes of the zeros of the characteristic polynominal.

Root condition

edit

Let   denote the (not necessarily distinct) roots of the characteristic equation

  ,

associated with the multistep difference method

 ,
 

If the absolute value  , for each i=1,2,...,m, and all roots with abosolute value 1 are the simple roots, then the difference method is said to satisfy the root condition.

Stability Definitions

edit
  1. Methods that satisfy the root condition and have   as the only root of the characteristic equation of the magnitude one are called strongly stable.
  2. Methods that satisfy the root condition and have more than one distinct root with magnitude one are called weakly stable.
  3. Methods that do not satisfy the root condition are called unstable.

Stable Multistep methods

edit

A multistep method of the form

 ,
 ,

is stable if and only if it satisfies the root condition. Moreover, if the difference method is consistent with the differential equation, then the method is stable if and only if it is convergent.

Examples

edit

Example1

edit

The fourth-order Adams-Bashfoth method is

 

where   The characteristic equation is

 

so we find the characteristic roots to be

 

Thus the 4th-order Adams Method satisfies the root condition and is strongly stable.

Example 2

edit

Milne's Method is

 

where   The characteristic equation is

 

so the characteristic roots are  

Thus the 4th-order Milne's Method satisfies the root condition, but it is only weakly stable.

Absolute Stability & Region of Absolute stability

edit

Definition

edit

Apply a numerical method to initial-value problem

 
 

Suppose that a round off error   is introduced in the initial condition for this method. At the nth step the round off error is  . Provided the step size h is chosen to satisfy  , the numerical method is said to be absolutely stable for the step size h. And    is said to be region of absolute stability for numerical method.

Region of absolute stability for one-step method

edit

In general, when a one-step method is applied to the test equation, a function   exists with the property that the difference method gives

  .

The initial round-off error   and the round-off error at the ith step   will satisfy    which is  .

The inequality   will hold if  . Thus, region R of absolute stability for a one-step method is

   

Region of absolute stability for multistep methods

edit

Consider the k-step method

 
 

Applying it to

 

we get

 
 

The characteristic polynominal of the method is

    

The region R of absolute stability for a multistep method is

  .

Example

edit

Determine the region of absolute stability for two step method  .

Applying this method to:  , gives

 
 

The characteristic polynominal of above method is

 

All the zeros of the characteristic polynominal are

 

Thus the region of absolute stability for this method is   .

Exercises

edit

Exercise 1

edit

Find the region of the absolute stability of Euler's method:

 

Exercise 2

edit

Find the region R of the absolute stability of Trapezoidal method

 

Exercise 3

edit

Make a table of the interval of absolute stability for four one-step methods: Euler's method, Backward- Euler, M-Euler and Trapezoidal method.

Exercise 4

edit

Find the Region of absolute stability of Adams-Bashforth explict Four-step Method

 

Quiz

edit

The following is a quiz covering information presented on the associated multistep method.

1 True or False: The multistep methods are always stable methods.

TRUE.
FALSE.

2 True or False: If the multistep method is strongly stable then it is weakly stable.

TRUE.
FALSE.

3 Check all that apply: Which of the following statements are right?...

The root condition can always be satisfied for the multistep method.
Methods that satisfy the root condition and have more than one distinct root with magnitude one are called strongly stable.
Methods that do not satisfy the root condition are unstable.
The Euler's method and the Backward Euler method have the same region of absolute stability.

4 Given the following ODE method

 

 ,

then which h make sure the absolute stability of the method.

 
 
 
 


References

edit