Contents
Preface to the Second Edition
0.1 References . . . . . . . . . . . . . . . . . . . . . . . . . . . .
0.2 References . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1 Recurrence Relations 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Binomial Coefficients . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Number of Partitions of a Set . . . . . . . . . . . . . . . . . 1
1.4 Horner’s Method . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5 Sample Means and Variances . . . . . . . . . . . . . . . . . 3
1.6 Expected Family Size . . . . . . . . . . . . . . . . . . . . . 4
1.7 Poisson-Binomial Distribution . . . . . . . . . . . . . . . . . 4
1.8 A Multinomial Test Statistic . . . . . . . . . . . . . . . . . 5
1.9 An Unstable Recurrence . . . . . . . . . . . . . . . . . . . . 6
1.10 Quick Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.11 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.12 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2 Power Series Expansions 13
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Expansion of P(s)n . . . . . . . . . . . . . . . . . . . . . . . 13
2.2.1 Application to Moments . . . . . . . . . . . . . . . . 14
2.3 Expansion of eP(s) . . . . . . . . . . . . . . . . . . . . . . . 14
2.3.1 Moments to Cumulants and Vice Versa . . . . . . . 15
2.3.2 Compound Poisson Distributions . . . . . . . . . . . 15
2.3.3 Evaluation of Hermite Polynomials . . . . . . . . . . 15
2.4 Standard Normal Distribution Function . . . . . . . . . . . 16
2.5 Incomplete Gamma Function . . . . . . . . . . . . . . . . . 17
2.6 Incomplete Beta Function . . . . . . . . . . . . . . . . . . . 18
2.7 Connections to Other Distributions . . . . . . . . . . . . . . 19
2.7.1 Chi-square and Standard Normal . . . . . . . . . . . 19
2.7.2 Poisson . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.7.3 Binomial and Negative Binomial . . . . . . . . . . . 19
2.7.4 F and Student’s t . . . . . . . . . . . . . . . . . . . . 20
2.7.5 Monotonic Transformations . . . . . . . . . . . . . . 21
2.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3 Continued Fraction Expansions 27
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2 Wallis’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . 28
3.3 Equivalence Transformations . . . . . . . . . . . . . . . . . 29
3.4 Gauss’s Expansion of Hypergeometric Functions . . . . . . 30
3.5 Expansion of the Incomplete Gamma Function . . . . . . . 33
3.6 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.7 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
4 Asymptotic Expansions 39
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.2 Order Relations . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.3 Finite Taylor Expansions . . . . . . . . . . . . . . . . . . . 41
4.4 Expansions via Integration by Parts . . . . . . . . . . . . . 43
4.4.1 Exponential Integral . . . . . . . . . . . . . . . . . . 44
4.4.2 Incomplete Gamma Function . . . . . . . . . . . . . 45
4.4.3 Laplace Transforms . . . . . . . . . . . . . . . . . . 45
4.5 General Definition of an Asymptotic Expansion . . . . . . . 46
4.6 Laplace’s Method . . . . . . . . . . . . . . . . . . . . . . . . 46
4.6.1 Moments of an Order Statistic . . . . . . . . . . . . 47
4.6.2 Stirling’s Formula . . . . . . . . . . . . . . . . . . . 49
4.6.3 Posterior Expectations . . . . . . . . . . . . . . . . . 49
4.7 Validation of Laplace’s Method . . . . . . . . . . . . . . . . 50
4.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
4.9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
5 Solution of Nonlinear Equations 55
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2 Bisection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
5.2.1 Computation of Quantiles by Bisection . . . . . . . . 56
5.2.2 Shortest Confidence Interval . . . . . . . . . . . . . . 56
5.3 Functional Iteration . . . . . . . . . . . . . . . . . . . . . . 58
5.3.1 Fractional Linear Transformations . . . . . . . . . . 60
5.3.2 Extinction Probabilities by Functional Iteration . . . 62
5.4 Newton’s Method . . . . . . . . . . . . . . . . . . . . . . . 63
5.4.1 Division without Dividing . . . . . . . . . . . . . . 65
5.4.2 Extinction Probabilities by Newton’s Method . . . . 65
5.5 Golden Section Search . . . . . . . . . . . . . . . . . . . . . 67
5.6 Minimization by Cubic Interpolation . . . . . . . . . . . . 68
5.7 Stopping Criteria . . . . . . . . . . . . . . . . . . . . . . . . 70
5.8 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.9 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
xiv Contents
6 Vector and Matrix Norms 77
6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
6.2 Elementary Properties of Vector Norms . . . . . . . . . . . 77
6.3 Elementary Properties of Matrix Norms . . . . . . . . . . . 78
6.4 Norm Preserving Linear Transformations . . . . . . . . . . 82
6.5 Iterative Solution of Linear Equations . . . . . . . . . . . . 84
6.5.1 Jacobi’s Method . . . . . . . . . . . . . . . . . . . . 85
6.5.2 Landweber’s Iteration Scheme . . . . . . . . . . . . . 85
6.5.3 Equilibrium Distribution of a Markov Chain . . . . 85
6.6 Condition Number of a Matrix . . . . . . . . . . . . . . . . 86
6.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
6.8 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7 Linear Regression and Matrix Inversion 93
7.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
7.2 Motivation from Linear Regression . . . . . . . . . . . . . . 94
7.3 Motivation from Multivariate Analysis . . . . . . . . . . . 95
7.4 Definition of the Sweep Operator . . . . . . . . . . . . . . . 95
7.5 Properties of the Sweep Operator . . . . . . . . . . . . . . . 96
7.6 Applications of Sweeping . . . . . . . . . . . . . . . . . . . 99
7.7 Cholesky Decompositions . . . . . . . . . . . . . . . . . . . 99
7.8 Gram-Schmidt Orthogonalization . . . . . . . . . . . . . . . 101
7.9 Orthogonalization by Householder Reflections . . . . . . . . 103
7.10 Comparison of the Different Algorithms . . . . . . . . . . . 105
7.11 Woodbury’s Formula . . . . . . . . . . . . . . . . . . . . . . 105
7.12 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
7.13 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
8 Eigenvalues and Eigenvectors 113
8.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
8.2 Jacobi’s Method . . . . . . . . . . . . . . . . . . . . . . . . 113
8.3 The Rayleigh Quotient . . . . . . . . . . . . . . . . . . . . 118
8.4 Finding a Single Eigenvalue . . . . . . . . . . . . . . . . . . 120
8.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
8.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
9 Singular Value Decomposition 129
9.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
9.2 Basic Properties of the SVD . . . . . . . . . . . . . . . . . 130
9.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
9.3.1 Reduced Rank Regression . . . . . . . . . . . . . . . 133
9.3.2 Ridge Regression . . . . . . . . . . . . . . . . . . . . 134
9.3.3 Polar Decomposition . . . . . . . . . . . . . . . . . . 134
9.3.4 Image Compression . . . . . . . . . . . . . . . . . . . 135
9.3.5 Principal Components . . . . . . . . . . . . . . . . . 135
Contents xv
9.3.6 Total Least Squares . . . . . . . . . . . . . . . . . . 136
9.4 Jacobi’s Algorithm for the SVD . . . . . . . . . . . . . . . . 137
9.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
9.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
10 Splines 143
10.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
10.2 Definition and Basic Properties . . . . . . . . . . . . . . . . 143
10.3 Applications to Differentiation and Integration . . . . . . . 148
10.4 Application to Nonparametric Regression . . . . . . . . . . 149
10.5 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
10.6 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
11 Optimization Theory 157
11.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
11.2 Unconstrained Optimization . . . . . . . . . . . . . . . . . 158
11.3 Optimization with Equality Constraints . . . . . . . . . . . 162
11.4 Optimization with Inequality Constraints . . . . . . . . . . 169
11.5 Convexity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
11.6 Block Relaxation . . . . . . . . . . . . . . . . . . . . . . . . 174
11.7 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181
11.8 References . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187