Computer-oriented methods for solving numerical problems in science and engineering; numerical solutions to systems of simultaneous linear equations, nonlinear algebraic equations (root solving), differentiation and integration, ordinary differential equations, interpolation, and curve fitting.
Course Outcomes
Instructor
Dr Gabrielle Allen
Department of Computer Science, Louisiana State University
Email: allen@bit.csc.lsu.edu
Web: http://www.cct.lsu.edu/~gallen
IM: gridrebel
Office hours (Johnston Hall, Room 305): Tuesday 1pm-3pm, Thursday 2pm-3pm; (Coates Hall, Room 288): Wednesday 1pm-3pm.
General Information
Location: TUREAUD HALL Room 213
Times: Tuesday and Thursday, 3.10pm to 4.30pm
Prerequisites
MATH 1552 and CSC 1251 or 1351 or 2390
Textbook
Elementary Numerical Analysis
Atkinson and Han
Third Edition, Wiley Publishers
ISBN: 0-471-43337-3
References
Numerical References in C: The Art of Scientific Computing
William H. Press, Brian P. Flannery, Saul A. Teukolsky, William T. Vetterling
Cambridge University Press
Online at: http://www.nrbook.com/a/bookcpdf.php
Numerical Analysis and Scientific Computation
Jeffery Leader
Addison Wesley
Introduction to Numerical Analysis
F.B. Hildebrand
Dover Press
Grading
Grades will be constructed from points earned from tests, exams, assignments and class participation as follows:
| Test 1 | 100pts |
| Test 2 | 100pts |
| Final Exam | 130pts |
| Assignments | 140pts |
| Class Participation | 30pts |
| TOTAL | 500pts |
Grading Scale
Grades for assignments and exams will use the following scale:
| A | 85% to 100% |
| B | 70% to 84% |
| C | 55% to 69% |
| D | 40% to 54% |
| F | Less than 40% |
Exams(tentative)
Test 1 (In Class): February 15th 2007
(Foundation and Root Finding)
Test 2 (In Class): March 27th 2007
(Interpolation, Approximation, Integration, Differentiation)
Final (In Class, 5.30pm to 7.30pm): May 12th 2007
Class Policy
- Students are responsible for checking their mail regularly
- If you email me make sure the subject includes CS2262
- Make-up tests will be permitted in exceptional circumstances. If test 1 or 2 is missed the grade will be 80% of the next test using a 100 point scale.
- NO access to calculators, phones, ipods, etc during class and tests/exams
- All problems with grades must be resolved within 3 class days following the return of graded work.
- Assignments:
- All work is to be completed by the individual student, except for any explicit group assignments.
- Electronically prepared assignments should be emailed, by the end of the day given as the deadline, to cs2262_assignments@cct.lsu.edu. Use the title of the assignment as the subject for the email.
- Written assignments should be handed in at the class on the day given as the deadline.
- Assignments must be submitted on time. One late assignment is allowed, which will be awarded a maximum of a "C" grade. Any exceptional circumstances should be discussed as soon as possible with the instructor.
Curricula
Download: PDF
- General Skills
- Ability to calculate error terms, deduce convergence rate, and general error properties, given the expression for an error.
- Ability to provide pseudo-code for any numerical method
- Ability to graphically represent numerical methods and their application
- Definition of error, sources of different kinds of error and their contribution to numerical solution of real world scientific problems.
- Definition of convergence, and ability to determine the rate of convergence from numerical errors from an iterative or other method.
- Knowledge of different ways that a problem may be ill-behaved.
- Mathematics: equation of a line, basic integration and differentiation, chain rule for differentiation, integration by parts, form of basic functions (ex , ln x, cos x, sin x), definition of a tridiagonal system, solution of quadratic equations, mean value theorem, matrix determinants.
- Computer Arithmetic
- Floating-point numbers, scientific notation, single precision and double precision IEEE floating-point formats, binary numbers, hexadecimal numbers, conversion between formats, accuracy of floating point representation.
- Rounding and chopping of numbers, loss of significant figures, noise in evaluating functions, underflow and overflow, summation of numbers, loop errors.
- Taylor Polynomials
- Derivation of general Taylor polynomials of arbitrary order about a particular point of approximation, Taylor's remainder theorem, calculation of and use of error bounds, calculating Taylor polynomials for simple expressions, Taylor's series.
- Root Finding
- Derivation of algorithm for bisection method, error bounds and rate of convergence for bisection method.
- Derivation of algorithm for false position and secant method, error bounds and rate of convergence for both methods.
- Derivation of algorithm for Newton's method. General properties of its application and error.
- General method of fixed point interation. Ability to express and apply the contraction mapping theorem and its corollary.
- Aitken error estimation and extrapolation.
- Ill-behaving root finding, general understanding of multiple roots and stability of roots.
- Graphical representation and interpretation of all root finding methods.
- Interpolation and Approximation
- Definition of polynomial interpolation. Given a polynomial, you should be able to say whether or not it interpolates a set of data. Difference between interpolating polynomials and approximating polynomials.
- Detailed derivation and application of linear polynomial interpolation.
- Definition of piecewise interpolating polynomials.
- Form of, and use of the general Lagrange polynomial interpolation formula.
- Properties of errors in polynomial interpolation.
- Motivation for and use of the near-minimax approximation
- Definition and use of divided differences, including their use in formulae for interpolation
- Definition of and motivation for cubic splines. Ability to calculate natural cubic splines for simple cases when provided with all defining equations. Given a function, you should be able to say whether or not it is a natural cubic spline for some set of data.
- Integration and Differentiation
- Derivation and use of trapezoidal rule, use of Simpsons rule, midpoint rule, graphical interpretation, properties of errors for methods.
- Deriving number of node points to use for a particular error tolerance.
- Corrected trapezoidal/Simpsons rule
- Derivation and use of Richardson extrapolation formula
- Gaussian integration, derivation for cases n=1 and n=2, change of variable for general ranges.
- Numerical derivatives, derivation of forward and backward difference formulae, method for differentiation using interpolation, method of undetermined coefficients.
- Linear Systems
- Examples of linear systems, e.g. polynomial interpolation, difference between direct and iterative methods.
- Matrices: order, notation, transpose, arithmetic and algebra, row operations, inverse, singular matrices, determinant, norms
- Solvability theorem.
- Direct methods: Gaussian elimination, pivoting, LU decomposition, operations count, calculating matrix inverse, tri-diagonal systems
- Iterative methods: General scheme, Jacobi, Gauss-Seidel, convergence criteria and behaviour of general iterative solvers, role of diagonally dominant matrices, role of matrix eigenvalues, residual correction for a general scheme, pseudo-code algorithms for Jacobi and Gauss-Seidel
- Ordinary Differential Equations
- Examples of ODEs, e.g. harmonic oscillator.
- Definition of order, linear, nonlinear and examples.
- Derivation of Eulers method using Taylors series and discussion of error term.
Lecture Notes
These are my teaching notes, which follow the textbook, and are not replacing the textbook. The class is expected to use the textbook as their main reference for the course. The sections in my notes follow the sections in the textbook, and I have indicated where particular sections from the textbook are not required for the course. These printed notes only cover the first half of the course.
Version March 22nd: [PDF]
Lecture Schedule and Assignments
| Class | Date | Lecture (Tentative Plan) | Assignments and Notes |
|---|---|---|---|
| 1 | Jan16 | Introduction | |
| 2 | Jan18 | Foundations: Representation of Numbers | Assignment 1 (Due Jan 25th) |
| 3 | Jan 23 | Foundations: Representation of Numbers, Errors | |
| 4 | Jan 25 | Foundations: Errors, Taylor Polynomials | Assignment 2 (Due Feb 1st) |
| 5 | Jan 30 | Guest Lecture: Prof Seidel | Presentation |
| 6 | Feb 1 | Foundations: Taylor Polynomials | Assignment 3 (Due Feb 8th) |
| 7 | Feb 6 | Root Finding | |
| 8 | Feb 8 | Examples | Assignment 4 (Due Feb 15th) |
| 9 | Feb 13 | Root Finding | |
| 10 | Feb 15 | Test 1 (Foundations & Root Finding) | |
| - | Feb 20 | - | No Class Assignment 5 (Double Assignment, Due March 1st) |
| 11 | Feb 22 | Root Finding | |
| 12 | Feb 27 | Exam Review | |
| 13 | Mar 1 | Root Finding | Assignment 6 (Due March 8th) |
| 14 | Mar 6 | Interpolation & Approximation | (Examples) |
| 15 | Mar 8 | Interpolation & Approximation | Assignment 7 (Due March 16th) |
| 16 | Mar 13 | Interpolation & Approximation | |
| 17 | Mar 15 | Interpolation & Approximation | |
| 18 | Mar 20 | Integration & Differentiation | Assignment 8 (Due March 27th, extended to April 5th) |
| 19 | Mar 22 | Integration & Differentiation | Assignment 9 (Due March 30th, extended to April 5th) |
| 20 | Mar 27 | Test 2 (Interpolation, Approximation, Integration, Differentiation) | |
| 21 | Mar 29 | Examples | |
| - | Apr 3 | - | No Class |
| - | Apr 5 | - | No Class |
| 22 | Apr 10 | Linear Systems: Introduction and Matrices | |
| 23 | Apr 12 | Linear Systems: Direct solvers, Gaussian Elimination | Assignment 10 (Due April 19th) |
| 24 | Apr 17 | Linear Systems: LU Decomposition | |
| 25 | Apr 19 | Linear Systems: Errors | Assignment 11 (Due April 27th) |
| 26 | Apr 24 | Linear Systems: Iterative Solvers | |
| 27 | Apr 26 | ODEs | Assignment 12 (Due May 3rd) |
| 28 | May 1 | ODEs | |
| 29 | May 3 | Review | Concentrated Study |
| - | May 12 | Final Exam | No Class |