Math 128B, Numerical Analysis, Spring 2010.

• Class Information
  • Unconventional ODE schemes by W. Kahan and R.-C. Li. Here is an email from R.-C. on the same subject.
  • Brent's method for root finding. We will discuss Brent's method later in the week of March 15.
  • Sample Midterm Exam.
  • Make-up class on Friday, Feb. 12 will be from 9:00-10:00AM in Room 6 Evans.
  • This semester, Ryan Hynd is teaching a one-unit credit course in matlab, Math 98 during the first 5 weeks of the semester. You are encouraged to take this one-unit course if you are not quite familiar with matlab programming. Note that this course is offered on a first-come first-served basis. So sign up as quickly as you can.
  • General information about the course can be found at /~mgu/MA128BSpring2010/general.html.
  • The class syllabus will be discussed in class. My current plan is to cover most of the material from Chapter 7 to Chapter 12 in Burden and Faires, plus two topics of interest to the class. We will probably discuss
    • Brent's method for root finding.
    • Unconventional ODE schemes by W. Kahan and R.-C. Li before Chapter 11 (boundary value ODEs.)
  • Possible Term Final Projects
    • Non-symmetric QR Algorithm : In this project, we extend the symmetric QR algorithm to solve the non-symmetric eigenvalue problem. This will involve Hessenberg reduction, and single and double shift QR algorithm.
    • Preconditioned Conjugate Gradient Method : In this project, we will develop the preconditioned version of the CG method, and test the effectiveness of various preconditioners. See Cojugate gradient method on Wikipedia.
    • Variations of the Fast Foruier Transform : The FFT comes in many different forms and variations. In this project, we study these variations and develop corresponding matlab code for doing these transforms. See Discrete cosine transform and Discrete sine transform on Wikipedia.
    • Brent's Method: We study convergence behavior of Brent's method for solving nonlinear equations, and compare it with the matlab function fzero.
  • Quiz and Exam Schedule:
    • Feb. 1 (quiz)
    • Feb. 22 (quiz)
    • March 8 (Midterm)
    • Mar. 29 (quiz)
    • Apr. 12 (quiz)
    • Apr. 26 (quiz)
  • Homework and Programming Assignment
    • Homework #1, due Feb. 1 in discussion.
    • Homework #2, due Feb. 8 in discussion.
    • Homework #3, due Feb. 17 in class.
    • Homework #4, due Feb. 22 in discussion.
    • Homework #5, due March 1 in discussion.
    • Homework #6, due March 8 in discussion.
    • Homework #7, due March 15 in discussion.
    • Homework #8, due March 29 in discussion.
    • Homework #9, due April 5 in discussion.
    • Homework #10, due April 12 in discussion.
    • Homework #11, due April 19 in discussion.
    • Homework #12, due April 26 in discussion.
    • Homework #13, due May 3 in review.
    • Programming Assignment #1, due Feb. 17 by Midnight.
    • Programming Assignment #2, due March 15 by Midnight.
    • Programming Assignment #3, due April 12 by Midnight.
    • Programming Assignment #4, due May 3 by Midnight. You will need the van der Pol solver, van der Pol function and boundary condition function for this Assignment.
    • Take Home Final Exam, due May 12 by Midnight.
  • Matlab Codes and Plots
    • Crank-Nicolson method for the heat equation. Here is a Demo program for Crank-Nicolson method. It requires a test function.
    • Shooting methods can be useful, but are sometimes unstable. Here is a Linear Shooting Demo program and a Nonlinear Shooting Demo program. They call the Linear Shooting Method and the Nonlinear Shooting Method . You will need the following programs to run the demos:
      • Wrapper functions for Linear Shooting and Nonlinear Shooting.
      • An internal function for Nonlinear Shooting.
      • Demo functions for Linear Shooting:
        • First demo: p function , q function , and r function .
        • Second demo: p function , q function , and r function .
      • Demo functions for Noninear Shooting: ODE function , its partial derivative with y , and partial derivative with y' .
    • Steepest Descent Method can have a hard time deciding whether to converge to a point that is nearly, but not, zero. Here is such a function. Note that there is a local minimum on the squared function that is not a zero of the original function.
    • Homotopy Method demo program that demonstrates convergence behavior of different initial guesses. Here is a demo function and its Jacobian matrix. This is the same function used in Section 10.2 in the book. Here is Homotopy method that solves the nonlinear equations by using the matlab ODE solver ode45, and here is the wrapper function called by ode45.
    • Newton Method for several variables demo program that demonstrates convergence behavior of different initial guesses. Here is a demo function and its Jacobian matrix. This is the function used in Section 10.2 in the book, which turns out to have two solutions, not one. Here is Newton's method for systems of nonlinear equations.
    • root-finder demo program that demonstrates convergence behavior of different root-finders, including the matlab built-in function fzero, Newton's method, Secant method, and Bisection method. You should run the demo program with different values of rho. Here is a demo function and its derivative.
    • Fourier Approximations to |sin x| and Errors. This is a non-smooth function, and the approximation is poor near points x =-pi, 0, pi.
    • This is a matlab program to test discrete and continuous Fourier Approximations. You will need to download DLS.m and EvalFourier.m to run the test program.
    • Fourier Approximations to exp(cos(x)) and Errors. This is a smooth and periodic function, and the Fourier approximations work very well.
    • Power2Chebyshev.m . This code returns a matrix $C$ such that a polynomial P(x) = a_0 + a_1 x + ... a_n x^n is converted into P(x) = b_0 + b_1 T_1(x) + ... b_n T_n(x) where (b_1, b_1, ..., b_n) = (a_0, a_1, ..., a_n)*C.
    • Here is an example with Newton's Method to find roots of non-linear equations.
    • Here is the QR algorithm for finding eigenvalues of a symmetric tridiagonal matrix. Last modified April 9, 2009 to fix a bug in deflation.
    • Here is an unstable version of the Householder Transformation.
    • The Power Method and the Inverse Power Method codes.
    • Redix 2 and 3 FFT .
    • The FFT and the Inverse FFT codes.
    • This is a demo code for performing Chebyshev rational approximation on an example function. Here is the Chebyshev polynomial evaluation function.
    • This code converts a power series into a Chebyshev series. For the function f(x) = 1/(1-x/2) on [-1, 1], the Chebyshev series converges much faster than the power series, requiring almost 40% fewer terms in the expansion for double precision accuracy. This matlab plot illustrates this point.
    • Conjugate Gradient with long recursions. This matlab code performs an iteration that is mathematically equivalent to Conjugate Gradient, but does so by explicitly performing A-conjugation against all previous A-conjudate vectors at every step. It also plots the non-zero patterns of the conjudate coefficients.
    • Preconditioned Conjugate Gradient.
    • Conjugate Gradient without Preconditioning .
  • Student Projects
    • SunEarthSat.m . This code was written by Eric Keldrauk in the Fall of 2008 as his final project for planetary simulations.
    • This is a planetary simulation package written by Daniel Andrews and Marco Marquez in the Spring of 2009 for their final project.
  • Web Links
    • Guide to Available Mathematical Software.
    • A brief history of numerical analysis.
    • Prof. Parlett's Notes on the QR algorithm .
    • Lecture notes on Chebyshev Alternation Theoreym at Cambridge University Numerical Analysis Group .
    • Wikipedia Entry on the Conjugate Gradient Method.
    • Top 10 Numerical Algorithms invented in 20th Century.