Ceci est une ancienne révision du document !
System of linear equations
Numerical methods used to solve such problem allow to introduce and experiment on Time_complexity, considering cubic time behavior of standard algorithms and i.e. quadratic time solutions using LU decomposition.
Theory
- Gaussian_elimination, Gauss and Gauss-Jordan eliminations (diagonalization, triangularization)
- Pivot_element, pivoting
-
- Chapter 2 in the book “Numerical Recipes” :
- 2.0 Introduction
- 2.1 Gauss-Jordan Elimination
- 2.2 Gaussian Elimination with Backsubstitution
- 2.3 LU Decomposition and Its Application
- Python NumPy library : NumPy Reference
- Time complexity analysis
- Hint : in Python, use the timeit module
Exercices and applications
- Exercices :
- write a python function for diagonalisation with partial pivoting
- random numbers → linear systems
- comparison with numpy standard library
- measurements of execution time to check cubic complexity
1D problems with neigbours
- Thermal diffusion and chemical diffusion (transient or stationary) on a regular 1D space with equidistant steps. ODE equations can be writen such a given evolution equation for node # i only imlies nodes i+1 and i-1
- Using tridiagonal Thomas algorithm allows to save computational time thanks to n complexity
- ? Python library with Thomas algorithm
References :
- Numerical recipes, The Art of Scientific Computing 3rd Edition, William H. Press, Saul A. Teukolsky, William T. Vetterling, Brian P. Flannery, 2007, isbn: 9780521880688
-