MATH 251 Final, Fall 2003

AMERICAN UNIVERSITY OF BEIRUT Faculty of Arts and Sciences Computer Science Department CMPS 251 FINAL EXAM FALL 2003-2004 Closed Book, Two hours GIVE YOUR ANSWERS ON THE QUESTION SHEET SUBMIT WITH BOOKLET STUDENT NAME ID NUMBER 1 1. In this problem, we consider the following table for the function f(x). All computations shall be carried out with 8 significant figures. xi yi 0.000 4.000000000000000 0.125 3.938461538461539 0.250 3.764705882352941 0.375 3.506849315068493 0.500 3.200000000000000 0.625 2.876404494382022 0.750 2.560000000000000 0.875 2.265486725663717 1.000 2.000000000000000 (a) Write the polynomial of degree 3 p(x) that would best approxi- mate f(0.3). Find p(0.3). 2 (b) Using the central difference formula to approximate f ′(0.5), fol- lowed by Richardson’s extrapolation find the best approximation to f ′(0.5). For that purpose, fill out the following table. h φc,h φ(1) c,h φ(2) c,h 0.5 × × × × 0.25 × × 0.125 3 (c) Using the Mid-point, trapezoidal and Simpson’s rules followed by Romberg integrations fill out the following table used to approxi- mate I = � 1 0 f(x)dx h Mh Th Sh R(1) h R(2) h h0 × × × × h0 2 × × h0 4 h0 8 × × × × × × × × 4 2. Suppose a real number L is appoximated by φ(h) such that: L = φ(h) + c1h3 + c2h5 + c3h7 + ..., where the coefficients {ci} are independent from h. What combina- tion of φ(h) and φ( h 2) would give a better approximation φ1(h) to L than φ(h)? What is the order α of the approximation of L by φ1(h), (i.e. L = φ1(h) + O(hα))? 5 3. Loss of significant figures may result in the computation of the follow- ing functions of the variable x for certain values of x. Specify these values then propose alternative functions that would remedy the loss of significant figures. (If necessary you may use Taylor’s series). (a) f(x) = x + √ x2 − 1 (b) g(x) = x − sin(x) 6 4. To perform Naive Gauss elimination for the following quadridiagonal matrix                     d1 u1 v1 0 .. .. 0 0 l1 d2 u2 v2 0 .. .. 0 0 l2 d3 u3 v3 0 .. 0 0 0 l3 d4 u4 v4 .. 0 : . . . . . . . 0 .. 0 li di . . . : . . . . . . . : . . . ln−3 dn−2 un−2 vn−2 0 . . . . ln−2 dn−1 un−1 0 .. .. 0 .. 0 ln−1 dn                     One uses the following algorithm: for i from 1 to n-1 li = li/di di+1 = di+1 − li ∗ ui if i<n-1 ui+1 = ui+1 − li ∗ vi end end Give the exact number of floating point operations needed to per- form this algorithm. 7 5. Give with justification the minimum number of arithmetic operations (additions, subtractions and multiplications) to compute, using nested multiplication, the following polynomials Polynomial p(x) Minimum number of arithmetic operations (x − 2)17 + (x − 2)31 4x5 − 6x12 + 2x17 − x33 8