__Computer methods in theoretical physics - TMF057(ZS
2017-18)__

News: (January
4, 2018) I translated LIST OF PROBLEM
FOR CREDITS (Zápočtové úlohy) and I corrected few minor errors there.

(December 22, 2017) I am
currently translating this web page to English. You can still see the previous
version below. It contains most of the examples in Python
(some using NumPy
libraries) which you could see in the lecture. On the last lecture I presented
preliminary LIST OF PROBLEM FOR CREDITS (Zápočtové úlohy). Only Czech version is currently
available. You should select one of the problems and solve it in suitable
programming language (C, C++, C#, Fortran, Pascal, Python) using floating point
arithmetic. You will present your solution at the exam including your understanding
of the theory related to the subject of the selected problem. The exam will
consist of this presentation and one additional theoretical question.

**LESSON 1 ****– Round-off
errors and numerical stability. **(see [1], for deeper understanding see also [4,5,7])

- Floating
point representation of real numbers and round-off error.
- Machine
epsilon, propagation of errors in basic arithmetic operations. Problem of
cancelling of numbers.
- Numerical
stability and conditioning number.

**Numerical demonstrations:**

- Round-off
error (trivial example) ...................... ……..demoL01.01_wrong_loop.py
- Sum
forward = sum backward? .................................. demoL01.02_suma.py
- Cancellation
of numbers.............................................. demoL01.03_cancelation.py
- Quadratic
equation (optimization of round-off )......... demoL01.04_quadratic.py
- Why
convergent series does not converge?................ demoL01.05_Taylor_exp.py

**Exercise: **Determination of pi according to
Archimedes. (attempt1-unstable, attempt2-stable, attempt3-convergence
acceleration)

**LESSON 2 – Iterations and
solution of nonlinear equations. **(see [1], for deeper understanding also
[5,7,8])

- Banach fixed point theorem and
convergence of iterations.
- Error
estimate, order of convergence and it acceleration.
- Aitken
a Aitken-Steffensen
algorithm.
- Iterative
solution to nonlinear equations. Newton method.

**Numerical demonstrations:**

- cos(cos(cos(...cos(1.0)...))).......................................demoL02.01_coscos.py
- Babylonian
method of calculation of square root... demoL02.02_Babylon.py
- Aitken
on cos cos.................................................demoL02.03_Aitken.py
- Aiten-Steffensen on cos
cos..................................demoL02.04_AitkenSteffensen.py
- Newton
fractal = answer to question: "Which root of z
^{3}-1=0 you find using Newton algorithm started from given point of complex plain?" https://en.wikipedia.org/wiki/Newton_fractal

**LESSON 3 - Interpolation
and interpolation polynomials. **(see [1], for deeper understanding [2,8])

- Existence
and uniqueness of polynomial interpolation.
- Lagrange
interpolation, Aitken-Nevilles scheme.
- Error
estimate and its behaviour on regular and Chebyshev
grid.
- Hermite interpolation, error estimate
and its relation to Taylor series.

**Numerical demonstration:
**(using Turtle
graphics from Python)

- Interpolation
on regular grid....................................demoL03.01_regular.py
- Behaviour
of polynomial omega................................demoL03.02_omega.gnu (script for gnuplot –
tested with version 4.7)
- Interpolation
of Chebyshev grid..............................demoL03.03_chebychev.py

**LESSON 4 – Interpolation
on regular grid, difference equations. **(see [1], for deeper understanding
[5])

- Operators
of forward and backward difference. Functions of the operators.
- Newton
interpolation formula.
- Derivation
of formulas for differentiation of interpolation polynomials.
- Numerical
integration and Euler-Maclaurin summation formula.
- Linear
difference equations and their solution. Explicit formula for Fibonacci sequence.

**LESSON 5 – Numerical differentiation
and integration. **(see [1], for deeper understanding [2,5,8])

- Analysis
of the truncation (discretization) and round-off errors for various
differentiation formulas.
- Integration
using Newton-Cotes formulae.
- Using
of Richardson extrapolation and Romberg integration.
- Gauss
quadrature and orthogonal polynomials.
- Discussion
and comparison of different integration methods, singularity of integrand,
improper integrals. More dimensions.

**Exercise: **Numerical differentiation, discretization
error and round-off error (values of numerical derivative for different h,
graph of the error in log/log scale in using gnuplot).

**Numerical demonstration:
**(Numerical
derivative, discretization x round-off errors)

- Derivatives
from different finite difference formulae .........demoL4.01_derivace.py
- Graphs
of results..............................................demoL4.01_derivace.gnu (script for gnuplot)

**LESSON 6 – Numerical integration
of differential equations. **(see [1], for deeper understanding [2,3])

- Formulation
of the initial value problem for ODE. Transformation of higher
order equation into system of the first order equations.
- Examples
and derivation of simple schemes.
- Formulation
of general linear multistep formula (LIMUFO). Order of precision and
consistency of the method..
- Relation
of Padé approximation of logarithmic function and LIMUFO. AB, BA a BD
methods.
- Characteristic
polynomials and stability. Stability of Adams and backward difference
methods.
- Dahlquist convergence theorems,
stability barrier, absolute stability, regions of stability.

**Numerical demonstrations:
**(Numerical solution
to ODE)

- Calculation
of solution using explicit methods ...........demoL5.01_LIMUFO.py
- Drawing
of the solution…… ....................................... reseni.gnu (script
for gnuplot, shows data from previous *.py)
- Testing
of convergence speed …………………............demoL5.02_global.py
- Graph
of order of convergence ........................................... konverg.gnu
- The
same as 1, 2, but implicit methods .............................................................demoL6.01_implicit.py, reseni.gnu
- The
same as 3,4 but implicit ............................................................demoL6.02_stiff.py,
kstif.gnu

**LESSON 7 - Numerical
linear algebra – matrix factorisation. **(see [2,4])

- General
remarks on numerical linear algebra: notion of matrix factorization, characterisation
of algorithm speed using asymptotic scaling of number of FLOPs
- Gram-Schmidt
orthogonalisation and QR-factorisation.
Stability, Hausholder method, scaling of number
of FLOPs.
- SVD,
existence of singular value decomposition and its applications.
- Least
squares problems. Normal equation and pseudoinverse. Solution of least
squares problems using QR factorisations and SVD.
- Matrix
and vector norm. Examples of norms and their calculation. Basic inequalities.
- Stability
and backward stability. Backward stability of QR factorization.

**Numerical demonstrations:** (QR factorisation and its application):

- Finding
eigenfunctions of harmonic oscillator
..................DemoL8.01_QR_LHO.py
- Backward
stability of QR factorisation..............................DemoL8.02_zpet_stabil.py
- Matrix
rank using SVD………..........................................DemoL8.03_Hello.py

**LESSON 8 – Numerical linear
algebra - Gaussian elimination. **(viz [2,4])

- Conditioning
number of matrix and its relevance for different numerical tasks.
- LU
decomposition and its relation to Gaussian elimination.
- Stability
of LU decomposition using Gauss elimination, pivoting.
- Using
LU decomposition for solution of systems of equations, finding matrix
inverse and determinant.
- Number
of FLOPs for Gauss elimination. Tridiagonal and band matrixes. Symmetric
matrixes (Choleski factorisation)
- Solution
of ill conditioned systems using SVD.

**Numerical demonstrations:** (Gauss elimination and LU decomposition)

- Gauss
without pivoting......................DemoL9.01_LU_nestab.py
- Gauss
with pivoting...........................DemoL9.02_LU_pivot.py
- LU
decomposition from scipy library.........DemoL9.03_LU_linalg.py

**LESSON 9 – Numerical linear
algebra – matrix diagonalisation. **(see
[2,4,5])

- Definition
of diagonalisation. Eigenvalues and their
multiplicity. Left and right eigenvectors. Characteristic polynomial.
- Diagonalization
of real symmetric matrix using Jacobi method. Convergence and operational
count.
- Overview
of other methods. Reduction to tridiagonal (or Hessenberg)
form.
- Principle
of QR algorithm. Finding roots of tridiagonal matrix characteristic
polynomial.

**Numerical demonstrations:
**(Diagonalisation using Jacobi method)

- Using
numpy routine..........................DemoL10.01_eigval.py
- Jacobi
method with "sweeps"..........................DemoL10.02_Jacobi.py
- Jacobiho method with elimination of
maximum element......DemoL10.03_Jacobi_max.py

**LESSON 10 - Discrete Fourier transform (I did not have time to do this
year, for info: [2,3])**

- FT, semiDFT
a DFT, Nyquist frequence.
- Algorithm of fast Fourier transform
(FFT) and its operation count.
- Applications of DFT.

**RECOMMENDED LITERATURE:**

I am using mainly [1] and [4]. Suitable complement for practical implementation of algorithms is [2]. Other books for more details on speciffic tomics, see green notes.

- [1] (not complete) my notes.-
*so**far only first part of lecture and only in Czech.* - [2] Press, Teukolsky, Vetterling, Flannery: Numerical Recipes in Fortran (or in
C), available online.
Older versions free. –
*basic reference for most topics of the lecture.* - [3] L. N. Trefethen: Finite difference and spectral methods for ODE and PDE. Unfinished book available online.
*Nice pedagogical explanation of LIMUFO.* - [4] L.N. Trefethen,
D. Bau III: Numerical Linear Algebra. SIAM 1997.
*Nice pedagogical text on numerical linear algebra.* - [5] Isaacson, Keller: Analysis of Numerical Methods.
*More detailed numerical and mathematical analysis for most of the topics of the lecture.* - [6] Koonin: Computational Physics.
*Solved**examples with motivation in physics.* - [7] Henrici: Essentials of Numerical Analysis with Pocket Calculator Demonstrations.
*Basics**of numerical mathematics with nice examples how it works.* - [8] Segethová: Základy
numerické matematiky. Skriptum MFF UK, in Czech, výběr základních algoritmů a jejich
analýza včetně důkazů.

**Note**** on Pythonu:** Above
numerical demonstrations in
Pythonu use libraries **numpy****
**and **matplotlib**. Python is
available online for free. You could:

*1 visit https://www.continuum.io/downloads and download
anaconda
2 install
3 run Anaconda Launcher
4 run Spyder - IDE (interaktive
console) or run Ipython-qtconsole - interactive
python .*

Informace z loňských stránek Karla Houfka naleznete naleznete zde.