Numerical Mathematics and Computing, Sixth Edition

Front Cover......Page 1
Title Page......Page 4
Copyright......Page 5
Contents......Page 10
1.1 Preliminary Remarks......Page 24
Significant Digits of Precision: Examples......Page 26
Accuracy and Precision......Page 28
Rounding and Chopping......Page 29
Nested Multiplication......Page 30
First Programming Experiment......Page 32
Mathematical Software......Page 33
Additional References......Page 34
Problems 1.1......Page 35
Computer Problems 1.1......Page 37
Taylor Series......Page 43
Complete Horner’s Algorithm......Page 46
Taylor’s Theorem in Terms of (x – c)......Page 47
Taylor’s Theorem in Terms of h......Page 49
Alternating Series......Page 51
Summary......Page 53
Problems 1.2......Page 54
Computer Problems 1.2......Page 59
2.1 Floating-Point Representation......Page 66
Normalized Floating-Point Representation......Page 67
Single-Precision Floating-Point Form......Page 69
Double-Precision Floating-Point Form......Page 71
Computer Errors in Representing Numbers......Page 73
Notation fl(x) and Backward Error Analysis......Page 74
Summary......Page 77
Problems 2.1......Page 78
Computer Problems 2.1......Page 82
Significant Digits......Page 84
Computer-Caused Loss of Significance......Page 85
Theorem on Loss of Precision......Page 86
Avoiding Loss of Significance in Subtraction......Page 87
Range Reduction......Page 90
Problems 2.2......Page 91
Computer Problems 2.2......Page 94
Introduction......Page 99
Bisection Algorithm and Pseudocode......Page 101
Examples......Page 102
Convergence Analysis......Page 104
False Position (Regula Falsi) Method and Modifications......Page 106
Problems 3.1......Page 108
Computer Problems 3.1......Page 110
3.2 Newton’s Method......Page 112
Interpretations of Newton’s Method......Page 113
Illustration......Page 115
Convergence Analysis......Page 116
Systems of Nonlinear Equations......Page 119
Fractal Basins of Attraction......Page 122
Additional References......Page 123
Problems 3.2......Page 124
Computer Problems 3.2......Page 128
3.3 Secant Method......Page 134
Secant Algorithm......Page 135
Convergence Analysis......Page 137
Fixed-Point Iteration......Page 140
Summary......Page 141
Problems 3.3......Page 142
Computer Problems 3.3......Page 144
Preliminary Remarks......Page 147
Polynomial Interpolation......Page 148
Interpolating Polynomial: Lagrange Form......Page 149
Interpolating Polynomial: Newton Form......Page 151
Nested Form......Page 153
Calculating Coefficients a[sub(i)] Using Divided Differences......Page 154
Algorithms and Pseudocode......Page 159
Vandermonde Matrix......Page 162
Inverse Interpolation......Page 164
Polynomial Interpolation by Neville’s Algorithm......Page 165
Interpolation of Bivariate Functions......Page 167
Summary......Page 168
Problems 4.1......Page 169
Computer Problems 4.1......Page 175
4.2 Errors in Polynomial Interpolation......Page 176
Runge Function......Page 177
Theorems on Interpolation Errors......Page 179
Summary......Page 183
Problems 4.2......Page 184
Computer Problems 4.2......Page 186
First-Derivative Formulas via Taylor Series......Page 187
Richardson Extrapolation......Page 189
First-Derivative Formulas via Interpolation Polynomials......Page 193
Second-Derivative Formulas via Taylor Series......Page 196
Summary......Page 197
Problems 4.3......Page 198
Computer Problems 4.3......Page 201
Definite and Indefinite Integrals......Page 203
Lower and Upper Sums......Page 204
Riemann-Integrable Functions......Page 206
Examples and Pseudocode......Page 207
Problems 5.1......Page 210
Computer Problems 5.1......Page 211
5.2 Trapezoid Rule......Page 213
Uniform Spacing......Page 214
Error Analysis......Page 215
Applying the Error Formula......Page 218
Recursive Trapezoid Formula for Equal Subintervals......Page 219
Multidimensional Integration......Page 221
Summary......Page 222
Problems 5.2......Page 223
Computer Problems 5.2......Page 226
Description......Page 227
Pseudocode......Page 228
Euler-Maclaurin Formula......Page 229
General Extrapolation......Page 232
Additional References......Page 234
Problems 5.3......Page 235
Computer Problems 5.3......Page 237
Basic Simpson’s Rule......Page 239
Simpson’s Rule......Page 242
Composite Simpson’s Rule......Page 243
An Adaptive Simpson’s Scheme......Page 244
Example Using Adaptive Simpson Procedure......Page 247
Newton-Cotes Rules......Page 248
Summary......Page 249
Problems 6.1......Page 250
Computer Problems 6.1......Page 252
Description......Page 253
Change of Intervals......Page 254
Gaussian Nodes and Weights......Page 255
Legendre Polynomials......Page 257
Summary......Page 260
Problems 6.2......Page 262
Computer Problems 6.2......Page 264
7.1 Naive Gaussian Elimination......Page 268
A Larger Numerical Example......Page 270
Algorithm......Page 271
Pseudocode......Page 273
Testing the Pseudocode......Page 276
Residual and Error Vectors......Page 277
Problems 7.1......Page 278
Computer Problems 7.1......Page 280
Naive Gaussian Elimination Can Fail......Page 282
Partial Pivoting and Complete Partial Pivoting......Page 284
Gaussian Elimination with Scaled Partial Pivoting......Page 285
A Larger Numerical Example......Page 288
Pseudocode......Page 289
Long Operation Count......Page 292
Summary......Page 294
Problems 7.2......Page 295
Computer Problems 7.2......Page 299
7.3 Tridiagonal and Banded Systems......Page 303
Tridiagonal Systems......Page 304
Strictly Diagonal Dominance......Page 305
Pentadiagonal Systems......Page 306
Block Pentadiagonal Systems......Page 308
Summary......Page 309
Problems 7.3......Page 310
Computer Problems 7.3......Page 311
8.1 Matrix Factorizations......Page 316
Numerical Example......Page 317
Formal Derivation......Page 319
Solving Linear Systems Using LU Factorization......Page 323
LDL[sup(T)] Factorization......Page 325
Cholesky Factorization......Page 328
Multiple Right-Hand Sides......Page 329
Example Using Software Packages......Page 330
Summary......Page 332
Problems 8.1......Page 334
Computer Problems 8.1......Page 339
Vector and Matrix Norms......Page 342
Condition Number and Ill-Conditioning......Page 344
Basic Iterative Methods......Page 345
Pseudocode......Page 350
Convergence Theorems......Page 351
Matrix Formulation......Page 354
Conjugate Gradient Method......Page 355
Summary......Page 358
Problems 8.2......Page 360
Computer Problems 8.2......Page 362
8.3 Eigenvalues and Eigenvectors......Page 365
Calculating Eigenvalues and Eigenvectors......Page 366
Mathematical Software......Page 367
Properties of Eigenvalues......Page 368
Gershgorin’s Theorem......Page 370
Singular Value Decomposition......Page 371
Numerical Examples of Singular Value Decomposition......Page 374
Application: Linear Differential Equations......Page 376
Application: A Vibration Problem......Page 377
Summary......Page 378
Problems 8.3......Page 379
Computer Problems 8.3......Page 381
8.4 Power Method......Page 383
Power Method Algorithms......Page 384
Aitken Acceleration......Page 386
Inverse Power Method......Page 387
Shifted (Inverse) Power Method......Page 388
Summary......Page 389
Problems 8.4......Page 390
Computer Problems 8.4......Page 391
9.1 First-Degree and Second-Degree Splines......Page 394
First-Degree Spline......Page 395
Modulus of Continuity......Page 397
Interpolating Quadratic Spline Q(x)......Page 399
Subbotin Quadratic Spline......Page 401
Summary......Page 403
Problems 9.1......Page 404
Computer Problems 9.1......Page 407
Introduction......Page 408
Natural Cubic Spline......Page 409
Algorithm for Natural Cubic Spline......Page 411
Pseudocode for Natural Cubic Splines......Page 415
Using Pseudocode for Interpolating and Curve Fitting......Page 416
Space Curves......Page 417
Smoothness Property......Page 419
Summary......Page 421
Problems 9.2......Page 422
Computer Problems 9.2......Page 426
9.3 B Splines: Interpolation and Approximation......Page 427
Interpolation and Approximation by B Splines......Page 433
Pseudocode and a Curve-Fitting Example......Page 435
Pseudocode......Page 437
Bézier Curves......Page 439
Summary......Page 441
Additional References......Page 442
Problems 9.3......Page 443
Computer Problems 9.3......Page 446
Initial-Value Problem: Analytical versus Numerical Solution......Page 449
Solving Differential Equations and Integration......Page 451
Vector Fields......Page 452
Taylor Series Methods......Page 454
Euler’s Method Pseudocode......Page 455
Taylor Series Method of Higher Order......Page 456
Summary......Page 458
Problems 10.1......Page 459
Computer Problems 10.1......Page 461
10.2 Runge-Kutta Methods......Page 462
Taylor Series for f (x, y)......Page 463
Runge-Kutta Method of Order 2......Page 464
Runge-Kutta Method of Order 4......Page 465
Pseudocode......Page 466
Summary......Page 467
Problems 10.2......Page 468
Computer Problems 10.2......Page 470
An Adaptive Runge-Kutta-Fehlberg Method......Page 473
An Industrial Example......Page 477
Adams-Bashforth-Moulton Formulas......Page 478
Stability Analysis......Page 479
Summary......Page 482
Problems 10.3......Page 483
Computer Problems 10.3......Page 484
Uncoupled and Coupled Systems......Page 488
Taylor Series Method......Page 489
Vector Notation......Page 490
Taylor Series Method: Vector Notation......Page 491
Runge-Kutta Method......Page 492
Autonomous ODE......Page 494
Summary......Page 496
Problems 11.1......Page 497
Computer Problems 11.1......Page 498
Higher-Order Differential Equations......Page 500
Autonomous ODE Systems......Page 502
Problems 11.2......Page 503
Computer Problems 11.2......Page 505
A Predictor-Corrector Scheme......Page 506
Pseudocode......Page 507
An Engineering Example......Page 511
Some Remarks about Stiff Equations......Page 512
Summary......Page 514
Computer Problems 11.3......Page 515
Linear Least Squares......Page 518
Linear Example......Page 521
Nonpolynomial Example......Page 522
Basis Functions {g[sub(0)], g[sub(1)], . . . , g[sub(n)]}......Page 523
Summary......Page 524
Problems 12.1......Page 525
Orthonormal Basis Functions {g[sub(0)], g[sub(1)], . . . , g[sub(n)]}......Page 528
Outline of Algorithm......Page 531
Smoothing Data: Polynomial Regression......Page 533
Summary......Page 538
Problems 12.2......Page 539
Computer Problems 12.2......Page 540
12.3 Other Examples of the Least-Squares Principle......Page 541
Use of a Weight Function w (x)......Page 542
Nonlinear Example......Page 543
Linear and Nonlinear Example......Page 544
Additional Details on SVD......Page 545
Using the Singular Value Decomposition......Page 547
Problems 12.3......Page 550
Computer Problems 12.3......Page 553
13.1 Random Numbers......Page 555
Random-Number Algorithms and Generators......Page 556
Examples......Page 558
Uses of Pseudocode Random......Page 560
Problems 13.1......Page 564
Computer Problems 13.1......Page 565
Numerical Integration......Page 567
Example and Pseudocode......Page 568
Computing Volumes......Page 570
Ice Cream Cone Example......Page 571
Computer Problems 13.2......Page 572
Loaded Die Problem......Page 575
Birthday Problem......Page 576
Buffon’s Needle Problem......Page 578
Two Dice Problem......Page 579
Neutron Shielding......Page 580
Additional References......Page 581
Computer Problems 13.3......Page 582
14.1 Shooting Method......Page 586
Shooting Method Algorithm......Page 588
Summary......Page 590
Problems 14.1......Page 591
Finite-Difference Approximations......Page 593
The Linear Case......Page 594
Pseudocode and Numerical Example......Page 595
Shooting Method in the Linear Case......Page 597
Pseudocode and Numerical Example......Page 598
Summary......Page 600
Problems 14.2......Page 601
Computer Problems 14.2......Page 603
Some Partial Differential Equations from Applied Problems......Page 605
Finite-Difference Method......Page 608
Pseudocode for Explicit Method......Page 610
Crank-Nicolson Method......Page 611
Pseudocode for the Crank-Nicolson Method......Page 612
Alternative Version of the Crank-Nicolson Method......Page 613
Stability......Page 614
Summary......Page 616
Problems 15.1......Page 617
Wave Equation Model Problem......Page 619
Analytic Solution......Page 620
Numerical Solution......Page 621
Pseudocode......Page 623
Advection Equation......Page 624
Lax-Wendroff Method......Page 625
Summary......Page 626
Computer Problems 15.2......Page 627
Helmholtz Equation Model Problem......Page 628
Finite-Difference Method......Page 629
Numerical Example and Pseudocode......Page 633
Finite-Element Methods......Page 636
More on Finite Elements......Page 640
Summary......Page 642
Problems 15.3......Page 643
Computer Problems 15.3......Page 645
Unconstrained and Constrained Minimization Problems......Page 648
One-Variable Case......Page 649
Unimodal Functions F......Page 650
Fibonacci Search Algorithm......Page 651
Golden Section Search Algorithm......Page 654
Quadratic Interpolation Algorithm......Page 656
Problems 16.1......Page 658
Computer Problems 16.1......Page 660
16.2 Multivariate Case......Page 662
Taylor Series for F: Gradient Vector and Hessian Matrix......Page 663
Alternative Form of Taylor Series......Page 664
Steepest Descent Procedure......Page 666
More Advanced Algorithms......Page 667
Minimum, Maximum, and Saddle Points......Page 669
Nelder-Mead Algorithm......Page 670
Method of Simulated Annealing......Page 671
Summary......Page 673
Problems 16.2......Page 674
Computer Problems 16.2......Page 677
First Primal Form......Page 680
Numerical Example......Page 681
Transforming Problems into First Primal Form......Page 683
Dual Problem......Page 684
Second Primal Form......Page 686
Summary......Page 687
Problems 17.1......Page 688
Computer Problems 17.1......Page 692
17.2 Simplex Method......Page 693
Vertices in K and Linearly Independent Columns of A......Page 694
Simplex Method......Page 695
Problems 17.2......Page 697
17.3 Approximate Solution of Inconsistent Linear Systems......Page 698
l[sub(1)] Problem......Page 699
l[sub(∞)] Problem......Page 701
Summary......Page 703
Computer Problems 17.3......Page 705
A.1 Programming Suggestions......Page 707
Case Studies......Page 710
On Developing Mathematical Software......Page 714
B.1 Representation of Numbers in Different Bases......Page 715
Conversion of Integer Parts......Page 716
Conversion of Fractional Parts......Page 718
Base Conversion 10 ↔ 8 ↔ 2......Page 719
More Examples......Page 721
Problems B.1......Page 722
Computer Problems B.1......Page 724
C.1 More on IEEE Standard Floating-Point Arithmetic......Page 726
Vectors......Page 729
Matrices......Page 731
Matrix Product......Page 734
Other Concepts......Page 736
Cramer’s Rule......Page 738
D.2 Abstract Vector Spaces......Page 739
Linear Independence......Page 740
Linear Transformations......Page 741
Change of Basis and Similarity......Page 742
Orthogonal Matrices and Spectral Theorem......Page 743
Norms......Page 744
Gram-Schmidt Process......Page 745
Answers for Selected Problems......Page 747
Bibliography......Page 768
Index......Page 777