MATH 368K. Numerical Methods for Applications.

Unique #58355, Spring 2007


Final Exam. Saturday, May 12, 7:00-10:00 p.m. in RLM 6.112
Open book and notes. The exam is comprehensive.
Please check your homework scores on the class e-gradebook. If there is a missing or incorrectly registered score, please let me know.
OFFICE HOURS: Tuesday 9-12:00 noon.

Problem Set 11. Due F 5/4.
12.3 # 3, 4, 6 [use matlab code from the demos]

Problem Set 10. Due F 4/27.
11.5 # 3b, 6, 7 (use code below)
12.1 # 2, 5 (modify the Poisson code below)
12.2 # 18
Exercises:
1. Verify the convergence of the Poisson code using test problem 12.1 # 3c.
  1. Verify that it converges with O(h2) accuracy when h = k. Be sure to use a linear solver tolerance that is much less than the error!
  2. Verify that it converges with O(h2) accuracy when k is negligible. This tests that the x-part is converging correctly.
  3. Verify that it converges with O(k2) accuracy when h is negligible. This tests that the y-part is converging correctly.
  4. Make a very small error to the code under the
    // SET BOUNDARY VALUES
    section of poisson.C by replacing
    for(j=1; j<m; j++) {
       y += k;
       u(0,j) = gL(y);
       u(n,j) = gR(y);
    }
    by
    for(j=1; j<m; j++) {
       u(0,j) = gL(y);
       u(n,j) = gR(y);
       y += k;
    }
    That is, a single line is moved so that the y-value is slightly off in the determination of the y-boundary condition. Explain what happens to the convergence rate when you conduct the previous three tests.
2. Use the test problems 12.2 #6(a,b) to test the three heat equation solvers forward difference, backward difference, and Crank-Nicolson.
  1. Show that the first is unstable if h and k are large, but the other two are stable for any h and k.
  2. Verify that the first two converge as O(k + h2), and the Crank-Nicolson is O(k2 + h2).
Code: The piecewise linear Rayleigh-Ritz method:    linRR.C    linRR.h
Code for Poisson's equation:    poisson.C    poisson.h    main.C
Code for solving the heat equation with various methods:    heat.C    heat.h    main.C

Problem Set 9. Due F 4/20.
11.2 # 4(a,c), 5
11.3 # 2, 7, 8
11.4 # 1, 4b, 6
Project: (a) Verify that the nonlinear finite difference code below converges with O(h2) accuracy (use the test problems from 11.4 # 1 and 2).
(b) Verify that the Newton solver imbedded in the code is second order accurate.
Code for the RK-4 nonlinear shooting method with Newton:    nonlinShooting.C    nonlinShooting.h
Code for the linear finite difference method:    linFD.C    linFD.h
Code for the nonlinear finite difference method for solving BVP's:    nonlinFD.C    nonlinFD.h

Extra: Software to find trajectories of projectiles.
projectile.C
projectile.h
projMain.C
matlabPlot.C
matlabPlot.h

Exam 2. Friday, April 13
Chapters 8.2-3,5-6; 10.1-4; and 11.1
You may use a calculator, single page of notes, and your textbook on this exam.

Problem Set 8. Due F 4/6.
10.4 # 2a, 4a, 5a [answer in back incorrect: (5.21509,-2.61114) is one answer (there are multiple minima)]
   Extra questions for 4a: Starting from the result from 2a, how many iterations are needed
   to solve the problem to accuracy 10-6 using
   (i) Newton's method and (ii) the method of steepest descent?
11.1 # 2a, 4(a,b), 7
Code for steepest descent algorithm:    steepDescent.C    steepDescent.h
Code for the RK-4 linear shooting method:    linShooting.C    linShooting.h

Problem Set 7. Due F 3/30.
10.2 # 1a, 10
10.3 # 1a, 10
Project:
1. Code both the Newton and Broyden algorithms to find roots. Write these, with the fixed point algorithm from Problem Set 6, as a software package suitable for reuse with other codes. The three function prototypes should be
state fixedpt(void g(const Vector&,Vector&), Vector& x, double tol, int& iter);
state newton(void f(const Vector&,Vector&), void df(const Vector&,Matrix&), Vector& x, double tol, int& iter);
state broyden(void f(const Vector&,Vector&), void df(const Vector&,Matrix&), Vector& x, double tol, int& iter);
You should use the gausss elimination (gaussElim.C/gaussElim.h) routines from an earlier exercise.
2. Test all three algorithms on the problems of 10.2 # 7. You will need to find a suitable fixed point function for that algorithm. You will need to provide the Jacobian (df) for the Newton algorithm. Report the number of iterations taken.

Problem Set 6. Due F 3/23.
10.1 # 4, 5(b,c), 6(b,c), 11
Code: For the exercises, you may use this C++ code fixedpt.C. The code uses the Matrix and Vector classes from Problem Set 1 (matrix.h/C).

Problem Set 5. Due F 3/9.
8.3 # 2a, 4a, 5a
8.5 # 1, 7a, 16
8.6 # 1a

Exam 1. Friday, Mar. 2
Chapter 7 and 8.1-2
You may use a single page of notes on this exam.

Problem Set 4. Due W 2/21.
8.1 # 7a
8.2 # 2b, 4b, 11 [Find L0, L1, and L2 only], 12b [degree one and two only]
Exercises:
1. By hand, compute the best linear and quadratic polynomials fitting the data (0,3), (1,4), (2,6), and (2,7). Compute the least squares errors, and make rough graph of your results.
2. Lease squares code:
(a) Write a function to compute the coefficients of the least squares polynomial of degree n for a given set of m data points (x[i],y[i]). You should use existing linear system solution software, such as the the gaussian elimination software (gaussElim.C and gaussElim.h), to solve the linear system. Be sure to handle the possibility that the linear system has no solution (i.e., return an error state).
(b) Test your code on exercise 8.1 # 3 (i.e., fit the data to polynomials of degree 1, 2, and 3).

Problem Set 3. Due W 2/14.
7.5 # 5a, 6a, 10, 13
Exercises:
1. If Ax=b but A is not symmetric, we can not expect conjugate gradients to work well. However, AT Ax=ATb is equivalent. Show that AT A is positive definite (assuming that A is invertible).
2. Preconditioned conjugate gradients.
(a) Extend the iterativeLA software package to implement preconditioned conjugate gradients with a given preconditioner.
(b) Test your code on the problem in exercise 7.5#9a to a tolerance of 1e-6 using preconditioner D-1/2 (i.e., Jacobi). Report the number of iterations needed for this problem.
Code: My version of (unpreconditioned) Conjugate Gradients

Problem Set 2. Due W 2/7.
7.3 # 14(a,b)b, 18, 19, 20, 21a, 22
7.4 # 2(a,c), 4(a,c)
Project: Write a code to implement the SOR algorithm. Add it to the iterativeLA package of the previous problem set. (You should check that omega is between 0 and 2; otherwise, there is an error, since SOR will not work.)

Problem Set 1. Due W 1/31.
7.1 # 1, 4, 13
7.2 # 2(b,e), 4(b,e), 6(b,e), 14
7.3 # 2(a,b), 4(a,b), 6(a,b), 8(a,b) [use the codes below for 6 and 8]
Exercise: Write a code to implement the Gauss-Seidel algorithm. You may and should start from the Jacobi code provided below.
Computer code:
   Matrices and vectors: matrix.C and matrix.h
   Iterative linear algebra: iterativeLA.C and iterativeLA.h
   Main test code: main.C