Details zum E-Book

Numerical Methods

Numerical Methods

Piotr Tatjewski

E-book

W podręczniku zaprezentowano podstawowy kurs metod numerycznych dla studentów uczelni technicznych, w szczególności kierunków Automatyka i Robotyka, Informatyka oraz Mechatronika. Przedstawiono zagadnienia dotyczące: reprezentacji liczb i błędów maszynowych, metod numerycznych dla układów równań liniowych i nieliniowych, wartości własnych i szczególnych, aproksymacji i interpolacji, równań różniczkowych zwyczajnych, całkowania i różniczkowania numerycznego.
 
Podręcznik może być wykorzystywany do nauczania metod numerycznych w języku angielskim. Jego polskojęzycznym odpowiednikiem jest książka „Metody numeryczne” wydana przez OWPW w 2013 roku.

Preface 9

Chapter 1. Preliminaries 11

1.1. Computer representation of numbers, representation errors 11

1.2. Floating-pointarithmetic 14

1.3. Condition number 17

1.4. The algorithm and its numerical realization 23

1.5.Numerical stability of algorithms 24

Chapter2. Linear equations, matrix factorizations 29

2.1.Norms of vectors and matrices 29

2.2. Conditioning of a matrix, of a system of linearequations 32

2.3. Gaussian elimination ,LU factorization 33

2.3.1. Upper-triangular systems of linear equations 34

2.3.2. Gaussian elimination 35

2.3.3. LU matrix factorization 37

2.3.4. Gaussian elimination with pivoting 40

2.3.5. Residual correction (iterative improvement) 48

2.3.6. Full elimination method (Gauss-Jordan method) 48

2.4. Cholesky-Banachiewicz (LLT)factorization 49

2.4.1. LLT factorization 49

2.4.2. LDLT factorization, relations between triangular factorizations  51

2.5. Calculation of determinants and inverse matrices 53

2.6. Iterative methodsforsystemsof linearequations 56

2.6.1. Jacobi’smethod 58

2.6.2. Gauss-Seidelmethod 59

2.6.3.Stoptests 60

Chapter 3. QR factorization, eigenvalues, singular values 63

3.1. Orthogonal-triangular (QR) matrix factorizations 63

3.2. Eigenvalues 69

3.2.1. Preliminaries 69

3.2.2. The QR method for finding eigenvalues 73

3.3. Singular values, SVD decomposition 79

3.4. Linear least-squaresproblem 81

3.5. Givens transformation, with applications 85

3.5.1. Givens transformation (rotation) 85

               3.5.2. Jacobi’s method for finding eigenvalues of a symmetric matrix 87                         

3.5.3. The QR matrix factorization using the Givens rotations 89

3.6. Householder transformation, with applications 90

3.6.1. Householder transformation (reflection) 90

3.6.2. The QR matrix factorization using the Householder reflections 92

3.6.3. Transformation of a matrix to the Hessenberg formusing the Householder reflections, preserving matrix similarity 93

Chapter 4. Approximation 97

4.1. Discret eleast-squares approximation 99

4.1.1. Polynomial approximation 102

4.1.2. Approximation using an orthogonal function basis 105

4.2. Pad´e approximation 107

Chapter 5. Interpolation 113

5.1. Algebraic polynomial interpolation 114

5.1.1. Lagrange interpolating polynomial 115

5.1.2. Newton’s interpolating polynomial 116

5.2. Spline function interpolation 123

Chapter 6. Nonlinear equations and roots of polynomials 135

6.1. Solvinga nonlinear equation 135

6.1.1. Bisection method 136

6.1.2. Regula falsi method 137

6.1.3. Secant method 139

6.1.4. Newton’s method 140

6.1.5. An example realization of an effective algorithm 142

6.2. Systems of nonlinear equations 143

6.2.1. Newton’s method 145

6.2.2. Broyden’s method 146

6.2.3. Fixpoint method 147

6.3. Roots of polynomials 148

6.3.1. Muller’s method 148

6.3.2. Laguerre’s method 150

6.3.3. Deflation by a linear term 151

6.3.4. Root polishing 152

6.3.5. Bairstow’s algorithm 152

Chapter 7. Ordinary differential equations 157

7.1. Single-step methods 163

7.1.1. Runge-Kutta(RK) methods 165

7.1.2. Runge-Kutta-Fehlberg(RKF) methods 170

7.1.3. Correction of the step-size 172

7.2. Multistep methods 175

7.2.1. Adams methods 175

7.2.2. The approximation error 177

7.2.3. Stability and convergence 180

7.2.4. Predictor-corrector methods 183

7.2.5. Predictor-corrector methods with a variablestep-size 186

7.3. Stiff systems of differential equations 192

Chapter 8. Numerical differentiation and integration 199

8.1. Numerical approximation of derivatives 199

8.2.Numerical integration 206

Bibliography 217