MATH 128A, SUMMER 2009, REVIEW SHEET FOR MIDTERM EXAMBENJAMIN JOHNSONThe midterm exam will be held Thursday, July 16, from 8:10AM to 9:40AM in 155 Kroeber. Theexam will cover sections 1.1-1.3, 2.1-2.6, 3.1-3.4, and 4.1-4.5 of the textbook.To do well on this exam you should be able to do at least each of the following:Chapter 1. MATHEMATICAL PRELIMINARIES AND ERROR ANALYSIS1.1 Review of Calculus(1) Give a precise definition for limx→af(x) = L or limn→∞xn= x.(2) Define what it means to say that a function f is differentiable at x = a.(3) State the Mean Value Theorem.(4) Use the Extreme value theorem to find the maximum or minimum value of afunction on a closed interval.(5) State Taylor’s theorem, and use the theorem to find the nthTaylor Polynomialand remainder term for a given function f and small integer n.1.2 Round-off Errors and Computer Arithmetic(1) Convert a long real floating point in binary digit representation to a base 10decimal.(2) Given a value p and an approximation p∗, compute the relative error and absoluteerror of this approximation.(3) Define what it means to say that p∗ approximates p to t significant digits.(4) Use three digit chopping arithmetic or three-digit rounding arithmetic to performa simple computation. For example, compute 4.522using three digit chopping (orrounding) arithmetic, and without using a calculator.1.3 Algorithms and Convergence(1) Give an algorithm for some basic procedure in pseudocode. For example, writesome pseudocode to computePnk=1akgiven some real inputs a1, . . . , ak. [Youdo not have to remember the textbook’s exact notation for pseudocode, but youshould be able to specify the input, the output and the steps of the algorithm inan very clear and readable manner.](2) Define linear and exponential growth.(3) Define what it means to say that hαni∞n=1converges to α with rate of convergenceO(βn).Chapter 2. SOLUTIONS OF EQUATIONS IN ONE VARIABLE2.1 The Bisection Method(1) Use the Bisection method for two or three steps to approximate the root of afunction f between a and b.(2) State and explain the rate of convergence for the bisection method.2.2 Fixed-Point Iteration(1) Define fixed point of a function f .(2) Explain why the two problems of finding roots and finding fixed points are equallydifficult.Date: July 16, 2008.12 BENJAMIN JOHNSON(3) Give an algorithm in pseudocode to implement fixed-pont iteration.(4) Carry out the first few steps of fixed point iteration for a given function g and agiven initial value p0.2.3 Newton’s Method(1) Explain how Newton’s method works.(2) Give precise conditions under which Newton’s method converges (i.e. State the-orem 2.5 on p.66 of the textbook)(3) Carry out a few steps of Newton’s method for a given function f and initial valuep0.(4) Explain how the Secant Method works.(5) Carry out the first few steps of the secant method for a given function f andinitial values p0and p1.2.4 Error Analysis for Iterative Methods(1) Define what it means to say that hpni∞n=0converges to α with asymptotic errorconstant λ.(2) Define what it means to say that a sequence is linearly convergent or quadraticallyconvergent.(3) Define what it means to say that f has a zero of multiplicity m.2.5 Accelerating Convergence(1) Define the forward difference operator ∆ and compute ∆kpnfor a given smallinteger k and a given sequence hpni.(2) Carry out the first few steps of Aitken’s ∆2method given a sequence hpni∞n=0.(3) Carry out the first few steps of Steffensen’s method for a given function g andinitial value p0.2.6 Zeros of Polynomials and Muller’s Method(1) State the Fundamental Theorem of Algebra(2) Use Horner’s method to evaluate a given polynomial P at a given value a.(3) Explain how M¨uller’s method works using graphs and pictures. (You do not needto memorize the algorithm).Chapter 3. INTERPOLATION AND POLYNOMIAL APPROXIMATION3.1 Interpolation and the Lagrange Polynonial(1) Give the defining equation for the Lagrange polynomial.(2) Define the monomial Ln,k.(3) Given a function f and A set of points x0, . . . , xnwrite and expression for theLagrange interpolating polynomial.(4) Explain what Neville’s method does and how it works.3.2 Divided Differences(1) Write an expression for the Lagrange polynomial in the form that uses divideddifferences.(2) Give the recursive definition for f [xi, . . . , xi+k].(3) State the Newton forward-difference formula.3.3 Hermite Interpolation(1) State the main properties of the Hermite interpolating polynomial.(2) Write a general expression for the Hermite Polynomial.3.4 Cubic Spline Interpolation(1) Define what it means for S to be a cubic spline interpolant for a function f , givensome interval [a, b] and a set of nodes a = x0< x1, . . . , < xn= b.(2) Explain the difference between a natural cubic spline and a clamped cubic spline.MATH 128A, SUMMER 2009, REVIEW SHEET FOR MIDTERM EXAM 3(3) Compute either a natural or clamped cubic spline interpolant for a function givenonly 2 points.Chapter 4. NUMERICAL DIFFERENTIATION AND INTEGRATION4.1 Numerical Differentiation(1) State the most basic formula for numerically approximating a derivative. [Hint:this same basic formula can be considered as either a forward-difference formula,or a backward-difference formula](2) State the two three-point formulas for approximating the derivative and explainthe circumstances under which each would be used.4.2 Richardson’s Extrapolation(1) Explain the basic idea behind Richardson’s extrapolation.(2) Given an approximation formula N (h) whose approximation error can be ex-pressed as a specific polynomial in h, perform the algebra required to obtain abetter approximation formula N1(h). [For example, if |M − N(h)| =Pnk=13 · hk,use algebra to find a new formula N1(h) such that |M − N1(h)| is O(h2).]4.3 Elements of Numerical Integration(1) State the most basic formula for numerically approximating an integral. [Hint:The technique of using this type of formula is called numerical quadrature](2) State the Trapezoid Rule for approximating a definite integral.(3) State Simpson’s Rule for approximating a definite integral.(4) Explain the difference between an open Newton-Cotes formula and a closed Newton-Cotes formula.(5) State the Midpoint Rule for approximating a definite integral.4.4 Composite Numerical Integration(1) Explain why n has to be even in order to apply the composite Simpson’s Rule.(2) State the composite Trapezoidal rule, (including the error