CMPS 251 Final, Fall 2013

Page | 1 Faculty of Arts & Sciences Department of Computer Science CMPS 251—Numerical Computing Fall 2013–14 Friday, Dec 20th, 2013 Instructions Write your name, Id number, and your major in the space provided above. THE EXAM IS CLOSED BOOK, CLOSED NOTES, & “CLOSED NEIGHBOR”!! Your answers must be presented on the question sheet itself. Your handwriting should be readable so it can be graded. Use the provided space for your answers. If the space is not enough, then most probably you are writing more than what is expected. In case you need more space, put an “explicit pointer” to where your answer is written or continued (e.g. draw an arrow, or say back of page or both !!!…) There are 8 problems altogether and 10 pages (including this front page). You may use the back of the sheets for scratch work. DO NOT CUT OFF ANY PAGE !! Family Name First Name Id. Num Major FINAL EXAM Duration: 90 Minutes Problem Grade Your Grade 1 20 2 10 3 25 4 10 5 15 6 15 7 25 8 10 Total 130 Page | 2 Problem 1 (20 Points) Approximations - Errors a. (7) Specify what is meant by the “absolute error” and the “relative error” in an approximation to a quantity . Absolute Error = Relative Error = Is the unit of round-off in a floating point number system a relative measure or an absolute measure? Circle one of the following: relative measure absolute measure b. (5) Round-off error is inherent in any numerical computing scheme that uses real numbers. Why is that so? Can it be avoided? c. (4) In a numerical scheme that is supposed to solve a system of linear algebraic equations, say using Gaussian Elimination, are there other kinds of errors besides round-off? If yes name one that you consider to be the most important. Be precise and brief. d. (4) In a numerical scheme that is supposed to produce an approximation to the solution of a differential equation, are there other kinds of errors, besides round-off? If yes name one that you consider to be the most important. Be precise and brief. Page | 3 Problem 2 (10 Points) a. (5) How many non-zero terms are needed in the Taylor series expansion of around to obtain an answer to 5 digits of accuracy (i.e., error less than ) . b. (5) Consider performing the computation as: a = sqrt(4 + 1e-6) – 2; Can the computation be performed reliably in single precision? How can we rewrite the computation to obtain better accuracy? Page | 4 Problem 3 (25 Points) Data Fitting Suppose that the following data about y(x) is given: x 1 2 3 4 y 0 2 2 4 a. (10) Show how to get the Spline of degree 1 that interpolates this data. b. (10) The data above is to be best fit in the least squares sense, by a linear polynomial y=ax+ b. Find a and b, showing the system of equations that they must be satisfy. c. (5) Show that (x*,y*) is on the straight line of (b), where x* and y* are the averages of the xi’s and yi’s respectively. Page | 5 Problem 4 (10 Points) Cubic Spline Do there exist a, b, c, and d such that the function -x (-10 x  -1) S(x) = a x3 + bx2 + cx + d (-1  x  1) x (1  x  10) is a natural cubic spline? Justify your answer. Page | 6 Problem 5 (15 Points) Euler’s Method Consider the Initial Value Problem (IVP): x’ = f(t,x) , t > 0 x(0) =  Suppose we are interested in approximating x(1), using a step size h = 1/n a. (5) Show how to derive the forward Euler method using Taylor’s series. b. (3) Of what order is the local discretization error? c. What is the global error, assuming that f is Lipschitz continuous w.r.t x? Page | 7 Problem 6 (15 Points) Shooting Method Consider the boundary value problem (BVP): x” + x’ - q x = a(t), 0  t  1 x(0) = 1, x(1) = 3 where q is a nonnegative constant and a(t) is a given continuous functions on (0,1). Suppose that we want to use the Shooting Method to solve the BVP. For that we consider the initial value problem (IVP) : x” + x’ - q x = a(t), 0 < t < 1 x(0) = 1, x’(0) = z a. (5)Show how to convert the second order initial value problem above, to a set of two first-order equations (i.e. a first order initial value problem but for a vector function). b. (5) Indicate how Euler’s method may be used to solve the problem in (a) above. c. (5) Suppose that we have numerically solved the two initial value problems: u” + u’ - q u = a(t), v” + v’ - q v = a(t), u(0) = 1, u’(0) = 1 v(0) = 1, v’(0) = 2 and have found as terminal values u(1) = 2 and v(1) = 3.5. What is a reasonable initial value problem to try next in attempting to solve the original BVP? Expalin. Page | 8 Problem 7 (25 Points) Discretization Method Consider the boundary value problem (BVP): x” + x’ - q x = a(t), 0  t  1 x(0) = 1, x(1) = 3 where q is a nonnegative constant and a(t) is a given continuous functions on (0,1). Subdivide the interval [0,1] using a uniform partition, 0=t0 < t1 < ... tn+1= 1, into n + 1 equal subintervals, with h = 1 / (n+1) , h > 0, n > 1. Consider the two centered difference formulas: x’(a) = [ x(a+h) - x(a-h)] / 2h + O (h ) x”(a) = [ x(a+h) – 2x(a) + x(a-h)] / h2 + O (h ) a. (6) Using these difference formulas, propose a discretization method for approximating the solution of the BVP. We seek x0, x1, ... xn+1 that approximate x(t0), x(t1), ... x(tn+1), where b. (7) Specify the resulting system of linear equations A x = b. In particular, specify the dimension and the structure of A, its entries, and the right hand side vector b. c. (5) For what values of h is A diagonally dominant? Page | 9 d. (4) Suggest a numerical method for solving the system A x = b of (b). Do you expect pivoting to be needed? Why? e. (3) Specify the big O order of the number of long operations involved, interms of the dimension of the matrix A. Page | 10 Problem 8 (10 Points) Finite Element Method Consider the boundary value problem (BVP): y” + y’ + q y = a(t), 0  t  1 (B.C.) y(0) = 0, y(1) = 0 where q is a nonnegative constant and a(t) is a given continuous functions on (0,1). Subdivide the interval [0,1] using a uniform partition, 0=t0 < t1 < ... tn+1= 1, into n + 1 equal subintervals, with h = 1 / (n+1) , h > 0, n > 1. This time we want to use the finite element method to approximate the solution. Without working out the full details, answer the following: a. (5) What will be the structure of the system of linear equations, assuming that the basis functions are the piecewise linear hat functions? Why? b. (5) What will be the structure of the system of linear equations, assuming that the basis functions are the piecewise cubic splines? Why?