Numerical Linear Algebra with Applications (eBook)

Using MATLAB and Octave

William Ford (Autor)

eBook Download: PDF | EPUB

2014 | 1. Auflage
628 Seiten
Elsevier Science (Verlag)
978-0-12-394784-0 (ISBN)

Infos

Numerical Linear Algebra with Applications is designed for those who want to gain a practical knowledge of modern computational techniques for the numerical solution of linear algebra problems, using MATLAB as the vehicle for computation. The book contains all the material necessary for a first year graduate or advanced undergraduate course on numerical linear algebra with numerous applications to engineering and science. With a unified presentation of computation, basic algorithm analysis, and numerical methods to compute solutions, this book is ideal for solving real-world problems. The text consists of six introductory chapters that thoroughly provide the required background for those who have not taken a course in applied or theoretical linear algebra. It explains in great detail the algorithms necessary for the accurate computation of the solution to the most frequently occurring problems in numerical linear algebra. In addition to examples from engineering and science applications, proofs of required results are provided without leaving out critical details. The Preface suggests ways in which the book can be used with or without an intensive study of proofs. This book will be a useful reference for graduate or advanced undergraduate students in engineering, science, and mathematics. It will also appeal to professionals in engineering and science, such as practicing engineers who want to see how numerical linear algebra problems can be solved using a programming language such as MATLAB, MAPLE, or Mathematica. - Six introductory chapters that thoroughly provide the required background for those who have not taken a course in applied or theoretical linear algebra - Detailed explanations and examples - A through discussion of the algorithms necessary for the accurate computation of the solution to the most frequently occurring problems in numerical linear algebra - Examples from engineering and science applications

William Ford completed his undergraduate degree at MIT, having majored in mathematics and minored in electrical engineering. He went on to complete a Ph.D. in mathematics at the University of Illinois, Urbana-Champaign, with his thesis paper entitled 'Numerical Solution of Pseudo-parabolic Partial Differential Equations,' and after two years of researching and teaching within the Department of Mathematics at Clemson University he joined the faculty of the Mathematics Department at the University of the Pacific, in Stockton, California. Here he went on to become a founding member of the Department of the Computer Science. Beginning in the 1980s, he and William Topp began jointly publishing books, that included a Motorola 68000 assembly language book through D.C. Heath, a book on data structures with C++ through Prentice Hall, and a book on data structures with Java through Prentice Hall. Dr. Ford additionally developed an IDE (Integrated Development Environment) named 'EZJava' to accompany the Java book and served as the Chair of the Computer Science Department until his retirement in 2014.

Inhalt

Front Cover 1
Numerical Linear Algebra with Applications 4
Copyright 5
Dedication 6
Contents 8
List of Figures 14
List of Algorithms 18
Preface 20
Matrices 28
Matrix Arithmetic 28
Matrix Product 29
The Trace 32
MATLAB Examples 33
Linear Transformations 34
Rotations 34
Powers of Matrices 38
Nonsingular Matrices 40
The Matrix Transpose and Symmetric Matrices 43
Chapter Summary 45
Problems 46
MATLAB Problems 49
Linear Equations 52
Introduction to Linear Equations 52
Solving Square Linear Systems 54
Gaussian Elimination 55
Upper-Triangular Form 56
Systematic Solution of Linear Systems 58
Computing the Inverse 61
Homogeneous Systems 63
Application: A Truss 64
Application: Electrical Circuit 66
Chapter Summary 67
Problems 69
MATLAB Problems 70
Subspaces 74
Introduction 74
Subspaces of Rn 74
Linear Independence 76
Basis of a Subspace 77
The Rank of a Matrix 78
Chapter Summary 82
Problems 83
MATLAB Problems 84
Determinants 86
Developing the Determinant of a 2bold0mu mumu section2 and a 3bold0mu mumu section3 Matrix 86
Expansion by Minors 87
Computing a Determinant Using Row Operations 91
Application: Encryption 98
Chapter Summary 100
Problems 101
MATLAB Problems 103
Eigenvalues and Eigenvectors 106
Definitions and Examples 106
Selected Properties of Eigenvalues and Eigenvectors 110
Diagonalization 111
Powers of Matrices 115
Applications 116
Electric Circuit 116
Irreducible Matrices 118
Ranking of Teams Using Eigenvectors 121
Computing Eigenvalues and Eigenvectors using MATLAB 122
Chapter Summary 123
Problems 124
MATLAB Problems 126
Orthogonal Vectors and Matrices 130
Introduction 130
The Inner Product 131
Orthogonal Matrices 134
Symmetric Matrices and Orthogonality 136
The L2 Inner Product 137
The Cauchy-Schwarz Inequality 138
Signal Comparison 139
Chapter Summary 140
Problems 141
MATLAB Problems 143
Vector and Matrix Norms 146
Vector Norms 146
Properties of the 2-Norm 148
Spherical Coordinates 150
Matrix Norms 153
The Frobenius Matrix Norm 154
Induced Matrix Norms 154
Submultiplicative Matrix Norms 158
Computing the Matrix 2-Norm 159
Properties of the Matrix 2-Norm 163
Chapter Summary 165
Problems 167
MATLAB Problems 169
Floating Point Arithmetic 172
Integer Representation 172
Floating-Point Representation 174
Mapping from Real Numbers to Floating-Point Numbers 175
Floating-Point Arithmetic 177
Relative Error 177
Rounding Error Bounds 178
Addition 178
Multiplication 178
Matrix Operations 178
Minimizing Errors 182
Avoid Adding a Huge Number to a Small Number 182
Avoid Subtracting Numbers That Are Close 182
Chapter Summary 183
Problems 185
MATLAB Problems 187
Algorithms 190
Pseudocode Examples 190
Inner Product of Two Vectors 191
Computing the Frobenius Norm 191
Matrix Multiplication 191
Block Matrices 192
Algorithm Efficiency 193
Smaller Flop Count Is Not Always Better 195
Measuring Truncation Error 195
The Solution to Upper and Lower Triangular Systems 195
Efficiency Analysis 197
The Thomas Algorithm 198
Efficiency Analysis 200
Chapter Summary 201
Problems 202
MATLAB Problems 204
Conditioning of Problems and Stability of Algorithms 208
Why Do We Need Numerical Linear Algebra? 208
Computation Error 210
Forward Error 210
Backward Error 211
Algorithm Stability 212
Examples of Unstable Algorithms 213
Conditioning of a Problem 214
Perturbation Analysis for Solving a Linear System 217
Properties of the Matrix Condition Number 220
MATLAB Computation of a Matrix Condition Number 222
Estimating the Condition Number 222
Introduction to Perturbation Analysis of Eigenvalue Problems 223
Chapter Summary 224
Problems 226
MATLAB Problems 227
Gaussian Elimination and the LU Decomposition 232
LU Decomposition 232
Using LU to Solve Equations 233
Elementary Row Matrices 235
Derivation of the LU Decomposition 237
Colon Notation 241
The LU Decomposition Algorithm 243
LU Decomposition Flop Count 244
Gaussian Elimination with Partial Pivoting 245
Derivation of PA=LU 246
Algorithm for Gaussian Elimination with Partial Pivoting 250
Using the LU Decomposition to Solve Axi = bi, 1i k 252
Finding A–1 253
Stability and Efficiency of Gaussian Elimination 254
Iterative Refinement 255
Chapter Summary 257
Problems 259
MATLAB Problems 263
Linear System Applications 268
Fourier Series 268
The Square Wave 270
Finite Difference Approximations 271
Steady-State Heat and Diffusion 272
Least-Squares Polynomial Fitting 274
Normal Equations 276
Cubic Spline Interpolation 279
Chapter Summary 283
Problems 284
MATLAB Problems 287
Important Special Systems 290
Tridiagonal Systems 290
Symmetric Positive Definite Matrices 294
Applications 296
The Cholesky Decomposition 296
Computing the Cholesky Decomposition 297
Efficiency 299
Solving Ax = b If A Is Positive Definite 299
Stability 300
Chapter Summary 300
Problems 301
MATLAB Problems 304
Gram-Schmidt Orthonormalization 308
The Gram-Schmidt Process 308
Numerical Stability of the Gram-Schmidt Process 311
The QR Decomposition 314
Efficiency 316
Stability 317
Applications of the QR Decomposition 317
Computing the Determinant 318
Finding an Orthonormal Basis for the Range of a Matrix 318
Chapter Summary 319
Problems 319
MATLAB Problems 320
The Singular Value Decomposition 326
The SVD Theorem 326
Using the SVD to Determine Properties of a Matrix 329
The Four Fundamental Subspaces of a Matrix 331
SVD and Matrix Norms 333
Geometric Interpretation of the SVD 334
Computing the SVD Using MATLAB 335
Computing A–1 336
Image Compression Using the SVD 337
Image Compression Using MATLAB 338
Additional Uses 340
Final Comments 341
Chapter Summary 341
Problems 343
MATLAB Problems 344
Least-Squares Problems 348
Existence and Uniqueness of Least-Squares Solutions 349
Existence and Uniqueness Theorem 349
Normal Equations and Least-Squares Solutions 351
The Pseudoinverse, m n 351
The Pseudoinverse, m< n
Solving Overdetermined Least-Squares Problems 352
Using the Normal Equations 353
Efficiency 353
Computational Note 353
Using the QR Decomposition 354
Efficiency 354
Using the SVD 356
Efficiency 356
Remark on Curve Fitting 359
Conditioning of Least-Squares Problems 359
Sensitivity when using the Normal Equations 360
Rank-Deficient Least-Squares Problems 360
Efficiency 365
Underdetermined Linear Systems 365
Efficiency 368
Chapter Summary 368
Problems 369
MATLAB Problems 370
Implementing the QR Decomposition 378
Review of the QR Decomposition Using Gram-Schmidt 378
Givens Rotations 379
Zeroing a Particular Entry in a Vector 380
Creating a Sequence of Zeros in a Vector Using Givens Rotations 382
Product of a Givens Matrix with a General Matrix 383
Zeroing-Out Column Entries in a Matrix Using Givens Rotations 384
Accurate Computation of the Givens Parameters 385
The Givens Algorithm for the QR Decomposition 386
The Reduced QR Decomposition 388
Efficiency 389
Householder Reflections 389
Matrix Column Zeroing Using Householder Reflections 392
Implicit Computation with Householder Reflections 394
Computing the QR Decomposition Using Householder Reflections 395
Efficiency and Stability 399
Chapter Summary 400
Problems 400
MATLAB Problems 403
The Algebraic Eigenvalue Problem 406
Applications of the Eigenvalue Problem 406
Vibrations and Resonance 407
The Leslie Model in Population Ecology 410
Buckling of a Column 413
Computation of Selected Eigenvalues and Eigenvectors 415
Additional Property of a Diagonalizable Matrix 416
The Power Method for Computing the Dominant Eigenvalue 417
Computing the Smallest Eigenvalue and Corresponding Eigenvector 420
The Basic QR Iteration 421
Transformation to Upper Hessenberg Form 422
Efficiency and Stability 427
The Unshifted Hessenberg QR Iteration 427
Efficiency 430
The Shifted Hessenberg QR Iteration 430
A Single Shift 431
Schur's Triangularization 432
The Francis Algorithm 436
Francis Iteration of Degree One 436
Preparation for Understanding the Iteration 436
Demonstration of the Francis Iteration of Degree One 436
Francis Iteration of Degree Two 440
Computing Eigenvectors 447
Hessenberg Inverse Iteration 448
Computing Both Eigenvalues and TheirCorresponding Eigenvectors 450
Sensitivity of Eigenvalues to Perturbations 451
Sensitivity of Eigenvectors 454
Chapter Summary 455
Problems 457
MATLAB Problems 459
The Symmetric Eigenvalue Problem 466
The Spectral Theorem and Properties of a Symmetric Matrix 466
Properties of a Symmetric Matrix 467
The Jacobi Method 467
Computing Eigenvectors Using the Jacobi Iteration 471
The Cyclic-by-Row Jacobi Algorithm 471
The Symmetric QR Iteration Method 473
Tridiagonal Reduction of a Symmetric Matrix 476
Efficiency 476
Orthogonal Transformation to a Diagonal Matrix 478
The Symmetric Francis Algorithm 479
Theoretical Overview and Efficiency 480
The Bisection Method 480
Efficiency 484
Matrix A Is Not Unreduced 484
The Divide-and-Conquer Method 485
Using dconquer 488
Chapter Summary 488
Problems 490
MATLAB Problems 492
Basic Iterative Methods 496
Jacobi Method 496
The Gauss-Seidel Iterative Method 497
The SOR Iteration 498
Convergence of the Basic Iterative Methods 500
Matrix Form of the Jacobi Iteration 500
Matrix Form of the Gauss-Seidel Iteration 500
Matrix Form for SOR 501
Conditions Guaranteeing Convergence 501
The Spectral Radius and Rate of Convergence 503
Convergence of the Jacobi and Gauss-Seidel Methods for Diagonally Dominant Matrices 504
Choosing for SOR 505
Application: Poisson's Equation 505
Chapter Summary 508
Problems 510
MATLAB Problems 513
Krylov Subspace Methods 518
Large, Sparse Matrices 518
Storage of Sparse Matrices 519
The CG Method 520
The Method of Steepest Descent 520
From Steepest Descent to CG 524
Convergence 528
Preconditioning 528
Preconditioning for CG 530
Incomplete Cholesky Decomposition 530
SSOR Preconditioner 533
Krylov Subspaces 535
The Arnoldi Method 536
Efficiency 536
An Alternative Formulation of the Arnoldi Decomposition 538
GMRES 539
Convergence 539
Preconditioned GMRES 541
The Symmetric Lanczos Method 543
Loss of Orthogonality with the Lanczos Process 543
The MINRES Method 546
Convergence 546
Comparison of Iterative Methods 547
Poisson's Equation Revisited 548
The Biharmonic Equation 550
Chapter Summary 551
Problems 553
MATLAB Problems 555
Large Sparse Eigenvalue Problems 560
The Power Method 560
Eigenvalue Computation Using the Arnoldi Process 561
Estimating Eigenvalues Without Restart or Deflation 562
Estimating Eigenvalues Using Restart 563
A Restart Method Using Deflation 564
Restart Strategies 566
The Implicitly Restarted Arnoldi Method 567
Convergence of the Arnoldi Iteration 571
Eigenvalue Computation Using the Lanczos Process 571
Mathematically Provable Properties 573
Chapter Summary 574
Problems 575
MATLAB Problems 575
Computing the Singular Value Decomposition 578
Development of the One-Sided Jacobi Methodfor Computing the Reduced SVD 578
Stability of Singular Value Computation 581
The One-Sided Jacobi Algorithm 582
Faster and More Accurate Jacobi Algorithm 584
Transforming a Matrix to Upper-Bidiagonal Form 585
Demmel and Kahan Zero-Shift QR Downward Sweep Algorithm 586
Chapter Summary 592
Problems 592
MATLAB Problems 593
Complex Numbers 596
Constructing the Complex Numbers 596
Calculating with Complex Numbers 597
Geometric Representation of C 598
Complex Conjugate 598
Complex Numbers in MATLAB 600
Euler's Formula 602
Problems 602
MATLAB Problems 603
Mathematical Induction 606
Problems 608
Chebyshev Polynomials 610
Definition 610
Properties 611
Problems 611
MATLAB Problems 612
Glossary 614
Bibliography 622
Index 624

Textauszug

List of Figures

Fig. 0.1 NLALIB hierarchy. xxv

Fig. 1.1 Matrix multiplication. 3

Fig. 1.2 Rotating the xy-plane. 7

Fig. 1.3 Rotated line 8

Fig. 1.4 Rotate three-dimensional coordinate system. 9

Fig. 1.5 Translate a point in two dimensions. 9

Fig. 1.6 Rotate a line about a point. 10

Fig. 1.7 Rotation about an arbitrary point. 11

Fig. 1.8 Undirected graph. 12

Fig. 2.1 Polynomial passing through four points. 26

Fig. 2.2 Inconsistent equations. 31

Fig. 2.3 Truss. 38

Fig. 2.4 Electrical circuit. 39

Fig. 2.5 Truss problem. 45

Fig. 2.6 Circuit problem. 45

Fig. 3.1 Subspace spanned by two vectors. 48

Fig. 4.1 Geometrical interpretation of the determinant. 75

Fig. 5.1 Direction of eigenvectors. 80

Fig. 5.2 Circuit with an inductor. 89

Fig. 5.3 Currents in the RL circuit. 92

Fig. 5.4 Digraph of an irreducible matrix. 93

Fig. 5.5 Hanowa matrix. 101

Fig. 6.1 Distance between points. 104

Fig. 6.2 Equality, addition, and subtraction of vectors. 104

Fig. 6.3 Scalar multiplication of vectors. 104

Fig. 6.4 Vector length. 106

Fig. 6.5 Geometric interpretation of the inner product. 106

Fig. 6.6 Law of cosines. 106

Fig. 6.7 Triangle inequality. 112

Fig. 6.8 Signal comparison. 112

Fig. 6.9 Projection of one vector onto another. 115

Fig. 7.1 Effect of an orthogonal transformation on a vector. 122

Fig. 7.2 Spherical coordinates. 123

Fig. 7.3 Orthonormal basis for spherical coordinates. 124

Fig. 7.4 Point in spherical coordinate basis and Cartesian coordinates. 125

Fig. 7.5 Function specified in spherical coordinates. 126

Fig. 7.6 Effect of a matrix on vectors. 128

Fig. 7.7 Unit spheres in three norms. 129

Fig. 7.8 Image of the unit circle. 133

Fig. 8.1 Floating-point number system. 149

Fig. 8.2 Map of IEEE double-precision floating-point. 150

Fig. 9.1 Matrix multiplication. 165

Fig. 10.1 Forward and backward errors. 184

Fig. 10.2 The Wilkinson polynomial. 187

Fig. 10.3 Ill-conditioned Cauchy problem. 188

Fig. 10.4 Conditioning of a problem. 189

Fig. 11.1 LU decomposition of a matrix. 206

Fig. 11.2 k × k submatrix. 215

Fig. 11.3 Gaussian elimination flop count. 217

Fig. 12.1 Square wave with period 2π. 244

Fig. 12.2 Fourier series converging to a square wave. 244

Fig. 12.3 The heat equation: a thin rod insulated on its sides. 245

Fig. 12.4 Numerical solution of the heat equation: subdivisions of the x and t axes. 245

Fig. 12.5 Numerical solution of the heat equation:locally related points in the grid. 246

Fig. 12.6 Grid for the numerical solution of the heat equation. 246

Fig. 12.7 Graph of the solution for the heat equation problem. 247

Fig. 12.8 Linear least-squares approximation. 250

Fig. 12.9 Quadratic least-squares approximation. 251

Fig. 12.10 Estimating absolute zero. 252

Fig. 12.11 Linear interpolation. 253

Fig. 12.12 Cubic splines. 253

Fig. 12.13 Cubic spline approximation. 256

Fig. 12.14 Sawtooth wave with period 2π. 258

Fig. 13.1 Conductance matrix. 270

Fig. 14.1 Vector orthogonal projection. 282

Fig. 14.2 Removing the orthogonal projection. 282

Fig. 14.3 Result of the first three steps of Gram-Schmidt. 283

Fig. 15.1 The four fundamental subspaces of a matrix. 305

Fig. 15.2 SVD rotation and distortion. 308

Fig. 15.3 (a) Lena (512 × 512) and (b) lena using 35 modes. 312

Fig. 15.4 Lena using 125 modes. 312

Fig. 15.5 Singular value graph of lena. 313

Fig. 15.6 SVD image capture. 314

Fig. 16.1 Geometric interpretation of the least-squares solution. 322

Fig. 16.2 An overdetermined system. 322

Fig. 16.3 Least-squares estimate for the power function. 329

Fig. 16.4 The reduced SVD for a full rank matrix. 330

Fig. 16.5 Velocity of an enzymatic reaction. 332

Fig. 16.6 Underdetermined system. 339

Fig. 17.1 Givens matrix. 353

Fig. 17.2 Givens rotation. 354

Fig. 17.3 Householder reflection. 363

Fig. 17.4 Linear combination associated with Householder reflection. 363

Fig. 17.5 Householder reflection to a multiple of e1. 366

Fig. 17.6 Transforming an m × n matrix to upper triangular form using householder reflections. 369

Fig. 17.7 Householder reflections and submatrices. 369

Fig. 17.8 Householder reflection for a submatrix. 369

Fig. 18.1 Tacoma Narrows Bridge collapse. 380

Fig. 18.2 Mass-spring system. 380

Fig. 18.3 Solution to a system of ordinary differential equations. 382

Fig. 18.4 Populations using the Leslie matrix. 387

Fig. 18.5 Column buckling. 387

Fig. 18.6 Deflection curves for critical loads P1, P2, and P3. 389

Fig. 18.7 Reduced Hessenberg matrix. 401

Fig. 18.8 Inductive step in Schur’s triangularization. 407

Fig. 18.9 Schur’s triangularization. 407

Fig. 18.10 Eigenvalues of a 2 × 2 matrix as shifts. 413

Fig. 18.11 Springs problem. 430

Fig. 19.1 Bisection. 454

Fig. 19.2 Interlacing. 454

Fig. 19.3 Bisection method: λk located to the left. 456

Fig. 19.4 Bisection method: λk located to the right. 457

Fig. 19.5 Bisection and multiple eigenvalues. 458

Fig. 19.6 Secular equation. 460

Fig. 20.1 SOR spectral radius. 479

Fig. 20.2 Region in the plane. 479

Fig. 20.3 Five-point stencil. 480

Fig. 20.4 Poisson’s equation. (a) Approximate solution and (b) analytical solution. 481

Fig. 20.5 One-dimensional Poisson equation grid. 484

Fig. 20.6 One-dimensional red-black GS. 486

Fig. 21.1 Examples of...

Produkt-Details

• Erscheint lt. Verlag: 14.9.2014
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge
• Themenwelt: Informatik ► Theorie / Studium ► Algorithmen
• Themenwelt: Mathematik / Informatik ► Mathematik ► Algebra
• Themenwelt: Mathematik / Informatik ► Mathematik ► Analysis
• ISBN-10: 0-12-394784-7 / 0123947847
• ISBN-13: 978-0-12-394784-0 / 9780123947840