CMPS 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 fur PNT EI iak OF BERLE: 1. In this problem, we consider the following table for the function f(z). All computations shall be carried out with 8 significant figures. zi vi 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(z) that would best approxi- mate f(0.3). Find p(0.3). (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. (c) Using the Mid-point, trapezoidal and Simpson’s rules followed by Romberg integrations fill out the following table used to approxi- mate I = fj f(x)dz 2. Suppose a real number L is appoximated by ¢(h) such that: L= o(h) + qh? + cgh® + cgh™ +..., where the coefficients {c;} are independent from h. What combina- tion of d(h) and ¢(8) would give a better approximation ¢'(h) to L than $(h)? What is the order a of the approximation of L by ¢'{h), (ie. L = '(h) + O(h?))? 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(t) =ac2+Va2?-1 4. To perform Naive Gauss elimination for the following quadridiagonal matrix d, Uy Vi . ” 0 ly dy U2 0 bk ad 0 0 k 0 One uses the following algorithm: for i from 1 to n-1 l, = b/d; dig. = dig, — li * Ui if i<n-1 Wiad = Ug — UY * vy end end Give the exact number of floating point operations needed to per- form this algorithm. 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 (@— 2) + @— 9 4x5 — 6x}? + Qz)7 — 798