Numerical Analysis with Algorithms and ProgrammingPDF|Epub|txt|kindle电子书版本网盘下载

Numerical Analysis with Algorithms and ProgrammingPDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

Chapter 1 Errors in Numerical Computations1

1.1 Introduction1

1.2 Preliminary Mathematical Theorems1

1.3 Approximate Numbers and Significant Figures3

1.3.1 Significant Figures3

1.3.1.1 Rules of Significant Figures3

1.4 Rounding Off Numbers3

1.4.1 Absolute Error4

1.4.2 Relative and Percentage Errors4

1.4.2.1 Measuring Significant Digits in xA4

1.4.3 Inherent Error5

1.4.4 Round-Off and Chopping Errors5

1.5 Truncation Errors7

1.6 Floating Point Representation of Numbers9

1.6.1 Computer Representation of Numbers9

1.7 Propagation of Errors10

1.8 General Formula for Errors11

1.9 Loss of Significance Errors12

1.10 Numerical Stability，Condition Number，and Convergence14

1.10.1 Condition of a Problem14

1.10.2 Stability of an Algorithm16

1.11 Brief Idea of Convergence16

Exercises16

Chapter 2 Numerical Solutions of Algebraic and Transcendental Equations19

2.1 Introduction19

2.2 Basic Concepts and Definitions19

2.2.1 Sequence of Successive Approximations19

2.2.2 Order of Convergence19

2.3 Initial Approximation20

2.3.1 Graphical Method20

2.3.2 Incremental Search Method21

2.4 Iterative Methods22

2.4.1 Method of Bisection22

2.4.1.1 Order of Convergence of the Bisection Method23

2.4.1.2 Advantage and Disadvantage of the Bisection Method24

2.4.1.3 Algorithm for the Bisection Method25

2.4.2 Regula-Falsi Method or Method of False Position25

2.4.2.1 Order of Convergence of the Regula-Falsi Method28

2.4.2.2 Advantage and Disadvantage of the Regula-Falsi Method28

2.4.2.3 Algorithm for the Regula-Falsi Method29

2.4.3 Fixed-Point Iteration29

2.4.3.1 Condition of Convergence for the Fixed-Point Iteration Method30

2.4.3.2 Acceleration of Convergence：Aitken’s △2-Process33

2.4.3.3 Advantage and Disadvantage of the Fixed-Point Iteration Method35

2.4.3.4 Algorithm of the Fixed-Point Iteration Method36

2.4.4 Newton-Raphson Method36

2.4.4.1 Condition of Convergence37

2.4.4.2 Order of Convergence for the Newton-Raphson Method38

2.4.4.3 Geometrical Significance of the Newton-Raphson Method38

2.4.4.4 Advantage and Disadvantage of the Newton-Raphson Method39

2.4.4.5 Algorithm for the Newton-Raphson Method41

2.4.5 Secant Method41

2.4.5.1 Geometrical Significance of the Secant Method42

2.4.5.2 Order of Convergence for the Secant Method43

2.4.5.3 Advantage and Disadvantage of the Secant Method45

2.4.5.4 Algorithm for the Secant Method46

2.5 Generalized Newton’s Method46

2.5.1 Numerical Solution of Simultaneous Nonlinear Equations48

2.5.1.1 Newton’s Method48

2.5.1.2 Fixed-Point Iteration Method55

2.6 Graeffe’s Root Squaring Method for Algebraic Equations59

Exercises64

Chapter 3 Interpolation71

3.1 Introduction71

3.2 Polynomial Interpolation71

3.2.1 Geometric Interpretation of Interpolation72

3.2.2 Error in Polynomial Interpolation72

3.2.3 Finite Differences73

3.2.3.1 Forward Differences73

3.2.4 Shift，Differentiation，and Averaging Operators77

3.2.4.1 Shift Operator77

3.2.4.2 Differentiation Operator78

3.2.4.3 Averaging Operator79

3.2.5 Factorial Polynomial82

3.2.5.1 Forward Differences of Factorial Polynomial82

3.2.6 Backward Differences85

3.2.6.1 Relation between the Forward and Backward Difference Operators86

3.2.6.2 Backward Difference Table86

3.2.7 Newton’s Forward Difference Interpolation86

3.2.7.1 Error in Newton’s Forward Difference Interpolation87

3.2.7.2 Algorithm for Newton’s Forward Difference Interpolation87

3.2.8 Newton’s Backward Difference Interpolation88

3.2.8.1 Error in Newton’s Backward Difference Interpolation89

3.2.8.2 Algorithm for Newton’s Backward Difference Interpolation89

3.2.9 Lagrange’s Interpolation Formula91

3.2.9.1 Error in Lagrange’s Interpolation93

3.2.9.2 Advantages and Disadvantages of Lagrange’s Interpolation93

3.2.9.3 Algorithm for Lagrange’s Interpolation94

3.2.10 Divided Difference94

3.2.10.1 Some Properties of Divided Differences95

3.2.10.2 Newton’s Divided Difference Interpolation Formula97

3.2.10.3 Divided Difference Table99

3.2.10.4 Algorithm for Newton’s Divided Difference Interpolation99

3.2.10.5 Some Important Relations100

3.2.11 Gauss’s Forward Interpolation Formula105

3.2.12 Gauss’s Backward Interpolation Formula106

3.2.13 Central Difference109

3.2.13.1 Central Difference Table110

3.2.13.2 Stirling’s Interpolation Formula110

3.2.13.3 Bessel’s Interpolation Formula111

3.2.13.4 Everette’s Interpolation Formula115

3.2.14 Hermite’s Interpolation Formula118

3.2.14.1 Uniqueness of Hermite Polynomial119

3.2.14.2 The Error in Hermite Interpolation120

3.2.15 Piecewise Interpolation120

3.2.15.1 Piecewise Linear Interpolation121

3.2.15.2 Piecewise Quadratic Interpolation121

3.2.15.3 Piecewise Cubic Interpolation122

3.2.16 Cubic Spline Interpolation126

3.2.16.1 Cubic Spline126

3.2.16.2 Error in Cubic Spline132

3.2.17 Interpolation by Iteration142

3.2.17.1 Aitken’s Interpolation Formula142

3.2.17.2 Neville’s Interpolation Formula145

3.2.18 Inverse Interpolation148

Exercises150

Chapter 4 Numerical Differentiation159

4.1 Introduction159

4.2 Errors in Computation of Derivatives159

4.3 Numerical Differentiation for Equispaced Nodes161

4.3.1 Formulae Based on Newton’s Forward Interpolation161

4.3.1.1 Error Estimate162

4.3.2 Formulae Based on Newton’s Backward Interpolation163

4.3.2.1 Error Estimate164

4.3.3 Formulae Based on Stirling’s Interpolation168

4.3.3.1 Error Estimate169

4.3.4 Formulae Based on Bessel’s Interpolation171

4.3.4.1 Error Estimate171

4.4 Numerical Differentiation for Unequally Spaced Nodes173

4.4.1 Formulae Based on Lagrange’s Interpolation173

4.4.1.1 Error Estimate174

4.4.2 Formulae Based on Newton’s Divided Difference Interpolation174

4.4.2.1 Error Estimate175

4.5 Richardson Extrapolation177

Exercises181

Chapter 5 Numerical Integration185

5.1 Introduction185

5.2 Numerical Integration from Lagrange’s Interpolation185

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 Formula194

5.3.1.1 Trapezoidal Rule and Its Error Estimate194

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

5.3.1.3 Weddle’s Rule205

5.3.1.4 Simpson’s Three-Eighth Rule with Error Term208

5.4 Newton-Cotes Quadrature Formula （Open Type）210

5.5 Numerical Integration Formula from Newton’s Forward Interpolation Formula211

5.6 Richardson Extrapolation220

5.7 Romberg Integration224

5.7.1 Algorithm for Romberg’s Integration226

5.8 Gauss Quadrature Formula228

5.8.1 Guass-Legendre Integration Method230

5.9 Gaussian Quadrature：Determination of Nodes and Weights through Orthogonal Polynomials232

5.9.1 Gauss-Legendre Quadrature Method235

5.9.2 Gauss-Chebyshev Quadrature Method237

5.9.3 Gauss-Laguerre Quadrature Method238

5.9.4 Gauss-Hermite Quadrature Method240

5.10 Lobatto Quadrature Method241

5.11 Double Integration243

5.11.1 Trapezoidal Method243

5.11.1.1 Algorithm for the Trapezoidal Method245

5.11.2 Simpson’s One-Third Method247

5.11.2.1 Algorithm for Simpson’s Method248

5.12 Bernoulli Polynomials and Bernoulli Numbers251

5.12.1 Some Properties of Bernoulli Polynomials253

5.13 Euler-Maclaurin Formula253

Exercises257

Chapter 6 Numerical Solution of System of Linear Algebraic Equations261

6.1 Introduction261

6.2 Vector and Matrix Norm262

6.2.1 Vector Norm262

6.2.2 Matrix Norm263

6.2.3 Condition Number of a Matrix264

6.2.4 Spectral Radius and Norm Convergence264

6.2.5 Jordan Block265

6.2.6 Jordan Canonical Form265

6.3 Direct Methods269

6.3.1 Gauss Elimination Method269

6.3.1.1 Pivoting in the Gauss Elimination Method272

6.3.1.2 Operation Count in the Gauss Elimination Method273

6.3.1.3 Algorithm for the Gauss Elimination Method274

6.3.2 Gauss-Jordan Method279

6.3.2.1 Algorithm for the Gauss-Jordan Method280

6.3.3 Triangularization Method283

6.3.3.1 Doolittle’s Method284

6.3.3.2 Crout’s Method287

6.3.3.3 Cholesky’s Method292

6.4 Iterative Method297

6.4.1 Gauss-Jacobi Iteration298

6.4.1.1 Convergence of the Gauss-Jacobi Iteration Method299

6.4.1.2 Algorithm for the Gauss-Jacobi Method301

6.4.2 Gauss-Seidel Iteration Method307

6.4.2.1 Convergence of the Gauss-Seidel Iteration Method308

6.4.2.2 Algorithm for the Gauss-Seidel Method310

6.4.3 SOR Method320

6.4.3.1 Convergence of the SOR Method320

6.4.3.2 Algorithm for the SOR Method321

6.5 Convergent Iteration Matrices331

6.6 Convergence of Iterative Methods332

6.6.1 Rate of Convergence332

6.7 Inversion of a Matrix by the Gaussian Method333

6.8 Ill-Conditioned Systems338

6.9 Thomas Algorithm344

6.9.1 Operational Count for Thomas Algorithm346

6.9.2 Algorithm346

Exercises347

Chapter 7 Numerical Solutions of Ordinary Differential Equations361

7.1 Introduction361

7.2 Single-Step Methods362

7.2.1 Picard’s Method of Successive Approximations362

7.2.2 Taylor’s Series Method367

7.2.2.1 Error Estimate368

7.2.2.2 Alternatively368

7.2.3 General Form of a Single-Step Method370

7.2.3.1 Error Estimate370

7.2.3.2 Convergence of the Single-Step Method372

7.2.4 Euler Method373

7.2.4.1 Local Truncation Error373

7.2.4.2 Geometrical Interpretation374

7.2.4.3 Backward Euler Method375

7.2.4.4 Midpoint Method377

7.2.4.5 Algorithm for Euler’s Method379

7.2.5 Improved Euler Method380

7.2.5.1 Algorithm of the Improved Euler Method383

7.2.6 Runge-Kutta Methods385

7.2.6.1 Algorithm for R-K Method of Order 4393

7.2.6.2 A General Form for Explicit R-K Methods395

7.2.6.3 Estimation of the Truncation Error and Control395

7.2.6.4 R-K-Fehlberg Method396

7.3 Multistep Methods406

7.3.1 Adams-Bashforth and Adams-Moulton Predictor-Corrector Method408

7.3.1.1 Error Estimate410

7.3.1.2 Algorithm of Adams Predictor-Corrector Method411

7.3.2 Milne’s Method415

7.3.2.1 Error Estimate416

7.3.2.2 Algorithm of Milne’s Method417

7.3.3 Nystrom Method421

7.4 System of Ordinary Differential Equations of First-Order423

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

7.5 Differential Equations of Higher Order428

7.6 Boundary Value Problems430

7.6.1 Finite Difference Method431

7.6.1.1 Boundary Conditions Involving the Derivative435

7.6.1.2 Nonlinear Second-Order Differential Equation438

7.6.2 Shooting Method442

7.6.3 Collocation Method448

7.6.4 Galerkin Method452

7.7 Stability of an Initial Value Problem454

7.7.1 Stability Analysis of Single Step Methods456

7.7.1.1 Stability of Euler’s Method456

7.7.1.2 Stability of the Backward Euler Method458

7.7.1.3 Stability of R-K Methods459

7.7.2 Stability Analysis of General Multistep Methods460

7.7.2.1 General Methods for Finding the Interval of Absolute Stability465

7.8 Stiff Differential Equations468

7.9 A-stability and L-stability469

7.9.1 A-stability469

7.9.2 L-stability471

Exercises471

Chapter 8 Matrix Eigenvalue Problem479

8.1 Introduction479

8.1.1 Characteristic Equation，Eigenvalue，and Eigenvector of a Square Matrix479

8.1.2 Similar Matrices and Diagonalizable Matrix480

8.2 Inclusion of Eigenvalues481

8.2.1 Gerschgorin’s Discs481

8.2.2 Gerschgorin’s Theorem481

8.3 Householder’s Method483

8.3.1 Algorithm for Householder’s Method487

8.4 The QR Method490

8.4.1 Algorithm for the QR Method492

8.4.2 The QR Method with Shift498

8.5 Power Method505

8.5.1 Algorithm of Power Method512

8.6 Inverse Power Method516

8.6.1 Algorithm of Inverse Power Method517

8.7 Jacobi’s Method527

8.8 Givens Method531

8.8.1 Eigenvalues of a Symmetric Tridiagonal Matrix532

Exercises535

Chapter 9 Approximation of Functions545

9.1 Introduction545

9.1.1 Bernstein Polynomials and Its Properties546

9.2 Least Square Curve Fitting549

9.2.1 Straight Line Fitting549

9.2.2 Fitting of kth Degree Polynomial551

9.3 Least Squares Approximation553

9.4 Orthogonal Polynomials554

9.4.1 Weight Function554

9.4.2 Gram-Schmidt Orthogonalization Process557

9.5 The Minimax Polynomial Approximation568

9.5.1 Characterization of the Minimax Polynomial571

9.5.2 Existence of the Minimax Polynomial573

9.5.3 Uniqueness of the Minimax Polynomial574

9.5.4 The Near-Minimax Polynomial575

9.6 B-Splines577

9.6.1 Function Approximation by Cubic B-Spline580

9.7 Pade Approximation583

Exercises587

Chapter 10 Numerical Solutions of Partial Differential Equations591

10.1 Introduction591

10.2 Classification of PDEs of Second Order591

10.3 Types of Boundary Conditions and Problems592

10.4 Finite Difference Approximations to Partial Derivatives593

10.5 Parabolic PDEs594

10.5.1 Explicit FDM594

10.5.1.1 Algorithm for Solving Parabolic PDE by FDM596

10.5.2 Crank-Nicolson Implicit Method598

10.5.2.1 Algorithm for Solving Parabolic PDE by the Crank-Nicolson Method599

10.6 Hyperbolic PDEs603

10.6.1 Explicit Central Difference Method603

10.6.1.1 Algorithm for Solving Hyperbolic PDE by the Explicit Central Difference Method605

10.6.2 Implicit FDM606

10.7 Elliptic PDEs608

10.7.1 Laplace Equation614

10.7.2 Algorithm for Solving Laplace Equation by SOR Method617

10.8 Alternating Direction Implicit Method621

10.8.1 Algorithm for Two-Dimensional Parabolic PDE by ADI Method623

10.9 Stability Analysis of the Numerical Schemes627

Exercises631

Chapter 11 An Introduction to the Finite Element Method641

11.1 Introduction641

11.2 Piecewise Linear Basis Functions641

11.3 The Rayleigh-Ritz Method642

11.3.1 Algorithm of Rayleigh-Ritz Method645

11.4 The Galerkin Method651

Further Reading651

Exercises652

Answers655

Bibliography673

Index675