Module 2: Root Finding Questions Question 1 The almost universally used algorithm to compute V5 is the recursion 1 a n : - n 3 1 $1? +1 2 (it? + 9:\") i l easily obtained by means of Newton's method. a. Assume you are working with a very simple processor that only supports addition, subtraction, multiplication and halving (a subraction of one in the exponent of a base-2 number), but not a. general divide. Devise a fast algorithm for this processor to directly approximate v1: (it then only remains to multiply with a. to get V5). Other approaches than Newton's method are available for generating fast iterative methods for com puting J5. One approach starts by noting that '2 zxrri where-rzlx a is an identity for any (positive) value of 2:. Hence the iteration _i at? mn+1=arn(1r) 2 whererzlt will converge in one step to 5. However, this iteration is useless since it requires the computation of a square root (we could have just as well computed 3/5 directlyl). To make this iteration useful, we note that 1" becomes small if :33.n is a good approximation to a, which suggests replacing (1 r)\"if by a truncated Taylor expansion. By including dierent numbers of terms in the Taylor expansion, we get iterative methods of arbitrary order of convergence. b. From the preceding discussion, derive the quadratically convergent recursion 3,, xi $n+1 = 3 (3 ) - (2) 0. Explain why it is quadratically convergent. c. Suppose a = 4, determine in which intervals around the root :1: = 2 the two iterations (1) and (2) will i. converge to the root :2: : 2, and ii. diverge to co. 2 Hint: Plot separate graphs of y = 3:, y = % (z + i), and y = :15, y = 52\"- (3 if), respectively. Illustrate the iteration process graphically in the style of Figure 2.6 in Atkinson