Esta es una lista de temas de análisis numérico .
General
- Números validados
- Método iterativo
- Tasa de convergencia : la velocidad a la que una secuencia convergente se acerca a su límite.
- Orden de precisión : tasa a la que la solución numérica de la ecuación diferencial converge a la solución exacta
- Aceleración en serie : métodos para acelerar la velocidad de convergencia de una serie.
- Proceso delta-cuadrado de Aitken : más útil para secuencias que convergen linealmente
- Extrapolación mínima de polinomios : para secuencias de vectores
- Extrapolación de Richardson
- Transformación de Shanks : similar al proceso delta-cuadrado de Aitken, pero aplicado a las sumas parciales
- Transformación de Van Wijngaarden : para acelerar la convergencia de una serie alterna
- Abramowitz y Stegun : libro que contiene fórmulas y tablas de muchas funciones especiales
- Biblioteca digital de funciones matemáticas - sucesor del libro de Abramowitz y Stegun
- Maldición de dimensionalidad
- Convergencia local y convergencia global: si necesita una buena suposición inicial para obtener la convergencia
- Superconvergencia
- Discretización
- Cociente de diferencias
- Complejidad:
- Complejidad computacional de operaciones matemáticas
- Análisis suavizado : mide el rendimiento esperado de los algoritmos bajo ligeras perturbaciones aleatorias de las entradas del peor de los casos
- Cálculo simbólico-numérico : combinación de métodos simbólicos y numéricos
- Aspectos culturales e históricos:
- Historia de la solución numérica de ecuaciones diferenciales usando computadoras
- Problemas de desafío de cien dólares y cien dígitos : lista de diez problemas propuestos por Nick Trefethen en 2002
- Talleres internacionales sobre QCD de celosía y análisis numérico
- Cronología del análisis numérico después de 1945
- Clases generales de métodos:
- Método de colocación : discretiza una ecuación continua al requerir que solo se mantenga en ciertos puntos
- Método de ajuste de nivel
- Conjunto de niveles (estructuras de datos) : estructuras de datos para representar conjuntos de niveles
- Métodos numéricos Sinc : métodos basados en la función sinc, sinc ( x ) = sin ( x ) / x
- Métodos ABS
Error
Análisis de errores (matemáticas)
- Aproximación
- Error de aproximación
- Número de condición
- Error de discretización
- Número de coma flotante
- Dígito de protección: precisión adicional introducida durante un cálculo para reducir el error de redondeo
- Truncamiento : redondear un número de punto flotante descartando todos los dígitos después de un cierto dígito
- Error de redondeo
- Aritmética de precisión arbitraria
- Aritmética de intervalos : representa cada número mediante dos números de punto flotante garantizados para tener el número desconocido entre ellos.
- Contratista de intervalo : asigna el intervalo al subintervalo que aún contiene la respuesta exacta desconocida
- Propagación de intervalo : contracción de dominios de intervalo sin eliminar ningún valor consistente con las restricciones
- Ver también: Método de elemento límite de intervalo , Elemento finito de intervalo
- Pérdida de importancia
- Error numérico
- Estabilidad numérica
- Propagación de errores:
- Propagación de la incertidumbre
- Lista de software de propagación de incertidumbre
- Aritmética de significancia
- Residual (análisis numérico)
- Propagación de la incertidumbre
- Cambio relativo - la diferencia relativa entre X e Y es | x - y | / max (| x |, | y |)
- Personajes importantes
- Falsa precisión : da cifras más significativas de las apropiadas.
- Error de truncamiento : error cometido al realizar solo un número finito de pasos
- Problema bien planteado
- Aritmética afín
Funciones elementales y especiales
- Algoritmo sin restricciones
- Suma:
- Algoritmo de suma de Kahan
- Suma por pares : ligeramente peor que la suma de Kahan pero más barata
- División binaria
- Multiplicación:
- Algoritmo de multiplicación : discusión general, métodos simples
- Algoritmo de Karatsuba : el primer algoritmo que es más rápido que la multiplicación sencilla
- Multiplicación de Toom-Cook - generalización de la multiplicación de Karatsuba
- Algoritmo de Schönhage-Strassen : basado en la transformada de Fourier, asintóticamente muy rápido
- Algoritmo de Fürer : asintóticamente un poco más rápido que Schönhage-Strassen
- Algoritmo de división : para calcular el cociente y / o el resto de dos números
- División larga
- Restaurando la división
- División no restauradora
- División SRT
- División de Newton-Raphson : usa el método de Newton para encontrar el recíproco de D y multiplica ese recíproco por N para encontrar el cociente final Q.
- División Goldschmidt
- Exponenciación:
- Exponenciación por cuadratura
- Exponenciación de la cadena de suma
- Algoritmos inversos multiplicativos : para calcular el inverso multiplicativo (recíproco) de un número.
- Método de Newton
- Polinomios:
- El método de Horner
- Esquema de Estrin : modificación del esquema de Horner con más posibilidades de paralelización
- Algoritmo de Clenshaw
- El algoritmo de de Casteljau
- Raíces cuadradas y otras raíces:
- Raíz cuadrada entera
- Métodos para calcular raíces cuadradas
- n- ésimo algoritmo raíz
- Desplazamiento del algoritmo raíz n- ésimo : similar a la división larga
- hypot - la función ( x 2 + y 2 ) 1/2
- Algoritmo alpha max plus beta min : se aproxima a hypot (x, y)
- Raíz cuadrada inversa rápida : calcula 1 / √ x utilizando detalles del sistema de punto flotante IEEE
- Funciones elementales (exponencial, logaritmo, funciones trigonométricas):
- Tablas trigonométricas : diferentes métodos para generarlas
- CORDIC : algoritmo de cambio y suma mediante una tabla de arcos tangentes
- Algoritmo BKM: algoritmo de cambio y suma utilizando una tabla de logaritmos y números complejos
- Función gamma:
- Aproximación de Lanczos
- Aproximación de Spouge : modificación de la aproximación de Stirling; más fácil de aplicar que Lanczos
- Método AGM : calcula la media aritmética-geométrica; los métodos relacionados calculan funciones especiales
- Método FEE (Evaluación rápida de la función E): suma rápida de series como la serie de potencias para e x
- Tablas precisas de Gal : tabla de valores de función con espaciado desigual para reducir el error de redondeo
- Algoritmo de espiga : algoritmos que pueden calcular dígitos individuales de un número real
- Aproximaciones de π :
- Algoritmo π de Liu Hui : primer algoritmo que puede calcular π con precisión arbitraria
- Fórmula de Leibniz para π - series alternas con convergencia muy lenta
- Producto de Wallis: producto infinito que converge lentamente a π / 2
- Fórmula de Viète : producto infinito más complicado que converge más rápido
- Algoritmo de Gauss-Legendre : iteración que converge cuadráticamente a π, según la media aritmética-geométrica
- Algoritmo de Borwein : iteración que converge trimestralmente a 1 / π y otros algoritmos
- Algoritmo de Chudnovsky: algoritmo rápido que calcula una serie hipergeométrica
- Fórmula de Bailey-Borwein-Plouffe : se puede utilizar para calcular dígitos hexadecimales individuales de π
- Fórmula de Bellard : versión más rápida de la fórmula de Bailey-Borwein-Plouffe
- Lista de fórmulas que involucran π
Álgebra lineal numérica
Álgebra lineal numérica - estudio de algoritmos numéricos para problemas de álgebra lineal
Conceptos básicos
- Tipos de matrices que aparecen en el análisis numérico:
- Matriz dispersa
- Matriz de bandas
- Matriz bidiagonal
- Matriz tridiagonal
- Matriz pentadiagonal
- Matriz de horizonte
- Matriz circulante
- Matriz triangular
- Matriz diagonalmente dominante
- Matriz de bloques : matriz compuesta por matrices más pequeñas
- Matriz de Stieltjes : definida positiva simétrica con entradas fuera de la diagonal no positivas
- Matriz de Hilbert : ejemplo de una matriz que está extremadamente mal acondicionada (y por lo tanto es difícil de manejar)
- Matriz de Wilkinson : ejemplo de una matriz tridiagonal simétrica con pares de valores propios casi iguales, pero no exactamente iguales
- Matriz convergente - matriz cuadrada cuyas potencias sucesivas se acercan a la matriz cero
- Matriz dispersa
- Algoritmos para la multiplicación de matrices:
- Algoritmo de Strassen
- Algoritmo de calderero-Winograd
- Algoritmo de Cannon : un algoritmo distribuido, especialmente adecuado para procesadores dispuestos en una cuadrícula 2d
- Algoritmo de Freivalds : un algoritmo aleatorio para verificar el resultado de una multiplicación
- Descomposiciones matriciales :
- Descomposición LU - triangular inferior multiplicado por triangular superior
- Descomposición QR : matriz ortogonal multiplicada por matriz triangular
- Factorización RRQR: factorización QR que revela el rango, se puede usar para calcular el rango de una matriz
- Descomposición polar : matriz unitaria multiplicada por matriz hermitiana semidefinida positiva
- Descomposiciones por similitud:
- Eigendecomposition - descomposición en términos de autovectores y autovalores
- Forma normal de Jordan : matriz bidiagonal de cierta forma; generaliza la descomposición propia
- Forma canónica de Weyr - permutación de la forma normal de Jordan
- Descomposición de Jordan-Chevalley : suma de la matriz nilpotente de conmutación y la matriz diagonalizable
- Descomposición de Schur : transformación de similitud que lleva la matriz a una matriz triangular
- Descomposición de valores singulares : matriz unitaria por matriz diagonal por matriz unitaria
- División de matrices : expresar una matriz dada como una suma o diferencia de matrices
Resolver sistemas de ecuaciones lineales
- eliminación gaussiana
- Forma escalonada de filas : matriz en la que todas las entradas por debajo de una entrada distinta de cero son cero
- Algoritmo de Bareiss : variante que garantiza que todas las entradas permanezcan enteras si la matriz inicial tiene entradas enteras
- Algoritmo de matriz tridiagonal : forma simplificada de eliminación gaussiana para matrices tridiagonales
- Descomposición LU : escriba una matriz como producto de una matriz triangular superior e inferior
- Descomposición de la matriz de crout
- Reducción de LU : una versión especial paralelizada de un algoritmo de descomposición de LU
- Descomposición de LU de bloque
- Descomposición de Cholesky : para resolver un sistema con una matriz definida positiva
- Algoritmo de grado mínimo
- Descomposición simbólica de Cholesky
- Refinamiento iterativo : procedimiento para convertir una solución inexacta en una más precisa
- Métodos directos para matrices dispersas:
- Solucionador frontal : utilizado en métodos de elementos finitos
- Disección anidada : para matrices simétricas, basada en la partición de gráficos
- Recursividad de Levinson - para matrices de Toeplitz
- Algoritmo SPIKE : solucionador paralelo híbrido para matrices de banda estrecha
- Reducción cíclica : elimine filas o columnas pares o impares, repita
- Métodos iterativos:
- Método Jacobi
- Método de Gauss-Seidel
- Sobre-relajación sucesiva (SOR): una técnica para acelerar el método Gauss-Seidel
- Sobre relajación sucesiva simétrica (SSOR): variante de SOR para matrices simétricas
- Algoritmo de backfitting : procedimiento iterativo utilizado para ajustar un modelo aditivo generalizado, a menudo equivalente a Gauss-Seidel
- Sobre-relajación sucesiva (SOR): una técnica para acelerar el método Gauss-Seidel
- Iteración de Richardson modificada
- Método de gradiente conjugado (CG): supone que la matriz es definida positiva
- Derivación del método de gradiente conjugado
- Método de gradiente conjugado no lineal : generalización para problemas de optimización no lineal
- Método de gradiente biconjugado (BiCG)
- Método estabilizado de gradiente biconjugado (BiCGSTAB) - variante de BiCG con mejor convergencia
- Método residual conjugado : similar al CG, pero solo se supone que la matriz es simétrica
- Método de residuo mínimo generalizado (GMRES): basado en la iteración de Arnoldi
- Iteración de Chebyshev : evita los productos internos pero necesita límites en el espectro
- Método de Stone (SIP - Procedimiento fuertemente implícito): utiliza una descomposición LU incompleta
- Método Kaczmarz
- Preacondicionador
- Factorización de Cholesky incompleta - escasa aproximación a la factorización de Cholesky
- Factorización de LU incompleta - escasa aproximación a la factorización de LU
- Iteración de Uzawa : para problemas de nodos de silla
- Sistemas subdeterminados y sobredeterminados (sistemas que no tienen o tienen más de una solución):
- Cálculo numérico del espacio nulo : encuentre todas las soluciones de un sistema indeterminado
- Pseudoinverso de Moore-Penrose : para encontrar una solución con la norma 2 más pequeña (para sistemas indeterminados) o el residuo más pequeño
- Aproximación escasa : para encontrar la solución más escasa (es decir, la solución con tantos ceros como sea posible)
Algoritmos de valores propios
Algoritmo de valor propio : un algoritmo numérico para localizar los valores propios de una matriz
- Iteración de poder
- Iteración inversa
- Iteración del cociente de Rayleigh
- Iteración de Arnoldi : basada en subespacios de Krylov
- Algoritmo de Lanczos - Arnoldi, especializado en matrices definidas positivas
- Algoritmo de bloque de Lanczos : para cuando la matriz está sobre un campo finito
- Algoritmo QR
- Algoritmo de valor propio de Jacobi : seleccione una submatriz pequeña que pueda diagonalizarse exactamente y repita
- Rotación de Jacobi : el bloque de construcción, casi una rotación de Givens
- Método de Jacobi para matrices hermitianas complejas
- Algoritmo de valor propio de divide y vencerás
- Método de espectro plegado
- LOBPCG - Método de gradiente conjugado preacondicionado en bloque localmente óptimo
- Perturbación de valores propios: estabilidad de valores propios bajo perturbaciones de la matriz
Otros conceptos y algoritmos
- Algoritmos de ortogonalización :
- Proceso Gram-Schmidt
- Transformación de cabeza de familia
- Operador de amo de casa: análogo de la transformación de amo de hogar para espacios de productos internos generales
- Rotación de Givens
- Subespacio de Krylov
- Pseudoinverso de matriz de bloques
- Bidiagonalización
- Algoritmo de Cuthill-McKee : permuta filas / columnas en una matriz dispersa para producir una matriz de banda estrecha
- Transposición de matriz en el lugar : calcular la transposición de una matriz sin usar mucho almacenamiento adicional
- Elemento pivote : entrada en una matriz en la que se concentra el algoritmo
- Métodos sin matrices : métodos que solo acceden a la matriz mediante la evaluación de productos de matriz-vector.
Interpolación y aproximación
Interpolación : construye una función que pasa por algunos puntos de datos dados
- Interpolación del vecino más cercano : toma el valor del vecino más cercano
Interpolación polinomial
Interpolación polinomial - interpolación por polinomios
- Interpolación linear
- Fenómeno de Runge
- Matriz de Vandermonde
- Polinomios de Chebyshev
- Nódulos de Chebyshev
- Constante de Lebesgue (interpolación)
- Diferentes formas para el interpolante:
- Polinomio de Newton
- Diferencias divididas
- Algoritmo de Neville : para evaluar el interpolante; basado en la forma de Newton
- Polinomio de Lagrange
- Polinomio de Bernstein - especialmente útil para aproximaciones
- Fórmula de interpolación de Brahmagupta: fórmula del siglo VII para la interpolación cuadrática
- Polinomio de Newton
- Extensiones a múltiples dimensiones:
- Interpolación bilineal
- Interpolación trilineal
- Interpolación bicúbica
- Interpolación tricúbica
- Puntos de Padua : conjunto de puntos en R 2 con un interpolante polinomial único y un crecimiento mínimo de la constante de Lebesgue
- Interpolación de Hermite
- Interpolación de Birkhoff
- Interpolación de Abel-Goncharov
Interpolación de splines
Interpolación de splines : interpolación por polinomios por partes
- Spline (matemáticas) : los polinomios por partes que se utilizan como interpolantes
- Spline perfecto - spline polinomial de grado m cuya m ésima derivada es ± 1
- Spline cúbico de Hermite
- Spline Centripetal Catmull – Rom - caso especial de splines cúbicos de Hermite sin auto-intersecciones o cúspides
- Interpolación cúbica monótona
- Hermite spline
- Curva de Bézier
- El algoritmo de de Casteljau
- curva de Bézier compuesta
- Generalizaciones a más dimensiones:
- Triángulo de Bézier : asigna un triángulo a R 3
- Superficie de Bézier : asigna un cuadrado a R 3
- B-spline
- Box spline : generalización multivariante de B-splines
- Función de potencia truncada
- Algoritmo de De Boor : generaliza el algoritmo de De Casteljau
- B-spline racional no uniforme (NURBS)
- T-spline : se puede considerar como una superficie NURBS para la que se permite terminar una fila de puntos de control
- Spline de Kochanek-Bartels
- Parche de Coons : tipo de parametrización múltiple que se utiliza para unir suavemente otras superficies.
- M-spline : un spline no negativo
- I-spline : una spline monótona, definida en términos de M-splines
- Suavizar spline : un spline que se adapta sin problemas a datos ruidosos
- Blossom (funcional) : un mapa simétrico, afín y único asociado a un polinomio o spline
- Ver también: Lista de temas de geometría computacional numérica
Interpolación trigonométrica
Interpolación trigonométrica : interpolación por polinomios trigonométricos
- Transformada discreta de Fourier : se puede ver como una interpolación trigonométrica en puntos equidistantes
- Relaciones entre transformadas de Fourier y series de Fourier
- Transformada rápida de Fourier (FFT): un método rápido para calcular la transformada discreta de Fourier
- Algoritmo FFT de Bluestein
- Algoritmo FFT de Bruun
- Algoritmo Cooley-Tukey FFT
- Algoritmo FFT de base dividida : variante de Cooley-Tukey que utiliza una combinación de radicales 2 y 4
- Algoritmo de Goertzel
- Algoritmo FFT de factor primo
- Algoritmo FFT de Rader
- Permutación de inversión de bits: permutación particular de vectores con entradas de 2 m que se utilizan en muchas FFT.
- Diagrama de mariposa
- Factor de giro : los coeficientes constantes trigonométricos que se multiplican por los datos.
- Transformada ciclotómica rápida de Fourier : para FFT sobre campos finitos
- Métodos para calcular convoluciones discretas con filtros de respuesta de impulso finitos utilizando la FFT:
- Método de superposición-adición
- Método de superposición-guardar
- Aproximación sigma
- Kernel de Dirichlet : convolucionar cualquier función con el kernel de Dirichlet produce su interpolante trigonométrico
- Fenómeno de Gibbs
Otros interpolantes
- Aproximación racional simple
- Modelado de funciones polinomiales y racionales : comparación de interpolación polinomial y racional
- Wavelet
- Onda continua
- Matriz de transferencia
- Consulte también: Lista de temas de análisis funcional , Lista de transformaciones relacionadas con wavelets
- Ponderación de distancia inversa
- Función de base radial (RBF): una función de la forma ƒ ( x ) = φ (| x - x 0 |)
- Spline poliarmónico : una función de base radial de uso común
- Spline de placa delgada : un spline poliarmónico específico: r 2 log r
- RBF jerárquico
- Superficie de subdivisión : construida mediante la subdivisión recursiva de un interpolante lineal por partes.
- Superficie de subdivisión Catmull-Clark
- Superficie de subdivisión de Doo-Sabin
- Superficie de subdivisión de bucle
- Slerp (interpolación lineal esférica): interpolación entre dos puntos en una esfera
- Interpolación de cuaterniones generalizada: generaliza slerp para la interpolación entre más de dos cuaterniones
- Transformada ponderada discreta de base irracional
- Interpolación de Nevanlinna-Pick : interpolación por funciones analíticas en el disco unitario sujeto a un límite
- Pick matrix : la interpolación de Nevanlinna-Pick tiene una solución si esta matriz es positiva semidefinida
- Interpolación multivariante : la función que se interpola depende de más de una variable
- Interpolación de Barnes : método para funciones bidimensionales que utilizan gaussianos comunes en meteorología
- Superficie de Coons : combinación de interpolación lineal e interpolación bilineal
- Remuestreo de Lanczos : basado en convolución con función sinc
- Interpolación de vecino natural
- Interpolación del valor del vecino más cercano
- Superficie PDE
- Interpolación transfinita : construye la función en el dominio plano dados sus valores en el límite
- Análisis de superficies de tendencia : basado en polinomios de orden inferior de coordenadas espaciales; utiliza observaciones dispersas
- Los métodos basados en polinomios se enumeran en Interpolación de polinomios
Teoría de la aproximación
Teoría de la aproximación
- Órdenes de aproximación
- Lema de Lebesgue
- Ajuste de curvas
- Reconstrucción de campo vectorial
- Módulo de continuidad : mide la suavidad de una función
- Mínimos cuadrados (aproximación de funciones) : minimiza el error en la norma L 2
- Algoritmo de aproximación Minimax : minimiza el error máximo en un intervalo (la norma L ∞ )
- Teorema de la equioscilación : caracteriza la mejor aproximación en la norma L ∞
- Conjunto de puntos no disolventes : la función de un espacio funcional dado se determina de forma única por los valores de dicho conjunto de puntos
- Teorema de Stone-Weierstrass : las funciones continuas se pueden aproximar uniformemente mediante polinomios o ciertos otros espacios funcionales.
- Aproximación por polinomios:
- Aproximación lineal
- Polinomio de Bernstein : base de polinomios útil para aproximar una función
- Constante de Bernstein - error al aproximar | x | por un polinomio
- Algoritmo de Remez : para construir la mejor aproximación polinomial en la norma L ∞
- Desigualdad de Bernstein (análisis matemático) : ligada al máximo de la derivada del polinomio en el disco unitario
- Teorema de Mergelyan : generalización del teorema de Stone-Weierstrass para polinomios
- Teorema de Müntz-Szász : variante del teorema de Stone-Weierstrass para polinomios si algunos coeficientes tienen que ser cero
- Lema de Bramble-Hilbert : límite superior de L p error de aproximación polinomial en múltiples dimensiones
- Polinomios discretos de Chebyshev : polinomios ortogonales con respecto a una medida discreta
- Teorema de Favard : los polinomios que satisfacen relaciones de recurrencia de 3 términos adecuadas son polinomios ortogonales
- Aproximación por series de Fourier / polinomios trigonométricos:
- Desigualdad de Jackson : límite superior para la mejor aproximación mediante un polinomio trigonométrico
- El teorema de Bernstein (teoría de aproximación) : un inverso a la desigualdad de Jackson
- Teorema de Fejér: las medias de Cesàro de sumas parciales de series de Fourier convergen uniformemente para funciones periódicas continuas
- Desigualdad de Erdős-Turán : límites de la distancia entre la probabilidad y la medida de Lebesgue en términos de coeficientes de Fourier
- Desigualdad de Jackson : límite superior para la mejor aproximación mediante un polinomio trigonométrico
- Diferentes aproximaciones:
- Moviendo mínimos cuadrados
- Padé aproximado
- Tabla de Padé - tabla de aproximaciones de Padé
- Teorema de Hartogs-Rosenthal : las funciones continuas se pueden aproximar uniformemente mediante funciones racionales en un conjunto de medidas cero de Lebesgue
- Operador de Szász-Mirakyan - aproximación por e - n x k en un intervalo semi-infinito
- Operador Szász – Mirakjan – Kantorovich
- Operador de Baskakov : generalizar polinomios de Bernstein, operadores Szász-Mirakyan y operadores Lupas
- Operador de Favard - aproximación por sumas de gaussianos
- Modelo sustituto - aplicación: reemplazar una función que es difícil de evaluar por una función más simple
- Teoría de la función constructiva : campo que estudia la conexión entre el grado de aproximación y la suavidad
- Ecuación diferencial universal: ecuación diferencial-algebraica cuyas soluciones pueden aproximarse a cualquier función continua.
- Problema de Fekete : encuentra N puntos en una esfera que minimizan algún tipo de energía
- Condición de Carleman : condición que garantiza que una medida está determinada únicamente por sus momentos
- Condición de Krein : condición de que las sumas exponenciales sean densas en el espacio L 2 ponderado
- Teorema del letargo : acerca de la distancia de puntos en un espacio métrico a los miembros de una secuencia de subespacios.
- Teorema de representación y proyección de Wirtinger
- Revistas:
- Aproximación constructiva
- Revista de teoría de la aproximación
Diverso
- Extrapolación
- Análisis predictivo lineal: extrapolación lineal
- Funciones unisolventes : funciones para las que el problema de interpolación tiene una solución única
- Análisis de regresión
- Regresión isotónica
- Compactación ajustada a curvas
- Interpolación (gráficos por computadora)
Encontrar raíces de ecuaciones no lineales
- Ver # álgebra lineal numérica para ecuaciones lineales
Algoritmo de búsqueda de raíces : algoritmos para resolver la ecuación f ( x ) = 0
- Métodos generales:
- Método de bisección : simple y robusto; convergencia lineal
- Algoritmo de Lehmer-Schur : variante para funciones complejas
- Iteración de punto fijo
- Método de Newton : basado en una aproximación lineal alrededor de la iteración actual; convergencia cuadrática
- Teorema de Kantorovich : da una región alrededor de la solución tal que el método de Newton converge
- Fractal de Newton : indica qué condición inicial converge a qué raíz en la iteración de Newton
- Método cuasi-Newton : utiliza una aproximación del jacobiano:
- Método de Broyden : utiliza una actualización de rango uno para el jacobiano
- Rango uno simétrico: una actualización del rango uno simétrico (pero no necesariamente positivo definido) del jacobiano
- Fórmula de Davidon-Fletcher-Powell : actualización del jacobiano en el que la matriz permanece definida positiva
- Algoritmo de Broyden-Fletcher-Goldfarb-Shanno : actualización de rango dos del jacobiano en el que la matriz permanece definida positiva
- Método BFGS de memoria limitada: variante truncada y sin matriz del método BFGS adecuado para problemas grandes
- Método de Steffensen : utiliza diferencias divididas en lugar de la derivada
- Método secante : basado en la interpolación lineal en las dos últimas iteraciones
- Método de posición falsa: método de la secante con ideas del método de bisección
- Método de Muller : basado en la interpolación cuadrática en las últimas tres iteraciones
- Método secante generalizado de Sidi: variantes de orden superior del método secante
- Interpolación cuadrática inversa : similar al método de Muller, pero interpola la inversa
- Método de Brent : combina el método de bisección, el método de la secante y la interpolación cuadrática inversa
- Método de Ridders : ajusta una función lineal multiplicada por un exponencial para las últimas dos iteraciones y su punto medio
- Método de Halley : usa f , f 'y f ' '; logra la convergencia cúbica
- Método del amo de casa : utiliza las primeras derivadas d para lograr el orden d + 1; generaliza el método de Newton y Halley
- Método de bisección : simple y robusto; convergencia lineal
- Métodos para polinomios:
- Método de Aberth
- El método de Bairstow
- Método Durand-Kerner
- El método de Graeffe
- Algoritmo Jenkins-Traub : rápido, confiable y ampliamente utilizado
- El método de Laguerre
- Método de división del círculo
- Análisis:
- Polinomio de Wilkinson
- Continuación numérica : el seguimiento de una raíz como un parámetro en la ecuación cambia
- Continuación lineal por partes
Mejoramiento
Optimización matemática : algoritmo para encontrar máximos o mínimos de una función dada
Conceptos básicos
- Conjunto activo
- Solución candidata
- Restricción (matemáticas)
- Optimización restringida: estudia problemas de optimización con restricciones
- Restricción binaria : una restricción que involucra exactamente dos variables
- Solución de esquina
- Región factible : contiene todas las soluciones que satisfacen las restricciones, pero que pueden no ser óptimas.
- Óptimo global y óptimo local
- Máximos y mínimos
- Variable de holgura
- Optimización continua
- Optimización discreta
Programación lineal
Programación lineal (también trata la programación de enteros ): la función objetivo y las restricciones son lineales
- Algoritmos para programación lineal:
- Algoritmo simplex
- Regla de Bland : regla para evitar el ciclismo en el método simplex
- Cubo de Klee-Minty - cubo perturbado (hiper); El método simplex tiene una complejidad exponencial en tal dominio
- Algoritmo entrecruzado : similar al algoritmo simplex
- Método Big M : variación del algoritmo simplex para problemas con restricciones tanto "menor que" como "mayor que"
- Método de punto interior
- Método elipsoide
- Algoritmo de Karmarkar
- Método predictor-corrector de Mehrotra
- Generación de columnas
- k-aproximación del conjunto de golpes k - algoritmo para problemas de LP específicos (para encontrar un conjunto de golpes ponderado)
- Algoritmo simplex
- Problema de complementariedad lineal
- Descomposiciones:
- Descomposición de Benders
- Descomposición de Dantzig-Wolfe
- Teoría de la planificación a dos niveles
- División variable
- Solución básica (programación lineal) : solución en el vértice de la región factible
- Eliminación de Fourier-Motzkin
- Base de Hilbert (programación lineal) : conjunto de vectores enteros en un cono convexo que generan todos los vectores enteros en el cono
- Problema de tipo LP
- Desigualdad lineal
- Problema de enumeración de vértices : enumere todos los vértices del conjunto factible
Optimizacion convexa
Optimizacion convexa
- Programación cuadrática
- Mínimos cuadrados lineales (matemáticas)
- Mínimos cuadrados totales
- Algoritmo de Frank – Wolfe
- Optimización secuencial mínima : divide los grandes problemas de QP en una serie de problemas de QP más pequeños posibles.
- Programa bilineal
- Búsqueda de base : minimiza la norma L 1 del vector sujeto a restricciones lineales
- Eliminación de ruido de búsqueda de bases (BPDN): versión regularizada de búsqueda de bases
- Algoritmo en la multitud : algoritmo para resolver la eliminación de ruido de la búsqueda de bases
- Eliminación de ruido de búsqueda de bases (BPDN): versión regularizada de búsqueda de bases
- Desigualdad de matriz lineal
- Optimización cónica
- Programación semidefinida
- Programación de cono de segundo orden
- Optimización de suma de cuadrados
- Programación cuadrática (ver arriba)
- Método de Bregman: método de acción de fila para problemas de optimización estrictamente convexos
- Método de gradiente proximal : use la división de la función objetivo en la suma de posibles piezas no diferenciables
- Método de subgradiente : extensión del descenso más pronunciado para problemas con una función objetivo no diferenciable
- Optimización biconvexa : generalización donde la función objetivo y el conjunto de restricciones pueden ser biconvexos
Programación no lineal
Programación no lineal : el problema de optimización más general en el marco habitual
- Casos especiales de programación no lineal:
- Ver programación lineal y optimización convexa arriba
- Programación geométrica : problemas que involucran signomios o posinomios
- Signomial : similar a los polinomios, pero los exponentes no necesitan ser números enteros.
- Posinomio : un significado con coeficientes positivos
- Programa cuadrático restringido cuadráticamente
- Programación lineal-fraccional : el objetivo es la proporción de funciones lineales, las restricciones son lineales
- Programación fraccionada : el objetivo es la proporción de funciones no lineales, las restricciones son lineales
- Problema de complementariedad no lineal (NCP): encuentre x tal que x ≥ 0, f ( x ) ≥ 0 y x T f ( x ) = 0
- Mínimos cuadrados : la función objetivo es una suma de cuadrados
- Mínimos cuadrados no lineales
- Algoritmo de Gauss-Newton
- Algoritmo BHHH : variante de Gauss-Newton en econometría
- Método de Gauss-Newton generalizado : para problemas de mínimos cuadrados no lineales restringidos
- Algoritmo de Levenberg-Marquardt
- Mínimos cuadrados ponderados iterativamente (IRLS): resuelve un problema de mínimos cuadrados ponderados en cada iteración
- Mínimos cuadrados parciales : técnicas estadísticas similares al análisis de componentes principales
- Mínimos cuadrados parciales iterativos no lineales (NIPLS)
- Programación matemática con restricciones de equilibrio : las restricciones incluyen desigualdades variacionales o complementariedades
- Optimización univariante:
- Búsqueda de sección dorada
- Interpolación parabólica sucesiva : basada en la interpolación cuadrática a través de las últimas tres iteraciones
- Algoritmos generales:
- Conceptos:
- Dirección de descenso
- Valor de adivinación : la suposición inicial de una solución con la que comienza un algoritmo.
- Búsqueda de línea
- Búsqueda de línea de retroceso
- Condiciones de Wolfe
- Método de degradado: método que utiliza el degradado como dirección de búsqueda.
- Descenso de gradiente
- Descenso de gradiente estocástico
- Iteración de Landweber : se utiliza principalmente para problemas mal planteados
- Descenso de gradiente
- Programación lineal sucesiva (SLP): reemplace el problema por un problema de programación lineal, resuélvalo y repita
- Programación cuadrática secuencial (SQP): reemplace el problema por un problema de programación cuadrática, resuélvalo y repita
- El método de Newton en optimización
- Consulte también el algoritmo de Newton en la sección Encontrar raíces de ecuaciones no lineales
- Método de gradiente conjugado no lineal
- Métodos sin derivados
- Descenso coordinado : muévase en una de las direcciones de las coordenadas
- Descenso de coordenadas adaptativo : adapte las direcciones de las coordenadas a la función del objetivo
- Descenso de coordenadas aleatorias - versión aleatorizada
- Método de Nelder-Mead
- Búsqueda de patrones (optimización)
- Método de Powell : basado en el descenso de gradiente conjugado
- Métodos de Rosenbrock : método sin derivadas, similar a Nelder-Mead pero con convergencia garantizada
- Descenso coordinado : muévase en una de las direcciones de las coordenadas
- Método lagrangiano aumentado : reemplaza problemas restringidos por problemas no restringidos con un término agregado a la función objetivo
- Búsqueda ternaria
- Búsqueda tabú
- Búsqueda local guiada : modificación de los algoritmos de búsqueda que genera penalizaciones durante una búsqueda
- Optimización de búsqueda reactiva (RSO): el algoritmo adapta sus parámetros automáticamente
- Algoritmo MM : mayorización-minimización, un amplio marco de métodos
- Desviaciones mínimas absolutas
- Algoritmo de maximización de expectativas
- Maximización de expectativas de subconjuntos ordenados
- Algoritmo de maximización de expectativas
- Búsqueda de vecino más cercano
- Mapeo espacial : utiliza modelos "toscos" (ideales o de baja fidelidad) y "finos" (prácticos o de alta fidelidad)
- Conceptos:
Control óptimo y optimización de dimensiones infinitas
Control optimo
- Principio mínimo de Pontryagin : versión de dimensión infinita de los multiplicadores de Lagrange
- Ecuaciones de Costate - ecuación para los "multiplicadores de Lagrange" en el principio mínimo de Pontryagin
- Hamiltoniano (teoría de control) : el principio mínimo dice que esta función debe minimizarse
- Tipos de problemas:
- Regulador lineal-cuadrático : la dinámica del sistema es una ecuación diferencial lineal, el objetivo es cuadrático
- Control lineal-cuadrático-gaussiano (LQG): la dinámica del sistema es una SDE lineal con ruido aditivo, el objetivo es cuadrático
- Ecuaciones de proyección óptimas : método para reducir la dimensión del problema de control de LQG
- Ecuación algebraica de Riccati: ecuación matricial que se presenta en muchos problemas de control óptimo
- Control bang-bang : control que cambia abruptamente entre dos estados
- Principio de mapeo de Covector
- Programación dinámica diferencial : utiliza modelos localmente cuadráticos de la dinámica y las funciones de costo.
- Punto DNSS : estado inicial para ciertos problemas de control óptimo con múltiples soluciones óptimas
- Condición de Legendre-Clebsch: condición de segundo orden para la solución de un problema de control óptimo
- Control óptimo pseudoespectral
- Método pseudoespectral de Bellman : basado en el principio de optimalidad de Bellman
- Método pseudoespectral de Chebyshev : utiliza polinomios de Chebyshev (del primer tipo)
- Método pseudoespectral plano : combina el método pseudoespectral de Ross-Fahroo con planitud diferencial
- Método pseudoespectral de Gauss : utiliza la colocación en los puntos de Legendre-Gauss
- Método pseudoespectral de Legendre : utiliza polinomios de Legendre
- Método de anudado pseudoespectral: generalización de métodos pseudoespectrales en un control óptimo
- Método pseudoespectral de Ross-Fahroo : clase de método pseudoespectral que incluye Chebyshev, Legendre y anudado
- Lema de Ross-Fahroo : condición para que las operaciones de discretización y dualidad se conmuten
- Lema π de Ross : existe una constante de tiempo fundamental dentro de la cual se debe calcular una solución de control para controlar la capacidad de control y la estabilidad.
- Modelo Sethi - publicidad de modelado de problemas de control óptimo
Optimización de dimensiones infinitas
- Programación semi-infinita : número infinito de variables y número finito de restricciones, o al revés
- Optimización de formas , optimización de topología : optimización en un conjunto de regiones
- Derivada topológica - derivada con respecto al cambio en la forma
- Programación semiinfinita generalizada : número finito de variables, número infinito de restricciones
Incertidumbre y aleatoriedad
- Enfoques para hacer frente a la incertidumbre:
- Proceso de decisión de Markov
- Proceso de decisión de Markov parcialmente observable
- Optimización robusta
- El modelo maximin de Wald
- Optimización del escenario : las limitaciones son inciertas
- Aproximación estocástica
- Optimización estocástica
- Programación estocástica
- Descenso de gradiente estocástico
- Algoritmos de optimización aleatorios :
- Búsqueda aleatoria : elija un punto al azar en la bola alrededor de la iteración actual
- Recocido simulado
- Recocido simulado adaptativo : variante en la que los parámetros del algoritmo se ajustan durante el cálculo.
- Gran algoritmo del diluvio
- Recocido de campo medio : variante determinista del recocido simulado
- Optimización bayesiana : trata la función objetiva como una función aleatoria y la coloca a priori.
- Algoritmo evolutivo
- Evolución diferencial
- Programación evolutiva
- Algoritmo genético , Programación genética
- Algoritmos genéticos en economía
- MCACEA (algoritmo evolutivo de coevolución de agentes coordinados múltiples): utiliza un algoritmo evolutivo para cada agente
- Aproximación estocástica de perturbación simultánea (SPSA)
- Luus – Jaakola
- Optimización de Enjambre de partículas
- Túneles estocásticos
- Búsqueda de armonía : imita el proceso de improvisación de los músicos.
- ver también la sección método Monte Carlo
Aspectos teóricos
- Análisis convexo - función f tal que f ( tx + (1 - t ) y ) ≥ tf ( x ) + (1 - t ) f ( y ) para t ∈ [0,1]
- Función pseudoconvexa - función f tal que ∇ f · ( y - x ) ≥ 0 implica f ( y ) ≥ f ( x )
- Función cuasiconvexa - función f tal que f ( tx + (1 - t ) y ) ≤ max ( f ( x ), f ( y )) para t ∈ [0,1]
- Subderivado
- Convexidad geodésica : convexidad para funciones definidas en una variedad de Riemann.
- Dualidad (optimización)
- Dualidad débil : la solución dual da un límite a la solución primaria
- Fuerte dualidad : las soluciones primarias y duales son equivalentes
- Precio sombra
- Cono doble y cono polar
- Brecha de dualidad : diferencia entre solución primaria y dual
- Teorema de dualidad de Fenchel : relaciona los problemas de minimización con los problemas de maximización de conjugados convexos.
- Función de perturbación : cualquier función que se relacione con problemas primarios y duales.
- Condición de Slater: condición suficiente para que la dualidad fuerte se mantenga en un problema de optimización convexa
- Integralidad dual total : concepto de dualidad para programación lineal entera
- Dualidad de Wolfe : para cuando la función objetiva y las restricciones son diferenciables
- Lema de Farkas
- Condiciones de Karush-Kuhn-Tucker (KKT): condiciones suficientes para que una solución sea óptima
- Condiciones de Fritz John : variante de las condiciones de KKT
- Multiplicador de Lagrange
- Multiplicadores de Lagrange en espacios de Banach
- Semi-continuidad
- La teoría de la complementariedad - estudio de los problemas con restricciones de la forma ⟨ u , v ⟩ = 0
- Problema de complementariedad mixta
- Problema de complementariedad lineal mixta
- Algoritmo de Lemke : método para resolver problemas de complementariedad lineal (mixta)
- Problema de complementariedad mixta
- Teorema de Danskin : utilizado en el análisis de problemas minimax
- Teorema del máximo: el máximo y el maximizador son continuos en función de los parámetros, en algunas condiciones
- Sin almuerzo gratis en búsqueda y optimización
- Relajación (aproximación) : aproximación de un problema dado a un problema más fácil al relajar algunas restricciones.
- Relajación lagrangiana
- Relajación de la programación lineal : ignorar las restricciones de integralidad en un problema de programación lineal
- Función autoconcordante
- Costo reducido : costo por aumentar una variable en una pequeña cantidad
- Dureza de aproximación : complejidad computacional de obtener una solución aproximada
Aplicaciones
- En geometría:
- Mediana geométrica : el punto que minimiza la suma de distancias a un conjunto de puntos dado.
- Centro de Chebyshev : el centro de la bola más pequeña que contiene un conjunto determinado de puntos
- En estadísticas:
- Modos condicionales iterados : maximización de la probabilidad conjunta del campo aleatorio de Markov
- Metodología de superficie de respuesta : utilizada en el diseño de experimentos.
- Colocación automática de etiquetas
- Detección comprimida : reconstruye una señal a partir del conocimiento de que es escasa o comprimible
- Problema de stock de corte
- Optimización de la demanda
- Despacho de destino : una técnica de optimización para despachar ascensores
- Minimización de energía
- Maximización de la entropía
- Tolerancia altamente optimizada
- Optimización de hiperparámetros
- Problema de control de inventario
- Modelo de vendedor de noticias
- Modelo extendido de vendedor de noticias
- Sistema de montaje bajo pedido
- Decodificación de programación lineal
- Problema de búsqueda lineal : encuentre un punto en una línea moviéndose a lo largo de la línea
- Aproximación de rango bajo : encuentre la mejor aproximación, la restricción es que el rango de alguna matriz es menor que un número dado
- Meta-optimización : optimización de los parámetros en un método de optimización
- Optimización de diseño multidisciplinar
- Asignación óptima del presupuesto de computación : maximice la eficiencia general de la simulación para encontrar una decisión óptima
- Problema de la bolsa de papel
- Optimización de procesos
- Economía recursiva : las personas toman una serie de decisiones de optimización de dos períodos a lo largo del tiempo.
- Dieta Stigler
- Problema de asignación de espacio
- Mayorización de estrés
- Optimización de trayectoria
- Teoría del transporte
- Optimización de la forma del ala
Diverso
- Optimización combinatoria
- Programación dinámica
- Ecuación de Bellman
- Ecuación de Hamilton-Jacobi-Bellman : análogo en tiempo continuo de la ecuación de Bellman
- Inducción hacia atrás : resolución de problemas de programación dinámica razonando hacia atrás en el tiempo
- Parada óptima : elegir el momento óptimo para realizar una acción en particular
- Algoritmo de probabilidades
- El problema de Robbins
- Optimización global :
- Algoritmo BRST
- Algoritmo MCS
- Optimización multiobjetivo : hay varios objetivos en conflicto
- Algoritmo de Benson : para problemas de optimización de vectores lineales
- Optimización binivel : estudia problemas en los que un problema está incrustado en otro.
- Subestructura óptima
- Algoritmo de proyección de Dykstra : encuentra un punto en la intersección de dos conjuntos convexos
- Conceptos algorítmicos:
- Función barrera
- Método de penalización
- Región de confianza
- Funciones de prueba para optimización :
- Función Rosenbrock: función bidimensional con un valle en forma de plátano
- Función de Himmelblau : bidimensional con cuatro mínimos locales, definidos por
- Función Rastrigin: función bidimensional con muchos mínimos locales
- Función shekel : multimodal y multidimensional
- Sociedad de optimización matemática
Cuadratura numérica (integración)
Integración numérica : la evaluación numérica de una integral.
- Método del rectángulo: método de primer orden, basado en la aproximación constante (por partes)
- Regla trapezoidal : método de segundo orden, basado en la aproximación lineal (por partes)
- Regla de Simpson : método de cuarto orden, basado en la aproximación cuadrática (por partes)
- Método adaptativo de Simpson
- Regla de Boole : método de sexto orden, basado en los valores en cinco puntos equidistantes
- Fórmulas de Newton-Cotes : generaliza los métodos anteriores.
- Método de Romberg : extrapolación de Richardson aplicada a la regla del trapecio
- Cuadratura gaussiana : grado más alto posible con un número determinado de puntos
- Cuadratura de Chebyshev-Gauss : extensión de la cuadratura gaussiana para integrales con peso (1 - x 2 ) ± 1/2 en [−1, 1]
- Cuadratura de Gauss-Hermite - extensión de la cuadratura de Gauss para integrales con peso exp (- x 2 ) en [−∞, ∞]
- Cuadratura de Gauss-Jacobi : extensión de la cuadratura de Gauss para integrales con peso (1 - x ) α (1 + x ) β en [−1, 1]
- Cuadratura de Gauss-Laguerre - extensión de la cuadratura de Gauss para integrales con peso exp (- x ) en [0, ∞]
- Fórmula de cuadratura de Gauss-Kronrod : regla anidada basada en la cuadratura de Gauss
- Reglas de Gauss-Kronrod
- Cuadratura de Tanh-sinh : variante de la cuadratura gaussiana que funciona bien con singularidades en los puntos finales
- Cuadratura de Clenshaw-Curtis : basada en la expansión del integrando en términos de polinomios de Chebyshev
- Cuadratura adaptativa : adaptación de los subintervalos en los que se divide el intervalo de integración en función del integrando
- Integración de Monte Carlo : toma muestras aleatorias del integrando
- Ver también el método #Monte Carlo
- Método de sistemas de estado cuantificado (QSS): basado en la idea de cuantificación de estado
- Cuadratura de Lebedev : utiliza una cuadrícula en una esfera con simetría octaédrica
- Cuadrícula dispersa
- Aproximación de Coopmans
- Diferenciación numérica : para integrales de orden fraccionario
- Suavización y diferenciación numérica
- Método de estado adjunto : aproxima el gradiente de una función en un problema de optimización
- Fórmula de Euler-Maclaurin
Métodos numéricos para ecuaciones diferenciales ordinarias
Métodos numéricos para ecuaciones diferenciales ordinarias : la solución numérica de ecuaciones diferenciales ordinarias (EDO)
- Método Euler: el método más básico para resolver una EDO
- Métodos explícitos e implícitos: los métodos implícitos deben resolver una ecuación en cada paso.
- Método de Euler hacia atrás - variante implícita del método de Euler
- Regla trapezoidal : método implícito de segundo orden
- Métodos de Runge-Kutta : una de las dos clases principales de métodos para problemas de valor inicial
- Método del punto medio : un método de segundo orden con dos etapas
- Método de Heun: un método de segundo orden con dos etapas o un método de tercer orden con tres etapas
- Método Bogacki-Shampine : un método de tercer orden con cuatro etapas (FSAL) y un método integrado de cuarto orden
- Método Cash-Karp : un método de quinto orden con seis etapas y un método integrado de cuarto orden
- Método Dormand-Prince : un método de quinto orden con siete etapas (FSAL) y un método integrado de cuarto orden
- Método de Runge-Kutta-Fehlberg : un método de quinto orden con seis etapas y un método integrado de cuarto orden
- Método de Gauss-Legendre : familia de métodos A-estable con un orden óptimo basado en la cuadratura gaussiana
- Butcher group - formalismo algebraico que involucra árboles enraizados para analizar los métodos de Runge-Kutta
- Lista de métodos Runge-Kutta
- Método lineal de varios pasos : la otra clase principal de métodos para problemas con valores iniciales
- Fórmula de diferenciación hacia atrás : métodos implícitos de orden 2 a 6; especialmente adecuado para ecuaciones rígidas
- Método de Numerov: método de cuarto orden para ecuaciones de la forma
- Método predictor-corrector : utiliza un método para aproximar la solución y otro para aumentar la precisión.
- Métodos lineales generales : una clase de métodos que encapsulan métodos lineales de varios pasos y de Runge-Kutta.
- Algoritmo de Bulirsch-Stoer : combina el método del punto medio con la extrapolación de Richardson para lograr un orden arbitrario
- Integrador exponencial : basado en la división de la EDO en una parte lineal, que se resuelve exactamente, y una parte no lineal.
- Métodos diseñados para la solución de EDO de la física clásica:
- Método Newmark-beta : basado en el teorema extendido del valor medio
- Integración de Verlet : un método popular de segundo orden
- Integración de Leapfrog : otro nombre para la integración de Verlet
- El algoritmo de Beeman : un método de dos pasos que amplía el método Verlet
- Relajación dinámica
- Integrador geométrico : un método que conserva parte de la estructura geométrica de la ecuación.
- Integrador simpléctico: un método para la solución de las ecuaciones de Hamilton que conserva la estructura simpléctica
- Integrador variacional: integradores simplécticos derivados utilizando el principio variacional subyacente
- Método de Euler semi-implícito : variante del método de Euler que es simpléctico cuando se aplica a hamiltonianos separables
- Deriva de energía : fenómeno en el que la energía, que debe conservarse, se aleja debido a errores numéricos.
- Integrador simpléctico: un método para la solución de las ecuaciones de Hamilton que conserva la estructura simpléctica
- Otros métodos para problemas de valor inicial (IVP):
- Línea de retardo bidireccional
- Circuito equivalente de elemento parcial
- Métodos para resolver problemas de valores en la frontera de dos puntos (BVP):
- Método de disparo
- Método de disparo múltiple directo : divide el intervalo en varios subintervalos y aplica el método de disparo en cada subintervalo
- Métodos para resolver ecuaciones algebraicas diferenciales (DAE), es decir, EDO con restricciones:
- Algoritmo de restricción : para resolver las ecuaciones de Newton con restricciones
- Algoritmo de Pantelides : para reducir el índice de una DEA
- Métodos para resolver ecuaciones diferenciales estocásticas (SDE):
- Método Euler-Maruyama - generalización del método Euler para SDE
- Método de Milstein : un método con un fuerte orden uno
- Método de Runge-Kutta (SDE) : generalización de la familia de métodos de Runge-Kutta para SDE
- Métodos para resolver ecuaciones integrales:
- Método de Nyström : reemplaza la integral con una regla de cuadratura
- Análisis:
- Error de truncamiento (integración numérica) : errores de truncamiento local y global y sus relaciones
- Fan de Lady Windermere (matemáticas) : identidad telescópica que relaciona errores de truncamiento local y global
- Error de truncamiento (integración numérica) : errores de truncamiento local y global y sus relaciones
- Ecuación rígida : aproximadamente, una EDO para la que los métodos inestables necesitan un tamaño de paso muy corto, pero los métodos estables no
- Estabilidad L : el método es estable A y la función de estabilidad desaparece al infinito
- Tamaño de paso adaptable : cambia automáticamente el tamaño de paso cuando parece ventajoso
- Parareal : un algoritmo de integración paralelo en el tiempo
Métodos numéricos para ecuaciones diferenciales parciales
Ecuaciones diferenciales parciales numéricas: la solución numérica de ecuaciones diferenciales parciales (PDE)
Métodos de diferencias finitas
Método de diferencias finitas : basado en la aproximación de operadores diferenciales con operadores diferencia
- Diferencia finita : el análogo discreto de un operador diferencial
- Coeficiente de diferencias finitas : tabla de coeficientes de aproximaciones en diferencias finitas a derivadas
- Operador de Laplace discreto : aproximación en diferencias finitas del operador de Laplace
- Autovalores y autovectores de la segunda derivada - incluye autovalores del operador de Laplace discreto
- Suma de Kronecker de laplacianos discretos : se utiliza para el operador de Laplace en múltiples dimensiones
- Ecuación de Poisson discreta: análogo discreto de la ecuación de Poisson utilizando el operador discreto de Laplace
- Plantilla (análisis numérico) : las disposiciones geométricas de los puntos de la cuadrícula afectados por un paso básico del algoritmo
- Plantilla compacta : plantilla que solo usa unos pocos puntos de cuadrícula, generalmente solo los vecinos inmediatos y diagonales
- Esquema compacto de diferencias finitas de orden superior
- Plantilla no compacta : cualquier plantilla que no sea compacta
- Plantilla de cinco puntos: plantilla bidimensional que consta de un punto y sus cuatro vecinos inmediatos en una cuadrícula rectangular
- Plantilla compacta : plantilla que solo usa unos pocos puntos de cuadrícula, generalmente solo los vecinos inmediatos y diagonales
- Métodos en diferencias finitas para la ecuación de calor y las PDE relacionadas:
- Esquema FTCS (espacio central en tiempo de avance) - explícito de primer orden
- Método Crank-Nicolson - implícito de segundo orden
- Métodos de diferencias finitas para PDE hiperbólicas como la ecuación de onda:
- Método Lax-Friedrichs : explícito de primer orden
- Método Lax-Wendroff : explícito de segundo orden
- Método MacCormack : explícito de segundo orden
- Esquema de ceñida
- Esquema de diferenciación a barlovento para convección : esquema de primer orden para problemas de convección-difusión
- Teorema de Lax-Wendroff : esquema conservador para el sistema hiperbólico de leyes de conservación que converge a la solución débil
- Método implícito de dirección alterna (ADI): actualice usando el flujo en la dirección x y luego usando el flujo en la dirección y
- Esquema de diferencias finitas no estándar
- Aplicaciones específicas:
- Métodos de diferencias finitas para la fijación de precios de opciones
- Método de dominio del tiempo de diferencias finitas: un método de diferencias finitas para la electrodinámica
Métodos de elementos finitos, métodos de discretización de gradientes
Método de elementos finitos - basado en una discretización del espacio de soluciones método de discretización de gradiente - basado tanto en la discretización de la solución como de su gradiente
- Método de elementos finitos en mecánica estructural : un enfoque físico de los métodos de elementos finitos
- Método de Galerkin : un método de elementos finitos en el que el residuo es ortogonal al espacio de elementos finitos
- Método de Galerkin discontinuo : un método de Galerkin en el que la solución aproximada no es continua
- Método de Rayleigh-Ritz : un método de elementos finitos basado en principios variacionales
- Método de elementos espectrales : métodos de elementos finitos de orden superior
- hp-FEM - variante en la que tanto el tamaño como el orden de los elementos se adaptan automáticamente
- Ejemplos de elementos finitos:
- Elemento cuadrilátero bilineal , también conocido como elemento Q4
- Elemento triangular de deformación constante (CST): también conocido como elemento T3
- Elemento cuadrilátero cuadrático , también conocido como elemento Q8
- Elementos Barsoum
- Método de rigidez directa : una implementación particular del método de elementos finitos, que se utiliza a menudo en el análisis estructural.
- Método Trefftz
- Actualización de elementos finitos
- Método de elementos finitos extendido : coloca funciones adaptadas al problema en el espacio de aproximación
- Elementos con clasificación funcional : elementos para describir materiales con clasificación funcional
- Superelemento : agrupación particular de elementos finitos, empleados como un solo elemento
- Método de elementos finitos de intervalo : combinación de elementos finitos con aritmética de intervalo
- Cálculo exterior discreto: forma discreta del cálculo exterior de geometría diferencial
- Análisis modal usando FEM - solución de problemas de valores propios para encontrar vibraciones naturales
- El lema de Céa : la solución en el espacio de elementos finitos es una aproximación casi óptima en ese espacio de la verdadera solución.
- Prueba de parche (elementos finitos) : prueba simple de la calidad de un elemento finito
- MAFELAP (MAthematics of Finite ELements and APplications) - conferencia internacional celebrada en la Universidad de Brunel
- NAFEMS : organización sin fines de lucro que establece y mantiene estándares en el análisis de ingeniería asistido por computadora.
- Optimización de topología multifase : técnica basada en elementos finitos para determinar la composición óptima de una mezcla
- Elemento finito de intervalo
- Método de elemento aplicado : para la simulación de grietas y colapso estructural
- Método Wood-Armer: método de análisis estructural basado en elementos finitos que se utiliza para diseñar armaduras para losas de hormigón.
- Análisis isogeométrico : integra elementos finitos en herramientas de diseño CAD basadas en NURBS convencionales
- Iteración de Loubignac
- Matriz de rigidez : análogo de dimensión finita del operador diferencial
- Combinación con métodos sin malla:
- Forma débil debilitada : forma de una PDE que es más débil que la forma débil estándar
- Espacio G: espacio funcional utilizado para formular la forma débil debilitada.
- Método de elementos finitos suavizados
- Método variacional multiescala
- Lista de paquetes de software de elementos finitos
Otros metodos
- Método espectral : basado en la transformación de Fourier
- Método pseudo-espectral
- Método de líneas : reduce la PDE a un gran sistema de ecuaciones diferenciales ordinarias.
- Método de elemento de límite (BEM): basado en la transformación de la PDE en una ecuación integral en el límite del dominio.
- Método de elemento de límite de intervalo : una versión que utiliza aritmética de intervalo
- Método del elemento analítico : similar al método del elemento de contorno, pero la ecuación integral se evalúa analíticamente
- Método de volumen finito : se basa en dividir el dominio en muchos dominios pequeños; popular en dinámica de fluidos computacional
- Esquema de Godunov: esquema conservador de primer orden para el flujo de fluidos, basado en una aproximación constante por partes
- Esquema MUSCL : variante de segundo orden del esquema de Godunov
- AUSM - método de división por advección aguas arriba
- Limitador de flujo : limita las derivadas espaciales (flujos) para evitar oscilaciones falsas
- Solucionador de Riemann : un solucionador de problemas de Riemann (una ley de conservación con datos constantes por partes)
- Propiedades de los esquemas de discretización : los métodos de volumen finito pueden ser conservadores, acotados, etc.
- Método de elementos discretos : un método en el que los elementos pueden moverse libremente entre sí.
- Método de elemento discreto extendido : agrega propiedades como la tensión a cada partícula
- Autómata celular móvil : combinación de autómatas celulares con elementos discretos
- Métodos sin malla: no usa una malla, pero usa una vista de partículas del campo
- Método sin malla de mínimos cuadrados discretos : basado en la minimización de la suma ponderada del cuadrado residual
- Método de elemento difuso
- Método de conjunto de puntos finito : representa el continuo mediante una nube de puntos
- Método semi-implícito de partículas móviles
- Método de soluciones fundamentales (MFS): representa la solución como combinación lineal de soluciones fundamentales
- Variantes de MFS con puntos de origen en el límite físico:
- Método del nudo límite (BKM)
- Método de partículas límite (BPM)
- Método sin malla regularizado (RMM)
- Método de límite singular (SBM)
- Métodos diseñados para problemas de electromagnetismo:
- Método de dominio del tiempo de diferencias finitas: un método de diferencias finitas
- Análisis riguroso de ondas acopladas: método semi-analítico del espacio de Fourier basado en el teorema de Floquet
- Método de matriz de línea de transmisión (TLM): basado en la analogía entre el campo electromagnético y la malla de líneas de transmisión.
- Teoría uniforme de la difracción : diseñada específicamente para problemas de dispersión.
- Partícula en celda : se utiliza especialmente en dinámica de fluidos
- Método de partículas en celda multifase : considera las partículas sólidas como partículas numéricas y fluidas
- Esquema de alta resolución
- Método de captura de impactos
- Confinamiento de vorticidad : para flujos dominados por vórtices en dinámica de fluidos, similar a la captura de impactos
- Método de paso dividido
- Método de marcha rápida
- Colocación ortogonal
- Métodos de Lattice Boltzmann : para la solución de las ecuaciones de Navier-Stokes
- Solucionador de Roe - para la solución de la ecuación de Euler
- Relajación (método iterativo) : un método para resolver PDE elípticas convirtiéndolas en ecuaciones de evolución.
- Amplias clases de métodos:
- Métodos miméticos : métodos que respetan en cierto sentido la estructura del problema original.
- Multifísica : modelos que constan de varios submodelos con diferentes físicas.
- Método de contorno sumergido : para simular estructuras elásticas sumergidas en fluidos
- Integrador multisimpléctico : extensión de integradores simplécticos, que son para ODE
- Método de cuadrícula estirada : para la solución de problemas que pueden estar relacionados con el comportamiento de una cuadrícula elástica.
Técnicas para mejorar estos métodos
- Método de red múltiple : utiliza una jerarquía de mallas anidadas para acelerar los métodos.
- Métodos de descomposición de dominios : divide el dominio en algunos subdominios y resuelve el PDE en estos subdominios.
- Método de Schwarz aditivo
- Método de Schwarz aditivo abstracto: versión abstracta del Schwarz aditivo sin referencia a información geométrica
- Método de descomposición de dominio de equilibrio (BDD): preacondicionador para matrices definidas positivas simétricas
- Equilibrio de la descomposición de dominios por restricciones (BDDC): mayor desarrollo de BDD
- Desgarro e interconexión de elementos finitos (FETI)
- FETI-DP : mayor desarrollo de FETI
- Método de dominio ficticio : preacondicionador construido con una malla estructurada en un dominio ficticio de forma simple
- Métodos de mortero : las mallas del subdominio no encajan
- Método de Neumann-Dirichlet : combina el problema de Neumann en un subdominio con el problema de Dirichlet en otro subdominio
- Métodos de Neumann-Neumann: métodos de descomposición de dominios que utilizan problemas de Neumann en los subdominios
- Operador de Poincaré-Steklov : asigna el campo eléctrico tangencial a la corriente eléctrica equivalente
- Método del complemento de Schur: método temprano y básico en subdominios que no se superponen
- Método alternativo de Schwarz: método básico y temprano en subdominios que se superponen
- Espacio grueso : variante del problema que utiliza una discretización con menos grados de libertad
- Refinamiento de malla adaptable : utiliza la solución calculada para refinar la malla solo cuando sea necesario
- Método rápido multipolar: método jerárquico para evaluar las interacciones partícula-partícula
- Capa perfectamente combinada: capa absorbente artificial para ecuaciones de onda, utilizada para implementar condiciones de contorno de absorción
Rejillas y mallas
- Clasificación de rejilla / Tipos de malla :
- Malla poligonal : consta de polígonos en 2D o 3D
- Malla triangular : consta de triángulos en 2D o 3D
- Triangulación (geometría) : subdivisión de una región dada en triángulos, o análogo de dimensiones superiores
- Malla no opaca : malla en la que todos los ángulos son menores o iguales a 90 °
- Triangulación de conjunto de puntos: malla triangular de manera que un conjunto de puntos dado son todos un vértice de un triángulo
- Triangulación de polígonos : malla triangular dentro de un polígono
- Triangulación de Delaunay : triangulación tal que ningún vértice está dentro del circuncentro de un triángulo
- Triangulación de Delaunay restringida : generalización de la triangulación de Delaunay que fuerza ciertos segmentos requeridos en la triangulación.
- Triangulación de Pitteway : para cualquier punto, el triángulo que lo contiene tiene el vecino más cercano del punto como vértice
- Triangulación de peso mínimo : triangulación de la longitud total mínima del borde
- Triangulación cinética : una triangulación que se mueve con el tiempo.
- Red irregular triangulada
- Cuasi-triangulación : subdivisión en simples, donde los vértices no son puntos sino segmentos de línea inclinados arbitrarios
- Malla de volumen : consta de formas tridimensionales
- Cuadrícula regular : consta de paralelogramos congruentes o análogos de dimensiones superiores.
- Cuadrícula no estructurada
- Cuadrícula geodésica: cuadrícula isotrópica en una esfera
- Generación de mallas
- Mallado basado en imágenes : procedimiento automático para generar mallas a partir de datos de imágenes 3D
- Cubos de marcha : extrae una malla poligonal de un campo escalar.
- Generación de mallas paralelas
- Algoritmo de Ruppert : crea triangularización Delauney de calidad a partir de datos lineales por partes
- Subdivisiones:
- Red apolínea : gráfico no dirigido formado al subdividir de forma recursiva un triángulo
- Subdivisión baricéntrica : forma estándar de dividir polígonos convexos arbitrarios en triángulos, o el análogo de dimensión superior
- Mejora de una malla existente:
- Segundo algoritmo de Chew : mejora la triangularización de Delauney refinando triángulos de baja calidad
- Suavizado laplaciano : mejora las mallas polinómicas moviendo los vértices
- Algoritmo Jump-and-Walk : para encontrar un triángulo en una malla que contiene un punto dado
- Continuo de torsión espacial : representación dual de una malla que consta de hexaedros
- Pseudotriángulo : región simplemente conectada entre tres conjuntos convexos mutuamente tangentes
- Complejo simple : todos los vértices, segmentos de línea, triángulos, tetraedros, ..., formando una malla
Análisis
- Teorema de equivalencia laxa : un método consistente es convergente si y solo si es estable
- Condición de Courant-Friedrichs-Lewy: condición de estabilidad para PDE hiperbólicas
- Análisis de estabilidad de Von Neumann : todos los componentes de Fourier del error deben ser estables
- Difusión numérica : difusión introducida por el método numérico, por encima de lo que está naturalmente presente.
- Difusión falsa
- Dispersión numérica
- Resistividad numérica : la misma, con resistividad en lugar de difusión.
- Formulación débil : una reformulación funcional-analítica de la PDE necesaria para algunos métodos.
- Disminución de la variación total : propiedad de los esquemas que no introducen oscilaciones espurias
- Teorema de Godunov: los esquemas lineales monótonos solo pueden ser de primer orden
- Problema de Motz: problema de referencia para problemas de singularidad
Método de Montecarlo
- Variantes del método Monte Carlo:
- Simulación directa Monte Carlo
- Método cuasi-Monte Carlo
- Cadena de Markov Monte Carlo
- Algoritmo de Metropolis-Hastings
- Metropolis de múltiples intentos : modificación que permite tamaños de paso más grandes
- Algoritmo de Wang y Landau - extensión de Metropolis Monte Carlo
- Ecuación de cálculos de estado por máquinas de cómputo rápido - artículo de 1953 que propone el algoritmo Metropolis Monte Carlo
- Conjunto multiconónico : técnica de muestreo que utiliza Metropolis-Hastings para calcular integrales
- Muestreo de Gibbs
- Acoplamiento del pasado
- Salto reversible cadena Markov Monte Carlo
- Algoritmo de Metropolis-Hastings
- Método dinámico de Monte Carlo
- Montecarlo cinético
- Algoritmo de Gillespie
- Filtro de partículas
- Filtro de partículas auxiliar
- Montecarlo inverso
- Algoritmo de demonio
- Muestreo de números pseudoaleatorios
- Muestreo por transformada inversa : método general y sencillo pero computacionalmente costoso
- Muestreo de rechazo : muestra de una distribución más simple pero rechaza algunas de las muestras
- Algoritmo Zigurat : utiliza una tabla precalculada que cubre la distribución de probabilidad con segmentos rectangulares.
- Para el muestreo de una distribución normal:
- Transformada de Box-Muller
- Método polar de Marsaglia
- Generador de números aleatorios de convolución : genera una variable aleatoria como una suma de otras variables aleatorias
- Búsqueda indexada
- Técnicas de reducción de varianza :
- Variantes antitéticas
- Variables de control
- Muestreo de importancia
- Muestreo estratificado
- Algoritmo VEGAS
- Secuencia de baja discrepancia
- Construcciones de secuencias de discrepancia baja
- Generador de eventos
- Templado paralelo
- Muestreo de paraguas : mejora el muestreo en sistemas físicos con barreras energéticas significativas
- Montecarlo híbrido
- Filtro de conjunto Kalman: filtro recursivo adecuado para problemas con una gran cantidad de variables
- Muestreo de ruta de transición
- Método Walk-on-Spheres : para generar puntos de salida del movimiento browniano a partir de dominios delimitados
- Aplicaciones:
- Pronóstico por conjuntos : produce múltiples predicciones numéricas a partir de condiciones o parámetros ligeramente iniciales
- Modelo de fluctuación de enlaces : para simular la conformación y la dinámica de los sistemas de polímeros
- Filtrado iterado
- Transporte ligero Metropolis
- Localización de Monte Carlo : estima la posición y orientación de un robot
- Métodos de Monte Carlo para el transporte de electrones
- Método de Monte Carlo para el transporte de fotones
- Métodos de Monte Carlo en finanzas
- Métodos de Monte Carlo para la fijación de precios de opciones
- Métodos cuasi-Monte Carlo en finanzas
- Modelado molecular de Monte Carlo
- Dinámica molecular integral de ruta : incorpora integrales de ruta de Feynman
- Montecarlo cuántico
- Difusión Monte Carlo : utiliza una función de Green para resolver la ecuación de Schrödinger
- Monte Carlo cuántico gaussiano
- Ruta integral Monte Carlo
- Reptation Monte Carlo
- Montecarlo variacional
- Métodos para simular el modelo de Ising:
- Algoritmo de Swendsen-Wang : toda la muestra se divide en grupos de espín iguales
- Algoritmo de Wolff : mejora del algoritmo de Swendsen-Wang
- Algoritmo de Metropolis-Hastings
- Campo auxiliar Monte Carlo : calcula promedios de operadores en problemas de mecánica cuántica de muchos cuerpos
- Método de entropía cruzada : para optimización multi-extrema y muestreo de importancia
- Consulte también la lista de temas de estadísticas.
Aplicaciones
- Física computacional
- Electromagnetismo computacional
- Dinámica de fluidos computacional (CFD)
- Métodos numéricos en mecánica de fluidos
- Gran simulación de remolinos
- Hidrodinámica de partículas suavizadas
- Analogía aeroacústica: se utiliza en aeroacústica numérica para reducir las fuentes de sonido a tipos de emisores simples.
- Método estocástico euleriano lagrangiano : utiliza la descripción euleriana para fluidos y lagrangiana para estructuras
- Modelo de estrés algebraico explícito
- Magnetohidrodinámica computacional (CMHD): estudia fluidos conductores de electricidad
- Modelo climático
- Predicción numérica del tiempo
- Cuadrícula geodésica
- Mecánica celeste
- Modelo numérico del sistema solar
- Método de salto cuántico : utilizado para simular sistemas cuánticos abiertos, opera en función de onda
- Método de análisis de diseño dinámico (DDAM): para evaluar el efecto de las explosiones submarinas en el equipo
- Quimica computacional
- Listas de celdas
- Clúster acoplado
- Teoría funcional de la densidad
- DIIS - inversión directa en (o de) el subespacio iterativo
- Sociología computacional
- Estadística computacional
Software
Para obtener una lista grande de software, consulte la lista de software de análisis numérico .
Revistas
- Acta Numerica
- Matemáticas de la computación (publicado por la American Mathematical Society )
- Revista de Matemática Computacional y Aplicada
- BIT Matemáticas numéricas
- Numerische Mathematik
- Revistas de la Society for Industrial and Applied Mathematics
- Revista SIAM de Análisis Numérico
- Revista SIAM de Computación Científica
Investigadores
- Cleve Moler
- Gene H. Golub
- James H. Wilkinson
- Margaret H. Wright
- Nicholas J. Higham
- Nick Trefethen
- Peter Lax
- Richard S. Varga
- Ulrich W. Kulisch
- Vladik Kreinovich