Numerical Methods Course Notes

Version 0.11
(UCSD Math 174, Fall 2004)
Steven E. Pav1
October 13, 2005

1Department of Mathematics, MC0112, University of California at San Diego, La Jolla, CA 92093-0112.
<spav@ucsd.edu> This document is Copyright
c 2004 Steven E. Pav. Permission is granted to copy,
distribute and/or modify this document under the terms of the GNU Free Documentation License, Version
1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, no Front-
Cover Texts, and no Back-Cover Texts. A copy of the license is included in the section entitled "GNU Free
Documentation License".

Contents

Preface i

1 Introduction 1
1.1 Taylor's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Loss of Significance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Vector Spaces, Inner Products, Norms . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Vector Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.2 Inner Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.3.3 Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.4 Eigenvalues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.4.1 Matrix Norms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2 A \Crash" Course in octave/Matlab 13
2.1 Getting Started . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2 Useful Commands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 Programming and Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.3.1 Logical Forks and Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 Plotting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
3 Solving Linear Systems 25
3.1 Gaussian Elimination with Naive Pivoting . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.1 Elementary Row Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.2 Algorithm Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.1.3 Algorithm Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.2 Pivoting Strategies for Gaussian Elimination . . . . . . . . . . . . . . . . . . . . . . 29
3.2.1 Scaled Partial Pivoting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.2 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.3 Another Example and A Real Algorithm . . . . . . . . . . . . . . . . . . . . . 32
3.3 LU Factorization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3.1 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.3.2 Using LU Factorizations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.3 Some Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.4 Computing Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4 Iterative Solutions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.4.1 An Operation Count for Gaussian Elimination . . . . . . . . . . . . . . . . . 37
3.4.2 Dividing by Multiplying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.3 Impossible Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.4 Richardson Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.5 Jacobi Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.6 Gauss Seidel Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.7 Error Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.4.8 A Free Lunch? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
4 Finding Roots 49
4.1 Bisection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.1.1 Modications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.1.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2 Newton's Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.2.1 Implementation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2.2 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.3 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.4 Using Newton's Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3 Secant Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3.1 Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.3.2 Convergence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5 Interpolation 63
5.1 Polynomial Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1.1 Lagranges Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1.2 Newton's Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.1.3 Newton's Nested Form . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.1.4 Divided Di erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2 Errors in Polynomial Interpolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2.1 Interpolation Error Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
5.2.2 Interpolation Error for Equally Spaced Nodes . . . . . . . . . . . . . . . . . . 73
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
6 Spline Interpolation 79
6.1 First and Second Degree Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
6.1.1 First Degree Spline Accuracy . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
6.1.2 Second Degree Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
6.1.3 Computing Second Degree Splines . . . . . . . . . . . . . . . . . . . . . . . . 82
6.2 (Natural) Cubic Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
6.2.1 Why Natural Cubic Splines? . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
6.2.2 Computing Cubic Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
6.3 B Splines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
7 Approximating Derivatives 89
7.1 Finite Di erences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
7.1.1 Approximating the Second Derivative . . . . . . . . . . . . . . . . . . . . . . 91
7.2 Richardson Extrapolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
7.2.1 Abstracting Richardson's Method . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.2.2 Using Richardson Extrapolation . . . . . . . . . . . . . . . . . . . . . . . . . 93
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
8 Integrals and Quadrature 97
8.1 The Defnite Integral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
8.1.1 Upper and Lower Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
8.1.2 Approximating the Integral . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8.1.3 Simple and Composite Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8.2 Trapezoidal Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
8.2.1 How Good is the Composite Trapezoidal Rule? . . . . . . . . . . . . . . . . . 101
8.2.2 Using the Error Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103
8.3 Romberg Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
8.3.1 Recursive Trapezoidal Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
8.4 Gaussian Quadrature . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
8.4.1 Determining Weights (Lagrange Polynomial Method) . . . . . . . . . . . . . . 107
8.4.2 Determining Weights (Method of Undetermined Coecients) . . . . . . . . . 108
8.4.3 Gaussian Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
8.4.4 Determining Gaussian Nodes . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
8.4.5 Reinventing the Wheel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113
9 Least Squares 117
9.1 Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
9.1.1 The De nition of Ordinary Least Squares . . . . . . . . . . . . . . . . . . . . 117
9.1.2 Linear Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
9.1.3 Least Squares from Basis Functions . . . . . . . . . . . . . . . . . . . . . . . 119
9.2 Orthonormal Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121
9.2.1 Alternatives to Normal Equations . . . . . . . . . . . . . . . . . . . . . . . . 122
9.2.2 Ordinary Least Squares in octave/Matlab . . . . . . . . . . . . . . . . . . . . 124
9.3 Orthogonal Least Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
9.3.1 Computing the Orthogonal Least Squares Approximant . . . . . . . . . . . . 128
9.3.2 Principal Component Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 129
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132
10 Ordinary Di erential Equations 135
10.1 Elementary Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
10.1.1 Integration and `Stepping' . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
10.1.2 Taylor's Series Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
10.1.3 Euler's Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
10.1.4 Higher Order Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
10.1.5 Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
10.1.6 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
10.1.7 Backwards Euler's Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
10.2 Runge-Kutta Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143
10.2.1 Taylor's Series Redux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
10.2.2 Deriving the Runge-Kutta Methods . . . . . . . . . . . . . . . . . . . . . . . 144
10.2.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
10.3 Systems of ODEs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
10.3.1 Larger Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
10.3.2 Recasting Single ODE Methods . . . . . . . . . . . . . . . . . . . . . . . . . . 147
10.3.3 It's Only Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
10.3.4 It's Only Autonomous Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 150
Exercises . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154
A Old Exams 157
A.1 First Midterm, Fall 2003 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
A.2 Second Midterm, Fall 2003 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158
A.3 Final Exam, Fall 2003 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
A.4 First Midterm, Fall 2004 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
A.5 Second Midterm, Fall 2004 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162
A.6 Final Exam, Fall 2004 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
B GNU Free Documentation License 167
1. APPLICABILITY AND DEFINITIONS . . . . . . . . . . . . . . . . . . . . . . . . . . 167
2. VERBATIM COPYING . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
3. COPYING IN QUANTITY . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
4. MODIFICATIONS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
5. COMBINING DOCUMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
6. COLLECTIONS OF DOCUMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169
7. AGGREGATION WITH INDEPENDENT WORKS . . . . . . . . . . . . . . . . . . . 169
8. TRANSLATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
9. TERMINATION . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
10. FUTURE REVISIONS OF THIS LICENSE . . . . . . . . . . . . . . . . . . . . . . . 170
ADDENDUM: How to use this License for your documents . . . . . . . . . . . . . . . . . 170
Bibliography                                         171