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.