• Overview of course organization and course topics
• Taylor's theorem (one-dimensional version)
• IEEE arithmetic: integers, floating point numbers, double precision numbers
• Absolute error, relative error, error propagation, cancellation

Read appendix A2.1, A2.2
Old lecture notes: Chapter 2: Computer Arithmetic and Computational Errors

• The machine epsilon
• The condition number of a problem and an algorithm
• Review of linear algebra (vectors and matrices)

Read appendix A1
Old lecture notes: Chapter 2: Computer Arithmetic and Computational Errors

• Intro to MATLAB (my notes)

Start reading chapter 1. Alternatively, find a MATLAB tutorial on the web, and read that.

More about linear algebra :

• inverse matrix
• eigenvalues and characteristic equation
• special types of matrices: diagonal, tridiagonal, banded, triangular, Hessenberg, symmetric, orthogonal

Finish reading chapter 1, or whatever tutorial you are using. Play around with MATLAB.

Start Topic 2: Linear Algebra

• A system of m equations in n unknowns is equivalent to a matrix equation Ax = b.
• Standard approach to all numerical analysis problems:
  1. Does the mathematically exact problem have a unique solution? If not, add more conditions until it does
  2. Find an algorithm
  3. Find an error estimate for the algorithm
• Answer to 1: A unique solution for all right-hand sides b exists if and only if A is square (m = n) and nonsingular. We will assume that from now on.
• Answer to 3: The only source of error in this situation is round-off error, which can be estimated from the condition number. The condition number is norm(A) · norm(A^-1), both for changes in the right-hand side b and changes in A.
• relevant MATLAB functions: A/B and A\B, inv(A), cond(A), rcond(A)

Read 2.1 - 2.4. You can skip the parts of 2.2 that deal with rank-deficient systems. We will come back to that later.
Old lecture notes: Chapter 3: Linear Systems of Equations

Gaussian Elimination

• We now tackle item 2. from the list above: Find an algorithm. The standard approach to deriving algorithms for most linear algebra problems is this:
  1. Identify types of matrices for which the problem is easy to solve
  2. Identify allowed operations which will not change the solution
  3. Figure out how to use allowed operations to reduce the original problem to one of the easy cases
• The answers for the case of solving Ax = b are
  1. Triangular matrices
  2. Elementary operations: scale a row, add a multiple of one row to another, interchange rows
  3. Gaussian Elimination

Read 2.5, 2.6.
Old lecture notes: Chapter 3: Linear Systems of Equations

More on Gaussian Elimination

• The need for pivoting, to avoid zero pivots and to improve stability
• Gaussian elimination is equivalent to factorization A = L ·U

The Cholesky algorithm

• If A is symmetric, positive definite, it can be factored as A = L · L^T
• If A is symmetric, it can be factored as A = L ·D· L^T

Read 2.7, 2.8
Old lecture notes: Chapter 3: Linear Systems of Equations

Final remarks on Gaussian Elimination

• Very well suited for banded matrices (O(n) operations)
• Solving matrix equations AX = B, especially AX = I to find X = A^-1
• We don't actually need A^-1. Ever.

QR factorization

• Definition of QR, full versus reduced QR factorization
• Gram-Schmid orthonormalization algorithm produces reduced QR
• Other algorithms (Givens rotations, Householder matrices) produce full QR
• Pivoting can be used to sort diagonal elements in R by size (and produce trapezoidal partition of R, instead of triangular)
• Use QR to find rank, nullspace and range of matrix

Read 2.9 if you want. Mostly it describes the Householder algorithm, which I did not cover in class.
Old lecture notes: Chapter 6: Linear Least-Squares Data Fitting

Least Squares Problems

• Source of problems, examples
• Solving them by Normal Equations
• Solving them by QR
• Solving them by SVD

More on the Singular Value Decomposition

Read 2.10, 2.11, 2.12. Skip the rest of chapter 2.
Old lecture notes: Chapter 6: Linear Least-Squares Data Fitting

Class meets in computer lab Carver 449 instead of our classroom

Homework 1 due

Linear Algebra in Matlab: Examples and demonstrations (my notes)

Start Topic 3: Nonlinear Equations and Optimization

• Overview of one-dimensional case
  • direct versus iterative methods
  • root finding versus optimization (finding max or min)
  • order of an iterative method
• the bisection method
• fixed point iteration

Read 3.1 — 3.4.
Old lecture notes: Chapter 7: Solution of Nonlinear Equations

More on solving nonlinear equations:

• fixed point iteration (continued)
• Newton's method

Read 3.5, 3.7. Skip 3.6.
Old lecture notes: Chapter 7: Solution of Nonlinear Equations

More on solving nonlinear equations:

• secant method
• why secant is better than Newton's method
• routine fzero in Matlab does a combination of bisection and secant

Overview of optimization:

• golden section search (similar to bisection)
• Newton's method (same as the other Newton's method for f = F')
• parabolic interpolation (similar to secant)
  

Old lecture notes: Chapter 9: Optimization and Nonlinear Least Squares

Aitken Δ² extrapolation

A quick survey of higher-dimensional root finding and optimization:

• Review of multivariable calculus
• Methods for root finding: fixed point iteration, Newton's method, quasi-Newton methods
• Methods for optimization: direction search methods

Old lecture notes: Chapter 9: Optimization and Nonlinear Least Squares

Class meets in computer lab Carver 449 instead of our classroom

• Interacting with a script (input, keyboard, debugging commands)
• Formatting output (disp, num2str, sprintf)
• Passing functions as parameters (eval, feval)
• Equation solving and optimization (fzero, fminbnd, fminsearch)
• Passing extra arguments (global)

My notes

Start Topic 4: Data Fitting

Homework 2 due

• Interpolation versus Approximation
• Evaluating polynomials: Horner scheme
• Different representations: powers of (x - x₀) instead of powers of x, or sum of Lagrange polynomials
• Polynomial Interpolation
  • using system of linear equations
  • Lagrange polynomials

Read 7.2
Old lecture notes: Chapter 4: Interpolation

• Newton's interpolation method
• Error term and instability of high degree polynomial interpolation (Runge example)
• Some example(s) for estimating the accuracy

Read 7.2
Old lecture notes: Chapter 4: Interpolation

Piecewise polynomials (splines)

Read 7.3
Old lecture notes: Chapter 4: Interpolation

• Review of polynomial and spline interpolation
• More on splines (if necessary)
• Review of least squares approximation
• Nonlinear least squares

Fourier analysis

Read 7.4

Class meets in computer lab Carver 449 instead of our classroom

My notes

Nonlinear Least Squares

Homework 3 due

Quick overview of numerical differentiation and integration

Read 4.1-4.6 (optional)

Review of ODE theory

Overview of numerical methods for ODEs

Read 5.1, 5.14, or 8.1 in my notes

Numerical Solution of ODEs

• Taylor series methods
• local and global error

Read 5.2, 5.3, or 8.4 in my notes

Numerical Solution of ODEs

• Runge-Kutta methods

Read 5.5, or 8.19 in my notes

Numerical Solution of ODEs

• multistep methods = predictor/corrector methods
• accuracy and stability

Read 5.4, 5.6, or 8.9 in my notes
Note: the trapezoidal method covered in 5.4 is a one-step implicit multistep method

Numerical Solution of ODEs

• shooting methods for boundary value problems
• methods for stiff ODEs

Read 5.15.

Homework 4 due

Class meets in computer lab Carver 449 instead of our classroom

My notes

Review

Discussion of final homework

Homework 5 due