Computer methods in theoretical physics - TMF057(winter 2019-20)

News: (October 1, 2019) The lecture is scheduled to Wednesdays 9:00-11:20 in lecture room of Institute of particle and nuclear physics on 8th floor. Martin Čížek is giving lecture this term. For web pages of Karel Houfek see this link. The old syllabus is given below. I will work on it during semester. The LIST OF PROBLEMS FOR CREDITS (Zápočtové úlohy) is old. You can check it to get idea about the extension of the tasks, but I will give the final list in the middle of the term.

Syllabus contains most of the examples in Python (some using NumPy libraries) which you could see in the lecture. The LIST OF PROBLEMS FOR CREDITS will appear in due time. 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.

Syllabus (Czech version is here)

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:

1. Round-off error (trivial example) ...................... ……..demoL01.01_wrong_loop.py
2. Sum forward = sum backward? .................................. demoL01.02_suma.py
3. Cancellation of numbers.............................................. demoL01.03_cancelation.py
4. Quadratic equation (optimization of round-off )......... demoL01.04_quadratic.py
5. 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:

1. cos(cos(cos(...cos(1.0)...))).......................................demoL02.01_coscos.py
2. Babylonian method of calculation of square root... demoL02.02_Babylon.py
3. Aitken on cos cos.................................................demoL02.03_Aitken.py
4. Aiten-Steffensen on cos cos..................................demoL02.04_AitkenSteffensen.py
5. Newton fractal = answer to question: "Which root of z³-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)

1. Interpolation on regular grid....................................demoL03.01_regular.py
2. Behaviour of polynomial omega................................demoL03.02_omega.gnu (script for gnuplot – tested with version 4.7)
3. 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)

1. Derivatives from different finite difference formulae .........demoL4.01_derivace.py
2. 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)

1. Calculation of solution using explicit methods ...........demoL5.01_LIMUFO.py
2. Drawing of the solution…… ....................................... reseni.gnu (script for gnuplot, shows data from previous *.py)
3. Testing of convergence speed …………………............demoL5.02_global.py
4. Graph of order of convergence ........................................... konverg.gnu
5. The same as 1, 2, but implicit methods .............................................................demoL6.01_implicit.py,   reseni.gnu
6. 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):

1. Finding eigenfunctions of harmonic oscillator ..................DemoL8.01_QR_LHO.py
2. Backward stability of QR factorisation..............................DemoL8.02_zpet_stabil.py
3. 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)

1. Gauss without pivoting......................DemoL9.01_LU_nestab.py
2. Gauss with pivoting...........................DemoL9.02_LU_pivot.py
3. 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)

1. Using numpy routine..........................DemoL10.01_eigval.py
2. Jacobi method with "sweeps"..........................DemoL10.02_Jacobi.py
3. 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.