Computational Methods for Modeling of Nonlinear Systems

Numerical Solution of Ordinary Differential Equations

2 0

ACADEMIC PRESS

New York

1971

COPYRIGHT 0 1971,

BY ACADEMIC PRESS,INC. ALL RIGHTS RESERVED N O PART OF THIS BOOK MAY BE REPRODUCED IN ANY FORM, BY PHOTOSTAT, MICROFILM, RETRIEVAL SYSTEM, OR ANY OTHER MEANS, WITHOUT WRITTEN PERMISSION FROM THE PUBLISHERS.

ACADEMIC PRESS, INC. 111 Fifth Avenue,

New York, New York 10003

United Kingdom Edition published by ACADEMIC P R E S S , INC. (LONDON) LTD.

Berkeley Square House, London WIX 6BA

LIBRARY OF CONGRESS CATALOG CARD NUMBER: 73-127689 AMS (MOS)1970 Subject Classification: 65L05

PRINTED IN THE UNITED STATES OF AMERICA

TO Mary and Jay

on on on by on

book

book on

on a

of

xi

Preface

book book by on

on upon on

1 2 4

3.

5

6

book book

by

A.

J. S.

S.

1 A

Fundamental Definitions and Equations

1.1. THE NUMERICAL PROBLEM AND NOMENCLATURE

dy/dx = Y’(x)=f(x,

(1.1-1)

by

Y(Xo) = Yo

(1.1-2)

f ( x ,y ) y

x. xo

x

1

2

1. Fundamental Definitions and Equations

y(x)

yo

x = xo.

y(x)

x

( y o , xo)

y(x), x

fxn>, y(x)

y

=

=

x

As

in y 2 ' , . . . , y,,,'

m

{yn},

on

2,

[yl,

..., dy/dx = y'

= f(x, y)

Y(X0) = Yo

on x by

Y,,,+~ (1.1-7)

by

Z' = F(z)

4x0) = 20 ( I . 1-8)

autotiornous

(1.1-8)

( 1.1-9) nonautonomous.

3

1.2. Taylor Series Expansion

a 5 x i b, - 03 < y < co

f ( x ,y ) a

b x

L

E

[a, b]

u

u, If(x, ). - f ( x ,

-

.)I 5 L Iu - 4 on [u, b ] ,

y(x)

y(x)

x.

x,,> xo,

{x,} {y,}

y(x,) (u = x,, , b)

{x,}

x by

,..., N ;

x,,+~=x,,+~,,;

x,,=a; x N = b

h, = h =

h,

x,,, xl, . . . , x N ,..., N ; h,=h

X , = X , + H ~ ;

x,,.

x,,

x,

= xo

+ ah

- 13)

c1

c(

x,

c(

xo, x l , x 2 , ... .

x

c1

1.2. TAYLOR SERIES EXPANSION

f ( x ,y )

x

y(x)

x

-

= xo

y,

4

1. Fundamental Definitions and Equations

ct

c(

=

1,

y'(x)= y"(x) = y y x ) y'"(x) = y [ 3 ' ( x )

y(x,) y'(x,),

x

h

y"(x,), .. . .

y(~,+~)

y)

y y'

Y"

=f,

= f '= f ,+ f , f

fx

x

Y"'

=f"=f,,+ =f

y(x)

y(x)

y.

+f XY+f,Cf, + f , f I

+ pf,j

= 0,1,2,

...

f (x,y )

1.3. ASPECTS OF NUMERICAL INTERPOLATION

y(x), {x,} (h,, = h =

[6]:

5

1.3. Aspects of Numerical Interpolation

1.

A AYn =Yn+l -Yn A2yn = & n + t - AYn = Yn+2 - 2Yn+1 + Yn A3yn = A2Yn+t - A2Yn = Y n + 3 - 3Yn+2 + 3Yn+ - Yn Aqyn = Aq- 'Yn+l -Aq-lYn

2.

V VYn=Yn P Y n - 1 V2y,=V~n-Vyn-t =~,,-2yn-t + Y ~ - z V 3 y n = V 2 y , , - V 2 ~ , - l= y f l - 3 y n - 1 + 3 ~ , - 2 - ~ , ~ - 3

(1.3-2)

vqyn = v4-'yn - v q - ' y , - l

+ a(a -

+

s((9

+

... ( 3 - n

+

n!

. . . (.

+n -

n!

x, - xo

Anyo,

CI

V"Yn>

Ex=-

=-

Xa

h

- Xn

. n

+

(1

h

by

{x,}.

(yo, y l , . . . , J.,)

y(x)

n or

n,

T,

C

x (1.3-3) by the

J*[""~(() (1.3-4) (1.3-1)

=

C51/7"+1y"'+'1(() xo < [ < x, .

(1.3-2).

of

6

1. Fundamental Definitions and Equations

book,

1.3.1. Hermite Interpolation

{x,},

{y,}

2n

n+1 nomials,

{x,}

{yn'}

{yn}

+2

osculating polyup by

ai(cc)

bj(cc)

2n

+1

n 2n+2

T, = C,h Y q(.) bi(cc) 1.7

[2n+2]

(0 by 1

a =1

HERMITE EXTRAPOLATION

i =0

1.5.

7

Specific Integration Formulas

HERMITE INTERPOLATION

Yn = T, =

1

+ Y n + 11 +

+

Yn = T, =

+

Yn

T, = Y,

=

+

- YA+ 11

+

-

+

(

+

+

1

-

i-

T, = Yn =

1

+

+

I

-

+ (

-

T, = (h6/80)yc6’(()

1.4. DIFFERENTIATION FORMULA;

dyjdx = y’(x)

yn’), y”(x), a

+

hy,‘ = (A + 3 - * . .)y, hy,’=(A+~A2-~A3+...)y,_l hZy; = +1 11 2 - _I 8 5 + * * .>Yn

h2yi = hy,’ = hy,’ =

2

-

+ -

1 2

+1 12

- ,

+ 3 7 3 + . . .)y, + ..* ) y n +

-373

1

1.5. SPECIFIC INTEGRATION FORMULAS

1.4 (1 5 1 )

8

1. Fundamental Definitions and Equations

y(x)

by

ODES. on

y(x) d x

=

dx

=

~ ( x d)x

=

+ :I/

s,,

X"+Z

Y(X)

L-

+ + A - &A2

+A +

XI8

-

1

A2

+ &A3

+ . . .IYn

--A4 720

+ 0 A3 - i&

A4

+ ...]y,,

+ A + & A2 - $ A3 + %A4 -

. *IYn

/::-y(x)

dx

=

-

/;:+'y(x)

dx

=

+ +V + &V2 + $V3 + %V4 + . *.]y,

Ln

y(x) d x

=

+ *V2 + +V3 + g V 4 + . . . l Y n + l

/;:+'y(x)

dx =

X,+2

-3

-

-

- &V3

*

& V2 -

- -V4 720

- ...]y,

V3 - &$ V4 - * * *IY,+ 1

1.6.

As by by (1.5-3)

Anyn, by

A3

x+:/2

x,

Y(X)

dx

< I <x,+~.

=

+ A + + A2]yn -

after

A2

9

1.5. Specific Integration Formulas

by by

(x,,, x , + ~ ) (x,,, , x,,+& (x,,, x , , + ~ ). ,. . . by

h do

X"

trapezoidal rule

Simpson's

rule.

5)

X"

+

(1.5- 18)

10

Fundamental Definitions and Equations

1.

1.6. INTEGRATION FORMULAS FOR ODE y,) Xn+ I

= Y,

+ Jx

= Yn

+

dx

xn+

1

y"x> dx *n

+h

= y,

yo

n

= 0,

y,,

,

1

d.

0

2,

...

xo, y,,

.. , 1.5

1.5 y'(x)

y,

, y,) = f , .

y,'

(1.6-1).

by

YL+a =

q

Y,'

+ .VY,

+ (a

-

,

+ V2y,' + +7

1 )(.)(a

+ 1) . . . ( a + q 1

4! (1.6-1)

yA+,] 4

Y,+,

= yn

(1.6-3)

+ I? 1ffiVi4',', i=O

=1

“i =

?^,’

11

Integration Formulas for ODE

1.6.

a(a

+

... ( a + i - 1) i!

da,

y[q+23

c = a 4 + i h 4+ 2 Y t 4 + 2 1 ( 5 ) a,

+ -c I 2 V2 + $

+ +&+ + ...]y,’

T, = @ ~ ~ y [ ~ ] ( ( ) ;

q=

, = y,, + hy,‘

= +hZy[’]([)

T, = + h 2 y [ ’ ] ( [ ) , T, = O(h2)

h2. by

=0 =

+

+

y n + I= y n - 3

+

- 4v

Y , + ~= y n - s

+

-

ynfl= yn-,

+ +v’ + +V3 + + +

+ ...]y,’,

=

+

5, 1 (

+ 0v3 + g v 4 + -lYn’, - 9V3

1, 3,

=3

+ OVs + ..*]v,‘ =5

(-

1)

by

1

12

1. Fundamental Definitions and Equations

-1

y,+l = yn-5

+

+ +V2y,' - 5V3y,,'+

- ~VY,,'

1 1 ~y,'] 4

T, =

(1.5-17),

y'(x)

y(x),

= 0,

1, 3,

y n + l= y ,

+ k [ 1 - +V - --l-Vz 12 3V'2 4

Y , + ~= Y , , - ~+

-

Y , , + ~= Y , , - ~+

-

-.

- +&V4

+ +V2 + OV3 - 2-V4 90 -

*

.lA+1, n+1,

i" =

0 (

r= 1

8V + y V 2 - $V3 + g V 4 - 0V5 -

+ k [ 6 - 18V + 27V2 -s v 5 + ...]yA+1,

by r Y"

n 1 +=

=0

+ (~/~)CYA+ + 1

T, =

Crank-Nicholson

=

3,

+(~/~)[YA+I

y,+l

T,=

1

-

3

r

5

+W-V"

Y , + ~= Y , , - ~

~

Y =

=

1

13

1.6. Integration Formulas for ODE

+

+ 12YA-1 +

+

yn+i = Y n - 3 T, = -(Sh7/945)y"'(~)

+

1.6.1 Adams Forms r =0

r=1 r Adams-Bashforth (A-B)

=0

Adams-Moulton (A-M)

r =0

y,+1 =

y,

+ h[y,' + +Vyn' + $~V2J),' + +V3yn' + ++##V"y,'

+ -4Aq75y 1440

r Yn+ 1 = Y"

+ "6*

n

'+

60480

n

' + . . .]

=0 1

-P Y A + 1 - i

w Y ; + 1 - &V3L'r;+ 1 - +&J4A+ 1

_ _I_~ 0 v 5 ~ -;T+ o 8 6 3 v6 I r n Y;+, +

on

A-B

(q = (q =

(q = 1. TABLE 1 . 1 ADAMS-BASHFORTH FORMS

4

0 1 2 3 4 5

h

YA-

Y.'

1

1

112

3

11720 1/1440

23 55 1901 4277

1

YA-2

Yn-3

Yrt-4

-1 - 16 - 59

5 37 2616 9982

25 1 2877

Y.-5

14

Fundamental Definitions and Equations

1.

4 Y,+

1

1.1,

=Y,

+ hyn’

( 1.6-25)

( 4 = 0)

1.2, TABLE 1.2 ADAMS-MOULTON FORMS

4

of h

0 1

1

Y:+ 1

1 1

112 1/12 1/24

2 3 4 5

5 9 25 1 475

]/I440

Y.;

1 8 19 646 1427

3

Y:-4

- 19 -173

27

Y,-

Y:-2

-1

-5 -264 -798

1 106 482

Y,,+~, y n

4.

1.6.2. Nystrom Forms r Y,+~ y,+1 = yn-l

1

+ h[2y,’ + OVy,’ + +V2y,‘ + 3V3y,‘

+ gv4yfl’+ +4v’Yn‘+ m 378 v06 y , ’ + . . ~ n + =l ~ n - l

=

Nystrom

(1.6-17). yfl-l

(1.6-29)

+ hC2yA+l - 2 v ~ L + l++V’.YA+~ + O V 3 ~ A + 1

- &7V4j)A+, - & V s ~ ~ +-l *V6y;+1

As on

+

(1.6-30)

15

1.7. Generalized Integration Formulas for ODE

on 1.3

q

=0

+ 2h"'

=

(1.6-31)

midpoint rule.

O(h3). TABLE 1.3 NYSTROM EXPLICIT FORM

4

h

Y"'

1 1 113 113

0 1 2 3 4

2 2 7 8 269

Y L1

y,,

r

,

Y"P3

Yn-4

0

1

-5

4

294

r =0 r =3

Y:-2

r

=

-1 -146

29

1

= 5.

y , , ...

1.7. GENERALIZED INTEGRATION FORMULAS FOR ODE

Y,+~

y,, Y , , - ~ , ...

16

1. Fundamental Definitions and Equations

(1.7-1) (1.7-2) by (1.7-1) (l.7-2),Y , + ~ yi’ on

on

Y , + ~ ,y n + * , . . .

y,

k

Yn+k

=

aiYn+k-i

+

i= 1

on

by

k

1 i=O

(1.7-2’)

fiiY;+k-i

(1.7-1) (1.7-2). 2k +

(1.7-1)by

Pk.

a l , . . . , ak, P o ,

...,

(1.7-2) k, h 1.7.5),

Of

pi

h yy, yy, ...) xi on (1.7-1)

yi‘

(1.7-1).

k

1.6.

r

(1.7-3)]

k k = 1, y , ,

y,

y,,‘;

yA+

single-step

k>

yi

( x n ,y,) y,

Y,+~ multiple-step

( x , + ~J ,J , + ~ ) ] .

ynPl. = 0,

open, explicit,

predictor

on

Y,+~

Po # 0,

Y,+~ closed, implicit,

corrector

on Y,+~

(1.7-I), a l , a z , . . . , c$,

Po,

P 2 , . . . , Pk. x

17

1.7. Generalized Integration Formulas for ODE

p, p.

by

1.7.1. The Method of Undetermined Coefficients

k

=

1,

+ /?[Po

Y n + i = %Y,

+ PiYn’l ul,

frl

fro,

y ( x ) = 1, x,

2(p =

yi‘ = 0 y.’ = 1

Y i = 1, Yi=xI

i=n,

Yi’ =2xi

y t. = x.2 t

7

y i = 1, yi’

x2

=0 =

Y , , + ~=

1 = uIxn0

yi =xi, y;

a1 = 1.

=

+ h[[joO +

1

=

(x,+~ - xn)/h=

1 = fro (p=

+

Y”+ I

p

fro

=

=

+ ff?/2)[Y;+

fro

frl 1

= 4.

+ Y,’]

(P =

+ 1 = 3. p

Yn+l

=

(p=

+

+ fr,

= x i 2 , yi’ = 2xi

=

- Bl)rA+1

+

( P = 1)

p1

18

1. Fundamental Definitions and Equations

p1 by

p

=2;

y(x)

x3. Yn+ 1

x3,

= Yfl

+(k/2)lX+ +

+

1

yC3]. y , = xi3, y,’ = 3xi2

y r 3 ]= 6

C = -h3/12

T, = -(h3/l2)yC3’([) y , = xi2, y,’ = 2xi,

T, =

C y C 2(yCZ1 ] = 2)

C y,,

1

=Y,

+ hC(1 -

= -h 2 [ $

1

1

- PI]

+ PlYn’l

-

k 2 C t - P*lv”l(i>

&

=

PI = 4,

p1 = 1,

p

k

+1

=

1

x,

=0

yi

x, , h

up

p.

kP+’ J!,,+

kJ$+1

= yn =

+ hyn’ + + k 2 y : + $I~J$’ + . . .

+ h2y: + +h3y: + . . .

p

19

1.7. Generalized Integration Formulas for ODE

(1.7-4),

Yfl 1 -1 0 0

Yn+1

- Yfl -3hYA+, - fhy,‘

0

hYn‘ 1 0 -112 - 112

h2yL 1I 2 0 -112 0

0

h3yr 1I6 0 -1/4 0 1/12

0

2

h up -+ih3yC31. 1.7.2. Adams Forms

k

As Yn+i

= a l Y n + a 2 Y n - l +a3Yn-2+cc4Yn-3 + h[pOyA+l + Plyn’+ p 2 Y A - 1 + p 3 Y A - 2

=4

+ 84.Y;-31 (1.7-10)

a2 = a3 = a4 = Po p = 4. (1.7-10)

y ( x ) = 1, x, x 2 , x3,

cc1=1,

P1=+$,

yn+1 = y ,

x4,

p 2 -- - g ,

p3=z,p

4 --

+ (h/24)[55yn’- 59yA-1 + 37yA-2

-224

- 9yA-31

(1.6-28).

=0

(1.7-11)

a2 =

a 3 = a4 = 0,

Po = 0

1.7.3. Higher-Order Derivative Forms

J’n+ 1

+ a 2 J’n-1 + = 3 Y n - 2 + h2CYoY:+ 1 + YiY: + Y 2 Y:-

= aIL’n

(1.7-1)

1

+ Y3~ i - 2 1

(1.7-12)

20

1. Fundamental Definitions and Equations

6. 5

x3.

y(x)

T, = CyC6’.

. . . , x5 a1 = 2

+ a3,

Yo = y2 =

+

=

t12

1, x,

a3 = a3

-

y1 =

-

=

y3 =

ct3 = 0

+

+

+

- Yfl-l

Y,+l =

T,=

~(-11

Numerov’s

+ P i ~ n ’ l+ h Z C ~ o I C ++i Y ~ Y : ]

+

=

p

y(x) = 1,

=4

x, . . . , x4 Po=&=+

yo=-’ = Y,

129

Y1

+

+

+

=&

+ XI

T,= 1.7.4. Gaussian Forms

Yn+l

= u1Yn

+ hPlf(xn+p,, Y n + p I ) + hP2 f(Xn+pz, al,

x,+~,

x,+~,

x,

pl,

Y,+PJ

p2,

x,+~

do

p =4

y(x)

= 1,

. . . , x4. P1+&=1

+ P2X,+Pz 2 B1X,2+p1+ 8 2 X,+p, 3 3 PIX,+L3, + B2 x n + p 2

BIXn+pl

=

4

=

3

=

t

21

1.7. Generalized Integration Formulas for ODE

4

pl, f12,

x , + ~,

= p 2 -- 2I

1, 3-43

cI1= Xn+p,

=

(

3 4 3 Xn+O2=-

t

~

6 be

1.12 As

book ( p =4),

1.7.5. Variable Step Forms h h = h,

Po = 0 a 4 = 0.

71 =

1,

7 2 = 2,

h

73

a2 =

fix

do

T ~ 7, 2 ,

(

PI

=

1- P2 -

4,

- P4

=

= 3,

22

1.

T ~ T,

T~ =

~

1,

,

T~

Fundamental Definitions and Equations

73

= 2,

T~ =

on

3

by

[9].

1.8. COMPILATION OF VARIOUS MULTIPLE-STEP INTEGRATION FORMULAS INCLUDING yi AND yi’

yn, y n - l , . . .

, yfl , r

...

,

{xn}.

Po = 0

flo # 0 k by

p

[2]. 1.8.1. Explicit Forms

k

=4

Yn+l =alyn+a2Yn-l

+C(3Yn-2

+E4Yn-3

+ ’?[Plyn’ + P 2 Y L - 1 + 83Y:-2 + f l 4 Y L - 3 1

(1.8-1)

xi p = 4.

1.4. 1.4

EXPLICIT EQUATION(1 3 - 1 ) k=4, 611

a2

a3

a4

1 0 0

0

0 0 1 0

0

I 0 0

0

tll =

p=4 P 2

55/24 813 2118 9/24

0

0 1

1

-59124 -513 -918 -413

(1.6-28),

P4

P 3

37/24 413 1518 813

c ( ~ =

-9124 -113 -318 0

1

1.3),

k Yn+l

=aiYn

=

3

+ a 2 L ’ n - 1 + H 3 Y n - 2 + ~ [ P I Y ~+’

+ 83Yn-21 (1.8-2)

23

1.8. Multiple-Step Integration Formulas Including y i and y,‘

(1.8-2)

4, p

5.

by

= 4,

a3

1.5

as.

(1.3-7).

a3 = 10

1.5

p=4

+

9 10 9 18 3

c(3 =

PI = p2

a3

=

p3 =

-

0

+ +

(- 1

T, =

”

9 0

9 1 6 6 0 12

9 1613

4413

0 1962 by

W.

by

-7

-8

- 18

- a3 a2 = 9

*

by / ~ ’ y [ ~ j ( & S ! .

(1.8-2),

3 a2

1.6.

a3 1.6

k

+ aZ

=

1

=3

+ a3 Yn-2 + I1[fllYn’ + f l 2 y i - 11 (1.8-3)

a3 (1.3-6)

J’n+ 1

T, =

=

=3

1.7

a3 = 0

a3. ci3 = 1

+

1

+

+ 6hCyn’ +

~ n - 2

11

24

1. Fundamental Definitions and Equations 1.7

(I k=3, - 54

5a3

MI=

u* = 5

u3 = a3 pi f 8 2 = 2 f 4a3 T. = 4 - 4 ~

3

9 1 6 6 0“

45 10 24 42 - 36

5 0 4 2 4

0 1962 by

W. by

Book by

‘T, = k

=4

p4 = 0, u3

1.8

p = 4.

a4

1.8 2-5)

-8

- u3

+ 8x4

-8 9 0 0

u3 = u3 a4 = a2 = 9

PI = ==

P 3 =

+ a3 + (- 1 + +9 d 3

T,= a

0 0 0 1

-

1413

-

a3

- 4a3

+

-I 9 1

0 6 6 0 9

by h5yr5](5)/5!.

a3 = 0, a4 = 1

y,,+

I = yn-3

1.8

+

-

y;,-

I

+ 3~*:-2)

0 1 1 3 0 3 36

1.8. Multiple-Step Integration Formulas Including

25

and y,’

1.8.2. Implicit Forms k Yn+

=

+ E Z Y,- + hCPo Y;+ + P l y ” ’ + P 2 .Y;-

=

1

11

(1.8-6)

= 3.

1.9

1

(1.8-6)

a2

p

TABLE 1.9

IMPLICIT EQUATION

1

1 - cc2 =(5 -

po

= (8

+

415 1i5 215 415 0

0 1 113 413 113

0

o(2 = o(2

c(2)/12

bT,= “

0

W.

1962 by

by

by

T, =

x2 = 1 Milne’s equation

1) = Y,-

y,+

T, = -(h5/9O)y[’’([) k

1

(1.8-7)

4.

=3

+ +

yn+l = E ~ Y ,

a2 1.10. a2 = z3 = 0

+ ( h / 3 ) M + 1+ 4yn’ + YA- 11

* * *

~ 3 Y , - 2

+ h[P,Y;+1 + . . . + p =4

u3

ci2 =

x 2 = 0, x 3 = 1 a2 = 0, u3 = - $

41. (1.8-8) 1 1 p

P3 = 0 = 4.

by

b3YA-21

3 Humming’s rz

1, x 3 = 0

h,

TABLE 1.10 (1 3-8)” = 3.

k 0 0

9/24 19/24 .- 5/24 1/24 -1916

p=4

0 1 0 I 13 413 113

0

0 1 318 918 918 318 - 912

0

-413

113 113 113 13/36 39/36 15/36 5/36 3

112 112 0 17/48 5 1/48 3/48 1/48 - 9i4

918 0 -118 318 618 318 0 -3

01962 by

b’. by

0 213 113 25/72 91/72 43/72 9/72 --43118

Book

by h 5 y r s 1 ( [ ) / 5 !

TABLE 1. I 1 (1.8-8) p3=0, XI

-

U/8)(9

-9

4

c(2 =c(2 a3

Po

-

PI Pz

-

-(1/8)(1 - X Z ) (1/24)(9 - a z ) (1/12)(9 f 7az) (1/24)(-9 i l 7 ~ 2 )

T, x h5y[5’([)

0 1 0 113 413 113 -1190

k=3,

9/17 9/11 -1117 6/17 18/17 0

-31170

p=4

1 119 -119 10127 22/27 -8127 -19/8lO

918 0 -118 318 314 -318 --1/40

917 -117 -117 8/21 213

--10/21 -171630

45/31 -9131 -5131 12/31 1813 1 18/31 -9/310

9i5 -315 -115 215 215 -415 -1130

27

1.9. Multiple-StepFormulas Including y i and y,'

1.9. COMPILATION OF VARIOUS MULTIPLE-STEP FORMULAS INCLUDING yi AND ~

i "

y" = f ( x , y )

yn, yn-

...

Y : + ~ ,y:, yz-

1,

.. . .

1.7.3

1.9.1. Explicit Forms

Y.+

1

+ @ 2 Yfl- 1 +

=

+

Y::-

11

(k = p

= 3.

do Y,+ 1 = - Yn- 1 + T, = (k4/12)Y[41(1)

k = 4, p = 5 Y"+ 1 = T, = -

1

+

-

+ Y:- 1 +

by Yn+ 1

= 2 ~ -n

Y.-

1

-~

yn+1 =

+

~

+

1

+

Y"+l = 2 Y n - Y n -

-

-

1

+

+

+

-

1

- 1761';-

x

1

-

+

-

Stormer's equation. 1.9.2. Implicit Forms k =2 = xi?,,

+

+

+

p = 3,

+

- 1'"-1 T, = - (k4/24)yt4'(<)

?'"+ 1 =

1

+ y:-

11

(1.9-8)

28

1. Fundamental Definitions and Equations

k

=

3

+ C(3Yn-2 + h2CYoY;+ t + YlYl + Yz

rlyn f

Yn+l

p

=5

cx3

+ Y3

a

1.12. TABLE 1.12 IMPLICIT EQUATION (I

k=3,

p=5

3

2

1

0

-3

1 1

0 0

-3

~~

1962 by

Hill,

by

by h 6 y L 6 ] / 6 ! .

a3 = 0 Yn+ 1

= 2Yn - Yrr-1

+ (hZ/12>[IY;:+ 1 +

+ Y;- 11

T, = Numeror’s

yn+ 1

= 2yfl - y n - 1

+

(1.9-10)

royal road

+

+

+ 4yi-2

-~ i - 3 1 1)

1.10. MULTIPLE-STEP INTERGRATION FORMULAS: HIGHER DERIVATIVE TERMS

As a J ’ ~ ,ji’

(1.7-14)

yi’,

1.10. Multiple-Step Integration Formulas Involving Higher-Derivative Terms

1.10.1. Explicit Forms

Yn+ 1

= XlYn

+ u2 Y n - I + U l Y , ' + D 2

11 + /I2[IY,?.;: +

1.13. 1.13

EXPLICIT EQUATION .10-1)"

"

Q 1962 by

Hill,

by by h5yrs1/5!.

I,

1

a2 = 0

1.10.2. Implicit Forms do : Yn+ 1

= j'n

T, =

+ ( ~ / ~ ) C Y A +1 +

+

11

p =4

(k = a2

'

4';-

1

+

29

30

1. Fundamental Definitions and Equations

5) 1

= 2yn - y n -

1

+ ( 3 h / 8 ) [ ~ ’ ; +1

11 +

1

+

-

11

0.

T, =

1.10.3. Higher-Derivative Forms

[5] = J’,

+ k ~ . , ,+’ ( h 2 / 2 ) y : +

T, = = yn

+

+

+

11 -

-

11

-

T, =

J’nt 1

= Yn

+

+ Y”’1- (h2/10)[!’::+ + yfi’]

+

T, = ( 1 2

1

-

J , [ ~ [)

by

k

by

by

k. k.

k

1.11. FURTHER DEFINITIONS

1.11.1. The Local Truncation Error 17

y(x) y(x)

+1 by

31

1.11. Further Definitions

bound

to

by

p

+1

p T ( x , h ) = ChP+ ‘ y [ p +

T,)

T ( x ,/ r )

local truncation error, xo

xl, . . . , x,,, by

... . y, + 1 = Y ,

+

>

= 0,

y, ; A),

1,2, . . .

on x,, y, ,

increnrent function

1

All

h

h)

x

y(x) T ( x , h) =

y(x); / I ) -

f

+

1

11)

If p

p’ (1.11-4)

h +0

T(x, h ) = O(hP‘+’) p p

on h,

g(h),

u(h)

C,,

u(h) = O(g(h))

h,

Iu(h)/g(h))I C1 h+O

hp+’ h. @ = f ( x , ,y,).

=Yn+hS(x,>Y”)

(l.6-7)), h) = +/z’y”’(<)

=

1,

32

Fundamental Definitions and Equations

1.

O(h2).

+ hf(x, Y ( X > ) - v(x + h)

T(x,h) = = y(x)

+ hy’(x)- y(x + h)

(1.1

p

p

p on bound,

< hP+’C bound

h-(p+

-

hP+’ C

-+

C

( 1.1

h30

As ly[21(x)l I M

by

IT(x,

= b(x)

+ hY’(X) - v(x + h)l 5 (h2/2)M

bound on

by

L[y(x)],

p L[x’] = 0,

j = 0, 1, . . . , p

L[x’] # 0,

j =p

+1 y

y(x) p

y(x) = j=o

.

1

k

p!

0

-x J + - f (X - V ) ” + ~ ~ + ’ ~ ( V dv ) y”l(o) J !

(x - v),

=

x -v)

(1.1 1- 10)

L,

1

1 k G , ( V ) ~ ~ ” ~ ’dv ’(V)

L[y(x)]= 7 P.

0

(1.1 1-1 1)

33

1.11. Further Definitions

by

influencefunction,

12)

CP(4 = L[(x g(x) x=(

aI x r b

f(x) b

jJ(x)s(x) g(x)

a

b

b

dx =

(1.11-13)

d x ) dx

on [a, b ] [ 2 ] . as

( I . 11- 14)

(1.11-15 )

Y , + ~- y ( x n + , )

T ( x , h)

(1.11-16)

Gp(v)

G,(v)

1.11.2 The Accumulated Truncation Error accumulated truncation error

we y(x)

by

~ ( x +n1) = Y(xn) + h@(xn J(Xn) ; h) - T(xn h ) 9

9

( I . 11- 17)

34

1. Fundamental and Definitions Equations

T ( x , , h) h -+ 0, T ( x n ,h) +

0

E, En

1-

= Y n - Y(xn)

y)

T(x,h ) =

IT(x,, h)l fl

by n = 0, 1, 2, . . .

T ( x ,h) = T. i

1 ~ 2 1i

i i i

(1

+ hL) + + hL)I&,I+ + hL)21e,l + + + + hL)I&,I + T + ~ L ) ~ I E+, I + + h ~+) + ~ L ) ' ] T on

by

bound on

(n + E,, =

0

35

1.11. Further Definitions

y), Ent1

+ hf& +

=

f;-

y, I

=

jj

(1.11-26)

, h)

I

lfyl

h)l 2 T,

bound on of

E,

by

bound

7

y” = f ’

=f,

+f,f.

A) = bound ~ ” ( 5by )

M

= a
f,

f, =

u20

+ hL)”+’ I

+ +

-

len+ll I

-

=

-

E~ = 0,

I

IEn t 1

t1

-

h --t 0,

1.11.3. Other Items on

All

do

local rounding error. Jn+l

en

+

= jn

12)

+ e,

- 11

-

11

L

36

1. Fundamental Definitions and Equations

h x

hM

En+1<

e

[i + ];

L

xO)l

-

En = J,, - y(x,). h+0,

e n ,Eo = 0,

e=

-

[

x = x, .

= xo

h, hop,, ( h M / 2 )+ (e/h),

h

hop,= (2kfe)'iZ hop,,(hM/2) = (e/h) good h y' = -y,

yo = 1.0, h=

h

y ( x ) = eCX.

h

=

x = 1.0

1.0,

2. on

360

hop,

e

M =1

110-,4,

h,,,

hop,

= 510-4

=

ll0-,.

h h

h h h

1.14

31

References 1.14 -YATX=

FORy’=

1.0

h

DP 1.810-7

9.210- 6

4.610- 4 .Sl0-

3

-

book

stability

principal error function. n

4 T ( x, h ) = hP+’+

+

4 = +y[’](().4 hp+’

1967.

1. 2.

“

1962. 3.

“

1962. 4. 5.

Z., J. D.,

A.

1955. y’ = f ( x , y ) by 2. Angew Mufh. Phys. 13,223

38

1.

6.

Fundamental Definitions and Equations

“

1962. 7.

f. Franklin Insr. 262, 111 8.

y” = +(x, y , y’)

Znsr. 263, 401

J. 9.

Wyk,

2 Runge-Kutta and Allied Single-Step Methods

a 4

3.

2.1. DEVELOPMENT OF SINGLE-STEP RUNGE-KUTTA FORMULAS

by

( x . + ~Y, , + ~ )

(x,,y,).

up by

(x,, y,)

f ( x , y ) within

( x , + ~Y, , + ~ ) .

by

f ( x ,y ) 39

40

2. Runge-Kutta and Allied Single-Step Methods

up

" wi

L'

f ( x ,y )

v

k,

1,

=

wl,. . . , w,

c 2 , ..., c v , a Z j , ...

y)

(x, y )

yn,

yn+l xn .

x,,+~

y)

h

v

=3

w2,

c2,

f ( x ,y )

x

Y' Y" = f x Y "'=f x x f ( x n , y,)

k1 = k2 = h f n

+

+ +

+

+f'f,, +f , ( f +f f y ) =

1

=Yn

+

= hfn

Y ) =f +f,f

=fn

Yn+

k3

y,

+ h f n + + h 2 ( f x + .ffy>n + + .r2fyy + f y f x + f y ffy>n

+ h2(c2 f x + a , , f l y > n +

fx

fx

+ ~2 a z l f f x y + +

+ +

+ a21ff)fy>n

+

+

+

41

2.1. Single-Step Runge-Kutta Formulas

(2.1-5) w 1 + w2

c p a21W.7

+

w3

+ (a31 + a32)w3

a21w2

by

(2.1-1) =

1

=

3

+ c3 w3 = 3 + 3c32 w3 = +

cp wp 3c22w2

+ c3(a31 + a32)w3 = 3 c2 LZ31w3

=

(2.1-4)

1

2

$21w2

+

+(a31

+

4

a32)'w3

=

a21431w3

=

(2.1-6)

+ a32

c2 = a p l

c3 = a31

(2.1-7)

(2.1-7)

c2 c3, p =3

a (p=u

=

2.1.1. Specific Runge-Kutta Forms . always

h2 : w1

+

w2

=

1,

c2w2

c2 1

( w l , w2)

p

(0,

= +,

(4,2 )

c2

(2.1-9)

w2 .

c2 = 4, +,

)I!, (+,+)

Y"+l

= Y"

+ h f ( x f l + +hYfl + 3hffl)

Yn+l

=Yn

+ (17/4)Cf(xn,

Y"+ I

=

Y"

= a21

(2.1-10)

+ 3f(xn +

+ ( h / 2 ) C f ( x f l ,Yfl) +

+ 11,

+ (2.1-

+

= 21 = 2 L' =

3

I - = 4,

42

2. Runge-Kutta and Allied Single-Step Methods

Y,+i = Y ,

k3 Y,+i

+ 4k2 +

+

= hf(x,? = Izf(x, = hf(x,

Y,)

+ fh, y, + + h , y , - k1 +

=Y,

+

+

k l = h f ( x n 2 Y,) k2 = h f ( x , t h , y , $1, y, k3 =

+ +

Y,+

i

+k2)

+ 3k2 +

+

=Y,

+ +

= hf(xJl7 Y,)

+ +h, Y , + k3 = h f ( x , -t- Sh, y , + $ k z ) =

-

by

= yn

+ 3kz + 3k3 +

+ Yn>

=

k2 = k3 = h f ( x , k4 = h f ( x ,

yn,

1

hy,:+ 1

+ t h , y,, + + k i ) + yn + + + h , J, + k2 +

+

+k1

k1 -

+ + + i [ k 1 + 4k2 f

= J.’, hy,’ = f7)’”’

k3]

-1

43

2.1. Single-Step RungeKutta Formulas

2.1.2. Alternative Approaches to Generation of Formulas

on

x , + ~by

x, (x,, x,+~).

+ X k i + 3k3I

=

kl = h f ( x n ,

kz k3

h j ( x , , + +h, y, = h f ( x n + +h, yn

=

+ +

#I)

Gk2)

Y,,+~

1, y n + l / 3

2.1.

+ (h/3)y,'

=

Yn+l/3

y,

p = 1, Yfl

2, y n + 2 / 3

Yn+l/3 Yn+2/3

= yn

p y,

+

= 2,

3, Y , , + ~

y,+2i3 Yn+ 1 = Yn

+ +Y,' + $ Y A + 2 , 3

TABLE 2.1

1 2 3

Yn+1/3

1

Y n + 213 Y", 1

114, 314

1 2 3

44

2. Runge-Kutta and Allied Single-Step Methods

h

p = 3,

h x.

1.5,

x , , + ~ ,A ~.

by

1.7.4

2.2

2.2

112

rt

1 1 I2

2 4

1

1

114

3

0

0 213

0 - 1/6)/10

314 119

+

5

0,1

1

2

0,1 1 I2

116 213

4

+

0, 1 (5 i 1/5)/10

(16 -

6

45

2.2. Condensed Nomenclature

[33], x,

(0,

x,,+~)

( - 1,

+

2.2 2.2

no

0 0

do x,+~

x,

look

As (Y, L‘) =

5),

7),

f(x, y )

r > 4. 2.2. CONDENSED NOMENCLATURE FOR RUNGE-KUTTA METHODS

by

0

or

c2

a21

c3

a31

a32

c4

a41

a42

a43

46

2. Runge-Kutta and Allied Single-Step Methods

A, aij on x, MI,, . . ., H'".

ki

y,, wT

c L'

11 3 1

2 1 4 1 6

6

ki+l explicit ki+l

b

A, k i , ki-,, ..., k,. As open-ended Runge-Kutta. on k i + l ,k i . . . . , k , k , , k,-,,. implicit closed-end Runge-Kutta

. . , k i + l ,k i , . . . , k,.

2.3. EXPLICIT RUNGE-KUTTA EQUATIONS OF DIFFERENT ORDER

L'

by p substitutions, derivative evaluations, L' p p

L'

stages,

N(r) p

z'

N ( r ) = z', N ( 5 ) = 4,

2'

1)

54

5, N(7) = 6 N(9) = 7

=

N ( 8 ) = 6,

1,

15

..., 4 p

= I'

5

no

47

2.3. Explicit Runge-Kutta Equations

0)

5 8.

2.3.1. First-Order Formulas (1, 1) (1,

2.3.2. Second-Order Formulas (2, 2) c2 p

=2

c2

C2

:2

1-tcz by

f + fyyf’)

h ) = \I3[+ - ( C 2 / 4 > l ( L Y X + + ( h 3 / 6 > ( f xf y + f;’f> Of = f ’

T ( x ,\I)

=f,

+f&,, + (h3/6)f,Df

= It3[+ -

+

= h3[+ -

c2 = +, 5,

fyf’

1,

+I: 0

9/, 3

c2

=

4

c2

=

5

0 1

3

1 3 4

4

-.

48

2.

Runge-Kutta and Allied Single-Step Methods

= 1 1 2 2

:

w1 = 0,

1.

2.

=

+

3.

+ ~n + + h, + A?,)

k2 =

do

y)

2.3.3. Third-Order Formulas (3, 3) c2

c3

by T(x,

+

-

=

+ (1

-

-

2

1 3 8

c2 =

2 1 3

6

+,

cj = 1

49

2.3. Explicit RungeKutta Equations

0 c2 =

3,

=3

c3

-

y ) =f(x). 2.3.4. Fourth-Order Formulas (4, 4) c3 .

c2

by

1 30

+ [--

w3 a 3 2 c22c3

+ w?c4(a42

2 c2

+ a 4 3 c32)

2 w4 a 4 3 a 3 2 c2

2

j

f P 2 . f

1

+

w 3 a 3 2 c 2 3 w4(a43c33 6

+

42

c f,,D3f

7

+ 1120 - - w4 a 4 3 a 3 2 c 2 ( c 3 + '4)]

f yO f y

1

+

120f3f)

0 ~

2

+

1

2

0 % 0 0 1

c* = cj =.=

+

50

2. Runge-Kutta and Allied Single-Step Methods

c2

= 4,

c3

=3

14)

0 1 2

3

1 2

(,I2

- \/2)/2 - J2’2

-

1

0

1

+ J2/2

~2

= ~3 = 3

(2.3-15)

2.3.5. Fifth-Order Formulas (5, 6) p 25

As

p = 5,

(2.3- 16)

a

192

0

-

0

192

8 1 1 2 5 192 192

[461,

_ _

&+,

G5,

( p = 6).

&,

2.3. Explicit Runge-Kutta Equations

0 1

51

1

-12

1 1 4 1 2

14 64

1

96

-1

-5 - A

64

64

1 2 -12 --

96

8 -

64 -

64

64

64

90

90

90

96

64

1 90

0

96

90

0

1

1

i

3

1

8

:;

-1 - -

1

2

4 5 --

1 4

64

64

_1_

0

90

2 2 0 -3 64

64

1 2 L j z G 90

90

90

0 1

-1

+

;

q - 1 1

-

-

-

1

-5

? 6 0 ° & 7

3

7

7

- 12-

7

0 1

1

.

1

1 -

r

0 - 3 1

3 4

8

-

1 8

13600

i%

8 7

90

52

2. Runge-Kutta and Allied Single-Step Methods

0 1 -

5 2 -

5

1 3 4 -

5

1 -

x,

k, x,,+~)

by k4

go

no k, by (5,

2.2 on

53.

x,-~

53

2.3. Explicit Runge-Kutta Equations n

rn

c;'

c? W

-.

3

?

4

G.

n

> 2

4

. n

0

4

. _ n

?

3

G. -?

t

2 .

0 3

0

n

4

oo

gg

n-

2

. 2

3

-. 4

4

sz 0

'

3

3 3

?!

m

3

54

2.

Runge-Kutta and Allied Single-Step Methods

0 1 -

1 -

1 -

1 -

1

0

2 -

7 -

2

2

4

27

3

-1 -

4

2

1

1 0 16 28 5 2

&

2

10

625

546 625

O

0

5 4

625

378 625

3555125 336

336

336

by

3

0 1 -

6 4 1 5 2 3 4 5

1 6

4 I5 5

6 8

_-

16 75

_ -8 25 18 5

361 320

1 -

5

3

2

144

31 384

16 25

~

407 128

2816

1 1 --

55 __

32

168

80

128

0 1 -__

9000 3 10 3 4

1

1 9000 -4047 10 2 0241 -~ 8 931041 -~ 81 ~

_4050 lo 20250 8 931500 81

15 ___-_ 8 _ _ _ _ _ _ 48910

112 __ 81

66

55

2.3. Explicit Runge-Kutta Equations

2.3.6. Sixth-Order Formulas (6, 7) and (6, 8)

0 1

1 -

1 -

1 -

-31

1

9

9

6

3 -

24

24

4 -

-3

6

4 8_ 5 27 24 _ -__ 8 8 8 8 _2 2_1 _ _ 9_8 1 -8 6_7_ _ 1 0 2 783 678 _ _447_82 _ -46 86 ___ 48 48

1 -

2

2 5 6

~~

41 840

?_

9

48

82

82

82

82

216 840

0

21 __

272 __

840

3 -

80 -

840

48

82

82

_2 7 _2 1 6_ 840

840

4_ 1 840

~

0 1 -

1 -

3

3

+

0

3

1 12 1 3 -

3 1 1 -

1 --

2

r

16

9 8

0

2

11 2

3 _16

3 --

8

_ _38 _ -43

1 2

0

1 300 1 -

5

3 -

5

14 15

1

~

1

300 29 5

__

__ 323

30 5

___ 330 5

5 5 1_ 0 1_ 0 4 __521640 -_ 810 810 417923 427350 I7 77 198

10 5

_ _1 82_17 00 5 10605 77 1225 3698 ~

~

1925 810 1309 77 1540 3698

~

54 77 810 3698

I

77 3698

_

_

~

56

2. Runge-Kutta and Allied Single-Step Methods

2.3.7. Higher-Order Formulas lo),

12)

2.4. RUNGE-KUTTA FORMULAS DERIVED FROM TRUNCATION ERROR ANALYSIS

p 24

As p > 4.

[56]

[38]

T(x,h) = P + 1 $

(2.4-1)

4

141 < C M K P ,

M,K

<M,

(2.4-2)

C= =

(2.4-3)

2.4.1 Second-Order Formulas (2.3-4) by

h ) = h3[+ - ( c 2 / 4 ) l ( f x x+ 2 f X Y ff

fyyf2)

+ ( h 3 / 6 ) ( f , f y+ f,’f>

(2.4-4)

(2.4-3) M, < KM,

f,
fXY
f,, < K 2 M f,,
(2.4-4)

h)/h31

=

141 < [4l+

- (c2/4)l

+

(2.4-5)

2.4.

bound on 4

c2 =

57

Truncation Error Analysis

141 < 4 M K 2 .

c2 = 3

2.3

+,

141 < + M K ~ 141 < 3 M K 2 141 < + M K ~

c2 = 3, c2 = 1,

2.4.2. Third-Order Formulas by

By

161.

c2 =

3,

~3

= 1,

c2 = cg = 1 47 c2

=

3, c3 = 3,

c2 = 3,

c3 =

+,

c2

c3

c2 = 4, c3 =

+

141 < 3 M K 3 141 < + M K 3 141 < + M K 3 141 < 3 M K 3 by c2 =

+ 0.4648162 0.7675919

= 0.4648162

0.4648162 0.8256939 0.2071768 0.3585646 0.4342585

2.4.3. Fourth-Order Formulas by

0 -2J

c3 =

c2 N 0.46 c3 N 0.77

58

2. Runge-Kutta and Allied Single-Step Methods

on

0 0.4 0.4 0.45573725 0.29697761 0.15875964 1 0.21810040 - 3.05096516 3.83286476

0 2 -

2

3 -

3 -20

5

5

1

5

3 4 19 -I2

44

44

c2

40 44

=f,

c3

=4

59

2.5. Quadrature and Implicit Formulas

y) = f ( x )

by 1

(T(x,h)l 5 (h5/2880)y[’1(C)

h = (1/2880).

bound

300

2.5. QUADRATURE AND IMPLICIT FORMULAS

3,

h. do

n

As

h. h h. h

A,

ki

aij. k , , k , ,.. . ,k i V l ,k i , k i + l ,. . .,k,; ki

As 2.1. 2.5.1. Basic Forms

by U

~n+l=~n+Cwiki i= 1

60

2. Runge-Kutta and Allied Single-Step Methods

,..., u

,

ki=hf u

c; = by

xr=

aij. c1 = 0, x = x, .

ki, k,, k,

x.

ki

i - 1.

aij.

A, j

=u

[8,9] u(u

Explicit

+

k,, . . . , k i - , .

ki, on i - 1.

z(u

Semi-Implicit

+ 3)/2

# 0.

ki,

k,,

. . ., k i . i

on c(u +

Implicit

ki,

k,,

. . ., k , . on

on

aij. u. by

y’ = f(y)

x

y

by XI

I

I

=

[

f ( x ) dx

= h C w; f ( x ,

+

i= 1

by

wl,. . . , w,

cl, . . . , cti, aij

61

2.5. Quadrature and Implicit Formulas

2.5.2. Gauss Forms

c 2 , . . . , c, -

=0

P,(x)

u.

xi

(- 1,

(0, by

p =

u

P,(2c

cl, . . . , aij( j = 1, 2, . . . ,

= 0.

-

i, i = 1,2, . . . ,

b.

w j ( j = 1,2,

...,

21)

U

C1 w j c ; - '

=

l/k,

k

=

1, 2 , . .., u

j=

#0 c = 1, 2,

u = 1,2, 3

. .., 5

p = 221, by

[ 151

+I+

(2.5-3) 1

(5 1/2

+

+ 3J

+

(10 - 3

+

-3

5

62

2. RungeKutta and Allied Single-Step Methods

2.5.3. Radau and Lobatto Forms

Case 1. c1 = 0; c 2 , . . . , c, Case 2. c, = c,, . . . , c,-~ Case 3. c1 = 0, c, = 1 ; c 2 , . . . , c,-~

1, x = 0 2, x = 1

x,) x.+~)

y); y).

to

3, x x ,+ ~ )

=0 y).

x =1

xn)

of p

= 2u -

1

p = 2v - 2

2

1

c1 = 0, all = aI2= . . . = a,, = 0 c, = 1, a,, = a,, = . * . = a,, = 0

1 2 3

1, 2, CASE

3.

aij

=

2

aij

3.

1 FORMULAS

010 1

u=1,

2.2

0

-

+

+ -

0

+ +

0

0

-

3

2.5.

Quadrature and Implicit Formulas

-

-

- 11

1

0 0 0

+ +

+ 11

+

63

-

u = 3, p = 5 CASE

3 FORMULAS

0=2,

O1 I 01 *0 1

I)

1 2

2

u=3, 121 6

3

6

2.2

0

+

-

+

+

0

1

0

+ +

1

7

+

-

1

-

0

0

0 119 21

0 1

+

-

1

0

0

0

- 21

-

+

119 219 U =

We

0 0 0

0 -

5, p = 8

0 0 0 0 0

64

2. Runge-Kutta and Allied Single-Step Methods

2.5.4. Semi-Implicit Forms [59]

[30].

by upon by

(2.5-15)

= h[f(Yn)

k2 k3

= h[f(Y,

1

+

= h [ f ( Y nf f

b,kJ b2

+ a2 4 Y n + + f

(2.5-16)

A(Yn + C 2

+

1

y' = f ( y ) . A ( y ) =f,

a,

= u2 =

= 0,

on

no

= hf(Yn)

= h[I

(2.5-16)

ki no k i + 2 ,. . . , k,. w,,. . . , w 3 ,a,, b,, a 2 , . . . ,

+

-

(2.5-15)

(2.5-16),

k,

k2

(2.5- 17)

:

by z' = 2, p = 3

a, 6, = c,

=

1 + ,/6/6 = 1.40824829,

=

{ -6

- J6 W,

a2 = 1

+ J58+ 20d'6}/(6 +

= -0.41315432,

=

- ./616 = 0.59175171 = 0.17378667

1.41315432

(2.5-18)

65

2.6. RungeKutta Formulas for Vector DE

u = 2, p = 2

u = 4, p = 3 u 2 = 1,

a,

a3=1,

b , = 1, b2 = +, b3 c1 = 1, c2 = Q d, =+, d 2 = F9 F5 fI 2e , = +, - 99

a,=+

= $q

cJ = e2 = g1 = 0 w, = ~ 1 9 - w,2 = -41 18,

U, = a,

w3

w 4 = -11 6

- 2

= 0.788675134,

b, = - 1.15470054, u =2

=9

W, =

c1 = 0,

3,

~2

=4

p =3

3.

A

ki. aij do

2.6. RUNGE-KUTTA FORMULAS FOR VECTOR DIFFERENTIAL EQUATIONS

on

m

= g(x,

y,

66

2.

Runge-Kutta and Allied Single-Step Methods

Y(X0) = Yo>

Y ' ( X 0 ) = Yo'

(2.6-2)

z(xo) = 20

(2.6-3)

= y'

2' =

f(x, z),

on (2.6-3). Y' = f ( 4Y , w) w' = b ( x , y , w)

y , w) =

y'

(2.6-4) (2.6-3).

=

(2.6-4)

(2.6-5)

on m = 2.

b

m (m 2 2) ~ ' l ' = f l ( x~, ~ 2 ' = f i ( x~,

1 ~ , 2 . ,. . , ~ m )

Ym' =fm(x, ~

1 ~ ,( 2 3

1~, 2

' ., . ) yrn)

(2.6-6)

. . . , yrn)

y

f.

2.7.

67

Two-step Runge-Kutta Formulas

m

2.7. TWO-STEP RUNGE-KUTTA FORMULAS

2.5 p

u

( x ~x,,+~). , As

to k

=2

121

by

by

on

upon n

U

4(Yn-1)

= W(Xn-1,

lz(yn-1) = h f ( X n - 1 /,(Yn-l)

+ u2h,

= hf(Xn-l

kl(Yn)= W ( X n

Yn-d + ulh, Y n - 1 + ull1)

3

+ ('2 - '3)'l

+ '3'2)

Yn)

k 2 ( ~ n )= W ( X n

+

k3(Yn)= W ( X n

+ u2

si = 0 u = 3, wi

Yn-1

Yn

u1

Yn

+ u1k1) + (.2

u2 u1

(p=

-4

kl

+ u3 k2) u3,

u2. u = 2,

I,

(p= u1 by

O(h3)

O(h4).

k,

68

2.

Runge-Kutta and Allied Single-Step Methods

u = 2, p

-

=

u3 =

-

-

=3

u 2 , ul

u1 # 0, u2 # 0, u1 # u 2 . u1 u l , u2

on bound “

u1 = u1 = 0.541, u2 = 0.722779927

”

0

p

=

3

p =4

(k >

by

2.8. LOCAL TRUNCATION ERROR ESTIMATES IN A SINGLE STEP

by T(x, h) h

T(x, h ) x,

x,+~;

2.9 x,

x, +

,

T(x, h).

2.8.1. Merson and Scraton Forms

T ( x , 17)

2.10 x,+~

69

2.8. Local Truncation Error Estimates in a Single Step

0 1 3

3

i

l 6

1

p=4

l 6

(p=

(u =

As

wi

a,,

c,

j n + ;l

Y,+~

by h

f ( x ,y)

good

- 9k3 + 8 k 4 - k51

T ( x , h) =

f ( x ,y )

[68] by 0 2 -

2 -

1 -

1 -

9

3 3 4

&

9

I

1 4 3 _2 4_

12 _6 9_ 128

128

2025

544 (x&)

* o

8 1

( 1 n 9k 1

3 2

2 5 0

+*k3

T(x, h ) = -(k4 x

u = 5, p = 4

210 __

128

- ‘$k2

- -&k4

+ sk3 - &k4)

2.8.2. Collatz Rule of Thumb [ 171

T ( x ,h) by

/7.

+ &+/i5)

70

2.

Runge-Kutta and Allied Single-Step Methods

k,

1

1

=

k,

1.0

h

h

1, h

1, h As

y)=

k, = k ,

f(x)

by ki. y' = ay

+b

by

As

2.8.3. Sarafyan Embedding Forms on

by (h) Y,,+~ Y l , n + l , y 2 , n + l , Y 3 , n + l > Yd,n+l,

ki. Y,,"+~ k , , , . . ,y 6 , n + 1 y , ,"+ p =1 y6,n+l p = 5 ( p = 5, u =

,

k,, y2,n+l k , , k , , k , ,k 4 y2,"+ p = 2

y4,n+l

Y6,n+l

k, k, . . . , y4,"+

y6,n+lr

k, . p =4

71

2.8. Local Truncation Error Estimates in a Single Step

up

up

j

h up

upon

O I

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

~

31 3

+I +

1 4

~ = 6 ,p = 5 2

1 1 0

~

n+ 1 28

2

&

125

O

625-625 5 4 378

625 546

n+ 1

0

3555125 336

336

336

= n+ 1

+ k,

=

ktki + 4 k 3

=

f

k4I [40, p. 21 11.

no on h

= 1

= Y,

~4,,,+ 1 =

+ k1

+k2 + + 2 k 2 + 2k, + k4I

(2.8-9)

72

2. Runge-Kutta and Allied Single-Step Methods

ki 1 0

upon

4.

1)

0<

upon

01

v

= 6,

ki =Yn n+ 1

+

= Y n - k~

+

0 1

1

-

1 -

2

4

-1 4

2

1

2

2

7

4 7

L + -_2_4_7 7

14) L!! 7

73

2.8. Local Truncation Error Estimates in a Single Step

= = yn = y,

+

Y2,n+l

+ 4k2

1

+ 32k3 + 12k4 + 32k5 +

=

+

= Yn

+ k2 2h

h. x, yn+l u = 6.

y4,n+l

h

[60] by

2.8.4. Fehlberg Embedding Forms (u = (u =

(u = (v =

-____.

0 1 16)

74

2. Runge-Kutta and Allied Single-Step Methods

h. 2.9. LOCAL TRUNCTION ERROR ESTIMATE IN TWO STEPS

2h

h

2.9.1. Extrapolation T(x, h).

5, (x,-,,

Y,-~)

(~,+~,y,+~) h (x,,

( x , , y,)

(x,,-,, Y,-~)

go

2h

y,,,)

go (x,,-,, Y , , - ~ ) h = x , + ~- x, = x, - x , - ~ . (x,,+~, y,+,)

= h' = x , + ~- x , - ~ .

T ( x , h) = 4hP+l

4 h: Y(xn+l)

-~

(nh )+ = l

h'

no y(x,+,)

h' = 2h

h

k

h' = kh

0

1.

4

75

2.9. Local Truncation Error Estimate in Two Steps

h.

1

p:

(y!,"+! - Y , " : ~ ) :

4

2

+

3 14

4

5

6

1 3 0 -L 62

126

bound on

h'

= 2h

2.9.2. Gorbunov-Shakhov Method

y, by

y,,

Y,,+~ T( x,h) = &'zP+' Y,+~

h p

yn*.

(-A)

(2.9-5)

y,* - y , = 24hp+l by

2,

y,. 1,

y.*

3 1

2

2.5. by

y,

yn+l y,+,

by (x,, y,)

4

(x,,,,

Y,+~)

- 4.

[29] T(x, h) = a+hP+'

(2.9-6)

a

jn+l

+a

-a.

yn+ 1 = X Y n +

1

+

Y=n+ 1 1

yn+l

(2.9-7)

76

2. Runge-Kutta and Allied Single-Step Methods

by

0 2 -

2

2

3

3

3

1 I 1 4 4

1 -

2 -

I 4

8

1 8

1 2

2

3 3-3-

-9

2-18-

0

4

4

-9

u = 4, p

=3

fc(

2.10. LOCAL TRUNCATION ERROR ESTIMATES IN MORE THAN TWO STEPS

[ 151

by

+ 9yll-1 - 18y, +

y,+l =

[ 161

+ 6yL-l +

O(h6).An by hyL-2 = 57,~,-, - 24y, y,+ 1 ,

+

+ 5 7 ~ +~ '

..., by 1.1

30T(x, h) = y n + 2+ 18Y,+i - 9 ~ -, ~OY,-I -

+ 6L

77

2.11. Local Round-Off Error in Single-Step Methods

T(x, h) x,+~

x,+ 2 . x,-~

x , + ~ x,+, .

x,,

x,

x,+~

x,+~ up by

to

x,+ . go h. 2.11. LOCAL ROUND-OFF ERROR IN SINGLE-STEP METHODS

= jj”

+ W x , , J,; 17) + en

e, y,

.

7,

upon

(IO(,, y , ; h ) = i r k l All

ki

+ 2k2 + 2k3 + k4] on

78

2. Runge-Kutta and Allied Single-Step Methods

ki

@

good

Yn+ 1 = Yn + ( h / 6 )Ck,

+ 2kZ + 2k3 + k41 ki

h/6

by h/6,

kis,

jn jn+l

h@(x,,, jn; h) As

2.12. THE EXPLICIT USE OF SINGLE-STEP FORMULAS

n y = y o , x = xo SINGLE-STEP COMPUTER ALGORITHM

by 1,2, . . . ,

=

h = hn

79

2.13. Modern Taylor Series Expansions

(1)

h, (3)

h

3).

h,, u

h, T(x, h) h, by bound ; by

h, .

As

2.13. MODERN TAYLOR SERIES EXPANSIONS

Y,+~

of y,

by

f ( x ,y )

by

80

2. Runge-Kutta and Allied Single-Step Methods

+ ha,-%> Y";

=Y,

p,

p

=

1,

.. . . y)

2.13.1. Error Bounds

1.11.2 >

Y n ;h ) -

9

Y(X,)

; h)

L

1

-

p Y,) -

5

9

-

bound on 1

h + 0,

hP

E,

y(0)= 1

Y'=Y,

bound

=

h,

E,,

~(x,)=

x, ,

x,

by

by

+ 1,

81

2.14. Published Numerical Results

2.13.2. Nonarithmetic Computer Operations on

.. . .

f(x, y),

As

on by

20

up. As

y). .... on

[53],

2.14. PUBLISHED NUMERICAL RESULTS

on

by [60].

82

2. Runge-Kutta and Allied Single-Step Methods

on [ 151

on

on y’ = y -

y(0) = 1

y(0) = 1

y’ =

h = 0.1

on 124,251

y” = -qJ 9

on y’

=y,

Y ( 0 ) = 1,

Y’(0) = 0

y ( 0 ) = 1.

h

on by

no

yl

= x(x

+

by

on

+ (x +

y(+) = Q

h

1. I 1.3.

83

2.15. Numerical Experiments

- x’)”’ h

+ 6 y = 0,

-

0.0125

y(0) =

y4,n+l

-4,

~ ‘ ( 0=)0 11

y6,n+1

x). As

y4,n+l

Y6,n+l

h

h. by

h

y ( 0 )= 1

y’ =

x < 0.1.

h

= 0.1,

h = 0.2, 0 = 4.66 > 1; h = 0.05, 0 = 0.4401 < 1. h < 0.1

0 = 1.2083 > 1 by

by

f ( x ,y )

64 upon

:

1.

2 . As h h 3. 2.15. NUMERICAL EXPERIMENTS

on

3.

2.3

I.

y ’ = --y

11. 111.

y ’ = +Y

Yo = 1 Yo = 1

y(x) =

y’ = u

Yo = 0

Y(X) = ( l / b ) ( P-

+ by

y(x) =

a = 1) =

I/Yz

Yz’= y” = - y

Y,’

=Y ,

Y2’ =

VI.

= y z o=

[I]

-Y1

y‘ = Ay

Yo=

1 y l ( x )=

x

x

y2(x) =

+ e-50x

yl(x) = y2(x) =

0 0

A=[

-50 70

+ e-12Ox

y 3 ( x )=

y’ = 1 - y*

Yo = 0

+1)

= (ezx -

y(x)

no

VIII. A Y,’ =

~

i

+

+

= ’

+

+ +

-

+

+

+O.O~Y~+~)Y~+~}/Z~,

YS’ = zi

-

+

=

Mi

yo =

+ + + o.o8~z)uZ/z6

[

+ 75,

[~:~~~

i = I , 2, .. . , 6

0.73576500 0.74875687

;

M

=

0.76774008

-0.1 1306320

0.77971 110 0.78383672 u1 = uz

= 0,

yo

(y = 0 ) .

IX. :

-(I yz’

=

+

E)yl O.S(exp E - 1)

E = 25yz/(yz

+

-

+

E-

-0.1111889 y z 0 = 0.0323358

85

2.15. Numerical Experiments

As

on

360150-67

2.3.

no

VIII I

11,

TABLE 2.4 EXACTSOLUTIONS FOR DIFFERENT SYSTEMS System I1

System I

0 0.2 0.4 0.6 0.8 1.o 2.5 5.0 7.5 10.0 15.0 20.0 25.0

System VII X

0 0.125 0.250 0.375 0.500 1.0 2.0 3.0 4.0 5.0 6.0

0 0.2 0.4 0.6 0.8

1.o 0.81 8731 0.670320 0.548812 0.449329 0.367879

1.o

1

3

0.45399910 - 4 0.30590210 - 6

2.5 5.0 7.5 10.0 15.0 20.0 25.0 System VI

0 0.2 0.4 0.6 0.8 1.O 2.0

2.0 0.98024 0.96079 0.94176 0.923 12 0.90484 0.81873

.o 0.4540010 - 4 0.2061 1 1 0 - 8 13 17

0.19287,o - 2 1 0.37201 1 0 - 4 3

Y(X>

0 0.124352 0.244919 0.358357 0.462117 0.761594 0.964027 0.995054 0.999329 0.999909 0.999987

86

2. Runge-Kutta and Allied Single-Step Methods

by on y,-y, y,

y,

2.4 11,

ci]

y,(x)] ; R y(x)

y(x)

Ri] y,(x)];

ciSP

yi(x) 2.15.1.

E~,,~]

(DP)].

of

2.5 11,

h

= 0.5

As

h,

x

11. E

= 25.0

= 0.231

x

= 25.0, yl(x) =

11

4 good by

h = 0.1

I1 1.0 h 5 0.1.

1.0

h

h.

on

3.10.

87

2.15. Numerical Experiments TABLE 2.5 DOUBLE PRECISION h = 0.5 R-K

R-K

R-K

I X

R

R

0 1.o 2.5 5.0 10.0 15.0 20.0 25.0

1.o 1.007841 1.019718 1.039824 1.081235 1.124294 1.169068 1.215626

1.o 0.9992085 0.9980225 0.9960488 0.9921132 0.9881932 0.9842887 0.9803996

0 1.0 2.5 5.0 10.0 15.0 20.0 25.0

1.o 1.003512 1.008804 1.017686 ’ 1.035685 1.054002 1.072644 1.091615

I1

1.o 1.000344 1.000861 1.001723 1.003449 1.005177 1.006909 1.008644

R 1.0 0.9999862 0.9999656 0.9999312 0.9998625 0.9997937 0.9997250 0.9996562 1.o 0.9999987 0.9999968 0.9999936 0.9999871 0.9999807 0.9999743 0.9999679

IV X

0

1.o 2.5 5.0 10.0 15.0 20.0 25.0

R2 1.o 1.00888 1.04048 1.15216 1.75982 3.89496 14.5637 126.009

R2 1.o 0.998311 0.995974 0.992600 0.987787 0.985528 0.985812 0.988649

h.

2. x

R, 1.o 1.00001 0.999919 0.999490 0.997586 0.994293 0.989622 0.983590

Rz 1.o 1.00005 1.00022 1.00079 1.00298 1.00658 1.01162 1.01811

88

2. Runge-Kutta and Allied Single-Step Methods

\

-10-

.. , \

Ralston third order, h=003125I

1

1

I

I

1

I

1

I

versus x .

Figure 2.1.

2.6

I/h x

=

1.0.

h) h) h

on

2.6. h, 2.7

2.8.

2.8 2.7

TABLE 2.6 SYSTEM I. SINGLE PRECISION ABSOLUTE ERRORVERSUS

FOR x = 1.0

1/ h

1 2 4 8 16 32 64 128

0.71210 - 2 0.291 1 0 - 3 0.14710 - 4 0.47710- 6

-4

-5

0.26210- 5 0.19010 - 5 0.41110 - 5

0. 0-5 0.10610 - 4

TABLE 2.7 SYSTEM V. SINGLE AND DOUBLE PRECISION WITH FOURTH-ORDER x = 0.5

x = 2.0

z

x = 6.0

h x

-

x

x

-

x

x

-

x

x-

x

x

-

x

x

-

x

90

2. Runge-Kutta and Allied Single-Step Methods

TABLE 2.8 SYSTEM x = 5.0

x = 10.0

h (e-.

- yDp)/e-X

0.5 0.25 0.125 0.10

-2

4 5

0.05

0.01

(e-x - ysP)/e-”

(cx - yDp)/e-”

-0.396693 10 - 2

874710 - 5 0.221 15310 5 0.93990010 - 5 0.70768910- 4

-

2

-0.90581710

5

(ecx - y s p ) / e - X - 0.79494010 - 2

10 - 4

0.44873810

5

-0.54293410 - 6

4

- 0.8371891, - 9

0.14551910 - 3

x.

x

x

y, y,

y,.

y3

2.9

y2 y3. y3

y,, y,,

h As

3

h.

h > 0.02.

1h=8 1h

do

2.10 x

y6

x

=

5.0

=

5.0

y6 do y l , . . . , y 5 . = 8.

I. /7.

91

2.15. Numerical Experiments

TABLE 2.9 SYSTEM VI. DOUBLE PRECISION

x El

h

25 50 75

8.7010-10 1.7710 -9 2.6610-9 3.5410 - 9 1 .0610 -9 8.7110-9 1.2910-8 1.7010-8

100

h = 0.005

h =0.01

25 50 75 100 25

8.08 10-9

1.7010-8 2.4910-8 3.2410 -8 1.701,-s 3.241o 8 4.62,- 8 5.8610 -8

50

h =0.02

Et

75 100 25 50 75 100

E3

-2.16,,-11 - 1.%lo-

-8.4710-10 -9.4610-10

11

-5.3210-12 -2.0310-12

-I.1510-11

-2.4410-

.%lo-

-1

If

- 3.7SI0- 1 4

9.6510 ' -6.4110-1' -4.7s10-15 -2.6710 - 2 0

-9.6510- 17 -6.411 0 - 10 -4.7810-15 -2.6710 - 2 0

-

- 1.3310-25

-1.3310-25

-3.3410-13 -9.3s10-24

- 3.3410-13

-9.3s10-24 - 1.98l0- 3 4 -3.71 1 ~ - 4 5

-1.9810-34

-3.71 10-45

I/h = 128. one function evaluation 2.07 =

(u = (u = =

6.21 8.28 12.42 14.49 2.10

2.5,

12

-3.%lo - 9 - 1.3010- 3.7510-14

-3.3510-9

17.

W

h,

t 4

2.10 y6

2 4 8 16 32 64 128

-0.02373383

-0.02374239

-0.02374220

-0.02374 1 05

-0.02374309 - 0.02374454

- 0.02373745

-0.02373829

-0.02373595

-0.02374147

1

-0.02373922

-0,02373504

0.02373456 l / h = 128 7.02

a -0.02373675

-0.02373990

- 0.02374192

-

P)

- 0.02374044 -0.02373964

- 0.02374359

in 7.03 a

-0.02373045

P

x = 5.0

-0.02374067

-0.02373324

-0.024039 18

11.11

12.78

-0.02373270 -0.02372888

8.28

8.47

11.16

z &

2 =

2.15.

93

Numerical Experiments

1/h

1. always below 2.

h

z’,

H

= 2h/c

(2.15-10)

H H

= 2h/3, = 2 h / 4 ,

= 2h/6

4.

H

IjH I/H

h). At

1 IH

on

3.

I 0.50 0.552 0.651

IV

I1

0.525 0.564 0.651

0.45 1.08 1.31 10

100

thefifrh-order method is to be preferred as long as high accuracy is desired.

do (2.3-17), (2.3-28)

(2.3-20),

(2.3-25)

(2.3-27), (2.3-32).

3,

upon I,

As

94

2. Runge-Kutta and Allied Single-Step Methods

As

y,+l=

h2 2

[

1)

h3 6

y(x) =

h4 24

h5 120

h 6 ]y 640 "

- x),

2.11

are by

the

to use. A by

4.3

4.8 5.1 on

2.12

on Also

100

2.

ROCumiloo steps,

no

360

TABLE 2.11 R1 R2

SYSTEM

N L

VI

h=0.01

h=0.1

1 .o

1.o 1.o

1.o 1

.o

1 .o

1.0 1

1.0046 0.99193

0.99944 1.0033

R1 RZ

1.o 1.o

1.o

1.0090 1.0173

0.99980 1.0330

R1

1 .o

1 .o 1.o

1 .o 1.o

1 .o

0.31795 4.0619

R1

0.99985

0.41171 3.0080

~=0.5

1 0.99955

0.99999 0.99995

0.99990 0.99976

0.99988 0.99749

x = 10.0

1.0082 0.99073

0.99758

1.0137 0.98295

1.1313 0.85916

x=0.5

~=0.5

x = 10.0

h=0.5

1.o 1.0

1.o 1

1

1.0

..

1.o

R2

R2

i;’

c

!?

-8

k. B

Rl R2

TABLE 2.12 SYSTEM I. h = 0.1.

AND

FOR

DIFFERENT METHODS )

SP

0.99999

0.99999 5

DP

1.o

1 .o 14

x = 10.0

SP

0.99999 4.5951 0 - 5

0.99999

1.o 9.36010 - 6

1.o

0.99672

0.99993 8.96310 - 6

1.0962 9.26710

1.0

1.0962 9.26610 - 2

0.99993 8.081 10-6

0.99994 1.17410- 5

0.99993

1.o 5.9311 0 - 1 5

1.o

1.o 3.74710 - 6

h =0.1 X 0.2 0.4 0.6 0.8 1.o

RO/step (SP) 7 -4.768 10

RO/step (DP) '6

- 8.74310 -

- 5.96010 - 7 - 5.96010 - 7

15

-

1.0016

0.99672 5

- 15

2

1.0016 4.45910 - 2 1.19152 2

1.19159 1

2.15.

97

Numerical Experiments

2.15.2. Use of Implicit Single-Step Methods 2.5. 10).

2.13,

2.13

h = 0.5 R X

0 1 .o 2.5 5.0 10.0 15.0 20.0 25.0

System I

System I1

1.o 1 1.0230 1.0466 1.0954 1.1464 1.1999 1.2558

1.o 1.0618 1.1618 1.3498 1.8219 2.4593 3.3196 4.4808

:

System IV 1.o 1.0089 1.1015 1.6048 8.6738 3

1.406610+ 4

h

11,

= 0.5.

2.5 good 2.14 on by

no

stability

on 11,

on

98

2. Runge-Kutta and Allied Single-Step Methods 2.14

h = 0. X

0.2 0.4 0.6 0.8 1.o

1.00002 1.00004 1,00006 1.00008 1.00010

0.2 0.4 0.6 0.8 1.o

1.00002 1 1.00006 1.00008 1.00010

11

1.0330,o - 10

7 6

2.503310 - 6 2.443710- 6

k,.

k,’s 2.15 good

11. h

2.5,

As

1.16

I1 100

0.651

up

1.16

100

0.86

TABLE 2.15 SYSTEM I AND 11. BUTCHER IMPLICIT METHOD System 11 x = 1.0

X

h=0.5

1.0 2.5 5.0 10.0 15.0 20.0

x

x = 1.0

= 10.0

X

EDP

ESP

x = 10.0

ESP

EDP

__

0.143010 - 5 0.7748 0 - 6 0.1 19210- 6 0.165810- 8 0.1560,,

-

6

0. 160710- 6 0.216510 - 8 10

12

1.0 2.5 5.0 10.0 15.0 20.0

2

0.104210+ 1 0.231010 + 3

0.12281,, - 3 0.299310 - 2 0.8884 0.197710+ 3 5

100

2. Runge-Kutta and AUied Single-Step Methods

2.15.3. Truncation Error Estimates 2.8

2.9

h,

All : 1.

T(x,

h

2.

T(x, h ) = 3.

2h

2.9.1.

- y;Z:1]/30.

2h

2.16 2

ci

on

Ti As

by by

h

on y= y4,n+l

y, =

y, = Y , , ~ + ~

y,

h

y, h

y,

y, h = 0.01

y 10- 14.

2.1 1 y,

.

h y,

= 0.1, x = 0.5

h

= 0.1, x =

10.0,

x = 0.5

TABLE 2.16 DOUBLE PRECISION. ESTIMATE OF TRUNCATION ERROR IV X

h =0.01

h = 0.1

0.2 0.5 1 .o

0.5 1.o 3.0 5.0

0.5 1.o 0.2 0.5 1.0 3.0 5.0

102

2.

Runge-Kutta and Allied Single-Step Methods 2.17

System IV Y

X

h = 0.01

0.1

Y4

1.

1.1051709 9.04837421p - 1

1.1051709 9.048374210- I

1.6487213 6.065306610- I

1.6487213

1.6487213

2.7182818 1

2.71 82818 3.6787944 10-

1

1

4.4816891 2.231301

1

1

0.5 1.0 1.5

2.0

4.4816891 7.3890561

0.6

1

1.o 2.0

2.71 828 18 1

4.481 6891

7.3890561

1.8221 188

1

1

7.3890561 1

I

h = 0.1

Y6

1.8221173 5.4881 1971,

1.8221 1

1

2.7182818 3.6787944 I 0 - 1

2.7182797 3 .678795610- 1

2.7182817

7.3890561

7.3890541

7.3890596 1.3513350710 - 1

1

1

5.0

610+ 2 6.737947010 - 3

1.484138510 + 2 6.737897610 - 3

1.4841396,, + 2 6.737891910- 3

10.0

2.2026466,0 + 4

2.202699410+ 4

2.2027010

5

5

5

I

1

I

I

1

+

4

VII h=0.01

0.2 0.6 1 .o 1.6 2.0 0.2 0.6 1 .o 2.0 3.0

1

7.615941610 - 1 9.21 66855 10- 1

1

1

1

1 1

I 1

1

5.370495710- I 7.61 59416,0 - 1 I

5.3704913 1 0 -

1

1

1

1

9.640271 3 10 - 1

1

1

9.95054671, - I

103

References

y,

h = 0.1, x

=

2.1 1, 1.710-1,

1 .710-s, 6.110-9

10.0

VII y,

h = 0.1, x

= 3.0

210-8

2.15.4. Recommendations

h,

4

REFERENCES in

1.

2. 3.

York, 1966. Comm. ACM 9, 626

W.

Simulation 11,

A

219 4.

A

J . Assoc. Comput. Much. 13, 495

J.

5.

Austral. Math. SOC.3, 185 6. J. C . , 203 7. J. 179 8. C., 9. Comp. 18, 233 10. J. 408 11. G . D. J . Assoc. Comput. Mach. 13, 114

A.

J . Austral. Math. SOC.3, J . Austral. Math. SOC.4,

Math. Comp. 18, 50

on

Math. Math. Comp. 19,

104

and Allied

2.

12.

Comrn. A C M 10, 102

13. Proc. IEEE 56, 744 SIAM J. Numer.

14. Anal. 3, 598 F. 15.

1966. 16.

S ., AFIPS Cony. Proc. 32, 467

17. 1960. E. J., Comput. J. 10, 195

18. 19.

Math. Comp. 18, 664

A

20.

y” = f ( x ) y +g(x), Comput. J. 7 , 314

21. B I T 6 , 181

22. 23.

IBM J. Res. Develop. 6 , 336 24. NASA Technical Report,

25.

NASA

Technical Report, J., 26.

Math. Comput. 20, 392

by

27. SIAM Rev. 6 , 134

28. Comput. J. 3, 108 Y. A.,

29.

U.S.S.R. Comput. Math. and Math. Phys. 3, 239

ibid., 4,427

30. Comput. J. 12, 183

31. 1962. P. “ York, 1962.

32. 33.

1956. 34.

by 35.

Comm. ACM 11, 814 L.,

306 36. Comm. ACM 9, 108

Math. Comp. 18,

105

References 37. SIAM Rev. 9, 647 38.

Math. Comp. 20, 386

39. SIAM J. Numer. Anal. 4, 607 Z.,

40. 41.

1955. Chiffres 2, 21

du (1

42. 1967. 43. SZAM J . Numer. Anal. 3 , 593

44. SIAM J. Numer. Anal. 4, 620 D., SIAM J. Numer. Anal. 4, 372 H. 46. (1 47. 45.

48.

SIAM Rev. 8, 374 Math. Comp. 22, 434

A., SIAM Rev. 7 , 551

49. Comput. J . 11, 305

50.

Simulation 12, 87

H.

51.

Proceedings

of Symposium on Data Processing, 52.

J.

P., 4.

1967.

53. 1966.

V. S., on

54.

by U.S.S.R. Comp. Math. and Math. Phys. 5 ,

608 55. Comm. A C M 6 , 491 56.

Math. Comp. 16, 431

S.,

57.

by

NASA Technical

Report,

58. 59.

NASA Technical Note,

S., H. Comput. J. 5 , 329

60. 61. 62.

E.,

SIAM Rev. 9, 417 Datamation, 12, 32 14

106

2. Runge-Kutta and Allied Single-Step Methods

63. 15 64. 18

65. 29 66.

BIT7, 156 67. Comput. J . 6 , 368

68. Comput. J . 7 , 246

by

69. Comp. 20,21

70. MTAC 12, 269 Comput. J. 10, 417

71. 72.

ZBM J. Res. Develop. 2, 340

73. Comm. A C M 9 , 293

74.

C., 22, 71

Quart. Appl. Math.

3 Stability of Multistep and Runge-Kutta Methods

n

3.1. LINEAR MULTISTEP METHODS

y

y’

do on

108

3. Stability of Multistep and Runge-Kutta Methods

Y n + l = 'lYn

+ ." + ' k Y n - k + l + h[POyA+l -t " '

-k

PkyA-k+ll

(Po = #

predicted on corrected (3.1-1)

Y,,+~ yn+

yL+l

4.

p(5) =

-rk

+

p(E)Yn-k+l

y;+,, y,,',

on

"'

@k

by Ekyn=y,,+k,

E,

J J , , + ~ ,y,,

+ +

+ ha(E)yL-k+l

, . . . , Y ; + ~y,,', , ...

=O

by Y , + ~ y, n , . . .

...

y(x).

Pi

xi

y(x),

O(hp+') k

&=O

i=O

:

1. 2. 3. p

Po p(4)

a(<)

(q, no

-

109

3.2. Numerical Stability of Linear Multistep Methods

2

o(t)

p(5)

by

concergent yo = Y(X), h-0 nh-rx

x E [a, 61

h-0

y,

y,(h) = y o ,

i = 0, 1,2, . . . , k - 1 = 0,

consistency,

y,

y(x), y(x)

by

3.2. NUMERICAL STABILITY OF LINEAR MULTISTEP METHODS

y, y(x,)

y , - y(x,),

1.

by by

2.

An k -1

110

Stability of Multistep and Runge-Kutta Methods

3.

n, E, , E,

=

-

y(x,)

+ WE)f(xn

p(E)y(xn)

by

> ~ ( x n ))

on y

n -k

T n == 0

+1

n

Tn = T ( x , , h) P(E)Y, + W E ) f ( x , > Y J

+

vfl

=0

q,, Y,,~ y,

p(E>IIyn - ~(xn)l+ W E > [ f ( x n yn) 1

Y,) - f ( x , 5 j 5 y(x,,) f(xn

y,

3

p(E)En

E,

E,,

, ...,

7

T n

-f(xn

dxn)) =fp(xn

j)

7

+ )I,

=0

YXY, - Y(x,>) by 1,

+ ho(E)I,c, + r, + q, = 0

by

R, , T, ,

q,,

n. E,

As

x.

n

111

3.2. Numerical Stability of Linear Multistep Methods

, T,,,

n.

).

, T,,

T,

y~.

y~.

n

g,,

p(E)s,

+ MG(E)E,,+ T + q = 0

A

[Ek

+

Uk-1 Ek- 1

+

+ ao]E,, = b

" *

a,, ... ,

n.

k pk

+ ak- 1pk-' +

+a,=O

* * *

k

As

+ c2 p2' +

= Clpln

..., c k

pkfl

by

+ c2n + + ~

=

+ ck

m,

pl, E,,,

* * '

+ +

+

, - ~ n ~ - c,pmn ~ ) p ~... ~

C k p c

1 a,,

..., a k - l p1 = v R

+ iv,

p2 =

-

r 2 = vR2 + vI2

1

8=

E,,

=

clrn

nO

+ c2 r"

nO

+ c 3 pjn +

* *

. -+ ck p /

by Enp

=

+

ak-1

+

"'

+ ao)

1 rn

E,+k

+

Ak-1Efl+k-1

+

"'

+

AoE,

=b

112

3. Stability of Multistep and Runge-Kutta Methods

G(E)E,= b,

G

x

G(p) = 0

G

m

p

x

m

{b[I

Ecij(pp)'+

&in=

16)

j = 1 1=1

G(p),

+

Ak-1

+ + AO]-'}i

i = 1, 2, ...,

PbC) + W P ) = 0

1

k En

cnh

- ( T + q)

+ Enp

1

by

cnP

+

= Ell,

ak-1

b=

+ + uo) *..

E,

+ E t a i + h n z t pi).

by n

E,

n

E , ~

ci

E~~

on

k

c0,

. . ., & k - l .

k

go E,,

y,. Yn = d i p i n

+

+ + dkp;

d2 ~ 2 "

* * *

di

on

y o , . . . ,yk-,,

di

ci

by

y' = l y , y(xo) = 1,

A

y(x) =

p,,

+ O(hP+')

p1 = ehA

1)

1 I3

3.2. Numerical Stability of Linear Multistep Methods

h + 0.

principal root, pln

k-1

spurious, parasitic,

extraneous roots k no

y' = Ay,

y(x,) =

d2 p2" + * *

lpll

> I p J , i = 2, 3, . . . , k ,

- + dkp / ,

n

dlpl,". /pil > lpll

i, p:

plfl,

no

pi

no

lpll > I p J , i = 2,3,

. ..,k. E,,

E,

i=

lpil 5

n. 2, . .. , k.

A Ipil s i = 1, 2, . Ipil 5 l p l l , i = 2, 3,

Absolurely stable Relatively stable

lpll i 1, i =

3, ..., k . y'

= Ay

. ., k

.. . , k

2,

. . . ,k ,

(plI < Ipil

inherently stable x,,

s

i

= 2,

< 0. x,.

x,,

2 0, Ipil 5 1,

no p:,

do

114

3. Stability of Multistep and Runge-Kutta Methods

y’ = f ( x , y ) ,

An = 1, = pn

on

hA

p(E)

A

h

lhll

Ipil = 1

lp,l

a(E). hi

>1 i=

1

2

0

Xh

n4

h >0

00,

< 0.

=

h -+ 0.

h -,0,

h

h.

h 3 0. h n -+

p(E)&,

--f

0

co.

+T+q =0

n -+ co.

En

k Ipil 5 1,

=

= C1’/lln

p(p) = 0

+

C2’pLn

+

+

Ck’p;

p(p) = 0

2, . . . , k,

lpil

>1

n -+ co.

i,

h +0

a

(1)

p(p) = 0

on

on p(p) = 0

ID,( 5

1 . Con-

3.2. Numerical Stability of Linear Multistep Methods

on weakZy stable.

by

[5].

by vi

on

+

p i ( h i ) = pi(h -+O)evlhrl ~ ( h ' )

pi(h +

pi(hi) p(p) = 0

=

1, v, = 1.

vi

on y' = Ay,yo = 1, by Yn+1 = Yn-1

p2 - 2hAp

p1

=hi

P2

=-

+

- 1 =0

+ +(

h y y

pl

pl = 1

+ o(h4)

+ LI +

p l = ehA- +(hA)3

+ o(h4)

by yn = d l ~ , "+ d2 ~

2 "

p1n = e'nh[ 1 - & n / i 3 i 3 +

. . .]

p2" = (- l)"e-A"h[l+ +nh313

dl

=

I - d2

+

y, = erlXX" - &i3x,erlXnh2 d 2 e"*

+ . . .]

yo = 1)

+ d2(

- l)ne-'xn

by

116

3. Stability of Multistep and Runge-Kutta Methods

p2.

y , # p,

d2 # 0.

< 0. y, .

h + 0, +1.

v2

=

- 1,

n,

h = 0,

y’ =

Ay. no /I + 0, IZ+

co, h, ,

h

n + 03,

3.3. DAHLQUIST STABILITY THEOREMS

p

Theorem 3.3.1. p = 2k, k + 2 . k odd,

k

k

p

Theorem 3.3.2. An Theorem 3.3.3. p = 2, k = 1.

+ 1.

a

k

117

3.3. Dahlquist Stability Theorems

A A((x)-stable,(x E (0, h>0

n -+ co

< a,

S, = { z :

S, (x

E

zf O}

3.1. A 3.3.2

(0,

2

= Ay

A(&)-

no

3.3.3

\

Absolutely stoble

S,

Unstable

h

/ Unstable

hh

Figure 3.1.

1.

3.3.6.

S,.

on Theorem 3.3.4. Theorem 3.3.5. Theorem 3.3.6. k = p =3

a

p 2k r E

k = p =4.

+ 1,

118

3. Stability of Multistep and Runge-Kutta Methods

3.4)

no

(3.1-1).

3.4. STABILITY OF MULTISTEP METHODS IN INTEGRATING COUPLED ODEs

do

(3.1-1) An by

(3.1-1).

on y' = Iy. (1.6-7)

y' = 2y, yn + 1 = p1 = 1

+ A,.

2

I, >0 I, <0

(3.4-1)

+ hA I 1 +hIl

=I,

+"bn 3.2.

s

(3.4-2)

1

I I 8 > 01 < 01.

I,

= 0,

8

I,

by

= Xe",

= 7[/2 =2

0

I, =

0.

119

3.4. Stability of Multistep Methods

+I

+I

Backward Euler

0

c

PI

Trapezoidal rule

-I

-I

-2 0

-2 5

-I 5

-05

-I 0

0

h i

Figure 3.2. = 1,

+ il,

A = Xeie

A.

(3.4-2) 11

+ hXeie]2 1

(3.4-3) (3.4-4)

I

I, =0

0 = 0,

bound

(3.4-3)

hI 2 - 2 .

(3.4-4)

8,

(3.4-3)

hX

3.3, hX 3.3

(3.4-4). 3.4

p =1

hl

[lo-14,27, 281

by

on ”

“

by

3.4.

eAX

3.3

120

3. Stability of Multistep and Runge-Kutta Methods 30

Figure 3.3.

3.

2.

-x -r E

H

1.1

3

Figure 3.4. 1-5.

121

3.4. Stability of Multistep Methods

1

pin

pi = ewihn = e w i x ,

wi

pi)//?.

wi.

pi,

"

"

w,

A

hw

hw

hw = hw,

hjl

+ ihw, hw,

hjl. hi" = hd, + i h l , , hw, hiL,

3.5

by

U = hw, V = hw,. U = 0,

by

on

U

A hi., - hA, U =0

U-V

h

3.4 i= 3.5. -0.25.. h = 0.10

hi. =

Y

-10

-08

+ 4i 3.5 I7 = 0.05

hw

+

-06

3.5.

-04

-02

=

hw =

h = 0.15

0

Gurk [14].

2

+ +

122

3.

Stability of Multistep and Runge-Kutta Methods

2.19i

hAR - hA,

U-V

on U =0

= Y"

+

y' = Ay

- hi)

=

Yn+l

- hA)-'. < 0, lpll

3.2

(1.6-20).

y'

=l

1.

y 1 ++hi

Yn+i

3.2

= ___ Y n

1- t h A

< 0.

1

lpll

3.3.3

by =

=

A

nij.

10)

=

y1

y,

.

Al

A2,

yl(x) = clule'lx

+ c2 ulelZX + c2 u2 e l z x

y z ( x ) = c11i2ellX

123

3.4. Stability of Multistep Methods

u = (ul,

v

u,)

u2)

= (u,,

c2

h by

+ 1)

1

=

+1 = by

In

+1 (I +

= (1

+

1

=

by =I

+

+

2.

+ -+ .

.

= 1,

+

Yln+l = Y2,+,

+

=Y L+

+ az2Yz") by

Y,"

YZn= upn

= up",

+

- p)u/h

a12u = a Z l u+ a Z 2v =

allu

- p)u/h

- p ) / h = -1, u

p =1

v

+ h1

1

124

3. Stability of Multistep and Runge-Kutta Methods

y," = y," = C l U 2 ( l

v,, c 2 , u,

u

(I + hA)

M(hA) (1

+ 2,h)"

1)

+ 112 h)" < 0,

+ I , h)" + h)"

+ Il,h)" + + +

nh)

< 0, (1

+ A,h( <

11

+ I,hl

<1

h by

l i h+ 0, <

yn+, = (I - +hA)-'(I

+ +hA)y,

M(hA) = (I - +hA)-'(I

Y l n + l = Yl,,

Y2"+l

= Y2,

+ 4hA)

+ (~/2",lY,"+,

+ a , 2 Y 2 , , + , )+ ( a I l Y 1 " +

+

+ a 2 2 4 ( 2 , + , ) + (a21Yln +

y l , = up"

y,,, = cp" a,,u+a,,v=

az,u

21-p

hl+p

U

+ a Z 2v = - h __ U l+p -

125

3.4. Stability of Multistep Methods

p

=

+ +hi+)/( 1 - fhA)

+

1

1 +hA, 1-

+

< 0, by

h --t 0,

A when used to integrate a coupled set of linear ODES the stability of the method depends only on the eigenvalues of A.

on

A

on y= = =

A = AZ

Ai.

A =

=p

126

3. Stability of Multistep and Runge-Kutta Methods

A

M(PAP-'h)

M(B) =

(

i= 1

=P

f

biBi)-'( i =

1

B =PAP-'

i= 1

i= 1

= PM(A)P-'

M(Ah) z M(Ah) M is pl, i

pl(hAi)z

[M(Ah)]" fl+

Ai

2,

. . ., m

=0

m

1pi(hii)l <

y' = Aiy, So

=

i=

2 , . . ., rn

on

As

akYn+k + ' % - 1 Y n + k - l

+ ". + a O Y n

+

= hA(Pkyn+k

+ POYn)

127

3.4. Stability of Multistep Methods

k. by

m =2

by

km m

by p i j , i = 1 , 2 ; j = 1, 2, ..., k .

2k k

by p l l eA2h

y. ellh

p, j

p1

,

= 2,

k.

. . ., k . Pll

pZl,

... , k

C,, = clul, D,,= c, u,, CZ1= q u , ,

j = 2, 3,

(2k

= 2).

PZl

D,, = c2 v 2 .

Ipijl I 1, i = 1, 2 ;j = 1, 2, . . . , Ipu,,J 2 Ipljl Ip21l 2 1 ~ 2 ~ 1 ,

= by on h

A

on

A.

k

C(aiI + hPiA)yn+i = 0

i=O

k

C(aiI i=O

+ h p i A ) ~ n +=i 0

128

3. Stability of Multistep and Runge-Kutta Methods

E,

z,+~ = Ez,,

k

1(ail + ~~,A)E’z, =o

i=O

2k k

i=O

by a i

pi,

on hAj,

j = 1, 2. 3.5. STABILITY OF INTEGRATION OF NONLINEAR ODEs

y’ = f(x, y). (y, , x,)

n Y’ =

+ [ f y I n ( ~ - YJ+ O(h2)

li, = 1,2, . . ., m

[f,],

y’ = f(x, y)

h.

(h

.

--f

5.1.1.

on

. h. f t

3.6. Stability of Runge-Kutta Methods

3.6. STABILITY OF RUNGEKUTTA METHODS

3.6.1. Explicit Runge-Kutta Methods 2.3.

y' = Ay,

2.3, y' =

f f l= Ay, , k , = hAy,,

k,

yn+1 =

p1

=

= hA(y,

+ k,) = hA(yfl+ Myn),

+ h l + $h2R2)y, 1 + hl

+ $hZA2 p =2

3.4. hl > Y , , + ~= pl(hA)yn,

p1 = 1

+ /?A +

+h21"2

I)

3.4.

+#3l3

130

3. Stability of Multistep and RungeKutta Methods

pl = 1

+ hi, + +h2A2 + +h3A3 + &h4A4

3.4

p

p 54

=v =

= 5,

u = 6,

a,

ai 2.3.5.

u6

2.3.5 by

IhAl < 1, Ihi,( > 1

(hi,)6

p = 5,

IhAl > 1. a6 3.4

3.1, 3.6

Unstable

30-

x

E 20-

H

-50

-4

0

-3 0

-20

-I

0

Re ( h i )

Figure 3.6.

hX

(2.3-30) [ZO].

0

131

3.6. Stability of Runge-Kutta Methods

a6

=0

a6

3.1,

bound

h. 3.6.2. Implicit Runge-Kutta Methods go by

If rn

ajxj

= j=O

=

2

bo = 1

j=O

n(X) =

rn

f(x).

+ n. 1. 2.

,(x)

=

rn

+n

x = 0. m

= j=O

F,,,

m

x = 0.

+n + 1

-

=

m

[(f 0

c j x j ) ( 0i b j x J ) -

+n + 1

fu j x j ] / i b j x j 0

0

on x.

(f 0

0

-

0

aid=

djxi m+n+ 1

c W p3

THEORETICAL STABILITY LIMITS FOR Method

1)

Order

Rek)

TABLE 3.1 DIFFERENT EXPLICIT RUNGE-KUTTA METHODS, q = hX Characteristic root

Im(q)

2 2 2

1

3 3 3

1 + q +aq2

4 4 4

1

+ q -t aq2 + :q3 + +4q4

1

+ q + : q z + f q 3 + 2zq4 + 2 0 4 5 ;

w

+ q + is2 + :q3

=0

=

=

same as

= =0

same as same as 5 6

=

- 1 SO

=

= 0.5625 1 + q + +q2 + fq3 + &&q4+ &0q5

+ &q6;

=

3.6. Stability of Runge-Kutta Methods

133

0

x

c)

-1;s +

-

N

I1

E

Y

.iN

+

-T

I

N

Y

r d

+Y

T

N

II

E

I

J:?

3

I1

E

31-

-

-Y

0

I1

N

+Y -

E

-I 0

I1 9

-

d

PI

I1

I1

I

9

II

P

II 9

134

Stability of Multistep and Runge-Kutta Methods

3.

P,,,(x)

As

Q,(x), fl

...,

C~,,,+,-~-~b~=0, 0

<

cj

b, = 1

a , = C ~ , - ~ b ~ , r = O , 1,..., m 0

bj=O,

m

ex

e-x.

=3

n

j>n

3.2

ex

= 4. A

rn

rn

n,

Yfl+l = Y ,

+

k , = hf(x,, + fh, Y ,

rn

=n

~

1 + +hA 1 - +hA Yfl

x,

+

k,. y' = Ay, = Yfl

+

k1 = h2(yn k, = h i ( y ,

+ +

+v

2

+ +

-

k,

+

+ $k,) k,

+

1 +hl = 1- +hi +

+1

rn + n

1

+

y' = l y =

=n

Yfl

135

3.6. Stability of Runge-Kutta Methods

lpll

<1

< 0.

< 0.

<1 :

by 3.2

<0 n

n.

3.2

n = 1, nz

=0

=0

2.5.

n = 1, m = 2

n

=

1, m = 3 y’ = Ay by

We F,,,(hA) E

F,,,(hA)

( 1bj(hA)’) (ir$hA)i)

= i”,

F,,”(hA)

-

= M(hA)

136

3. Stability of Multistep and Runge-Kutta Methods

by

by

h 4

on hA on

3.10

3.6.3. Semi-Implicit Runge-Kutta Methods 2.5.4

” = 1+

1 -

-

+ (+ > 0,

3.7.

on

Also

’’

=

11 - 1.578hl+ 0.622h212

137

3.7. Stability of Single-Step Methods

I

Stoble t 6

-*I-

-I

-8

Re (hN

Figure 3.7.

y‘ = Ay. J J , , + ~=

[I - fhA

+ +h2A2 - &h3A3]-’[I + +hA + $h2A2 + &h3A3]~, O(h5).

70 x 70.

A y n + l = [I

-

+hA

+ &h2A2]-1[I + fhA + &h2A2]yn

O(h5)

do A

3.7. STABILITY OF SINGLE-STEP METHODS EMPLOYING SECOND DERIVATIVES

l’n+l

+h2yOl’;:+l

+alyn+h~lyn’+h2y,y~

138

3. Stability of Multistep and Runge-Kutta Methods

by

3.3.3 uI = 1,

Po, y o ,

y1

r

Y,+

1

= Y, -

1

i= 1

on up

1 =

+

Y?’)

r = 2. r = 3.

r = 1,

+ P,hA +

1 - Po hA - yo h2A2

i = 1, 2, . . . , m, by

hAi -+ 0

p.

p = 3,

+ PI = 1 + Po + Y o = 3 Po

Yo =

=

1

+ (1 - P,)hA +

- Po)

- 3Po)h2A2

1 - Po h l - (+ - + P o ) h 2 A 2

p = 2.

y1 = 0,

Po, ?’”+ 1 =

Yfl

+ I 0 0 L+I + ( 1 - P0)Yfl’l + h2(+ - Po)Y:+

1

139

3.7. Stability of Single-Step Methods

Do

Do = 3, pl

p = 3.

3.8

i o

-I

-60

-20

-3 0

-10

0

t20

+6 0

+I 0

t30

+I

i 0

-I

hX

[23].

Figure 3.8.

hA. hA 2 6.

Do

= -$,

p =3

n = 2, m = 1

n

m = 1.

Do p, hX = 0,

+1

hX = 2/(2P0 -

-1

hX = 1

J [ 1 - 4/(2&

-

12)

140

3. Stability of Multistep and Runge-Kutta Methods

$ 2 13,

23, jpll>

-

0 < hX <

Po = +. pl 3.8.

p = 3,

13,

=

1+

pl

by

by r

Yn+i

= YE

+ iX= Y1i r ' i [ ( - l )

i+ 1~ [i] n + l I

yir

2r

r. 3.8. STABILITY VERSUS ACCURACY

A h ]MI

no

h h

by

h h on

by

pl

by

w i=

As hw,-hw, (U- V

hi.,-hR,

by

141

3.8. Stability Versus Accuracy

To on

[hi.[< 0.1.

h

no

2, ..., m. sujjicient

lhll,l I 1, i = 2,

< 0.

i = 1,

. . . ,177, necessary

1. JhlLil< 0.1

i

2. ]hlLilI 1, i = 1, 2,

. . .. m.

by [21]. JJ,’ = -

-

-

= = 4.0010

=

y , = 0.0005e-3X -

+ 4e-0.3X

y, =

50.0005. h 5 0.333,

2. As

2,

=

x>0 2, = -0.3 0.3h < 0.1,

h < 0.333 = 2,

,12

=

14

= s e - 3 s - 3e-0.3‘ = 10e-3” + 4e-0.3“

(3.8-3)

142

3.

Stability of Multistep and Runge-Kutta Methods

h < 0.0333, =

-3

no by

h on 6. by on on

A

on

u(t) j ( s ) / U ( s ) = G(s). z-

s=

j ( z ) / i ( z )= G’(z) G(s) z = eihn

C’(z) 0.

by

-

G(iR)l/lG(iR)l.

hl, hw,

hw, by

/I

3.9. PUBLISHED NUMERICAL RESULTS

on 0.999

-1

/d,

3.10.

143

Numerical Experiments

0.9991.

y(0) =

on

h on by

bound

h by

3.10. NUMERICAL EXPERIMENTS

2.15,

no bound on

h.

3.1

on h l

As

+

by

h

2.

h,

hA

bound on h. 3.10.1. Preliminaries

2 1. System I. =-

3.1 2. System IV. = -1 I,, =

1.

+ 1. A,,,= i

3. System V. 3.1.

3.1.

144

3.

Stability of Multistep and Runge-Kutta Methods

4. System = - 120.

A3

on h

5. System

3.1

by

3.5

fy

=

3.1

4.

by

3.10.2. Explicit Methods h

by

by 3.3. h

=

h = 2.5,

1.0

on TABLE 3.3 STABILITY BOUNDSFOR SYSTEMS I AND V I h = 1.0

h = 2.5

R I .63 2.68 12.9

X ~

5.0 10.0 25.0

R

X

__

2.5 5.0 7.5 10.0 15.0 20.0 50.0

V

xX

12.0 21.0 30.0 50.0

h = 3.0

h = 1.0

__ 6.0

-1 0

x

-

2.34

1

- 16.48

0.15

45.64 245.4

145

3.10. Numerical Experiments

h = 1.0

/i =

3.0. h

by

bound /I

h,

on 3.3 h

3.1 on bound 3.2

y’ = - y

1.6

3.4. 1.7. h = 2.0.

/z = 1.0

upon y’ = - y 5.7

3.4 /I, =

h=

= 0.028

h=

= 0.0475.

3.4 h = 0.025, h = 0.04

h = 0.1

3.10.3. Implicit Methods

1, 11, VT, 3.5 2.18 2.19

I, 11, 3.6 1

11

h

no by

R2

= 2.5

146

3.

Stability of Multistep and Runge-Kutta Methods

TABLE 3.5 DOUBLE PRECISION. ROSENBROCK THIRD-ORDER METHOD 11, h = 2.5

h = 2.5 Y

R

R

&

2.5 5 7.5 10.0 12.5 15.0 17.5 20.0 22.5 25.0

~

IV, h = 2.5

1.380 1.904

&

6.748 -

3.627 - 5.005 6.908

17.5

s

- 1.1 8210 + 2

3

01 1

2.073 + 3 - 5.38710 + 3

2.50510+ 1

4

&

15.0

*

P

1

R

&

1.168 1

.017 1

1.002

i;'

c

VII, h = 1

VII, h = 2.5

2.5 5.0 7.5 10.0 12.5

w 1

R

148

3. Stability of Multistep and Runge-Kutta Methods

h

h

=

1.0

h=

= 2.5

h

= 2.5.

h

h. TABLE 3.6 SYSTEM I. DOUBLE PRECISION BUTCHER IMPLICITMETHOD E,

X

-

h = 2.0

8,

h = 4.0

8,

h = 6.0

2.0 4.0 6.0 8.0 10.0 12.0 14.0 16.0 18.0 20.0 22.0 24.0

h

h = 2.0, 4.0, h = 2.0 on h = 6.0,

h = 4.0,

3.7

Po = 1. b.

3.6

6.0

3.7.

3.10.

149

Numerical Experiments

3.7

E ~ h , = 2.0

X

0.51831,- 3 O.I3O2,01 -0.178310-1 -0.642910-2 0.366210-1 -O.Z688,,-1 -0.25501 0 - 1 0.603710-1 -0.235410-1 -0.5421 10- 1 0.256910-1 0.535010-1 -0.1590 0.2443 0.2537

2.0 4.0 6.0 8.0 10.0 12.0 14.0

16.0 18.0 20.0 30.0 40.0 50.0 60.0 66.0

y n , ynp1,

ynfl

E

~ h , = 4.0

€2,

h = 6.0

-

0.2745 -

-0.4310 -

0.3952lo-1 -

0.9459 -0.196910+ 1 -0.5832,0+1 -0.1091 I 0 + 2 -

Y:+~, y l ,

As do

3.5 go up.

h

= 0.1

no

3.8 h = 0.1, X

0.5 I .o I .5

2.0 3.0 4.0 5.0 6.0 7.0

0.2985$ 0- 2 0.8507,o -2 0.134110-1 0.143310-1 0.241410- 2 0.320710-1 0.389610-1 0.211610-~ I 0.517910-

0.3658104 0.397510-4 0.510310-5 0.914310-4 0.267410-3 0.202410-3 0.172210-3 3 0.5269100.4232103

c2

150

3. Stability of Multistep and Runge-Kutta Methods

on

11 =

0.01, 0.1, 0.5, 1.0, 2.0,

5.0.

/I

1. by

2. h

/z

h

Simulation,

1. 11, 219, 1968.

2.

J. Math. and Phys. 44, I 3. Proc. IE€€ (Letters) 55, 2016 4. Math. Scand. 4, 33

5. Proc. Symposia in Applied Mathematics 15, 147 6.

BIT 3 , 27

E.

7.

Comput. J . 10, 195 8.

AIChE J. 14, 946

9. E.’s, BIT 8, 276 ( I 10.

Quart. Appl. Math. 12, 133

1

by 12.

J . Assoc. Comput. Mach. 1, 5

J., 13, 87

13. Gurk, 6 , 58 14. Quart. Appl. Math. 13, 73 15.

1962. 16.

P.,

York, 1963.

151

References 17. 18.

1964. B., ‘‘

York,

1956.

L. G . ,

19.

22. 1967.

20.

five SIAM J . Numer. Anal. 3 , 593

21. NASA Technical Report, 22. NASA Technical Note, 23. NASA Technical Note, 24. Comput. J . 11, 305 ‘‘

25. 1958. 26.

1966.

J. Assoc. Comput. Mach. 1,

27. 186 28.

D.

G.

pp.

York, 1962.

York,

29. 1963. 30. 31.

Comput. J., 10,417 0. 65

A

on

BIT 7 ,

4 Predictor-Corrector Methods

: Yn+l

+ a2Yn-I + + akYn+l-k + h [ P o A + 1 + P l Y n ' + ... +

=a1Yn

* * *

Po = 0

(1.7-1)

Po # 0. by yn+l ;

Y,+~

h h

al,

. . . , ak, Po

... , P k

h P-C

152

1.7.5

153

4.1. A Simple Predictor-Corrector Set

4.1 1

y

y’.

y 4.10

y”, y”, . . . .

4.1. A SIMPLE PREDICTOR-CORRECTOR SET

:

y,+ 1 = y,-

~ , += l

Y,

1

+

+

qx,

+ Y:],

A) =

?.(x.,h ) =

=

lW,

> IW, 41, (k =

(k = by

.

y,, yz , . . , y ,

Y,+~.

by = f ( ~ , , + ~p,+l). ,

j,,,;

Y,+~ Y,+~,

y;+,,

ynf2.

predicted Y , + ~ corrected

evaluation, jA+l,

Y,+~ by Y;+~ ecaluated.

Y,+~

on

Tn

y’

154

4. Predictor-Corrector Methods

Y,+~,

by Y , * + ~ ,

by

Y,+~

by

y,+,

Y,,+~.

by s

j,,+

yn+,

4.8.

1.

good

ynfl

Y,,-~

y,,’

do go on 2.

4.3 h Y,,+~.

y,

3.

f,+,)

by

do Y,,+~, j,+l) Y,+~) P-C x.

4.

yo

y,.

155

4.2. A Modified Predictor-Corrector Set

xo ,

yo

4.2. A MODIFIED PREDICTOR-CORRECTOR SET

by

<

= Tfl+l,P= = T n , 1,

xn < 5c < xn+1

=

= 7n+1

+

=

-

+ Y,+

1

=

-

-

+

1=

=!

-

by

x,+,,

y 1)

=

< i<

=

only

j7,+l

by 1

-

1

= =

3

(0

$K+

=

Y , + ~- j n + l

4.13

<

h on

156

4. Predictor-Corrector Methods

Tn+1, p = 4(Yn + 1 - Yn + 1)

Tn+

1, p

= %n+

1

- Yn+

1)

= 4(Yn

- Yn) by

$(yn -

pn)

Yn+l Tn+l,c=

-+(Yn+I

-

mn+,,pn+l,

c,+~

by on no ;

As fn

+

157

4.3. Convergence of Iterations in the Corrector

2

O(h3)]

3

O(h4)]. y = x3

by c,+, = y(x,+,) - Y , , + ~

y

= x3].

by

4.1

4.3. CONVERGENCE OF ITERATIONS IN THE CORRECTOR

Y,,+~ yn+

on

by w,.

LHS

Y,+l

- hBof(x,+,>

Yn+J - w,

=0

Y,,+~. :

4.3.1. Jacobi Iteration

by Y ! Z l l ) - hPof(x,+,, Y21)

-

w,

=0

158

4. Predictor-Corrector Methods

[31].

Y+:

1

Y,*+~

- hPof(x,+

- Y,*,

YS+ll)

Y Z l l ) - Y,*+

1

1

=

=

- wn = 0

1 , Y,*+l)

WO(f2

1

hbO[fYIY(Y%

- f:+

1

- Y,*,

bound on f,, , IlfJ

y,*+ I yI ys;'!,.

IlY%+11) - Y,T+ 1 I/ 5 hP0 L

IlY?++ll)

1)

- Y:+

1

I I Y 2 1 - Y+: 1 II

/I 5 ( h P 0 LY+

l l Y 2 l - Y,*,

1

II

A IhPoLI < 1

f,,,

on fy, L

L,

hPol4naxl < 1

bound

11,,,,1 is

on h,

h

h x.

hPo 1A,,,1

= 0.1. 1.6.1,

1.2,

= 2,

3, q =4, 4

=

hL < J$hL < + hL <=g 2 5 1

< L,

159

4.3. Convergence of Iterations in the Corrector

yn+i = Y n - 1

+

+ <3 rn

-

< 1, (s

I

(S)

- ~ (s+ n +1)iI

+

(s+l)

(1 - ~ B ~ L ) I Y , * + ~ 5

hPoif%

+

Y,+~.

=

-

-

4.3.2. Accelerated Iteration A +.)y~~~)-hBof(xn+,,y~!,)-~,-ccy~!,=O C!

C!

= 0,

by (1 + u)Y,*+1 - hBof(xn+

C!

1,

Y,*+ 1) - wn - “Y,*+

1

=0

= 0.

by

of

1,

160

4. Predictor-Corrector Methods

by

c1

4.3.3. Newton-Raphson Iteration

on

f,,+l

Y,,+~

by y;++;)

= Y,,+ (s) 1

+ [I - kPo A!;

1

1]-'[kflof??

-

f,

A?il

~ $ 21 + w,,] y?!'.

4.3.1

ll[I

-

~ P o ~ ? ! l l ~ 'II(Wy)[I li

- hPoA?!llI/

IY?;/)

4.3.2

-

Y,!?,l/

51

As II[I - ~ f l o ~ ? ? l l - l l l= 1 II(d/ay)[I - kPo A?!

k<

11H

6107

kPo

lly?,?:) - y$!ll\ on

h

6 0.1. Anfl A?! y,,. yn+'

by

yn h

A,,+1

4.3.4. Backward Iteration on

161

4.3. Convergence of Iterations in the Corrector

Y?!I

Y?!

1

=

- Y+:

hPof(xn+l,

1

=

Y??:)) + w n

(S+l) hfio[fn+ 1

-f*

]

n+ i (s+l) = hBo[fyly[~n+ 1

YX+

11

~ ~ / ~ P o ~ l l r f y l -
lower bound on h

bound

A f,

4.3.5. Summary

on

1A,,,,,1

h

bound on 17 bound.

1.

A 10,

2.

A 10, h

on

162

4. Predictor-Corrector Methods

4.4. ACCURACY AND STABILITY FOR SOME SIMPLE PREDICTOR-CORRECTOR METHODS

by Yn+ 1

= Yn

Yn+ t

=

~n

+ hyn‘ +

1

+~ n ’ l

if the cor-

by rector is used only once.

4.4.1. Truncation Error Considerations

y’ = Ay

L

p, = 1

+ hl.

p1

0

h’1’ 2

h2i2 2

p, = 1 +hi+-+-

p I = 1 + h/!

1

h3i3 4 h3Eb3

2

h’i.’ ++ __ + h4A4 2 4 8 ~

3

163

4.4. Accuracy and Stability

y' = Ay

by

h2A2 h3A3 h4A4 eh' = 1 + hA + - - - ... 6 24 2

+

+

+

by ,ul - eh',

- h2A2/2

0

- h3A3/6

h3A3/12 h3A3/12

(4.1-2) P-C

(4.1-1) Y n + l =Yn-, Yn+ 1

yn+l = ( 1

= Yn

2 3

+ 2hA~n

+ (h/2)CAJn+ + A ~ n l 1

+ (hA/2)+ h2A2)yn+ (hA/2)ynp1

- h3A3/6

,u2

+ hA

1,313112

- hA/2

0 1

h3A3/12

- hA/2

2

A

4.4.2. Stability Considerations

on

(4.4-7)

164

4. Predictor-Corrector Methods

An on

on

by by

-2 < hA < 0.

bound

s

-2
s=O, 1,2,3

by

Y?++?

= Y”

+

1

+

s

P1=

1+

-

1by 1

+ h42

=ix@ s-+

co,

< 2. y,!?,!,’)

y?!

by P-C

1

165

4.4. Accuracy and Stability

3.4, by

+ h i + h 2 i 2 / 2+ O(h4) pz = -(1 - h i + h2i2/2) 4- O(h4) pl = 1

p1

> 0, p l

p2

< 0, p l

p2

by

p2

< 0.

> 0, 4.4.1

<

< 0. do do

4.4.3. Increasing the Stability Bounds

bound bound

[46] y,+, Y n + l = ~,Y,+,(s =

+

- dY,+,(s =

0 _<

aI

_< 1.

xl,

4.1 a1 = 3.4 a1 = a1 =

hi >

bound

As a, = =1

s =2

yn +

bound by

by P-C

166

4.

Predictor-Corrector Methods

Unstable

20I

r< c

H

10 +To

(-51,O) Stable

0 -40

-30

-2 0

-I

0

0

ReihX)

Figure 4.1. Euler (P) and trapezoidal rule (C) stability bounds.

4.1

bound

4.5. MILNE PREDICTOR-CORRECTOR FORMS

[35].

(k = (1.8-7) =Yn-3 + (4h/3) c2Y:,-Y;-l T(.u,h) = (2Sh5/90)y[51(~)

= !‘n

-1

+

+ 4Yn’ +

T ( x , 11) = good l d . As

167

4.5. Milne Predictor-Corrector Forms

4.2

by :

pn+ = Y I%+ 1 =

c,+

~

+-(4h/3)[2yn’ ~

+ 2y;-,]

-

Pn+ 1 - (28/29)(Pfl - 4

(4.5-3)

,= y,- + (h/3)[mA+ + 4yn‘ + yA- ,]

yn+, =

+(1/29)(~,+~ - c n + J

4.5.1. Milne Corrector (4.5-2)

y’ = Ay (4.5-4) p1

p2.

h + 0, p2-1=0

pl =

+ 1, p2 =

- 1. (4.5-4)

p l z e +h l ,

by

p 2 r e- h l / 3

(4.5-6)

p2

> 0, p,

(4.5-6) )p21 < 1. p2

p2

no

< 0, p1 bound. ptl

hi.

[36] 4.2

bt2

[19] 4.3, 4.4

[7] by

0

by 4.2

hA.

a. hl

no

-2.01

-2.0

- 1.0

- 0

\

t 1.0

t 2.0

hX

4.2.

W.

(4.5-5) Journalofthe ACM, Volume 6, pp.

hh.

0 1959,

t2 0

+ I 0

-5 A

0

a 0 x 3.

-I 0 .

-2 0 -30

-2 0

-I 0

0

+I0

hX

Figure 4.3. Journalof the A C M , Volume 6 , pp.

0 1959,

t20

t 30

169

4.5. Milne Predictor-Corrector Forms

hX

Figure 4.4. Journaloffhe A C M , Volume 9, pp. 457-468;

0 1962,

4.5.2. Milne Predictor-Corrector Combination y'

= 1.y

(4.5-7) y n - 3 ( k = 3).

yn+l

4.5

x

< 171 < - 0.3

/71,
/7 -+

pl =

0 4.5.

+ 1,

p 2 = - 1,

p 3 = p4 = 0,

170

4. Predictor-Corrector Methods

-24

-20

-16

-12

-08

-04

0

to4

to8

t12

+I6

f20

hX

E.

Figure 4.5. Journal ofrhe ACM, Volume 9, pp.

1962,

03I

x c

Unstable

02H

0

I-

I

0

/ih

Figure 4.6.

W.

Volume 12, pp.

;

8 1965,

P-C Journal of the A C M ,

171

4.5. Milne Predictor-Corrector Forms

1p1 = 1

1p1 =

lehAl

bound

4.6

< hL <

4.6

bound

no

4.5.3. Modifled Milne P-C Combinations 4.7

hi,

by

1.8 (WITH MODlFlC 1.6

I.4

1.2

10 i 0.0

04

02 -hA

Figure 4.7.

Journal of rlie A C M , Volume 9, pp. 457-468;

0 1962,

172

4. Predictor-Corrector Methods


bound no

hl

4.5.4. Increased Stability by Averaging

Y,+l,

Y,,+~,

Y,,+~.

Y,+, y,+, = Y , - ~+

As

by

by

h.

+ 3 ~ "+'

+

4.5.5. Hermite Predictor and Milne Corrector up As As by

ifthe corrector is not iterated. Yn+ 1

=

+ 5 ~ " - + h(4~n'+

1)

y' = l y

Y,+1

+ 4(

- h n ) ~, (5

+ 2h1)~,,- 1 = 0

173

4.5. Milne Predictor-Corrector Forms

h -+ 0, p l =

+1

pz =

on

y'

+

Yn+l

=

Yn+ 1

=Yn-

1

+ 2yA-J

+

+ (h/3)CYA+ 1 +

+ YL- 1 1

= Ay

Y,,

- 1) y ,

+ ( W 3 ) C Y n + 1 + 4yn + ~ n - 1 1

- +h2jV2yn - (1

+

p , = +{4hzlL2 [J$l?"A" p2 = 3{$hzA2 - [J$h4i4

As h + O , p1 -+ 1

+ ( 5 + 2/?A)Yn- 1

Yn+ 1 = Yn+l = Y n - 1

+ 2h1. + + h 2 i 2 ) y n + +

1

=0

+ 2hA + + 2hi. +-+h2i2)]"2}

p 2 -+ - 1,

pl

hA,

p2

1.0 < hA < 0

/?A.

Unstable

05

Stable

0

Figure 4.8. Juunrol o f / / i e A C M , Volume 14, pp. 351-362; 1967,

174

4. Predictor-Corrector Methods

4.8.

bound

-

1.0 <

hi. < 0 no on

4.6. HAMMING PREDICTOR-CORRECTOR SET

do

Yn+ 1

T(x,

=

Yn-3

+

=

- YA- 1

+

1

+

=

Yn+ I =

- Y n - 2 1 -t

-

T ( x ,h ) =

4.6.1. Hamming Corrector on

J’n+ 1

=

+ nZ

l’n-

1

+ % 3L ’ n - 2

f h[aO

YA+ 1 +

$- P 2

YA- 1 1 (p=

175

4.6. Hamming Predictor-Corrector Set

-9

a1 = a2

= a2

c(3

=

po = PI =

4

>

- a,), T ( x ,h ) =

- a2)

+ 7a2) f

83

+5~~)h~y[~’([)/360 x2 = 1

x2

h =0 8p3 -

+

- a2)p2 pl = 1

- C I ~= )

p2

p3

4.9

a2.

a,

< a2 < 1.0 a2 =

0

1, &, $, 0,

-3,-2-

al, a 3 , ..

-A.

. , pz

h = 0. a2 a2 = 0

I

PI

\ -I 0

j -05 -06

I

0

fO 5

+I 0

a2

Figure 4.9. W.

(4.6-6) Journalof the A C M , Volume 6 , pp.

az.

0 1959,

176

4. Predictor-Corrector Methods

-08

-I 6

-24

0

to8

t16

t24

hX

Figure 4.10. Roots of iterated Hamming corrector. [Adapted and reprinted from P. E. Chase, Journal of rhe ACM, Volume 9, pp. 457-468; copyright 0 1962, Association for Computing Machinery, Inc.]

rx2

=0

(4.6-2)

h 15 %) (az = 0 )

h # 0.

by

0,

by x ,

0

by

4.10 (4.6-7) 4.4 -2.6 < h l < 0.

4.6.2. Hamming Predictor-Corrector Combination (4.6-1)

(4.6-2) on

-0.5 < h l < 0

h = 0.

4.12)

do

4.6.

Hamming Predictor-Corrector Set

177

< h l < 0. (4.6-3) by

+

p5(121) -t p4(-126 112(hl)2) + p3(54hl 168(h1)2) + p2(14 - 24hl - 168(l11)~)+ p( - 9 - 42hl + 112(h1)2) + 42hl = 0 (4.6-8) 4.2). [32]

(k = 5 ) by = Y n 4-

Yn-3

Y n + l = ikC126Yn

- Yn-4

4-$h[2Yi - 3YL-i - 14yn-2 + 9 ~ n - 3

3YA-2 - 2YA-31

+ h(42jA+ + 1 0 8 ~-~ 5’ 4 ~ 4 - + 24.~;-2)] 1

(4.6-9)

1

(4.6-3). (4.6-8) 4.11.

(4.6-911,

hl

Figure 4.11. Roots of Hamming modified P-C combination. [Adapted and reprinted from P. E. Chase, Journal of the A C M , Volume 9, pp. 4 5 7 4 6 8 ; copyright 01962, AssociaComputing Machinery, Inc.] tion

178

4.

Predictor-Corrector Methods

< h l < 0.

4.12

by by 4.7 4.13, 4.6,

As

< h l < 0,

< h l < 0, < h l < 0. As

O4 0

2

0

04

00

S 12

16

20

, 1

- hA Figure 4.12. Journalof the A C M , Volume 9, pp. 4 5 7 4 6 8 ;

0 1962,

179

4.6. Hamming Predictor-Corrector Set

Unstable E

H

05-

0 -2 0

I

-10

-I 5

-05

0

Re (hX)

hX

Figure 4.13.

L.

0 1965,

ACM, Volume 12, pp. 227-241 ;

4.6.3. Extensions

by by

W.

Journal ofthe

180

4. Predictor-Corrector Methods

by bound

>

h2 >

bound (v = 4)

0

(u =

2.352

0 0 5 0 -18 9 10 0 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1 0 0 1.547 - 1.867 2.017 112 112 0 417 317 0 0 0 0 1 0

k k k

=3

k k

=7

=4 =5

=8

3 k =4 k =5 k =6

k =2 k k

=4

=5

k =7

0 918 1 1 1 1 1 1 1

0 1

1 0 0 0 0 0 0 0 0

0

0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0

1 1.442

1 2 4 9 813 312 19011720 427711440 198,721160,480 434,2411120,960 2.002 1 103142 22,32117440 62,249117280

0 3 813 0 51 - 591 371 - 27741 26161 99821 705,5491 - 1,162,1691 2,183,8771 1.818 -991 691 - 881 611 24,2161 101,4301 5,615,1991

113

413 618

112

11 81

-118

0 0 0 0 0 0 0

0 0 2 18 - 413 - 11

113 - 318 0 - 11 - 51

25 11720 47511440

191 6461 14271

36,7991120,960

139,8491

- 121,7971

- 2641 - 7981

181

4.7. Adams Predictor-Corrector Set

do

4.7. ADAMS PREDICTOR-CORRECTOR SET

(A-M) 4.1 4. PREDICTORS‘

0 0 0 0

- 12741 -72981

- 171 -1.51

0 19,0871 295,7671

- 134,4721 - 1,041,7231

(1

’

0

yc

- 36,7991

(1

.4016h

0

- 120341 - 764901

yC6’

0 28871 407,1391 2,102,2431 0 0 0 30,5451 3,444,8491

0 164,1171

- 50791 - 1,149,0481

1,691h ‘180,640)y[’

0

CORRECTORS 8 3

P4

P 5

P7

P6

W ,h )

0 0

y[” 931

0

yL4’

0

1061 4821 37,5041 123,1331

- 191 - 1731

are the same as the first one

0 271 63121 41,4991

that

0

-

0

1,3511

y[*’

182

4. Predictor-Corrector Methods

=

=

by

A-M) y' = Ay

(1

-

(

111) yn+ 1 - 1

+

;

h A) yn

5hl + 24 yn

-1

hl

- 2 yn- 2 k

p3

+ A(hl)pZ + B(/IA)p + C ( h l ) = 0

=0 =

183

4.7. Adams Predictor-Corrector Set

A(hl>, . . . , C(hl)

h +0

hl. =0

(p pl = 1, p2 = p3 = 0.

1

h (p -

= 0.

=0

on h = 0. no

h

h 4.7.1. Third-Order Adams P-C Combination ( p =3)

by y' = Ay.

::

(

p - l+-hlp

+

(t:)

5 -hlp--hhl=O 12

hA

144

by

hl 12

-

80 25 +h212 p - - h2A2 = 0 144 144

4.14,

< h l < 0,

< h l < 0,

- 1.8 < hA < 0.

P-C

- 1.6 < h l

< 0.

4.14

184

4. Predictor-Corrector Methods

15

10

4 c

E

H

05

0

-

-I 5

-I

0

-0 5

0

R e (hX)

Figure 4.14. Region of stability in complex hX plane for third-order Adams P-C combination.

4.7.2. Fourth-Order Adams P-C Combination

(

- 1+-hA

p

)p 3 + -2459h A p 2 - - h A2437p + - h A =2409

hA (1 - - h294A ) ’ (1 + -iz) p--

(5hA 24

CL+-+-

-

(

p - 1+-+h2A2p

7:A

)

5hi + -+-

5 hA p2+-hAp--=0

24

24

59h2A2)p2 64

(-24hA + 6437

- h2A’)p

9h2A2 +--0 64

-+-

95h2A2)p - (hi. 64 24

91h2A2)p2 64

9h2A2 -0 +-45h2A2 64 P - - 64 C, PECE

PE(CE)2

185

4.7. Adams Predictor-Corrector Set

-20

0

-I 0

+I0

Figure 4.15. Mathematics

of Computation;

0 1965, Volume 19, pp.

et al.

4.15

4.16

0, 0,

x.

< hA < 0,

< hA < 0,

< hA < 0

- 1.3 < hA

< 0,

et al.

-2 0

0

-I 0

+I0

hX

Figure 4.16. Mathematics Compzctarion;

0 1965, Volume 19, pp.

186

4. Predictor-Corrector Methods

5 h < \ D

&

\

10-

05-

,

--,---;-

" -30

-20

I

I

-I

0

ijl 0

hX

+I0

[12].

Figure 4.17.

< h2 < 0.

bound

4.17

by 4.18,

2 0-

-

4.19,

Unstable

4

L=

E

H

IOStable

0

by

187

4.7. Adam Predictor-Corrector Set

-

1

x

E

H

0 5-

n -

1

-20

--

I

5

-I 0

-05

0

Re (hi)

hX

Figure 4.19.

Journal o f t h e A C M , Volume 13,

0 1966,

pp. 374-385;

i

4.7.3. Higher-Order Adams P-C Combinations 4.20

4.21 4.2

by

188

4.

Predictor-Corrector Methods

Figure 4.20.

hX Journal of the ACM, Volume 13, pp. 374-385;

0 1966,

Unstable

I I

-I 5

Figure 4.21.

hh Journal of the A C M , Volume 13,

pp. 374-385;

0 1966,

189

4.7. A d a m Predictor-Corrector Set

STABILITY

TABLE 4.2 BOUNDSOF ADAMSFORMS

~~

Real

stability

p

-6.0 -3.0 -1.8 -1.2

-1.5 -0.92 -0.68 -0.49 -0.35 -0.25

-1.3 -0.95 -0.7 -0.5

-0.5

1.3i 0.9i 0.7i 0.5%

0.4i 0.3i

4.7.4. Crane-Klopfenstein P-C Combination by go

181 4,7.5.

hA

go

bound bound

hl

hl. = - 1.3

=

4.22 jn+ 1 =

-

-1

-

+ 2.0 +

-2 -

-3

-

190

4. Predictor-Corrector Methods

- 4.0

- 3.0

-2.0 Re ( h i )

-1.0

0

hh

Figure 4.22.

L. Journal of the ACM,

hi

0 1965,

12, pp.

hi = bound

=

on 4.22 4.19.

bound

hl

= 0.70i

4.7.5. Krogh P-C Combination

go by

y,.

yn-l

4.1

4.23 4.3

hi -

0.3i,

1.3

P-C

= - 1.8,

191

4.7. Adams Predictor-Corrector Set 15

IC

c x

I

E

H

05

C

-

-1 5

-I 0

-0.5

0

Re ( h i )

hX

Figure 4.23.

F.

Journal of rhe ACM, Volume 13,

0 1966,

pp.

4.7.6. Nordsieck Method

y,, y,,’, y”, . . . , Yn,Yn-t%Yn-2,* . . .

xn

by

4.7.7. Hull Combinations

a,

pi; pz =

p3 = -c,

192

4. Predictor-Corrector Methods

p 2 = +c

p3 = -c p2 =

p3 = = 0.

=

+ 5c2 + + + - +

+

+ (-

=y,

+

c2yn-1

+ (19c2 +

- c2yn-2

+

-

c2yn-2

+

+

- 5)yA +

+

+

As

+

-c

+

- 5)yA-I

+ (-5c2 + + -c +

by

+ (5c2 + 8)

= ( 1 - c ) ~ n + ( ~ - c ~ ) ~ n - 1+ c 2 y n - 2

+ +

+

+ 1

c=

c=

T ( x ,h ) =

4.7.8. Extensions

4.4.3

Yn+ 1

= yn

+

- YA-

11

T(x, h) = y‘ = Ay bound < h l < 0.

-

1.0 < h l <

bound

Y,,+~ =

yoYn+,(P)

+

-

0I yo I

1.0.

y o = 1.0,

y o = 0, yo = 0.65

193

4.8. PE(CE)‘ Versus P(EC)’ Combinations

bound

- 5.7

< hA < 0

Y,,,~

h.

2h (4.7-20)

T ( x , h ) = 2 [ ( 5 l 1 ~ / 1 2 ) y [ ~=~ ( i ) ] 2h. T ( x ,h ) =

=

by

bound

bound

-

on

4.8. PEKE)” VERSUS P(ECY COMBINATIONS

yA+l Y,,+~ jJL+,}

s = 1,

{Y”+~,

{ J J ” + ~ y;,,} ,

2h

Y,,+~ s=I

h.

194

4. Predictor-Corrector Methods

bound.

do ?

y’ = Ay)

Yn+ 1

= Yn

y,

+

1

= yn-l

+

+

jn+l

by j,+l

=

+ = J’, + = Y,

p5

- (1

-

+

+y ) 4

+ 37j’A-z +

15

91

+ 24p 3 - 24 - i1J.p + - hi,p - - = 0 8 8

O(k5) =

1,

4.8.

195

PE(CE)” Versus P(J3C)s Combinations

h =

on

4.19 bound

- 1.3 < hA

< 0.

4.24.

<

bound

1

c x 1

O2

E l

O L 0

Unstable!

1 _-

-0 3

R e (hX)

Figure 4.24.

P(EC)

hh

0 1968, Volume 22,

Mathematics of Computation;

pp. 557-564.1

hA < 0

- 1.3 < h i

<0

bound 4.24, 4.19.

by

196

4. Predictor-Corrector Methods

4.7.4. -

jnil =

+

+

+

+

+

+ 4.25

As hl =

hA =

by

Also

Unstable

R e (hX)

hX

Figure 4.25. P(EC)

Marhernarics of Compurarion; Volume 22, pp. 557-564.1

4.26 4.5

4.27

4.12. As bound

bound < hA < 0. bound

0 1968,

197

4.8. PE(CE)' Versus P(EC)' Combinations

0

- 1.0

-0.5

0

to 5

+I0

+0.5

+ 1.0

hX

Figure 4.26.

-I 0

- 0.5 Figure 4.27. Roots

0 hX

198

4.

Predictor-Corrector Methods

4.9. SPECIAL SECOND-ORDER DIFFERENTIAL EQUATIONS

Y” =f ( x ,v> y’

by

y,,+

- ynP3

=

T ( x ,11)

+

+

+

+

+

=

by yn+l =

- yn-l

+

q x ,/ I )

= -

up Y,“ = p n + l=

Yn)

+

-

cnil

= 2yn - y n - l

Yn+1

=

+ yi-] +

+

+

+ toy,” + y i p 1 ] -

Cn+J

4.10. USE OF HIGHER-ORDER DERIVATIVE P-C COMBINATIONS

y’

=f(x, y )

1.10,

(k = j,l+ T ( x ,/ I )

= =

+

+ (2h2/3)[2y;+

4.11.

199

Hybrid Type Methods

As Yn+l

+ Yn’l +

= Y,+

+

T ( x ,11) =

[j,: -

no

no Ail. y”.

jn+ =

Y , ~ +1 =

+

1

+ YA-

- Y,-

11 + ( 2 h / 7 ) [ A + +

-

11

1

+

j;+

As h + 0 7p2 - 8p + 1 = 0 pl = 1

p2 =

1

h

by

y”

4.11. HYBRID TYPE METHODS

p, uI, .. . , a k , P o ,

3.3.1 p I k + 2. 2k

.. . , P k ; p = 2k

[17], p

= 2k

P-C

+1

200

4. Predictor-Corrector Methods

f ( x ,y )

between xn

x,+~;

4.11.1. The Butcher Approach by

+ '2Yn-1 + + C l k Y n + l - k + h[fiO f n + 1 + f i l f n + ' + P k f n +

Y n + l = 'lYn

' * *

* '

h f i f + l - O .p 2k + 3 p = 2k + 2. 2k + 1. As

1- k l

+ hfifn+

1-0

by 8 # 0, 1, 2, . . . , k . 8

3

3

on ~(y,+~-~

p

8

= 2k

+2

fn+l-O, -o.

M

=

-

1 1 K = --+0

Hi = H i - 1 +

- 8) ... ( k

- 0)/k!}'

1 + ... +-

+-k -18

i 2 1,

Ho = 0

(4.

4.11.

6=

k

= 4,

k

As

h =0 k = 8, no

6 = 3.

5 , 6,

y,+l =Y,,

20 1

Hybrid Type Methods

=

1, Q

=

+

k

=

1, 2, 3,

3, +A1

+

0(h5).

p =4

h/2

Y,,+~

y,, yfl+l,2 k =2

+ 2 = 4,

=k

k

=2

3.3.3,

h. f,+

-0.

do Tfl+i-e = E

+

+

i ~ n E2yn-i

+

+

* * *

+M2Yn-1 + +

Y n + l ='IYn

+

Tfl+,- e

+ &Yn+l-k

. * *

+ B k f , + 1- k l

+ MkYn+l-k + ... + Tn+l-e "'

ffl+l-e

f,+l.

JJ,+~

2k

2k p = 2k - 1 p = 2k p = 2k - 1

do

;

f,,+

j n +I ;

+1

do = Yfl +

Tfl+

= Y, ~

n 1+ = ~n

+ h[2Tfl+ +

1

+

1/2

+ fnI

k=l, JG+ l j 2 = Y f l -

Yn+ Y,+

= 1

=

+ w 3 ) r 9 f f l+ 3

,] + (k/15)[32Tfl+

-

~ 1~-

Yfl-

k=2,

+

112

p=5

-

+

-

+ 12fn - f,(4.1

202

4. Predictor-Corrector Methods

=

zz

Yn+l

=

+

+

+

+ -

+

+

-

1

-

+

-

+

-

-

-

-

%=+,

4.28 bound - 1.45 < hA

< -0.1.

hX

P-C

Figure 4.28.

P-C :

k 2 5 1

3 2 6

4.11.

203

Hybrid Type Methods

As

4.11.2. Different Predictors A

+2

p = 2k

by

8

2k

+

k 5 6.

6

+3

fn+l

p

pfl+l

-B

on

2k y) 2k

= 2k

+3

+ 2.

jn+

ffl+l.

f f l +-B

h-

p,+,

+

= 4 5

+

= --3TYfl+ Yn+l

=

j,+l =

+ +

=

+ =

+ k

= 2,

1,

+

+

+

+ +

+ffll

Q = 3,

lpll = 1

+fl-1

= Yfl+

k

+

+

+ + +

+

+

6 = 0.5773502,

Ipll = 1,

by

4.11.3. Further Predictors

[25] p = 2k

+ 1) k

=2

+

+

+ +

lpll = 0.039630

+ 2.

204

4. Predictor-Corrector Methods

j7n+l

bfn+l - 0

As

Y,+,;

el. 1. 2.

yi

jn+el J,+e J;1+8,

(P3)

4.

yi

Y,,+~

+2 p = 2k

0

+ 1 by k

(P2)

k k

yi

+2

+

fi

+2

2k

+4

2k

+4

yi

+1

k k+l 1 1

,fi

fi

4

2k

+3

2k

+3

k 1

+

6

fi

fi

1

(C’

fi

yi

jn+l

.E+ e

”

(P2)

3.

p = 2k

“

fi

P-C

k _< 6

(PI)

4.11.

205

Hybrid Type Methods

+

+ 3.221Yn-z + h[3.686fn + 6.072fn-, + O.9558fn-,] = 0 . 5 3 3 6 ~+ ~ 0 . 4 4 9 4 ~ ~+ - 0.01695~,-~ + h[0.7024fn + 0.1942fn-, + 0.08660~n+,,7] ynfl = + h[0.3095fn - O.O098O3fn-, + 0.7002Tn+0,7] = - 5 . 7 9 3 ~ ~ 3.572yn-1

Jn+0,7

J n + 1/2

~ 1 "

yn+l=yn+(h/6)Cfn+l +47n+1/2+fnI = +,

k = 1,

= 0.7

(4.11-13)

+ 23.4IJn-2 + 4.509JJn-3 + h[6.955fn + 26.96fn- + 17.18fn-, + 1.40Ofn-,] = -.5709yn + .8758yn-, + .6808yn-, + .O1430yn-, + h[1.262fn + 1.266jn-, + .2466fn-, + .082537n+.7566] j n + = .7195~,+ .2804~,- + h[.5929fn + .09455fn- .002092fn + .594ifn y n c l = .9603~,+ .03963~,-, + h[.1293fn+, + .2772fn

Jn+.7566

= -16.30Yn - 11.61yn-,

Jn+,5773

+ .7566]

-2

+ .009285fn-, + .6237fn+.,,,,] k

= 2,

0 = 0,5773,

0,

= .7566

(4.1 1-14)

P-C

4.11.4. The Special Second-Order ODE no p = 2k p = 6, 0 = 0.3

by 4

J n + l - @=

4

p i y n + I - i + h2C7iy;+1-i i= 1

E l = - 1.9320993

E2 =

6.4719549

i i j = -3.4476119

ii4

=

-0.0922437

i= 71 =

v2 =

0.862500525 3.030380475

0.433679775 y4 = -0.007217775 73 =

(4.11-1 5 )

206

4. Predictor-Corrector Methods

=

+

+

-

... p

-

+ 14.66 . . .

+ 2.66 . . .

=7

u1 =

2.05804967222800

Yo =

'2

=

y1 =

'3

=

yz =

=

4'

y=

0.152641470035498 0.161595975532325

y3 =

0 0.704431783153855 0.0872587915934802 0.154458906599228

~4 =

/lo = 0.

4.11.5. More Than One Nonstep Point

in the corrector

on As k<

p

= 2k

k

+1

k 2 15

p = 2k by

+ 2.

7

207

4.11. Hybrid Type Methods

. . . , Pk.

+

2k 3 p = 2k + 2. k 5 15

O2

c(,,

. . . , a k , b,, b,, P o , pl, #

h=

0, go

k 5 4, k no (h #

by

208

4. Predictor-Corrector Methods

4.12. STARTING THE P-C COMPUTATION

y = yo

y,, y 2 , . . . yo

yo

... .

4.13. ADJUSTMENT OF THE STEP SIZE DURING THE P-C SOLUTION

x

A,,

by

4.13.1. Stability Considerations A,,

bound on

by

bound on ( -Ah)calc

on h,,,

. A l , ,,, . by

bound on A,,

bound.

1=f, f,

h,,,

by

209

Adjustment of the Step Size

4.13.

(4.13-2)

A bound on

4.13.2. Truncation Error Considerations j , , - y,,

jn+l - yn

As

h

by

h

go

h/2

h 2h h/2

h,,,,

2h

bound on up

h

jnfl -Y,+~

h

h

All y,, y,-,,

I7

k

= 2)

y,

.

yn-2

2h

y n W 2At

h3 j, -y,

by Z 3

= 8.

h k =2

J,,-~

y,-l,2

210

4. Predictor-Corrector Methods

by

y,,

+(j,-

h

h

h.

up

4.13.3. Further Stability Details on h,,,.

A A

= A,

A,

=f, =

A,,' =f,' A,,' hA

c = ?.,,'/A,,, A,, # 0.

hA

c. o

AA

c=0 c#0 c = 0 (A,,= ;

4.14. TABULATION OF EQUATIONS AND STABILITY BOUNDS

4.1

4.3

4.14. Tabulation of Equations and Stability Bounds

211

4.3

1.

-2

0

-02

-2, -2,

s= 1

0 21

s=3

2. -2, -2,

s=l s=2

-1, -1, -1,

s=l s=2 s=3

3.

4.

’

-0.8 < hh < -0.42 < hx <

5. -1 -2.6

6.

S=

1

S=

2

-0.85

0.71

-0.55 -6.0 -1.8, -1.3, -2.0, -1.6

0.721

7.

c

s=l s=2 s=3

1.31 1.61 0.71

8. -0.3 S=

1

S=

2

0.421 li 0.91

9. -0.2

0.25 .3i

-0.95

0.71

212

4. Predictor-Corrector Methods 4.3

10. 0.55i 1.051

0.41 0.681

-0.5 -0.5 -0.4

0.71 0.951 0.721 0.551 0.421 0.31

- 1.45 - 1.05

12. -

0

< hh <

13.

-0.1

4.15. PUBLISHED NUMERICAL RESULTS

on is

4.15.1. Stability of P-C Methods

y’ =

+ 100 - 10oy,

A

y(0)= 0

4.15.

213

Published Numerical Results

x

2

y’ = 1 - y ,

y(0) = 2 by

y (0) = 0, y’(0) =

y” = - y ,

of

Y,’ = Y2

Yz’ =

3

4.15.2. Adams P-C Combinations (p= 6

y’ = ay

+b

wx c = 0,

k k 2 3

-

x

1500 380

4

5

43

k 6 7 8

-

x

17 6 2

214

4. Predictor-Corrector Methods

do

on

s,

s/h =2 =3 p =6

no

= =4

1 s = 2,

7

4.15.3. Variable Coefficient and Hybrid Methods 1

on

P-C, h

4.11.

by et al.

on

on

4.15.4. Comparison of P-C and Runge-Kutta Methods

on

y);

up

21 5

4.16. Numerical Experiments

(2.3-20),

on bound

1.

2. do 4.16. NUMERICAL EXPERIMENTS

2 on

2.

(-

4.17 will

&$‘

-:,\.: 5

4.16.1. Milne Methods

h = 0.01

1.0

4.4

h = 0.01 x.

3

h = 0.1,

h = 1.0

on

h

216

4. Predictor-Corrector Methods 4.4

SYSTEM

SINGLEPRECISION MILNEFORMS pea'

X

81

E2

0.1 0.3 0.5 0.7 1.o 2.5 5.0 7.5

1 1 1 1 1 1 2 2

0.5 0.7 1.o 2.5 5.0 7.5 10.0

3 4

4.0 5.0 6.0 7.0 8.0 10.0

15 13 23 7 24 6

2 3

0.136910- 1

5

h h (h = 0.1

h

= 0.01

h 4.7

h up up

4.16.2. Hamming Methods

4.5

on

VII

h

= 0.02,

0.1,

217

4.16. Numerical Experiments

4.5

&

X

h = 0.5 0.1 0.2 0.3 0.5 0.7 0.9 1.o .5 2.0 3.0 4.0 5.0

-3

17110 50710 - I

I

0.5

h, h, h

h = 1.0

= 0.5

on

on

4.16.3. Adams Methods

111,

VTI. s = 1, 2,

111

4.6 h

= 0.25

b

=

3. 1.

-

218

4. Predictor-Corrector Methods

4.6 111. b

=

- 1,

h = 0.25.

x = 20.0

h = 0.01 5625

s/h.

s=2

s=1

3

on

( p = 3)

h

I

Figure 4.29. PE(CE)”.

2

versus s / h

3

= 2.0.

IV

VII

4 5 Log2 ( s / h )

111.

6

7

I

219

4.16. Numerical Experiments

-

-2-

L

e

al -

2-3A 0

-4

-

-2

I

I

I

I

I

1

I

I

1

I

I

I

-

L

8 -

0 -3-

0,

3

-4

-

s=1

p

= 3.

111.

on

h h = 1/100,

4.7

p = 4.

on h = 1/100 = 0.01 y, y3

y,.

y1

x, x ‘v y,

h= = 0.02 is y,, by h=

y, y3

h=

y3).

y, , = 0.025,

p

= 4,

220

4.

Predictor-Corrector Methods TABLE 4.7

SYSTEMVI. SINGLE PRECISION ADAMSFORMS, p =4

0.16 0.26 0.36 0.46 0.56 0.76 0.96 1.26 1.56 1.96 5.96 10.96 15.96 25.96 45.96 0.20 0.325 0.45 0.70 1.20 1.70 2.20 2.70 3.70 4.70

k,

hI

k

= 4,

5,

6

h2 h

4.16.4. Hermite-Milne Methods 4.5.5 4.8

V. =0

x.

= 1,

y(x)

on

22 1

4.16. Numerical Experiments 4.8

I

I

h = 0.5, s = 0 X

s = 1,

I/h 2.0

YDP

1 .o 0.6067 0.3593 0.2708 -0.1875 2.2083

0 0.5

1 .o 1.5 2.0 2.5 3.0 3.5 4.0

-

4.0

8.0 10.0

20.0 100.0

x = 1.0

(CX -YDp)/e-X

-0.283810- 2 -0.121510-3 -0.637610-5 -0.252610- 5 -0.147910- 6 -0.225010-9

(Kx-ysp)/e-”

-0.283810-2 -0.121610-3 -0.631 5 -0.243010-5 -O.16ZO1o- 6 0.226810- 5

14.OOOO

92.8333 -613.000 4049.33 -26748.0

4.5

5.0

V s -1

h ___ 0.50 0.25 0.125 0.10 0.05 0.01

x

= 0.5

x - y,D,)/sin x x = 6.0

x = 2.0

0.540010 - 3

0.911810-3

0.873110-4 0.534010-5 0.187910-5 0.135310- 6 0.215410-9

O . ~ O ~ O ~ O - -0.972710-3 ~

s=2

0.202910 5 0.790310-6 0.44271 0- 7 0.64270 - 10

-0.215110- 1 -0.497310- 4 -0.194610 - 4 -0.110310-5 -0.161610 - 8

=

=0

s= 1 on

h.

4.16.5. P(EC)’ Modes

All

upon

x = 20.0 14.88 0.3899 0.1

-1

0.388610 - 2 0.122210 - 3

222

4. Predictor-Corrector Methods

4.8, on

h,

s,

4.9

4.32

151.

by

s = 1, do

h = 0.5 h = 0.125

s = 1,

bound

h = 1.0 2

0.125. s h = 0.5 s = 3,

3

s=1

-81

0

05

I

10

1

15

20

(s/

Figure 4.32. P(EC)”.

versus s/h

System I.

25

3

h

=

4.16. Numerical Experiments 4.9

0.5 0.25 0.125 0.0625 0.03125 0.01 5625

0.5 0.125 0.03125 0.5 0.25 0.125 0.0625 0.03125 0.015625 0.5 0.25 0.125 0.0625 0.03125 0.015625 0.5 0.25 0.125 0.0625 0.03125 0.015625

0.5 0.125 0.03125 a

on E

223

224

4. Predictor-Corrector Methods

h

no

x

11,

11,

h

x.

x = 15.0,

y(x) =

h = 0.03125.

0.197

h

= 0.50

h = 0.125, y1

x.

h’s

= 1,

h = 0.0626

h = 0.25.

= 2,

bound

h h on bound

x=O.5, on As 1. 2. 3.

h

h = 0.00125

225

4.16. Numerical Experiments

4.16.6. Hybrid Methods 1, 11, good h = 1.0

4.10 h = 0.1

4.10 h = 0.1

I1 &

X

0.2

0.4 1.o

2.0 5.0

&

-0.673510- 5 0.112610- 4 -0.816510-5 20.226410- 5 0.408710- 7 IV

X

0.2

0.4 0.6 0.8 1.o

2.0 4.0 5.0 VI X

&

0.8

2.0

0.715210 - 6 0.178810- 5 0.48271,- 5 0.655610- 5 0.882 I 5

5.0

0.1001

0.2 0.4 0.6 1.o

<10-6

~

- 4

226

4. Predictor-Corrector Methods

4.16.7. Higher-Derivative Methods

P:

(u)

(b) P :

+ \ifn

= y,

+

Y , + ~= y,

P:

1

+

= yn

+ ilfn +

= y,

+ hj, +

fn+ 1]

(d) P :

c:

(c) P :

yn+ 1 = y n

+

(9) P :

n 1+ =

Yn+ 1

yn-

1

+

+ f n + 11 +

+

P : j n + l= y n - l ~

+

+

11

-

+

fA+11 f:+ 11

-

+ +

1

+

+ h[fn-

= 2yn - y n - 1

+ 1

1

+

-

1

+ 3fn’]

yn+l

+

+

-

by 1.

V

0.001

h’s

2.0.

4.1 1

h h = 0.01

2.8,

h = 0.1

by /7 = 2.0

x = 5.0

4.12 h.

el h. h.

x on

4.16.

227

Numerical Experiments

4.11 =

X

0.5 1.o 1.5 2.0 2.5 3.0 3.5 4.0 5.0 6.0

X

h = 0.01

h = 0.1

h = 0.5

5.0

h=1.0 0.633110 - 1

8.0

10.0 12.0 15.0 16.0 20.0 24.0

0.623610 + 2 0.2027

0.513810 + 2 0.1521 0.1636,o + 7

4.12

E*

x = 5.0

h = 0.01

h = 0.1

h = 1.0

O.8OOO10

0.813910 - 2

0.8679

h = 1.0. h = 2.0. h = 1.0. h = 2.0. h = 1.0. h = 2.0. h = 1.0.

-4

0.3644

h = 2.0. h = 1.0. h = 2.0. h

-4

=

2.0, h = 1.0. h = 2.0.

228

4. Predictor-Corrector Methods

10' 10-2

IO-~

e ; -

10-6

10-8

IO-~ 0

r

Figure 4.33.

2

3

X

4

6

5

h

x

W h:C

10-12

b,

) 001

Y

10-l~

I 0- 140

2

I

3

4

5

X

Figure 4.34.

x

h

6

229

4.16. Numerical Experiments

0

1

1

i

i

i

i

i

2

3

4

5

6

x

Figure 4.35.

X

7

h

V

10 1 I00

10-1 10-2 -

o3

E W

10-6

10'~ 10-8 10-9

10-10

0

2

4

3

5

6

X

Figure 4.36. Error

x

V

h

g,

230

4. Predictor-Corrector Methods

4.12 go up.

k

(k = 2

=

up, ;

4.16.8. Recommendations on

A 1. 2. on h

3. 4. 5.

4.17. NUMERICAL COMPARISONS OF SINGLE- AND MULTIPLE-STEP METHODS

no

rn

4.17.1. Solution of PDEs by the Method of Lines by

23 1

4.17. Numerical Comparisons of Methods

Yt = Y x x 2 ) = 0, Yx(0, t ) = 0,

t>O t>O

y(x, 0) = - I ,

0 <x < 1 yxx x

m t

x “

y’ = Ay,

y(0)

Im x

y

= -1

A

on

A

As Y , = [ 1 + .(

+

+

2x2

1)2

I”

Yxx

Y ( 1 , t ) = 0, Y,(O, t ) = 0,

t>O

y(x, 0)= - 1 ,

0 <x < 1

t>O

by

A

by t

m;

As 1. 2.

(2.5-18).

m.

232

4.

Predictor-Corrector Methods

3. (4.6-3).

P-M,-C-M,

y,

h, y,, +

y,,+ y,, + Y,,+~

y,,,, h up

on 4.13 DOUBLE PRECISION

EQUATION

50 X

t

= 0.20

= 0.10

0.8 0.6 0.4 0.2 0

h

-

150

is

50 X

t = 0.001

t = 0.01

t

= 0.10

t = 0.20

t

0.8 0.6 0.4 0.2 0

h occurs

h=

0.50

4.17. Numerical Comparisons of Methods

233

TABLE 4.13 (continued) PRECISION EQUATION (4.17-3). DOUBLE Rosenbrock

Hamming

Errors at value

50 points

30 points t = 0.01

X

0.8 0.6 0.4 0.2 0

4.210-4

5.210-5 5.310-7

-8 1 .Ole - 9

h Computing time Comments

10-2

10-4

-

-54 sec/100 steps.

18 sec/100 steps. Unstable at h =

Stable for h = 10-5. Unstable for h = 10-4.

bound

h

2h. by

on

PDE by (4.17-1). P-C;

4.13.

by

=

1.5

50/30 = 1.7.

h

by 4.14

PDE

234

4. Predictor-Corrector Methods 4.14

30 X

0.8 0.6 0.4 0.2 0.0 h

- 77 15

30 = 0.10

t

X

0.8 0.6 0.4 0.2 0.0

t

= 0.20

h 65

15 X

0.8 0.6 0.4 0.2 0.0 h

t

= 0.10

= 0.20

5.410 - 3 8.11 0 - 3 1.010 - 2 6.910 - 3 10-3

20 30

t = 0.40

4.17.

Numerical Comparisons of Methods

235

do

on 1.

by 2.

on

3.

4.17.2. Solution of System IX

yZ(0) =

=

x = 5.0.

h = 0.001

h = 3.0,

1. 2. 3. 4. 5. 6. 7.

h

= 0.1

0.5

h = 0.001

4.15. E 4.16

236

4. Predictor-Corrector Methods

SYSTEM

TABLE 4.16 Ix. DIFFERENT METHODS REACHX

h = 0.001

= 5.0

h = 0.1

h

P V"

tDP

V

k P

tDP

2000

1.6

1.7

200

0.13

0.13

22.8

3000

2.1

2.4

300

0.18

0.34

27.5

3500

2.5

2.7

350

0.21

0.36

12.9

1000

tDPc

20,000

16.1

17.3

30,000

21.4

35,000

25.3

10,000

Y

tse

tSP

V

''

1.04

0.08

10,007

6.4

7.3

1007

0.71

0.80

113

0.11

0.12

10,007

5.8

7.5

1007

0.56

0.68

113

0.09

0.11

10,007

6.3

7.7

1007

0.57

0.17

113

0.10

0.11

-1

h = 1.0 h = 3.0 h = 1.0 h = 3.0 h = 1.0 h = 3.0 h = 3.0

h=0.5 h=1 h = 0.5 h=1 h = 1.0

h = 3.0 a

x

5.0

:

x=5.0

a

5

r

c

P

w

f4-. v1

P 0,

z3 Lr

!2

238

4.

Predictor-Corrector Methods

:

h = 0.01

1.

good

h

2.

h = 0.1

3.

h = 0.5,

4.

4.16

= 0.01

4.15

1 : 2 : 3.5

h h

=

1.0,

h = 1.0.

=

on on :

1.

by

2.

4.17.3. Recommendations 1.

h = 3.0.

(rn <

239

References

2.

1.

Simulution 31,

A 219

2. 3.

J. Math. Comp. 1 9 , W J. J.

4.

A

M.

Much. 14, 769

J. Assoc. Assoc. Cbmput. Much. 12, 124

5. 6.

Math. 20, 1 A J . Assoc. Comput. Much. 14, 84

4

5

7.

J. Assoc. Comput. Mach. 9, 457 W., A J . Assoc. Comput. Much. 12, 227

8.

J.,

9.

J . Assoc.

Much. 9, 104 G. A

10.

3,

27

on

11.

J.

Syst. Sci. 2, 203

12. 13.

AZChEJ. 14,946

J . Assoc. Comput. Much. 15, 712

14.

I.

“A SIAM

1966. 15. SIAM J . Numer. Anal. 2, 69 16. Comp. 21, 146 17. B., H. J., J . Assoc. Compuct. Much. 11, 188 18.

Math.

Comput. J. 9, 410

240

4. Predictor-Corrector Methods

19.

J . Assoc. Comput. Mach. 6, 37 S.

20.

by

J . Assoc. Comput.

Mach. 14, 549

21. J. SIAM 9, 31 22. 23.

J . SIAM 10, 351 A. Comput. Mach. 10, 291

J. Assoc. S.,

24. Math. Comp. 22,557

25.

G. J. Assoc. Comput. Mach. 14, 155

26. J . Assoc. Comput. Mach. 15, 390 27. J . Assoc. Comput. Mach. 13, 374 28. J . Assoc. Comput. Mach. 14, 351 on

29.

Math. Comp. 21,

717 30. SIAM J. Numer. Anal. 4, 597

31. 1962. 32.

O.D.E., NASA Technical Report, 33.

Simulation 12, 87

34. Rev. Franc. de Traitement de L’lnformation, 135

35. 1953. 36. J . Assoc. Comput. Mach. 6, 196

7, 46

37.

J . Assoc. Comprrt. Mach. 9, 64 38.

Math. Comp.

16, 22 39.

BIT6, 51

40. Comput. J . 4, 64

41.

in

SIAM Rev. 7 , 114

42. 43.

1965.

5, 164

241

References

44.

A J. Numer. Anal. 2, 265 (1965). 45. J., 84 (1965). 46. H. “ (Arch. Elektron. Rechmen.) 3 , 286 (1968). 47. W. of

SZAM Math. Comp. 19,

BIT 5, 276 (1965).

5 Extrapolation Methods

5.1. EXTRAPOLATION TO THE LIMIT

5.1.1. Accumulated Truncation Error of Single-Step Methods on y(x)

@(x, y ; h) by

IE,~

C

Chp,

E, +

0

h + 0. how

E,

E,.

Theorem 5.1.1.

E, E, = hPE(X,)

e(x),

(5.1-1)

rnagnged error function,

E(XO)

242

+ O(hP* ')

=0

(5.1-3)

243

5.1. Extrapolation to the Limit

by yn(h)

y(xn)

h, yn(h)= y(x,) y(x)

+

+ O(hP+')

(5.1-4)

E(X)

(5.1-4) =A x n )

+ O(hp+')

+ y,, .

y(x,).

(5.1-6) by

y(x,),

O(hP+').

by

h h/8, 2.9.1 x,-~

x,+, by

2h,

h

by

(5.1-7)

by y(x,+J, Y 2 1

=

1)

+ O(hP+')

5.1.2. Extrapolation to the Limit

by

(5.1-8)

244

5. Extrapolation Methods

on by T(h).

y,,(h) = T(h).

h, T(h) = 70 -k

71h”

+

-k 7 2 h Y 2

* * * ,

i = 1, 2,

. ..,

zo

yi =

b_=

yi = i y

0 < 71 < 72 < * “ p =1

1-2) ~(x,,),

1. z1

T(h)

[I21

yi= T(h)

by

h ”

.

yi = i, i = 1,2, . . . .

s t f ( x ) dx by

+

T(h) = h[+f(a) f ( a

+ h) + - - + +f(b)] *

- 10) O(h2), h

y i = iy, y = 2.

h/2. Tio)=

4T(h/2) - T ( h ) 3

1 0

Ti0)

0(h4), = To

-7 2 h4 - . . . 4

Tio)=

16Tio’(h/2) - T‘,O’(h) 15

3)

O(h6),

-

245

5.1. Extrapolation to the Limit

by

Tik)

by

2k

by

y,(h)

Tik)

hk

=(x - ~

Tf)

)/2~, hk = (b -

by

T(h)

yi = i

y i = 2i,

Tg) by

by by (k)

T

on

h. A

ho > h, > * - - > h, y i = iy

(5. I y = 1, 2

h, = h0/2,,

by

A by

246

5. Extrapolation Methods

y = 2.

y

=

Theorem 5.1.2

A T z )= to n+m

T(h)

h

y =2

=0

(5.1-18)

bound. Theorem 5.1.3 y i =2i

T(h)

k + co,

T g )- T o

= (-

1)"hk2 * * * hz+m(tm+ + O ( h k 2 ) ) hk+ 1

-> O k1O

hk

8,

bound,

> 0, 1)

< 6 m + l h k 2 " ' h k2 + m T T!:)

to

5.1.3

T~

T ti to

lT'io) - tO1< Km m+m

on

TLo)

Km+ -Km

T(h) h

=0

by

Tg)

247

5.2. Extrapolation Algorithms for ODE

by

T!L)(hi)= T(hi),

i = k , . .., k

+ nz

do,

(k) Tm-2 (k+ 1 )

Tm-2

T:?;’ on

5.2. EXTRAPOLATION ALGORITHMS FOR ODE

on

5.2.1. The Euler-Romberg Method

y(x,,)

y,,

y’ = f ( x , y ) ; y(xo) = y o .

x,, y,,

y(x,,)

h, y , = y(X,,)

+ ‘Cl(X,,)h -k t 2 ( X , , ) h 2 -k

‘C3(X,)h3

4-

.*‘

on x. on

k

= 0,

1, 2, . .. h,

y,(hk)

= i,

y,,

h,, YAk).

x,,- xo. i = 1, 2, . . .,

248

5. Extrapolation Methods

(5.2-1).

hk

h,

odd

(5.2-1)

= /1,/2~,

(5.1-15) (5.2-2)

hk,k

1, 2,

= 0,

... ,

- ygL

y $ )= (hk/hk+rn)y:zi) (hk/hk+m)

(5.2-3)

(5.1-17), 1

(5.2-3)

-

y)

x,

hk,k

= 0, 1,

do

2,

x,,,

... ,

h,

- x,.

x,,

each

x 2 , ...,

= h,

-

.

local h,

(x,,, y,,) - x,, = h,

Y,,+~

, by

by

by Yh'), by

Y,,+~, h,,

Yk0) = y n

+ h,f,

(5.2-4)

Yhk)

Yp y61) yco,

y p

yC1) y p

by h,, h, , ..., by 5.1 Yhl) h, =h,/2 Y J 2 ) h, = h,/4

h,/hk, k

= 1,

2,

. .. ,

hk = h0/2k, 11.

hk

= ho/2k

x,

h, h,,

... Y

(5.2-2)

on

x,,+~.

5.2. Extrapolation Algorithms for ODE

I

I I I

I I I

I I

I

I

I

I

249

I

I i

Figure 5.1. Successive halving in Euler’s method. [Adapted and reprinted from

T.R . McCalla, “Introduction to Numerical Methods and Fortran Programming,” p. 342; copyright 1962, John Wiley & Sons.]

by E ~ ,

YLk)

yn+

Y,,+~.

1. 2.

Y p =y,

+ h,f,. YLk’

:

by

-5)

250

5. Extrapolation Methods

k > 1, go

3. 4.

k

4. by

=

1,

2.

Y , , ~ = Y, k =k

1. k < Kmax

+1 k

2. K,,,

(5.2-1)

odd Y

h,

h2

on local

each global entire

x, = a

x=b

xn= x g

+ nh, .

5.2.2. The Trapezoidal Rule

h2

T(x,/ I )

= yn(h) Yn + 1

T(x, / I )

= Yn

+ ('7/2)(fn

+1

+f n )

+

(5.2-6)

= y(Xn) 4- 7L(x)/72 T 2 ( X ) h 4 -I-

~~(x), 72(x), . . .

-

a

(5.2-7)

*

(5.2-1).

global 5.3.2. (5.2-6)

is

(5.2-6)

exactly

25 1

5.2. Extrapolation Algorithms for ODE

4.3.3

x,

1.

x =b

=u

Thy!, n = 1, 2,

h,.

N = (b - u)/ho. X, = X,

..., N ,

n

T

+ nh,.

x, = a

2.

hk = h,/2k, k = 1 , 2, x, = x, + nh,, n = 1, 2, . . . , N ; k = 1, 2, . . ., K. T

.. . . At

x=b T& , Tgk,,

x, . x,, x, = x,

3. 4.

K

=K

+ nh,, by

+1

1

K. y , = Ti:;

on 6

5.2.3. The Modified Midpoint Method h2 h h

on by

x,

y’ = f ( x , y ) h,, hk = ho/2k,

k

= 0,

x, + 11, by

h,, 1 . 2, . .

hk = { A o , ho/2, h0/3,h0/4, h0/5,h0/6}

[8]

252

5.

Extrapolation Methods

T(hk,x) T(0, x)

~ ( h , x) ,

=

y(x)

= y(x)

hk-0

ti,

y(ti,h)

+ h, . [x,, x, + h,]. x, + h, , n = 1, 2,

< ti< x,

x,

x,

,

.. .

Y(41, k ) = Y o + hf(x0 > Yo)

by

by

y(x, h)

h.

T(h,x)

T(hk, x) by

T,’,)

TLkl

1.

Tik’= T ( h , , X )

= 0,

a

h,

+

x, = x, nh,, n = 1 , 2, . . . , N . S(/7,, xl) on h,, k = 0,

2.

K

2, . . . , T(2h,, x,) T

h,/h, by T c ) , by (5.1-17)

3. A

on on

Tz) TAo’ ,

TAy y,.

4.

2

3

x, = x,

on

+ nli,,

n

= 2,

3, . . . , N .

TAk-’),

253

5.3. Stability and Error Analysis

on :

I1 II

h

'

5.3. STABILITY AND ERROR ANALYSIS OF EXTRAPOLATION METHODS

5.2.

Yn+l

x , + ~- xn = h,

A>Yn

=

pl(hoA) xn

locally

x,+~

yn + 1 = B(h0 2, m, klyn

k m

h,,

Y m

=M,

k = K,

yn+1 = P(h0 h,,

h, =

k = 1 , 2,

M , Klyn

... , K .

Ilk,

k

= 1,

2,

... , K,

n Y , = [P(/70

4M , K)]"y0

(5.3-4)

254

5. Extrapolation Methods

< 0,

y' = Ay IB(h0L M ,

5 1

K

M

hoA by

5.3.1. The Euler-Romberg Method by

Y Yg'

=

+

=

k

7

= 0,

1 , 2 , ...

T

m

Y p= i=O

-2

m

-

,

- cm-l,-l = 0

2" - 1

YhK)

P(hOib,

M,K,

Y,+~,

K+i

=

2K+t

m =1 Y y=

k

-

= 0,

Y y = {1

+ h, 2 +

42k)yk}yn

255

5.3. Stability and Error Analysis

y,( k ) - 38 k

0

m

c2,0 = t.

c 2 , 2= +, c ~ =, ~

0

-

=2

+gyp

= 0,

Y i 0 )= {+(1

+ +h,A)"

- 2(1

+ +h01)' +

+ hoE.)}y,

rn

K K K

h,

M, M

=0

A4 A4 = 1

Y

5.2

hoA.

P(hoA, M ,

Figure 5.2.

h,

6

-t- 1

M,

p(ho

M. M W O ) I I U X

As

1

2

3

4

5

6

256

5. Extrapolation Methods

5.3.2. Trapezoidal Rule

local global

no

on

[a, b].

by

T

=

(51-15)

T

By

M

=

1, K

= 0,

2.

/3(ho1,

h, I by by

M

K

I/3(hoA, 1,

< hoA < 0

hoR > 1.85.

by h,

+ co,

<1

257

5.4. Published Numerical Results

5.3.3. The Modified Midpoint Rule 5.3.1

5.3.2.

3.3.

hoA

6. 5.4. PUBLISHED NUMERICAL RESULTS

by by

on

1. 2. :

3.

-1 :

x =0

1. y’ = -y, y(0) = 1.

x

= 20

x = 20

e - 20 x

(y, - e-20)/

= 20.

2. 3. 4.

16.

y’ = - y (M

=

M

=6

258

5.

Extrapolation Methods

by

2. (M =

A4 = 6

3. A on y’ = - y

M

M on y’ = - y , M = 10

M

= 4.

A4 = 6. M

= 10

5.5. NUMERICAL EXPERIMENTS

on

2 6.

FORTRAN DIFSYS

by by

ho,

EPS,

ho m

7, h o , , , ~ = ~ . ~ ~ O , O I C I ho, n e w = O . ~ ~ O , . M

nt 2 7,

ho,

h0/2,

ho/8,

...

259

5.5. Numerical Experiments

I,y’

5.1,

=

-y,

5.1

ho = 0.05, ho

X

0 5 7 7 7 5

0 0.05 0.125 0.1925 0.25325 0.307925

0.05 0.075 0.0675 0.06075 0.054675

y

x

1 49 105 105 105 49

0 4

y

0.0250

. 0.0

-3

(u)

E

1.o 0.9506108 0.8840196 0.8279507 0.7804320 0.7383381

=1

0

0.0125 0.0250 0.0375

0.5908082

1

0.0083 0.0167 0.0250 0.0333 0.0417

0.9606364

2

0.0062 0.0187 0.0250 0.03 0.0375 0.0437

0.9231223

3

0.0042 0.0083 0.0125 0.0167 0.0208 0.0250 0.0292 0.0333 0.0375 0.0417 0.0458

0.9513791

4

260

5. Extrapolation Methods TABLE 5.1 (continued) Progress in calculation, First Series x values

Extrapolations

Extrapolated y

0.0031 0.0062 0.0094 0.0125 0.0156 0.0187 0.0219 0.0250 0.0281 0.0313 0.0344 0.0375 0.0406 0.0437 0.0469

Counter

0.9506108

5

End step 1, 10.9513791 - 0.95061081 = 17.710-41< l . O l O - 3

5.1

x = 0.05. “

”

u

0.

RHS h, = 0.05

l.010-3. (0, 0.05}

EPS =

yo,os;

yo,,,

EPS =

yo.,,

x

= 0.9506108

0.0750

h,

5.1

As

yo.,,, 0.0675

h,

= 0.8840196. =

0.8279507. EPS = 0.1

5.2.

by

h = 0.5. 5.1

5.5.

Numerical Experiments

261

5.2 SYSTEM SINGLE PRECISION, MODIFIED MIDPOINT METHOD X'

-

E

Counter

0

0

-

0 0.0500 0.1250 0.2375 0.4062 0.6594 1.039 1.608 2.462 3.744 4.224 4.945 6.026 7.698 10.08

3 3 3 3 3 3 3 3 3 23 3 3 3 3

1 21 21 21 21 21 21 21 21 21 357 21 21 21 21

0 0.5000 0.8750 1.437 2.281 2.914 3.863 5.287 7.422 10.62

0 5 15 3 3 13 3 3 3 3

1 49 223 21 21 22 1 21 21 21 21

0 7 7 7 7 7 7 6 7

1 105 105 105 105 105 105 73 105 49 21 21

0 0.1925 0.4637 0.7603 1.084 1.439 1.827 2.308 2.987 3.946 5.228 7.656

ho = 0.05, EPS = 0

3

3.310-3 5

5

3 13

262

5.

Extrapolation Methods

5.2

X"

0 0.3387 0.6521 0.9549 1.286 1.648 2.096 2.655 3.444 4.712 7.073

8

ho 0

1 105 105 105 105 73 49 105 49 49 49

0 7 7 7 7 6 5 7 5 5 5

2

2

a

5.2

EPS = 0.1

h,

h,

h = 0.05

= 0.05

EPS =

1.0,,-5

420

(0,

h, =

0.05

EPS =

1

5.3. h,

= 0.05

/I,

7. h,

6.

263

5.5. Numerical Experiments 5.3

v

System X'

c2

0 0.1015 0.3190 0.4966 0.6409 0.8091 0.9048 1.091 1.368 1.564 1.763 1.987 2.152 2.332

X

0 0.2739 0.3209 0.3607 0.3990 0.4317 0.4595 0.4859 0.5109 0.5354 0.5622 0.5845 0.6065 0.6253

U

0 5 7 6 3 6 5 6 6 5 4 4 5 5

1 49 105 73 21 73 49 73 73 49 33 33 49 49

V

E

0 9 6 7 8 8 6 6 6 6 7 8 8 6

1 217 73 105 153 153 73 73 73 73 105 153 153 73

264

5.

Extrapolation Methods

5.5.1. A Nonlinear System

on

Yl’ = 2 0 1 -2 2 Yl -2 3Yl Y2’ = Q l - Q 2 Y 2 - Q 3 Y l Y,(O) = 5.010-3, Y*(O) = 300

1.735, Q2

= 2.510-5, = 5.678,,-3,

(5.5-

X 2 = 5.01,-3, X 3 = 7.8610+12, = 11363, Q, = $2, =7.8610+16. y, y2 4.41 1 0 - 3 306 h, 0.05 90.0 EPS

l.Ol,-s

0.1

5.4

h, y1

h,

= 0.05

h,

2.7

1.4

EPS

1.2

h,.

EPS

h, . 5.4 h = 20.0.

0.55 h, = 20.0

1.4

x h, . by by

5.5.2. Summary 1.

= 0.05

y2 = 20.0

TABLE 5.4 NONLINEAR SYSTEM. SINGLEPRECISION" ~~

h~ = 0.05, EPS = X

a

YI

ho Yz

0 0.05 0.125 0.2375 0.4062 0.6593 1.039 1.608 2.462 3.744 5.666 8.549 12.87 19.36 29.09 43.68 65.58

300.0 300.001 300.004 300.008 300.013 300.022 300.035 300.054 300.082 300.125 200.188 300.282 300.420 300.621 300.908 301.310 301.853

1163.

305.967

= 20.0, EPS = 1

X

0 20.0 50.0 95.0 162.5 263.75 350.87 404.08 477.89 588.61 754.68 844.36 978.88 1180.66

~~

~

h = 20.0

5

Yz

300.0 300.63 30 1.47 302.48 303.59 304.63 305.17 305.36 305.57 305.76 305.89 305.92 305.95 305.97

X

Yz

__

0 100 200 300 400 500 600 700 800 900 1000

1040

300.0 302.62 305.09 304.92 305.38 305.64 305.79 305.87 305.91 305.94 305.95 305.96

f q

i;'

c

v w z

B5.

266

5.

Extrapolation Methods

6 on

2.

by

1.

[4].

F. Proc. of Symposia in Applied Mathematics, 15, 199 (1963). by

2. Numer. Math. 8, 1 (1966).

3. Numer. Math. 8, 93 (1966).

4. Argonne National Laboratory Report,

7428

1968).

BIT, 3, 27

5. (1963). “A

6.

Proc. IFZP Congress, Supplement, P.,

7.

I , 32 (1968).

York, 1967. 8.

SIAM

W. J . Numer. Anal. 2, 384 (1965).

9. 10.

14,

York, 1964

For

York, 1962. 11.

12.

13.

‘‘

1967. C. London, 226, 300 (1927). W., heim), 28, 30 (1955).

Trans. Roy. Soc. Norske Vid. Selsk. Forh. (Trond-

6 Numerical Integration of Stiff Ordinary Differential Equations

stif.

[2]. 6.1. DEFINITION OF THE PROBLEM

VI,

y'

= Ay,

y A=

y(0)

= [2,

[

=

do [ y l ,y 2 , y 3 ]

0

-50

0

1, 21, = e-0.'"

yz(x) = F y3(x) = e

+ e-50" (6.1-1)

5 0 X

- 5 ~+ ~e

-lzo~

267

268

6. Numerical Integration of Stiff ODEs

1, = - 120,1,

A

=

- 50,

1, = - 0.1. y,, y , , 1, A,,

y3

1,

1, h

by

IhAJ, 1,

=

1, 2

by

1

10.

A,

by

< 2,

h=

A. no

h

As (rn >

6.7.1

A by

< 0, i

=

1, 2,

.. ., m,

A = A(x)

[df/dy].

by [ 151

A

=

[

-0.04 0.04 0

- 104y, - 6107y , 6107y2

1

1O4yz

- 104y, 0

269

6.1. Definition of the Problem

A by

A1

+ x

+ 104y, +

=0

+

+ 61011

A1 = 0, = 0, = y , = 0, y 3 = 0, y , = 1,

= 0,

x,

=0

(6.1-4)

1y i = 1 1, = 0, 1, = 0,

= - lo4.

by

h by

h<

0 2 x 5 40, 2105

y‘ = Ay.

x,+~

x, by

by

m

p l i= 1

+ hA,,

=

rn on in M(/7A) = I + hA, 2, . . . , m.

h

2, hood

At

stability accuracy.

2, h

270

6. Numerical Integration of Stiff ODEs

on

h on

on 6.7. 6.2 EXPLICIT SINGLE-STEP METHODS

6.2.1. Treanor’s Method A [ 161.

by

by y’

jj

=

-P(y - j )

x

x

by yi’= f i ( x , y)

by yi’ =

-(Pi)nyi

+ (Ail, + (BJn x + (Ci)n x2

A i ,B i ,C i ,

Pi

[x,, x,

f,(x, y)

x,, x,

P j

+ $A,

x,

+

by

+ $h y,

=Y,

+ (h/2)f”

=Yn

+

Y 2 1 = Y,

+

=Yn

+

(2) Jn+1/2

.vn+ 1

+

+

PhF,

+ hu,(Pyn + f n ) + + f!i’?,/,) +

+ f,P, -

+

+

271

6.2. Explicit Single-Step Methods

e-Ph

Fl

=-

-1 ,

F2=-

- Ph

e - P h- 1

+ Ph (6.2-3)

e-Ph- 1 + Ph - +(Ph)’ F3 = -(Ph)3 UI

=

-F2

+ 4F3, ~3

212

= 4F3

(6.2-4)

- 3Fz P.

(6.2-2)

= 2(Fz - 2F3)

Pi

(6.2-1)

P

(6.2-3) Pi

(6.2-2) p . = - f ‘$!+ 112 - f YC’+ 1 / 2 - Y!,?+

112

(6.2-5)

1,2

to by P

Pi

(6.2-2) (6.2-5). If

(6.2-3)

P

m

P

Pi P Pi 1. 2. 3. 4. 5.

h. yA$)1/2 P y,+,

y,!:)l,2

Pi

> E,,,, - ynl/lyn+ll< ]

(6.2-2). (6.2-5). Pi< 0, P = 0. (6.2-2). h = h/2 2. h = 2h 2. 6.1.

hA h

by

- 2 < hAi < 0, hLi < -2,

P.

6.1. If

Ph

= 8,

- 10,

-2.785.

272

6. Numerical Integration of Stiff ODEs 1-

I

I

I

ASYMPTOTIC TO 2, SECOND-ORDER R UNGE K UT T A B 0 UN DARY

THE

-

16

c

a 12

-hX

hh [ll].

Figure 6.1.

on

P,

< hAi < 0, hAi <

6.1

A

6.2.2. Lawson’s Method

to 2.5, (1.1-5), z(x) =

- xA)y(x)

(6.2-6)

273

6.2. Explicit Single-Step Methods

= yo

-

=

m xm

A z' =

-xA)[f,

g, =

-

f, -

g,

1

+ h 1 aij

+ ci

=

1

..., u

ki=exp[-(xn+cih)A][(fxn+cih,pi)-Api], u

=

+1

i= 1

=

5

hA)y,

= = =

0=

-

+

+h

h,

i- 1

aij

-

j= 1

-

+h

wi

1-

II ... I C" 5 1

f,,

h, As

274

6. Numerical Integration of Stiff ODEs

6.2.3. Osborne's Method pl(hA) + 0

hi, + - 00.

hi, + - a.A P(hA)/Q(hA). [I21

pl(hi,) = O(l/hA) y' = Ay

h2 + - co.

by

y

yo

+

m

C f f i X i

(6.2-11)

i =1

- h < t1 < t2 < * . . < tm< 0,

-h < x < 0.

(6.2-12)

Yo =

a , , . . . , a,

by

m

y-, =yo

+ Cai(-h)'

(6.2- 13)

i= 1

(6.2-14) (6.2-14)

We

Ca = -Ayoe

(6.2-15)

e (6.2-16)

C=

p(A) =

p,(A)

=

+(e -

(6.2- 17) (6.2- 1 8)

C.

K;(C)= ai

-AY~P;(~)/P(A)

(6.2-19)

275

6.3. Implicit Single-Step Methods

-1

pi(A) m

C;, = 0

p(A) - 1.

C;, = 0, p(A) pi(A) m. pl(A) = p 1(12)

- 1,

A+

-00.

xT(-h)$i(A) = 2,

t1= -A,

C;, = 0,

pl(A)

tl, C;,, . . . , &,,-l

(C;, =O). -+ 0

l1 > - h,

=2

+

- 00. Also

t1 1)

n

= 2,

=

1

(hA).

Y , , + ~= pl(hA)y,.

6.3.

h

y.

276

6. Numerical Integration of Stiff ODEs

6.3.1. Implicit and Semi-Implicit Runge-Kutta Methods good

2.5.4.

k i. ki

A

6.3.2. Trapezoidal Rule with Extrapolation

6.3.3. The Method of Liniger and Willoughby 3.3.3 p 2 2.

2.

by exponenfiuZJirfing. ~ n + l=

pl(hRi)Yn

<1

< 0,

p,(hAi)

on Yn+ 1 =

+ PO YA+ I + P I Y ~ ’ ]+ YO A’+1 + ~ on

1 . ~ 3

by

(6.3-2)

277

6.3. Implicit Single-Step Methods

to PI

=

PI

4

= =b =0

PI

a

1

- hZ

b = 3.

2,

3,

-

0

+ Ch) d r

b,>Y”(X

-

-

a)[

0

1

+(b

1

- a)[

-

0

P1

=

+ ih) d [

-

+

-

+ [h) dr

+

+

1 p, hA y 1 h 2 i 2 1 - Po h>”- yo

1,

<0

lpll < 1

< a

> 0, b > 0 >0 by

278

6. Numerical Integration of Stiff ODES

2

3

p )= 4 + 2(1 - a ) h l + ( b - a ) h Y 4 - 2(1

vu'3'

=

12 + 12 -

+ a ) h l + (0 - u)~z/Z + + a)hl + +

i = 1, 2,

. . . , m,

As

3.7,

hA = 0 3.7

h l up p = 3. hl, (hl,( $ 1, All = 0

both

pl,

IhliJ

h l i -+ 0.

b

a,

h l = qo = eqO

qo,

exponentiallyfitted

1

pl,

qo

p 1 (40) = -401 - ( e - 4 0 (a, = 4) qo = 0 a

3 2

a(qo) =

1

(p,

=

qo = co

+ 640 + 12 - eq0(qO2- 6qo + 12)]

x [ e Y q o 2 - 240) + 402 +

a

2 h l , qo 4 4 0 41) = 9

b(40

2

41)

b,

ql,

-

= 2(qo - d / C 4 0 r(q1) -

- 40 r(41)l

1

279

6.3. Implicit Single-Step Methods

r(q) =

qo

- e - Q ) [ - ( 2+ q) + (2 + q)e-4]-'

8)

a

q1

qo

0 > qo > - co

hl+ 0 0 > q o , q1 > - 03.

qo

b

q1

q1 1

3

6.3.4. General Observations on Implicit Methods

hR -+ - co,

pl

-+

-1

hA -+ - co.

h

3.10.3

hR.

on on,

by by

by

1. 2. 3.

y1 by (YO+

4.

y , by

5.

+

y,

.

y,

.

+ y,

+ y3)/4.

y , , y,, y s , . . . .

280

6. Numerical Integration of Stiff ODES

by 1

p = 1.

3.3.3. p = 2.

+, 2

3

hA h/l 6.2. As

hX

pL1

-

Figure 6.2. pl (hA)

hA,

pl

1,

3, PI.

28 1

6.4. Predictor-Corrector Methods

6.4. PREDICTOR-CORRECTOR METHODS

6.4.1. Gear’s Method

6.3.

hA

Figure 6.3.

171.

hi < D by D,c(

by

3.3.3

6.3,

6

D,U ,

8.

As h? - co,

o(<)= 0. o(t)

--f

k. k

up

6.4.

D < - 6. 0 < 0.5 A,,

r

k

=

6

282

6.

ODES Im (hi1

-6

-3

-4

-5

-2

-I

-6

k

6.4.

=

...,

=

+

Gear's

- hf(x,

6.1.

1

B i j = (!),

B

PR/crk

-/,

i >j).

6.1

10

11 12

1, 14

15 16

1

0 0 0 0 0

213 1

1201274

I13

1 611 1

0 0 0

0 0

0

0

72011764

1

1

1

1 15 1po 0

2251274 851214 151274 11274 0

162411164 13511 764 1 7511764 2 111164

0

1/1164

283

6.5. Other Stiff Methods

h

k

by

k

h bound.

(5.1-2)], c k hkyCk1. A

6

h6. h

(6.4-4) by

ytkl

kh

k k A

k

k

+ 1,

2 by

h k h up

M

M

A

M

h

on

M

M

A M =3

on by

6.5. OTHER STIFF METHODS

on

284

6. Numerical Integration of Stiff ODES

y' = f(x, y) U' = AU

+ h(u, v, X)

v' = g(u, v, x) u(0)

A.

= uo;

v(0) = vo

r(x) p'

=

p = A-'r(x)

-Ap

+ r(x>

+ A-2r'(x) + A-3r"(x) po(t) [xn,x,,+~]. pl(x)

by

by

r(x)

4%)= h(PO(Xi)>V(Xi)>Xi) p2(x)

by

r(x)

xi) = h(p(xi), ~ ( x j )xi) , IIA-'II llhull

p(t)

u el

v

al.

a on y;+,

y,',

y,,'. ,v,,+~

x,+~= x,

by yn . w

by

+ w/?

by

285

6.6. Published Numerical Results

by

on

on 6.6 PUBLISHED NUMERICAL RESULTS

on by

13

[ll].

on

pi* by

yn+l

h by

[ 131.

1.

2. on 3.

on

1.

286

6. Numerical Integration of Stiff ODEs

2. on no good 3.

6.7. NUMERICAL EXPERIMENTS

6.7.1. ODE Examples

1.

2. 3.

y’ = y(0) = 10 = 10 VT

Y,’= y,’

= =0

+

-

=

+ - Y,) -

+

Y2W

+ IOe-200x

+

=0

4. 6.7.2. Methods Used

1.

2. 3. 4.

DIFSYS

5.

6.3.4 6. 6.3.4 M =3

287

6.7. Numerical Experiments

7.

6.3.4 8. 1

9. 3

6.7.3. Computational Results 1 x =0

x = 15.

-

- x) 1 6.2.

R,

[y, - y(x,,)]/y(x,) 6.2

COMPUTATIONAL RESULTS TOR EXAMPLE 1

R,, h RK4

x

= 0.4

x = 1.0

0.01 0.005

11 18 16.5 b 2 36 1 3 4

0.24 d 0.2 0.2

0.2 0.2 __ (I

h

x, 0.4

on

10. IBM 7094.

0.01 0.1,

0.2

x

= 0.1.

<

x = 0.4

x = 10 x = 10,

288

6. Numerical Integration of Stiff ODES

DEQ h

DIFSYS DEQ.

h

2

by

VI, - 120, - 50,

- 0.1.

6.3.

VI TABLE 6.3 COMPUTATIONAL RESULTS FOR EXAMPLE 2 R1n Method

h

RK4 DEQ TM DIFSYS

0.01 0.01 0.2" d 0.2 0.2 0.01/0.2= 0.2

TR TR-EX CAL LWI

x = 0.4

x = 10

Rz.

R3n

x = 0.4

x = 0.4

Automatic step-size control. Unstable. h changed from 0.01 to 0.2 at x = 0.1. Initial step size 0.1, extrapolations performed until

< x = 15

x =0

x = 0.4

x = 10.

20 x = 10. CAL

3 h = 0.005 - 60 x =0

Time (sec)

- 0.17, x = 15. As

6.4,

DIFSYS

289

6.7. Numerical Experiments

CAL

CAL

6.4 COMPUTATIONAL RESULTSFOR EXAMPLE 3

RZ.

Rln

h

x

0.01

K4

DIFSYS TR-EX CAL

x = 10

x = 0.4

x = 10

0 0 2.9'0-2 4.310- 1 5.71,- 1 0 0 2.910-1

0.005 0.2" d 0.2 0.2

DEQ

= 0.4

0.2

16 41 5 12 2 44 4

(1

0.01 0.1,

h

x = 0.1.

0.2

<

4

As 0, 0,

0, 0, -

x =0

x = 40.

liL, ,l

0.04

2405

on x 2 16,

1, , .1i

x = 10,

x = 40 x = 0.012. DIFSYS

x = 0.358.

x

h

=

h = 0.001 by

CAL h = 0.02

x = 0.02.

6.5. All h = 0.001, E 138

0.001

x =0

h = 0.005 up

x =1

> 1. h = 0.05.

x

> 1, LWI

h,

W 0

TABLE 6.5 COMPUTATIONAL RESULTS FOR EXAMPLE 4

~

h

x = 0.4

x = 10

Automatic step size control. Unstable. Initial step size 0.1, extrapolations performed until error <

x = 0.4

x = 10

x = 0.4

x = 10

Time (set)

P

z

E

6.7.

29 1

Numerical Experiments

on h h 5 0.25. h 5 0.1.

x =0

x = 40

9.3

34

174.673.

h 20

0.02

23.3

1. bound. bound,

2. on

3.

h by h

4.

5.

292

6. Numerical Integration of Stiff ODEs

(m >

on

mx m

on

7094 10 0.083 1.5

20 0.533 11.2

30 1.684 60

40 3.917

50 7.567

-

-

REFERENCES 1.

on Cunad. J.

Eng. 46, 425

A

2.

IBM J.

Develop. 10, 292

3. 1968.

Proc. IFIP Congress,

4.

5. A

6.

IBM J .

Deu., 11, 537

7.

Proc. IFIP Congress,

8.

Proc.

IBM Scientific Computing Syniposiirm on Control Theory and Application, 1966.

9. J . SIAM Numer. Anal. 4, 372

293

References A,, IBM Research Report

10. 11.

NASA Technical Note,

12. 1968.

Proc. IFIP Congress,

13.

K., Univ. of Illinois Dept. of Computer Science Report,

14.

I., SIAM Rev. 1, 3

15.

16.

H. (J. C. k Math. Comp. 20, 39

274,

Index

A

11

12

122

13, 2

B 213 5 30

61 271, 285 82, 142, 214 185 207, 214 251, 258 45, 47, 51, 52, 55 199, 207

122 167, 212 268 264 257, 266 69

67 C

136 82

16 12

29 5

296

Index

D

108 251 119 199, 214 115 119, 121

279 17 203 245 137 143, 186, 208 36 205

H 25, 77, 115, 242 230 82, 91, 191, 213

E 140

199

123

11, 122 276 113

I 31 33

9 9

250 250

9 9

266 66

246 J

F 81 5

K

285

207, 214 214 G

214 20 43 199, 214, 281

82

L 30, 67, 210 54,

285

Index

297 P 131,

273,

275

109 18

113 231 282

3 44 140, 177, 271, 285

I.

214 162

50, 51, 53

190 55

M 248

T.

242 140 123 110

165 91

199 230 15 25, A. 30

191 12 16 226

N 230

160 208

5

5 2 20, 28, 149 14, 50

16 37

R

0

11

12

P., 245 44 A,, 179, 212 K., 283, 285

298

Index 284 244

54, 55, 82 108 36 16 113

245 136, 142, 145 73 35 36 28

113 A(@)-,117 113

119

65 114 114 45 56

114 10 122

4546, 47

130

4748 55

132, 113

54, 73, 82 50

ODES, 128 75 65, 136

150 P(EC)”

61 62 62

113

54 144

114 103 122 114 115 165, 172, 199, 214 83, 231 69, 82 54

286 282

299

Index 76-77

272-273 69-74 7476

276279 277-278 286-

30-33

5

29 1

162-163

274-275 284, 270-272 272

U

251, 258 C., 142

1719

27

V

T 3-4, 79-81 84 207, 214 137 9, 12, 122, 250-251 270-272 33-35, 242-243 69-77

22, 214 21

W 70, 285 83, 214 230 0. B., 117