Namespaces
Variants
Actions

Difference between revisions of "Milne method"

From Encyclopedia of Mathematics
Jump to: navigation, search
m (tex encoded by computer)
m (fixing overline)
 
(One intermediate revision by the same user not shown)
Line 21: Line 21:
  
 
$$  
 
$$  
y _ {i} - y _ {i-} 2 = \  
+
y _ {i} - y _ {i- 2}  = \  
2 h f ( x _ {i-} 1 , y _ {i-} 1 ) ,
+
2 h f ( x _ {i- 1} , y _ {i- 1} ) ,
 
$$
 
$$
  
Line 33: Line 33:
  
 
In computations using this formula it is necessary, by some other means, to find an additional initial value  $  y _ {1} \approx y ( x _ {1} ) $.  
 
In computations using this formula it is necessary, by some other means, to find an additional initial value  $  y _ {1} \approx y ( x _ {1} ) $.  
The Milne method has second-order accuracy and is Dahlquist stable, that is, all solutions of the homogeneous difference equation  $  y _ {i} - y _ {i-} 2 = 0 $
+
The Milne method has second-order accuracy and is Dahlquist stable, that is, all solutions of the homogeneous difference equation  $  y _ {i} - y _ {i- 2} = 0 $
 
are bounded uniformly with respect to  $  h $
 
are bounded uniformly with respect to  $  h $
for  $  i = 0 \dots [ ( A - a ) / h ] $,  
+
for  $  i = 0, \dots, [ ( A - a ) / h ] $,  
 
for any fixed interval  $  [ a , A ] $.  
 
for any fixed interval  $  [ a , A ] $.  
 
For Dahlquist stability it is sufficient that the simple roots of the characteristic polynomial of the left-hand side of the difference equation do not exceed one in modulus, and that the multiple roots are strictly less than one in modulus. In the case given, the characteristic polynomial  $  \rho ( \lambda ) = \lambda  ^ {2} - 1 $
 
For Dahlquist stability it is sufficient that the simple roots of the characteristic polynomial of the left-hand side of the difference equation do not exceed one in modulus, and that the multiple roots are strictly less than one in modulus. In the case given, the characteristic polynomial  $  \rho ( \lambda ) = \lambda  ^ {2} - 1 $
Line 48: Line 48:
  
 
$$  
 
$$  
\overline{y}\; _ {i}  =  y _ {i-} 4 +  
+
\overline{y} _ {i}  =  y _ {i- 4} +  
 
\frac{4h}{3}
 
\frac{4h}{3}
  
( 2 f _ {i-} 3 + f _ {i-} 2 + 2 f _ {i-} 1 ) ,\ \  
+
( 2 f _ {i- 3} + f _ {i- 2} + 2 f _ {i- 1} ) ,\ \  
 
i = 4 , 5 \dots
 
i = 4 , 5 \dots
 
$$
 
$$
Line 58: Line 58:
  
 
$$  
 
$$  
\overline{ {\overline{y}\; }}\; _ {i}  = \  
+
\overline{ \overline{y} } _ {i}  = \  
y _ {i-} 2 +  
+
y _ {i- 2} +  
 
\frac{h}{3}
 
\frac{h}{3}
  
( f _ {i} + 4 f _ {i-} 1 + f _ {i-} 2 ) ,\ \  
+
( f _ {i} + 4 f _ {i- 1} + f _ {i- 2} ) ,\ \  
 
i = 4 , 5 \dots
 
i = 4 , 5 \dots
 
$$
 
$$
Line 70: Line 70:
 
$$  
 
$$  
 
f _ {i}  =  f ( x _ {i} , y _ {i} ) ,\ \  
 
f _ {i}  =  f ( x _ {i} , y _ {i} ) ,\ \  
\overline{f}\; _ {i}  =  f ( x _ {i} , \overline{y}\; _ {i} ) .
+
\overline{f} _ {i}  =  f ( x _ {i} , \overline{y} _ {i} ) .
 
$$
 
$$
  
Line 80: Line 80:
 
\frac{1}{29}
 
\frac{1}{29}
  
( \overline{y}\; _ {i} - \overline{ {\overline{y}\; }}\; _ {i} ) .
+
( \overline{y} _ {i} - \overline{ {\overline{y} }} _ {i} ) .
 
$$
 
$$
  

Latest revision as of 17:45, 20 January 2022


A finite-difference method for the solution of the Cauchy problem for systems of first-order ordinary differential equations:

$$ y ^ \prime = f ( x , y ) ,\ \ y ( a ) = b . $$

The method uses the finite-difference formula

$$ y _ {i} - y _ {i- 2} = \ 2 h f ( x _ {i- 1} , y _ {i- 1} ) , $$

where

$$ x _ {i} = a + i h ,\ \ i = 0 , 1 ,\dots . $$

In computations using this formula it is necessary, by some other means, to find an additional initial value $ y _ {1} \approx y ( x _ {1} ) $. The Milne method has second-order accuracy and is Dahlquist stable, that is, all solutions of the homogeneous difference equation $ y _ {i} - y _ {i- 2} = 0 $ are bounded uniformly with respect to $ h $ for $ i = 0, \dots, [ ( A - a ) / h ] $, for any fixed interval $ [ a , A ] $. For Dahlquist stability it is sufficient that the simple roots of the characteristic polynomial of the left-hand side of the difference equation do not exceed one in modulus, and that the multiple roots are strictly less than one in modulus. In the case given, the characteristic polynomial $ \rho ( \lambda ) = \lambda ^ {2} - 1 $ has roots $ \lambda = \pm 1 $ and, consequently, the stability condition holds. However, in solving a system of equations $ y ^ \prime = A y $ with a matrix $ A $ having negative eigen values, a rapid growth in the calculation error occurs.

The predictor-corrector Milne method uses a pair of finite-difference formulas:

a predictor

$$ \overline{y} _ {i} = y _ {i- 4} + \frac{4h}{3} ( 2 f _ {i- 3} + f _ {i- 2} + 2 f _ {i- 1} ) ,\ \ i = 4 , 5 \dots $$

and a corrector

$$ \overline{ \overline{y} } _ {i} = \ y _ {i- 2} + \frac{h}{3} ( f _ {i} + 4 f _ {i- 1} + f _ {i- 2} ) ,\ \ i = 4 , 5 \dots $$

where

$$ f _ {i} = f ( x _ {i} , y _ {i} ) ,\ \ \overline{f} _ {i} = f ( x _ {i} , \overline{y} _ {i} ) . $$

An approximate expression for the error is given by the quantity

$$ \epsilon _ {i} = \ \frac{1}{29} ( \overline{y} _ {i} - \overline{ {\overline{y} }} _ {i} ) . $$

Additional initial values $ y _ {i} \approx y ( x _ {j} ) $, $ j = 1 , 2 , 3 $, are calculated by some other means, for example, by the Runge–Kutta method, which has fourth-order accuracy. The method was proposed in [3].

References

[1] N.S. Bakhvalov, "Numerical methods: analysis, algebra, ordinary differential equations" , MIR (1977) (Translated from Russian)
[2] B.P. Demidovich, I.A. Maron, E.Z. Shuvalova, "Numerische Methoden der Analysis" , Deutsch. Verlag Wissenschaft. (1968) (Translated from Russian)
[3] W.E. Milne, "Numerical solution of differential equations" , Dover, reprint (1970)

Comments

In the Western literature, the method here called "Milne method" is called the (explicit) midpoint rule. Instead, the corrector appearing in the "predictor-corrector Milne method" is called the Milne method or a Milne device. This method is direct generalization of the Simpson quadrature rule to differential equations. The terminology "Dahlquist stability" is nowadays seldom used in the English literature. More frequently, one uses "zero-stabilityzero-stability" , "root-stabilityroot-stability" , or just "stability" .

References

[a1] P. Henrici, "Discrete variable methods in ordinary differential equations" , Wiley (1962)
How to Cite This Entry:
Milne method. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Milne_method&oldid=47837
This article was adapted from an original article by V.V. Pospelov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article