12NME1 - Numerical methods

Here you can find auxiliary study materials for undergraduate course 12NME1 - Numerical methods lectured at the Faculty of Nuclear Sciences and Physical Engineering, Czech Technical University in Prague.

academic year: 2020/2021
time: Monday, 7:30 - 9:10
room: T-105

Warning: Due to the COVID-19 pandemic, the tutorials will be held at the scheduled time remotely using Microsoft Teams (Team-B202-NME1-Valenta). If the situation changes, you will be informed.

Requirements

in order to obtain the assessment, there are several formal requirements:

Attendace at tutorials:

  • maximum of 3 unjustified absences are allowed throughout the semester
  • please consult the attendance list regularly and inform me in case of any error

Assessment task:

  • you have to solve correctly given task and defend your solution
  • the assessment tasks will be assigned in April, the deadline for submission will be in September (the exact dates will be specified later)
  • first, send me your task solution via e-mail; if your solution is correct, the date of defense will be determined individually upon mutual agreement

Those who obtained the assessment previous year do not have to attend the tutorials again.

Those who attended the tutorials previous year and did not defend the assessment task may get another task to be submitted until the end of March. If the defense of the new assessment task is successfull, they do not have to attend the tutorials again.

Warning: Since it is not possible to properly check the attendance in the remote mode, the requirements above are no longer valid. Instead, you will be given a short task at the end of each tutorial. To obtain the assessment, it is neccessary to solve correctly and submit on time at least 6 out of 11 tasks throughout the semester. Please consult the evaluation list regularly and inform me in case of any error.

About the study materials

The study materials currently consist of only the implementation of selected numerical methods and algorithms (without comments). For closer info, you should attend the tutorials. The methods are written in Python 3, and organized into a collection of Jupyter notebooks. In addition, they rely on several Python packages:

  • numpy (mainly for data structures)
  • scipy (for several numerical algorithms)
  • matplotlib (for visualization)

Although all these packages can be installed one-by-one, I recommend to obtain them by installing Anaconda.

What is Anaconda and how to install it:

Anaconda is a Python distribution for scientific computing. It includes Jupyter and dozens of the most popular Python packages for scientific computing, including numpy, scipy and matplotlib.

To install Anaconda,

  1. open https://www.anaconda.com/products/individual with your web browser
  2. download the suitable Anaconda installer for Windows/MacOS/Linux (you will find them at the bottom of the web page)
  3. install Anaconda using all of the defaults for installation except make sure to check that the Anaconda distribution is the default Python

How to obtain the notebooks:

All the notebooks are stored in this GitHub repository under the tutorials directory. You may either download all the notebooks as a .zip archive, or use git:

  1. Clone the repository:
    $> git clone https://github.com/valenpe7/numerical_methods.git
  2. Pull in new changes:
    $> git pull

How to launch the notebooks:

After you have installed Anaconda on your computer and obtained the notebooks, you are ready to run the notebook server. You can start the notebook server from the command line (Terminal on MacOS/Linux, Anaconda Prompt on Windows) by running:

$> jupyter notebook

This will print some information about the notebook server in your terminal, including the URL of the web application (by default, http://localhost:8888), and open your default web browser to this URL. When Jupyter opens in your browser, you will see the “Notebook Dashboard”, which will show a list of the notebooks, files, and subdirectories in the directory where the notebook server was started. Navigate to the tutorials directory and click on the selected notebook.

Alternatively, if you do not have installed Anaconda, you may launch the notebooks on-line using

Tutorials

Tutorial 00 - Introduction to numerical methods

Organization of tutorials, installation and setup of required tools

Tutorial 01 - Introduction to Python and Jupyter

Basic concepts and features of Python, numeric and math-related functions and data types, Jupyter environment, numpy, scipy, matplotlib modules.
Download the assignment and submit your solution in the .ipynb format here (deadline: 28/02/2021 23:59 CET).
Materials from lecture: nbviewer, binder, ipynb

Tutorial 02 - Error analysis

Floating point representation of numbers, roundoff error, truncation error, numerical stability and condition number.
Download the assignment and submit your solution in the .ipynb format here (deadline: 07/03/2021 23:59 CET).
Materials from lecture: nbviewer, binder, ipynb

Tutorial 03 - Linear algebra

Basic linear algebra operations, direct methods for solving linear equation systems, forward and backward substitution, Gaussian elimination, LU decomposition, Thomas algorithm.
Download the assignment and submit your solution in the .ipynb format here (deadline: 14/03/2021 23:59 CET).
Materials from lecture: nbviewer, binder, ipynb

Tutorial 04 - Linear algebra (cont'd)

Iterative methods for solving linear equation systems, Jacobi method, Gauss-Seidel method, successive overrelaxation method, power iteration and eigensystems, conjugate gradient method.
Download the assignment and submit your solution in the .ipynb format here (deadline: 21/03/2021 23:59 CET).
Materials from lecture: nbviewer, binder, ipynb

Tutorial 05 - Interpolation

Piece-wise linear interpolation, Lagrange interpolation and Neville’s algorithm, Chebyshev polynomials and approximation, linear and quadratic least squares interpolation.
Download the assignment and submit your solution in the .ipynb format here (deadline: 28/03/2021 23:59 CET).
Materials from lecture: nbviewer, binder, ipynb

Tutorial 06 - Data sorting

Various algorithms for data sorting and their comparison, bubble sort, selection sort, insertion sort, shell sort, quicksort, heap sort, benchmarking.
Download the assignment and submit your solution in the .ipynb format here (deadline: 11/04/2021 23:59 CET).
Materials from lecture: nbviewer, binder, ipynb

Tutorial 07 - Nonlinear equations

Root finding and nonlinear set of equations, bisection method, secant method, false position method, Newton-Raphson method.
Download the assignment and submit your solution in the .ipynb format here (deadline: 18/04/2021 23:59 CET).
Materials from lecture: nbviewer, binder, ipynb

Tutorial 08 - Optimization

Search for extremes of functions, golden section search, parabolic interpolation search, gradient descent.
Download the assignment and submit your solution in the .ipynb format here (deadline: 25/04/2021 23:59 CET).
Materials from lecture: nbviewer, binder, ipynb

Tutorial 09 - Quadrature

Numerical integration of functions, rectangular rule, trapezoidal rule, Simpson’s rule, Romberg’s method, Gaussian quadrature, Monte-Carlo integration and random number generators.
Download the assignment and submit your solution in the .ipynb format here (deadline: 02/05/2021 23:59 CET).
Materials from lecture: nbviewer, binder, ipynb

Tutorial 10 - Initial value problems

Initial value problems of ordinary differential equations, explicit and implicit Euler method, Runge-Kutta methods, Leap-frog, Adams-Bashford, Adams-Moulton, predictor-corrector, Bulirsch-Stoer algorithm, stiff equations.
Download the assignment and submit your solution in the .ipynb format here (deadline: 09/05/2021 23:59 CET).
Materials from lecture: nbviewer, binder, ipynb

Tutorial 11 - Boundary value problems

Boundary value problems of ordinary differential equations, finite difference method, shooting method, finite element method.
Download the assignment and submit your solution in the .ipynb format here (deadline: 16/05/2021 23:59 CET).
Materials from lecture: nbviewer, binder, ipynb

Tutorial 12 - Final tutorial

Individual consultations, evaluation of assessment tasks, refreshing of selected topics.

The solutions to all the tutorial exercises and assignment tasks will be available here and here.

The study materials are evolving quickly. Therefore, if you find any mistake, please submit an issue to the GitHub project repository.

[1] W. H. Press, B. P. Flannery, S. A. Teukolsky, V. H. Vetterling, Numerical Recipes: The art of scientific computing, Cambridge University Press, Cambridge, 3rd edition 2007.

[2] A. Ralston, P. Rabinowicz, A First Course in Numerical Analysis, McGraw-Hill 1965 (reprinted by Dover Publications, 2001).

[3] R. W. Hamming, Numerical Methods for Scientists and Engineers, 2nd edition, Dover Publications 1986.