CS450 Calendar

Note: Some calendar entries are clickable and link to entries below.

Lecture 28 (May 1, 2019, 1 p.m. - May 1, 2019, 2:15 p.m.)

Quiz for Lecture 28

Topics:

Boundary value problems
- Shooting method: implementation
- Non-uniqueness for nonlinear BVPs
- Finite difference methods
- Collocation method
- Weighted residual/Galerkin/Finite element methods, weak derivatives
Solving large, sparse linear systems
- Coordinate format, CSR format
- Stationary iterative methods for linear systems
- Conjugate Gradient Method

Scribbles

Lecture 27 (April 26, 2019, 1 p.m. - April 26, 2019, 2:15 p.m.)

Quiz for Lecture 27

Topics:

Predictor/Corrector Methods: Heun's method
Runge-Kutta methods
- Butcher tableaus
- Implicit/explicit/diagonally explicit
- High-order vs low order, efficiency
- Dissipation properties, relationship to stability region
Multi-step methods
Stability regions for RK methods
Cost metrics, trade-offs, more advanced methods (IMEX, Multi-Rate, Runge-Kutta-Chebyshev)
Boundary Value Problems: Intro, General formulation
- Shooting method

Scribbles

Lecture 26 (April 24, 2019, 1 p.m. - April 24, 2019, 2:15 p.m.)

Quiz for Lecture 26

Topics:

Forward and Backward Euler methods
Global and local error, order of accuracy for IVP solvers
Stability of IVP solvers
- Stability regions
- Forward and backward Euler: stability properties
- Stability for systems and nonlinear ODEs
- Unconditional stability
Stiff ODEs
- Examples, definitions, and computational treatment
- Accuracy and Stability concerns

Scribbles

Lecture 25 (April 19, 2019, 1 p.m. - April 19, 2019, 2:15 p.m.)

Quiz for Lecture 25

Topics:

Initial value problems
- Introduction, implicit and explicit methods
- Examples of IVPs
- Properties: linear, homogeneous, constant coefficient
- Existence, uniqueness, sensitivity
- Transformation to first-order form
- Transfomration to autonomous form
- Stability and asymptotic stability
- Forward Euler and experiments on its stability

Scribbles

Lecture 24 (April 17, 2019, 1 p.m. - April 17, 2019, 2:15 p.m.)

Quiz for Lecture 24

Topics:

Composite quadrature: Setup, error estimate
Numerical differentiation
- Conditioning, noise sensitivity, cancellation
- Deriving finite difference formulas via Taylor
- Deriving finite difference formulas via interpolation
- Scaling and shifting FD formulas
- Error estimates for numerical differentiation
Richardson extrapolation

Scribbles

Lecture 23 (April 12, 2019, 1 p.m. - April 12, 2019, 2:15 p.m.)

Quiz for Lecture 23

Topics:

Quadrature: Introduction, Existence/Uniqueness
Interpolatory quadrature, weights, nodes
Clenshaw-Curtis, Newton-Cotes
Method of undetermined coefficients
Midpoint, Trapezoidal, Simpson's rules
Degree of exactness of Newton-Cotes quadature rules, odd-order exactness increase
Order of accuracy estimate based on interpolation
Stability of Quadrature
Gaussian quadrature: Introduction

Scribbles

Lecture 22 (April 10, 2019, 1 p.m. - April 10, 2019, 2:15 p.m.)

Quiz for Lecture 22

Topics:

Interpolation Error Identity
Connection between error result and Chebyshev best-approximation
Asymptotic error estimates for interpolation
Piecewise interpolation and splines

Scribbles

Lecture 21 (April 5, 2019, 1 p.m. - April 5, 2019, 2:15 p.m.)

Quiz for Lecture 21

Topics:

Interpolation: Setup, problem statement, purpose, error model
Interpolation: Existence, Uniqueness, Sensitivity, Lebesgue Constant
Runge and Gibbs phenomena, advantages of edge-clustered nodal sets
Monomial interpolation and its conditioning issue
Lagrange and Newton interpolation, complexity of interpolation
Orthogonal Polynomials: Legendre, Chebyshev
Chebyshev interpolation: basis evaluation through recurrence, nodes, Vandermonde matrix

Scribbles

Lecture 20 (April 3, 2019, 1 p.m. - April 3, 2019, 2:15 p.m.)

Quiz for Lecture 20

Topics:

Levenberg-Marquardt as a least squares problem
Equality-constrained optimization
Lagrange Multipliers
Inequality-constrained optimization: Lagrangian, KKT conditions, computational approach

Scribbles

Lecture 19 (March 29, 2019, 1 p.m. - March 29, 2019, 2:15 p.m.)

Quiz for Lecture 19

Topics:

Newton review
Quasi-Newton methods, BFGS
Nonlinear least squares
Gauss-Newton method, Levenberg-Marquardt
Equality-constrained optimization, Necessary conditions

Scribbles

Lecture 18 (March 27, 2019, 1 p.m. - March 27, 2019, 2:15 p.m.)

Quiz for Lecture 18

Topics:

Sensitivity of optimization in $n$ dimensions
Unimodality, Golden Section Search
Newton's method in one dimension
Steepest Descent in $n$ dimensions, convergence
Extrapolation-based methods, momentum, heavy ball method, relationship to CG
Newton's method in $n$ dimensions

Scribbles

Lecture 17 (March 15, 2019, 1 p.m. - March 15, 2019, 2:15 p.m.)

Quiz for Lecture 17

Topics:

Fixed point iteration in $n$ dimensions, convergence criteria
Newton's method in $n$ dimensions
Broyden's method
Optimization: Problem statement, definitions
Global/local minima, coercivity, existence
Convexity, uniqueness of minima
Necessary/sufficient conditions for a minimizer, Hessians
Sensitivity of optimization (1D)

Scribbles

Lecture 16 (March 13, 2019, 1 p.m. - March 13, 2019, 2:15 p.m.)

Quiz for Lecture 16

Topics:

Fixed point iteration recap
Newton's method, convergence properties
Secant method, convergence properties
Muller's method, inverse quadratic interpolation
Trust region methods, hybrid methods

Scribbles

Lecture 15 (March 8, 2019, 1 p.m. - March 8, 2019, 2:15 p.m.)

Quiz for Lecture 15

Topics:

Rates of convergence recap
Stopping criteria
Bisection Method
Convergence Analysis for fixed point iteration

Scribbles

Lecture 14 (March 6, 2019, 1 p.m. - March 6, 2019, 2:15 p.m.)

Quiz for Lecture 14

Topics:

Arnoldi and Lanczos Iteration: Recap and Computation
Computation of the SVD
Nonlinear equations: Problem statement, existence, sensitivity
Rates of Convergence

Scribbles

Lecture 13 (March 1, 2019, 1 p.m. - March 1, 2019, 2:15 p.m.)

Quiz for Lecture 13

Topics:

Computational Expense in QR iteration, Householder similarity transform
Krylov space methods
Orthogonalization in Krylov space methods
Incremental computation in Krylov space methods
Arnoldi Iteration

Scribbles

Lecture 12 (Feb. 27, 2019, 1 p.m. - Feb. 27, 2019, 2:15 p.m.)

Quiz for Lecture 12

Topics:

Power iteration: convergence
Rayleigh quotient
Normalized Power Iteration, Inverse iteration, Rayleigh quotient iteration
Cost of power iteration variants
Orthogonal iteration
QR iteration, without and with shift

Scribbles

Lecture 11 (Feb. 22, 2019, 1 p.m. - Feb. 22, 2019, 2:15 p.m.)

Quiz for Lecture 11

Topics:

Eigenvalues: geometric and algebraic multiplicity
Diagonalizability and counterexamples
Similarity transforms and eigenvalue preservation
Eigenvalue transformations: shift, inversion, power, polynomial, similarity
Bauer-Fike eigenvalue sensitivity bound
Power Iteration: Idea, Convergence, Failure Modes

Scribbles

Lecture 10 (Feb. 20, 2019, 1 p.m. - Feb. 20, 2019, 2:15 p.m.)

Quiz for Lecture 10

Topics:

SVD: Introduction
Computing 2-norms, 2-norm condition numbers
Rank and numerical rank
Low-rank approximation, Eckart-Young-Mirsky theorem
Moore-Penrose pseudoinverse, SVD solution to total least squares
Relative cost of LU, QR, SVD
Eigenvalues: Introduction, spectrum, spectral radius
Eigenvalues: Computability

Scribbles

Lecture 9 (Feb. 15, 2019, 1 p.m. - Feb. 15, 2019, 2:15 p.m.)

Quiz for Lecture 9

Topics:

Householder QR
Givens QR
Total Least Squares (Problem Statement)
SVD: Definition
SVD: Properties (rough overview, to be repeated)

Scribbles

Lecture 8 (Feb. 13, 2019, 1 p.m. - Feb. 13, 2019, 2:15 p.m.)

Quiz for Lecture 8

Topics:

QR for Least Squares
Gram-Schmidt
Existence of QR, economical and full
Modified Gram-Schmidt
Intro to Householder

Scribbles

Lecture 7 (Feb. 8, 2019, 1 p.m. - Feb. 8, 2019, 2:15 p.m.)

Quiz for Lecture 7

Topics:

Least squares
Polynomial data fitting
Normal equations
Existence and Uniqueness for LSQ
LSQ: Geometric interpretation, connection to orthogonal projection
Pseudoinverse and condition number of non-square full-rank matrices
Sensitivity and Conditioning of LSQ

Scribbles

Lecture 6 (Feb. 6, 2019, 1 p.m. - Feb. 6, 2019, 2:15 p.m.)

Quiz for Lecture 6

Topics:

LU with Pivoting
Computational cost, finding inverses, solving with multiple right-hand sides
BLAS/LAPACK
LU Existence for non-invertible, non-square
Reduced LU
Schur complements
LU and Roundoff error
Sherman-Morrison

Scribbles

Lecture 5 (Feb. 1, 2019, 1 p.m. - Feb. 1, 2019, 2:15 p.m.)

Quiz for Lecture 5

Topics:

Residual and error in linear systems
Matrix change bounds in linear systems
Fw/Bw substitution
Elimination matrices
LU with Pivoting (intro)

Scribbles

Lecture 4 (Jan. 25, 2019, 1 p.m. - Jan. 25, 2019, 2:15 p.m.)

Quiz for Lecture 4

Topics:

Implementing FP arithmetic
Catastrophic Cancellation
Matrix norms
Matrix condition numbers

Scribbles

Examlet 0 (Jan. 24, 2019 - Jan. 26, 2019)

As you may have seen in our class policies, our "examlets" will take place in a computer-based testing facility ("CBTF") in Grainger Library.

You must schedule your test appointment with the Computer-Based Testing Facility at this link. This examlet is now available for scheduling.

Find out more about the testing facility, such as:

where it is
when to show up
what to bring (and not to bring)

The exam will be 110 minutes in length, and it will cover the material of the first two lectures, plus linear algebra basics and Python coding basics.

Lecture 3 (Jan. 23, 2019, 1 p.m. - Jan. 23, 2019, 2:15 p.m.)

Quiz for Lecture 3

Topics: