Elementary Numerical Methods

COMP 361/5611 – Elementary Numerical Methods Assignment 3 – Due Sunday, October 12, 2014

Problem 1. (20%) Show how to use Newton’s method to compute the cube root of 5. Numerically carry out the first 10 iterations of Newton’s method, using x(0) = 1 . Analytically determine the fixed points of the Newton iteration and determine whether they are attracting or repelling. If a fixed point is attracting then determine analytically if the convergence is linear or quadratic. Draw the “x(k+1) versus x(k)

diagram”, again taking x(0) = 1, and draw enough iterations in the diagram, so that the long time behavior is clearly visible. For which values of x(0) will Newton’s method converge?

Problem 2. (20%) Also use the Chord method to compute the cube root of 5. Numerically carry out the first 10 iterations of the Chord method, using x(0) = 1 . Analytically determine the fixed points of the Chord iteration and determine whether they are attracting or repelling. If a fixed point is attracting then determine analytically if the convergence is linear or quadratic. If the convergence is linear then determine analytically the rate of convergence. Draw the “x(k+1) versus x(k)

diagram”, as in the Lecture Notes, again taking x(0) = 1, and draw enough iterations in the diagram, so that the long time behavior is clearly visible. (If done by hand then make sure that your diagram is sufficiently accurate, for otherwise the graphical results may be misleading.)

Do the same computations and analysis for the Chord Method when x(0) = 0.1.

More generally, analytically determine all values of x(0) for which the Chord method will converge to the cube root of 5.

Problem 3. (20%) Consider the discrete logistic equation, discussed in the Lecture Notes, and given by

x(k+1) = cx(k)(1− x(k)), k = 0, 1, 2, 3, · · · .

For each of the following values of c, determine analytically the fixed points and whether they are attracting or repelling: c = 0.70, c = 1.00, c = 1.80, c = 2.00, c = 3.30, c = 3.50, c = 3.97. (You need only consider “physically meaningful” fixed points, namely those that lie in the interval [0, 1].) If a fixed point is attracting then determine analytically if the convergence is linear or quadratic. If the convergence is linear then analytically determine the rate of convergence. For each case include a statement that describes the behavior of the iterations, as also shown in the Lecture Notes.

1

Problem 4. (20%) Consider the example of solving a system of nonlinear equations by Newton’s method, as given on Pages 95-97 of the Lecture notes. Write a program to carry out this iteration, using Gauss elimination to solve the 2 by 2 linear systems that arise. Use each of the following 16 initial data sets for the Newton iteration:

(x (0) 1 , x

(0) 2 ) = (i, j) , i = 0, 1, 2, 3 , j = 0, 1, 2, 3 .

Present and discuss your numerical results in a concise manner.

Problem 5. (20%) The multiplicity of the zero x∗ is the least integer m such that f (k)(x∗) = 0 for 0 ≤ k < m, but f (m)(x∗) 6= 0. Show analytically that in the case of a zero of multiplicity m, the modified Newton’s method

xn+1 = xn −m f(xn)

f ′(xn)

is quadratically convergent.