Mathematics 171–Numerical Analysis I Review Sheet–Midterm 1

General Information

The first midterm will be given in class Thursday, October 8. This will be a 75 minute in-class exam. You may (and certainly should) use a hand calculator.

Topics to be Covered

The exam will cover the material from the beginning of the semester through class on Thursday, October 1. This includes:

1. Floating point numbers, floating point arithmetic, and some of their effects in numerical calculations.

2. Maple’s floating point number systems and elementary Maple commands for numerical computation.

3. The bisection, Newton-Raphson iteration, and fixed point iteration methods to solve f(x) = 0. Be prepared to apply 3 or 4 iteration steps of bisection, fixed-point iteration or Newton’s Method on a “reasonable” example, by hand.

4. Criterion for convergence of fixed-point iteration. Linear and quadratic convergence.

Proofs to Know

The following are somewhat loose statements of the major theoretical points in the material we have studied. You should review and know exact statements and proofs of these results.

1. If L is a fixed point of g satisfying |g′(L)| < 1 then iteration x_{n} = g(x_{n−1}) will converge to L starting from any x_{0} in a suitable interval I containing L.

2. Newton’s Method converges quadratically to a simple root of f(x) = 0, starting from x_{0} sufficiently close to the root.

Review Problems

From Burden and Faires, questions like p. 26/4,5,25, p. 53/3 (how many steps could each of these take, in theory?), 11, 12, p. 63/1,2, p. 75/6.

1.

a. Find a rearrangement x = g(x) of the equation x^{3} − 9x^{2} + 18x − 6 = 0 for which fixed point iteration will converge to a root near x = 2. (Just show that your rearrangement will “work.”) Will this iteration give a linearly or a quadratically convergent sequence of approximations to the root?

b. Perform three iteration steps.

2. As methods for computing approximate values of \sqrt{A}, the two iterations:

x_{n} = g_{1}(x_{n−1}) = \frac{1}{2}x_{n−1} + \frac{A}{2x_{n−1}}

and

x_{n} = g_{2}(x_{n−1}) = \frac{2}{3}x_{n−1} + \frac{A}{3x_{n−1}}

are proposed.

a) Give Maple commands that could be used to compute the 10th term in each of these sequences with A = 7.0, starting from x_{0} = 2.0.

b) Show that both methods will yield sequences converging to \sqrt{A} (at least if x_{0} is chosen suitably).

c) Which iteration would tend to converge faster to \sqrt{A}. Why?

3. The series

∑_{n=2}^{∞} \frac{1}{n ln n}

is divergent. (The partial sums exceed every positive real number if enough terms are included.)

a) Give a Maple input command or commands that could be used to compute the partial sum

∑_{n=2}^{20} \frac{1}{n ln n}

(Hint: use a variable psum to represent the running total as you add in terms one at a time.)

b) (A “thought” question.) Suppose you write a computer program to compute the partial sum

∑_{n=2}^{k} \frac{1}{n ln n}

using the floating point arithmetic in a 10-decimal digit floating point number system, with exponents e, −128 ≤ e ≤ 127, using k as an input parameter. If you call it supplying huge values for k, say k = 10^{120}, … 10^{125}, 10^{126}, 10^{127}, …, discuss how the results would compare with what you would expect mathematically.

4. (Another “thought” question.) The function f(x) = sin(1/x) − x has infinitely many different roots in the interval (0, 1]. Can any root-finding method, implemented in a given floating point number system, find all of these these roots? (By this, I mean could you solve every one of the problems of the form: find the root closest to 1, 2nd closest to 1, ... , nth closest to 1, ... .) Why or why not?