m136_le2_answers.pdf

Math 136 Introduction to Numerical Analysis Second Long Examination Answers University of the Philippines Baguio, Second Semester, A.Y. 2023-2024 ”Cheating is a form of intellectual dishone...

Math 136 Introduction to Numerical Analysis Second Long Examination Answers University of the Philippines Baguio, Second Semester, A.Y. 2023-2024 ”Cheating is a form of intellectual dishonesty that will not be condoned. Anyone caught cheating shall be dealt with in accordance with the rules on student conduct and discipline. Cheating is punishable with a grade of 5.0 in the course and/or (1) suspension for a period of not less than one year; or (2) expulsion from the University.” 1. (1 pt each) Write TRUE if the statement is always true. Otherwise write FALSE. (a) FALSE Given two continuous function f and g on the interval [a, b], the absolute value of the difference between the largest function value and the least function value of f and g, respectively, on [a, b] is equal to the infinity (or supremum) norm of h = |f − g| on [a, b]. (b) FALSE The interpolating polynomial about m ∈ N distinct nodes is always degree m − 1. (c) TRUE The Method of Undetermined Coefficients, Lagrange Interpolation, and Newton-Lagrange Interpolation produces the same solution to a Polynomial Interpolation Problem. (d) FALSE The more the equidistant interpolation nodes from a function, the more accurate our inter- polation polynomial is to the same function. (e) FALSE The Simpson 3/8’s rule uses quadratic polynomial to approximate the function. (f) FALSE Increasing the degree of the interpolation polynomial for non-composite Newton-Cotes quadra- ture gives better approximation for the integral of the function. (g) TRUE Increasing the number of sub-intervals considered for composite Newton-Cotes quadrature gives better approximation for the integral of the function. R1 (h) TRUE The exact value of 0 ex dx is less than the approximate value if we use Trapezoidal Rule. (i) TRUE The normalized weights for Newton-Cotes depends on the number of quadrature nodes. (j) TRUE There is a Runge-Kutta Method with one hundred stages. (k) TRUE A convergent single-step scheme is consistent. (l) FALSE The update scheme for the θ-method is uk+1 = uk + h2 [(1 − θ)f (tk , uk ) + θf (tk+1 , uk+1 )]. 2. (5 pts) Find the solution of the polynomial interpolation problem given (−1, 2), (1, 2), (2, 1), (3, 6), (4, 7). 4 Solution: − x2 + 10 3 9 2 10 3 x − 2 x − 3 x + 7 or 2 + 0(x + 1) − 3 (x + 1)(x − 1) + 56 (x + 1)(x − 1)(x − 2) − 12 (x + 1)(x − 1)(x − 2)(x − 3) 1 3. Give concise statements (at most 4 sentences only) that answers the following: 5 2 (a) (5 pts) In the item no. 3, verify that the polynomial g(x) = − x3 + 52 x4 −5x3 + x2 + 16 3 x−1 interpolates the given data. Explain why this does not violate the uniqueness of solution to the polynomial interpolation problem. Solution: In PIP, we are only guaranteed of degree 4 since we have 5 interpolation points. We can have another polynomial if we introduce additional interpolation point e.g. (0, −1). (b) (2 pts) What is the difference between explicit and implicit methods? Solution: Explicit methods uses previous known values to find the next iterate. Implicit methods uses the current unknown iterate to update it. Usually, root finding methods are used to solve implicit problems. (c) (3 pts) What does a stable solution to ODE mean? Why do we consider stability of solutions when solving the ODE numerically? Solution: If small changes to initial value will lead to small changes in the solution of ODE, then the solution is stable. A stable solution is desirable for numerical schemes since rounding errors due to floating point operations may affect the solution of the ODE. f [x1 ,...,xn+1 ]−f [x0 ,...,xn ] 4. (5 pts) Given distinct points {xk }n+1 k=0 , show that f [x0 , x1 ,... , xn+1 ] = xn+1 −x0. Use the back of the first page for your proof.  Solution: Let Pn (x) be the solution of PIP on f about the distinct points {xk }n+1 k=0. Also let P̃n−1 be the solution of PIP on f about the distinct points {xk }n+1 k=1. Recall that the leading coefficient of Pn (x) is denoted by f [x0 ,... , xn ]. We first prove the following Neville’s Formulation: (x − x0 )P̃n−1 (x) − (x − xn+1) )Pn−1 (x) Pn (x) = =: Qn (x). (1) xn+1 − x0 Note that both Pn (x) and Qn (x) is of degree at most n. It is easy to see that Q(xk ) = f (xk ) for k = 0, 1,... , n + 1. Hence Q(x) is also a solution to the PIP on f about the points k = 0, 1,... , n + 1. By the uniqueness of solution to PIP, (1) is true for all x ∈ R. Taking the leading coefficients of both sides of (1), we obtain f [x1 ,... , xn+1 ] − f [x0 ,... , xn ] f [x0 , x1 ,... , xn+1 ] =. xn+1 − x0 5. (5 pts) Let the Lagrange characteristic polynomial be denoted by ℓn,k (x) for k = 0, 1,... n given the distinct points {xk }nk=0. Prove that nk=0 ℓn,k (x) = 1 for all x ∈ R. Use the back of the first page for your proof. P Solution: Consider the constant function Pfn (x) = 1. The Lagrange Pn polynomial interpolation on f about n the distinct points {xk }k=0 is Ln (x) = k=0 f (xk )ℓn,k (x) = k=0 ℓn,k (x). Since f is a polynomial of degree 0, then Ln (x) must also be of degree 0. Since Ln (x0 ) = 1 due to PIP property, then Ln (x) = 1 for all x. dy 6. (5 pts) Solve the value of y(0.2) given the initial value problem dx = x + 2y, y(0) = 1 by applying Heun Method twice. Do not round your computations and your final answer. Solution: k x k yk f (xk , yk ) yk′ = yk + hf (xk , yk ) f (xk+1 , yk′ ) 0 0 1 2 1.2 2.5 1 0.1 1.225 2.55 1.48 3.16 2 0.2 1.5105  q  7. (3 pts) Find the values of α, β and γ so that the integral of f (x) over [−1, 1] is exactly φ(f ) = αf − 35 + q  3 2 βf (0) + γf 5 for f (x) = 1; f (x) = x; and f (x) = x. Use the back of this page for the proof. (a) (3 pts) Verify that any polynomial p of degree up to and including 5 is exactly equal to φ(p). R1 2 (b) (4 pts) Evaluate 0 e−x dx using the new scheme. First convert the interval of integration [0, 1] into [−1, 1] by some change of variables. Then apply the scheme (without rounding the function values) to obtain the approximate value of the integral. Round your final answer to 10 decimal places. Solution: R1  q  q  From −1 f (x)dx = αf − 35 + βf (0) + γf 3 2 5 , for f (x) = 1, x, x , we obtain the following system r r 3 3 2 3 3 2 = α + β + γ; 0=− α+ γ; = α + γ. 5 5 3 5 5 5 It follows from the second and third equation that α = γ = 9 and from the first equation that β = 89. Given p(x) = a0 + a1 x + a2 x2 + a3 x3 + a4 x4 + a5 x5 , then r ! r r r 3 3 3 3 3 9 9 3 p − = a0 − a1 + a2 − a3 + a4 − a5 5 5 5 5 5 25 25 5 r ! r r r 3 3 3 3 3 9 9 3 p = a0 + a1 + a2 + a3 + a4 + a5. 5 5 5 5 5 25 25 5 Then Z 1 2 2 p(x)dx = 2a0 + a3 + a5 = φ(p). −1 3 5  R1 2 R1 −(t+1)2 /4 dt. Consider the following change of variable x = 1 2t + 12. Hence 0 e−x dx = 1 2 −1 e Let 2 f (t) = e−(t+1) /4 so that Z 1 r ! r ! −x2 5 3 8 5 3 e dx = φ(f ) = f − + f (0) + f 0 9 5 9 9 5  q 2  q 2 5 − 1− 35 /4 8 −1/4 5 − 1+ 35 /4 = e + e + e 9 9 9 ≈ 0.746814584191 Prepared by: Junius Wilhelm G. Bueno 31052024