Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

MATH256 Group Project

1. This question is concerned with solutions of the equation C(z) = 0, where

C(z) = z3 +pz + q,

for real parameters p and q. The discriminant of C is given by

∆ = q2  + p3 .

There are three real roots if ∆ ≤ 0 (including repeated roots if ∆ = 0). Otherwise there is one  real root and a complex conjugate pair. In your analysis, you can assume that p  0 and q  0. When taking a complex cube root, keep in mind that there are three possible values (unless z = 0). Thus, if z = reiθ  with r > 0 and −π < θ ≤ π, then

z1/3  = ei(2kπ+θ)/3,    k = 0, 1, 2.

You need not prove that taking the cube root of a complex number is a safe operation, and you can assume that ∆ itself is safely calculated.

(a) Verify that the three roots of C are given by

zj  = S+ + S−     where   S± =  −  ± ∆1/2  1/3 ,                             (∗)

provided the cube roots are taken in such a way that S+S− = −p/3. (Note that the square roots can be taken in the ‘obvious’ way, because using the alternative values just interchanges S+  and S− .)

Avoid messy algebra: you may find that it helps to calculate S + S and S+S−  first.

(b)  Explain how both S+  and S−  can always be safely calculated (i.e. without any danger of

catastrophic cancellation).

(c) Show that if ∆ ≤ 0 then S− = S+  (the complex conjugate).  Hence explain how all three roots can be safely calculated in this case.

(d) Show that if p < 0 but ∆ ≥ 0 then the real root can be safely calculated.  The complex roots can then be calculated through their relationships to the coefficients of C. Can this be achieved without any danger of catastrophic cancellation? Why (or why not)?

(e) Show that the imaginary parts of the complex roots can always be safely calculated if p > 0. Can the other information about the roots (the real root and the real part of the complex  roots) be safely obtained in this case? Why (or why not)?

Hint: find and simplify an expression for the product of the complex roots.


2.  Let f(x) be a quartic polynomial with distinct, real roots α1, . . . , α4 .

 

S(x) =  =  +  +  +  , and find a similar expression for T(x) =  −   .

(b)  Let x0  and λ be real numbers such that x0   αj  for j = 1, 2, 3, 4 and λ  x0 , and consider

Q(x) = K(x − x0)2 − (x − λ)2 ,

(α1 − λ)2          (α2 − λ)2          (α3 − λ)2          (α4 − λ)2

 

(i) What can be said about roots of Q(x) between x0  and αj?

(ii)  By writing αj  − λ = (αj  − x0) + (x0 − λ), prove that

K = 4 − 2(x0 − λ)S0 + (x0 − λ)2T0 ,

where S0  = S(x0) and T0  = T(x0).

(c)   (i)  Make the change of variables y = x − x0  and µ = x0 − λ to obtain an expression for  Q(y, µ) as a quadratic in µ. It turns out that the optimal choice for µ — which moves the  roots of Q as close as possible to the roots of f — occurs at the point where ∂Q/∂µ = 0.

Denote this value by µ0 ; find its value, and then show that Q(y, µ0) = 0 if y2 h3T0 − Si − 2S0y − 4 = 0.

In your answer, you may assume that T0y2   1.

(ii)  Is it possible to have T0y2  = 1 and ∂Q/∂µ = 0 at the root? Why (or why not)?

(d)  By solving the quadratic from part (c) and writing f0  = f(x0), f = f′(x0) etc. show that

x1  = ϕ(x0) = x0 −              4f0                        

f ± h9 12f0fi1/2.

Hint: move the square root into the denominator before eliminating S0  and T0 .

(e)   (i) Write a Maple procedure which takes as its arguments a function f , an initial estimate for a root x0 , a number of steps n and a boolean called display. The procedure should use the function ϕ from part (d) to produce a sequence of iterates x1, x2, . . . , xn, such that xj+1  = ϕ(xj).  In each step, the sign that gives the denominator the larger magnitude should be chosen. The procedure should return xn  as its result. If display is true, the procedure should display |f(x)| at each step using scientific notation (use %10.3e with printf). If display is false, no information should be displayed while the procedure is running.

(ii) Test your procedure for the case

f(x) = 4x4 − 8x3 − 77x2 + 270x − 225,

with the initial estimate x0  = 1.0.  Perform a further test using an arbitrarily chosen function (but not a polynomial). Estimate the rate of convergence in both cases.