Mathematics 371 – Numerical Analysis Lab 2/Midterm Problem Set 1 September 28, 2001

Ground Rules

The lab problems below and the additional theoretical questions form the first midterm problem set announced in the course syllabus. This is an open book, open notes, open Swords 335 assignment. You must work independently on these problems, and you may not consult with other faculty members, etc. You may consult other sources in the library, on the Internet, etc. but if you find something relevant there, please footnote it. When you have finished your solutions, please write out a short statement that you have abided by these ground rules, sign it, and return it with your solutions.

This assignment is due no later than 5:00pm on Friday, October 5.

Lab Problems

In class on Friday, September 21 we wrote a rudimentary Maple procedure implementing Newton-Raphson iteration. Last time we also introduced Steffensen’s iteration. There are two files containing Maple source code for these methods available from the course homepage. Download and save them to your directory to start. (Use the same procedure as in the previous lab.) Insert print or lprint statements to display all the terms in the iteration sequences for the Maple output you submit.

A) Use Newton-Raphson to solve 0 = tan(πx)−6 starting from x_{0} = 0.4 until an accuracy of 10^{−7} is obtained. Explain why your sequence of approximations to the root is converging quadratically, and estimate the asymptotic constant K_{2} in the equation

lim_{n→∞} \frac{|x_{n} − p|}{|x_{n−1} − p|^{2}} = K_{2}.

B) If you apply Newton-Raphson to solve

0 = \frac{1}{2} + \frac{1}{4}x^{2} − x sin(x) − \frac{1}{2} cos(2x)

starting from x_{0} = \frac{π}{2} , in theory you should generate a sequence of approximations converging to p ≐ 1.895494267 (exact value to 10 decimal digits). What happens if you use our NewtonRaphson procedure in Maple’s default floating point number system and iterate until an accuracy of 10^{−6} is obtained? Alter the procedure to print out x_{n} and |x_{n} − x_{n−1}| for each n, and explain what is happening here. What happens if you use fewer (say 5) or more (say 20) decimal digits in the floating point computation?

C) Now, solve the same equation as in B using Steffensen’s iteration, and floating point number systems with 5,10,20 digits. Compare the results from Newton-Raphson and Steffensen. What additional lesson about root-finding in floating point arithmetic do you see by considering this equation?

D) Do Problem 30 from Section 2.3 in the text.

Additional Theoretical Problems

E) Suppose that p is a root of f(x) = 0 of multiplicity m ≥ 2. Show that if Newton-Raphson iteration converges to p from some x_{0}, then the convergence is linear, and determine (with proof) the asymptotic constant K_{1} in the equation

lim_{n→∞} \frac{|x_{n} − p|}{|x_{n−1} − p|} = K_{1}.

If you had two equations, one with a root of multiplicity 2, and one of multiplicity 3, and you used Newton-Raphson on both, which sequence of approximations would converge faster? Explain.

F) Suppose that p is a root of f(x) = 0 of multiplicity m. Show that if f′′′ is continuous on some interval containing p, then the iteration

x_{n} = x_{n−1} − \frac{mf(x_{n−1})}{f′(x_{n−1})}

will give a quadratically convergent sequence of approximations to p, starting from x_{0} in a suitable interval. This rate of convergence is as good as that for Steffensen’s iteration. But which method is better, and why?

G) Show that the following iteration method

x_{n} = x_{n−1} − \frac{f(x_{n−1})}{f′(x_{n−1})} − \frac{1}{2} \frac{f′′(x_{n−1})}{f′(x_{n−1})} (\frac{f(x_{n−1})}{f′(x_{n−1})})^{2}

will yield cubic convergence under suitable hypotheses (say what these are). Even though cubic convergence is “super-fast” convergence (much faster even than quadratic convergence), this kind of method is almost never used in practice. Why do you suppose that is the case?