# Lecture WS 18/19 Numerical Algorithms

Lecturer
Prof. Marc Alexander Schweitzer
Contact for exercises
Denis Düsseldorf

### Content

#### Learning targets

Broad overview and understanding of propositions, relations and methods from the area of numerical algorithms. Competence to evaluate the scope, utility, and limits of the methods and techniques and to independently apply abstract mathematical results to concrete problems. Competence to place the results in a more general mathematical context. Overview of connections to other areas and ability to arrive at rigorous mathematical proofs starting from heuristic considerations.

The selection of topics is based on the module handbook for the Master programme in mathematics.

In particular, we will introduce and discuss the h-,p- and hp-versions of the finite element method (FEM) and its application to conservation equations.

#### Topics

• Repetition of classical finite element method (FEM) and functional analysis: h-FEM on regular meshes
• Fast solvers: Multigrid, Domain Decomposition
• High order FEM and isogeometric analysis (IGA): p-FEM, k-FEM
• Enriched Approximations: extended FEM (XFEM), generalized FEM (GFEM), partition of unity methods (PUM)
• Discontinuous Galerkin: Elliptic problems, conservation laws
1. From smooth/regular problems and solutions
2. to general/irregular/non-smooth/singular/discontinuous solutions

### Literature

Some of these books are also available in German/English, as ebook or in another edition in the library. The essay of Carl de Boor on B-Spline Basics is available as PDF.

### Prerequisites

Prerequisites for this lecture are the topics and exercises of the preceding lectures Algorithmische Mathematik I (V1G5), Algorithmische Mathematik II (V1G6), V2E1 Einführung die Grundlagen der Numerik (V2E1).

These prerequisite topics include:

• Calculus, multidimensional differentiation and integration and Taylor expansion
• Elementary combinatorics and probability theory
• Structured programming, in particular C, Python
• Polynomial Interpolation
• Least Squares Approximation
• Conditioning of problems, Stability of algorithms
• Inner products, Orthogonality, Hilbert Spaces, Best approximation in Hilbert spaces
• Orthogonalization, Gram-Schmidt, Orthogonal Polynomials
• Solution of systems of linear equations: Gauss elimination, LU decompostion, Cholesky decomposition, QR decomposition
• Solution of nonlinear equations: bisection, Newton
• Classical iterative methods for systems of linear equations: Jacobi, Gauss-Seidel, Richardson, SOR
• Krylov subspaces, Krylov subspace methods: Gradient descent, CG, PCG, MINRES, GMRES
• Preconditioning of iterative methods: PCG
• Eigenvalues, Eigenvectors, Bounds for the spectrum, Power iteration, Lanczos, Arnoldi, QR algorithm

### Tutorials

Admittance for oral exam based on homework assignments requiring

• 50% of points from theory assignments
• 50% of points from programming assignments

### Script

There are inofficial(!) lecture notes. The current version can be found below. Note that there is no guarantee for the lecture notes to be complete, neither correct. There are surely a number of typos inside. If you encounter one, please let me know by mail!
Script, version 2019-01-30

### Homework assignments

Worksheets with homework assignments are distributed and put on the website Tuesdays. Please, submit your homework assignments Tuesdays right before the beginning of the lecture one week after handout. Submit programming assignments as plain text Python files.

Programming exercises will be based mainly in Python/NumPy/matplotlib. Please send in your solutions to programming exercises via mail to your tutorial’s teaching assistant.

This combination is a very useful for quick implementation. Algorithms can be put into code fast. Plots can be produced with little effort. Much of what is needed for the lecture can be found in the following examples.

Some Documentation and Tutorials can be found at the following links.

One easy way to obtain all necessary Python packages is Anaconda.

More installation alternatives, suggestions and instructions can be found on the websites for NumPy and matplotlib.

Model solutions are base on Python in version 2.7.8. For editing and writing Python code, any good editor will do. We recommend Vim or Notepad++.

### Exercise sheets

Remarks

Warm-up sheet. No submission, no grading

Sample Code: sheet_03.py (password sent by mail)

Sample Code: sheet_04.py (passwort sent by mail)

Bonus. Submission is not obligatory. You can get additional points.

### Exam

• Graded oral exam, length 30 minutes, in seminar room 3.024 at INS/IEL Endenicher Allee 19b)
• successful participation in tutorials required for admittance to examination
• Registration for the second exam has started. Available dates can be seen here: secondExam_dates.pdf (X X X means that a slot is taken!). First come first serve - if you want to register please come to my office (1.039) or send a mail to ed tod nnob-inu tod sni ta frodlesseuda tod b@foo tod de. Please note that for a valid registration you have to firm the registration sheet (office 1.039).

### Dates and location

Dates:
Tuesday
10:15 – 12:00

Thursday
08:15 – 10:00

Location:
Seminar room 2.035
INS/IEL
Endenicher Allee 19b

Exercise class:
First meeting: 2018-17-10

New location:Starting from wednesday, 2018-10-24, the exercise class will take place in seminar room 2.035, INS/IEL,Endenicher Allee 19b, wednesdays 08:30 – 10:00