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.
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
Except ill-conditionned, linear systems can be solved “exactly” using linear algebra algorithms in a finite and known number of arithmetic operations.
The accuracy is determined by the number of numerical figures which are encoded in floating point description
For a general system of n equations, diagonalisation requires of the order of n3 operations. Also for solving a system using these method.
If the coefficient matrix is the same for different systems (only the independent coefficients are different), it is possible to solve systems with the order of n2 operations, if the matrix of coeeficients is decomposed in the product of two triangular matrix (Lower-Upper decomposition). This n3 step is realised only once.
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