Griffiths D.F., Higham D.J. Numerical Methods for Ordinary Differential Equations: Initial Value Problems

Подождите немного. Документ загружается.

256 D. Constant-Coeﬃcient Diﬀerence Equations

D.1 First-order Equations

Consider the ﬁrst-order linear constant-coeﬃcient problem:

n+1

= ax

+ b, n = 0, 1, . . . . (D.2)

By setting, in turn, n = 0, 1, 2 we can compute

= ax

+ b,

= ax

+ b = a

+ (a + 1)b,

= ax

+ b = a

+ (a

+ a + 1)b

and, continuing in the same vein, we can clearly compute any term in the

sequence x

, although the nature of the nth term m ay not be obvious.

A systematic approach ﬁrst considers the homogeneous equation x

n+1

for which x

= ax

, x

= ax

= a

and, by induction, the nth term is

= a

, for any value of x

. Setting x

= A, an arbitrary constant, the CF

is given by

= Aa

We next look for a particular solution. Since the right-hand side of (D.2) is con-

stant, we look for a PS in the form of a c onstant sequence x

= C. Substituting

= x

n+1

= C into (D.2) le ads to

C =

1 − a

, (a 6= 1).

Constan

t solutions are often referred to as ﬁxed points (FPs) of the 4E (see

Chapter 12—Long-Term Dynamics).

The sum of the CF and PS:

= Aa

1 − a

(a 6= 1), (D.

is seen, by substitution, to be a solution of (D.2). It can be proved that there

are no other solutions of this equation and that this is, therefore, the general

solution (GS) provided that a 6= 1.

When a = 1 the recurrence becomes

n+1

− x

= b,

so, by the telescoping series property,

= (x

− x

n−1

) + (x

n−1

− x

n−2

) + ··· + (x

− x

) + x

= b + b + ··· + b + x

= nb + x

D.2 Second-order Equations 257

Hence, the GS in this case is

= A + nb,

where A is an arbitrary constant.

Before proceeding to the solution of second-order equations, we note that

the GS of (D.2) allows us to ﬁnd the GS of the 4E

n+1

= ax

+ bk

, n = 0, 1, . . . (D.4)

by means of the substitution (known as the variation of constants) x

= k

We ﬁnd that y

satisﬁes

n+1





, (D.5)

which is of the form (D.2). By comparing with the solution of (D.2) it is readily

shown that (D.5) has GS







A(a/k)

b/k

1 − a/k

(a/k 6= 1),

A +

(b/k)n (a/k = 1).

Hence, using x

= k

, it is seen that (D.4) has GS







k − a

(a 6= k)

+ bnk

n−1

(a = k).

(D.6)

D.2 Second-order E quations

We begin by looking for the GS of the homogeneous equation

n+2

+ ax

n+1

+ bx

= 0. (D.7)

This equation will have solutions of the form x

= Ar

, where A is an arbitrary

constant, provided that r is a root of the quadratic equation

+ ar + b = 0, (D.8)

known as the auxiliary equation. Suppose that this equation has roots α and

β, then, since (r − α)(r − β) = r

− (α + β)r + αβ, it follows that

a = −(α + β), b = αβ.

Thus, the inhomogeneous 4E

n+2

+ ax

n+1

+ bx

= f

(D.9)

258 D. Constant-Coeﬃcient Diﬀerence Equations

may be written as x

n+2

− (α + β)x

n+1

+ αβx

= f

. That is,



n+2

− αx

n+1



− β



n+1

− αx



= f

By deﬁning y

= x

n+1

− αx

this becomes y

n+1

− βy

= f

and we have

succeeded in rewriting (D.9) as the ﬁrst-order system of 4Es

n+1

− αx

= y

n+1

− βy

= f

)

. (D.10)

In the homogeneous case f

≡ 0 the second of these has GS y

= Cβ

, where

C is an arbitrary constant, and then the ﬁrst becomes

n+1

− αx

= Cβ

This has the same form as (D.4) and so we can deduce its GS immediately

(

Aα

+ Bβ

(α 6= β)

(A + Bn)α

(α = β),

(D.11)

where A and B are arbitrary constants (B can be expressed in terms of α , β

and C).

Notice that, in the case that α = β and |α| = 1, then |x

| → ∞ in general

as n → ∞, and this is the reason that multiple roots lying on the unit circle

in the c omplex plane had to be excluded in the deﬁnition of the root condition

used for zero-stability (Deﬁnitions 5.4 and 5.5).

The only inhomogeneous case of (D.9) that we will consider is for a constant

forcing term, in which case f

≡ f for all n. Then, the se cond of (D.10) has GS







Cβ

1 − β

(β 6= 1),

C + nf (

β = 1).

When this is substituted into the right-hand side of the ﬁrst equation in (D.10)

we can employ a similar process to that in the previous section to ﬁnd











Aα

+ Bβ

(1 − α)(1 − β)

, (α 6= 1, β 6

= 1, α 6= β)

(A + Bn)α

(1 − α)

(α = β 6= 1),

Aα

+ B +

1 − α

n (α 6= β =

1),

An + Bβ

1 − β

n (β 6= α =

1),

A + Bn +

, (α = β = 1).

It may be veriﬁed by substitution that the last of these results, x

= A + Bn +

, satisﬁes x

n+2

− 2x

n+1

+ x

= f.

D.3 Higher Order Equations 259

D.3 Higher Order Equations

Seeking solutions of the homogeneous equation

n+k

+ a

k−1

n+k−1

+ ··· + a

= 0

in the form x

= Ar

requires r to be a root of the auxiliary equation

+ a

k−1

+ ··· + a

= 0. (D.12)

For each root r of this equation, supp os e that it has multiplicity m, then there

is a contribution

P (n)r

to the CF, where P (n) is a polynomial in n of degree m − 1 (and so contains

m arbitrary coeﬃcients). For example, when m = 1, the polynomial P (n) has

degree 0 and is, therefore, a constant (P (n) = A); when m = 2, the polynomial

P (n) has degree 1 and has the form P (n) = A + Bn. The full CF is the sum

of all such terms over all roots of the auxiliary equation.

EXERCISES

D.1.

Determine general solutions of the 4Es

(a) 2x

n+1

= x

+ 3, (b) x

n+1

= 2x

+ 3, (c) x

n+1

= x

+ 3.

Find also the solutions satisfying the initial condition x

= 5 in each

case. Discuss the behaviour of solutions as n → ∞.

D.2.

Use Equation (D.3) to show that the solution of (D.2) that satisﬁes

= η is given by

= ηa

+ b

1 − a

(a 6= 1). (D.

13)

By employing l’Hˆopital’s rule, show that this reduces to x

= η + nb

in the limit a → 1.

Verify this result by showing that (D.13) may be written

= ηa

+ b(1 + a + a

+ ··· + a

n−1

)

and then setting a = 1.

D.3.

Determine general solutions of the 4Es

a) 2x

n+1

= x

+ 3 × 2

260 D. Constant-Coeﬃcient Diﬀerence Equations

b) x

n+1

= 2x

+ 3 × 2

c) x

n+1

= x

+ 3 × 2

D.4.

Determine general solutions of the 4Es

(a) x

n+2

− 3x

n+1

− 4x

= 3, (b) x

n+2

− 3x

n+1

− 4x

= 3 × 2

n+2

− 4x

n+1

+ 4x

= 3, (d) x

n+2

− 4x

n+1

+ 4x

= 3 × 2

In case (a), ﬁnd the solution satisfying the starting conditions x

= 0

and x

= −1.

D.5.

Show that the auxiliary equation of the 4E

n+5

− 8x

n+4

+ 25x

n+3

− 38x

n+2

+ 28x

n+1

− 8x

= 0

can be factorized as (r − 2)

(r − 1)

= 0. Hence, ﬁnd the GS of the

4E.

Bibliography

[1] U. Alon. An Introduction to Systems Biology. Chapman & Hall/CRC,

London, 2006.

[2] U. M. Ascher and L. R. Petzold. Computer Methods for Ordinary Diﬀeren-

tial Equations and Diﬀerential-Algebraic Equations. SIAM, Philadelphia,

USA, 1998.

[3] W.-J. Beyn. Numerical methods for dynamical systems. In W. Light,

editor, Advances in Numerical Analysis, Vol. 1, pages 175–236. Clarendon

Press, 1991.

[4] P. Bogacki and L. F. Shampine. A 3(2) pair of Runge–Kutta formulas.

Appl. Math. Lett., 2:1–9, 1989.

[5] M. Braun. Diﬀerential Equations and their Applications. Springer-Verlag,

1983.

[6] J. C. Butcher. Numerical Methods for Ordinary Diﬀerential E quations.

Wiley, Chichester, UK, 2nd edition, 2008.

[7] B. Calderhead, M. Girolami, and D. J. Higham. Is it safe to go out yet?

Statistical inference in a zombie outbreak model. Technical Report 6,

University of Strathclyde, Glasgow, 2010. To appear in R. J. Smith?,

editor, “Mathematical Modelling of Zombies”, University of Ottawa Press.

[8] S. Chow and E. V. Vleck. A shadowing lemma approach to global error

analysis for initial value ODEs. SIAM J. Sci. Comput., 15:959–976, 1994.

[9] L. Cobb. Stochastic diﬀerential equations for the Social Sciences. In

L. Cobb and R. M. Thrall, editors, Mathematical Frontiers o f the Social

and Policy Sciences. Westview Press, 1981.

262 Bibliography

[10] G. J. Cooper. Stability of Runge–Kutta methods for trajectory problems.

IMA J. Numer. Anal., 7:1–13, 1987.

[11] J. C. Cox, J. E. Ingersoll, and S. A. Ross. A theory of the term s tructure

of interest rates. Econometrica, 53:385–407, 1985.

[12] A. Croft and R. Davidson. Mathematics for Engineers. Pearson/Prentice

Hall, Harlow, UK, 3rd edition, 2008.

[13] S. Cyganowski, P. Kloeden, and J. Ombach. From Elementary Proba bility

to Stochastic Diﬀeren tial Equations with MAPLE. Springer, Berlin, 2002.

[14] G. Dahlquist. Convergence and stability in the numerical integration of

ordinary diﬀerential equations. Math. Scand., 4:33–53, 1956.

[15] G. Dahlquist. Stability and error bounds in the numerical integration of

ordinary diﬀerential equations. Trans. of the R. Inst. Technol. Stockholm,

Sweden, (130):87pp, 1959.

[16] G. Dahlquist and A. Bj¨ork. Numerical Methods. Prentice Hall, 1974.

[17] G. Dahlquist and A. Bj¨ork. Numerical Methods in Scientiﬁc Computation.

SIAM, Philadelphia, USA, 2008.

[18] S. Elaydi. An Introduction to Diﬀerence Equations. Undergraduate Texts

in Mathematics. Springer-Verlag, 3rd edition, 2005.

[19] K. Eriksson, D. Estep, P. Hansbo, and C. Johnson. Computational Dif-

ferential Equations. Cambridge University Press, 1996.

[20] G. Fulford, P. Forrester, and A. Jones. Modelling with Diﬀerential and Dif-

ference Equations, volume 10 of Australian Mathematical Society Lecture

Series. Cambridge University Press, 1997.

[21] M. B. Giles. Multilevel Monte Carlo path simulation. Operations Research,

56:607–617, 2008.

[22] O. Gonzalez, D. J. Higham, and A. M. Stuart. Qualitative properties of

modiﬁed equations. IMA J. Numer. Anal., 19:169–190, 1999.

[23] A. Griewank. Evaluating Derivatives: Principles and Techniques of Algo-

rithmic Diﬀerentiation, volume 19 of Frontiers in Applied Mathematics.

SIAM, 2000.

[24] D. F. Griﬃths and J. M. Sanz-Serna. On the scope of the method of

modiﬁed equations. SIAM J. Sci. Stat. Comput., 7:994–1008, 1986.

[25] D. F. Griﬃths, P. K. Sweby, and H. C. Yee. On spurious asymptotic

numerical solutions of explicit Runge–Kutta methods. IMA J. Num. Anal.,

12:319–338, 1992.

Bibliography 263

[26] E. Hairer, C. Lubich, and G. Wanner. Geometric Numerical Integra-

tion: Structure-Preserving Algorithms for Ordinary Diﬀerential Equations.

Springer, Berlin, 2002.

[27] E. Hairer, C. Lubich, and G. Wanner. Geome tric numerical integration

illustrated by the St¨ormer–Verlet method. In A. Iserles, editor, Acta Nu-

merica, pages 399–450. Cambridge University Press, 2003.

[28] E. Hairer, S. P. Nørsett, and G. Wanner. Solving Ordinary Diﬀerential

Equations I: Nonstiﬀ P roblems. Springer-Verlag, Berlin, 2nd revised edi-

tion, 1993.

[29] E. Hairer and G. Wanner. Solving Ordinary Diﬀerential Equations II: Stiﬀ

and Diﬀerential-Algebraic Problems. Springer-Verlag, Berlin, 2nd edition,

1996.

[30] J. K. Hale and H. Kocak. Dynamics and Bifurcations. Springer, Berlin,

3rd edition, 1991.

[31] D. J. Higham. An algorithmic introduction to numerical simulation of

stochastic diﬀerential equations. SIAM Review, 43:525–546.

[32] D. J. Higham. An Introduction to Financial Option Valuation: Mathe-

matics, Stochastics and Computation. Cambridge University Press, Cam-

bridge, 2004.

[33] D. J. Higham. Modeling and simulating chemic al reactions. SIAM Rev.,

50:347–368, 2008.

[34] D. J. Higham and N. J. Higham. Matlab Guide. SIAM, Philadelphia,

USA, 2nd edition, 2005.

[35] D. J. Higham and L. N. Trefethen. Stiﬀness of ODEs. BIT Numer. Math.,

33:285–303, 1993.

[36] N. J. Higham. Accuracy and Stability of Numerical Algorithms. SIAM,

Philadelphia, 1996.

[37] N. J. Higham. Functions of Matrices: Theory and Computation. SIAM,

Philadelphia, PA, USA, 2008.

[38] K. E. Hirst. Calculus of One Variable. Springer (Springer Undergraduate

Mathematics Series), Berlin, 2006.

[39] A. Iserles. A First Course in the Numerical Analysis of Diﬀerential Equa-

tions. Cambridge University Press, 2nd edition, 2008.

[40] E. I. Jury. Theory and Application of the z-Transform Method. John Wiley

and Sons, 1964.

264 Bibliography

[41] C. T. Kelley. Iterative Methods for Linear and Nonlinear Equations, vol-

ume 16 of Frontiers in Applied Mathematics. SIAM, Philadelphia, USA,

1995.

[42] P. E. Kloeden and E. Platen. Numerical Solution of Stochastic Diﬀerential

Equations. Springer Verlag, Berlin, third printing, 1999.

[43] Y. K. Kwok. Mathematical Models of Financial Derivatives. Springer,

Berlin, 1998.

[44] J. D. Lambert. Numerical Methods in Ordinary Diﬀerential Systems. John

Wiley and Sons, Chichester, 1991.

[45] B. Leimkuhler and S. Reich. Simulating Hamiltonian Dynamics. Cam-

bridge University Press, 2004.

[46] D. Lesmono, E. J. Tonkes, and K. Burrage. An early political election

problem. In J. Crawford and A. J. Roberts, editors, Proceedings of 11th

Computational Techniques and Applications Conference CTAC-2003, vol-

ume 45, pages C16–C33, 2003.

[47] R. J. Leveque. Finite Diﬀerence Methods for Ordinary and Partial Diﬀer-

ential Equation. SIAM, Philadelphia, USA, 2007.

[48] D. J. Logan. A First Course in Diﬀerential Equations. Undergraduate

Texts in Mathematics. Springer-Verlag, 2006.

[49] X. Mao. Stochastic Diﬀerential Equations and Applications. Horwoo d,

Chichester, second edition, 2008.

[50] R. I. McLachlan and G. R. W. Quispel. Geometric integrators for ODEs.

J. Phys. A, 39:5251–5286, 2006.

[51] T. Mikosch. Elementary Stochastic Calculus (with Finance in View).

World Scientiﬁc, Singapore, 1998.

[52] G. N. Milstein and M. V. Tretyakov. Stochastic Numerics for Mathematical

Physics. Springer-Verlag, Berlin, 2004.

[53] C. B. Moler. Numerical Computing with Matlab. SIAM, 2004.

[54] K. W. Morton and D. F. Mayers. Numerical Solution of Partial Diﬀerential

Equations. Cambridge University Press, 2nd edition, 2005.

[55] P. Munz, I. Hudea, J. Imad, and R. J. Smith?. When zombies at-

tack!: Mathematical modelling of an outbreak of zombie infection. In

J. Tchuenche and C. Chiyaka, editors, Infectious Disease Modelling Re-

search Progress, pages 133–150, Nova, 2009.

Bibliography 265

[56] J. D. Murray. Mathematical Biology, volume 17 of Interdisciplinary Applied

Mathematics. Springer-Verlag, 3rd edition, 2002.

[57] R. K. Nagle, E. B. Saﬀ, and A. D. Snider. Fundamentals of Diﬀerential

Equations and Boundary Value Problems. Pearson Education Inc., 4th

edition, 2004.

[58] P. J. Nahin. Chases and Escapes: The Mathematics of Pursuit and Eva-

sion. Princeton University Press, Princeton, USA, 2007.

[59] R. E. O’Malley, Jr. Thinking About Ordinary Diﬀerential Equations, vol-

ume 18 of Cambridge Texts in Applied Mathematics. Cambridge University

Press, 1997.

[60] J. M. Sanz-Serna. Geometric integration. In I. S. Duﬀ and G. A. Watson,

editors, The State of the Art in Numerical Analysis, pages 121–143. Oxford

University Press, 1997.

[61] J. M. Sanz-Serna and M. P. Calvo. Numerical Hamiltonian Problems, vol-

ume 7 of Applied Mathematics and Mathematical Computation. Chapman

& Hall, 1994.

[62] L. F. Shampine. Numerical Solution of Ordinary Diﬀerential Equations.

Chapman & Hall, New York, USA, 1994.

[63] L. F. Shampine, I. Gladwell, and S. Thompson. Solving ODEs with Mat-

lab. Cambridge University Press, 2003. ISBN: 0-521-53094-6.

[64] J. Stewart. Calculus. Thomson Brooks/Cole, Belmont, USA, 6th edition,

2009.

[65] A. M. Stuart and A. R. Humphries. Dynamical Systems and Numerical

Analysis. Cambridge University Press, C ambridge, 1996.

[66] J. M. T. Thompson and H. B. Stewart. Nonlinear Dynamics an d Chaos,

Geometrical Methods for Engineers and Scientists. John Wiley and Sons,

2nd edition, 2002.

[67] L. N. Trefethen and M. Embree. Spectra and Pseudospectra: The Behav-

ior of Nonnormal Matrices and Operators. Princeton University Press,

Princeton, 2005.

[68] F. Verhulst. Nonlinear Diﬀerential Equations and Dynamical Systems.

Universitext. Springer-Verlag, 2nd edition, 1990.

[69] D. J. Wilkinson. Stocha stic Modelling for S ystems Biology. Chapman &

Hall/CRC, 2006.