Numerical Analysis Exam 1 Study Guide Solutions

Exam 1 Study Guide Solutions 1. Convert the base 10 number 0.4 into binary, then into floating point format. Compute the error in the floating point approximation (Use double precision and IEEE rounding). SOLUTION: First compute the binary form. 0.4 0.8 0.6 0.2 .. . × × × × 2 2 2 2 = = = = 0.8 0.6 0.2 0.4 + + + + 0 1 1 0 ⇒ 0.011001100110... Now into (normalized) floating point format. Before doing that, we might look to see what the 54th element will be (we’ll be moving the “binary point” 2 places to the right afterwards, then we’ll need the 52d place). Reason it out (or use modular arithmetic) to see that in positions 53, 54, 55, 56 we’ll have the 0110 pattern. Shifting the point to the right and leaving a gap between elements 52 and 53 (post shift), 0.0110011001100110... = 1.1001100..01 1001... × 2−2 Now, we’ll need to round up to get the floating point number: f l(0.4) = 1.1001100...10 × 2−2 where we’ve dropped 0.10011001100... × 2−52 × 2−2 and added 2−52 × 2−2 = 14 . To get the error in the floating point number, we need to convert the error back into base 10: 0.1001100110011.. × 2−54 = 10.01100110... × 2−56 = 2.4 × 2−56 = 24 1 3 · · 2−52 =  10 16 20 Putting it all together, 1 1 3  +  = 0.4 +  20 4 10 Hint: Sometimes it is easier to see what the error is by putting it all in terms of  = 2−52 f l(0.4) = 0.4 − 2. Convert the binary number: 0.11010101... into base 10. SOLUTION: We’ll use the technique from class: Let x 2x 4x 8x =0 =1 = 11 = 110 .1101010... .1010101... .0101010... .1010101... ⇒ 8x − 2x = (110 − 1)2 = 5 ⇒ x= 5 6 We can quickly double check our answer: 5/6 4/6 2/6 4/6 .. . × × × × 2 2 2 2 = = = = 4/6 2/6 4/6 2/6 + + + + 1 1 0 1 ⇒ 0.11010101... 3. Give Taylor’s Theorem with the Lagrange form of the remainder (this is what we did in Homework set 1). Let f (x) be n + 1 times continuously differentiable at x = a. Then there is a c between x and a so that: f n (a) f n+1 (c) f (x) = f (a) + f 0 (a)(x − a) + . . . + (x − a)n + (x − a)n+1 n! (n + 1)! 1 4. Let P (x) be a polynomial interpolation of f (x) at the n + 1 data points, (x0 , y0 ), . . . , (xn , yn ). What is the form of the error, |f (x) − P (x)|? Are we guaranteed that the error will decrease as we increase the number of data points used? In fact, what did we see in the homework? The form of the error is: |f (x) − Pn (x)| = f (n+1) (c) (x − x0 )(x − x1 ) · · · (x − xn ) (n + 1)! We are NOT guaranteed that the error will decrease as n increases. In fact, if the data points are evenly spaced, we saw that it was possible for the error to increase (The Runge Phenomena, as seen in f (x) = 1/(1 + 12x2 ) with 7, 15, 25 evenly spaced points). 5. What methods do we have for polynomial interpolation over a fixed set of base points. Use them to give the interpolating polynomial for the data: x −1 y 1 1 2 3 0 3 1 Are they giving the same answer? Explain. We had a linear algebra version (but we didn’t actually solve the matrix equation yet, so this version is optional). We had Lagrange and Newton’s Divided Differences. For the Lagrange polynomial, we construct Li (x), then add them together: L0 (x) = (x − 1)(x − 2)(x − 3) 1 = − (x − 1)(x − 2)(x − 3) (−1 − 1)(−1 − 2)(−1 − 3) 24 L1 (x) = L2 (x) = L3 (x) = (x + 1)(x − 2)(x − 3) 1 = (x + 1)(x − 2)(x − 3) (1 + 1)(1 − 2)(1 − 3) 4 (x + 1)(x − 1)(x − 3) 1 = − (x + 1)(x − 1)(x − 3) (2 + 1)(2 − 1)(2 − 3) 3 (x + 1)(x − 1)(x − 2) 1 = (x + 1)(x − 1)(x − 2) (3 + 1)(3 − 1)(3 − 2) 8 In this case, P (x) = 1 · L0 (x) + 0 · L1 (x) + 3 · L2 (x) + 1 · L3 (x) For the Newton’s Divided Difference Method, −1 1 −1/2 1 0 7/6 −11/12 3 2 3 3 1 −5/2 −2 In this case, the polynomial is: 1 7 11 P (x) = 1 − (x + 1) + (x + 1)(x − 1) − (x + 1)(x − 1)(x − 2) 2 6 12 For practice, we could write this in nested form:     1 7 11 P (x) = 1 + (x + 1) − + (x − 1) + (x − 2) − 2 6 12 2 6. Explain the bisection method. The bisection method is used to solve f (x) = 0 for x. We use the Intermediate Value Theorem to bracket the solution- That is, we first find a, b (assume a < b) so that f (a), f (b) are opposite in sign. We get a new interval by computing c = 1+b 2 , and f (c). Keep either [a, c] or [b, c], whichever keeps the root bracketed. Repeat. As an algorithm, we could write: Given a, b so that f (a), f (b) are opposite in sign: • Let c = (a + b)/2. Compute f (c). • Get the new interval: – If f (c) = 0 (LUCKY!) We’re done. – If f (a)f (c) < 0, set b = c and repeat. – Otherwise, set a = c and repeat. 7. Using the bisection method on the interval [a, b], how would we determine how many iterations are needed to find the solution to 10−10 ? Answer with an integer. As we discussed in class (and in HW 2 Solutions, Problem 2), we’ll solve the following for n: |b − a| ≤ 10−10 2n+1 ⇒ |b − a|1010 ≤ 2n+1 ⇒ ln |b − a| + 10 ln(10) ≤ (n + 1) ln(2) Which gives us: n≥ ln |b − a| + 10 ln(10) −1 ln(2) so take n to be the next greatest integer up. (The “Answer with an integer” was meant for a different problem- Sorry!) Algebra/Calculus side note: If 0 < a < b, is it true that ln(a) < ln(b)? 8. What does it mean to say that a sequence is converging linearly? quadratically? on order α? A sequence {xn } converges to x of order α means that: |xn+1 − x| =λ<∞ n→∞ |xn − x|α lim For linear convergence, α = 1. For quadratic convergence, α = 2. SIDE REMARK: Using the error notation en = |xn − x|, linear/quadratic convergence gives us (respectively): en+1 en+1 lim =λ lim =λ n→∞ en n→∞ e2 n (a) Let xn = 1 n2 . Determine the order of the convergence (to 0). 1 (n+1)2 lim n→∞ (1/n2 )α n2α = lim = lim n→∞ (n + 1)2 n→∞  nα n+1 2  = nα−1 lim n→∞ 1 + 1 n 2 As long as α − 1 is not positive, this last limit exists. The largest α that makes this possible is α = 1. Therefore, the sequence 1/n2 converges linearly to 0. n (b) Let xn = 10−2 . Determine the order of the convergence (to 0). n+1 n 10−2 2n ·α−2n+1 = lim 102 (α−2) n ·α = lim 10 −2 n→0 10 n→0 n→0 lim As long as α − 2 is not positive, this last limit exists. The largest α that makes this possible is α = 2. The given sequence has quadratic convergence to 0. 3 9. Explain the fixed point iteration (FPI) method. Under what conditions are we guaranteed that the method converges (linearly and quadratically)? Fixed Point iteration means that, given an initial point x0 and a function, f (x), we create a sequence of points (the orbit of x0 ), x1 = f (x0 ), x2 = f (x1 ), x3 = f (x2 ), . . . Fixed point iteration may be used to solve for the roots of a function, g(x) = 0 by re-writing the equation as x = f (x) for some appropriate f . The FPI Theorem (p. 2 of “Convergence and Error”) states that, if f is continuous on [a, b] and differentiable on (a, b), and there exists k such that |f 0 (x)| ≤ k < 1 for all x in (a, b), then given x0 in (a, b), the orbit will converge to the fixed point, r. We get linear convergence if f 0 (r) 6= 0, and quadratic convergence if f 0 (r) = 0. We showed this by proving that, in the case where f 0 (r) 6= 0, then, letting en = |xn − r|, lim n→∞ en+1 = f 0 (r) en and in the case that f 0 (r) = 0, and f 00 (r) 6= 0, en+1 f 00 (r) = n→∞ e2 2 n lim This gives us a way of estimating en+1 in terms of en (See questions below). Side Remark: If f (r) = r, f 0 (r) = 0, f 00 (r) = 0, what kind of convergence can we expect? Look at the Taylor expansion: f (x) = f (r) + f 0 (r)(x − r) + From which we get: f 00 (r) f 000 (c) f 000 (c) (x − r)2 + (x − r)3 = f (r) + (x − r)3 2 6 6 xn+1 − r f (xn ) − f (r) f 000 (c) = = 3 3 (xn − r) (xn − r) 6 Taking limits of the absolute value of the terms, we see that we get cubic convergence. 10. Explain (graphically) Newton’s Method. Under what conditions are we guaranteed that the method converges? When will it converge only linearly? Quadratically? The graphical meaning we’ll cover in class. We showed that, for a sufficiently smooth function g (twice continuously differentiable), it is always possible to find an interval about the root, [r − δ, r + δ] so that, if g 0 (r) 6= 0, we get quadratic convergence to the root. Where did δ come from? If we let F (x) = x − gg(x) 0 (x) , we found we could apply the Fixed Point theorem to F . To find an appropriate δ, we need an interval about r so that F, F 0 are continuous AND |F 0 (x)| < 1. The last step is guaranteed, since F 0 (r) = 0. Finally, we showed that, if g 0 (r) = 0, we only get linear convergence (Are you surprised it would converge at all? After all, that means the denominator is going to zero!) 4 11. Suppose we are using Newton’s Method on f (x) = x3 − x2 − 5x − 3. Assuming convergence to the root r = −1, estimate the error en+1 = |xn+1 − xn | in terms of en . Do the same if we assume convergence to another root, r = 3. We’re given information about f (x) so we can determine if we’re getting quadratic convergence or linear convergence at the roots. This depends on f 0 (r), as noted in the previous question. As usual, let F (x) = x − f (x)/f 0 (x). If f (x) = x3 − x2 − 5x − 3, then f 0 (x) = 3x2 − 2x − 5. We can also compute F (x), F 0 (x): F (x) = x − (x − 3)(x + 1)2 2x2 − 3x + 3 = , x + 1)(3x − 5) 3x − 5 F 0 (x) = 2(x − 3)(3x − 1) (3x − 5)2 NOTE: If you don’t simplify F 0 (x), we won’t be able to compute F 0 (−1) directly; we would have to take the limit. We see that f 0 (−1) = 0, so in that case we only can expect linear convergence. That means, in terms of the error: en+1 1 ≈ F 0 (−1) = en 2 And, at x = 3, we see that f 0 (3) 6= 0, but F 0 (3) = 0. This means, in terms of the FPI theorem, that we can expect at least quadratic convergence. In that case, we construct F 00 (x) = 64/(3x − 5)3 , so en+1 F 00 (3) 1 ≈ = 2 en 2 2 Exam Note: The algebra here can get a little messy. I would typically give you simplified expressions for F, F 0 , F 00 if I were to ask this on an exam. 12. Suppose the bisection is applied to f (x) = 1/x with a starting interval [−2, 1]. Does the method converge to a real number? Is it the root? Iterate bisection a few times to get a sense of what it will do. If you do that, you should find that the intervals are: [−2, 1] → [−1/2, 1] → [−1/2, 1/4] → [−1/8, 1/4] → [−1/8, 1/16] → ... We note that the interval length is going to zero, so Bisection is converging. However, it is not converging to the root- In fact, the root (there is none) is never bracketed, so we started with a false assumption. It is interesting that nevertheless, there is convergence to something. 13. Suppose f (x) = x1 as in the previous problem, but now we apply Newton’s Method to it. If x0 = 1, find x50 (Note: This is not a Matlab problem). Construct F (x) = x − f (x)/f 0 (x) = x − (−x) = 2x. If x0 = 1, then: x1 = 2, x2 = 22 , x3 = 23 , ..., x50 = 250 14. Find each fixed point for g(x) = 12 x2 + 12 x and determine if FPI is locally convergent to it (locally convergent means that the algorithm will converge, given an initial point that is close enough to the solution). The fixed points are found by solving x = g(x). In this case, x= 1 2 1 x + x 2 2 ⇒ so the fixed points are x = 0, x = 1. 5 0= 1 x(x − 1) 2 Will we converge to x = 0? Compute g 0 (0) = 21 . This is less than 1 (in absolute value), so if we start close to x = 0, we can expect convergence (linear). Will we converge to x = 1? Compute g 0 (1) = 32 . This is greater than 1 (in absolute value), so we will not converge to this fixed point, no matter how close we start (unless we start exactly at the fixed point). 15. Find the forward and backward error for finding the root of the function f (x) = ax − b. For root-finding, we gave the general formulas: Forward Error = |∆r|, Backward Error = |f (r + ∆r)| In our case, Forward error is |∆r|, and the backward error is: |f (r + ∆r)| = |a(r + ∆r) − b| = |(ar − b) + a∆r| = |a||∆r| Note that the error magnification factor is 1/|a|, which is what one might expect- That is, a line that is almost horizontal gives us numerical problems when computing f (x)- Values of x that are very far apart will give corresponding f (x) values that are very close together. 16. Give an interval of the form (a − δ, a + δ) on which we can guarantee the convergence of Newton’s Method, if f (x) = x2 − 1 and the root is r = −1. We did this in class previously. The idea is to find a symmetric interval about r = 1 so that F, F 0 are continuous, and most importantly, |F 0 (x)| < 1: In this case, F (x) = x − x2 − 1 1 = 2x 2  x+ 1 x  F 0 (x) = , 1 2  1− 1 x2  We see that the radius of our interval about r = 1 has to be less than 1 for F, F 0 to be continuous. We also see that, if x > 1, then |F 0 (x)| < 21 . In fact, F 0 (x) will never be equal to 1 for any x, so we need to find the point in 0 < x < 1 so that F 0 (x) = −1, and that will give the restriction:   1 1 1 1 1 1 − 2 = −1 ⇒ 1 − 2 = −2 ⇒ x2 = ⇒ x = √ 2 x x 3 3 √ The appropriate radius is then: δ = 1 − 1/ 3 Notes about the new material, Chebyshev’s Theorem: I’ll give you the following information: Tn (x) = cos(n cos−1 (x)) cos(a + b) = cos(a) cos(b) − sin(a) sin(b) Tn+1 (x) = 2xTn (x) − Tn−1 (x) Be sure that you can: 1. Construct T0 (x), T1 (x), T2 (x): T0 (x) = 1, T1 (x) = x, T2 (x) = 2x − 1 2. Show that Tn (1) = 1, Tn (−1) = (−1)n . Tn (1) = cos(n cos−1 (1)) = cos(n · 0) = cos(0) = 1 Tn (−1) = cos(n cos−1 (−1) = cos(nπ) Here we see that, if n = 1, cos(π) = −1, n = 2, cos(2π) = 1, n = 3, cos(3π) = −1, and so on. 6 3. Find a formula for Tn (0).  π Tn (0) = cos(n cos−1 (0)) = cos n 2 Listing these out, we see that: n 1 2 Tn (0) 0 −1 3 4 ... 0 1 ... So, we could say something like: Tn (0) =   0 −1  1 if n is odd if n = 2, 6, 10, . . . if n = 4, 8, 12, . . . 4. Determine T999 (−1/2) We can compute this directly:  
2π T999 (−1/2) = cos 999 · cos−1 (−1/2) = cos 999 · = cos(333 · 2π) = cos(2π) = cos(0) = 1 3 5. Explain why the lead coefficient of Tn (x) is 2n−1 . This is due to the fact that T0 = 1 and the recursion relation Tn+1 = 2xTn (x) + Tn−1 (x). Given that the first (n = 0) lead coefficient is 1, all others will be increasing powers of two. 6. Be able to solve for the zeros of Tn (x) by solving the following equation for x: cos(n cos−1 (x)) = 0 As you do this, explain why there are n + 1 solutions (Hint: Consider the domain and range of the restricted cosine function). ERROR: This should have said that there are exactly n zeros- A polynomial of degree n cannot have n + 1 roots. Let θ = cos−1 (x), or cos(θ) = x, where −1 ≤ x ≤ 1 and 0 ≤ θ ≤ π (these are the restrictions so that cos(x) is 1 − 1 and invertible). Now, if cos(A) = 0, then A must be an odd multiple of π, π 3π 5π A = ± ,± ,± ,... 2 2 2 Therefore, π 3π 5π nθ = ± , ± , ± , . . . 2 2 2 or the candidates for θ: θ=± π 3π 5π ,± ,± ,... 2n 2n 2n However, 0 ≤ θ ≤ π, so this leaves: θ= π 3π 5π (2k − 1)π , , ,..., ,...,π 2n 2n 2n 2n How many of these are there? We can’t let k go above n, since that would put θ to be more than π, therefore there are exactly n of them. 7 7. Finally, what was Chebyshev’s Theorem? Do we have to use Chebyshev Polynomials to do the interpolation? Theorem 1 (Chebyshev’s Theorem) The choice of real numbers −1 ≤ x1 , x2 , . . . , xn ≤ 1 that makes the value of max |(x − x1 )(x − x2 ) · · · (x − xn )| −1≤x≤1 as small as possible is:  xi = cos (2i − 1)π 2n  , i = 1, 2, . . . , n Furthermore, the minimum value is 1/2n−1 . 8. Assume that the Chebyshev points are used, and we construct a fifth degree polynomial, P5 (x) to interpolate f (x) = ex on [−1, 1]. Use the error formula to determine the worst-case estimate of the error, |ex − P5 (x)| valid on the whole interval [−1, 1]. |ex − P5 (x)| ≤ ec e 1 |(x − x1 ) · · · (x − x6 )| ≤ ≈ 1.2 × 10−4 6! 720 25 9. Suppose that I want to do a Chebyshev interpolation using 5 points on the interval [−1, 4]. How would I do it, and what are the points (You may use your calculator, and give your answers to 3 decimal points, rounded). The 5 points would be: 0.9659 0.7071 0.2588 -0.2588 -0.7071 Which, by the way, could be computed in Matlab as: k=1:5; cos( ((2*k-1)*pi)/(2*6) ) 8