Hispanopedia Wiki
Articulo de referencia

Certificación numérica

La certificación numérica es el proceso de verificar la corrección de una solución candidata a un sistema de ecuaciones . En matemáticas computacionales (numéricas), como la geo...

Hispanopedia WikiContenido en espanolLectura gratuita

La certificación numérica es el proceso de verificar la corrección de una solución candidata a un sistema de ecuaciones . En matemáticas computacionales (numéricas), como la geometría algebraica numérica , las soluciones candidatas se calculan algorítmicamente, pero existe la posibilidad de que contengan errores. Por ejemplo, además de la inexactitud de los datos de entrada y las soluciones candidatas, los errores numéricos o los errores en la discretización del problema pueden dar lugar a soluciones candidatas erróneas. El objetivo de la certificación numérica es proporcionar un certificado que demuestre cuáles de estas soluciones candidatas son, efectivamente, soluciones aproximadas.

Los métodos de certificación se pueden dividir en dos tipos: certificación a priori y certificación a posteriori . La certificación a posteriori confirma la corrección de las respuestas finales (independientemente de cómo se generen), mientras que la certificación a priori confirma la corrección de cada paso de un cálculo específico. Un ejemplo típico de certificación a posteriori es la teoría alfa de Smale , mientras que un ejemplo típico de certificación a priori es la aritmética de intervalos .

Certificados

Un certificado para una raíz es una prueba computacional de la corrección de una solución candidata. Por ejemplo, un certificado puede consistir en una solución aproximada.incógnita{\displaystyle x}, una regiónR{\displaystyle R}que contieneincógnita{\displaystyle x}y una prueba de queR{\displaystyle R}Contiene exactamente una solución al sistema de ecuaciones.

En este contexto, un certificado numérico a priori es un certificado de corrección en el sentido informático . Por otro lado, un certificado numérico a posteriori opera únicamente sobre soluciones, independientemente de cómo se hayan calculado. Por lo tanto, la certificación a posteriori es diferente de la corrección algorítmica; por ejemplo, un algoritmo podría generar candidatos aleatoriamente e intentar certificarlos como raíces aproximadas mediante una certificación a posteriori .

Métodos de certificación a posteriori

Existen diversos métodos para la certificación a posteriori , entre ellos:

teoría alfa

La piedra angular de la teoría alfa de Smale es la acotación del error para el método de Newton . El trabajo de Smale de 1986 [ 1 ] introdujo la cantidadα{\displaystyle \alpha }, que cuantifica la convergencia del método de Newton. Más precisamente, seaF{\displaystyle F}ser un sistema de funciones analíticas en las variablesincógnita{\displaystyle x},D{\displaystyle D}el operador de derivada ynorte{\displaystyle N}El operador de Newton. Las cantidades β(F,incógnita)=‖incógnita−norte(incógnita)‖=‖DF(incógnita)−1F(incógnita)‖{\displaystyle \beta (f,x)=\|xN(x)\|=\|Df(x)^{-1}f(x)\|}γ(F,incógnita)=sorberk≥2‖DF(incógnita)−1DkF(incógnita)k¡‖1k−1{\displaystyle \gamma (f,x)=\sup _{k\geq 2}\left\|{\frac {Df(x)^{-1}D^{k}f(x)}{k!}}\right\|^{\frac {1}{k-1}}} y α(F,incógnita)=β(F,incógnita)γ(F,incógnita){\displaystyle \alpha (f,x)=\beta (f,x)\gamma (f,x)} se utilizan para certificar una solución candidata. En particular, si α(F,incógnita)<13−3174,{\displaystyle \alpha (f,x)<{\frac {13-3{\sqrt {17}}}{4}},} entoncesincógnita{\displaystyle x}es una solución aproximada paraF{\displaystyle f}, es decir, el candidato está en el dominio de convergencia cuadrática para el método de Newton. En otras palabras, si se cumple esta desigualdad, entonces hay una raízincógnita∗{\displaystyle x^{\ast }}deF{\displaystyle F}de modo que las iteraciones del operador de Newton convergen como ‖nortek(incógnita)−incógnita∗‖≤122k−1‖incógnita−incógnita∗‖.{\displaystyle \left\|N^{k}(x)-x^{\ast }\right\|\leq {\frac {1}{2^{2^{k}-1}}}\|xx^{\ast }\|.}

El paquete de software alphaCertified proporciona una implementación de la prueba alfa para polinomios mediante la estimaciónβ{\displaystyle \beta }yγ{\displaystyle \gamma }. [ 2 ]

Métodos de Newton y Krawczyck por intervalos

SuponerGRAMO:Rnorte→Rnorte{\displaystyle G:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}}es una función cuyos puntos fijos corresponden a las raíces deF{\displaystyle F}. Por ejemplo, el operador de Newton tiene esta propiedad. Supongamos queI{\displaystyle I}es una región, entonces,

  1. SiGRAMO{\displaystyle G}mapasI{\displaystyle I}en sí mismo, es decir,GRAMO(I)⊆I{\displaystyle G(I)\subsetequ I}, luego por el teorema del punto fijo de Brouwer ,GRAMO{\displaystyle G}tiene al menos un punto fijo enI{\displaystyle I}y, por lo tantoF{\displaystyle F}tiene al menos una raíz enI{\displaystyle I}.
  2. SiGRAMO{\displaystyle G}es contractiva en una región que contieneI{\displaystyle I}, entonces hay como máximo una raíz enI{\displaystyle I}.

Existen versiones de los siguientes métodos aplicadas a los números complejos, pero tanto la aritmética de intervalos como las condiciones deben ajustarse para reflejar este caso.

Método de Newton por intervalos

En el caso univariado, el método de Newton se puede generalizar directamente para certificar una raíz en un intervalo. Para un intervaloJ{\displaystyle J}, dejarmetro(J){\displaystyle m(J)}ser el punto medio deJ{\displaystyle J}. Luego, el operador de Newton de intervalo aplicado aJ{\displaystyle J}es

Inorte(J)=metro(J)−F(metro(J))/F′(J).{\displaystyle IN(J)=m(J)-F(m(J))/F'(J).}

En la práctica, cualquier intervalo que contengaF′(J){\displaystyle F'(J)}puede utilizarse en este cálculo. Siincógnita{\displaystyle x}es una raíz deF{\displaystyle F}, entonces por el teorema del valor medio , hay algúndo∈J{\displaystyle c\in J}de tal manera queF(metro(J))−F′(do)(metro(J)−incógnita)=F(incógnita)=0{\displaystyle F(m(J))-F'(c)(m(J)-x)=F(x)=0}. En otras palabras,F(metro(J))=F′(do)(metro(J)−incógnita){\displaystyle F(m(J))=F'(c)(m(J)-x)}. DesdeF′(J){\displaystyle F'(J)}contiene el inverso deF{\displaystyle F}en todos los puntos deJ{\displaystyle J}De ello se deduce quemetro(J)−incógnita∈F(metro(J))/F′(J){\displaystyle m(J)-x\in F(m(J))/F'(J)}. Por lo tanto,incógnita=metro(J)−(metro(J)−incógnita)∈Inorte(J){\displaystyle x=m(J)-(m(J)-x)\in IN(J)}.

Además, si0∉F′(J){\displaystyle 0\not \in F'(J)}, entonces ometro(J){\displaystyle m(J)}es una raíz deF{\displaystyle F}yInorte(J)={metro(J)}{\displaystyle IN(J)=\{m(J)\}}ometro(J)∉Inorte(J){\displaystyle m(J)\not \in IN(J)}. Por lo tanto,J∩norte(J){\displaystyle J\cap N(J)}es como máximo la mitad del ancho deJ{\displaystyle J}. Por lo tanto, si hay alguna raíz deF{\displaystyle F}enJ{\displaystyle J}, el procedimiento iterativo de reemplazoJ{\displaystyle J}porJ∩Inorte(J){\displaystyle J\cap IN(J)}convergerá a esta raíz. Si, por otro lado, no hay raíz deF{\displaystyle F}enJ{\displaystyle J}Este procedimiento iterativo acabará produciendo un intervalo vacío, testimonio de la inexistencia de raíces.

Consulte el método de Newton por intervalos para ver análogos de este enfoque en dimensiones superiores.

Método de Krawczyck

DejarY{\displaystyle Y}ser cualquieranorte×norte{\displaystyle n\times n}matriz invertible enGRAMOL(norte,R){\displaystyle GL(n,\mathbb {R} )}Normalmente, uno tomaY{\displaystyle Y}ser una aproximación aF′(y)−1{\displaystyle F'(y)^{-1}}. Luego, define la funciónGRAMO(incógnita)=incógnita−YF(incógnita).{\displaystyle G(x)=x-YF(x).} Observamos queincógnita{\displaystyle x}es un fijo deGRAMO{\displaystyle G}si y solo siincógnita{\displaystyle x}es una raíz deF{\displaystyle F}Por lo tanto, el enfoque anterior puede utilizarse para identificar las raíces deF{\displaystyle F}Este enfoque es similar a una versión multivariada del método de Newton, reemplazando la derivada con la matriz fija.Y{\displaystyle Y}.

Observamos que siJ{\displaystyle J}es una región compacta y convexa yy∈J{\displaystyle y\in J}, entonces, para cualquierincógnita∈J{\displaystyle x\in J}, existendo1,…,donorte∈J{\displaystyle c_{1},\dots ,c_{n}\in J}de tal manera que

GRAMO(y)−GRAMO(incógnita)=[∇gramo1(do1)T⋮∇gramonorte(donorte)T](y−incógnita).{\displaystyle G(y)-G(x)={\begin{bmatrix}\nabla g_{1}(c_{1})^{T}\\\vdots \\\nabla g_{n}(c_{n})^{T}\end{bmatrix}}(y-x).}

DejarGRAMO′(J){\displaystyle G'(J)}sea ​​la matriz jacobiana deGRAMO{\displaystyle G}evaluado enJ{\displaystyle J}. En otras palabras, la entrada(GRAMO′(J))ij{\displaystyle (G'(J))_{ij}}consiste en la imagen de∂gramoi∂incógnitaj{\displaystyle {\frac {\partial g_{i}}{\partial x_{j}}}}encimaJ{\displaystyle J}De ello se deduce queGRAMO(incógnita)∈GRAMO(y)+∇GRAMO(J)(incógnita−y),{\displaystyle G(x)\in G(y)+\nabla G(J)(x-y),} donde el producto matriz-vector se calcula utilizando aritmética de intervalos. Luego, permitiendoincógnita{\displaystyle x}variar enJ{\displaystyle J}, de ello se deduce que la imagen deGRAMO{\displaystyle G}enJ{\displaystyle J}Satisface la siguiente condición de contención:GRAMO(J)⊂GRAMO(y)+GRAMO′(J)(J−y),{\displaystyle G(J)\subset G(y)+G'(J)(J-y),} donde los cálculos se realizan, una vez más, utilizando aritmética de intervalos. Combinando esto con la fórmula paraGRAMO{\displaystyle G}El resultado es el operador de Krawczyck.

Ky,Y(J)=y−YF(y)+(I−F′(J))(J−y),{\displaystyle K_{y,Y}(J)=y-YF(y)+(I-F'(J))(J-y),}

dóndeI{\displaystyle I}es la matriz identidad .

SiKy,Y(J)⊂J{\displaystyle K_{y,Y}(J)\subset J}, entoncesGRAMO{\displaystyle G}tiene un punto fijo enJ{\displaystyle J}, es decir,F{\displaystyle F}tiene raíz enJ{\displaystyle J}Por otro lado, si la norma máxima de la matriz utiliza la norma del supremo para vectores de todas las matrices enI−F′(J){\displaystyle I-F'(J)}es menor que1{\displaystyle 1}, entoncesGRAMO{\displaystyle G}es contractivo dentroJ{\displaystyle J}, entoncesGRAMO{\displaystyle G}tiene un punto fijo único.

Una prueba más sencilla, cuandoJ{\displaystyle J}es un paralelepípedo alineado con los ejes, utilizay=metro(J){\displaystyle y=m(J)}, es decir, el punto medio deJ{\displaystyle J}. En este caso, hay una raíz única deF{\displaystyle F}si

‖K(incógnita)−metro(incógnita)‖<w(incógnita)2,{\displaystyle \|K(X)-m(X)\|<{\frac {w(X)}{2}},}

dóndew(incógnita){\displaystyle w(X)}es la longitud del lado más largo deJ{\displaystyle J}.

Prueba de Miranda

  • Prueba de Miranda (Yap, Vegter, Sharma)

Métodos de certificación a priori

  • Aritmética de intervalos (Moore, Arb, Mezzarobba)
  • Números de condición (Beltran–Leykin)

aritmética de intervalos

La aritmética de intervalos permite obtener un certificado numérico a priori mediante el cálculo de intervalos que contienen soluciones únicas. Al utilizar intervalos en lugar de tipos numéricos simples durante el seguimiento de rutas, los candidatos resultantes se representan mediante intervalos. El intervalo de solución candidato constituye en sí mismo el certificado, ya que garantiza que la solución se encuentra dentro de dicho intervalo.

Números de condición

La geometría algebraica numérica resuelve sistemas polinomiales mediante métodos de continuación homotópica y seguimiento de trayectorias. Al monitorear el número de condición de una homotopía rastreada en cada paso y asegurar que ninguna trayectoria de solución se cruce, se puede calcular un certificado numérico junto con la solución. Este esquema se denomina seguimiento de trayectorias a priori . [ 3 ]

El seguimiento de trayectorias numéricas no certificado se basa en métodos heurísticos para controlar el tamaño del paso de tiempo y la precisión. [ 4 ] En contraste, el seguimiento de trayectorias certificado a priori va más allá de las heurísticas para proporcionar un control del tamaño del paso que garantiza que para cada paso a lo largo de la trayectoria, el punto actual se encuentre dentro del dominio de convergencia cuadrática para la trayectoria actual.

Referencias

  1. ↑ Smale, Steve (1986). "El método de Newton estima a partir de datos en un punto". La fusión de disciplinas: nuevas direcciones en matemáticas puras, aplicadas y computacionales : 185–196 .
  2. ↑ Hauenstein, Jonathan; Sottile, Frank (2012). "Algoritmo 921: alphaCertified: certificación de soluciones a sistemas polinomiales". ACM Transactions on Mathematical Software . 38 (4): 28. doi : 10.1145/2331130.2331136 .
  3. ↑ Beltran, Carlos; Leykin, Anton (2012). "Seguimiento de homotopía numérica certificada". Matemáticas Experimentales . 21 (1): 69– 83.
  4. ↑ Bates, Daniel; Hauenstein, Jonathan; Sommese, Andrew; Wampler, Charles (2009). "Control del tamaño de paso para el seguimiento de trayectorias". Matemáticas Contemporáneas . 496 (21).