CS412 Fall 14 Prof Ron September 23 2014 Assignment 2 Due October 7 2014 2 15 p m after that day assignments should be put into the mbox of Chaowen Yu 1 In 1669 Sir Isaac Newton demonstrated a new method he found for solving equations by finding the root x3 3x 5 0 has in 2 3 Since you envy Newton you try to do the same albeit a few years after him For that choose a cubic polynomial that has a root i e a zero in the interval 2 3 the cubic polynomial must involve at least three terms i e do not choose something like x3 a 0 for a suitable a Then run the 1669 algorithm on your problem we did not tell you what method Newton used so you need to make some intelligent guess here Then find that same root by using the bisection method and by using the secant method use matlab FYI Newton did not use matlab during his demo Derive from the output the rate of convergence of each method to the extent that this is possible 2 no code and or programming is involved in this question In a certain computer the accuracy of addition subtraction and multiplication is eight significant decimal digits while division is accurate only to two significant decimal digits To improve the accuracy of division we use Newton s method with respect to the function f x 1 1 ax for the computation of the number a1 a Explain how this method is implemented your explanation should cover at least the following points i how does the Newton method when applied to the above function compute the number 1 a ii What is the trick here precisely how are we able in this way to divide 1 by a better than the machine s hardware can do To understand the process better do the first iteration for a 13 Take your initial guess for 1 13 to be 0 1 make all the calculations Show that no division is used in the iteration b Use the expression for the error look below after the end of the assignment and derive the number of iterations that are needed for eight significant digit accuracy An important remark the number of iterations crucially depends on your initial guess There is a natural initial guess provided by the machine s division that should be adopted 3 About 300 years after Newton the famous numerical analyst Wilkinson showed that roots of polynomials are highly sensitive to small alterations in their coefficients He used the polynomial p t t 1 t 2 t 3 t 20 10 8 t19 a Prove that p has a root in 20 22 and then use the secant method you already have a code from 1 for finding that root Your code may contain a while loop for the iterations but you should try to avoid a loop for evaluating p the matlab command prod v computes the product of the entries of the row column vector v 1 b In order to appreciate the power of superlinear convergence find experimentally the number of iterations needed in a to get the root to within an error 10 3 find also the number of iterations for accuracy 10 13 and compute the ratio of these two numbers What would have been that ratio had we used bisection instead of secant As an estimate for the error in the secant case take the difference between consecutive approximations As an estimate for the error in the bisection case take half the size of your current interval c What in your opinion is the reason for choosing secant here and not Newton or bisection Give all reasons you may think about d Explain how this example helped Wilkinson in making his point Why in your opinion is this an important observation Hint suppose that we try to find polynomial roots by running some program on some machine 4 Find the polynomial of degree 10 that interpolates the function arctan at the 11 equally spaced points linspace 0 5 11 you may use any interpolation process including those that I used in 3inter demo You are not allowed however to use the matlab library m file polyfit m Then compute the error over the interval 1 6 i e evaluate the error on a fine mesh on the interval 1 6 The matlab command linspace 1 6 generates such mesh Try then to see whether similar results are obtained if you increase the number of interpolation points and or change their distribution Turn in your code your output and a brief account of the conclusions you drew from this experiment 2