Numerical mathematics /
Grasselli, Matheus.
Numerical mathematics / Matheus Grasselli, Dmitry Pelinovsky. - Sudbury, Mass. : Jones and Bartlett Publishers, c2008. - xiv, 668 p. ill. ; 24 cm.
Includes bibliographical references (p. 653-654) and indexes.
Contents
1 Elements of the Laboratory 13
1.1 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2 Scalars, Vectors and Matrices . . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Matrix Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4 Built-in Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.5 Programming with MATLAB . . . . . . . . . . . . . . . . . . . . . . . 35
1.6 Graphics and Data Files . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.7 Floating¿Point Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 49
1.8 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.9 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
1.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2 Linear Systems 59
2.1 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.2 Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.3 Systems of Linear Equations . . . . . . . . . . . . . . . . . . . . . . . . 82
2.4 Vector and Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . 87
2.5 Direct Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
2.6 Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
2.7 Cholesky Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
2.8 Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
2.9 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
2.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
3 Orthogonality 135
3.1 Inner Product Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
3.2 Orthogonal Projections . . . . . . . . . . . . . . . . . . . . . . . . . . 145
3.3 QR Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
3
3.4 The Least¿Squares Method . . . . . . . . . . . . . . . . . . . . . . . . 166
3.5 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
4 Eigenvalues and Eigenvectors 177
4.1 Matrix Eigenvalue Problems . . . . . . . . . . . . . . . . . . . . . . . . 178
4.2 Properties of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . 182
4.3 Properties of Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.4 Normal Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
4.5 Sensitivity of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . 202
4.6 Power Iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
4.7 Simultaneous Iterations . . . . . . . . . . . . . . . . . . . . . . . . . . 222
4.8 Singular Value Decomposition . . . . . . . . . . . . . . . . . . . . . . . 231
4.9 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
4.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
5 Polynomial Functions 247
5.1 Properties of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . 247
5.2 Vandermonde Interpolation . . . . . . . . . . . . . . . . . . . . . . . . 256
5.3 Lagrange Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
5.4 Newton Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
5.5 Errors of Polynomial Interpolation . . . . . . . . . . . . . . . . . . . . 271
5.6 Least Square Approximation . . . . . . . . . . . . . . . . . . . . . . . 279
5.7 Approximation with Orthogonal Polynomials . . . . . . . . . . . . . . 288
5.8 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
5.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
6 Differential and Integral Calculus 303
6.1 Derivatives and Finite Differences . . . . . . . . . . . . . . . . . . . . . 304
6.2 Higher¿Order Numerical Derivatives . . . . . . . . . . . . . . . . . . . 309
6.3 Multi¿Point First¿Order Numerical Derivatives . . . . . . . . . . . . . 316
6.4 Richardson Extrapolation . . . . . . . . . . . . . . . . . . . . . . . . . 321
6.5 Integrals and Finite Sums . . . . . . . . . . . . . . . . . . . . . . . . . 327
6.6 Newton-Cotes Integration Rules . . . . . . . . . . . . . . . . . . . . . . 339
6.7 Romberg Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
6.8 Gaussian Quadrature Rules . . . . . . . . . . . . . . . . . . . . . . . . 353
6.9 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
4
6.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
7 Vector Calculus 369
7.1 Scalar Functions of Several Variables . . . . . . . . . . . . . . . . . . . 370
7.2 Partial Derivatives and Differentiability . . . . . . . . . . . . . . . . . 378
7.3 The Gradient Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
7.4 Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
7.5 Vector Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
7.6 Line Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
7.7 Surface Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
7.8 Integral Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
7.9 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
7.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
8 Zeros and Extrema of Functions 419
8.1 One¿dimensional root finding . . . . . . . . . . . . . . . . . . . . . . . 420
8.2 Multidimensional root finding . . . . . . . . . . . . . . . . . . . . . . . 439
8.3 One¿dimensional minimization . . . . . . . . . . . . . . . . . . . . . . 447
8.4 Multidimensional Minimization . . . . . . . . . . . . . . . . . . . . . . 454
8.5 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
9 Initial¿Value Problems for ODEs 463
9.1 Approximations of Solutions . . . . . . . . . . . . . . . . . . . . . . . . 463
9.2 Single¿Step Runge¿Kutta Solvers . . . . . . . . . . . . . . . . . . . . . 472
9.3 Adaptive Single¿Step Solvers . . . . . . . . . . . . . . . . . . . . . . . 485
9.4 Multi¿step Adams Solvers . . . . . . . . . . . . . . . . . . . . . . . . . 495
9.5 Implicit Methods for Stiff Differential Equations . . . . . . . . . . . . 510
9.6 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
9.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
10 Boundary¿Value Problems for ODEs and PDEs 525
10.1 Finite¿Difference Methods for ODEs . . . . . . . . . . . . . . . . . . . 526
10.2 Shooting Methods for ODEs . . . . . . . . . . . . . . . . . . . . . . . . 540
10.3 Finite¿Difference Methods for Parabolic PDEs . . . . . . . . . . . . . 552
10.4 Finite¿Difference Methods for Hyperbolic PDEs . . . . . . . . . . . . . 565
10.5 Finite¿Difference Methods for Elliptic PDEs . . . . . . . . . . . . . . . 575
10.6 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588
5
10.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590
11 Spectral Methods 595
11.1 Trigonometric Approximation and Interpolation . . . . . . . . . . . . . 595
11.2 Errors of Trigonometric Interpolation . . . . . . . . . . . . . . . . . . . 604
11.3 Trigonometric Methods for Differential Equations . . . . . . . . . . . . 612
11.4 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628
11.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629
12 Finite Element Methods 633
12.1 Spline Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
12.2 Hermite Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 648
12.3 Finite Elements for Differential Equations . . . . . . . . . . . . . . . . 658
12.4 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668
12.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 669
Subject Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678
MATLAB Functions and Commands . . . . . . . . . . . . . . . . . . . . . . 686
Mathematical Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 688
9780763737672 0763737674
Numerical analysis.
518 / G768
Numerical mathematics / Matheus Grasselli, Dmitry Pelinovsky. - Sudbury, Mass. : Jones and Bartlett Publishers, c2008. - xiv, 668 p. ill. ; 24 cm.
Includes bibliographical references (p. 653-654) and indexes.
Contents
1 Elements of the Laboratory 13
1.1 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.2 Scalars, Vectors and Matrices . . . . . . . . . . . . . . . . . . . . . . . 16
1.3 Matrix Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
1.4 Built-in Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.5 Programming with MATLAB . . . . . . . . . . . . . . . . . . . . . . . 35
1.6 Graphics and Data Files . . . . . . . . . . . . . . . . . . . . . . . . . . 43
1.7 Floating¿Point Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 49
1.8 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
1.9 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
1.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
2 Linear Systems 59
2.1 Vector Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.2 Linear Maps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70
2.3 Systems of Linear Equations . . . . . . . . . . . . . . . . . . . . . . . . 82
2.4 Vector and Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . 87
2.5 Direct Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
2.6 Iterative Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
2.7 Cholesky Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
2.8 Determinants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
2.9 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
2.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
3 Orthogonality 135
3.1 Inner Product Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
3.2 Orthogonal Projections . . . . . . . . . . . . . . . . . . . . . . . . . . 145
3.3 QR Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
3
3.4 The Least¿Squares Method . . . . . . . . . . . . . . . . . . . . . . . . 166
3.5 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175
3.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176
4 Eigenvalues and Eigenvectors 177
4.1 Matrix Eigenvalue Problems . . . . . . . . . . . . . . . . . . . . . . . . 178
4.2 Properties of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . 182
4.3 Properties of Eigenvectors . . . . . . . . . . . . . . . . . . . . . . . . . 192
4.4 Normal Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 198
4.5 Sensitivity of Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . 202
4.6 Power Iterations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209
4.7 Simultaneous Iterations . . . . . . . . . . . . . . . . . . . . . . . . . . 222
4.8 Singular Value Decomposition . . . . . . . . . . . . . . . . . . . . . . . 231
4.9 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243
4.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245
5 Polynomial Functions 247
5.1 Properties of Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . 247
5.2 Vandermonde Interpolation . . . . . . . . . . . . . . . . . . . . . . . . 256
5.3 Lagrange Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 263
5.4 Newton Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266
5.5 Errors of Polynomial Interpolation . . . . . . . . . . . . . . . . . . . . 271
5.6 Least Square Approximation . . . . . . . . . . . . . . . . . . . . . . . 279
5.7 Approximation with Orthogonal Polynomials . . . . . . . . . . . . . . 288
5.8 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297
5.9 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 299
6 Differential and Integral Calculus 303
6.1 Derivatives and Finite Differences . . . . . . . . . . . . . . . . . . . . . 304
6.2 Higher¿Order Numerical Derivatives . . . . . . . . . . . . . . . . . . . 309
6.3 Multi¿Point First¿Order Numerical Derivatives . . . . . . . . . . . . . 316
6.4 Richardson Extrapolation . . . . . . . . . . . . . . . . . . . . . . . . . 321
6.5 Integrals and Finite Sums . . . . . . . . . . . . . . . . . . . . . . . . . 327
6.6 Newton-Cotes Integration Rules . . . . . . . . . . . . . . . . . . . . . . 339
6.7 Romberg Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349
6.8 Gaussian Quadrature Rules . . . . . . . . . . . . . . . . . . . . . . . . 353
6.9 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363
4
6.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364
7 Vector Calculus 369
7.1 Scalar Functions of Several Variables . . . . . . . . . . . . . . . . . . . 370
7.2 Partial Derivatives and Differentiability . . . . . . . . . . . . . . . . . 378
7.3 The Gradient Vector . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384
7.4 Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 388
7.5 Vector Fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 391
7.6 Line Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398
7.7 Surface Integrals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 402
7.8 Integral Theorems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 409
7.9 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415
7.10 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
8 Zeros and Extrema of Functions 419
8.1 One¿dimensional root finding . . . . . . . . . . . . . . . . . . . . . . . 420
8.2 Multidimensional root finding . . . . . . . . . . . . . . . . . . . . . . . 439
8.3 One¿dimensional minimization . . . . . . . . . . . . . . . . . . . . . . 447
8.4 Multidimensional Minimization . . . . . . . . . . . . . . . . . . . . . . 454
8.5 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461
8.6 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 462
9 Initial¿Value Problems for ODEs 463
9.1 Approximations of Solutions . . . . . . . . . . . . . . . . . . . . . . . . 463
9.2 Single¿Step Runge¿Kutta Solvers . . . . . . . . . . . . . . . . . . . . . 472
9.3 Adaptive Single¿Step Solvers . . . . . . . . . . . . . . . . . . . . . . . 485
9.4 Multi¿step Adams Solvers . . . . . . . . . . . . . . . . . . . . . . . . . 495
9.5 Implicit Methods for Stiff Differential Equations . . . . . . . . . . . . 510
9.6 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518
9.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 520
10 Boundary¿Value Problems for ODEs and PDEs 525
10.1 Finite¿Difference Methods for ODEs . . . . . . . . . . . . . . . . . . . 526
10.2 Shooting Methods for ODEs . . . . . . . . . . . . . . . . . . . . . . . . 540
10.3 Finite¿Difference Methods for Parabolic PDEs . . . . . . . . . . . . . 552
10.4 Finite¿Difference Methods for Hyperbolic PDEs . . . . . . . . . . . . . 565
10.5 Finite¿Difference Methods for Elliptic PDEs . . . . . . . . . . . . . . . 575
10.6 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588
5
10.7 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 590
11 Spectral Methods 595
11.1 Trigonometric Approximation and Interpolation . . . . . . . . . . . . . 595
11.2 Errors of Trigonometric Interpolation . . . . . . . . . . . . . . . . . . . 604
11.3 Trigonometric Methods for Differential Equations . . . . . . . . . . . . 612
11.4 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628
11.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 629
12 Finite Element Methods 633
12.1 Spline Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633
12.2 Hermite Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . 648
12.3 Finite Elements for Differential Equations . . . . . . . . . . . . . . . . 658
12.4 Summary and Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668
12.5 Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 669
Subject Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678
MATLAB Functions and Commands . . . . . . . . . . . . . . . . . . . . . . 686
Mathematical Symbols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 688
9780763737672 0763737674
Numerical analysis.
518 / G768
