-> 20250918_NumCSE_Eigen_cheatsheet
-> HS2025_tasks

Exercises

• 0.1
• 0.2
• 0.3

• 1.1
• 1.2
• 1.3
• 1.4
• 1.5
• 1.6
• 1.7
• 1.8
• 1.9
• 1.10
• 1.11
• 1.12
• 1.13
• 1.14

• 2.3
• 2.5 (solved sloppily, with ChatGPT / solutions)
• 2.13

• 3.1
• 3.2
• 3.6

• 4.1
• 4.5
• 4.6
• 4.7
• 4.8

• Problem 4-4: Solving triangular Toeplitz systems (220 min)
• Problem 5-2: Largrange Polynomials (60 min)
• Problem 5-13: Various Aspects of Interpolation by Global Polynomials (35 min)
• Problem 5-16: Some Aspects of Interpolation by Global Polynomials (35 min) !!important task
• Problem 5-18: Polynomial Interpolation based on Newton basis (60 min) (done with ChatGPT)

• Problem 5-1: Evaluating the derivatives of interpolating polynomials (135 min)
• Problem 6-6: Polynomial Best Approximation (35 min)
• Problem 6-9: Finding domains of analyticity (45 min)
• Problem 6-3: Adaptive polynomial interpolation (105 min)

week8

• Problem 6-8: Monomial representation of Chebychev polynomials (30 min)
• Problem 6-10: Convergence of Chebychev Interpolants (70 min)
  • look at solution again for b) https://people.math.ethz.ch/~grsam/NumMeth/HOMEWORK/6-10-2-1:.pdf
• Problem 6-5: Chebychev interpolation of analytic functions (130 min) (quite tricky, especially f))
• Problem 6-1: Piecewise linear approximation on graded meshes (170 min)

week9

• Problem 7-1: Smooth integrand by transformation (115 min) (I understood this task and it was quite fun)
• Problem 7-18: Regularizing Transformation (95 min)
• Problem 7-3: Numerical Quadrature of Improper Integrals (75 min)
• Problem 7-12: Clenshaw-Curtis-Fejer Quadrature Formula (130 min)
  • d) really tricky (derive + compute nodes, weights using FFT)

week 10

• Problem 7-14: Aspects of Numerical Quadrature (65 min)
  • would be nice to discuss d) with Prof. Hiptmair -> done in Q&A 2025-11-24, ca. at 30.00
• Problem 7-5: Quadrature Error Plots (30 min)
  • write result on cheatsheet -> comparison of different Q.R. -> see Q&A 2025-11-24 (als written down in [[#Q&A]])
• Problem 7-16: On Quadrature Formulas (30 min)
  • explain b)
• Problem 7-17: Quadrature Formulas (60 min) (more like 30min; not sure about b))
• Problem 7-15: Convolution Quadrature (125 min)

week 11

• Problem 8-1: Convergent Newton iteration (25 min) (nice and simple)
• Problem 8-4: A derivative-free iterative scheme for finding zeros (85 min)
  • d) understood the idea, but not the execution
• Problem 8-8: Julia Set (105 min)
• Problem 8-10: Solving a quasi-linear system (130 min)

problem 12

• Problem 8-16: Periodic Collocation for a Non-Linear Differential Equation (95 min)
  • running program -> ok; running tests -> failed
• Problem 8-11: Radioactive Decay (95 min)
• Problem 8-15: Non-linear Least Squares Location Estimation (100 min)

Videos

week 1

• 1.1.1 Notations (6 min)
• 1.2.1 Eigen (11 min)
• 1.2.3 (Dense) Matrix Storage Formats (9 min)
• 1.4 Computational Effort (28 min)
• 1.5 Machine Arithmetic and Consequences (15 min)
• 1.5.4 Cancellation (21 min)
• 1.5.5 Numerical Stability (17 min)

week 2

• 2.1 Introduction: Linear Systems of Equations (LSE) (5 min)
• 2.1.0.3. Nodal Analysis of Linear Circuits (7 min)
• 2.2.2 Sensitivity of Linear Systems (15 min)
• 2.3 Gaussian Elimination & 2.5 Survey: Elimination Solvers for Linear Systems of Equations (16 min)
• 2.6 Exploiting Structure when Solving Linear Systems (17 min)
• 2.7.1 Sparse Matrix Storage Formats (10 min)
• 2.7.2 Sparse Matrices in Eigen (6 min)
• 2.7.3 Direct Solution of Sparse Linear Systems of Equations (9 min)

week 3

• 3.0.1 Overdetermined Linear Systems of Equations: Examples (12 min)
• 3.1.1 Least Squares Solutions: Definition (8 min)
• 3.1.2 Normal Equations (16 min)
• 3.1.3 Moore-Penrose Pseudoinverse (7 min)
• 3.2 Normal Equation Methods (12 min)
• 4.1.1 Discrete Finite Linear Time-Invariant Causal Channels/Filters (21 min)
• 4.1.2 LT-FIR Linear Mappings (24 min)
• 4.1.3 Discrete Convolutions (17 min)
• 4.1.4 Periodic Convolutions (24 min)

week 4

• 4.2.1 Diagonalizing Circulant Matrices (33 min)
• 4.2.2 Discrete Convolution via Discrete Fourier Transform (13 min)
• 4.2.3 Frequency filtering via DFT (40 min)
• 4.2.5 Two-dimensional DFT (38 min)
• 4.3 Fast Fourier Transform (FFT) (29 min)
• 4.5 Toeplitz Matrix Techniques (20 min)

week 5

• 5.1 Abstract Interpolation (AI) (16 min)
• 5.2 Global Polynomial Interpolation (6 min)
• 5.2.2 Polynomial Interpolation: Theory (5 min)
• 5.2.3 Polynomial Interpolation: Algorithms (17 min)
• 5.2.3.3 Extrapolation to Zero (12 min)
• 5.2.3.4 Newton Basis and Divided Differences (16 min)
• 5.2.4 Polynomial Interpolation: Sensitivity (13 min)

week 6

• 6.1 Approximation of Functions in 1D: Introduction (7 min)
• 6.2.1 Polynomial Approximation: Theory (13 min) (solved review questions)
• 6.2.2 Error Estimates for Polynomial Interpolation (13 min) (solved review questions)
• 6.2.2.2 Interpolands of Finite Smoothness (17 min) (solved review with chatgpt)
• 6.2.2.3 Analytic Interpolands (27 min)

week 7 (no review quesitons solved)

• 6.2.3.1 Chebychev Interpolation: Motivation and Definition (10 min)
• 6.2.3.2 Chebychev Interpolation: Error Estimates (14 min)
• 6.5.1 Approximation by Trigonometric Interpolation (5 min)
• 6.5.2 Trigonometric Interpolation Error Estimates (14 min) (didn't quite understand)
• 6.6.1 Piecewise Polynomial Lagrange Interpolation (17 min)

week 8 (no review quesitons solved)

• 7.1 Numerical Quadrature: Introduction (4 min)
• 7.2 Quadrature Formulas – Quadrature Rules (13 min)
• 7.3 Polynomial Quadrature Formulas (8 min)
• 7.4.1 Order of a Quadrature Rule (8 min)
• 7.4.2 Maximal-Order Quadrature Rules (16 min)
  • look again at proofs (there are 3 of them), might be important
• 7.4.3 Quadrature Error Estimates (18 min)

week 9 (no review questitons solved)

• 7.5 Composite Quadrature (18 min)
• 7.6 Adaptive Quadrature (13 min)
• 8.1 Iterative Methods for Non-Linear Systems of Equations: Introduction (5 min)
• 8.2.1 Fundamental Concepts (6 min)
• 8.2.2 Speed of Convergence (15 min)
• 8.2.3 Termination Criteria/Stopping Rules (14 min)
• 8.3 Fixed-Point Iterations (12 min)

week 10

• 8.4.1 Finding Zeros of Scalar Functions: Bisection (6 min)
• 8.4.2.1 Newton Method in the Scalar Case (20 min)
• 8.4.2.3 Multi-Point Methods (12 min)
• 8.4.3 Asymptotic Efficiency of Iterative Methods for Zero Finding (9 min)
• 8.5.1 The Newton Iteration in Rn (I) (10 min)
• 8.5.1.15 Multi-dimensional Differentiation (20 min)
  • look at pedestrian way
• 8.5.1 The Newton Iteration in Rn (II) (15 min)
• 8.5.2 Convergence of Newton’s Method (9 min)
• 8.5.3 Termination of Newton Iteration (7 min)
• 8.5.4 Damped Newton Method (11 min)

week 11

• 8.6 Quasi-Newton Method (15 min)
• 8.7 Non-linear Least Squares (7 min)
• 8.7.1 Non-linear Least Squares: (Damped) Newton Method (13 min)
• 8.7.2 (Trust-region) Gauss-Newton Method (13 min)
• 11.1 Initial-Value Problems (IVPs) for Ordinary Differential Equations (35 min)

week 12

• 11.2 Introduction: Polygonal Approximation Methods (17 min)
• 11.3. General Single-Step Methods (14 min)
• 11.3.2 (Asymptotic) Convergence of Single-Step Methods (20 min)
• 11.4 Explicit Runge-Kutta Single-Step Methods (27 min)
• 11.5 Adaptive Stepsize Control (32 min)

Midterm

• HS22 - 0.2 nicht relevant, 0.1 nochmals anschauen; ansonsten gut machbar
• [ ]

Q&A

#timestamp 2025-11-24
Q&A Week 11

Vorlesung

#timestamp 20250918

Video 1.4: Complexity introduction, tricks to improve complexity

tricks to improve complexity

• exploit associativity

• hidden summation

but $y_i=\sum _{j\ge i}{a}_i{b}_j{x}_j=a_i\sum _{j\ge i}{b}_j{x}_j$

• reuse of intermediate results

Video 1.5: Machine numbers, relative errors, gram-schmidt orthogonalisation

Video 1.5.4 cancellation + how to avoid

cancellation in difference quotients

-> cancellation in numerator
-> divided by tiny h -> error "blows up"

#todo look at Vieta's formula

#todo where to find review questions?

Video 1.5.5 Numerical Stability

Problem $\widehat{=}$ function/mapping from data to result space (usually normed vector space)

stable algorithm $\widehat{=}$ an algorithm, which gives a slightly perturbed result. The result has to be reachable by the problem (which is exact) from a slightly perturbed data(point), near the exact data. This has to be true for every data(point)

Video 2.1

square LSE -> uniqueness of solution, if $A$ invertible / A regular / $det(A)\ne 0$ / cols lin. indep. / rows lin. indep.

(do not use matrix inversion function to solve LSE with numerical libraries)

Video 2.1.0.3

Video 2.2.2 Sensitivity/Conditioning of LSE

quantifies how small (relative) perturbation of data lead to changes of the output

condition of a matrix $A\in {\mathbb{R}}^{n\times n}$:

$\text{cond}(A)\approx 1$: LSE well-conditioned
$\text{cond}(A)\gg 1$: LSE ill-conditioned (result relatively useless)

if condition number of matrix is very large, it's columns/rows are almost linearly dependent ($\widehat{=}$parallel)

Video 2.3 Gaussian Elimination (GE), LU-decomposition

• Gaussian eleminitaion -> $n^3$
• LU-Decomposition -> $n^3$

-> three-stage splitting of GE

X = A.lu().solve(B)

Video 2.6 Exploiting structure when solving linear systems

Video 2.7.1 sparse matrix: how to store

Video 2.7.2 sparse matrices in Eigen

standard CRS/CSS format

#include<Eigen/Sparse>
Eigen::SparseMatrix<int, Eigen::RowMajor> Bsp(rows, cols);

#initalise
std::vector <Eigen::Triplet<double>> triplets;
Bsp.setFromTriplets(triplets.begin(), triplets.end());

alternative: allocate enough space at start (see 2.7.2.1) / squeeze out zeroes -> slightly more effizient than triplets, but the non-zero data size is not always known in advance

Video 2.7.3 direct solutions of sparse LSE (LGS)

mat.solve(vec);
// note: matrix is
Eigen::SparseLU<Eigen::SparseMatrix<double>> mat;

-> sparse solution is stable

(sparse elimination for combinatorial graph laplacian: asymptotic runtime $\mathcal{O}(n^{1.5})$)

=> in practice: Cost(sparse solution of $A\overrightarrow{x}=\overrightarrow{b}$) = $\mathcal{O}((nnz(A){)}^{\alpha })$, $\alpha \approx 1.5-2.5$

Video 3.0.1 Overdetermined linear systems

Video 3.1.1 Least squares solution

idea: find vector $\overrightarrow{\tilde{x}}$ for $A\overrightarrow{x}=\overrightarrow{b}$, s.t. the residual $r:=\overrightarrow{b}-A\overrightarrow{x}$ is as small as possible

notation: lsq(A,b) $:=x\in {\text{argmin}}_{y\in {\mathbb{R}}^n}||Ay-b|{|}_2^2$

• least square solutions always exists

Video 3.1.2 solving least square problems

Video 3.1.3 Moore-Penrose-Pseudoinverse

LSQ solution not unique:

• FRC is violated $⟺\text{rank}(A)<n⟺\mathcal{N}(A)\ne \{0\}$

-> Additional selection criterium:

4.1 Filters and Convolutions

Video 4.1.1 Filters and Convolutions

discrete finite linear time-invariant casual channels/filters

• finite: it stops after some time
• time-invariant: the result does not change if it arrives now or 1min later
• linear: addition + multiplication with scalar
• casual: output only after onset of input

Video 4.1.2 LT-FIR linear Mappings + convolutions

• convolutions are commutative

Video 4.1.3 Discrete Convolutions

Video 4.1.4 Periodic convolutions

Video 4.2.1 Diagonalizing circulant matrizes

n-th root of unity

• the scaled fourier matrix $\frac{1}{\sqrt{n}}{F}_n$ is unitary:

• the fourier matrix diagonalizes circulant matrices

Video 4.2.2 Discrete Convolution via DFT

Eigen::FFT<double> fft;
fft.inv(
	(
		(fft.fwd(u)).cwiseProduct(fft.fwd(x))
	).eval()
)

explanation:

Video 4.2.3 Frequency filtering via DFT

Video 4.2.5 Two dimensional DFT

Video 4.2 FFT

Video 4.5 Toeplitz Matrix Techniques

Toeplitz matrices:

• data sparse (not sparse)

Video 5.1 AI (Abstract Interpolation)

get unique solution $\mathrm{\forall }y$ only if $m=n$ (matrix square)

if $A$ square, regular => can write Interpolant as linear combination of basis functions

interpolant can be recovered by forming a matrix-vector product

#todo write down end of video

Video 5.2 Uni-Variate Polynomials

Polynomials form a Vectorspace with

convention for storing polynomials:

Video 5.2.2 Polynomial Interpolation Theory

B1 - Lagrangian basis
B2 - Newton basis
B3 - monomial basis

Video 5.2.3 Polynomial Interpolation Algorithms

$\mathcal{O}(\underset{construction}{\underbrace{n^2}}+\underset{\text{eval()}}{\underbrace{N\cdot n}})$

-> adding one more point ($\widehat{=}$ one diagonal) $\mathcal{O}(n)$

Video 5.2.3.3 Extrapolation to Zero

Video 5.2.3.4 Newton Basis

Homer-like scheme

Video 5.2.4 Polynomial Interpolation: sensitivity

sensitivity: amplification of perturbation of data (of a problem)

-> tiny errors will have huge impact on the interpolation result
-> not suitable for data interpolation

6. Approximations of functions in 1D

Video 6.1 Introduction

in 5: create function to combine data points
in 6: find easier function, because 5 too costly

-> find simple (easy to evaluate) function with small approximation error (norm)

Video 6.2.1 Polynomial approximation: theory

bernstein theorem: if $f$ nearly continuous -> can be approximated by polynomial

• but not how close, how fast -> dissapointing

jackson theorem: Max-norm of best-approximation error

how to move from interval $[-1,1]$ to $[a,b]$:

• max norm stays same
• perserves degree of polynomials
• derivative: change uniformly

Video 6.2.2 Convergence of interpolation errors

what can you tell from algebraic divergence?
-> how to increase polynomial degree to achieve certain reduction of error

Video 6.2.2.2 Interpolands of finite smoothness

Runge's Counterexample: $f(t)=\frac{1}{1+t^2}$, $I=[-5,5]$ -> approximation has exponential blow-up of error

${\tau }_t$ is not known, so usually we use the lest tight bound with the max norm:

Video 6.2.2.3

real analytic function
-> if has convergent taylor series for every point in interval $I$

Video 5.2.3.1 Chebychev Interpolation

The $n$-th Chenychev polynomial is

Video 5.2.3.2 Chebyshev INterpolation Error Estimates

equidistnt nodes affected by oscillations close to endpoints

Lebeseque links best approximation error and interpolation errors

Lebesque constant for Chebychev nodes:

-> increase verys slowly

(compare with equid. nodes: ${\lambda }_{\tau }\ge C{e}^{n/2}$)

trick: plug in lebesque constant in between interpolation error and best approximation error

Suitebla integration path: elippsis around $[-1,1]$:

$\rho >1$
-> cos, to cancel out with chebyshev polynomials

for chebyshev polynomials for analytic functions

slower for smaller domain of analyticity $D\in \mathbb{C}$

Video 6.5 Approximation by Trigonometric Polynomials

space of 1-periodic functions of trigonometric functions of degree 2n

Video 6.5.2 Trigenometric Interpolation Error Estimates (fourier series)
#todo didn't quite understand the video

-> ${\hat{c}}_j$ bounded

Video 6.6.1 Piecewise Polynomial Lagrange Interpolation

approximation by piecewise polynomials

piece-wise polynomials; benefit:

• locality
• cheap algorithm
• shape preservation

$H$: mesh

lagrange interpolation for function that is $n+1$ times continously differentiable ($C^{n+1}$)

for mesh width $\to$ 0 ($h_m{\to }_0$) we have algebraic convergence with rate $n+1$

7. Numerical Quadrature

Video 7.1 Introduction

Numerical Quadrature (Integration)

Video 7.2 Quadrature Formulas Rules

$f$ given in procedural form

double f(double)

transformation:

interpolation schemes (5) -> approximation schemes (6) (simple functions) -> quadrature schemes (7)

quadrature erros can often be computer easily, especially for quadrature rules arising from interpolation schemes

(bounded by max norm of interpolation error)

Video 7.3 Polynomial Quadrature Formulas

Use Lagrangian polynomial interpolation

• midpoint rule

• trapezoidal rule

solution:

• chebyshev nodes -> no cancellation, since weights $w_j>0$

error estimates for polynomial quadrature:

Video 7.4.1 Gauss Quadrature / Order of a Quadrature Rule

order of polynomial n-pt. quadrature rule = n, since n-1 polynomail -> n+1 of that order of quadrature rule

7.4.1.7: how to compute weights to achieve order n by solving a suitable linear system:

-> solve weights to get quadrature rule of at least order $n$

Video 7.4.2: Maximal-Order Quadrature Rules

how to find maximum order quadrature rule?

how to find n-point quadrature rule of order 2n?

Note that Hiptmair mostly proves lemmas indirectly.

Video 7.4.3 Quadrature Error Estimates

very important property for quadrature error:

from chapter 6);

• limithed smoothness of f: ($f\in C^r([a,b])$, but $f\notin C^{r+1}([a,b])$):
  algebraic convergence with rate r ($\mathcal{O}(n^{-r})$)
• analytic $C^{\mathrm{\infty }}$-integrand (analytic extension):
  exponential convergence ($O(q^n)$)

restoring smoothness (removing singularity by transformation):

• integration by substitution (e.g. $\sqrt{t}$ -> gets analytic) (more art than science, but can often be used)

The message of asymptotic estimates:

• tell us how much additional work ~ n is needed to reduce Error by factor
• algebraic convergence:
  
• exponential convergence:
  
  -> adavantage of exponential convergence: needs fixed amount of points to reduce error by factor

Eigen::ArrayXd::LinSpaced(n,a,b)

builds a sequence of $n$ values

Video 7.5 Composite Quadrature

split interval into mesh, integrate very mesh individually
-> cost = number of mesh cells (* integral)

good approximation for local error:

"h-covergence": convergence by making mesh finer

-> for equidistant meshes, use Gauss-Legendre Q.R. instead of composite quadrature
-> for trigonometric polynomials (periodic functions):

with

best approximation error estimeted by triag.pol.:

Video 7.6 Adaptive Quadrature (13 min)

goal: choosing mesh such that local errors are equidistribution
-> choose mesh a priori (based on prior knowledge about f) (often not known)
-> choose mesh a posteriori (automatic based on informatio gained during the computation)

with initial mesh $M=\{x_j{\}}_{j=0}^m$

1. compute estimate for each mes cell: (simpson - trepezoidal Q.R.)
2. sum up to get estimate for total error
3. if error too large, find intervals contribute above average to the total error
4. add their midpoints to the new refined mesh. start anew.

8. Iterative Methods for Non-linear Systems of Equations

Video 8.1 Iterative Methods for Non-Linear Systems of Equations: Introduction (5 min)

form:

• n number of unknowns/equations
• no general theory
• F often only implicit

8.2 Iterative Methods

Video 8.2.1 Fundamental Concepts (6 min)

solve by "getting closer and closer" iteratively
-> will this solution converge?

m-point method:

-> insert last $m$ iterates to get next one

• start with initial $m$ guesses:
  

consistent: vector at which iteration becomes stationary -> vector must be solution

-> consequence: assume

• limit of sequence exists ($\overrightarrow{x}$ cvgt.)
• iteration function consistent (${\varphi }_F$ consistent)
• iteration function continuous on all arguments (${\varphi }_F$ continous)

=>

local convergence:

• cvg. will heavily depend on initial guess

Video 8.2.2 Speed of Convergence (15 min)

How fast will the norm converge?

smallest L: rate of cvg.

Detect linear convergence:

• p=1 -> linear convergence
• C usually unknown

Detect p$>1$ convergence:

quadratic convergence (p=2): doubling of correct digits in each step

Video 8.2.3 Termination Criteria/Stopping Rules (14 min)

Ideal stopping rule:
stop iteration if prescribed absolute or relative tolerance reacher
-> not working, since exact value not known

practical stopping rules

• A priori termination -> STOP after a fixed no. of steps
• Residual-based termination -> STOP, when $||F({\overrightarrow{x}}^k)||\le \tau \widehat{=}$ prescribed tolerance
  • tells us little about $|x-x^{\ast }|$
    
• Correction-based termination -> stop convergent iteration, when correction stops changing much
  

error estimate:

-> Reliable error estimate, even if we only know upper bound $\bar{L}$, $L\le \bar{L}<1$

8.3 Fixed-Point Iterations

Video 8.3 Fixed-Point Iterations (12 min)

we do not always know $x^{\ast }$, so assume:

Video 8.4.1 Finding Zeros of Scalar Functions: Bisection (6 min)

find $x^{\ast }\in \mathbb{R}$ with $F(x^{\ast })=0$

Idea: geometrically decrease interval
-> linear convergence, factor $\frac{1}{2}$

+ guaranteed cenverence -> robust
+ F - only evluations needed -> procedural ok
+ derivative-free
+ works $\mathrm{\forall }$ continuous $F$
- not extremely fast

Video 8.4.2.1 Newton Method in the Scalar Case (20 min)

Idea: replace function locally around $x^{(k)}$ with a simpler method $F(x)\approx F_k(x)$

Newton: use tangent on $x^{(k)},F(x^{(k)})$

Ex. 8.4.2.4: functions with same $x^{\ast }$ may have different Newton iterations -> advantageous to first recast function before calculating Newton iteration

Find $F^{\prime }(x)$ implicit with implicit differentiation

If (F) is hard to solve but close to an easily invertible $\hat{F}$, define

Then $F(x)=0⟺G(x)=0$, and $G$ is almost linear.
Newton on (G) converges faster and from farther away because the preconditioning makes the problem closer to the identity map.

Video 8.4.2.3 Multi-Point Methods (12 min)

secant method:

• replaces derivative in Newton's method by quotient
• 2-point method, requires 2 initial guesses
• derivative-free
• one F-evaluation per step
• if function flat, breaks down
• fractional convergence with p$\approx$ 1.62

-> secant method more efficient (see 8.4.3) than Newton method!

8.4 Finding Zeros of Scalar Functions

Video 8.4.3 Asymptotic Efficiency of Iterative Methods for Zero Finding (9 min)

lower bound for number of required steps:

8.5 Newtons Method in ${\mathbb{R}}^n$

Video 8.5.1 The Newton Iteration in Rn (I) (10 min)

The standard method for solving (generic) non-linear systems of equations.

Newton method if affine invariant (invariant to multiplicaiton with matrix from left)
-> should also be desireable for stopping rules

Video 8.5.1.15 Multi-dimensional Differentiation (20 min)

Matrix * Vector is general way to write linear mapping ${\mathbb{R}}^n\to {\mathbb{R}}^n$


bilinear $\widehat{=}$ linear in every argument

Video 8.5.1 The Newton Iteration in Rn (II) (15 min)

Simplified Newton method: $\mathcal{O}(n^2)$ instead of $\mathcal{O}(n^3)$ from solving LSE by "freezing" Jacobian

• Drawback: usually sacrifices the asymptotic quadratic convergence of the Newton method: merely linear convergence can be expected.

#todo look video again to understand better

Video 8.5.2 Convergence of Newton’s Method (9 min)

Convergence of Newton's method:
$n=1⟹$ local quadratic cvg.

Video 8.5.3 Termination of Newton Iteration (7 min)

terminate, when $||x^{(k)}-x^{\ast }||$ small

=> $||x^{(k)}-x^{\ast }||\approx ||x^{(k)}-x^{(k+1)}||$, but unnecseeary iteration k+1 ($\mathcal{O}(n^3)$)

-> affine invariant: does not change when

Video 8.5.4 Damped Newton Method (11 min)

=> goal: enlarge domain of cvg.

• Newton correct in the wrong direction -> no remed
• "Overshooting" Newton correction -> apply damping

if quadratic cvg. =>

if NMT (natural monotonicity test) fails

• $\lambda \leftarrow \frac{\lambda }{2}$ & retry
  if passed
• next step, (8.5.4.2), $k\leftarrow k+1$
• $\lambda \leftarrow 2\lambda$ in next step

-> works, because of affine invariant property of Newton method

8.6 Quasi-Newton Method

Video 8.6 Quasi-Newton Method (15 min)

Drawback of Netwon method: DF required

• Goal: Derivative-free iteration of NLSE
• for $n=1$: Secant method, 8.4.2.3

• replaces $DF(x^{(k)})$ (Jacobian) with difference quotient approximation $J_k\in {\mathbb{R}}^{n,n}$

$(BC)+(SC)$ unique determine $J_k$

• No asymptotic quadratic cvg. for Broyden's quasi-Newton method (but still faster than e.g. simplfied Newton)
• rank-1-modification

for $k=1$ (see also problem 8.10)d) from week 11), the Sherman-Morrison-Woodbury formula can be simplified to:

1. solve $n\times n$ LSE
2. vector arithmetic from then on (very cheap)

can have stability problems! (because of SMW-formula)

8.7 Non-linear Least Squares

Video 8.7 Non-linear Least Squares (7 min)

minimize Euclidean norm of residual (same as linear case)

• forefactor $\frac{1}{2}$ only convention
• More general version of the linear least squares problem

linear case:

linear combination of basis function

non-linear case:

Video 8.7.1 Non-linear Least Squares: (Damped) Newton Method (13 min)

with $F\in C^2$, $\varphi :{\mathbb{R}}^n\to \mathbb{R}$

then the LSE for Newton crrection $\overrightarrow{s}\in {\mathbb{R}}^n$ is:

-> normal equation in case $F(x)=Ax-b$ (see paper notes W11)

Video 8.7.2 (Trust-region) Gauss-Newton Method (13 min)

Advantages over Newton-method:
+ 2nd-derivativ free
+ Larger domain of cvg.
- no local quadratic cvg.

-> no global cvg., but we can also use damping (called trust region Method $\widehat{=}$ implicitly damped Gauss-Newton method)

11. Numerical Integration - Single Step Methods

Video 11.1 Initial-Value Problems (IVPs) for Ordinary Differential Equations (35 min)

• for autonomous ODE, choosing initial time $t_0=0$ is natural
• time invariant -> wa can always fix initial time $t_0=0$ without loosing generality

time-dependent ODEs can be converted to autonomous ODEs

conversion: from higher-order ODEs for first-order ODEs

• for initial-value problem, we have to specify initial values for both $y,\dot{y},\dot{y}\dot{},\dots$ for the first-order ODE

left:

• trajectory of single initial point moving through space
• fix starting point, vary time

right:

• a set of points move through space, with evolution operators ${\varphi }^1,{\varphi }^2,\dots$
• time fixed, look how all spatial points move

=> as time progresses, the evolution operator takes a "part of the space" and "flows" it forward

Recovering the ODE from the Flow: the vector field $f(y)$ (which defines the differential equation) is simply the initial velocity of the evolution operator.

• for Autonomous ODE, we have the group property: