MATH 164
Introduction to
Numerical Analysis

Instructor: Roberto De Leo.     Term: Spring 2022.

Lecture 1, January 20

Topics

  • Introduction to the course.
  • What are the main goals of Numerical Analysis? Besides keeping track of computational errors, the main goal of NA is finding algorithms (as stable, fast and lean as possible!) to solve continuous mathematical problems (see this article by L. Trefethen).
  • Representing real numbers on a computer: scientific notation and floating point systems (if you are brave enough, read "What Every Computer Scientist Should Know About Floating-Point Arithmetic" by David Goldberg).
    A floating point system consists in representing numbers in scientific notation (in some base - usually base 2 for nowadays computers) while keeping only some fixed number of digits for both the number itself and its exponent.
  • See my compendium, page 1, for a toy decimal floating point system with three digits. It is much easier to notice the quirks of floating point systems in such a toy one.

Readings

Lecture 2, January 25

Topics

Readings

Homework #1

Due date: Feb. 3

Solve problems 1 and 2 in 1.5.

Lecture 3, January 27

Topics

  • Binary numbers
  • Floating point arithmetic quirks
  • What is Numerical Analysis
  • Evaluating numerically the derivative of a function

Readings

Links

Decimal to single-precision converter

Homework #1

Due date: Feb. 3

Solve problems 3 and 5 in 1.5.

Lecture 4, February 1

Topics

  • Evaluating numerically the derivative of a function: Forward differencing.
  • Evaluating numerically the derivative of a function: Centered differencing.
  • MATLAB: loops, arrays, plots.

Readings

Extra material

Homework #2

Due date: Feb. 8

Solve problem 1 in 2.5.

Lecture 5, February 3

Topics

  • The bisection method.
  • The Newton method.

Readings

Extra material

Lecture 6, February 8

Topics

  • The Newton method.
  • The Secant method.

Readings

Extra material

Lecture 7, February 10

Topics

  • The Secant method.
  • Linear Spaces and Linear maps.
  • MATLAB: conditionals, logical operators, comparing floating point numbers, defining functions.

Readings

Extra material

Homework set #3

Due date: Feb. 17

Solve problems 1, 2 and 3 in 3.6.

Lecture 8, February 15

Topics

  • The LU method.

Readings

Extra material

Lecture 9, February 17

Topics

  • LU with Pivoting.
  • Using LU decomposition to solve a system.
  • Computational complexity of the LU algorithm.
  • Error Analysis.

Readings

Extra material

Homework set #4

Due date: Feb. 24

Solve all four problems in 4.10.

Lecture 10, February 22

Topics

  • Norms in vector spaces.
  • Norms of matrices.
  • Error Analysis.

Readings

Lecture 11, February 24

Topics

  • Review of the implementation of the Gaussian elimination algorithm.
  • Error Analysis: why $b-A\hat x$ is not necessarily a good indicator of the precision of the solution.

Readings

Lecture 12, March 1

Topics

  • Iterative Methods.
  • Application: solving a Boundary Value Problem.

Readings

Extra Readings

Lecture 13, March 3

Topics

  • Application: solving a Boundary Value Problem.
  • The MATLAB/Octave backslash operator
  • Eigenvalues and eigenvectors.

Readings

Extra material

Lecture 14, March 15

Topics

  • Eigenvalues and eigenvectors.
  • Power method.

Readings

Extra material

Lecture 15, March 17

Topics

  • LU and QR methods
  • What does it mean "optimizing a function"?

Readings

Homework set #5

Due date: Mar. 24

Solve problems 1,2,3 in 5.5.

Lecture 16, March 22

Topics

  • Gradient methods.
  • The Steepest Descent method.

Readings

Lecture 17, March 24

Topics

  • Various implementations of the Steepest Descent method.

Readings

Homework set #6

Due date: Mar. 31

Rate of convergence of steepest descent. At the end of Section 6.4, I defined the rate of convergence of a sequence. Modify the code in Section 6.4 (or write your own!) to estimate the rate of convergence of the Steepest Descent method with constant step-size.
Hint. Add code to store in some array the distances between the elements $\mathbf{x_{k}}$ of the steepest descent method and the solution $\mathbf{x_{*}}$ and then display a loglog plot of $\|\mathbf{x_{k+1}}-\mathbf{x_{*}}\|$ versus $\|\mathbf{x_{k}}-\mathbf{x_{*}}\|$. To find the slope of the line you will see, you can use the same method we used in the second code in Section 2.2.1.

Lecture 18, March 29

Topics

  • Newton's method.
  • Conjugate gradient.

Readings

Lecture 19, March 31

Topics

  • Conjugate gradient.
  • Polynomial interpolation.

Readings

Lecture 20, Apr 5

Topics

  • Error of a polynomial interpolation.
  • Numerical integration: left Riemann sum.

Readings

Lecture 21, Apr 7

Topics

  • Newton Cotes integration for $n=0,1$.

Readings

Homework set #7

Due date: Apr 15

Solve problems 1,2,3 in 7.5.

Lecture 22, Apr 12

Topics

  • Newton Cotes integration for $n=2$.
  • Ordinary Differential Equations.

Readings

Lecture 23, Apr 14

Topics

  • Explicit Euler method.

Readings

Lecture 24, Apr 19

Topics

  • Heun method.
  • Runge-Kutta method.
  • Stiff ODEs.
  • Implicit Euler method.

Readings

Lecture 25, Apr 21

Topics

  • BVPs
  • Shooting method
  • Finite Difference Method.
  • Review.

Readings