Difference equations : from rabbits to chaos / Paul Cull, Mary Flahive, Robby Robson.

Format:

Book

Author/Creator:

Cull, Paul, 1943-

Contributor:

Flahive, Mary E., 1948-

Robson, Robert O., 1954-

Series:

Undergraduate texts in mathematics

Language:

English

Subjects (All):

Difference equations.

Physical Description:

xiii, 392 pages : illustrations ; 25 cm.

Place of Publication:

New York : Springer, [2005]

Summary:

Difference equations are models of the world around us. From clocks to computers to chromosomes, processing discrete objects in discrete steps is a common theme. Difference equations arise naturally from such discrete descriptions and allow us to pose and answer such questions as: How much? How many? How long? Difference equations are a necessary part of the mathematical repertoire of all modern scientists and engineers.

In this new text, designed for sophomores studying mathematics and computer science, the authors cover the basics of difference equations and some of their applications in computing and in population biology. Each chapter leads to techniques that can be applied by hand to small examples or programmed for larger problems. Along the way, the reader will use linear algebra and graph theory, develop formal power series, solve combinatorial problems, visit Perron-Frobenius theory, discuss pseudorandom number generation and integer factorization, and apply the Fast Fourier Transform to multiply polynomials quickly.

The book contains many worked examples and over 250 exercises. While these exercises are accessible to students and have been class-tested, they also suggest further problems and possible research topics.

Contents:

Computation vii

Notational Preliminaries viii

1 Fibonacci Numbers 1

1.1 The Rabbit Problem 1

1.2 The Fibonacci Sequence 2

1.2.1 Computing Fibonacci numbers 4

1.2.2 A formula for the Fibonacci numbers 5

1.2.3 Further Fibonacci facts 6

1.3 Notation for Asymptotic Analysis 6

2 Homogeneous Linear Recurrence Relations 11

2.1 The Solution Space of (HL) 12

2.2 The Matrix Form 15

2.3 A Simpler Basis for the Solution Space 17

2.3.1 Distinct eigenvalues 19

2.3.2 Repeated eigenvalues 21

2.4 The Asymptotic Behavior of Solutions 25

3 Finite Difference Equations 33

3.1 Linear Difference Equations 33

3.1.1 First-order equations 34

3.2 General and Particular Solutions 36

3.2.1 Finding a particular solution via summation 39

3.3 A Special Class of Linear Recurrences 41

3.4 Operator Notation 45

3.5 The Shift Operator on the Space of Sequences 47

3.6 Formal Power Series 50

3.6.1 Formal differentiation 55

3.6.2 An application of formal power series 56

4 Generating Functions 67

4.1 Counting Strings with Some Restrictions 67

4.2 An Overview of the Generating Function Technique 70

4.2.1 Rational representation 75

4.3 A Review of Partial Fractions 76

4.4 Examples of the Generating Function Technique 82

4.4.1 The Catalan numbers 83

4.4.2 Stirling numbers of the second kind 85

4.5 Reversion of Generating Functions 87

4.5.1 Using the Fourier Transform 91

5 Nonnegative Difference Equations 101

5.1 Nonnegative Polynomials 102

5.1.1 The dominant root 102

5.2 When are integer solutions rounded powers of an eigenvalue? 106

5.2.1 Using the Rounding Theorem 110

5.3 Estimation of the Roots 113

5.3.1 Estimation of the dominant root 113

5.3.2 Estimation of the second root 113

5.4 Calculation of the Roots 116

5.4.1 The rate of convergence in Newton's method 121

5.5 Asymptotic Size of Solutions 125

5.5.1 Homogeneous nonnegative recurrences 125

5.5.2 Nonhomogeneous nonnegative equations 127

6 Leslie's Population Matrix Model 137

6.1 Leslie's Model 137

6.1.1 How to tell whether a Leslie matrix is primitive 141

6.2 Leslie's Convergence Theorem 142

6.3 Imprimitive Leslie Matrices 144

6.3.2 A special case: Only one positive fertility rate 145

6.3.3 Asymptotically periodic Leslie matrices 145

6.4 Companion Matrices 147

6.4.1 Matrices with repeated eigenvalues 155

6.5 Nonnegative Companion Matrices 157

6.5.1 Periodic nonnegative companion matrices 159

6.6 Back to Leslie Matrices 164

6.6.1 Periodic Leslie matrices 165

6.6.2 Averaging 168

6.7 The Limiting Effect of L on Nonnegative Vectors 169

6.7.1 The period of the total population 171

7 Matrix Difference Equations 179

7.1 Homogeneous Matrix Equations 179

7.2 Nonnegative Matrix Equations 186

7.2.1 Applications to Markov chains 187

7.3 Graphs and Matrices 189

7.3.1 Next node representation 193

7.3.2 Comments on imprimitivity 194

7.4 Algorithms for Primitivity 198

7.4.1 Algorithm I 198

7.4.2 Algorithm II 202

7.5 Matrix Difference Equations with Input 206

7.5.1 Reduction to one dimension 207

7.5.2 Reduction to homogeneous form 211

8 Modular Recurrences 217

8.1 Periodicity 218

8.1.1 Periodicity of linear modular recurrences 221

8.1.2 Fast modular computations 224

8.2 Finite Fields 225

8.3 Periods of First-Order Modular Recurrences 227

8.3.1 First-order modular recurrences with maximal period 230

8.4 Periodic Second-Order Modular Recurrences 232

8.4.1 Periods of modular Fibonacci sequences 233

8.5 Applications 238

8.5.1 Application 1: Pseudorandom number generation 238

8.5.2 Application 2: Integer factorization 242

9 Computational Complexity 253

9.1 Analysis of Algorithms 254

9.1.1 Measuring run time 254

9.1.2 An example: The Towers of Hanoi puzzle 256

9.2 Computer Arithmetic 261

9.2.1 Addition and subtraction 262

9.2.2 Multiplication and division 262

9.3 An Introduction to Divide-and-Conquer 263

9.3.1 Example: Polynomial multiplication 264

9.4 Simple Divide-and-Conquer Algorithms 268

9.4.1 Example 1: A return to polynomial multiplication 270

9.4.2 Example 2: Matrix multiplication 271

9.4.3 Example 3: MERGESORT 272

9.4.4 Example 4: Applications of Newton's method 273

9.5 The Fast Fourier Transform 274

9.5.1 The general form of the Fast Fourier Transform 276

9.5.2 The FFT when n = 2[superscript k] 277

9.5.3 Fast evaluation and fast interpolation 280

9.5.4 The fast polynomial multiplication algorithm 281

9.6 Average Case Analysis 284

9.6.1 The LARGETWO algorithm 284

9.6.2 The QUICKSORT algorithm 286

10 Some Nonlinear Recurrences 297

10.2 Nonlinear Systems 299

10.2.1 Sarkovskii's Theorem 302

10.3 Chaos 303

10.3.1 A simple chaotic system 303

10.4 Local Stability 307

10.4.1 Local stability of a fixed point 307

10.4.2 Local stability of a cycle 308

10.4.3 Local stability in two dimensions 310

10.5 Global Stability 313

10.5.1 Staircase convergence 314

10.5.2 Nonmonotonic convergence 315

10.6 Linear Fractional Recurrences 317

10.6.1 Asymptotic behavior 318

10.6.2 Rational coefficients and periodicity 322

10.6.3 Chaotic-like behavior 324

10.6.4 Invariant distributions 326

10.6.5 Proving global stability 330

A Worked Examples 337

A.1 All Simple Roots 337

A.2 One Multiple Root 342

A.3 One Multiple Root, Several Simple Roots 345

A.4 The Input is [gamma superscript n subscript 1]p[subscript 1](n) + [gamma superscript n subscript 2]p[subscript 2](n) 346

B Complex Numbers 347

C Highlights of Linear Algebra 353

C.1 Vector Spaces and Subspaces 353

C.2 Linear Independence and Basis 354

C.3 Linear Transformations 355

C.4 Eigenvectors 356

C.5 Characteristic and Minimal Polynomials 358

D Roots in the Unit Circle 361

D.1 Marden's Method 362.

Notes:

Includes bibliographical references (pages [369]-380) and index.

ISBN:

0387232338

0387232346

OCLC:

56615855