Numerical Methods for Digital Computers (Fall 2020) Homework: 01 ICSI 401 – Numerical Methods Instructor: Abram Magner Date: Fall 2020 Instructions: Please answer the following questions in complete sentences, showing all work (including code and output of programs, when applicable). I prefer that you type your solutions (e.g., using LaTeX, with Overleaf, TeXworks, etc., or Word), but will accept handwritten notes. If the grader cannot read your handwriting, then they cannot award you points. Due date: Monday, 9/14/2020, 11:59 p.m., on Blackboard. 1.1 Calculus, Taylor series Consider the function f(x) = sin(x)x . 1. Compute limx→0 f(x) using l’Hoˆpital’s rule. 2. Use Taylor’s remainder theorem to get the same result: (a) Write down P1(x), the first-order Taylor polynomial for sin(x) centered at a = 0. (b) Write down a good upper bound on the absolute value of the remainder R1(x) = sin(x)− P1(x), using your knowledge about the derivatives of sin(x). The goal here is to show that R1(x)/x is negligible. (c) Express f(x) as f(x) = P1(x)x + R1(x) x , and compute the limits of the two terms as x→ 0. 1.2 Asymptotic notation Recall the definitions of the asymptotic notations. We will say that f(x) has “order of growth xα as x→ x0” (where x0 is either some fixed real number or ±∞) if f(x) = Θ(xα) as x→ x0. 1. Consider the functions f(x) = x sinx and g(x) = x. Is f(x) = Θ(g(x)) as x → ∞? Why or why not? (Hint: As always, you should refer back carefully to the definition of Θ(·).) 2. Suppose that we know that f(x) = x+ Θ(x2) and g(x) = Θ(x) > 0 as x→ 0. Determine the order of growth of f(x) + g(x). (This problem is meant to get you comfortable with manipulating asymptotic notation when it appears in expressions. When I say something like “f(x) = x + Θ(x2)”, this means that there is some function h(x) = Θ(x2), and f(x) = x+h(x). That is, the fact that h(x) = Θ(x2) is the only thing you know about h(x).) 3. Suppose that we know that f(x) = eΘ(x) as x → ∞. Does this imply that f(x) = Θ(ex)? (Hint: Think carefully about the definition of Θ(·), and consider f(x) = e2x.) 1-1 1-2 Homework 01: ICSI 401 – Numerical Methods 1.3 Relative versus absolute error 1. Suppose that you are approximating a function g(n) by some function f(n). Suppose, further, that you know that the absolute error in approximating g(n) by f(n) satisfies |f(n)−g(n)| = o(1) as n → ∞ (that is, limn→∞ |f(n) − g(n)| = 0). Is it true that the relative error also decays to 0? If not, come up with functions f(n) and g(n) for which this is not true. (Hint: Come up with some g(n) and f(n) satisfying g(n) = o(1) and f(n)/g(n) = Θ(1).) 1.4 Matlab warmup/Gentle linear algebra review 1. Complete G&C Chapter 2, Exercise 2. 2. Complete G&C Chapter 2, Exercise 3.
