Numerical Methods

Slides Change History

9/15/95:

Chapter 5 added.

9/28/95:

Textual: changed \cdots to \ldots according to Lamport, p. 42.

9/29/95:

Chapter 6 added.

10/18/95:

Finished revamping the HTML stuff.
Fixed two typos in Linear Systems, p. 17 (from Katalin Balla).

10/24/95:

Changed gray fill-in for graphs to color.
Changed Runge picture and added another, p. 60 and 62.

10/25/95:

Changed some slide titles, pp. 57-62.

11/1/95:

Fixed a typo on page 45 in Nonlinear Equations.
Added a graph to page 57 in Interpolation and Approximation.
Chapter 7 added.

11/5/95:

Added text to graph page 149 in Approximation by Splines.

11/20/95:

Chapter 8 added.

11/20/95:

Updated first slide with my info.

12/14/95:

Change all over: in notation of C^k[a,b], etc.

12/17/95:

Removed "minimize \mb{\prod}" point, as per Prof. Ivo Babuska.

1/3/96:

Chapter 10 added.
Other small things

1/16/96:

Added the HTML package to the FTP site, and changed the README file and index.html .

1/28/96:

Added book info to first slide.
Copyright 1995 -> 1996.

1/31/96:

Base Representations: pp. 3 and 4, Ward Cheney caught two missing "+"'s, and also added "-->rational<-- base"

3/12/96:

Reduced the GIF image sizes by 20%, which unfortunately this double the file sizes.
In Taylor ln(x) example: k > 1 --> k \ge 1.

3/18/96:

Added 2 VGs of cos (0.1) examples to Taylor Series.
Added steps to Taylor series procedure.
In second form of Taylor, xi depends on h, not x.
Added some words in "O" notation definition.
Added the constant C for the Taylor series truncation error.
I had the wrong sign for the comparison of two adjacent terms in the Alternating series theorem.
Added some words after the Alternating series theorem.

3/19/96:

Sum for Taylor of ln(x) should start from k=1, not k=0.
In the Alternating Series theorem, cleaned up the indices and limits.

3/20/96:

Posting to all of this file and continuous updating.

4/2/96:

At begining of Nonlinear Systems, clear definition of f(x) = 0, and all equations in that form
Mention of multiple roots
Cleared up the wording of \epsilon being the error and \tau being the tolerance, and their relationship one to the other
In a lot of places, first guess: x_1 -> x_0
Using r for the root, rather than x in many places
Newton's Method: that \ell(x) is the tangent to f(x_0)
Secant Method: use of "\approx" for derivative
In summary: C^1 -> C^2
In summary: secant also requires neighborhood, somewhat

4/17/96:

Slight textual changes in Interpolation chapter.

5/1/96:

(all these are regarding Numerical Quadrature)
slight textual changes
a lot of "intervals" -> "subintervals"
switched order of first two slides
specified 3 methods: L, U, (L + U) / 2
"error" -> "error tolerance" in a few places
added point regarding need for extrema calculations for first three methods, and not for CTR
moved Dirichlet example down one line
lower limit of CTR, uniform mesh summation: 0 -> 1
rearranged first 2 slides of CSR
CTR on two intervals, the error is of power 3, not 2
CSR function evaluations: 2n+1 -> n+1
Integration Introspection rewording
summary table changed slightly
mention existence of adaptive quadrature methods

5/2/96:

Fixed some resizing issues, making the GIF colors much better and truer to the original PostScript. The files sizes are much smaller as well.

5/6/96:

In Gaussian Quadrature, I pointed out that the fact that the x_i are the zeros of q(x) is only needed for the last step.

5/21/96:

In Linear Systems, for the work on A, I added "(for choice of pivot row)" to the "n ratios" for clarity.

6/4/96:

In Splines, at the end of Quadratic Splines, I point out that 1 z_i need be chosen, not necessarily z_0, and then on the last slides with the graph example, I specify that I chose z_0 = 0.
I clarified (I hope!) the necessary sparse linear systems needed to be solved for the various splines.
Towards the end of Splines, I used the name Serpentine Curve.

6/6/96:

In the chapter of Base Representations, I added some snippets of facts, like 1/3 is indeed rational, and that a "bit" is a binary digit. Also that the base number system for a computer is 2. (Sorry I had to be so explicit, but you know some students, ....)

6/11/96:

At the beginning of ODEs, I point out that this is somewhat the opposite of numerical differentiation.
ODEs: in the three figures, I added $t$ and $x(t)$ to the x and y labels, resp.
In the Taylor Method Numerical Example, I point out that an n = 100 was used, and that the "actual" solution is just for 5 significant digits only.
Cleared up the number of new evaluations required, for the various ODE methods, on a number of slides.

6/18/96:

(all in the Least Squares Method chapter)
the estimates for a and b are now \hat{a} and \hat{b} instead of a_e and b_e, as to not confuse "_e_stimate" and "_e_rror"
removed the absolute value signs for the definition of the error e_k, plus appropriate changes for this
if y's dependence on a and b is linear, then \phi's dependence is quadratic, not linear
point out for the linear data, that the coefficient matrix is made up of the cross-products of the coefficients of a and b
in the definition of the basis functions g_j, "equations" -> "functions"
plus miscellaneous wording

6/24/96:

In the Least Squares Method chapter, in the definition of the the variance of polynomial regression, I use the subscript k for the points, instead of i, for consistency

8/6/96:

Updated the README file, primarily with the 14-week semester plan

3/1/98:

changed the background color for easier viewing

3/15/98:

changed/corrected the graphic example of the Newton interation for nonlinear equations

3/22/98:

Taylor Series, Examples, added explanation of how to determine range (of x) for series convergence

3/23/98:

Taylor Series, towards the end, added example of second form of Taylor's Theorem, including expansion, range of convergence and truncation error estimates by Taylor, and AST

3/26/98:

at beginning of Interpolation, cleared up the role of splines
secant method also requires good initial estimates
secant method requires only one function evaluation per iteration, vs. Newton's two

4/5/98:

added minor wordings and explanations to three places

4/19/98:

in Gaussian forward elimination, the pivot row (i) proceeds until n - 1, not n

4/20/98:

Linear Systems: mentioned that for multiple RHSs, if they are known from the start, then process them simultaneously; if not, LU decomposition, etc.

5/10/98:

Splines: when querying for uniqueness, specified that this is only for no additional knots

5/17/98:

Ordinary Differential Equations: Higher Order Taylor Methods: regarding the numerical disadvantage, this is both computationally and accuracy-wise

3/14/99:

Taylor Series: cos (0.1) table example, cleared up definition of "n terms," and a mistake in the error

3/21/99:

Taylor Series: added elaboration to xi range estimation
Taylor Series: stressed that in the ratio test and AST, we are not looking at xi and the error term

4/23/99:

redid a few slides on Taylor range of convergence analysis
LSD-addition: example requires 6, not 5, significant decimal digits
stated the obvious, that the bisection method requires f to be C^0
Nonlinear Equations: mention a bit about error in f(x), not just in x, ..., stopping criteria
stressed that the bisection method does _not_ converge linearly, but similar ...
added a bit about stopping criteria in Newton's method, that often it is in f(x) and not x, as that might be all we have, and that there are in general: absolute/relative, size/change, x or f(x), or combinations
hinted that 1.618... is the golden ratio
mentioned that the techniques of nonlinear equations are often combined, with possibilities for restarting due to divergence or cycles
added a note comparing to the English term "interpolation" and contrasting with "extrapolation"

5/3/99:

for error a function of the beta deriv of f, it is zero for all polynomials up to (and including) degree (beta - 1)

6/6/99:

better explained the graphs of the ODE Taylor methods
ODEs: point out that the units, e.g., for time/distance/speed, are consistent
for Euler method, point out that slopes match up at points, only if f is not a function of x
least squares: if error is defined as a distance to the best line, this is a much harder problem

6/17/99:

added (preliminarily) a new chapter on simulation

7/1/99:

fixed a whole bunch of typos in the new chapter on simulation

3/8/01:

added examples and explanations all over

5/14/01:

in Gaussian Quadrature, pointed out that even though there is zero error for polynomials up to degree 2n+1, in general the interpolation polynomial with be different for degree > n

7/23/01:

the last slide of the first chapter had a mathematical error ( :-( )

3/4/02:

added verbiage to Taylor expansion of polynomial
added explanation of "big-O" notation
added explanation of to LSD Addition slide

2/5/03:

added Taylor expansion picture of cos
added example of second form of Taylor expansion
mentioned what base 16 is
more "big O" notation explanation
use graphing tool to seed root-finding techniques
clarified that Newton method failures can happen at any x_n and not just at x₀
pointed out that a loop-d-loop in an interative method can happen over more than just 2 points
reiterating that Newton's iterative method requires 2 function evaluations per iteration
added examples of max interpolation error calculations
compared adding points for L or U, vs. CTR, for non-monotonic functions ... monotonic improvement for L and U but not for CTR (necessarily)
noted the problems with using current hundredths of seconds, as a random number generator

2/19/03:

better example of difference of Taylor error estimate, using the error term, vs. AST

2/23/03:

added some numerical figures to LSD example of x - sin(x)

2/24/03:

explanation what is needed for Taylor series, and what for specific Taylor approximations

3/4/03:

explanation about the constant, in the convergence theorem of Newton's method

3/4/03:

stressed in many places that estimates of error is actually estimates of max error
lots of small textual stuff

4/2/03:

added slide on Scaled Partial Pivoting

2/23/04:

added Tsur-El Ram-Cohen's question: why bother with Taylor Series of 1/(1-x) which is so simple to calculate as is

3/16/04:

cleared up wording of bisection method rate vs. linear convergence

3/22/04:

added to notes at the end of Chebyshev Interpolation
minor changes in numerical differentiation

4/20/04:

added that the direction of the AST error is also known, for a specific n

5/4/04:

added a slide explaining the new angle of of minimizing the error, just after the Composite Simpson's Rule

5/6/04:

belatedly updated the largest Mersenne prime info

5/11/04:

rewrote slide on Scaled Partial Pivoting

6/17/04:

cleared up a bit of the polynomial regression presentation

6/17/04:

added the a_ij notation for sparse matrices

Numerical Methods Slides Change History

Numerical Methods

Slides Change History