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.
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
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
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...
| Erscheint lt. Verlag | 14.9.2014 |
|---|---|
| Sprache | englisch |
| Themenwelt | Mathematik / Informatik ► Informatik ► Programmiersprachen / -werkzeuge |
| Informatik ► Theorie / Studium ► Algorithmen | |
| Mathematik / Informatik ► Mathematik ► Algebra | |
| Mathematik / Informatik ► Mathematik ► Analysis | |
| ISBN-10 | 0-12-394784-7 / 0123947847 |
| ISBN-13 | 978-0-12-394784-0 / 9780123947840 |
| Haben Sie eine Frage zum Produkt? |
PDF (Adobe DRM)Größe: 26,1 MB
Kopierschutz: Adobe-DRM
Adobe-DRM ist ein Kopierschutz, der das eBook vor Mißbrauch schützen soll. Dabei wird das eBook bereits beim Download auf Ihre persönliche Adobe-ID autorisiert. Lesen können Sie das eBook dann nur auf den Geräten, welche ebenfalls auf Ihre Adobe-ID registriert sind.
Details zum Adobe-DRM
Dateiformat: PDF (Portable Document Format)
Mit einem festen Seitenlayout eignet sich die PDF besonders für Fachbücher mit Spalten, Tabellen und Abbildungen. Eine PDF kann auf fast allen Geräten angezeigt werden, ist aber für kleine Displays (Smartphone, eReader) nur eingeschränkt geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen eine
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen eine
Geräteliste und zusätzliche Hinweise
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
EPUB (Adobe DRM)Größe: 17,4 MB
Kopierschutz: Adobe-DRM
Adobe-DRM ist ein Kopierschutz, der das eBook vor Mißbrauch schützen soll. Dabei wird das eBook bereits beim Download auf Ihre persönliche Adobe-ID autorisiert. Lesen können Sie das eBook dann nur auf den Geräten, welche ebenfalls auf Ihre Adobe-ID registriert sind.
Details zum Adobe-DRM
Dateiformat: EPUB (Electronic Publication)
EPUB ist ein offener Standard für eBooks und eignet sich besonders zur Darstellung von Belletristik und Sachbüchern. Der Fließtext wird dynamisch an die Display- und Schriftgröße angepasst. Auch für mobile Lesegeräte ist EPUB daher gut geeignet.
Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen eine
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen eine
Geräteliste und zusätzliche Hinweise
Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.
aus dem Bereich
