Explorations in numerical analysis

Author

• Lambers, James V.

Additional Author(s)

• Sumner, Amber C.

Publisher

New Jersey: World Scientific Publishing Co. Pte. Ltd., 2019

Language

English

ISBN

9789813209978

Series

Subject(s)

• NUMERICAL ANALYSIS
• NUMERICAL ANALYSIS-COMPUTER PROGRAMS
• NUMERICAL ANALYSIS-DATA PROCESSING

Notes

. Include bibliographical references (p. 641-648).

Abstract

This book evolved over a period of several years from lecture notes written by the first author. The original notes for a course at Stanford University in 2001 were based on [Golub and Ortega (1993)], then significantly expanded at the University of California at Irvine in 2004, influenced by [Burd en and Faires (2004)]. At the University of Southern Mississippi, additional notes for undergraduate and graduate courses taught by both authors, and guided by textbooks in numerical analysis[Ascher and Greif (2011); Burden and Faires (2004); Sauer (2012); S¨uli and Mayers(2003)], as well as numerical linear algebra [Demmel (1997); Golub and van Loan(2012)], and numerical methods for partial differential equations [Leveque (2007);Trefethen (2000)], completed the foundation for this book. It is written for a year-long sequence of numerical analysis courses for either advanced undergraduate or beginning graduate students. Part II is suitable for a semester-long first course on numerical linear algebra.~Publisher.

Physical Dimension

Number of Page(s)

xv, 658 p.

Dimension

25 cm.

Other Desc.

ill.

Summary / Review / Table of Content

Contents
Preface vii
Part I Preliminaries 1
1. What is Numerical Analysis? 3
1.1 Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.2 Getting Started with MATLAB . . . . . . . . . . . . . . . . . . . 11
1.3 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 42
2. Understanding Error 45
2.1 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
2.2 Computer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . 59
2.3 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.4 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
Part II Numerical Linear Algebra 75
3. Direct Methods for Linear Systems 77
3.1 Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3.2 The LU Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.3 Special Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
3.4 Estimating and Improving Accuracy . . . . . . . . . . . . . . . . . 113
3.5 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 119
3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4. Least Squares Problems 123
4.1 The Full Rank Least Squares Problem . . . . . . . . . . . . . . . . 123
4.2 Computing the QR Factorization . . . . . . . . . . . . . . . . . . . 129
4.3 Rank-Deficient Least Squares . . . . . . . . . . . . . . . . . . . . . 148
xi
.4 The Singular Value Decomposition . . . . . . . . . . . . . . . . . . 154
4.5 Other Least Squares Problems* . . . . . . . . . . . . . . . . . . . . 160
4.6 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 166
4.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
5. Iterative Methods for Linear Systems 169
5.1 Stationary Iterative Methods . . . . . . . . . . . . . . . . . . . . . 170
5.2 Gradient Descent Methods . . . . . . . . . . . . . . . . . . . . . . . 175
5.3 Other Krylov Subspace Methods* . . . . . . . . . . . . . . . . . . . 185
5.4 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 192
5.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193
6. Eigenvalue Problems 197
6.1 Eigenvalues and Eigenvectors . . . . . . . . . . . . . . . . . . . . . 197
6.2 Power It er at i ons . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211
6.3 The QR Algorithm* . . . . . . . . . . . . . . . . . . . . . . . . . . 216
6.4 The Symmetric Eigenvalue Problem* . . . . . . . . . . . . . . . . . 227
6.5 The SVD Algorithm* . . . . . . . . . . . . . . . . . . . . . . . . . . 235
6.6 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 238
6.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 239
Part III Data Fitting and Function Approximat io n 243
7. Polynomial Interpolation 245
7.1 Existence and Uniqueness . . . . . . . . . . . . . . . . . . . . . . . 246
7.2 Lagrange Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . 248
7.3 Newton Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . 253
7.4 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
7.5 Oscullatory Interpolation . . . . . . . . . . . . . . . . . . . . . . . . 270
7.6 Piecewise Polynomial Interpolation . . . . . . . . . . . . . . . . . . 275
7.7 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 285
7.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285
8. Approximation of Functions 289
8.1 Discrete Least Squares Approximation . . . . . . . . . . . . . . . . 290
8.2 Continuous Least Squares Approximation . . . . . . . . . . . . . . 299
8.3 Rational Approximation* . . . . . . . . . . . . . . . . . . . . . . . 310
8.4 Trigonometric Interpolation . . . . . . . . . . . . . . . . . . . . . . 317
8.5 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 326
8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326
9. Differentiation and Integration 329
9.1 Numerical Differentiation . . . . . . . . . . . . . . . . . . . . . . . 330
9.2 Numerical Integration . . . . . . . . . . . . . . . . . . . . . . . . . 342
9.3 Newton-Cotes Rules . . . . . . . . . . . . . . . . . . . . . . . . . . 346
9.4 Composite Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . 350
9.5 Extrapolation to the Limit . . . . . . . . . . . . . . . . . . . . . . . 353
9.6 Adaptive Quadrature . . . . . . . . . . . . . . . . . . . . . . . . . . 362
9.7 Gauss Quadrature . . . . . . . . . . . . . . . . . . . . . . . . . . . 369
9.8 Multiple Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378
9.9 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 384
9.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
Part IV Nonlinear Equations and Optimization 389
10. Zeros of Non l in ear Functions 391
10.1 Solution by Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . 391
10.2 The Bisection Method . . . . . . . . . . . . . . . . . . . . . . . . . 394
10.3 Fixe d-Point Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . 402
10.4 Newton’s Method and the Secant Method . . . . . . . . . . . . . . 411
10.5 Improvements to Root-Finding Methods* . . . . . . . . . . . . . . 423
10.6 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 430
10.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 431
11. Optimization 435
11.1 Systems of Nonlinear Equations . . . . . . . . . . . . . . . . . . . . 435
11.2 Optimization Based on Newton’s Method . . . . . . . . . . . . . . 445
11.3 Derivative-Free Optimization* . . . . . . . . . . . . . . . . . . . . . 459
11.4 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 463
11.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464
Part V Differential Equations 467
12. Initial Value Problems 469
12.1 Basics of Differential Equations . . . . . . . . . . . . . . . . . . . . 470
12.2 One-St e p Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 474
12.3 Multistep Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 482
12.4 Convergence Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 487
12.5 Adaptive Methods* . . . . . . . . . . . . . . . . . . . . . . . . . . . 501
12.6 Higher- Order Equations and Systems of Equations . . . . . . . . . 505
12.7 Addition al Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 510
12.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 510
13. Two-Point Boundary Value Problems 515
13.1 The Shooting Method . . . . . . . . . . . . . . . . . . . . . . . . . 516
13.2 Finite Difference Methods . . . . . . . . . . . . . . . . . . . . . . . 522
13.3 Collocation* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 530
13.4 The Finite Element Method* . . . . . . . . . . . . . . . . . . . . . 535
13.5 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 543
13.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 544
14. Partial Differential Equations 547
14.1 Fundamentals of PDEs . . . . . . . . . . . . . . . . . . . . . . . . . 547
14.2 Elliptic Equations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 549
14.3 Parabolic Equations . . . . . . . . . . . . . . . . . . . . . . . . . . 559
14.4 Hyperbolic Equations . . . . . . . . . . . . . . . . . . . . . . . . . . 567
14.5 The Finite Element Method* . . . . . . . . . . . . . . . . . . . . . 572
14.6 Spectral Methods* . . . . . . . . . . . . . . . . . . . . . . . . . . . 579
14.7 Additional Resources . . . . . . . . . . . . . . . . . . . . . . . . . . 586
14.8 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 587
Appendices 595
Appendix A Review of Calculus 595
A.1 Limits and Continuity . . . . . . . . . . . . . . . . . . . . . . . . . 595
A.2 Derivatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 599
A.3 Extreme Values . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 601
A.4 Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603
A.5 The Mean Value Theorem . . . . . . . . . . . . . . . . . . . . . . . 604
A.6 Taylor’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606
Appendix B Review of Linear Algebra 611
B.1 Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611
B.2 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 612
B.3 Subspaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 613
B.4 Linear Independence and Bases . . . . . . . . . . . . . . . . . . . . 614
B.5 Linear Transformations . . . . . . . . . . . . . . . . . . . . . . . . . 616
B.6 Matrix-Matrix Multiplication . . . . . . . . . . . . . . . . . . . . . 618
B.7 Other Fundamental M at r i x Operations . . . . . . . . . . . . . . . . 619
B.8 The Identity Matrix . . . . . . . . . . . . . . . . . . . . . . . . . . 625
B.9 The Inverse of a Matrix . . . . . . . . . . . . . . . . . . . . . . . . 625
B.10 Triangular and Diagonal Matrices . . . . . . . . . . . . . . . . . . . 626
B.11 Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627
B.12 Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629
B.13 Vector and Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . 630
B.14 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 637
B.15 Inner Product Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . 639
Bibliography 641
Index 651

Exemplar(s)

#	Accession No.	Call Number	Location	Status
1.	00237/19	518.0285 Lam E	Library - 7th Floor	Available