Ford Numerical Linear Algebra with Applications

Using MATLAB and Octave
1. Auflage 2014
ISBN: 978-0-12-394784-0
Verlag: Elsevier Science & Techn.
Format: EPUB
Kopierschutz: 6 - ePub Watermark

E-Book, Englisch, 628 Seiten

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.

Autoren/Hrsg.

Ford, William

Inhaltsverzeichnis

1;Front Cover;1
2;Numerical Linear Algebra with Applications;4
3;Copyright;5
4;Dedication;6
5;Contents;8
6;List of Figures;14
7;List of Algorithms;18
8;Preface;20
9;Matrices;28
9.1;Matrix Arithmetic;28
9.1.1;Matrix Product;29
9.1.2;The Trace;32
9.1.3;MATLAB Examples;33
9.2;Linear Transformations;34
9.2.1;Rotations;34
9.3;Powers of Matrices;38
9.4;Nonsingular Matrices;40
9.5;The Matrix Transpose and Symmetric Matrices;43
9.6;Chapter Summary;45
9.7;Problems;46
9.7.1;MATLAB Problems;49
10;Linear Equations;52
10.1;Introduction to Linear Equations;52
10.2;Solving Square Linear Systems;54
10.3;Gaussian Elimination;55
10.3.1;Upper-Triangular Form;56
10.4;Systematic Solution of Linear Systems;58
10.5;Computing the Inverse;61
10.6;Homogeneous Systems;63
10.7;Application: A Truss;64
10.8;Application: Electrical Circuit;66
10.9;Chapter Summary;67
10.10;Problems;69
10.10.1;MATLAB Problems;70
11;Subspaces;74
11.1;Introduction;74
11.2;Subspaces of Rn;74
11.3;Linear Independence;76
11.4;Basis of a Subspace;77
11.5;The Rank of a Matrix;78
11.6;Chapter Summary;82
11.7;Problems;83
11.7.1;MATLAB Problems;84
12;Determinants;86
12.1;Developing the Determinant of a 2bold0mu mumu section2 and a 3bold0mu mumu section3 Matrix;86
12.2;Expansion by Minors;87
12.3;Computing a Determinant Using Row Operations;91
12.4;Application: Encryption;98
12.5;Chapter Summary;100
12.6;Problems;101
12.6.1;MATLAB Problems;103
13;Eigenvalues and Eigenvectors;106
13.1;Definitions and Examples;106
13.2;Selected Properties of Eigenvalues and Eigenvectors;110
13.3;Diagonalization;111
13.3.1;Powers of Matrices;115
13.4;Applications;116
13.4.1;Electric Circuit;116
13.4.2;Irreducible Matrices;118
13.4.3;Ranking of Teams Using Eigenvectors;121
13.5;Computing Eigenvalues and Eigenvectors using MATLAB;122
13.6;Chapter Summary;123
13.7;Problems;124
13.7.1;MATLAB Problems;126
14;Orthogonal Vectors and Matrices;130
14.1;Introduction;130
14.2;The Inner Product;131
14.3;Orthogonal Matrices;134
14.4;Symmetric Matrices and Orthogonality;136
14.5;The L2 Inner Product;137
14.6;The Cauchy-Schwarz Inequality;138
14.7;Signal Comparison;139
14.8;Chapter Summary;140
14.9;Problems;141
14.9.1;MATLAB Problems;143
15;Vector and Matrix Norms;146
15.1;Vector Norms;146
15.1.1;Properties of the 2-Norm;148
15.1.2;Spherical Coordinates;150
15.2;Matrix Norms;153
15.2.1;The Frobenius Matrix Norm;154
15.2.2;Induced Matrix Norms;154
15.3;Submultiplicative Matrix Norms;158
15.4;Computing the Matrix 2-Norm;159
15.5;Properties of the Matrix 2-Norm;163
15.6;Chapter Summary;165
15.7;Problems;167
15.7.1;MATLAB Problems;169
16;Floating Point Arithmetic;172
16.1;Integer Representation;172
16.2;Floating-Point Representation;174
16.2.1;Mapping from Real Numbers to Floating-Point Numbers;175
16.3;Floating-Point Arithmetic;177
16.3.1;Relative Error;177
16.3.2;Rounding Error Bounds;178
16.3.2.1;Addition;178
16.3.2.2;Multiplication;178
16.3.2.3;Matrix Operations;178
16.4;Minimizing Errors;182
16.4.1;Avoid Adding a Huge Number to a Small Number;182
16.4.2;Avoid Subtracting Numbers That Are Close;182
16.5;Chapter Summary;183
16.6;Problems;185
16.6.1;MATLAB Problems;187
17;Algorithms;190
17.1;Pseudocode Examples;190
17.1.1;Inner Product of Two Vectors;191
17.1.2;Computing the Frobenius Norm;191
17.1.3;Matrix Multiplication;191
17.1.4;Block Matrices;192
17.2;Algorithm Efficiency;193
17.2.1;Smaller Flop Count Is Not Always Better;195
17.2.2;Measuring Truncation Error;195
17.3;The Solution to Upper and Lower Triangular Systems;195
17.3.1;Efficiency Analysis;197
17.4;The Thomas Algorithm;198
17.4.1;Efficiency Analysis;200
17.5;Chapter Summary;201
17.6;Problems;202
17.6.1;MATLAB Problems;204
18;Conditioning of Problems and Stability of Algorithms;208
18.1;Why Do We Need Numerical Linear Algebra?;208
18.2;Computation Error;210
18.2.1;Forward Error;210
18.2.2;Backward Error;211
18.3;Algorithm Stability;212
18.3.1;Examples of Unstable Algorithms;213
18.4;Conditioning of a Problem;214
18.5;Perturbation Analysis for Solving a Linear System;217
18.6;Properties of the Matrix Condition Number;220
18.7;MATLAB Computation of a Matrix Condition Number;222
18.8;Estimating the Condition Number;222
18.9;Introduction to Perturbation Analysis of Eigenvalue Problems;223
18.10;Chapter Summary;224
18.11;Problems;226
18.11.1;MATLAB Problems;227
19;Gaussian Elimination and the LU Decomposition;232
19.1;LU Decomposition;232
19.2;Using LU to Solve Equations;233
19.3;Elementary Row Matrices;235
19.4;Derivation of the LU Decomposition;237
19.4.1;Colon Notation;241
19.4.2;The LU Decomposition Algorithm;243
19.4.3;LU Decomposition Flop Count;244
19.5;Gaussian Elimination with Partial Pivoting;245
19.5.1;Derivation of PA=LU;246
19.5.2;Algorithm for Gaussian Elimination with Partial Pivoting;250
19.6;Using the LU Decomposition to Solve Axi = bi, 1i k;252
19.7;Finding A–1;253
19.8;Stability and Efficiency of Gaussian Elimination;254
19.9;Iterative Refinement;255
19.10;Chapter Summary;257
19.11;Problems;259
19.11.1;MATLAB Problems;263
20;Linear System Applications;268
20.1;Fourier Series;268
20.1.1;The Square Wave;270
20.2;Finite Difference Approximations;271
20.2.1;Steady-State Heat and Diffusion;272
20.3;Least-Squares Polynomial Fitting;274
20.3.1;Normal Equations;276
20.4;Cubic Spline Interpolation;279
20.5;Chapter Summary;283
20.6;Problems;284
20.6.1;MATLAB Problems;287
21;Important Special Systems;290
21.1;Tridiagonal Systems;290
21.2;Symmetric Positive Definite Matrices;294
21.2.1;Applications;296
21.3;The Cholesky Decomposition;296
21.3.1;Computing the Cholesky Decomposition;297
21.3.2;Efficiency;299
21.3.3;Solving Ax = b If A Is Positive Definite;299
21.3.4;Stability;300
21.4;Chapter Summary;300
21.5;Problems;301
21.5.1;MATLAB Problems;304
22;Gram-Schmidt Orthonormalization;308
22.1;The Gram-Schmidt Process;308
22.2;Numerical Stability of the Gram-Schmidt Process;311
22.3;The QR Decomposition;314
22.3.1;Efficiency;316
22.3.2;Stability;317
22.4;Applications of the QR Decomposition;317
22.4.1;Computing the Determinant;318
22.4.2;Finding an Orthonormal Basis for the Range of a Matrix;318
22.5;Chapter Summary;319
22.6;Problems;319
22.7;MATLAB Problems;320
23;The Singular Value Decomposition;326
23.1;The SVD Theorem;326
23.2;Using the SVD to Determine Properties of a Matrix;329
23.2.1;The Four Fundamental Subspaces of a Matrix;331
23.3;SVD and Matrix Norms;333
23.4;Geometric Interpretation of the SVD;334
23.5;Computing the SVD Using MATLAB;335
23.6;Computing A–1;336
23.7;Image Compression Using the SVD;337
23.7.1;Image Compression Using MATLAB;338
23.7.2;Additional Uses;340
23.8;Final Comments;341
23.9;Chapter Summary;341
23.10;Problems;343
23.10.1;MATLAB Problems;344
24;Least-Squares Problems;348
24.1;Existence and Uniqueness of Least-Squares Solutions;349
24.1.1;Existence and Uniqueness Theorem;349
24.1.2;Normal Equations and Least-Squares Solutions;351
24.1.3;The Pseudoinverse, m n;351
24.1.4;The Pseudoinverse, m

Leseproben

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 2p. 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 2p. 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...