Resolución de sistemas de ecuaciones cuadráticas

Question

Hay algoritmos eficientes para resolver un sistema de ecuaciones lineales de la forma

$$\forall i \qquad 0 = a^i + \sum_j b^i_j x^j$$

o

$$\mathbf{0} = \mathbf{a} + \mathbf{b} \cdot \mathbf{x}$$

¿Existen algoritmos eficientes para resolver un sistema de ecuaciones cuadráticas de la forma

$$\forall i \qquad 0 = a^i + \sum_j b^i_j x^j + \sum_k \sum_j c^i_{jk} x^j x^k$$

o

$$\mathbf{0} = \mathbf{a} + \mathbf{b} \cdot \mathbf{x} + \mathbf{c} \cdot \mathbf{x} \cdot \mathbf{x}$$

y si es así, ¿cuáles son?

Answer 1

Como muestra Robert Israel 's respuesta a una pregunta similar En los casos particulares de este esquema de problemas no es necesario que las soluciones se expresen de forma sencilla (a diferencia del caso lineal, en el que la solución es siempre expresable como expresiones finitas en los coeficientes dados, en los casos cuadráticos y de mayor grado, la solución puede necesitar raíces de polinomios de alto grado, para los que no es necesario que haya ninguna expresión en los coeficientes originales). Así que lo mejor que podemos esperar es un método similar a la eliminación que cambie menos variables por grados más altos. Base de Groebner cálculos son un método de este tipo.

Se podría desear que el límite de grado 2 en las entradas permitiera una solución más agradable, pero no Un algoritmo de solución acotada de grado 2 es en realidad un algoritmo para un sistema con grados no acotados.

Hay varios Implementación de la base de Groebner . No recomiendo que se intente esta técnica a mano, excepto para ejercicios cuidadosamente construidos (para los cuales, ver libros, como Cox, Little y O'Shea, Ideales, Variedades y Algoritmos: Una introducción a la geometría algebraica computacional y al álgebra conmutativa ).