MATH 4073 - Numerical Analysis I, Section 001 - Fall 2005
MWF 8:30 - 9:20 a.m., 356 PHSC *

Instructor: Nikola Petrov, 802 PHSC, (405)325-4316, npetrov AT math.ou.edu.

Office Hours: M & F 2-3 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.

Please turn in HW#12 IN CLASS on Friday, December 9!
I will give you solutions to HW#12 in class on the same day.

The final exam will be from 10:30 a.m. to 12:30 p.m. on Wednesday, December 14.

The final will be a cumulative closed-book, closed-notes exam.
You are allowed to bring three 8x11-in sheets of paper with useful info.
Write the expressions for the errors of the different methods in your formula sheet!
Include the Taylor expansions of sin, cos, exp and ln in your formula sheet!
Do not forget to bring your calculators!

To prepare for the exam, review your lecture notes and the book.
Also look at the two hour exams and the homeworks
(all homework solutions are deposited in the Math-Chemistry library).

Additional office hours: TBA.

Just for fun:

• The greek_alphabet.

Homeworks (Solutions are posted after the due date in the Chemistry-Mathematics Library, 207 PHSC)

• Homework 1, due Wed, Aug 31.
• Homework 2, due Wed, Sep 7.
• Homework 3, due Wed, Sep 14.
• Homework 4, due Wed, Sep 21.
• Homework 5, due Wed, Sep 28.
• Homework 6, due Wed, Oct 12.
• Homework 7, due Wed, Oct 19.
• Homework 8, due Wed, Oct 26. Here are some graphs of the differences between the interpolating polynomial and the function f(x) in Problems 2 and 3 of this homework:
  • Problem 2: graphs of S(x) and f(x);
  • Problem 2: graph of S(x) - f(x);
  • Problem 2: graph of S'(x) - f'(x);
  • Problem 2: graph of S''(x) - f''(x);
  • Problem 3: graph of S₀(x)-f(x) for 0< x <1;
  • Problem 3: graph of S₁(x)-f(x) for 1< x <3;
  • Problem 3: graph of S'₀(x)-f'(x) for 0< x <1;
  • Problem 3: graph of S'₁(x) - f'(x) for 1< x <3.
• Homework 9, due Wed, Nov 2.
• Homework 10, due Wed, Nov 9. Codes traprl.m and simprl.m from the book Numerical Methods Using MATLAB by J.H. Mathews and K. D. Fink (4th edition, Pearson Prentice Hall, 2004).
• Homework 11, due Wed, Nov 30.
• Homework 12, due Fri, Dec 9. 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); codes rhs.m and twoders.m, and instructions how to run these codes.

Content of the lectures:

• Lecture 1 (Mon, Aug 22): Introduction. Review of calculus: notations, limit and continuity of a function, limit of a sequence (Sec. 1.1).
• Lecture 2 (Wed, Aug 24): Review of calculus (cont.): derivative of a function, Rolle's theorem, mean value theorem, extreme value theorem, Riemann sums and integral, mean value theorem for integrals, Taylor's theorem, examples of Taylor series. Computer arithmetic: binary, decimal and hexadecimal systems. (Sec. 1.1, 1.2).
• Lecture 3 (Fri, Aug 26): Computer arithmetic (cont.): bits and bytes, 1985 IEEE standard for a long real number, working with a finite number of digits - rounding and chopping. Roundoff errors: absolute and relative errors, floating-point operations, examples of roundoff errors - computing a sum, solving a quadratic equation (Sec. 1.2).
• Lecture 4 (Mon, Aug 29): Roundoff errors (cont.): nested way of computing polynomials (Sec. 1.2). Algorithms and convergence: pseudocode, loops, conditional execution, examples; stable, unstable and conditionally stable algorithms; linear and exponential growth of the error, examples (Sec. 1.3).
• Lecture 5 (Wed, Aug 31): Algorithms and convergence (cont.): rate of convergence, "big O" notation (Sec. 1.3). The bisection method: general idea, algorithm, a Matlab code bisection.m and instructions how to run it, the output from running it (Sec. 2.1).
• Lecture 6 (Fri, Sep 2): The bisection method (cont.): 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 the theorem), iterating a function graphically (Sec. 2.2).

• Lecture 7 (Wed, Sep 7): Fixed-point iteration (cont.): existence and uniqueness of fixed points (proof of the theorem), attracting and repelling fixed points, fixed-point iteration algorithm, a Matlab code fixedpoint.m, examples of failures of fixed-point iteration (Sec. 2.2).

• Lecture 8 (Fri, Sep 9): Newton's method: idea and iterative procedure, geometric interpretation, Newton's method algorithm, theorem about existence of interval of convergence of Newton's iteration (Theorem 2.5) (Sec. 2.3).

• Lecture 9 (Mon, Sep 12): Newton's method (cont.): modifications of Newton's method: the secant method (avoids computing the derivative of f(x)), the false position ('Regula Falsi') method (the root is bracketed between p_n-1 and p_n at each step of the iteration) (Sec. 2.3). Matlab codes newton.m and secant.m

• Lecture 10 (Wed, Sep 14): Error analysis for iterative methods: order of convergence, asymptotic error constant, linear and quadratic convergence, theorem about linear convergence of an iterative method p_n = g(p_n-1) with nonzero g'(p) (statement and proof), theorem about quadratic convergence of an iterative method p_n = g(p_n-1) with zero g'(p) (statement only) (Sec. 2.4)

• Lecture 11 (Fri, Sep 16): Error analysis for iterative methods (cont.): theorem about quadratic convergence of an iterative method p_n = g(p_n-1) with zero g'(p) (proof), constructing a quadratically convergent iterative procedure from a zero-finding problem, multiplicity of a zero of a function, relations between the multiplicity and the number of zero derivatives (Sec. 2.4).

• Lecture 12 (Mon, Sep 19): Error analysis for iterative methods (cont.): dealing with multiple zeros. Accelerating convergence: Aitken's method for accelerating convergence, forward differences. (Sec. 2.4, 2.5). Mathematica notebooks rate_of_convergence.nb and root_5_of_7.nb (and the files rate_of_convergence.txt and root_5_of_7.txt containing the same in plain text)

• Lecture 13 (Wed, Sep 21): Accelerating convergence (cont.): Steffensen's method for accelerating convergence, order of convergence of Steffensen's modification of a fixed-point iteration. Zeros of polynomials and Muller's method: fundamental theorem of algebra, corollaries (Sec. 2.5, 2.6).

• Lecture 14 (Fri, Sep 23): Zeros of polynomials and Muller's method (cont.): Horner's method (synthetic division), computing P(p_n-1) and P'(p_n-1) in Newton's method for polynomials by using synthetic division, method of deflation for finding zeros of polynomials (Sec. 2.6).

• Lecture 15 (Mon, 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).

• Lecture 16 (Wed, Sep 28): Introduction to interpolation and approximation: need of approximating data, interpolation and approximation, approximation properties of polynomials - Weierstrass Approximation Theorem, examples of failure of Taylor polynomials for approximation on an interval, on the dangers of rearranging (i.e., "reshuffling") infinite series - a "proof" that ln2=0 (Sec. 3.0).

• Lecture 17 (Fri, Sep 30): Hour Exam I.

• Lecture 18 (Mon, Oct 3): Interpolation and Lagrange polynomial: idea, explicit expression, error bound in Lagrange interpolation (Sec. 3.1).

• Lecture 19 (Wed, Oct 5): Interpolation and Lagrange polynomial (cont.): example: error bounds in piecewise-linear interpolation; including newly acquired data in "older" Lagrange interpolant, computing the value of the interpolating polynomial for a single value of the argument x, Neville's method; a handout on Neville's method (Sec. 3.1).

• Lecture 20 (Mon, Oct 10): Interpolation and Lagrange polynomial (cont.): Neville's method (cont.) - a handout (the same as the one in Lecture 19). Newton's divided differences: advantages of this representation (computationally efficient way to compute the coefficients of the interpolating polynomial P_n(x), and also to compute the value of P_n(x) at a given value of x), divided differences f[x₁,x₂,...,x_n], compact notation F_i,k = f[x_i-k,x_i-k+1,...,x_i] (i = index of the rightmost point, k = order of the divided difference) (Sec. 3.1, 3.2).

• Lecture 21 (Wed, Oct 12): Newton's divided differences (cont.): divided differences and high derivatives (Theorem 3.6); the case of equally spaced points x₀, x₁, ..., x_n: Newton's forward and backward differences formulae (Sec. 3.2).

• Lecture 22 (Fri, Oct 14): Cubic spline interpolation: general idea, piecewise-linear interpolation, cubic spline interpolant S(x) and its restrictions S_j(x) to [x_j,x_j+1], compatibility conditions on the functions S_j(x) at the internal points x_j+1 (j=0,1,...,n-1), origin of the boundary conditions (Sec. 3.4).

• Lecture 23 (Mon, Oct 17): Cubic spline interpolation (cont.): reformulating the conditions on S_j(x) in terms of the coefficients a_j, b_j, c_j, d_j; deriving a linear system for c_j from the conditions on S_j(x) at the internal points and the free (natural) boundary conditions (read the case of clamped boundary conditions from the textbook) (Sec. 3.4).

• Lecture 24 (Wed, Oct 19): Cubic spline interpolation (cont.): theoretical error bounds, remarks about the practical values of cubic splines. Numerical differentiation: idea, forward- and backward-difference formulae (Sec. 3.4, 4.1).

• Lecture 25 (Fri, Oct 21): Numerical differentiation (cont.): (n+1)-point formula for f'(x₀), 3-point formulae for f'(x₀), 3-point formula for f''(x₀) (Sec. 4.1).

• Lecture 26 (Mon, Oct 24): Richardson's extrapolation: idea, derivation, application: obtaining f'(x₀) by applying the centered difference 3-point formula and Richardson's extrapolation (Sec. 4.2).

• Lecture 27 (Wed, Oct 26): Richardson's extrapolation (cont.): derivation of a 5-point formula for f'(x₀) by Richardson's extrapolation. Numerical integration: goal, examples, ideas (Sec. 4.2, 4.3).

• Lecture 28 (Fri, Oct 28): Numerical integration (cont.): trapezoidal formula and Simpson's formula for numerical quadrature (Sec. 4.3).

• Lecture 29 (Mon, Oct 31): Numerical integration (cont.): an example of applying the trapezoidal and the Simpson's formulae (integrating sin(x) from 0 to Pi/2); degree of accuracy of a quadrature formula, 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 30 (Wed, Nov 2): Composite numerical integration: composite trapezoidal, Simpson's and midpoint rules, error bounds; practical issues in numerical integration: infinite limits of integration, singularities in the integrand (Sec. 4.4).

• Lecture 31 (Fri, Nov 4): Romberg integration: idea - composite trapezoidal rule for different stepsizes followed by Richardson's extrapolation (Sec. 4.5).

• Lecture 32 (Mon, Nov 7): Gaussian quadrature: idea and a simple example; theoretical foundations: linear space (vector space) (Sec. 4.7).

• Lecture 33 (Wed, Nov 9): Gaussian quadrature (cont.): theoretical foundations: linear space of polynomials of degree not exceeding n, inner product linear space, examples, weight function w (Sec. 4.7).

• Lecture 34 (Fri, Nov 11): Hour Exam II.

• Lecture 35 (Mon, Nov 14): The lecture is cancelled, but you have to read the material from the handout on Gaussian quadrature, part I which contains the following material: Gaussian quadrature (cont.): theoretical foundations: inner product in a space of polynomials, examples (Legendre polynomials, Hermite polynomials), statement of the theorem about Gaussian quadrature.

• Lecture 36 (Wed, Nov 16): Gaussian quadrature (cont.): theoretical foundations: proof of the theorem about Gaussian quadrature, an example of application, handout on Gaussian quadrature, parts I and II.

• Lecture 37 (Fri, Nov 18): Elementary theory of initial-value problems: initial-value problem (IVP) for a first-order ODE, Lipschitz condition and Lipschitz constant, examples of Lipschitz and non-Lipschitz functions, existence and uniqueness of solutions of an IVP for a first-order ODE (Sec. 5.1).

• Lecture 38 (Mon, Nov 21): Elementary theory of initial-value problems (cont.): examples of nonexistence and nonuniqueness of solutions of IVPs, equation of formation of a droplet of a liquid in saturated vapor (Sec. 5.1).

• Lecture 39 (Mon, Nov 28): Elementary theory of initial-value problems (cont.): well-posedness of an an IVP for a first-order ODE. Euler's method: idea, implementation, an example (Sec. 5.1, 5.2).

• Lecture 40 (Wed, Nov 30): Euler's method (cont.): error analysis (Sec. 5.2).

• Lecture 41 (Fri, Dec 2): Higher-order Taylor methods: local truncation error, higher-order Taylor methods (Sec. 5.3).

• Lecture 42 (Mon, Dec 5): Higher-order Taylor methods (cont.): an example; local truncation error of higher-order Taylor methods (without a proof) (Sec. 5.3). Runge-Kutta methods: idea, preparation - Taylor Theorem for a function of two variables (Sec. 5.4).

• Lecture 43 (Wed, Dec 7): Runge-Kutta methods (cont.): derivation of the midpoint method (Sec. 5.4).

• Lecture 44 (Fri, Dec 9): Runge-Kutta methods (cont.): derivation of the modified Euler method and Heun's method; Runge-Kutta method of order four; error control and idea of Runge-Kutta-Fehlberg method (Sec. 5.4, 5.5). Last words of wisdom, tears, etc.

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 mainly MATLAB to illustrate how some algorithms are implemented. You, however, can use any of the alternative formats if you are more comfortable with them. MATLAB is available on many of the PCs 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.

Some Important Dates :

1. Final Day to Register or Add a Class: Friday, August 26
2. Last day to drop a class with a refund: Friday, September 2.
3. Last day to drop a class without recorded grade: Friday, September 2.
4. Last day to withdraw with an automatic W: Friday, September 30.
5. Last day to withdraw with a W/F without permission of the Dean: Friday, December 9.

Policy on W/I Grades : Through Friday, October 1, 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 Friday, October 30. However, after October 30, 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 October 30 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 click here.

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:

• A 33-page Practical Introduction to Matlab, by Mark Gockenbach (Michigan Technological University); the same Introduction, in html format.
• A 16-page Matlab Tutorial by Peter Blossey (University of Washington).
• A 8-page Introduction to Plotting with Matlab from the University of Washington.
• A very detailed (125 pages) Matlab Overview by Ed Overman (Ohio State University).
• A 35-page Matlab Primer by Kermit Sigmon (University of Florida).