Respuestas
¿Demasiados anuncios?
Esta es mi primera respuesta larga en matemáticas.de la pila, pero pidió algo estoy trabajando en el.
Si usted está interesado en la algorítmica de los resultados reales y ecuaciones, entonces uno podría decir que para polinomios, todo es decidable y para más funciones generales, casi todo es indecidible. En particular, el conjunto de primer orden de la teoría de los números reales con la multiplicación es decidable, así que usted puede incluir ecuaciones polinómicas, cuantificadores, disyunciones, etc.
Sin embargo, una vez que permite el uso arbitrario de funciones complicadas que contiene composiciones de polinomios y el pecado de la función, entonces la existencia de una solución ya algorítmicamente indecidible.
Común de los paquetes de software se basan en métodos iterativos, creo que la mayoría de ellos utilizan algunas variantes del método de Newton; pero el resultado anterior muestra que usted no puede tener la integridad de los resultados de uso de este tipo de algoritmos.
Para dominios compactos y algunos razonablemente computable funciones de entrada, todavía hay indecidible resultados, mira esta pregunta que yo pregunté en mathoverflow.
Si usted tiene $n$ ecuaciones en $n$ variables $f(x)=0$ en un almacén de cuadro de $B=[0,1]^n$ tal que $f$ razonablemente puede ser representado en un equipo - por ejemplo, es una combinación de funciones comunes -, entonces siempre se puede refutar la existencia de una solución por medio de la aritmética de intervalos, si la solución no existe; sin embargo, dicho algoritmo nunca iba a terminar si la solución existe. Por otro lado, se puede demostrar la existencia de una solución si $0\notin f(\partial B)$ y el grado $\deg(f,B)\neq 0$ (el grado puede ser calculada); esto es equivalente a nonextendability de $\partial B\to\mathbb{R}^n\setminus\{0\}$ a un mapa continuo $B\to\mathbb{R}^n\setminus\{0\}$. Este es siempre el caso si la solución es robusto (es decir, resistente al wrt. las perturbaciones de la $f$); por esta declaración y un poco de la historia del problema, aquí está un artículo sobre este tema. Esta es una analogía a la determinante, ya que si el determinante es distinto de cero, la solución también es "estable" wrt. pequeñas perturbaciones de las ecuaciones.
Una pregunta interesante es si, para una pieza de sabios lineal mapa de $f: K\to\mathbb{R}^n$ en un número finito de simplicial complejo de $K$ y un número de $\alpha>0$, si se sostiene que para cada una de las $\alpha$-perturbación $g$ $f$ (que es, $\|g-f\|\leq \alpha)$, $g(x)=0$ tiene una solución en $K$. Sorprendentemente, esto es decidable si $\dim K\leq 2n-3$ o $n$ es aún, y indecidible por un extraño $n$ y arbitraria $K$. Usted puede encontrar el correspondiente papel aquí.
@Julie Kirk;
Iteración es el arma principal para resolverlos. Newton es un método iterativo. Si alguna vez desea entrar en algunos de los problemas prácticos relacionados con conseguir aciertos iniciales y luego de problemas trate de "Métodos numéricos que trabajan (generalmente)" Forman S. Acton o "Real computación hecho Real" de Acton. Pero sólo si usted es serio acerca de saber porque son difíciles.
