MA615 Numerical analysis I

Instructor: Nikolay S. Strigul

Office Hours: by appointment

Lectures:Thursday 6:15 pm -8:45 pm, Peirce 116.

Assignments, Exams: There will be regular homework assignments, midterm and final exams.

Grading:

- Homework assignments: 30 %
- Midterm: 30 %

- Final: 40 %

Course programCourse program (PDF)

General comments:MA615 is the first part of a one-year course in numerical analysis for graduate students majoring in pure and applied mathematics. This course covers numerical methods of linear algebra (solution of linear algebraic equations, eigenvalues and eigenvectors), solutions of non-linear equations, interpolation and approximation methods, and extreme problems. The second part of the course, MA616 Numerical Analysis II, will be offered sequentially in the spring semester and covers numerical integration, solutions of differential (both, ODEs and PDEs) and integral equations, and statistical methods.

The course will be very intense; it will include three components: theoretical, computational and applications. All presented numerical methods will be considered theoretically in substantial depth, including derivation, convergence, error analysis, and limitations. Then the code in C++ for every method will be presented; some methods also will be illustrated with the Mathematica program. Also we will apply numerical methods to real-life problems and they will be used in concert with analytical results; examples will be taken mostly from Mathematical Biology, which is my research area.

In addition to the standard topics—such as, computational linear algebra, interpolation, extrapolation, integration, and solution of algebraic, differential and integral equations—some other topics may be considered, provided that the mandatory material is covered. In the first semester such an additional topic may be computational geometry, with applications in individual-based modeling of spatial populations. In the second semester, we may consider Markov chain Monte Carlo methods and Bayesian inference techniques, in applications to the ecology, in particular, by applying these methods to the forest inventory (FIA) data.

Prerequisites:The major prerequisites for MA615 are graduate courses in Linear Algebra (MA551 or equivalent) and Advanced Calculus (MA448 and MA449). It is strongly advised that students take MA615 only if they have a solid background in these disciplines. This course has absolutely no room to deeply review linear algebra and advanced calculus. However, the course is designed such that no preliminary experience in programming is required: C++ language will be introduced with examples in parallel with the theory development. Some background in numerical methods and programming such as an undergraduate course in numerical analysis or an introductory course in C++ will certainly be an asset.

Textbooks:

1) Numerical Recipes: The Art of Scientific Computing by W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery. Third Edition (2007), Cambridge University Press, ISBN: 0521880688.

Students should buy this textbook and the CD: Numerical Recipes Source Code CD-ROM: The Art of Scientific Computing by W.H. Press, S.A. Teukolsky, W.T. Vetterling, and B.P. Flannery. Third Edition (2007), Cambridge University Press, ISBN: 0521706858.

2) Introduction to Numerical Analysis by J. Stoer, R. Bulirsch, Third Edition (2002), Springer, ISBN: 038795452.

Course program:Aug 30. Lecture 1.- Algorithms, Numbers, C++, and Mathematica.

1. Memory, binary numbers, sources of error.

2. Propagation of errors.

3. Algorithms and C syntax.

4. Stability in numerical analysis.

5. Introduction to Mathematica.

Sep 6. Lecture 2.- Nonlinear algebraic equations. Rootfinding.

6. The bisection method.

7. The secant method.

8. Newton's method.

9. Combined methods.

Sep 13. Lecture 3.- Multiple roots. Roots of Polynomials.

10. The Newton's method and multiple roots.

11. Brent's method.

12. Roots of polynomials.

Sep 20. Lecture 4.- Matrices in C++.

13. Pointers.

14. Dynamic memory allocation.

15. Classes and objects.

16. The class "vector".

17. The class "matrix".

Sep 27. Lecture 5.- Linear algebraic equations I.

18. Gaussian elimination.

19. Pivoting.

20. Modifications of Gaussian elimination.

21. Error analysis.

Oct 4. Lecture 6.- Linear algebraic equations II.

22. LU Decomposition.

23. Iteration methods.

24. Singular Value Decomposition.

25. Sparse Linear Systems.

Oct 11. Lecture 7.- Eigenvalues and eigenvectors I.

26. The Gershgorin circle theorem.

27. Error and stability.

28. Symmetric matrices.

29. Nonsymmetric matrices.

Oct 18. Lecture 8.- Eigenvalues and eigenvectors II.

30. Orthogonal transformations.

31. Householder method.

Oct 25. Lecture 9.- Eigenvalues and eigenvectors III.

32. The QR method.

33. Finding Eigenvectors by Inverse Iteration.

Nov 1. Lecture 10.- Polynomial Interpolation and Extrapolation.

34. Searching an ordered table.

35. Polynomial interpolation theory.

36. Newton divided differences.

37. Forward and backward differences.

Nov 8. Lecture 11.- Piecewise Polynomial Interpolation.

38. Local interpolation problems.

39. Spline functions.

40. Cubic spline interpolation.

Nov 15. Lecture 12.- Orthogonal polynomials.

41. Orthogonal polynomials.

42. The least squares approximation.

43. Chebyshev Approximation.

44. Rational Chebyshev Approximation.

Nov 22. Thanksgiving Recess

Nov 29. Lecture 13.- Computational Geometry I.

45. Points and boxes.

46. Nearest-neighbor finding.

47. Triangles in two and three dimensions.

48. Polygons.

49. Spheres and Rotations.

Dec 6. Lecture 14.- Triangulations.

50. Voronoi diagrams.

51. Application to individual-based spatial population models.

Dec 13. Final exam.

back