Numerical Methods Course Notes & Sample Exams

[Admin]

[Sadece Üyeler Görebilir. Üye olmak için tiklayiniz...]


1 Introduction 1
1.1 Taylor's Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Loss of Signicance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Nave 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
iii
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 Modications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Dierences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Dierences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Denite 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 Dierential 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
vi CONTENTS
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

[ferroburak]

şifresi [Sadece Üyeler Görebilir. Üye olmak için tiklayiniz...]

çözünürlüğü biraz daha iyi olsaydı birde