links - NumCSE

-> Feedback zu programmieraufgaben: 20260224_NumCSE_Prüfungskorrektur

Info

  • exam
    • NumCSE midterm: Monday 10:15 - 11:00, HG G 19.1 (@2025-10-27)
    • NumCSE endterm: Monday 10:15 - 11:00, HG G 19.1 (@2025-12-15)
    • NumCSE final exam:
    • mid+endterm: 10min reading + 30min writting; closed-book; optional
    • final exam: 30min reading + 180min writing; open-book; codeExpert + paper
  • exercises

  • practice classes

Hilfsmittel NumericalMethodsForCSE

  • final exam: [course script, Eigen documentation, C++ documentation]
  • mid-/endterm (optional for bonus): closed book

Quote

The course content is quite interesting, but the material is really chaotic. Subsubsubsubsections, missing links, wrongly named files, incoherent structure, overly detailed script - it really does not help that on top of all that, the curse is teached in a flipped classroom mode. The course is far too much effort for only 9 credits, but it is probably the most important course for CSE, so I would recommend to pay attention and try to do as much as possible.

This is after submitting last exercise of the course, after the last week of the semester: From 60 (60!) people, only 3 completed the last exercises - most gave up after (~12) weeks (before the endterm).

-> 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)
  • 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)

week 13

  • Problem 11-3: Extrapolation of evolution operators (125 min)
  • Problem 11-2: Explicit Runge-Kutta methods (100 min)
  • Problem 11-4: System of second-order ODEs (90 min)
  • Problem 11-5: Non-linear Evolutions in Spaces of Matrices (80 min)

week 14

  • [ ]

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) (review question a) done)
  • 11.3.2 (Asymptotic) Convergence of Single-Step Methods (20 min) (review question 11.3.1.17)a) done)
  • 11.4 Explicit Runge-Kutta Single-Step Methods (27 min) (done all review questions)
  • 11.5 Adaptive Stepsize Control (32 min) (done all review questions)

week 13

  • 12.1 Model Problem Analysis (40 min)
  • 12.2 Stiff Initial-Value Problems (24 min)
  • 12.3 Implicit Runge-Kutta Single-Step Methods (50 min)
  • 12.4 Semi-Implicit Runge-Kutta Methods (13 min)
  • 12.5 Splitting Methods (21 min)

Midterm

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

Q&A

timestamp 2025-11-24 Q&A Week 11

Compisute quadrature rules vs global Gauss quadrature

When choosing quadrature rule, always first consider Gauss (global)

  • benefits from function smoothness / analyticity
  • if , but M-p.w. smooth (piece-wise in Mesh cells, only non-linear at Mesh nodes) -> composite Q.R. will cvg. alg. with max rate -> use composite Q.R.
  • equidistant trapezoidal rule is exact for trigonometric polynomials (periodic functions)

Equidistant TR cvg. exponentially for periodic integrands

  • integrand has anlytic extension (on beyond integration interval)
  • integration is over a period

timestamp 2025-12-03 Q&A Week 12

Quote

I don’t have the result on my cheatsheet and I am too lazy to compute it

  • Hiptmair

timestamp 20260203 exam Q&A

How to tell type/speed of cvg. from tabulated data?

Given: , “error”

  1. exp. cvg:

=> -> if multiple entries same for different n, then exp. cvg.

Alternative: (simpler)

=> tabulate

  1. alg cvg.:

(“exp cvg. in m”) =>

  1. root exp. convergence

-> non-linear regression / least squares for

Vorlesung

timestamp 20250918

Video 1.4: Complexity introduction, tricks to improve complexity

tricks to improve complexity

  • exploit associativity
  • hidden summation

but

  • reuse of intermediate results

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

Never exactly compare floats (always compare with small diff)

Video 1.5.4 cancellation + how to avoid

cancellation in difference quotients

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

Minimal relative error for

todo look at Vieta’s formula

rel. error no. of decimal digits of accuracy

todo where to find review questions?

Video 1.5.5 Numerical Stability

Problem function/mapping from data to result space (usually normed vector space)

stable algorithm 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)

impact of roundoff of stable algorithm is the same order of magnitude as perturbations because rounding of input data

Video 2.1

square LSE -> uniqueness of solution, if invertible / A regular / / 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 :

: LSE well-conditioned : LSE ill-conditioned (result relatively useless)

if condition number of matrix is very large, it’s columns/rows are almost linearly dependent (parallel)

Video 2.3 Gaussian Elimination (GE), LU-decomposition

  • Gaussian eleminitaion ->
  • LU-Decomposition ->

-> 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 )

=> in practice: Cost(sparse solution of ) = ,

Video 3.0.1 Overdetermined linear systems

You cannot afford not to use every piece of information available

Video 3.1.1 Least squares solution

idea: find vector for , s.t. the residual is as small as possible

notation: lsq(A,b)

  • 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

-> 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

All circulant matrices have the same eigenvectors!

n-th root of unity


  • the scaled fourier matrix 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

DFT is a computer's eye for periodic patterns in data

Video 4.2.5 Two dimensional DFT

Video 4.2 FFT

The execution time for fft depends on the length of the transform. It is fastest for powers of two. It is almost as fast for lengths that have only small prime factors. It is typically several times slower for lengths that are prime or which have large prime factors

Video 4.5 Toeplitz Matrix Techniques

Toeplitz matrices:

  • data sparse (not sparse)

overdetermined LSE -> least squares estimator

Video 5.1 AI (Abstract Interpolation)

get unique solution only if (matrix square)

if 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

-> adding one more point ( one diagonal)

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 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 to :

  • 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: , -> approximation has exponential blow-up of error

is not known, so usually we use the lest tight bound with the max norm:

Quantitative interpolation error estimates rely on smoothness!

Video 6.2.2.3

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

Every real-analytic function on can be extended to a complex-analytic function on some open set with .

Video 5.2.3.1 Chebychev Interpolation

The -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: )


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

Line in lin-log plot -> exponential convergence

Line in log-log plot -> algebraic convergence

smoothness is crucial, also for chebyshev nodes

Suitebla integration path: elippsis around :

-> cos, to cancel out with chebyshev polynomials for chebyshev polynomials for analytic functions

slower for smaller domain of analyticity

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

-> bounded

Video 6.6.1 Piecewise Polynomial Lagrange Interpolation

approximation by piecewise polynomials

piece-wise polynomials; benefit:

  • locality
  • cheap algorithm
  • shape preservation

: mesh


lagrange interpolation for function that is times continously differentiable ()

for mesh width 0 () we have algebraic convergence with rate

7. Numerical Quadrature

Video 7.1 Introduction

Numerical Quadrature (Integration)

7.2 Quadrature Rules

Video 7.2 Quadrature Formulas Rules

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)

7.3 Polynomial Quadrature formulas

Video 7.3 Polynomial Quadrature Formulas

Use Lagrangian polynomial interpolation

  • midpoint rule
  • trapezoidal rule

midpoint, trapezoidal

Dangerous for : huge weights with alternating sign: cancellation

solution:

  • chebyshev nodes -> no cancellation, since weights

error estimates for polynomial quadrature:

7.4 Gauss 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

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: (, but ): algebraic convergence with rate r ()
  • analytic -integrand (analytic extension): exponential convergence ()

high smoothness fast convergence

restoring smoothness (removing singularity by transformation):

  • integration by substitution (e.g. -> 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 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

  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.

estimate is normally not good, but always on the large side

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 iterates to get next one

  • start with initial guesses:

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

  • limit of sequence exists ( cvgt.)
  • iteration function consistent ( consistent)
  • iteration function continuous on all arguments ( continous)

=>


local convergence:

  • cvg. will heavily depend on initial guess

questions

  • how fast will the convergence of the sequence solution be? 8.2.2
  • what is the initial region of local convergence? partially answered by 8.3

Video 8.2.2 Speed of Convergence (15 min)

How fast will the norm converge?

smallest L: rate of cvg.

Detect linear convergence:

Error points aligned in lin-log plot

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

Detect p convergence:

No easy graphical way to see

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 prescribed tolerance
    • tells us little about
  • Correction-based termination -> stop convergent iteration, when correction stops changing much

error estimate: -> Reliable error estimate, even if we only know upper bound ,

8.3 Fixed-Point Iterations

Video 8.3 Fixed-Point Iterations (12 min)

we do not always know , so assume:

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

find with

intermediate value theorem

If on interval , negative, positive -> continous function must have zero somewhere in

Idea: geometrically decrease interval -> linear convergence, factor

+ guaranteed cenverence -> robust + F - only evluations needed -> procedural ok + derivative-free + works continuous - not extremely fast

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

Idea: replace function locally around with a simpler method

Newton: use tangent on

required

Ex. 8.4.2.4: functions with same may have different Newton iterations -> advantageous to first recast function before calculating Newton iteration

Find implicit with implicit differentiation

If (F) is hard to solve but close to an easily invertible , define

Then , and 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 1.62

Newton, multi-point methods converge only locally!

-> 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

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 bilinear linear in every argument

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

Simplified Newton method: instead of 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: local quadratic cvg.

Video 8.5.3 Termination of Newton Iteration (7 min)

terminate, when small

=> , but unnecseeary iteration k+1 ()

-> 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

  • & retry if passed
  • next step, (8.5.4.2),
  • in next step

called a reject=accept approch

-> 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 : Secant method, 8.4.2.3

  • replaces (Jacobian) with difference quotient approximation

unique determine

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

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

  1. solve 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 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 ,

then the LSE for Newton crrection is: -> normal equation in case (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 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 is natural
  • time invariant -> wa can always fix initial time 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 for the first-order ODE

both time-dependent and higher-order ODEs can be converted to 1st-order autonomous IVPs:

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
  • 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 (which defines the differential equation) is simply the initial velocity of the evolution operator.

Numerical integration is concerned with the approximation of evolution operators.

  • for Autonomous ODE, we have the group property:

11.2 Introduction: Polygonal Approximation Methods

11.2 Introduction: Polygonal Approximation Methods (17 min) (17.3 min)

explicit Euler method

  • replace with diff. quot anchored on M
  • explicit: no calculation, only evaluation at points:

implicit Euler method

  • backwards diff. quotient instead of forwards diff. quotient
  • feasible? -> continuity argument: for solution should still exist

Implicit function theorem

For sufficiently small : Existence & uniqueness of solutions of (11.2.2.2)

implicit midpoint method again: replace with diff. quot. on M

  • symmetric diff. quot., halfway between

11.3 General Single-Step Methods

Video 11.3. General Single-Step Methods (14 min)

Numerical Integration is concerned with the approximation of evolution operators.

=>

Video 11.3.2 (Asymptotic) Convergence of Single-Step Methods (20 min) (~30min)

… for the sake of simplicity, but without loss of generality …

<repetition> (from [7.4.3.12]) algebraic convergence

  • line in log-log plot

exponential convergence

  • line in lin-log plot (?)
  • </repetition>

explicit/implicit Euler method:

  • algebraic convergence with order 1
  • for

implicit midpoint method

  • alg. cvg. with rate 2

All (common) single-step methods display algebraic convergence

for max point-wise error, we observe decay like for

  • explicit/implicit newton method: order 1
  • implicit midpoint method: order 2

Total error arises from accumulation of propagated one-step errors!

  • Remains valid for all consistent SSMs:

11.4 Explicit Runge-Kutta Single-Step Methods

Video 11.4 Explicit Runge-Kutta Single-Step Methods (27 min)

Questions we can answer:

  • How much additional effort do we have to invest for a desired gain (in accuracy)?

explicit trapezoidal method

  • no solution of equs. required

explicit midpoint method

Video 11.5 Adaptive Stepsize Control (32 min)

<repetition> <repetition>

abs. tolerance is safeguard if we encounter a zero-state

adaptive timestepping

  • stable (always)
  • can “fail”, have even larger errors than uniform mesh, if the initial “large” steps accumulate many errors before we get to the fine mesh step part

refined local stepsize control:

  • find “optimal” timestep -> largest possible timestep b.c. of efficiency derivation:

embedded runge-kutta methods:

  • Idea: use same increments , but with different weights -> is (high-order) p+1 method -> inparticular for IVPs with sensitive dependence on initial conditions (exp 11.5.2.10)
  • b.c. one-step error is only loosly connected to discretization error

Video 12.1 12.1 Model Problem Analysis (40 min)