Preface to the Solutions Manual for the Third Edition ix
1 Introductory Concepts and Calculus Review 1
1.1 Basic Tools of Calculus 1
1.2 Error, Approximate Equality, and Asymptotic Order Notation 10
1.3 A Primer on Computer Arithmetic 13
1.4 A Word on Computer Languages and Software 17
1.5 A Brief History of Scientific Computing 18
2 A Survey of Simple Methods and Tools 19
2.1 Horner's Rule and Nested Multiplication 19
2.2 Difference Approximations to the Derivative 22
2.3 Application: Euler's Method for Initial Value Problems 30
2.4 Linear Interpolation 34
2.5 Application - The Trapezoid Rule 38
2.6 Solution of Tridiagonal Linear Systems 46
2.7 Application: Simple Two-Point Boundary Value Problems 50
3 Root-Finding 55
3.1 The Bisection Method 55
3.2 Newton's Method: Derivation and Examples 59
3.3 How to Stop Newton's Method 63
3.4 Application: Division Using Newton's Method 66
3.5 The Newton Error Formula 69
3.6 Newton's Method: Theory and Convergence 72
3.7 Application: Computation of the Square Root 76
3.8 The Secant Method: Derivation and Examples 79
3.9 Fixed Point Iteration 83
3.10 Roots of Polynomials (Part 1) 85
3.11 Special Topics in Root-finding Methods 88
3.12 Very High-order Methods and the Efficiency Index 98
4 Interpolation and Approximation 101
4.1 Lagrange Interpolation 101
4.2 Newton Interpolation and Divided Differences 104
4.3 Interpolation Error 114
4.4 Application: Muller's Method and Inverse Quadratic Interpolation 119
4.5 Application: More Approximations to the Derivative 121
4.6 Hermite Interpolation 122
4.7 Piecewise Polynomial Interpolation 125
4.8 An Introduction to Splines 129
4.9 Tension Splines 135
4.10 Least Squares Concepts in Approximation 137
4.11 Advanced Topics in Interpolation Error 142
5 Numerical Integration 149
5.1 A Review of the Definite Integral 149
5.2 Improving the Trapezoid Rule 151
5.3 Simpson's Rule and Degree of Precision 154
5.4 The Midpoint Rule 162
5.5 Application: Stirling's Formula 166
5.6 Gaussian Quadrature 167
5.7 Extrapolation Methods 173
5.8 Special Topics in Numerical Integration 177
6 Numerical Methods for Ordinary Differential Equations 185
6.1 The Initial Value Problem-Background 185
6.2 Euler's Method 187
6.3 Analysis of Euler's Method 189
6.4 Variants of Euler's Method 190
6.5 Single Step Methods-Runge-Kutta 197
6.6 Multistep Methods 200
6.7 Stability Issues 204
6.8 Application to Systems of Equations 206
6.9 Adaptive Solvers 210
6.10 Boundary Value Problems 212
7 Numerical Methods for the Solution of Systems of Equations 217
7.1 Linear Algebra Review 217
7.2 Linear Systems and Gaussian Elimination 218
7.3 Operation Counts 223
7.4 The LU Factorization 224
7.5 Perturbation, Conditioning and Stability 229
7.6 SPD Matrices and the Cholesky Decomposition 235
7.7 Application: Numerical Solution of Linear Least Squares Problems 236
7.8 Sparse and Structured Matrices 240
7.9 Iterative Methods for Linear Systems - A Brief Survey 241
7.10 Nonlinear Systems: Newton's Method and Related Ideas 242
7.11 Application: Numerical Solution of Nonlinear BVP's 244
8 Approximate Solution of the Algebraic Eigenvalue Problem 247
8.1 Eigenvalue Review 247
8.2 Reduction to Hessenberg Form 249
8.3 Power Methods 250
8.4 Bisection and Inertia to Compute Eigenvalues of Symmetric Matrices 253
8.5 An Overview of the QR Iteration 257
8.6 Application: Roots of Polynomials, II 260
8.7 Application: Computation of Gaussian Quadrature Rules 261
9 A Survey of Numerical Methods for Partial Differential Equations 265
9.1 Difference Methods for the Diffusion Equation 265
9.2 Finite Element Methods for the Diffusion Equation 270
9.3 Difference Methods for Poisson Equations 271
10 An Introduction to Spectral Methods 277
10.1 Spectral Methods for Two-Point Boundary Value Problems 277
10.2 Spectral Methods in Two Dimensions 279
10.3 Spectral Methods for Time-Dependent Problems 282
10.4 Clenshaw-Curtis Quadrature 283
CHAPTER 1
INTRODUCTORY CONCEPTS AND CALCULUS REVIEW
1.1 BASIC TOOLS OF CALCULUS
- 2. What is the third-order Taylor polynomial for , about ?
Solution: We have and
so that , , . Therefore
- 3. What is the sixth-order Taylor polynomial for , using ? Hint: Consider the previous problem.
- 4. Given that
for , where is between and 0, find an upper bound for , valid for all , that is independent of and .
- 5. Repeat the above, but this time require that the upper bound be valid only for all .
Solution: The only significant difference is the introduction of a factor of in the denominator:
- 6. Given that
for , where is between and 0, find an upper bound for , valid for all , that is independent of and .
- 7. Use a Taylor polynomial to find an approximate value for that is accurate to within .
Solution: There are two ways to do this. We can approximate and use , or we can approximate and use . In addition, we can be conventional and take , or we can take in order to speed convergence.
The most straightforward approach (in my opinion) is to use a Taylor polynomial for about . The remainder after terms is
We quickly have that
and a little playing with a calculator shows that
but
So we would use
To fourteen digits, , and the error is , much smaller than required.
- 8. What is the fourth-order Taylor polynomial for , about ?
Solution: We have and
so that , , . Thus,
- 9. What is the fourth-order Taylor polynomial for , about ?
- 10. Find the Taylor polynomial of third-order for , using:
- .
Solution: We have so
- ;
- .
- 11. For each function below construct the third-order Taylor polynomial approximation, using , and then estimate the error by computing an upper bound on the remainder, over the given interval.
- , ;
- , ;
- , ;
- , ;
- , .
Solution:
- The polynomial is with remainder This can be bounded above, for all , by
- The polynomial is with remainder We can't bound this for all , because of the potential division by zero.
- The polynomial is with remainder This can be bounded above, for all , by
- The polynomial is the same as in (b), of course, with remainder For all this can be bounded by
- The polynomial is with remainder This can be bounded above, for all , by Obviously, this is not an especially good approximation.
- 12. Construct a Taylor polynomial approximation that is accurate to within , over the indicated interval, for each of the following functions, using .
- , ;
- , ;
- , ;
- , ;
- , .
Solution:
- The remainder here is for . Therefore, we have Simple manipulations with a calculator then show that but Therefore the desired Taylor polynomial is
- The remainder here is for . Therefore, we have Simple manipulations with a calculator then show that but Therefore the desired Taylor polynomial is
- , .
- Solution: The remainder is now and makes the error small enough.
- , .
- 13. Repeat the above, this time with a desired accuracy of .
- 14. Since
we can estimate by estimating . How many terms are needed in the Gregory series for the arctangent to approximate to 100 decimal places? 1,000? Hint: Use the error term in the Gregory series to predict when the error gets sufficiently small.
Solution: The remainder in the Gregory series approximation is
so to get 100 decimal places of accuracy for , we require
thus, we have to take terms. For 1,000 places of accuracy we therefore need terms.
Obviously, this is not the best procedure for computing many digits of !
- 15. Elementary trigonometry can be used to show that
This formula was developed in 1706 by the English astronomer John Machin. Use this to develop a more efficient algorithm for computing . How many terms are needed to get 100 digits of accuracy with this form? How many terms are needed to get 1,000 digits? Historical note: Until 1961, this was the basis for the most commonly used method for computing to high accuracy.
Solution: We now have two Gregory series, thus complicating the problem a bit. We have
Define as the approximation generated by using an term Gregory series to approximate and an term Gregory series for . Then we have
where is the remainder in the Gregory series. Therefore,
To finish the problem we have to apportion the error between the two series, which introduces some arbitrariness into the problem. If we require that they be equally accurate, then we have that
and
Using properties of logarithms, these become
and
For , these are satisfied for , . For , we get , . Changing the apportionment of the error doesn't change the results by much at all.
- 16. In 1896, a variation on Machin's formula was found:
and this began to be used in 1961 to compute to high accuracy. How many terms are needed when using this expansion to get 100 digits of ? 1,000 digits?
Solution: We now have three series to work with, which complicates matters only slightly more compared to the previous problem. If we define based on
taking terms in the series for , terms in the series for , and terms in the series for , then we are led to the inequalities
and
For , we get , , and ; for we get , , and .
Note: In both of these problems a slightly more involved treatment of the error might lead to fewer terms being required.
- 17. What is the Taylor polynomial of order 3 for , using ?
Solution: This is very direct:
so that
- 18. What is the Taylor polynomial of order 4 for , using ? Simplify as much as possible.
- 19. What is the Taylor polynomial of order 2 for , using ?
- 20. What is the Taylor polynomial of order 3 for , using ? Simplify as much as possible.
Solution: We note that , so we have (using the solution from the previous problem)
The polynomial is its own Taylor polynomial.
- 21. Let be an arbitrary polynomial of degree less than or equal to . What is its Taylor polynomial of degree , about an arbitrary ?
- 22. The Fresnel integrals are defined as
and
Use Taylor expansions to find approximations to and that are accurate for all with . Hint: Substitute into the Taylor expansions for the cosine and sine.
Solution:
We will show the work for the case of , only. We have
Looking more carefully at the remainder term, we see that it is given by
Therefore,
A little effort with a calculator shows that this is less than for ; therefore the polynomial is
- 23. Use the Integral Mean Value Theorem to show that the "pointwise" form (1.3) of the Taylor remainder (usually called the Lagrange form) follows from the "integral" form (1.2) (usually called the Cauchy form).
- 24. For each function in Problem 11, use the Mean Value Theorem to find a value such that
is valid for all , in the interval used in Problem 11.
Solution: This amounts to finding an upper bound on over the interval given. The answers are as given below.
- , ; .
- , ; is unbounded, since and is possible.
- , ; .
- , ; .
- , . .
- 25. A function is called monotone on an interval if its derivative is strictly positive or strictly negative on the interval. Suppose is continuous and monotone on the interval , and ; prove that there is exactly one value such that = 0.
Solution: Since is continuous on the interval and , the Intermediate Value Theorem guarantees that there is a point where , i.e., there is at least one root. Suppose now that there exists a second root, . Then . By the Mean Value Theorem, then, there is a point between and such that
But this violates the hypothesis that is monotone, since a monotone function must have a derivative that is strictly positive or strictly negative. Thus we have a contradiction, thus there cannot exist the second root.
A very acceptable argument can be made by appealing to a graph of the function.
- 26. Finish the proof of the Integral Mean Value Theorem (Theorem 1.5) by writing up the argument in the case that is negative.
Solution: All that is required is...