73110 : Computer Lab 4

Every student should fill out his/her own lab worksheet. Do as many problems as you can, not necessarily in order.

You are encouraged to discuss the problems with the teaching assistant and with your neighbour.

Problem 1

1. The vector p=[1 2 3 4 5] represents what polynomial? Answer:______________
   
2. Horner's algorithm for evaluating polynomials is implemented in what Matlab function? Answer:_________
3. The coefficients of the derivative of a polynomial are computed by what Matlab function? Answer:_________
4. The roots of a polynomial are computed by what Matlab function? Answer:_____________

Problem 2

Synthetic division of polynomials is also called deconvolution, and is implemented in Matlab's deconv function. Thus Example 5 in section 3.5 of the textbook can be computed as follows.

p=[1,-4,7,-5,-2];
z0=3;
[p,r]=deconv(p,[1,-z0])
[p,r]=deconv(p,[1,-z0])
[p,r]=deconv(p,[1,-z0])
[p,r]=deconv(p,[1,-z0])

Using this as a model, use deconv to find the Taylor series of the polynomial 9z^4-7z^3+z^2-2z+5 about the point z=1. Answer: ______________________

Problem 3

1. Use Theorem 3 and 4 of section 3.5 to find the radius of a complex disk centered at the origin that contains all the roots of p(z), and the radius of a complex disk centered at the origin that contains none of the nonzero roots of p(z). Answer: radius of containing disk is __________, radius of excluding disk is ___________.
2. Do a graphical analysis with polyval to determine the number of real roots. Answer: the polynomial has ____ real roots.
   
3. Use Newton's method to find a complex root of the polynomial, using your answers in parts 1 and 2 to guide your choice of starting point. You could use newton.m from lab 3, or alternatively (after defining x and tol) you could use  the commands (which uses the Bodewig criterion from theorem 6 of section 3.5):
   
        dx=inf; dp=polyder(p); n=length(p)-1;
        while n*abs(dx)>tol, dx=-polyval(p,x)/polyval(dp,x); x=x+dx; end
   
    Answer: ________________ is a root of p(z).
4. Because the polynomial has real coefficients, complex roots will occur in conjugate pairs. Thus, if a+bi is the roots you found in part 3 then a-bi is also a root, and so f(z)=(z-a-bi)(z-a+bi)=z^2-2az+a^2+b^2 is a factor of the polynomial. Use deconv to deflate the polynomial, that is, to find the quotient polynomial p(z)/f(z). Answer: p/f=_____________.
5. Apply Newton's method or the quadratic formula to the deflated polynomial to find the remaining roots of p(z). Answer:________ and _____________ are roots of p(z).
6. Verify that the roots satisfy the estimates found in part 1 of this question. Answer: the distances between the roots and the origin in the complex plane are __________ and ____________.
   

Problem 4

[Textbook computer problem 2.3(6); 1st ed. problem 2.3(15)]

1. Generate the coefficients of the polynomial p(x)=(x-20)(x-19)...(x-2)(x-1) using the Matlab command
        p=poly(1:20)
   Answer: the coefficient of x^19 is _________ 
2. Compute the roots of the polynomial using roots. What are the errors of the computed roots corresponding to the roots r=1, r=16, and r=20? Answer: If c(r) denotes the computed root closest to r, then  |c(1)-1| = ______, |c(16)-16|=_______, and |c(20)-20|=___________. 
3. According to the analysis in section 2.3, a perturbation of e in the leading coefficient of the polynomial p(x) will cause the root r to move a distance of |e*r^20/p'(r)|. How far will the roots r=1, r=16, and r=20 move if the perturbation is e=1e-10? (Hint: p'(r) can be evaluated using polyval(polyder(p),r).) Answer: r=1 moves ______________, r=16 moves ____________, r=20 moves______________.
4. Compute the roots of the polynomial when the coefficient of x^20 is changed from 1 to 1+1e-10, and determine how far the computed roots corresponding to r=1, r=16, and r=20 have moved. Answer: c(1) moves ______________, c(16) moves ____________, c(20) moves______________. 
5. Comparing the answers in parts 3 and 4 shows that the polynomial roots are sensitive to perturbations in the leading coefficient. Repeating the analysis for the other coefficients gives similar results. In general, the roots of high degree polynomials are sensitive to perturbations in the coefficients. The polynomial in this question has coefficients that are not machine numbers, and the representation of the coefficients as floating point numbers is a perturbation that can cause significant changes in the roots. This partly explains the relatively large errors seen in part 2 of this question. Question: what is the representation error of the coefficient of x^4? Answer: |fl(a4)-a4|<=__________________
   

Problem 5

Problem 6

The file roots1.m  is an implementation of Laguerre's method. Compare its speed and accuracy to roots. Answer: __________ is faster and ________ is more accurate. What method does roots use? Answer: ______________.