CPSC 402 Test #1 Topics

The test will cover Chapter 1, Sections 1.1 - 1.4 and Chapter 2, Sections 2.1 - 2.5 (we haven't discussed 2.5 in class yet but we will Monday and most of the ideas have been discussed - the Secant Method is related to both the False Position Method and Newton's Method).

The main ideas are:

• Algorithms: Be able to write a solution to a problem as a precisely defined sequence of steps. Know the considerations in writing an algorithm: for example, arranging computations to avoid accumulated round off error, minimizing the number of operations (and function evaluations in root finding methods), and determining appropriate stopping conditions for any algorithm that has a loop (iterative and algorithms such as the ones for approximating an integral). Be able to count the number of operations in a given algorithm.
• Convergence - Rate of Convergence and Order of Convergence: Know the definitions of each of these. Be able to apply the definitions. Also have an intuitive understanding - be able to look at the error in output from an iterative algorithm and determine the approximate order of convergence. Know the theoretical order of convergence for the bisection method, fixed point methods, Newton's method and the Secant method. Know the conditions that guarantee convergence for fixed point methods. Be able to determine if those conditions apply for a given function. For linear convergence (and for roots with multiplicity m > 1 in Newton's method) know the asymptotic error constant and what it tells you about how fast the algorithm is converging. You should be able to use the Mean Value Theorem to prove the convergence rate is linear when g'(p) is not 0.
• Error: Be able to compute absolute and relative error. Know the components of accumulated roundoff error - introduced and propagated. Know approximations of error used in the root finding algorithms (you don't need to memorize the error approximation for false position and fixed point with linear convergence but understand the basic idea of where the formulas come from). Know the approximation of error in using a Taylor polynomial to approximate a funcion.
• Floating Point Number Systems: Know what the 4 components are and be able to determine properties of a given system (UFL, OFL, machine precision/epsilon, subnormals or gradual underflow). Understand what these mean.
• Floating Point Arithmetic: Know how it works, understand what circumstances cause error, be able to detect when error may arise, know methods of revising the algorithm to avoid error as much as possible (next item).
• Basic bag of tricks for minimizing the number of operations and for minimizing roundoff error (especially cancellation error): rationalizing (and the related idea used in the 1 - cos(x) example), Horner's method of nested evaluation of polynomials, using Taylor polynomials to approximate.
• Conditioning: Understand the basic idea of an ill-conditioned problem (see pages 37 - 38, problem #15 page 41).
• Root finding Algorithms: Bracketing (Enclosure) versus Fixed-Point, Bisection, False Position, Fixed Point, Newton's, Secant. Know (or be able to derive) the iteration formulas for these. Have a geometric understanding of them. Know the convergence orders. Understand the relationship between convergence orders and stopping conditions. Be able to compare the algorithms - for example, what are the tradeoffs in using Newton instead of Bisection? For a given root finding problem be able to find corresponding functions for fixed point schemes.
• Calculus Concepts: Taylor's Theorem, Intermediate Value Theorem, Mean Value Theorem.