Numerical Analysis Notes for Math 575A - University of Arizona

Numerical Analysis Notes for Math 575A

William G. Faris Program in Applied Mathematics

University of Arizona

Fall 1992

Contents

1 Nonlinear equations

5

1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Bisection . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.3.1 First order convergence . . . . . . . . . . . . . . . . 9

1.3.2 Second order convergence . . . . . . . . . . . . . . . 11

1.4 Some C notations . . . . . . . . . . . . . . . . . . . . . . . . 12

1.4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 12

1.4.2 Types . . . . . . . . . . . . . . . . . . . . . . . . . . 13

1.4.3 Declarations . . . . . . . . . . . . . . . . . . . . . . . 14

1.4.4 Expressions . . . . . . . . . . . . . . . . . . . . . . . 14

1.4.5 Statements . . . . . . . . . . . . . . . . . . . . . . . 16

1.4.6 Function definitions . . . . . . . . . . . . . . . . . . 17

2 Linear Systems

19

2.1 Shears . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.2 Reflections . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3 Vectors and matrices in C . . . . . . . . . . . . . . . . . . . 27

2.3.1 Pointers in C . . . . . . . . . . . . . . . . . . . . . . 27

2.3.2 Pointer Expressions . . . . . . . . . . . . . . . . . . 28

3 Eigenvalues

31

3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.2 Similarity . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

3.3 Orthogonal similarity . . . . . . . . . . . . . . . . . . . . . . 34

3.3.1 Symmetric matrices . . . . . . . . . . . . . . . . . . 34

3.3.2 Singular values . . . . . . . . . . . . . . . . . . . . . 34

3.3.3 The Schur decomposition . . . . . . . . . . . . . . . 35

3.4 Vector and matrix norms . . . . . . . . . . . . . . . . . . . 37

3.4.1 Vector norms . . . . . . . . . . . . . . . . . . . . . . 37

1

2

CONTENTS

3.4.2 Associated matrix norms . . . . . . . . . . . . . . . 37 3.4.3 Singular value norms . . . . . . . . . . . . . . . . . . 38 3.4.4 Eigenvalues and norms . . . . . . . . . . . . . . . . . 39 3.4.5 Condition number . . . . . . . . . . . . . . . . . . . 39 3.5 Stability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.5.1 Inverses . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.5.2 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . 40 3.5.3 Eigenvalue location . . . . . . . . . . . . . . . . . . . 41 3.6 Power method . . . . . . . . . . . . . . . . . . . . . . . . . . 43 3.7 Inverse power method . . . . . . . . . . . . . . . . . . . . . 44 3.8 Power method for subspaces . . . . . . . . . . . . . . . . . . 44 3.9 QR method . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 3.10 Finding eigenvalues . . . . . . . . . . . . . . . . . . . . . . . 47

4 Nonlinear systems

49

4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 49

4.2 Degree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.2.1 Brouwer fixed point theorem . . . . . . . . . . . . . 52

4.3 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3.1 First order convergence . . . . . . . . . . . . . . . . 52

4.3.2 Second order convergence . . . . . . . . . . . . . . . 54

4.4 Power series . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.5 The spectral radius . . . . . . . . . . . . . . . . . . . . . . . 56

4.6 Linear algebra review . . . . . . . . . . . . . . . . . . . . . 57

4.7 Error analysis . . . . . . . . . . . . . . . . . . . . . . . . . . 59

4.7.1 Approximation error and roundoff error . . . . . . . 59

4.7.2 Amplification of absolute error . . . . . . . . . . . . 59

4.7.3 Amplification of relative error . . . . . . . . . . . . . 61

4.8 Numerical differentiation . . . . . . . . . . . . . . . . . . . . 63

5 Ordinary Differential Equations

65

5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5.2 Numerical methods for scalar equations . . . . . . . . . . . 65

5.3 Theory of scalar equations . . . . . . . . . . . . . . . . . . . 67

5.3.1 Linear equations . . . . . . . . . . . . . . . . . . . . 67

5.3.2 Autonomous equations . . . . . . . . . . . . . . . . . 67

5.3.3 Existence . . . . . . . . . . . . . . . . . . . . . . . . 68

5.3.4 Uniqueness . . . . . . . . . . . . . . . . . . . . . . . 69

5.3.5 Forced oscillations . . . . . . . . . . . . . . . . . . . 70

5.4 Theory of numerical methods . . . . . . . . . . . . . . . . . 71

5.4.1 Fixed time, small step size . . . . . . . . . . . . . . . 71

5.4.2 Fixed step size, long time . . . . . . . . . . . . . . . 73

CONTENTS

3

5.5 Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5.5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . 77 5.5.2 Linear constant coefficient equations . . . . . . . . . 77 5.5.3 Stiff systems . . . . . . . . . . . . . . . . . . . . . . 81 5.5.4 Autonomous Systems . . . . . . . . . . . . . . . . . 82 5.5.5 Limit cycles . . . . . . . . . . . . . . . . . . . . . . . 84

6 Fourier transforms

87

6.1 Groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

6.2 Integers mod N . . . . . . . . . . . . . . . . . . . . . . . . . 87

6.3 The circle . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

6.4 The integers . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

6.5 The reals . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

6.6 Translation Invariant Operators . . . . . . . . . . . . . . . . 90

6.7 Subgroups . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92

6.8 The sampling theorem . . . . . . . . . . . . . . . . . . . . . 94

6.9 FFT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

?

4

CONTENTS

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download