MATH 4073 - Numerical Analysis I, Section 001 - Fall 2006
TR 9:00 - 10:15 a.m., 116 PHSC
Instructor:
Nikola Petrov, 802 PHSC, (405)325-4316, npetrov AT math.ou.edu.
Office Hours:
Tue 11 a.m.-noon, Wed 1:30-2:30 p.m., or by appointment.
Prerequisites:
MATH 3113 (Intro to ODEs) or 3413 (Physical Math I).
Text:
R. L. Burden, J. D. Faires.
Numerical Analysis.
8th ed, Brooks/Cole, 2004, ISBN 0-534-39200-8.
The course will cover the major portions of Chapters 1-5.
The final exam will be from 8 to 10 a.m.
on Wednesday, December 13.
Homework
(Solutions are posted after the due date in the Chemistry-Mathematics
Library, 207 PHSC)
-
Homework 1, due: Thu, Aug 31.
-
Homework 2, due Thu, Sep 7.
-
Homework 3 (to be posted later),
due Thu, Sep 21.
Codes needed for Homework 3 (and codes to help you program):
-
Homework 4, due Thu, Sep 28.
-
Homework 5, due Thu, Oct 5.
-
The MATLAB code
muller.m
needed for Homework 5.
-
Homework 6, due Thu, Oct 19.
-
Homework 7, due Thu, Oct 26.
-
Homework 8, due Thu, Nov 2.
-
Homework 9, due Thu, Nov 9,
in class!
The MATLAB codes
comp_trap.m
and
comp_simp.m
needed for Homework 9.
-
Homework 10, due Tue, Nov 28
in class!
-
Homework 11, due Thu, Dec 7
in class!
MATLAB codes
euler.m
and
taylor2.m
from the book
Numerical Methods Using MATLAB
by J.H. Mathews and K. D. Fink
(4th edition, Pearson Prentice Hall, 2004);
taylor3.m
codes
rhs_erf.m
and
twoders.m,
and
instructions
how to run these codes.
Content of the lectures:
-
Lecture 1 (Tue, Aug 22):
Introduction.
Review of calculus:
notations, limit and continuity of a function,
limit of a sequence, intermediate value theorem,
derivative of a function,
continuity and differentiability,
Rolle's theorem, mean value theorem,
extreme value theorem
(Sec. 1.1).
-
Lecture 2 (Thu, Aug 24):
Review of calculus (cont.):
Riemann sums and integral,
fundamental theorem of calculus,
mean value theorem for integrals, Taylor's theorem,
examples of Taylor series (Sec. 1.1).
Computer arithmetic: binary, decimal and hexadecimal systems,
bits and bytes, 1985 IEEE standard for a long real number,
working with a finite number of digits - rounding and chopping
(Sec. 1.2).
-
Lecture 3 (Tue, Aug 29):
Computer arithmetic (cont.):
Roundoff errors: absolute and relative errors,
floating-point operations,
examples of roundoff errors - computing a sum,
solving a quadratic equation, nested way of computing polynomials
(Sec. 1.2).
Algorithms and convergence:
pseudocode, loops, conditional execution, examples,
truncation error of an alternating series
whose terms decrease in absolute value
(Sec. 1.3).
-
Lecture 4 (Thu, Aug 31):
Algorithms and convergence (cont.):
stable, unstable and conditionally stable
algorithms; linear and exponential growth of the error,
error in a numerical solution of a recurrence relation,
rate of convergence, "big O" notation, examples
(Sec. 1.3).
The bisection method:
general idea, algorithm
(Sec. 2.1).
-
Lecture 5 (Tue, Sep 5):
The bisection method:
a MATLAB code
bisection.m
and instructions
how to run it,
the output
from running it,
stopping criteria, rate of convergence
(Sec. 2.1).
Fixed-point iteration:
fixed points,
relation between finding a zero and finding a fixed point,
existence and uniqueness of fixed points
(formulation and graphical interpretation of Theorem 2.2),
proof of part (a) of the theorem
(Sec. 2.2).
-
Lecture 6 (Thu, Sep 7):
Fixed-point iteration (cont.):
existence and uniqueness of fixed points (Theorem 2.2),
proof of part (b) of the theorem;
iterating a function graphically,
attracting and repelling fixed points;
Fixed Point Theorem (Theorem 2.3), proof,
Corollary 2.4 (Math majors, please read the proof)
(Sec. 2.2).
Newton's method:
basic idea, Newton's method as an iterative procedure
(Sec. 2.3).
-
Lecture 7 (Tue, Sep 12):
Newton's method (cont.):
geometric representation of Newton's method,
examples of failure of Newton's method,
problems with Newton's method
(one needs to compute derivatives,
one needs a good choice of initial point p0,
the root is not necessarily bracketed);
secant method:
does not involve computing derivatives,
geometric representation,
problems with the secant method
(one needs a good choice of initial points
p0 and p1,
the root is not necessarily bracketed);
method of false position (Regula Falsi):
geometric representation,
in this method the root is bracketed between
pn and
pn-1 at each step
(Sec. 2.3).
Error analysis of iterative methods:
order of convergence α
and asymptotic error constant λ
of a convergent sequence (and of an iterative method),
linear and quadratic convergence,
illustration of the speed of convergence
in the linearly and in the quadratically converging cases
(Sec. 2.4).
-
Lecture 8 (Thu, Sep 14):
Error analysis of iterative methods (cont.):
theorem about linear convergence
of an iterative method
pn
= g(pn-1)
with g'(p)≠0
(Theorem 2.7, with proof),
theorem about quadratic convergence
of an iterative method
pn
= g(pn-1)
with g'(p)=0
(Theorem 2.8, with sketch of proof);
constructing a quadratically convergent
iterative procedure from a zero-finding problem
(and obtaining the Newton's method as a result!);
multiplicity of a zero of a function
(Sec. 2.4).
-
Lecture 9 (Tue, Sep 19):
Error analysis of iterative methods (cont.):
relations between the multiplicity
and the number of zero derivatives,
modification of Newton method
to deal with multiple zeros
(Sec. 2.4).
Accelerating convergence:
Aitken's method for accelerating convergence,
forward differences
(Sec. 2.5).
-
Lecture 10 (Thu, Sep 21):
Accelerating convergence (cont.):
Steffensen's method for accelerating convergence,
order of convergence of Steffensen's modification
of a fixed-point iteration.
(Sec. 2.5).
Zeros of polynomials and Muller's method:
fundamental theorem of algebra, corollaries,
Horner's method (synthetic division),
computing P(pn-1)
and P'(pn-1)
in Newton's method for polynomials
by using synthetic division,
method of deflation for finding zeros of polynomials
(Sec. 2.6).
-
Lecture 11 (Tue, Sep 26):
Zeros of polynomials and Muller's method (cont.):
Muller's method for finding zeros of polynomials.
Sensitivity of zeros of polynomials - Wilkinson's example
(Sec. 2.6).
Introduction to interpolation and approximation:
need of approximating data,
differnent approaches - interpolation and approximation.
-
Lecture 12 (Thu, Sep 28):
Interpolation and Lagrange polynomial:
idea, explicit expression, error bound in Lagrange interpolation,
example of a local linear interpolation
(Sec. 3.1).
-
Lecture 13 (Tue, Oct 3):
Interpolation and Lagrange polynomial (cont.):
Neville's iterated interpolation method
(Sec. 3.1).
Newton's divided differences:
divided-differences way of writing an interpolating polynomial
(Sec. 3.2).
-
Lecture 14 (Thu, Oct 5):
Newton's divided differences (cont.):
forward and backward differences,
"s choose k" notation,
forward-differences and backward-differences ways
of writing an interpolating polynomial
(Sec. 3.2).
-
Lecture 15 (Tue, Oct 10):
Hour Exam 1.
-
Lecture 16 (Thu, Oct 12):
Cubic spline interpolation:
general idea, cubic spline interpolant S(x)
and its restrictions Sj(x)
to [xj,xj+1],
compatibility conditions on the functions
Sj(x)
at the internal node points
xj+1 (j=0,1,...,n-2),
physical meaning and mathematical formulation
of the boundary conditions,
reformulating the conditions on
Sj(x)
in terms of the coefficients
aj,
bj,
cj,
dj;
deriving a linear system for
bj
and
cj
from the conditions on
Sj(x)
at the internal points
(Sec. 3.4).
-
Lecture 17 (Tue, Oct 17):
Cubic spline interpolation (cont.):
deriving a linear system for
cj
from the conditions on
Sj(x)
at the internal points
and the free (natural) boundary conditions
(read the case of clamped boundary conditions
from the textbook);
theoretical error bounds,
remarks about the practical importance
of cubic splines
(Sec. 3.4).
Numerical differentiation:
idea, forward- and backward-difference formulae
for f'(x0),
3-point formulae for f'(x0)
(Sec. 4.1).
-
Lecture 18 (Thu, Oct 19):
Numerical differentiation (cont.):
derivation of the 3-point formulae for f'(x0),
error terms in the different formulae for
f'(x0),
derivation of a formula for f''(x0)
and the error term
(Sec. 4.1).
Richardson extrapolation:
idea and derivation
(Sec. 4.2).
-
Lecture 19 (Tue, Oct 24):
Numerical integration:
goal, examples, ideas,
trapezoidal formula and Simpson's formula
for numerical quadrature
(Sec. 4.3).
-
Lecture 20 (Thu, Oct 26):
Numerical integration (cont.):
an example of applying the trapezoidal and the Simpson's formulae
(integrating sin(x) from 0 to Pi/2);
open and closed Newton-Cotes methods,
theorem about the errors of Newton-Cotes methods
(open and closed),
an example of an open Newton-Cotes method
- the midpoint rule
(Sec. 4.3).
-
Lecture 21 (Tue, Oct 31):
Composite numerical integration:
composite trapezoidal, Simpson's and midpoint rules,
error bounds.
(Sec. 4.4).
Practical issues in numerical integration:
infinite limits of integration, singularities in the integrand
(see the examples in Sec. 4.9).
Romberg integration:
idea - composite trapezoidal rule
for different stepsizes followed by
Richardson's extrapolation
(Sec. 4.5).
-
Lecture 22 (Thu, Nov 2):
Romberg integration (cont.):
an example
(Sec. 4.5).
Gaussian quadrature:
idea and a simple example
(Sec. 4.7).
-
Lecture 23 (Tue, Nov 7):
Gaussian quadrature
- theoretical foundations:
linear space (vector space),
linear space of polynomials
of degree not exceeding n,
inner product linear space,
inner product in a space of polynomials,
weight function w, examples
- see my
handout on Gaussian quadrature.
-
Lecture 24 (Thu, Nov 9):
Gaussian quadrature (cont.):
using orthogonal polynomials for numerical integration
- Theorem 1 in the
handout on Gaussian quadrature.
-
Lecture 25 (Tue, Nov 14):
Hour exam 2.
-
Lecture 26 (Thu, Nov 16):
Gaussian quadrature (cont.):
an example.
Elementary theory of initial-value problems:
initial-value problems (IVPs) for ordinary
differential equations (ODEs)
- definition, examples
(Sec. 5.1).
-
Lecture 27 (Tue, Nov 21):
Elementary theory of initial-value problems (cont.):
Lipschitz condition and Lipschitz constant,
examples of Lipschitz and non-Lipschitz functions,
bounded derivative implies Lipschitz,
existence and uniqueness of solutions
of an IVP for a first-order ODE,
well-posedness of an an IVP for a first-order ODE,
examples of nonexistence and nonuniqueness of solutions of IVPs,
equation of formation of a droplet of a liquid
in saturated vapor
(Sec. 5.1).
Euler's method:
idea, derivation
(Sec. 5.2).
-
Lecture 28 (Tue, Nov 28):
Euler's method (cont.):
implementation, error analysis
(without derivation)
(Sec. 5.2).
-
Lecture 29 (Thu, Nov 30):
Classes cancelled.
-
Lecture 30 (Tue, Dec 5):
Higher-order Taylor methods:
finding the Taylor series of the exact solution
y(t)
of the IVP
y'=f(t,y(t)),
y(a)=α,
an example;
idea of higher-order Taylor methods,
example - derivation of a Taylor method of order 3,
remarks about implementation
(Sec. 5.3).
-
Lecture 31 (Thu, Dec 7):
Runge-Kutta methods:
idea, preparation (Taylor Theorem
for a function of two variables),
derivation of the midpoint Runge-Kutta method
(Sec. 5.4).
Grading: Your grade will be determined by your performance on
the following coursework:
- Two midterm exams, one hour each
(each midterm contributes 20% to your overall grade).
- Homework (30% of your overall grade).
- Comprehensive final exam (30% of your overall grade).
Course Objectives:
This course is intended to be a mathematical
introduction to the theory and practical use
of certain basic numerical methods
that often arise in applications.
While the emphasis of the course will be placed solidly on applications,
we will discuss some of the mathematical theory behind the methods we study.
Some theoretical understanding is critical to the proper practice
of numerical analysis because no numerical method works 100% of the time.
Thus when a method fails, the theory behind the method can often illuminate
what went wrong and perhaps give insights into alternative approaches
that may work better for the given problem.
Course Content:
-
Review of pertinent concepts from calculus.
-
Computer arithmetic and round-off errors.
-
Algorithms and convergence.
-
Solutions of equations in one variable
(bisection method, Newton's method, error analysis).
-
Interpolation and polynomial approximation
(Lagrange polynomials, cubic splines).
-
Numerical differentiation and integration
(Richardson's extrapolation,
Newton-Cotes formulae for integration,
Romberg integration, Gaussian quadrature).
-
Initial-value problems for ordinary differential equations
(Euler's method, higher-order Taylor methods, Runge-Kutta methods).
Attendance:
You are required to attend class on those days when an
examination is being given; attendance during other class periods is also
strongly encouraged.
You are fully responsible for the
material covered in each class, whether or not you attend.
Make-ups for missed exams will be given only if
there is a compelling reason for the absence,
which I know about beforehand
and can document independently of your testimony
(for example, via a note or phone call from a
doctor, parent, or clergyman).
Homework: Homework assignments will be set
regularly throughout the semester.
Each homework
will consist of several problems,
of which some pseudo-randomly chosen problems will be graded.
Your two lowest homework grades will be dropped.
All hand-in assignments
will carry a specific due date and must be submitted
in class on the due date.
If you cannot come to class, you can
turn in your homework in my office no later than 2 p.m.
on the same day (if I am not in my office,
you can slip it in under the door).
No late homeworks will be accepted.
Shortly after a homework assignment's due date,
solutions to the problems from that assignment
will be placed on restricted reserve in the Chemistry-Mathematics Library
on the second floor of the Physical Sciences Center.
All homework assignments will be posted on this
page one week before the assignment is due
Technology:
Because this is a mathematics course,
we will emphasize the mathematical underpinnings of numerical
analysis and deliberately de-emphasize acquiring expertise in
any particular computer programming
language or software package. However, we will
frequently engage in computations
to illustrate the mathematical results that we derive.
For all computations required on in-class exams
and for most homework problems,
a calculator will be sufficient.
Even if the complexity of the numerical methods requires the
use of a computer,
the amount of programming you will need to do
will be very small, and previous programming experience is not assumed.
Moreover, the textbook comes with a CD-ROM
which contains programs for all of the numerical algorithms
developed in the textbook
(written in Fortran, C, Maple, Mathematica, Pascal, and MATLAB);
these programs are also available
on the web at
http://www.as.ysu.edu/~faires/Numerical-Analysis/DiskMaterial/index.html.
In class I will use MATLAB and Mathematica to illustrate
how some algorithms are implemented.
MATLAB and Mathematica are available on the computers in the University's computer labs,
in particular, in the College of Arts and Sciences computer labs
in the Physical Sciences Center (room 232) and in Dale Hall Tower;
you can also purchase a student version of MATLAB to load on your own PC
at the University Bookstore (the price is about $100),
but please note that you are not required to buy it.
Academic calendar for
Fall 2006.
Policy on W/I Grades : Through September 29, you can withdraw
from the course with an automatic W. In addition,
it is my policy to give
any student a W grade, regardless of his/her
performance in the course,
through the extended drop period that ends on December 8. However,
after December 8, you can only drop
via petition to the Dean of your college.
Such petitions are not often granted. Furthermore, even if the petition
is granted, I will give you a grade of "Withdrawn Failing" if you are
indeed failing at the time of your petition. Thus it is in your
own best interest to drop the course on or before December 8 if you think there
is a reasonable chance that you will not want to see the course through to
the end.
The grade of I (Incomplete) is not intended to serve as
a benign substitute for the grade
of F. I only give the I grade
if a student has completed the majority
of the work in the course (for example everything except the final exam),
the coursework cannot be completed because of compelling and verifiable
problem beyond the student's control, and the student expresses a clear
intention of making up the missed work as soon as possible.
Academic Misconduct: All cases of suspected academic misconduct will
be referred to the Dean of the College of Arts and Sciences for prosecution
under the University's Academic Misconduct Code. The penalties can be quite
severe. Don't do it!
For more details on the University's
policies concerning academic misconduct see
http://www.ou.edu/provost/integrity/.
Students With Disabilities:
The University of Oklahoma is committed to providing reasonable accommodation
for all students with disabilities. Students with disabilities who require
accommodations in this course are requested to speak with the instructor
as early in the semester as possible. Students with disabilities must be
registered with the Office of Disability Services prior to receiving
accommodations in this course. The Office of Disability Services is located
in Goddard Health Center, Suite 166: phone 405-325-3852 or TDD (only)
405-325-4173.
Other course materials:
Good to know: