Computational Statistics by James E. Gentle

Numerical Linear Algebra for Applications in Statistics

by James E. Gentle

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