Introduction to Precise Numerical Methods (eBook)

Front cover 1
Title page 4
Copyright page 5
Table of contents 6
Preface 12
Acknowledgments 14
1 Introduction 16
1.1 Open-source software 16
1.2 Calling up a program 17
1.3 Log files and print files 18
1.4 More on log files 19
1.5 The tilde notation for printed answers 20
2 Computer Arithmetics 24
2.1 Floating-point arithmetic 24
2.2 Variable precision floating-point arithmetic 25
2.3 Interval arithmetic 26
2.4 Range arithmetic 28
2.5 Practical range arithmetic 30
2.6 Interval arithmetic notation 30
2.7 Computing standard functions in range arithmetic 32
2.8 Rational arithmetic 33
Software Exercises A 35
Notes and References 38
3 Classification of Numerical Computation Problems 40
3.1 A knotty problem 40
3.2 The impossibility of untying the knot 42
3.3 Repercussions from nonsolvable problem 3.1 42
3.4 Some solvable and nonsolvable decimal place problems 44
3.5 The solvable problems handled by calc 47
3.6 Another nonsolvable problem 47
3.7 The trouble with discontinuous functions 48
Notes and References 50
4 Real-Valued Functions 52
4.1 Elementary functions 52
Software Exercises B 54
5 Computing Derivatives 56
5.1 Power series of elementary functions 56
5.2 An example of series evaluation 63
5.3 Power series for elementary functions of several variables 64
5.4 A more general method of generating power series 67
5.5 The demo program deriv 69
Software Exercises C 69
Notes and References 69
6 Computing Integrals 72
6.1 Computing a definite integral 72
6.2 Formal interval arithmetic 74
6.3 The demo program integ for computing ordinary definite integrals 76
6.4 Taylor’s remainder formula generalized 78
6.5 The demo program mulint for higher dimensional integrals 79
6.6 The demo program impint for computing improper integrals 81
Software Exercises D 82
Notes and References 83
7 Finding Where a Function f(x) is Zero 84
7.1 Obtaining a solvable problem 84
7.2 Using interval arithmetic for the problem 87
7.3 Newton’s method 88
7.4 Order of convergence 90
Software Exercises E 92
8 Finding Roots of Polynomials 94
8.1 Polynomials 94
8.2 A bound for the roots of a polynomial 100
8.3 The Bairstow method for finding roots of a real polynomial 101
8.4 Bounding the error of a rational polynomial’s root approximations 105
8.5 Finding accurate roots for a rational or a real polynomial 107
8.6 The demo program roots 110
Software Exercises F 110
Notes and References 111
9 Solving n Linear Equations in n Unknowns 112
9.1 Notation 112
9.2 Computation problems 113
9.3 A method for solving linear equations 115
9.4 Computing determinants 117
9.5 Finding the inverse of a square matrix 119
9.6 The demo programs equat, r_equat, and c_equat 120
Software Exercises G 121
Notes and References 122
10 Eigenvalue and Eigenvector Problems 124
10.1 Finding a solution to Ax= 0 when det A= 0 125
10.2 Eigenvalues and eigenvectors 128
10.3 Companion matrices and Vandermonde matrices 133
10.4 Finding eigenvalues and eigenvectors by Danilevsky’s method 137
10.5 Error bounds for Danilevsky’s method 142
10.6 Rational matrices 149
10.7 The demo programs eigen, c_eigen, and r_eigen 150
Software Exercises H 151
11 Problems of Linear Programming 152
11.1 Linear algebra using rational arithmetic 152
11.2 A more efficient method for solving rational linear equations 155
11.3 Introduction to linear programming 156
11.4 Making the simplex process foolproof 160
11.5 Solving n linear interval equations in n unknowns 163
11.6 Solving linear interval equations via linear programming 167
11.7 The program linpro for linear programming problems 170
11.8 The program i_equat for interval linear equations 171
Software Exercises I 171
Notes and References 172
12 Finding Where Several Functions are Zero 174
12.1 The general problem for real elementary functions 174
12.2 Finding a suitable solvable problem 175
12.3 Extending the f(x) solution method to the general problem 178
12.4 The crossing parity 180
12.5 The crossing number and the topological degree 181
12.6 Properties of the crossing number 185
12.7 Computation of the crossing number 186
12.8 Newton’s method for the general problem 190
12.9 Searching a more general region for zeros 191
Software Exercises J 193
Notes and References 195
13 Optimization Problems 196
13.1 Finding a function’s extreme values 196
13.2 Finding where a function’s gradient is zero 199
13.3 The demo program 203
Software Exercises K 203
Notes and References 204
14 Ordinary Differential Equations 206
14.1 Introduction 206
14.2 Two standard problems of ordinary differential equations 208
14.3 Difficulties with the initial value problem 211
14.4 Linear differential equations 212
14.5 Solving the initial value problem by power series 213
14.6 Degree 1 interval arithmetic 216
14.7 An improved global error 220
14.8 Solvable two-point boundary-value problems 223
14.9 Solving the boundary-value problem by power series 225
14.10 The linear boundary-value problem 228
Software Exercises L 229
Notes and References 231
15 Partial Differential Equations 232
15.1 Partial differential equation terminology 232
15.2 ODE and PDE initial value problems 234
15.3 A power series method for the ODE problem 235
15.4 The first PDE solution method 238
15.5 A simple PDE problem as an example 242
15.6 A defect of the first PDE method 243
15.7 The revised PDE method with comparison computation 244
15.8 Higher dimensional spaces 245
15.9 Satisfying boundary conditions 246
Software Exercises M 247
Notes and References 248
16 Numerical Methods with Complex Functions 250
16.1 Elementary complex functions 250
16.2 The demo program c_deriv 252
16.3 Computing line integrals in the complex plane 252
16.4 Computing the roots of a complex polynomial 253
16.5 Finding a zero of an elementary complex function f(z) 254
16.6 The general zero problem for elementary complex functions 257
Software Exercises N 260
Notes and References 262
The Precise Numerical Methods Program PNM 263
Index 264