- Guillermo Vilanova
Personal notes- Systems of equations
- General Concepts
- Problem description
- Given vector "b" and matrix "A", find "x"
- Norm of a vector
- Norm of a matrix
- Spectral radius
- The supremum eigenvalue among the absolute values of the elements in its spectrum
- Condition number
- Systems of linear equations
- Analytic Methods
Álgebra
- Numerical Methods
- Direct methods
- Direct solution of SLE
- SLE with diagonal matrix
- SLE with lower triangular matrix
- Forward substitution
- SLE with upper triangular matrix
- Backward substitution
- Elimination methods
- Description of the method
El método consiste en obtener un sistema cuya matriz sea triangular superior mediante eliminación (de la misma manera que el método de Gauss analítico) o una matriz diagonal (en el caso de utilizar la variante de Gauss-Jordan) y, posteriormente, resolver el sistema resultante mediante sustitución hacia arriba en el primer caso o directamente en el segundo.
Prueba: "\vector{u}" $$A\cdot\overrightarrow {x}=\overrightarrow {b}$$
Para obtener la matriz triangular superior "U" se siguen los siguientes pasos:
- Pivotamiento. Consiste en cambiar una fila/columna por otra fila/columna con el objetivo de no utilizar un pivote (definir pivote) cuyo valor sea muy próximo a cero, ya que lo utilizaremos para dividir. Como lo que buscamos es una matriz triangular superior pivotaremos siempre utilizando filas.
- Sin pivotamiento: Puede dar problemas si algún pivote es nulo. No se necesita pivotamiento si la matriz es definida. Es recomendable programarlo para evitar errores de "overflow".
- Pivotamiento Primitivo: Intercambiar una fila por la siguiente cuyo término que será nuestro futuro pivote sea no nulo. El problema es que puede que sea muy próximo a cero.
- Pivotamiento Parcial: Consiste en buscar el elemento de la fila que sea mayor en valor absoluto y pivotar hasta que ocupe la posición deseada. Es el más utilizado ya que el tiempo de computación es T(n) para cada fila => T(n²); aunque en ocasiones no es del todo bueno.
- Pivotamiento Parcial más sofisticado: Consiste en buscar el elemento de la fila que sea mayor en valor en comparación con los elementos de su fila y pivotar hasta que ocupe la posición deseada. No se usa mucho porque es muy caro: T(n²) para cada fila => T(n³)
- Pivotamiento Completo. Consiste en buscar el elemento de mayor valor absoluto de la matriz entera. Se trata de un método caro (T(n³)) que además no es fácil de implementar ya que se necesita cambiar las incógnitas. Sin embargo, minimiza los errores de redondeo, por lo que se utiliza cuando la matriz está mal condicionada
- Normalización: Dividir toda la fila entre el valor del pivote.
- Eliminación de las filas siguientes: Restar cada fila por la anterior multiplicada por un coeficiente de manera que queden elementos nulos por debajo del pivote (en su columna).
- Repetir el proceso para cada columna.
En el caso de Gauss-Jordan, una vez obtenida la matriz triangular superior "U" habría que repetir el mismo proceso, pero hacia arriba.
- Gaussian elimination
- Description of the method
Se trata de obtener un sistema con matriz triangular superior "U" mediante eliminación y después resolverlo por sustitución hacia arriba.
- Algorithm
- Computational cost=>
- Advantages and disadvantages
- At the end, it is necessary to solve a SLE with a triangular matrix.
- It is computationally cheaper than Gaussian-Jordan elimination.
- It can be applied to band or skyline matrices.
- Gaussian-Jordan elimination
- Description of the method
Se trata de obtener un sistema con matriz triangular diagonal "D" mediante eliminación. Una vez realizado el proceso de eliminación nos quedará un sistema con la siguiente forma:
D·x=b'
(la prima indica que el vector original de términos independientes se ha modificado).
Como la matriz es una matriz diagonal de unos, nos queda ya la solución: x = b'
- Algorithm
- Comutational cost =>
- Advantages and disadvantages
- At the end it is not necessary to solve any SLE (opposite to Gaussian elimination): The matrix ends as a identity matrix, hence the solution to the system is in the vector of independent terms.
- It is a more expensive method than the previous.
- It can not be applied to band or skyline matrices.
- Advantages and disadvantages
- Advantages
- Easy to code
- Direct algorithm (finite and known number of steps).
- It is a universal method: Any non-singular matrix can be solved (with pivoting).
- Pivoting is not necessary if the matrices are definite (less computational cost).
- Similar problems in which only the vector "b" of independent terms changes can be solved with a low computational cost.
- Disadvantages
- Pivoting destroys the bandwith of band and skyline matrices.
- The symmetry of the matrix is not conserved (altough some adaptations of the method may conserve it).
- When applied to large matrices it may propagate rounding errors.
- Decomposition methods
- Frontal method
- Description of the method
Se trata, en esencia, de un método de Gauss por bloques.
Difícil de Programar.
Es el método de Gauss para elementos finitos. Se utiliza cuando la matriz es una matriz vacia estructurada.
En la actualidad no se usa ya que los ordenadores disponen de mucha memoria.
- Advantages and disadvantages
- Advantages
- Big SLE can be solved with low memory computers
- Disadvantages
- Not trivial programmation
-
- Crout method
- Description of the method
Por tratarse de un método de descomposición consta de dos pasos.
- Descomposición de la matriz A en el producto de tres matrices: L·D·U. La primera es una matriz triangular inferior (con una diagonal de unos), la segunda una matriz diagonal y la tercera una matriz triangular superior (con una diagonal de unos).
- Resolución de tres sistemas de ecuaciones acoplados.
- L·z=b ; Se resuelve por sustitución hacia abajo.
- D·y=z ; Se resuelve directamente.
- U·x=y ; Se resuelve por sustitución hacia arriba.
En el caso de hallarse ante una matriz no definida es necesario pivotar para obtener en la diagonal elementos no nulos.
Este método es un método de Gauss "camuflado".
- Decomposition
- Resolution of three SLE with direct solution
- Algorithm
- Comutational cost => T(n³) + T(n²)
- Advantages and disadvantages
- Cholesky method
- Description of the method
Por tratarse de un método de descomposición consta de dos pasos.
- Descomposición de la matriz "A" simétrica en el producto de tres matrices: L·D·Lt. La matriz "L" es una matriz triangular inferior (con una diagonal de unos) y "Lt" es su matriz traspuesta; la matriz "D" es una matriz diagonal.
- Resolución de tres sistemas de ecuaciones acoplados.
- L·z=b ; Se resuelve por sustitución hacia abajo.
- D·y=z ; Se resuelve directamente.
- Lt·x=y ; Se resuelve por sustitución hacia arriba.
En el caso de hallarse ante una matriz no definida es necesario pivotar para obtener en la diagonal elementos no nulos.
- Decomposition
- Resolution of three SLE with direct solution
- Algorithm
- Comutational cost => T(n³) + T(n²)
- Advantages and disadvantages
- Only valid for symmetric matrices
- Advantages and disadvantages
- Advantages
- Particularly good methods for band and skyline matrices.
- Once the decomposition has been made, similar problems in which just the vector of independent terms changes can be solved with a low computational cost T(n²).
- They are more stable than elimination methods regarding the error propagation.
- Disadvantages
- If the matrix is non-definite, it requires the pivoting of the matrix (higher computational cost).
- Iterative refinement
- Description of the method
- Advantages and disadvantages
- Allows the refinment of the solution and the reduction of the errors
- The subsequent iterations are not expensive, for the indepent term is the only one that changes.
- Iterative methods
- General description
- Convergence conditions
-
- Gradient Method
- Chosen matrix
- Algorithm
- Comutational cost =>
- Convergence condition
- Eigenvalues must be between 0 and 2
- Advantages and disadvantages
- Easy implementation
- Pretty bad method
- Usually it does not converge, and when it does, it is slow
- Jacobi Method
- Chosen matrix
- Algorithm
- Comutational cost =>
- Convergence condition
- Advantages and disadvantages
- Symmetry is conserved
- It converges a little bit faster than Gauss-Seidel method
- It works better than the Gauss-Seidel method 70-80% of the times
- Gauss-Seidel Method
- Chosen matrix
- Algorithm
- Comutational cost =>
- Convergence condition
- Advantages and disadvantages
- Simmetry is not conserved
- It converges a little bit slower than Jacobi method
- It works better than the Jacobi method 20-30% of the times
- Advantages and disadvantages
- If they work, they work for any initial value.
- If they do not work for an initial value, they won't work for any.
- Acceleration of the convergence
- Over-relaxation
"A posteriori" preconditioning
"A priori" preconditioning
- Semi-Iterative methods
- Description of the method
- It is a mixture of direct and iterative methods
- Direct methods.: A, b ==> x
Iterative methods : A, b,x_{0} ==> x_{1},x_{2},...,x_{k},x_{k+1}
Semi-Iterative methods : A, b,x_{0} ==> x_{1},x_{2},...,x_{k},...,x_{n}=x - Solution is obtained after a finite number of steps
-
- Cojugate direction Methods
- Description of the method
- Different methods depending on how the basis
of A-conjugate vectors (s1,s2,...,sn) is obtained- Gram-Schmitz Method
- Description of the method
- Álgebra I
- Choose the vectors v_{i} linearly independent
(+)
Conditions of the form sTAS=0 giving the values of beta
- Comutational cost => T(n³)
- Advantages and disadvantages
- Very expensive
- Very slow
- Conjugate Gradient Method
- Main ideas
- It is an improvement of the Gram-Schmitz method, where the conjugate vectors v_{i} are chosen such that the most of the beta coefficients are zero
- Description of the method
- Algorithm
Dado el sistema Ax = b + R, con algunas x_{v} = p_{v} , se procede de la siguiente manera:
1) Se inicializan los valores de los g.d.l. prescritos, x_{v} = p_{v} .
2) Cuando se calcula el residuo r = b − Ax se opera con toda la matriz.
3) Al actualizar los valores de x en cada iteracion se ignoran (no se modifican) las incógnitas correspondientes a los g.d.l. prescritos,x_{v} = p_{v}.
4) Al comprobar la condicion de convergencia en r hay que tener en cuenta que los términos corespondientes a los g.d.l. prescritos no tienden a 0 sino a los valores de
las reacciones correspondientes.
5) Finalmente, las reacciones se obtienen a partir del ultimo residuo, ya que R = −r.
- Notes
- There are several formulations to calculate beta, namely
HESTENES–STIEFEL FLETCHER–REEVES, POLAK–RIBIERE, MYERS. - Solving the least energy problem we obtain the optimus advance direction, which is the same as the one of this method
- Advantages and disadvantages
- Very efficient
- Works good
- Very fast
- Advantages and disadvantages
- Only valid for definite and symmetric matrices
- GMRES
- Description of the method
- Algorithm
Implementación práctica. Pasos a realizar:
1. Calcular el vector residuo y su norma a partir de la aproximación inicial.
2. Calcular el vector de proyección de Householder w cuyos terminos no nulos se almacenan por columnas en la parte inferior de una matriz H de dimensión (n + 1) ∗ (m + 1).
3. Definir la columna de la matriz de Hessemberg a partir del residuo y del vector w. Sólo es necesario calcular la componente de la diagonal. Los terminos no nulos se almacenan en la parte superior de la matriz H .
4. Si j = 1 (primera iteración), definir el vector y a partir de la matriz H .
5. Si j > 1 (siguientes iteraciones), aplicar triangularización de la nueva columna de la matriz H y del vector y . (Tengase en cuenta que es necesario aplicar las transformaciones de triangularizacion de todas las columnas anteriores a esta nueva columna de la matriz H antes de aplicar la triangularización de la columna actual).
6. El último término calculado en el vector y (en valor absoluto) indica la norma del residuo para el subespacio de Krylov utilizado y sirve para establecer la convergencia del metodo. Si hay convergencia pasamos al paso 9.
7. Calcular v aplicando recurrentemente los proyectores de Householder a partir de los vectores w almacenados en la parte inferior de la matriz H
8. Calcular el nuevo vector z con el que comenzar de nuevo todo el proceso y volver al paso 2 (lo que equivale a aumentar el tamaño del subespacio de Krylov utilizado).
9. Resolver el sistema de ecuaciones triangular superior almacenado en la parte superior de la matriz H cuyo vector de terminos independientes es el vector y .
10. Calcular la nueva aproximación a la solucion de forma recurrente aplicando los
proyectores de Householder definidos por los vectores w almacenados en la parte inferior de la matriz H .
11. Calcular el residuo para la nueva solucion obtenida. Si no hay convergencia, reiniciar el cálculo en el paso 1 con la nueva solución obtenida en el paso 10 (restart).
- Comutational cost =>
- Convergence
- Roughly speaking, this says that fast convergence occurs when the eigenvalues of A are clustered away from the origin and A is not too far from normality.
- Variations
- Truncated GMRES
- Restarted GMRES
- Advantages and disadvantages
- Can be implemented in parallel
- Reduced computational cost
- Accurate and robust algorithm
- Valid for regular matrices and non symmetric
- The more similar to the mass matrix, the faster the method is
- For each iteration the dimension of the matrices is increased, thus it is slower for each iteration (the computational cost grows O(n²)). This is the motivation for the restarted GMRES
- Advantages and disadvantages
- Valid for very large SLE
- Commonly used when iterative methods fail
- They inherit the advantages and disadvantages of both methods
- Eventually they may be stopped obtaining an approximation to the solution
- It may be used with minimum storage schemes for sparse matrices because the coefficients of the matrices are conserved
- Systems of non-linear equations
- General Description
- The methods are the same as those used for the evaluations of the roots of an equation, as if the SNLE were an equation and not a system
- All of them are iterative methods
- In each iteration a SEL is solved (using one of the above described methods)
- Successive approximations
- Newton-Raphson Method
- Methods derived from Newton-Rahpson method
Simple Newton
Wittaker
Quasi-Newton o Secant
- Approximation & Interpolation
- Objective
- Functions
- Polynomial
- Interpolation
- Standard basis
- Lagrangian basis
- Newton basis
- Chevyshev improvement (Optimal points)
- Approximation
- Mini-Max
- Least squares
- Standard basis
- Ortogonal basis
- Fourier series
- Exponential series
- Rational funtions
- Criteria
- Approximation
- Mini-Max
- Least squares
- Interpolation
- Pure interpolation
- Integration
- General Description
- Cálculo I
- Primitive of a function
- Definition
- Necessary condition for the existence of the primitive
- Riemann integral
- Darboux sums. Properties
- Necessary and sufficient condition of integrability
- Sufficient conditions of integrability
- Properties
- Mean value theorem
- Fundamental theorem of calculus. Barrow proof
- Second Fundamental Theorem
- Improper integrals
- Analytic Methods
- Cálculo I
- Inmediate
- ...
- Numerical Methods
- Definition of the problem
- Solutions
- Solution Nº1
- Newton Integration
- Closed Newton Integration
- Newton-Cotes quadratures
- Open Newton Integration
- Newton-Cotes quadratures
- Solution Nº2
- Gaussian Integration
- Gauss-Legendre quadratures
- Gauss-Laguerre quadratures
- Gauss-Hermite quadratures
- Gauss-Chevyshev quadratures
- Solution Nº3
- Mixed integration
- Coonvergence of the quadratures
- Main ideas
- Conclusions
- improvement of the integration
- Main idea
- To use two methods and combine the results
- Composite integration
- Richardson integration
- Romberg integration
- Particular cases
- Filon integration
- improper integrals
- Infinite interval
- Different approximations
- To use Gauss-Laguerre/Hermite integral
- To transform the interval into a finite one
- To divide into subintervals: Laguerre+Composite+Laguerre
- Singular integrals
- Different approximations
- To divide into subintervals: Open Newton-Cotes + Gauss-Chevyshev
- To decompose and resolve analytically the singularity
- Multiple integrals
- EDOs or IVP
- General Description
- Analytic Methods
- Numerical Methods
- General description
- Problem statement
- Definitions
- Well-posed problem
- Consitency
- Convergence
- Estability
- Lax theorem
- Description of the process
- Simple Interval Methods
- General description
- Methods
- Approximation of the derivative
- Euler Method
- Forward Euler
- Backward Euler
- Central differences
- Series expansion
- Taylor series expansion
- Runge-Kutta
- General description
- First order
- Second order
- Third order
- Fourth order
- Multiple Interval Methods
- General description
- Methods
- Explicit, Open o Predictor
- Implicit, Closed o Corrector
- Predictor-Corrector Method
- Shooting Method
- EDP or BVP
- General Description
- Boundary conditions
- Dirichlet or essential
- Neuman or natural
- Robin
- Cauchy
- Analytic Methods
- Method of Characteristics
- Separation of variables
- Eigenfunction Expansion Method
- Green Function
- Integral Transform
- Change of varibles
- Fundamental solution
- Superposition principle
- Methods for Nonlinear equations
- H-principle
- Method of Characteristics
- Perturbation Analysis
- Lie Group Method
- Semianalytical Methods
- Numerical Methods
- Finite Difference Method
- General Description
- Methods
- Explicit Method
- Implicit Method
- Crank-Nicholson Method
- Integral or Weighted
Residual Methods- Finite Element Method (FEM)
- Conforming Method
- Macro-element Method
- A genius approach is to subdivide a given element into several small subelements and then use low-order polynomials on each subelement so that the C 1 continuity on the entire element is achieved.
- Nonconforming Method
- Another approach is to relax directly the C m−1 continuity of the finite element space. It comes to the so-called NONCONFORMING finite element method which had and still has a great impact on the development of finite element methods
- However, it was found shortly that some nonconforming elements converge and some do not. The convergence behavior sometimes depends on the mesh configuration.
- Mixed Finite Element Method
- Extended Finite Element Method (XFEM)
- Finite Volume Method (FVM)
- In the finite volume method, volume integrals in a PDE that contain a divergence term are converted to surface integrals, using the divergence theorem.
- These terms are then evaluated as fluxes at the surfaces of each finite volume
- It is conservative
- Another advantage of the finite volume method is that it is easily formulated to allow for unstructured meshes.
- Boundary Element Method (BEM)
- Isogeometric Analysis
- Spectral or Integral Transform Methods
- General Description
- The main idea of these methods is to approximate the unknown solution in the entire domain by a global function (non-zero in the whole domain), opposing the Integral methods which uses local functions.
- It is a global approach, rather than a local approach as in the FEM.
- The solution is expressed as a sum of certain basis functions multiplied by coefficients that have to be determined.
- Spectral Methods achieve a greater precision with smaller points than Finite Difference methods.
- Advantages and disadvantages
- Advantages
- Excellent error properties with the so-called "exponential convergence" being the fastest possible, when the solution is smooth.
- Disadvantages
- There are no known three-dimensional single domain spectral shock capturing results.
- Smooth solution required.
- Methods
- Galerkin Spectral Methods
- PDE written in terms of the coefficients of the finite expansion of the basis functions
- Spectral Collocation Methods
or Pseudospectral- Similar to FDM due to direct use of grid points = Collocation points.
- The underlying idea is to approximate the solution in the whole domain by an interpolating high order polinomial at the collocation points.
- Convergence: O(N^m) for every m
- Tau Spectral Methods
- Similar to the first, but the expanding function is not obligued to satisfy the BC, requiring an extra equation.
- Comparisson among methods
- Basis functions
- The functions are ortogonal
-
- Periodic problems
- Fourier
- Hermite
- Laguerre
- Non-periodic problems
- Solutions of Sturm-Liouville problems
(I.e. Chevyshev, Legendre... polynomials)
- References
- Level Set Method (LSM)
- General Description
- Fast Marching Method
- Generalized-alpha method
- General Description
- Turbulence
- Reynolds-averaged Navier–Stokes
- Reynolds stress model (RSM)
- Large eddy simulation
- Detached eddy simulation
- Direct numerical simulation
- Coherent vortex simulation
- Probability density function (PDF) methods
- Vortex method
- Vorticity confinement method
- Method of Lines
- Tau Method
- Meshfree Methods
- Maximum entropy method
