Table of Contents
Preface xi
1 Errors in Numerical Analysis 1
1.1 Enter Data Errors 1
1.2 Approximation Errors 2
1.3 Round-Off Errors 3
1.4 Propagation of Errors 3
1.4.1 Addition 3
1.4.2 Multiplication 5
1.4.3 Inversion of a Number 7
1.4.4 Division of Two Numbers 7
1.4.5 Raising to a Negative Entire Power 7
1.4.6 Taking the Root of pth Order 7
1.4.7 Subtraction 8
1.4.8 Computation of Functions 8
1.5 Applications 8
Further Reading 14
2 Solution of Equations 17
2.1 The Bipartition (Bisection) Method 17
2.2 The Chord (Secant) Method 20
2.3 The Tangent Method (Newton) 26
2.4 The Contraction Method 37
2.5 The Newton–Kantorovich Method 42
2.6 Numerical Examples 46
2.7 Applications 49
Further Reading 52
3 Solution of Algebraic Equations 55
3.1 Determination of Limits of the Roots of Polynomials 55
3.2 Separation of Roots 60
3.3 Lagrange’s Method 69
3.4 The Lobachevski–Graeffe Method 72
3.4.1 The Case of Distinct Real Roots 72
3.4.2 The Case of a Pair of Complex Conjugate Roots 74
3.4.3 The Case of Two Pairs of Complex Conjugate Roots 75
3.5 The Bernoulli Method 76
3.6 The Bierge–Viète Method 79
3.7 Lin Methods 79
3.8 Numerical Examples 82
3.9 Applications 94
Further Reading 109
4 Linear Algebra 111
4.1 Calculation of Determinants 111
4.1.1 Use of Definition 111
4.1.2 Use of Equivalent Matrices 112
4.2 Calculation of the Rank 113
4.3 Norm of a Matrix 114
4.4 Inversion of Matrices 123
4.4.1 Direct Inversion 123
4.4.2 The Gauss–Jordan Method 124
4.4.3 The Determination of the Inverse Matrix by its Partition 125
4.4.4 Schur’s Method of Inversion of Matrices 127
4.4.5 The Iterative Method (Schulz) 128
4.4.6 Inversion by Means of the Characteristic Polynomial 131
4.4.7 The Frame–Fadeev Method 131
4.5 Solution of Linear Algebraic Systems of Equations 132
4.5.1 Cramer’s Rule 132
4.5.2 Gauss’s Method 133
4.5.3 The Gauss–Jordan Method 134
4.5.4 The LU Factorization 135
4.5.5 The Schur Method of Solving Systems of Linear Equations 137
4.5.6 The Iteration Method (Jacobi) 142
4.5.7 The Gauss–Seidel Method 147
4.5.8 The Relaxation Method 149
4.5.9 The Monte Carlo Method 150
4.5.10 Infinite Systems of Linear Equations 152
4.6 Determination of Eigenvalues and Eigenvectors 153
4.6.1 Introduction 153
4.6.2 Krylov’s Method 155
4.6.3 Danilevski’s Method 157
4.6.4 The Direct Power Method 160
4.6.5 The Inverse Power Method 165
4.6.6 The Displacement Method 166
4.6.7 Leverrier’s Method 166
4.6.8 The L–R (Left–Right) Method 166
4.6.9 The Rotation Method 168
4.7 QR Decomposition 169
4.8 The Singular Value Decomposition (SVD) 172
4.9 Use of the Least Squares Method in Solving the Linear Overdetermined Systems 174
4.10 The Pseudo-Inverse of a Matrix 177
4.11 Solving of the Underdetermined Linear Systems 178
4.12 Numerical Examples 178
4.13 Applications 211
Further Reading 269
5 Solution of Systems of Nonlinear Equations 273
5.1 The Iteration Method (Jacobi) 273
5.2 Newton’s Method 275
5.3 The Modified Newton’s Method 276
5.4 The Newton–Raphson Method 277
5.5 The Gradient Method 277
5.6 The Method of Entire Series 280
5.7 Numerical Example 281
5.8 Applications 287
Further Reading 304
6 Interpolation and Approximation of Functions 307
6.1 Lagrange’s Interpolation Polynomial 307
6.2 Taylor Polynomials 311
6.3 Finite Differences: Generalized Power 312
6.4 Newton’s Interpolation Polynomials 317
6.5 Central Differences: Gauss’s Formulae Stirling’s Formula Bessel’s Formula Everett’s Formulae 322
6.6 Divided Differences 327
6.7 Newton-Type Formula with Divided Differences 331
6.8 Inverse Interpolation 332
6.9 Determination of the Roots of an Equation by Inverse Interpolation 333
6.10 Interpolation by Spline Functions 335
6.11 Hermite’s Interpolation 339
6.12 Chebyshev’s Polynomials 340
6.13 Mini–Max Approximation of Functions 344
6.14 Almost Mini–Max Approximation of Functions 345
6.15 Approximation of Functions by Trigonometric Functions (Fourier) 346
6.16 Approximation of Functions by the Least Squares 352
6.17 Other Methods of Interpolation 354
6.17.1 Interpolation with Rational Functions 354
6.17.2 The Method of Least Squares with Rational Functions 355
6.17.3 Interpolation with Exponentials 355
6.18 Numerical Examples 356
6.19 Applications 363
Further Reading 374
7 Numerical Differentiation and Integration 377
7.1 Introduction 377
7.2 Numerical Differentiation by Means of an Expansion into a Taylor Series 377
7.3 Numerical Differentiation by Means of Interpolation Polynomials 380
7.4 Introduction to Numerical Integration 382
7.5 The Newton–Côtes Quadrature Formulae 384
7.6 The Trapezoid Formula 386
7.7 Simpson’s Formula 389
7.8 Euler’s and Gregory’s Formulae 393
7.9 Romberg’s Formula 396
7.10 Chebyshev’s Quadrature Formulae 398
7.11 Legendre’s Polynomials 400
7.12 Gauss’s Quadrature Formulae 405
7.13 Orthogonal Polynomials 406
7.13.1 Legendre Polynomials 407
7.13.2 Chebyshev Polynomials 407
7.13.3 Jacobi Polynomials 408
7.13.4 Hermite Polynomials 408
7.13.5 Laguerre Polynomials 409
7.13.6 General Properties of the Orthogonal Polynomials 410
7.14 Quadrature Formulae of Gauss Type Obtained by Orthogonal Polynomials 412
7.14.1 Gauss–Jacobi Quadrature Formulae 413
7.14.2 Gauss–Hermite Quadrature Formulae 414
7.14.3 Gauss–Laguerre Quadrature Formulae 415
7.15 Other Quadrature Formulae 417
7.15.1 Gauss Formulae with Imposed Points 417
7.15.2 Gauss Formulae in which the Derivatives of the Function Also Appear 418
7.16 Calculation of Improper Integrals 420
7.17 Kantorovich’s Method 422
7.18 The Monte Carlo Method for Calculation of Definite Integrals 423
7.18.1 The One-Dimensional Case 423
7.18.2 The Multidimensional Case 425
7.19 Numerical Examples 427
7.20 Applications 435
Further Reading 447
8 Integration of Ordinary Differential Equations and of Systems of Ordinary Differential Equations 451
8.1 State of the Problem 451
8.2 Euler’s Method 454
8.3 Taylor Method 457
8.4 The Runge–Kutta Methods 458
8.5 Multistep Methods 462
8.6 Adams’s Method 463
8.7 The Adams–Bashforth Methods 465
8.8 The Adams–Moulton Methods 467
8.9 Predictor–Corrector Methods 469
8.9.1 Euler’s Predictor–Corrector Method 469
8.9.2 Adams’s Predictor–Corrector Methods 469
8.9.3 Milne’s Fourth-Order Predictor–Corrector Method 470
8.9.4 Hamming’s Predictor–Corrector Method 470
8.10 The Linear Equivalence Method (LEM) 471
8.11 Considerations about the Errors 473
8.12 Numerical Example 474
8.13 Applications 480
Further Reading 525
9 Integration of Partial Differential Equations and of Systems of Partial Differential Equations 529
9.1 Introduction 529
9.2 Partial Differential Equations of First Order 529
9.2.1 Numerical Integration by Means of Explicit Schemata 531
9.2.2 Numerical Integration by Means of Implicit Schemata 533
9.3 Partial Differential Equations of Second Order 534
9.4 Partial Differential Equations of Second Order of Elliptic Type 534
9.5 Partial Differential Equations of Second Order of Parabolic Type 538
9.6 Partial Differential Equations of Second Order of Hyperbolic Type 543
9.7 Point Matching Method 546
9.8 Variational Methods 547
9.8.1 Ritz’s Method 549
9.8.2 Galerkin’s Method 551
9.8.3 Method of the Least Squares 553
9.9 Numerical Examples 554
9.10 Applications 562
Further Reading 575
10 Optimizations 577
10.1 Introduction 577
10.2 Minimization Along a Direction 578
10.2.1 Localization of the Minimum 579
10.2.2 Determination of the Minimum 580
10.3 Conjugate Directions 583
10.4 Powell’s Algorithm 585
10.5 Methods of Gradient Type 585
10.5.1 The Gradient Method 585
10.5.2 The Conjugate Gradient Method 587
10.5.3 Solution of Systems of Linear Equations by Means of Methods of Gradient Type 589
10.6 Methods of Newton Type 590
10.6.1 Newton’s Method 590
10.6.2 Quasi-Newton Method 592
10.7 Linear Programming: The Simplex Algorithm 593
10.7.1 Introduction 593
10.7.2 Formulation of the Problem of Linear Programming 595
10.7.3 Geometrical Interpretation 597
10.7.4 The Primal Simplex Algorithm 597
10.7.5 The Dual Simplex Algorithm 599
10.8 Convex Programming 600
10.9 Numerical Methods for Problems of Convex Programming 602
10.9.1 Method of Conditional Gradient 602
10.9.2 Method of Gradient’s Projection 602
10.9.3 Method of Possible Directions 603
10.9.4 Method of Penalizing Functions 603
10.10 Quadratic Programming 603
10.11 Dynamic Programming 605
10.12 Pontryagin’s Principle of Maximum 607
10.13 Problems of Extremum 609
10.14 Numerical Examples 611
10.15 Applications 623
Further Reading 626
Index 629
