An Introduction to Numerical Analysis for Electrical and Computer Engineers

Preface xiii

1 Functional Analysis Ideas 1

1.1 Introduction 1

1.2 Some Sets 2

1.3 Some Special Mappings: Metrics, Norms, and Inner Products 4

1.3.1 Metrics and Metric Spaces 6

1.3.2 Norms and Normed Spaces 8

1.3.3 Inner Products and Inner Product Spaces 14

1.4 The Discrete Fourier Series (DFS) 25

Appendix 1.A Complex Arithmetic 28

Appendix 1.B Elementary Logic 31

References 32

Problems 33

2 Number Representations 38

2.1 Introduction 38

2.2 Fixed-Point Representations 38

2.3 Floating-Point Representations 42

2.4 Rounding Effects in Dot Product Computation 48

2.5 Machine Epsilon 53

Appendix 2.A Review of Binary Number Codes 54

References 59

Problems 59

3 Sequences and Series 63

3.1 Introduction 63

3.2 Cauchy Sequences and Complete Spaces 63

3.3 Pointwise Convergence and Uniform Convergence 70

3.4 Fourier Series 73

3.5 Taylor Series 78

3.6 Asymptotic Series 97

3.7 More on the Dirichlet Kernel 103

3.8 Final Remarks 107

Appendix 3.A COordinate Rotation DIgital Computing (CORDIC) 107

3.A.1 Introduction 107

3.A.2 The Concept of a Discrete Basis 108

3.A.3 Rotating Vectors in the Plane 112

3.A.4 Computing Arctangents 114

3.A.5 Final Remarks 115

Appendix 3.B Mathematical Induction 116

Appendix 3.C Catastrophic Cancellation 117

References 119

Problems 120

4 Linear Systems of Equations 127

4.1 Introduction 127

4.2 Least-Squares Approximation and Linear Systems 127

4.3 Least-Squares Approximation and Ill-Conditioned Linear Systems 132

4.4 Condition Numbers 135

4.5 LU Decomposition 148

4.6 Least-Squares Problems and QR Decomposition 161

4.7 Iterative Methods for Linear Systems 176

4.8 Final Remarks 186

Appendix 4.A Hilbert Matrix Inverses 186

Appendix 4.B SVD and Least Squares 191

References 193

Problems 194

5 Orthogonal Polynomials 207

5.1 Introduction 207

5.2 General Properties of Orthogonal Polynomials 207

5.3 Chebyshev Polynomials 218

5.4 Hermite Polynomials 225

5.5 Legendre Polynomials 229

5.6 An Example of Orthogonal Polynomial Least-Squares Approximation 235

5.7 Uniform Approximation 238

References 241

Problems 241

6 Interpolation 251

6.1 Introduction 251

6.2 Lagrange Interpolation 252

6.3 Newton Interpolation 257

6.4 Hermite Interpolation 266

6.5 Spline Interpolation 269

References 284

Problems 285

7 Nonlinear Systems of Equations 290

7.1 Introduction 290

7.2 Bisection Method 292

7.3 Fixed-Point Method 296

7.4 Newton–Raphson Method 305

7.4.1 The Method 305

7.4.2 Rate of Convergence Analysis 309

7.4.3 Breakdown Phenomena 311

7.5 Systems of Nonlinear Equations 312

7.5.1 Fixed-Point Method 312

7.5.2 Newton–Raphson Method 318

7.6 Chaotic Phenomena and a Cryptography Application 323

References 332

Problems 333

8 Unconstrained Optimization 341

8.1 Introduction 341

8.2 Problem Statement and Preliminaries 341

8.3 Line Searches 345

8.4 Newton’s Method 353

8.5 Equality Constraints and Lagrange Multipliers 357

Appendix 8.A MATLAB Code for Golden Section Search 362

References 364

Problems 364

9 Numerical Integration and Differentiation 369

9.1 Introduction 369

9.2 Trapezoidal Rule 371

9.3 Simpson’s Rule 378

9.4 Gaussian Quadrature 385

9.5 Romberg Integration 393

9.6 Numerical Differentiation 401

References 406

Problems 406

10 Numerical Solution of Ordinary Differential Equations 415

10.1 Introduction 415

10.2 First-Order ODEs 421

10.3 Systems of First-Order ODEs 442

10.4 Multistep Methods for ODEs 455

10.4.1 Adams–Bashforth Methods 459

10.4.2 Adams–Moulton Methods 461

10.4.3 Comments on the Adams Families 462

10.5 Variable-Step-Size (Adaptive) Methods for ODEs 464

10.6 Stiff Systems 467

10.7 Final Remarks 469

Appendix 10.A MATLAB Code for Example 10.8 469

Appendix 10.B MATLAB Code for Example 10.13 470

References 472

Problems 473

11 Numerical Methods for Eigenproblems 480

11.1 Introduction 480

11.2 Review of Eigenvalues and Eigenvectors 480

11.3 The Matrix Exponential 488

11.4 The Power Methods 498

11.5 QR Iterations 508

References 518

Problems 519

12 Numerical Solution of Partial Differential Equations 525

12.1 Introduction 525

12.2 A Brief Overview of Partial Differential Equations 525

12.3 Applications of Hyperbolic PDEs 528

12.3.1 The Vibrating String 528

12.3.2 Plane Electromagnetic Waves 534

12.4 The Finite-Difference (FD) Method 545

12.5 The Finite-Difference Time-Domain (FDTD) Method 550

Appendix 12.A MATLAB Code for Example 12.5 557

References 560

Problems 561

13 An Introduction to MATLAB 565

13.1 Introduction 565

13.2 Startup 565

13.3 Some Basic Operators, Operations, and Functions 566

13.4 Working with Polynomials 571

13.5 Loops 572

13.6 Plotting and M-Files 573

References 577

Index 579