$\newcommand{\eps}{\varepsilon} \newcommand{\kron}{\otimes} \DeclareMathOperator{\diag}{diag} \DeclareMathOperator{\trace}{trace} \DeclareMathOperator{\rank}{rank} \DeclareMathOperator*{\minimize}{minimize} \DeclareMathOperator*{\maximize}{maximize} \DeclareMathOperator{\subjectto}{subject to} \newcommand{\mat}[1]{\boldsymbol{#1}} \renewcommand{\vec}[1]{\boldsymbol{\mathrm{#1}}} \newcommand{\vecalt}[1]{\boldsymbol{#1}} \newcommand{\conj}[1]{\overline{#1}} \newcommand{\normof}[1]{\|#1\|} \newcommand{\onormof}[2]{\|#1\|_{#2}} \newcommand{\MIN}[2]{\begin{array}{ll} \minimize_{#1} & {#2} \end{array}} \newcommand{\MINone}[3]{\begin{array}{ll} \minimize_{#1} & {#2} \\ \subjectto & {#3} \end{array}} \newcommand{\MINthree}[5]{\begin{array}{ll} \minimize_{#1} & {#2} \\ \subjectto & {#3} \\ & {#4} \\ & {#5} \end{array}} \newcommand{\MAX}[2]{\begin{array}{ll} \maximize_{#1} & {#2} \end{array}} \newcommand{\MAXone}[3]{\begin{array}{ll} \maximize_{#1} & {#2} \\ \subjectto & {#3} \end{array}} \newcommand{\itr}[2]{#1^{(#2)}} \newcommand{\itn}[1]{^{(#1)}} \newcommand{\prob}{\mathbb{P}} \newcommand{\probof}[1]{\prob\left\{ #1 \right\}} \newcommand{\pmat}[1]{\begin{pmatrix} #1 \end{pmatrix}} \newcommand{\bmat}[1]{\begin{bmatrix} #1 \end{bmatrix}} \newcommand{\spmat}[1]{\left(\begin{smallmatrix} #1 \end{smallmatrix}\right)} \newcommand{\sbmat}[1]{\left[\begin{smallmatrix} #1 \end{smallmatrix}\right]} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\eye}{\mat{I}} \newcommand{\mA}{\mat{A}} \newcommand{\mB}{\mat{B}} \newcommand{\mC}{\mat{C}} \newcommand{\mD}{\mat{D}} \newcommand{\mE}{\mat{E}} \newcommand{\mF}{\mat{F}} \newcommand{\mG}{\mat{G}} \newcommand{\mH}{\mat{H}} \newcommand{\mI}{\mat{I}} \newcommand{\mJ}{\mat{J}} \newcommand{\mK}{\mat{K}} \newcommand{\mL}{\mat{L}} \newcommand{\mM}{\mat{M}} \newcommand{\mN}{\mat{N}} \newcommand{\mO}{\mat{O}} \newcommand{\mP}{\mat{P}} \newcommand{\mQ}{\mat{Q}} \newcommand{\mR}{\mat{R}} \newcommand{\mS}{\mat{S}} \newcommand{\mT}{\mat{T}} \newcommand{\mU}{\mat{U}} \newcommand{\mV}{\mat{V}} \newcommand{\mW}{\mat{W}} \newcommand{\mX}{\mat{X}} \newcommand{\mY}{\mat{Y}} \newcommand{\mZ}{\mat{Z}} \newcommand{\mLambda}{\mat{\Lambda}} \newcommand{\mPbar}{\bar{\mP}} \newcommand{\ones}{\vec{e}} \newcommand{\va}{\vec{a}} \newcommand{\vb}{\vec{b}} \newcommand{\vc}{\vec{c}} \newcommand{\vd}{\vec{d}} \newcommand{\ve}{\vec{e}} \newcommand{\vf}{\vec{f}} \newcommand{\vg}{\vec{g}} \newcommand{\vh}{\vec{h}} \newcommand{\vi}{\vec{i}} \newcommand{\vj}{\vec{j}} \newcommand{\vk}{\vec{k}} \newcommand{\vl}{\vec{l}} \newcommand{\vm}{\vec{l}} \newcommand{\vn}{\vec{n}} \newcommand{\vo}{\vec{o}} \newcommand{\vp}{\vec{p}} \newcommand{\vq}{\vec{q}} \newcommand{\vr}{\vec{r}} \newcommand{\vs}{\vec{s}} \newcommand{\vt}{\vec{t}} \newcommand{\vu}{\vec{u}} \newcommand{\vv}{\vec{v}} \newcommand{\vw}{\vec{w}} \newcommand{\vx}{\vec{x}} \newcommand{\vy}{\vec{y}} \newcommand{\vz}{\vec{z}} \newcommand{\vpi}{\vecalt{\pi}} \newcommand{\vlambda}{\vecalt{\lambda}}$

# Numerical Methods

## References

The class textbook
Numerical Methods by Anne Greenbaum and Tim Chartier
A fun reference
Insight through computing by Charles van Loan and K.Y. Daisy Fan

## Lecture 40

Newton's method, the secant method, the fixed point form of a nonlinear equation, and a review before the final midterm.

Chapter 4 Sections 4.3, 4.4.3, 4.5
Handout
Nonlinear equations (Pages 3, 4)
Slides
Lecture 40
Julia
Lecture 40 (html) (ipynb)
Notes
Lecture 40

## Lecture 39

Introduction to nonlinear equations

Chapter 4 Sections 4.1, 4.2
Handout
Nonlinear equations
Slides
Lecture 39
Julia
Lecture 39 (Bisection) (html) (ipynb)
Notes
Lecture 39

## Lecture 38

Stiff equations, Implicit methods, BVPs

Chapter 11 Sections 11.4
Chapter 13 Sections 13.1
Handout
Intro to BVPs
BVPs questions
Julia
Lecture 38 (Backwards Euler) (html) (ipynb)
Lecture 38 (BVPs) (html) (ipynb)
Slides
Lecture 38

## Lecture 37

Absolute stability, consistency, stability, convergence, local truncation error,

Chapter 11 Sections 11.4
Handout
Intro to ODEs (Pages 3-4)
Slides
Lecture 37
Julia
Lecture 37 (html) (ipynb)
Notes
Lecture 37

## Lecture 36

Solving ODEs on a computer.

Chapter 11 Sections 11.1, 11.2
Slides
Lecture 36
Handout
Intro to ODEs (Pages 1-2)
Julia
Lecture 36 (html) (ipynb)
Lecture 36 Example ODE (html) (ipynb)

## Lecture 35

We saw the error analysis of a Newton Cotes formula, and also looked at the error analysis of the piecewise trapezoidal rule. I mentioned Simpson's rule (or the three point Newton Cotes rule) see the book for more information.

Chapter 10.1,10.3
Slides
Lecture 35
Notes
Lecture 35

## Lecture 34

(QUIZ!) We continued talking about quadrature rules and looked at deriving Newton-Cotes formulas.

Chapter 10.1,10.3
Notes
Lecture 34

## Lecture 33

An introduction to numerical integration, the method of undetermined coefficients and quadrature.

Chapter 10.1,10.3
Slides
Lecture 33
Notes
Lecture 33

## Lecture 32

On the ill-conditioning of numerical differentiation, high dimensional polynomial interpolation, and how to analytically differentiate expressions for polynomials

Chapter 9 Chapter 8, 9
Slides
Lecture 32
Julia
Lecture 32 (html) (ipynb)
Notes
Lecture 32

## Lecture 31

The TA went over the last exam and quiz.

## Lecture 30

Error combos in numerical differentiation and Richardson extrapolation.

Slides
Lecture 30
Chapter 9 Section 9.1, 9.2
Julia
Lecture 30 (html) (ipynb)
Notes
Lecture 30

## Lecture 29

We saw truncation error for numerical differentiation and how to derive an accuracy estimate using Taylor series.

Chapter 9 Section 9.1
Slides
Lecture 29
Notes
Lecture 29

## Lecture 28

The quiz! Then we saw the Barycentric form of the Lagrange interpolant, as well as some error analysis. Finally, we briefly discussed piece-wise polynomial interpolation.

Chapter 8 Section 8.5
Slides
Lecture 28
Julia
Lecture 28 (html) (ipynb)

## Lecture 27

Today, we saw Lagrange interpolation.

Chapter 8 Section 8.1, 8.2
Handout
Polynomial Forms
Slides
Lecture 27
Notes
Lecture 27
Julia
Lecture 27 (html) (ipynb)

## Lecture 26

Introduction to applied mathematics and polynomial interpolation and ApproxFun

Chapter 8 Section 8.1, 8.2
Handout
Polynomial Approximation Intro
Slides
Lecture 26
Julia
Lecture 26 (html) (ipynb)
Lecture 26 (ApproxFun) (html) (ipynb)
Software
Chebfun and the Julia counter-part
ApproxFun

The midterm

## Lecture 24

We saw the power method convergence rate, the block power method, and then reviewed for the midterm.

Slides
Lecture 24
Notes
Lecture 24

## Lecture 23

We started covering eigenvalues of matrices and saw the basis for the power method..

Chapter 12 Section 12.1 (Eigenvalue methods)
Handouts
Eigenvalues (Pages 1-2)
Julia
Lecture 23 Eigenvectors of a string (html) (ipynb)
Slides
Lecture 23
Notes
Lecture 23

## Lecture 22

We finished our coverage of condition numbers for linear systems, saw matrix norms, and got a another brief intro to iterative methods. See the handout for much more detail.

Chapter 7 Section 7.4 (Conditioning)
Chapter 12 Section 12.2 (Iterative methods)
Julia
Lecture 21 Conditioning and Stability (html) (ipynb)
Handouts
Iterative methods
Slides
Lecture 22
Notes
Lecture 22

## Lecture 21

We finished up with least squares using the QR decomposition of a matrix. (This involved a quick study of orthogonal matrices and how they generalize the notion of a rotation.) We had a quick aside about iterative methods for linear systems that gets you to where you need to be for the homework, then we dove into conditioning and stability.

Chapter 7 Section 7.6 (Least squares)
Gram-Schmidt process
Chapter 7 Section 7.4 (Conditioning of linear systems)
Handouts
Iterative Methods
Conditioning and Stability
Julia
Lecture 21 Conditioning and Stability (html) (ipynb)
Slides
Lecture 21
Notes
Lecture 21

## Lecture 20

Today we continued our coverage of least squares problems
and the geometry of a simple example; and the QR factorization
of a matrix and it's relationship to Gram-Schmidt

Chapter 7 Section 7.6 (Least squares)

Gram-Schmidt process

Slides
Lecture 20
Handouts
Intro to Least Squares

## Lecture 19

Today we covered PageRank as a linear system and least squares problems

Chapter 7 Section 7.6
Slides
Lecture 19
Julia
Lecture 19 Galileo's problem (html) (ipynb)
Handouts
PageRank as a linear system
Intro to Least Squares

## Lecture 18

We counted the number of operations in Gaussian Elimination and saw the midterm and saw an important property of LU. See the slides and the videos online.

Chapter 7 Section 7.3
Slides
Lecture 18
Handouts
Flops in LU

## Lecture 17

We saw code for Gaussian Elimination with LU and Pivoting.

Chapter 7 Section 7.3
Slides
Lecture 17
Julia
Lecture 17 (html) (ipynb)
Notes
Lecture 17

## Lecture 16

We went over Linear Systems of equations, where they come from, and how to use Gaussian Elimination and the LU factorization to solve them! In class next time, we will see code to implement these operations in Julia

Chapter 7 Section 7.2
Julia
Lecture 16 (html) (ipynb)
Notes
Lecture 16

## Lecture 15

This was the memory hierarchy and high-performance matrix matrix multiplication.

HowToOptimizeGEMM
Memory hierarchy
Slides
Lecture 15
Notes
Lecture 15

## Lecture 14

Today, we saw an introduction to matrix methods, why they are important, where they occur, and an brief introduction to matrix-matrix multiplication

Chapter 7 Section 7.0, 7.1
Chapter 2
Chapter 1
Slides
Lecture 14
Notes
Lecture 14

## Lecture 13

The first midterm!

## Lecture 12

We reviewed the class so far! This included a briefly summary of topics, a review of HWs 1 and 2, and a set of potential questions for the midterm.

Slides
Lecture 12

## Lecture 11

We reviewed the problems on the Quiz. Then we went back into Monte Carlo methods and gave a visual explanation for how Monte Carlo integration works. This then led to a discussion of how to compute the variance properly

Chapter 3
Slides
Lecture 11
Julia
Lecture 11 (Monte Carlo) (html) (ipynb)
Lecture 11 (Variance) (html) (ipynb)

## Lecture 10

We reviewed some of the basics of probability, random variables, and expectations. We saw how to compute Pi via a Monte Carlo method, and saw how to turn an integral into an expectation so we can use Monte Carlo. Then we saw the CLT.

Chapter 3
Slides
Lecture 10
Notes
Lecture 10

## Lecture 9

Introduction to Monte Carlo methods via three examples: the Monty Hall problem, a pop-quiz on a property of the unit circle, and Google's PageRank problem.

Chapter 3
Slides
Lecture 9
Julia
Lecture 9 (Monty Hall) (html) (ipynb)
Lecture 9 (Circle points) (html) (ipynb)
Lecture 9 (PageRank random surfer) (html) (ipynb)

## Lecture 8

Today we had a quiz on floating point arithmetic and then we saw a few guidelines on how to ensure good floating point computations; and why you must always be careful!

Chapter 5
Once dead by Richard Phillips (See intro to Chapter 55, page 208)
Julia
Lecture 8 (Accurate norms) (html) (ipynb)
Slides
Lecture 8

## Lecture 7

Today we covered how computers do floating point arithmetic, IEEE rounding modes, and the guarantees of IEEE floating point arithmetic.

Chapter 5 - Section 5.5 and 5.6
The mathematics of the Intel Floating Point Bug
Numerical Computing with IEEE Floating Point Arithmetic by Michael Overton
Julia
Lecture 6 (Floating point numbers) (html) (ipynb) (Holdover from last time!)
Slides
Lecture 7
Notes
Lecture 7

## Lecture 6

Today, we saw an intro to floating point arithmetic.

Slides
Lecture 6
Notes
Lecture 6
Chapter 5

## Lecture 5

We did a quick intro to Latex, and more Julia including control flow, function, and plotting. Then we did a review of the Quiz.

Slides
Lecture 5
Julia
Lecture 4 (control flow examples) (html) (ipynb)
Lecture 5 (plotting) (html) (ipynb)
Lecture 5 (functions) (html) (ipynb)
Lecture 5 (functions, filled-in) (html) (ipynb)
Lecture 4 (script) (html) (ipynb)
Latex
Simple Latex Document
Simple Latex Document Compiled
Edited Homework 1
Edited Homework 1 Compiled
Edited Homework 1 Extra Files

## Lecture 4

In this lecture, we did a long intro the to the julia language.

Slides
Lecture 4
Chapter 2 (but using our Julia conversion below)
Chapter 2 converted: Using Julia (html) (ipynb)
Chapter 2 converted: Plotting in Julia (html) (ipynb)
Julia
Lecture 4 (control flow examples) (html) (ipynb)

## Lecture 3

We had a quiz and saw how to use the Julia language.

Slides
Lecture 3
Chapter 2
Julia
Chapter 2 converted: Using Julia (html) (ipynb)
Chapter 2 converted: Plotting in Julia (html) (ipynb)
Lecture 3 in class commands (html) (ipynb)

## Lecture 2

We reviewed what happens in mathematical modeling and how we take a problem from an initial statement into a compute model. We saw two examples: the XKCD Raptor Problem as well as Google's PageRank problem.

Slides
Lecture 2
Notes
Lecture 2
Chapter 1
Julia
Lecture 2: The XKCD Raptor Problem (html) (ipynb)

## Lecture 1

We reviewed the syllabus, and saw the importance of computing.

Slides
Lecture 1