Numerical Analysis with Algorithms and ProgrammingPDF电子书下载

Chapter 1 Errors in Numerical Computations 1

1.1 Introduction 1

1.2 Preliminary Mathematical Theorems 1

1.3 Approximate Numbers and Significant Figures 3

1.3.1 Significant Figures 3

1.3.1.1 Rules of Significant Figures 3

1.4 Rounding Off Numbers 3

1.4.1 Absolute Error 4

1.4.2 Relative and Percentage Errors 4

1.4.2.1 Measuring Significant Digits in xA 4

1.4.3 Inherent Error 5

1.4.4 Round-Off and Chopping Errors 5

1.5 Truncation Errors 7

1.6 Floating Point Representation of Numbers 9

1.6.1 Computer Representation of Numbers 9

1.7 Propagation of Errors 10

1.8 General Formula for Errors 11

1.9 Loss of Significance Errors 12

1.10 Numerical Stability，Condition Number，and Convergence 14

1.10.1 Condition of a Problem 14

1.10.2 Stability of an Algorithm 16

1.11 Brief Idea of Convergence 16

Exercises 16

Chapter 2 Numerical Solutions of Algebraic and Transcendental Equations 19

2.1 Introduction 19

2.2 Basic Concepts and Definitions 19

2.2.1 Sequence of Successive Approximations 19

2.2.2 Order of Convergence 19

2.3 Initial Approximation 20

2.3.1 Graphical Method 20

2.3.2 Incremental Search Method 21

2.4 Iterative Methods 22

2.4.1 Method of Bisection 22

2.4.1.1 Order of Convergence of the Bisection Method 23

2.4.1.2 Advantage and Disadvantage of the Bisection Method 24

2.4.1.3 Algorithm for the Bisection Method 25

2.4.2 Regula-Falsi Method or Method of False Position 25

2.4.2.1 Order of Convergence of the Regula-Falsi Method 28

2.4.2.2 Advantage and Disadvantage of the Regula-Falsi Method 28

2.4.2.3 Algorithm for the Regula-Falsi Method 29

2.4.3 Fixed-Point Iteration 29

2.4.3.1 Condition of Convergence for the Fixed-Point Iteration Method 30

2.4.3.2 Acceleration of Convergence：Aitken’s △2-Process 33

2.4.3.3 Advantage and Disadvantage of the Fixed-Point Iteration Method 35

2.4.3.4 Algorithm of the Fixed-Point Iteration Method 36

2.4.4 Newton-Raphson Method 36

2.4.4.1 Condition of Convergence 37

2.4.4.2 Order of Convergence for the Newton-Raphson Method 38

2.4.4.3 Geometrical Significance of the Newton-Raphson Method 38

2.4.4.4 Advantage and Disadvantage of the Newton-Raphson Method 39

2.4.4.5 Algorithm for the Newton-Raphson Method 41

2.4.5 Secant Method 41

2.4.5.1 Geometrical Significance of the Secant Method 42

2.4.5.2 Order of Convergence for the Secant Method 43

2.4.5.3 Advantage and Disadvantage of the Secant Method 45

2.4.5.4 Algorithm for the Secant Method 46

2.5 Generalized Newton’s Method 46

2.5.1 Numerical Solution of Simultaneous Nonlinear Equations 48

2.5.1.1 Newton’s Method 48

2.5.1.2 Fixed-Point Iteration Method 55

2.6 Graeffe’s Root Squaring Method for Algebraic Equations 59

Exercises 64

Chapter 3 Interpolation 71

3.1 Introduction 71

3.2 Polynomial Interpolation 71

3.2.1 Geometric Interpretation of Interpolation 72

3.2.2 Error in Polynomial Interpolation 72

3.2.3 Finite Differences 73

3.2.3.1 Forward Differences 73

3.2.4 Shift，Differentiation，and Averaging Operators 77

3.2.4.1 Shift Operator 77

3.2.4.2 Differentiation Operator 78

3.2.4.3 Averaging Operator 79

3.2.5 Factorial Polynomial 82

3.2.5.1 Forward Differences of Factorial Polynomial 82

3.2.6 Backward Differences 85

3.2.6.1 Relation between the Forward and Backward Difference Operators 86

3.2.6.2 Backward Difference Table 86

3.2.7 Newton’s Forward Difference Interpolation 86

3.2.7.1 Error in Newton’s Forward Difference Interpolation 87

3.2.7.2 Algorithm for Newton’s Forward Difference Interpolation 87

3.2.8 Newton’s Backward Difference Interpolation 88

3.2.8.1 Error in Newton’s Backward Difference Interpolation 89

3.2.8.2 Algorithm for Newton’s Backward Difference Interpolation 89

3.2.9 Lagrange’s Interpolation Formula 91

3.2.9.1 Error in Lagrange’s Interpolation 93

3.2.9.2 Advantages and Disadvantages of Lagrange’s Interpolation 93

3.2.9.3 Algorithm for Lagrange’s Interpolation 94

3.2.10 Divided Difference 94

3.2.10.1 Some Properties of Divided Differences 95

3.2.10.2 Newton’s Divided Difference Interpolation Formula 97

3.2.10.3 Divided Difference Table 99

3.2.10.4 Algorithm for Newton’s Divided Difference Interpolation 99

3.2.10.5 Some Important Relations 100

3.2.11 Gauss’s Forward Interpolation Formula 105

3.2.12 Gauss’s Backward Interpolation Formula 106

3.2.13 Central Difference 109

3.2.13.1 Central Difference Table 110

3.2.13.2 Stirling’s Interpolation Formula 110

3.2.13.3 Bessel’s Interpolation Formula 111

3.2.13.4 Everette’s Interpolation Formula 115

3.2.14 Hermite’s Interpolation Formula 118

3.2.14.1 Uniqueness of Hermite Polynomial 119

3.2.14.2 The Error in Hermite Interpolation 120

3.2.15 Piecewise Interpolation 120

3.2.15.1 Piecewise Linear Interpolation 121

3.2.15.2 Piecewise Quadratic Interpolation 121

3.2.15.3 Piecewise Cubic Interpolation 122

3.2.16 Cubic Spline Interpolation 126

3.2.16.1 Cubic Spline 126

3.2.16.2 Error in Cubic Spline 132

3.2.17 Interpolation by Iteration 142

3.2.17.1 Aitken’s Interpolation Formula 142

3.2.17.2 Neville’s Interpolation Formula 145

3.2.18 Inverse Interpolation 148

Exercises 150

Chapter 4 Numerical Differentiation 159

4.1 Introduction 159

4.2 Errors in Computation of Derivatives 159

4.3 Numerical Differentiation for Equispaced Nodes 161

4.3.1 Formulae Based on Newton’s Forward Interpolation 161

4.3.1.1 Error Estimate 162

4.3.2 Formulae Based on Newton’s Backward Interpolation 163

4.3.2.1 Error Estimate 164

4.3.3 Formulae Based on Stirling’s Interpolation 168

4.3.3.1 Error Estimate 169

4.3.4 Formulae Based on Bessel’s Interpolation 171

4.3.4.1 Error Estimate 171

4.4 Numerical Differentiation for Unequally Spaced Nodes 173

4.4.1 Formulae Based on Lagrange’s Interpolation 173

4.4.1.1 Error Estimate 174

4.4.2 Formulae Based on Newton’s Divided Difference Interpolation 174

4.4.2.1 Error Estimate 175

4.5 Richardson Extrapolation 177

Exercises 181

Chapter 5 Numerical Integration 185

5.1 Introduction 185

5.2 Numerical Integration from Lagrange’s Interpolation 185

5.3 Newton-Cotes Formula for Numerical Integration （Closed Type） 187

5.3.1 Deduction of Trapezoidal，Simpson’s One-Third，Weddle’s，and Simpson’s Three-Eighth Rules from the Newton-Cotes Numerical Integration Formula 194

5.3.1.1 Trapezoidal Rule and Its Error Estimate 194

5.3.1.2 Simpson’s One-Third Rule or Parabolic Rule with Error Term 198

5.3.1.3 Weddle’s Rule 205

5.3.1.4 Simpson’s Three-Eighth Rule with Error Term 208

5.4 Newton-Cotes Quadrature Formula （Open Type） 210

5.5 Numerical Integration Formula from Newton’s Forward Interpolation Formula 211

5.6 Richardson Extrapolation 220

5.7 Romberg Integration 224

5.7.1 Algorithm for Romberg’s Integration 226

5.8 Gauss Quadrature Formula 228

5.8.1 Guass-Legendre Integration Method 230

5.9 Gaussian Quadrature：Determination of Nodes and Weights through Orthogonal Polynomials 232

5.9.1 Gauss-Legendre Quadrature Method 235

5.9.2 Gauss-Chebyshev Quadrature Method 237

5.9.3 Gauss-Laguerre Quadrature Method 238

5.9.4 Gauss-Hermite Quadrature Method 240

5.10 Lobatto Quadrature Method 241

5.11 Double Integration 243

5.11.1 Trapezoidal Method 243

5.11.1.1 Algorithm for the Trapezoidal Method 245

5.11.2 Simpson’s One-Third Method 247

5.11.2.1 Algorithm for Simpson’s Method 248

5.12 Bernoulli Polynomials and Bernoulli Numbers 251

5.12.1 Some Properties of Bernoulli Polynomials 253

5.13 Euler-Maclaurin Formula 253

Exercises 257

Chapter 6 Numerical Solution of System of Linear Algebraic Equations 261

6.1 Introduction 261

6.2 Vector and Matrix Norm 262

6.2.1 Vector Norm 262

6.2.2 Matrix Norm 263

6.2.3 Condition Number of a Matrix 264

6.2.4 Spectral Radius and Norm Convergence 264

6.2.5 Jordan Block 265

6.2.6 Jordan Canonical Form 265

6.3 Direct Methods 269

6.3.1 Gauss Elimination Method 269

6.3.1.1 Pivoting in the Gauss Elimination Method 272

6.3.1.2 Operation Count in the Gauss Elimination Method 273

6.3.1.3 Algorithm for the Gauss Elimination Method 274

6.3.2 Gauss-Jordan Method 279

6.3.2.1 Algorithm for the Gauss-Jordan Method 280

6.3.3 Triangularization Method 283

6.3.3.1 Doolittle’s Method 284

6.3.3.2 Crout’s Method 287

6.3.3.3 Cholesky’s Method 292

6.4 Iterative Method 297

6.4.1 Gauss-Jacobi Iteration 298

6.4.1.1 Convergence of the Gauss-Jacobi Iteration Method 299

6.4.1.2 Algorithm for the Gauss-Jacobi Method 301

6.4.2 Gauss-Seidel Iteration Method 307

6.4.2.1 Convergence of the Gauss-Seidel Iteration Method 308

6.4.2.2 Algorithm for the Gauss-Seidel Method 310

6.4.3 SOR Method 320

6.4.3.1 Convergence of the SOR Method 320

6.4.3.2 Algorithm for the SOR Method 321

6.5 Convergent Iteration Matrices 331

6.6 Convergence of Iterative Methods 332

6.6.1 Rate of Convergence 332

6.7 Inversion of a Matrix by the Gaussian Method 333

6.8 Ill-Conditioned Systems 338

6.9 Thomas Algorithm 344

6.9.1 Operational Count for Thomas Algorithm 346

6.9.2 Algorithm 346

Exercises 347

Chapter 7 Numerical Solutions of Ordinary Differential Equations 361

7.1 Introduction 361

7.2 Single-Step Methods 362

7.2.1 Picard’s Method of Successive Approximations 362

7.2.2 Taylor’s Series Method 367

7.2.2.1 Error Estimate 368

7.2.2.2 Alternatively 368

7.2.3 General Form of a Single-Step Method 370

7.2.3.1 Error Estimate 370

7.2.3.2 Convergence of the Single-Step Method 372

7.2.4 Euler Method 373

7.2.4.1 Local Truncation Error 373

7.2.4.2 Geometrical Interpretation 374

7.2.4.3 Backward Euler Method 375

7.2.4.4 Midpoint Method 377

7.2.4.5 Algorithm for Euler’s Method 379

7.2.5 Improved Euler Method 380

7.2.5.1 Algorithm of the Improved Euler Method 383

7.2.6 Runge-Kutta Methods 385

7.2.6.1 Algorithm for R-K Method of Order 4 393

7.2.6.2 A General Form for Explicit R-K Methods 395

7.2.6.3 Estimation of the Truncation Error and Control 395

7.2.6.4 R-K-Fehlberg Method 396

7.3 Multistep Methods 406

7.3.1 Adams-Bashforth and Adams-Moulton Predictor-Corrector Method 408

7.3.1.1 Error Estimate 410

7.3.1.2 Algorithm of Adams Predictor-Corrector Method 411

7.3.2 Milne’s Method 415

7.3.2.1 Error Estimate 416

7.3.2.2 Algorithm of Milne’s Method 417

7.3.3 Nystrom Method 421

7.4 System of Ordinary Differential Equations of First-Order 423

7.4.1 Algorithm of R-K Method of the Fourth Order for Solving System of Ordinary Differential Equations 424

7.5 Differential Equations of Higher Order 428

7.6 Boundary Value Problems 430

7.6.1 Finite Difference Method 431

7.6.1.1 Boundary Conditions Involving the Derivative 435

7.6.1.2 Nonlinear Second-Order Differential Equation 438

7.6.2 Shooting Method 442

7.6.3 Collocation Method 448

7.6.4 Galerkin Method 452

7.7 Stability of an Initial Value Problem 454

7.7.1 Stability Analysis of Single Step Methods 456

7.7.1.1 Stability of Euler’s Method 456

7.7.1.2 Stability of the Backward Euler Method 458

7.7.1.3 Stability of R-K Methods 459

7.7.2 Stability Analysis of General Multistep Methods 460

7.7.2.1 General Methods for Finding the Interval of Absolute Stability 465

7.8 Stiff Differential Equations 468

7.9 A-stability and L-stability 469

7.9.1 A-stability 469

7.9.2 L-stability 471

Exercises 471

Chapter 8 Matrix Eigenvalue Problem 479

8.1 Introduction 479

8.1.1 Characteristic Equation，Eigenvalue，and Eigenvector of a Square Matrix 479

8.1.2 Similar Matrices and Diagonalizable Matrix 480

8.2 Inclusion of Eigenvalues 481

8.2.1 Gerschgorin’s Discs 481

8.2.2 Gerschgorin’s Theorem 481

8.3 Householder’s Method 483

8.3.1 Algorithm for Householder’s Method 487

8.4 The QR Method 490

8.4.1 Algorithm for the QR Method 492

8.4.2 The QR Method with Shift 498

8.5 Power Method 505

8.5.1 Algorithm of Power Method 512

8.6 Inverse Power Method 516

8.6.1 Algorithm of Inverse Power Method 517

8.7 Jacobi’s Method 527

8.8 Givens Method 531

8.8.1 Eigenvalues of a Symmetric Tridiagonal Matrix 532

Exercises 535

Chapter 9 Approximation of Functions 545

9.1 Introduction 545

9.1.1 Bernstein Polynomials and Its Properties 546

9.2 Least Square Curve Fitting 549

9.2.1 Straight Line Fitting 549

9.2.2 Fitting of kth Degree Polynomial 551

9.3 Least Squares Approximation 553

9.4 Orthogonal Polynomials 554

9.4.1 Weight Function 554

9.4.2 Gram-Schmidt Orthogonalization Process 557

9.5 The Minimax Polynomial Approximation 568

9.5.1 Characterization of the Minimax Polynomial 571

9.5.2 Existence of the Minimax Polynomial 573

9.5.3 Uniqueness of the Minimax Polynomial 574

9.5.4 The Near-Minimax Polynomial 575

9.6 B-Splines 577

9.6.1 Function Approximation by Cubic B-Spline 580

9.7 Pade Approximation 583

Exercises 587

Chapter 10 Numerical Solutions of Partial Differential Equations 591

10.1 Introduction 591

10.2 Classification of PDEs of Second Order 591

10.3 Types of Boundary Conditions and Problems 592

10.4 Finite Difference Approximations to Partial Derivatives 593

10.5 Parabolic PDEs 594

10.5.1 Explicit FDM 594

10.5.1.1 Algorithm for Solving Parabolic PDE by FDM 596

10.5.2 Crank-Nicolson Implicit Method 598

10.5.2.1 Algorithm for Solving Parabolic PDE by the Crank-Nicolson Method 599

10.6 Hyperbolic PDEs 603

10.6.1 Explicit Central Difference Method 603

10.6.1.1 Algorithm for Solving Hyperbolic PDE by the Explicit Central Difference Method 605

10.6.2 Implicit FDM 606

10.7 Elliptic PDEs 608

10.7.1 Laplace Equation 614

10.7.2 Algorithm for Solving Laplace Equation by SOR Method 617

10.8 Alternating Direction Implicit Method 621

10.8.1 Algorithm for Two-Dimensional Parabolic PDE by ADI Method 623

10.9 Stability Analysis of the Numerical Schemes 627

Exercises 631

Chapter 11 An Introduction to the Finite Element Method 641

11.1 Introduction 641

11.2 Piecewise Linear Basis Functions 641

11.3 The Rayleigh-Ritz Method 642

11.3.1 Algorithm of Rayleigh-Ritz Method 645

11.4 The Galerkin Method 651

Further Reading 651

Exercises 652

Answers 655

Bibliography 673

Index 675