CHAPTER 1 Numerical Computation 1
1.1 Motivation and Objectives 1
1.1.1 A Simple Calculation 1
1.1.2 Chapter Objectives 2
1.1.3 Mathematical Background 3
1.2 Number Representation 3
1.2.1 Binary,Decimal,and Hexadecimal 3
1.2.2 Integers 6
1.2.3 Floats 7
1.3 Machine Precision 8
1.4 Round-Off Error 10
1.4.1 Chopping and Rounding 10
1.4.2 Error Propagation 11
1.5 Truncation Error 14
1.6 Random Number Generation 15
1.6.1 Uniform Distribution 15
1.6.2 Gaussian Distribution 19
1.7 Numerical Software 22
1.7.1 A Numerical Library:NLIB 23
1.7.2 NLIB Example Browser 24
1.7.3 Pseudo-Prototypes 25
1.8 Applications 26
1.8.1 Throwing Darts to Estimate π:MATLAB 26
1.8.2 Monte Carlo Integration:C 29
1.9 Summary 32
Problems 34
1.10.1 Analysis 34
1.10.2 Computation 35
CHAPTER 2 Linear Algebraic Systems 37
2.1 Motivation and Objectives 37
2.1.1 Robotic Arm 38
2.1.2 Converter Circuit 38
2.1.3 DC Motor 39
2.1.4 Chapter Objectives 40
2.2 Gauss-Jordan Elimination 41
2.3 Gaussian Elimination 50
2.4 LU Decomposition 54
2.5.1 LU Factorization 55
2.5.2 Forward and Back Substitution 59
2.5.3 Tridiagonal Systems 62
2.5 Ill-Conditioned Systems 64
2.5.1 Vector and Matrix Norms 64
2.5.2 Condition Number 66
2.5.3 Approximate Condition Number 68
2.5.4 Iterative Improvement 69
2.6 Iterative Methods 70
2.6.1 Jacobi's Method 71
2.6.2 Gauss-Seidel Method 73
2.6.3 Relaxation Methods 74
2.6.4 Convergence 77
2.7 Applications 79
2.7.1 Chemical Absorption Process:MATLAB 79
2.7.2 Planar Truss:C 82
2.7.3 DC Bridge Circuit:MATLAB 84
2.7.4 Mass-Spring-Damper System:C 86
2.8 Summary 89
Problems 91
2.9.1 Analysis 91
2.9.2 Computation 93
CHAPTER 3 Eigenvalues and Eigenvectors 96
3.1 Motivation and Objectives 97
3.1.1 Seismograph 97
3.1.2 Convergence of Iterative Methods 99
3.1.3 Chapter Objectives 101
3.2 The Characteristic Polynomial 102
3.3 Power Methods 105
3.3.1 Direct Power Method 105
3.3.2 Inverse Power Method 109
3.4 Jacobi's Method 111
3.5 Householder Transformation 113
3.6 QR Method 116
3.6.1 Deflation 118
3.6.2 Shifting 119
3.7 Danilevsky's Method 120
3.8 Polynomial Roots 124
3.9 Applications 126
3.9.1 Transient Analysis of an Absorption Process:C 126
3.9.2 Population Growth Model:MATLAB 130
3.9.3 Telescope Position Control:C 133
3.9.4 Rotating Masses and Torsional Springs:MATLAB 136
3.10 Summary 140
Problems 141
3.11.1 Analysis 142
3.11.2 Computation 143
CHAPTER 4 Curve Fitting 145
4.1 Motivation and Objectives 146
4.1.1 Gravitational Acceleration 146
4.1.2 Circadian Rhythms 147
4.1.3 Chapter Obiectives 148
4.2 Interpolating 149
4.2.1 Piecewise-Linear Interpolation 150
4.2.2 Polynomial Interpolation 151
4.2.3 Lagrange Interpolation Polynomials 153
4.2.4 Polynomials 155
4.3 Newton's Difference Formula 156
4.4 Cubic Splines 158
4.5 Least Squares 165
4.5.1 Straight Line Fit 166
4.5.2 Polynomial Fit 168
4.5.3 Orthogonal Polynomials 168
4.6 Two-Dimensional Interpolation 174
4.7 Applications 177
4.7.1 Pressure-Temperature Curves:MATLAB 177
4.7.2 Water Resource Management:C 180
4.7.3 Voltage Regulator Circuit:MATLAB 182
4.7.4 Nonlinear Friction Model:C 185
4.8 Summary 188
Problems 189
4.9.1 Analysis 190
4.9.2 Computation 191
CHAPTER 5 Root Finding 193
5.1 Motivation and Objectives 194
5.1.1 Tunnel Diode Circuit 194
5.1.2 Leaky Tank 196
5.1.3 Bacterial Chemostat 197
5.1.4 Chapter Objectives 198
5.2 Bracketing Methods 199
5.2.1 Bisection Method 199
5.2.2 False Position Method 202
5.3 Contraction Mapping Method 205
5.3.1 Root Finding 207
5.3.2 Aitken Extrapolation 209
5.4 Secant Method 210
5.5 Muller's Method 212
5.6 Newton's Method 216
5.7 Polynomial Roots 219
5.7.1 Quadratic Formula 219
5.7.2 Synthetic Division 221
5.7.3 Laguerre's Method 224
5.8 Nonlinear Systems of Equations 228
5.9 Applications 232
5.9.1 Propane Cylinder:C 232
5.9.2 Bacterial Chemostat:MATLAB 236
5.9.3 Industrial High-Temperature Oven:C 238
5.9.4 Suspension Cable:MATLAB 241
5.10 Summary 244
Problems 246
5.11.1 Analysis 246
5.11.2 Computation 247
CHAPTER 6 Optimization 250
6.1 Motivation and Objectives 251
6.1.1 Nonlinear Regression 251
6.1.2 Electrical Load Design 252
6.1.3 Container Design 253
6.1.4 Chapter Objectives 254
6.2 Local and Global Minima 255
6.3 Line Searches 257
6.3.1 Golden Section 257
6.3.2 Derivative Bisection 262
6.3.3 Inverse Parabolic Interpolation 263
6.4 Steepest Descent Method 265
6.5 Conjugate-Gradient Method 268
6.6 Quasi-Newton Methods 270
6.7 Penalty Functions 274
6.8 Simulated Annealing 278
6.8.1 Annealing Schedules 280
6.8.2 Constrained Optimization 281
6.9 Applications 286
6.9.1 Heat Exchanger:MATLAB 286
6.9.2 Transportation Planning:C 291
6.9.3 Maximum Power Extraction:MATLAB 295
6.9.4 Container Design:C 298
6.10 Summary 300
Problems 302
6.11.1 Analysis 302
6.11.2 Computation 304
CHAPTER 7 Differentiation and Integration 307
7.1 Motivation and Objectives 308
7.1.1 Magnetic Levitation 308
7.1.2 Mechanical Work 309
7.1.3 Water Management 310
7.1.4 Chapter Objectives 311
7.2 Numerical Differentiation 312
7.2.1 First Derivative 312
7.2.2 Second Derivative 315
7.2.3 Richardson Extrapolation 317
7.3 Noise-Corrupted Data 319
7.4 Newton-Cotes Integration Formulas 321
7.4.1 Trapezoid Rule 323
7.4.2 Simpson's Rules 324
7.4.3 Midpoint Rule 325
7.5 Romberg Integration 328
7.6 Gauss Quadrature 331
7.6.1 Legendre Polynomials 332
7.6.2 Chebyshev Polynomials 334
7.6.3 Laguerre Polynomials 335
7.6.4 Hermite Polynomials 336
7.7 Improper Integrals 337
7.8 Multiple Integrals 340
7.8.1 Parameterization Method 340
7.8.2 Monte Carlo Integration 342
7.9 Applications 345
7.9.1 Change in Enthalpy:C 345
7.9.2 Dam Design:MATLAB 347
7.9.3 RC Network:C 350
7.9.4 Link of Robotic Arm:MATLAB 353
7.10 Summary 354
Problems 357
7.11.1 Analysis 357
7.11.2 Computation 358
CHAPTER 8 Ordinary Differential Equations 361
8.1 Motivation and Objectives 362
8.1.1 Satellite Attitude Control 363
8.1.2 Pendulum 364
8.1.3 Predator-Prey Ecological System 364
8.1.4 Chapter Objectives 365
8.2 Euler's Method 366
8.3 Runge-Kutta Methods 368
8.4 Step Size Control 372
8.4.1 Interval Halving 373
8.4.2 Runge-Kutta-Fehlberg Method 374
8.4.3 Step Size Adjustment 375
8.5 MultiStep Methods 378
8.5.1 Adams-Bashforth Predictor 378
8.5.2 Adams-Moulton Corrector 379
8.6 Bulirsch-Stoer Extrapolation Methods 382
8.6.1 Modified Midpoint Method 382
8.6.2 Richardson Extrapolation 383
8.7 Stiff Differential Equations 387
8.7.1 Implicit Methods 389
8.7.2 Semi-Implicit Extrapolation Method 391
8.7.3 Differential-Algebraic Systems 394
8.8 Boundary Value Problems 395
8.8.1 Shooting Method 396
8.8.2 Finite Difference Method 398
8.9 Applications 401
8.9.1 Chemical Reactor:MATLAB 401
8.9.2 Cantilever Beam:C 404
8.9.3 Phase-Locked Loop:MATLAB 406
8.9.4 Turbulent Flow and Chaos:C 410
8.10 Summary 413
Problems 415
8.11.1 Analysis 415
8.11.2 Computation 416
CHAPTER 9 Partial Differential Equations 422
9.1 Motivation and Obiectives 423
9.1.1 Laplace's Equation 423
9.1.2 Heat Equation 424
9.1.3 Wave Equation 425
9.1.4 Equation Classification 426
9.1.5 Chapter Objectives 427
9.2 Elliptic Equations 428
9.2.1 Central Difference Method 428
9.2.2 Boundary Conditions 431
9.2.3 Iterative Solution Methods 432
9.3 One-Dimensional Parabolic Equations 437
9.3.1 Explicit Forward Euler Method 437
9.3.2 Implicit Backward Euler Method 440
9.3.3 Crank-Nicolson Method 442
9.4 Two-Dimensional Parabolic Equations 444
9.5 One-Dimensional Hyperbolic Equations 448
9.5.1 d'Alembert's Solution 449
9.5.2 Explicit Central Difference Method 452
9.6 Two-Dimensional Hyperbolic Equations 455
9.7 Applications 459
9.7.1 Heated Rod:C 460
9.7.2 Plate Deflection:MATLAB 462
9.7.3 Electrostatic Field:C 464
9.7.4 Twisted Bar:MATLAB 466
9.8 Summary 468
Problems 469
9.9.1 Analysis 469
9.9.2 Computation 472
CHAPTER 10 Digital Signal Processing 475
10.1 Motivation and Objectives 476
10.1.1 Harmonic Distortion 476
10.1.2 Radar 477
10.1.3 Chapter Objectives 477
10.2 Fourier Transform 478
10.3 Fast Fourier Transform(FFT) 480
10.4 Correlation 487
10.5 Convolution 490
10.5.1 Pulse Response 491
10.5.2 Stability 493
10.6 Digital Filters 495
10.6.1 Frequency Response 495
10.6.2 FIR Filter Design 497
10.7 Two-Dimensional FFT 502
10.8 System Identification 506
10.8.1 Least-Squares Method 507
10.8.2 Adaptive LMS Method 511
10.9 Applications 514
10.9.1 Heat Exchanger Frequency Response:MATLAB 514
10.9.2 Flagpole Motion:C 516
10.9.3 Band Pass Filter:MATLAB 519
10.9.4 Helicopter Noise:C 522
10.10 Summary 524
Problems 526
10.11.1 Analysis 526
10.11.2 Computation 527
References and Further Reading 530
APPENDIX 1 NLIB Using MATLAB 533
1.1 A Numerical Toolbox:NLIB 534
1.1.1 Toolbox Installation 534
1.1.2 NLIB Example Browser 535
1.2 Main-Program Support 536
1.2.1 Tabular Display 536
1.2.2 Graphical Display 538
1.2.3 Utility Functions 542
1.3 Linear Algebraic Systems 544
1.4 Eigenvalues and Eigenvectors 548
1.5 Curve Fitting 552
1.6 Root Finding 555
1.7 Optimization 558
1.8 Differentiation and Integration 563
1.9 Ordinary Differential Equations 567
1.10 Partial Differential Equations 571
1.11 Digital Signal Processing 578
APPENDIX 2 NLIB Using C 584
2.1 A Numerical Library:NLIB 585
2.1.1 NLIB Installation 585
2.1.2 Library Usage 585
2.1.3 NLIB Example Browser 587
2.2 NLIB Data Types 588
2.2.1 Scalars 588
2.2.2 Vectors 588
2.2.3 Matrices 589
2.2.4 Precision 590
2.3 NLIB Core 591
2.3.1 Vector and Matrix Allocation 591
2.3.2 Vector and Matrix Input/Output 594
2.3.3 Matrix Algebra 598
2.3.4 Complex Arithmetic 600
2.3.5 Random Number Generation 602
2.3.6 Utility Functions 604
2.4 Tabular Display 605
2.4.1 Screen 605
2.4.2 Keyboard 606
2.4.3 Printer 607
2.5 Graphical Display 608
2.5.1 Curves 609
2.5.2 Surfaces 612
2.6 Linear Algebraic Systems 614
2.7 Eigenvalues and Eigenvectors 619
2.8 Curve Fitting 623
2.9 Root Finding 626
2.10 Optimization 631
2.11 Differentiation and Integration 637
2.12 Ordinary Differential Equations 641
2.13 Partial Differential Equations 646
2.14 Digital Signal Processing 653
APPENDIX 3 Vectors and Matrices 661
3.1 Vector and Matrix Notation 661
3.2 Basic Operations 663
3.3 Matrix Inverse 665
3.4 Eigenvalues and Eigenvectors 666
3.5 Vector Norms 668
APPENDIX 4 Answers to Selected Problems 669
Index 703