by
James E. Gentle
Table of Contents
1 Computer Storage and Manipulation of Data ... 1
1.1 Digital Representation of Numeric Data ... 3
1.2 Computer Operations on Numeric Data ... 18
1.3 Numerical Algorithms and Analysis ... 26
Exercises ... 41
2 Basic Vector/Matrix Computations ... 47
2.1 Notation, Definitions, and Basic Properties ... 48
- 2.1.1 Operations on Vectors; Vector Spaces ... 48
- 2.1.2 Vectors and Matrices ... 52
- 2.1.3 Operations on Vectors and Matrices ... 55
- 2.1.4 Partitioned Matrices ... 58
- 2.1.5 Matrix Rank ... 59
- 2.1.6 Identity Matrices ... 60
- 2.1.7 Inverses ... 61
- 2.1.8 Linear Systems ... 62
- 2.1.9 Generalized Inverses ... 63
- 2.1.10 Other Special Vectors and Matrices ... 64
- 2.1.11 Eigenanalysis ... 67
- 2.1.12 Similarity Transformations ... 69
- 2.1.13 Norms ... 70
- 2.1.14 Matrix Norms ... 72
- 2.1.15 Orthogonal Transformations ... 74
- 2.1.16 Orthogonalization Transformations ... 74
- 2.1.17 Condition of Matrices ... 75
- 2.1.18 Matrix Derivatives ... 79
2.2 Computer Representations and Basic Operations ... 81
- 2.2.1 Computer Representation of Vectors and Matrices ... 81
- 2.2.2 Multiplication of Vectors and Matrices ... 82
Exercises ... 84
3 Solution of Linear Systems ... 87
3.1 Gaussian Elimination ... 87
3.2 Matrix Factorizations ... 92
- 3.2.1 $LU$ and $LDU$ Factorizations ... 92
- 3.2.2 Cholesky Factorization ... 93
- 3.2.3 $QR$ Factorization ... 95
- 3.2.4 Householder Transformations (Reflections) ... 97
- 3.2.5 Givens Transformations (Rotations) ... 99
- 3.2.6 Gram-Schmidt Transformations ... 102
- 3.2.7 Singular Value Factorization ... 102
- 3.2.8 Choice of Direct Methods ... 103
3.3 Iterative Methods ... 103
- 3.3.1 The Gauss-Seidel Method with Successive Overrelaxation ... 103
- 3.3.2 Solution of Linear Systems as an Optimization Problem; Conjugate Gradient Methods ... 104
3.4 Numerical Accuracy ... 107
3.5 Iterative Refinement ... 109
3.6 Updating a Solution ... 109
3.7 Overdetermined Systems; Least Squares ... 111
- 3.7.1 Full Rank Coefficient Matrix ... 112
- 3.7.2 Coefficient Matrix Not of Full Rank ... 113
- 3.7.3 Updating a Solution to an Overdetermined System ... 114
3.8 Other Computations for Linear Systems ... 115
- 3.8.1 Rank Determination ... 115
- 3.8.2 Computing the Determinant ... 115
- 3.8.3 Computing the Condition Number ... 115
Exercises ... 117
4 Computation of Eigenvectors and Eigenvalues and the Singular Value
Decomposition ... 123
4.1 Power Method ... 124
4.2 Jacobi Method ... 126
4.3 $QR$ Method for Eigenanalysis ... 129
4.4 Singular Value Decomposition ... 131
Exercises ... 134
5 Software for Numerical Linear Algebra ... 137
5.1 Fortran and C ... 138
- 5.1.1 BLAS ... 140
- 5.1.2 Fortran and C Libraries ... 142
- 5.1.3 Fortran 90 and 95 ... 146
5.2 Interactive Systems for Array Manipulation ... 148
- 5.2.1 Matlab ... 148
- 5.2.2 S, S-Plus ... 151
5.3 High-Performance Software ... 153
5.4 Test Data ... 155
Exercises ... 157
6 Applications in Statistics ... 161
6.1 Fitting Linear Models with Data ... 162
6.2 Linear Models and Least Squares ... 163
- 6.2.1 The Normal Equations and the Sweep Operator ... 165
- 6.2.2 Linear Least Squares Subject to Linear Equality Constraints ... 166
- 6.2.3 Weighted Least Squares ... 166
- 6.2.4 Updating Linear Regression Statistics ... 167
- 6.2.5 Tests of Hypotheses ... 169
- 6.2.6 D-Optimal Designs ... 170
6.3 Ill-Conditioning in Statistical Applications ... 172
6.4 Testing the Rank of a Matrix ... 173
6.5 Stochastic Processes ... 175
Exercises ... 176
Appendix A: Notation and Definitions ... 183
Appendix B: Solutions and Hints for Selected Exercises ... 191
Bibliography ... 197
- Literature in Computational Statistics ... 198
- World Wide Web, News Groups, List Servers, and Bulletin Boards ... 199
- References ... 202
Author Index ... 213
Subject Index ... 217