CS323-Fall 2019. WHAT TO READ BEFORE CLASS
The following list shows what I intend to cover during each class.
After class I will revise the entry to record what was a c t u
a l l y covered. This page will thus become a lecture diary.
If you try to read about this material in advance (from a text or my
handouts on the topic), it should make it easier to follow the class.
This could also reduce note-taking e.g., if you just
annotate the relevant course notes during the class.
1. Sept. 4, 2019 : Introduction to the course. Then described the
k-digit, normalized floating point number system under both the
"chopping" convention and the "rounding" convention. Discussed some
aspects of algebra in this system, e.g. addition is not
associative. Showed that the density of numbers in this system
decreases as the distance from the origin increases...
2a. Sept. 9, 2019: CANCELLED.
2b. Sept. 11, 2019: ...(continued); absolute and relative errors
under both rounding and chopping conventions and the fact that worst-possible
relative error under chopping is twice as large as the worst-case relative
error under rounding. Finally, began the first real topic of the course
"Solution of Non-linear Equations" [given f, a continuous function on an
interval [a,b], find w in (a,b): f(w)=0], and described the first method
used to attack it - the Bisection Method - shown to always "work" (once
begun correctly, it produces approximatins converging to a root). You
should download the course notes for this topic ["Notes on Nonlinear
equations" (6 pages)].
3. Sept. 16, 2019: Finish bisection and then describe the
regula-falsi root-finding alg and some of its properties. Describe
Newton's (root-finding) alg. and mentioned the "secant alg.", and how
it differs from Newton's alg... gave examples.
We will study these methods (and others) - along with some of their properties
- in more detail in the upcoming classes.
4. Sept 18, 2019: ... continued. Did examples showing fast convergence of Newton
and introduced the details of the secant algorithm, with an
example. Began the topic of "fixed points" of continuous functions and
mentioned a method (fixed point iteration) which helps understand
Newton's method.
5. Sept. 23, 2019: Showed how a given root problem for a continuous fn f
["get w in R: f(w)=0)"] there is a fixed-point problem for a continuous fn g
["get w in R: g(w)=w"], and they have the same solution x=w. Therefore roots
of f can be found by finding fixed points of g. WHY MENTION IT? Because of
the nice method for finding fixed points: FIXED POINT ITERATION. We described
it and got some intuitions of what it does and when it would seem to succeed.
We then proved the Contraction Mapping Principle: "IF w is a fixed point of
a function g and g is is a contraction on an interval I=(w-a,w+a), then
fixed-point-iteration converges to w=g(w) as long as it is started at P_0 in I."
There were some corollaries.
6. Sept. 25, 2019: Using the contraction mapping principle we
showed that in Newtons' method, if the initial point P_0 is close enough to
w (a non-tangency root of f), then the iterations will converge to w. Next,
began the study of convergence rates in fixed point iteration (FPI). The
method is based on the application of Taylors' theorem to the function
g whose fixed points we are seeking via FPI. The crucial statement is: "If k is
the least integer j > 0 such that the j(th) derivative of g at x=w is NOT 0,
then the size of the error (if we do one more FPI step), divided by the k^{th}
POWER OF the size of the error if we stop now, converges to a constant. In other
words the next FPI error is ultimately a factor of the k^{th} power of the
current (small) error!!! Thus at a non-tangency root, Newton's method - if started
close enough - has quadratic convergence, or better!
7. Sept. 30, 2019: Continuing, we mentioned another FPI method -
the "chord method". Wanting to do Newton's FPI (but not knowing f'(x)),
we replace this term in the Newton iteration by a fixed slope m. The
chord method is then FPI on the function g(x)=x-f(x)/m; i.e., P_{n+1}
= P_{n}-f(P_n)/m. If started close enough to the root and if the sign
of m agrees with that of f at w (the root of f), then it will converge
to w at a linear rate. There is one exception: if [miraculously] m=f'(w),
the convergence will be quadratic or better. We next studied the
convergence of the secant method, not directly amenable to the Taylor-polynomial
approach we had been applying. We went through some steps (leaving out
several crucial details) that show that the size of the error at step k+1
is l.e.q. a constant times the product of the sizes of the errors at
step k and at step k-1. We then (just) stated that this relation can be
shown to imply |e_{n+1}| l.e.q. K|e_n|^{.5(1+sqrt(5))}
(the exponent is about 1.618) [its convergence is much faster than
linear but much slower that quadratic]. And FINALLY we discussed the
"accelleration of convergence of linearly converging sequences, describing
Aitkins method and Steffanson's method.
8. Oct. 2, 2019: Began study of systems of linear equations
(reviewed vectors, matrices, some linear algebra). Began discussing the
Gaussian Elimination and Backsolving algorithm and showed - by a small example of
[ONLY] two equations in two unknowns - how the process is prone to large
roundoff errors when performed in fixed precision. In the example -
solved using 4 digit arithmetic with rounding - the computed solution had errors
of about 67%!!
9. Oct. 9, 2019: Used previous example to motivate the "partial
pivoting strategy" in Gaussian elimination; applied to the previous
example it generated the exact solution in 4-digit arithmetic! However
a second example with 2 equations in two unknowns - solved in 4-digit arithmetic and
using partial pivoting - produced a solution whose errors were 50%, compared to the
exact solution, and this motivated the "scaled-partial-pivoting" strategy. Finally
began to study the "computational cost" of solving a system of n eqns. via Gaussian
elimination by counting the number of multiplication and division steps used. We
saw that (2n^3+3n^2-5n)/6 * or / steps are used in reducing the augmented coefficient
matrix to upper-triangular form.
10. Oct. 14, 2019: Repeated the computational cost of solving Ax=b with n eqns
and unknowns using Gauss-Jordan elimination and got (n^3-n)/2 +n^2 * or / ops,
about 50% MORE than via Gaussian elim. Argued that Gauss-Jordan is still useful because
it easily adapts to produce A-inverse (using approximately n^3 * or / steps).
Began the topic of the LU factorization of an n by n coefficient matrix.
11. Oct.16, 2019: ...continued. Showed that once we know A as the product
of LU (L lower tringular, U, [unit]-upper triangular, we can solve Ax=b by first
solving Ly=b (for y), then solving Ux=y (for x), and the cost is just n^2 OPS.
Alas there are invertible n by n coefficient matrices that cannot be expressed as
a product of L (unit-lower-) and U (upper-) triangular matrices, so we began to study
the LUP factorization of A (an invertible n by n coefficient matrix)...
12. Oct.21, 2019: ...(continued). Began topic of the iterated
improvement algorithm in solving linear systems.
13a. Oct. 23 Class cancelled
13b. Oct. 30, 2019: Finished iterative improvement, with an example . Began topic
of iterative methods for solving linear systems. Set up framework for the multivariate
analogue of fixed point iteration for linear systems.
14. Nov. 4, 2019: Began Jacobi's method of F.P.I. to approximate the solution of Ax=b.
Went through an illustrative example and sketched some aspects of the
convergence theorem (if the coefficient matrix A is diagonally dominant,
the Jacobi iterations will converge to w = (A-inverse)*b.
15. Nov. 6, 2019: Reiterated some ideas in the convergence proof for Jacobi FPI.
Then mentioned what the Gauss-Seidel FPI algorithm is, and gave an illustration
using a 2 by 2 example. In this example, the Gauss-Seidel iterations appeared to converge
much faster than the Jacobi iterations. After a pause, we began the
topic of Polynomial Approximation (of functions), reviewing polynomials and
some of their properties, two "key" ones being (a) the fundamental
Theorem of algebra (which implies that if a degree n polynomial has n+1
distinct real roots, then it must be identically zero) and (b) the Weierstrass uniform
approximation theorem ("if f is a continuous function on an interval [a,b] and
a constant c>0 is given, there is an integer N>0 so that for n>N, we can find a
polynomial P_n(x) for which |f(x)-P_n(x)| < c, all x in [a,b]. Finally reviewed
the Taylor polynomial approximation for a function f, and its error at a given
point.
16. Nov. 11, 2019: Began topic of interpolation, in which a continuous function f
is given, along with n+1 distinct "collocation points" u_0,...u_n. The goal
is to find I_n(x) - a polynomial of degree at most n which "agrees with" f at each of
the u_i. We proved that there is a unique such polynomial and in doing so, derived
Lagrange's form of the interpolating polynomial for the given function f, based on the
given collocation points u_0,...u_n. Next, we discussed the error theorem
for I_n, with an example.
17. Nov.13, 2019: Finally, we derived "Newton's form" of I_n (motivated by the
fact that Lagrange's form of the polynomial entails an overly-costly evaluation
of it at a given x). A good feature of Newton's form is that once it has been obtained,
you can evalutate it at a given x using [only] n * or / operations and n + or - ops
(contrast this with the quadratic cost to evaluate Lagrange's form at x)...
18. Nov. 18, 2019: ...In fact of the three ways to represent a degree n interpolating
polynomial, Newtons form is the most "economical", based on the cost to obtain the polynomial
and on the cost to evaluate it at a given x. Discussed Runge's phenomenon, highlighting
the fact that adding collocation points and increasing the degree of the
an interpolating approximation does NOT necessarily make the approximation better
[see handout on this]. Introduced the "minimax" distance between functions on
the interval [a,b] whereby d(f,g) = max(|f(x)-g(x)|), the max over all x in [a,b].
We seek M_n(x), the degree-at-most-n polynomial that is closest to f in this distance.
After showing several examples we described the theorem of Tchebycheff: "Given a
continuous function f on [a,b] and a degree = n: 1) there is a UNIQUE degree = n
polynomial having minimum distance from f (so M_n exists and is unique);
2) M_n interpolates f, so there are points a < u_o < u_1 < ... < u_n < b
and f(u_i)=M_n(u_i), i=0,1,...n; 3) M_n "equioscillates"; i.e., there are n+2 oscillation
points y_0 < y_1 ... < y_{n+1} and f(y_i)-M_n(y_i) = -[f(y_(i+1))-M_n(y_(i+1))]. Did a
few other concrete examples of finding minimax polynomial approximations.
19. Nov. 20, 2019: Summarized preceeding facts about minimax
approximation and began Tchebycheff interpolation and the Tchebycheff
points. Mentioned the existence of the Remez algorithm (no details) that
converges to the minimax approximation M_n for a given function on
[a,b], and finished by stating Powells' theorem [d_{infty}(f,C_n) leq
K*log(n)/n^2] on the rate of convergence of Tchebycheff
interpolation. Handed out "Runge's phenomenon" (available on course
pages) Finally, we began the topic of least-squares polynomial
approximation along with the idea of a BASIS for the degree-at-most n
polynomials...
20. Nov. 25, 2019: ... e.g., the MONOMIAL (or usual) basis:
1,x,x^2,... Discussed the NORMAL eqns whose solution gives the
coefficients of P_n, the degree-at-most-n (continuous) least-squares polynomial
approximation to f on [a,b], with a detailed example
(degree=1). Pointed out that the (degree l.e.q. n) continuous LSQ
approximation problem on [0,1] entails solving a system of n+1 linear
equations where the coefficient matrix is the n+1 by n+1 Hilbert
matrix (!) - a fact that motivates the need for a different basis for
the degree n polynomials. Indtroduced the LEGENDRE FUNCTIONS on [-1,1]
and some easily checked facts about them.