Hispanopedia Wiki
Articulo de referencia

Método de Wu para el conjunto de características

El método de Wenjun Wu es un algoritmo para resolver ecuaciones polinómicas multivariables introducido a finales de la década de 1970 por el matemático chino Wen-Tsun Wu . Este ...

Hispanopedia WikiContenido en espanolLectura gratuita

El método de Wenjun Wu es un algoritmo para resolver ecuaciones polinómicas multivariables introducido a finales de la década de 1970 por el matemático chino Wen-Tsun Wu . Este método se basa en el concepto matemático de conjunto característico , introducido a finales de la década de 1940 por JF Ritt . Es totalmente independiente del método de bases de Gröbner , introducido por Bruno Buchberger (1965), aunque las bases de Gröbner pueden utilizarse para calcular conjuntos característicos. [ 1 ] [ 2 ]

El método de Wu es potente para la demostración mecánica de teoremas en geometría elemental y proporciona un proceso de decisión completo para ciertas clases de problemas. Se ha utilizado en investigaciones en su laboratorio (KLMM, Laboratorio Clave de Mecanización Matemática de la Academia China de Ciencias) y en todo el mundo. Las principales líneas de investigación sobre el método de Wu se centran en sistemas de ecuaciones polinómicas de dimensión positiva y álgebra diferencial , donde los resultados de Ritt se han hecho efectivos. [ 3 ] [ 4 ] El método de Wu se ha aplicado en diversos campos científicos, como la biología, la visión por computadora , la cinemática robótica y, especialmente , las demostraciones automáticas en geometría. [ 5 ]

Descripción informal

El método de Wu utiliza la división de polinomios para resolver problemas de la forma:

∀incógnita,y,z,…I(incógnita,y,z,…)⟹F(incógnita,y,z,…){\displaystyle \forall x,y,z,\dots I(x,y,z,\dots )\implies f(x,y,z,\dots )\,}

donde f es una ecuación polinómica e I es una conjunción de ecuaciones polinómicas . El algoritmo es completo para tales problemas en el dominio complejo .

La idea central del algoritmo es que se puede dividir un polinomio entre otro para obtener un resto. La división repetida da como resultado que el resto desaparezca (en cuyo caso la afirmación "i implica f" es verdadera) o que quede un resto irreducible (en cuyo caso la afirmación es falsa).

Más específicamente, para un ideal I en el anillo k [ x 1 ,  ..., x n ] sobre un cuerpo k , un conjunto característico (Ritt) C de I está compuesto por un conjunto de polinomios en I , que tiene forma triangular: los polinomios en C tienen variables principales distintas (véase la definición formal más adelante). Dado un conjunto característico C de I , se puede decidir si un polinomio f es cero módulo I . Es decir, la prueba de pertenencia es verificable para I , siempre que se disponga de un conjunto característico de I . 

Conjunto de características de Ritt

Un conjunto característico de Ritt es un conjunto finito de polinomios en forma triangular que representan un ideal. Este conjunto triangular satisface una condición mínima respecto al orden de Ritt y conserva muchas propiedades geométricas interesantes del ideal. Sin embargo, puede que no sea su sistema de generadores.

Notación

Sea R el anillo de polinomios multivariados k [ x 1 , ..., x n ] sobre un cuerpo k . Las variables están ordenadas linealmente según su subíndice: x 1 < ... < x n . Para un polinomio no constante p en R, la variable de mayor magnitud presente en p , llamada variable principal o clase , desempeña un papel particular: p puede considerarse naturalmente como un polinomio univariado en su variable principal x k con coeficientes en k [ x 1 , ..., x k −1 ]. El grado de p como polinomio univariado en su variable principal también se denomina grado principal.

Conjunto triangular

Un conjunto T de polinomios no constantes se denomina conjunto triangular si todos los polinomios de T tienen variables principales distintas. Esto generaliza de forma natural los sistemas triangulares de ecuaciones lineales .

Orden de Ritt

Para dos polinomios no constantes p y q , decimos que p es menor que q con respecto al orden de Ritt y se escribe como p  < r q , si se cumple alguna de las siguientes afirmaciones: 

(1) la variable principal de p es menor que la variable principal de q , es decir, mvar( p )  <  mvar( q ),
(2) p y q tienen la misma variable principal, y el grado principal de p es menor que el grado principal de q , es decir, mvar( p ) = mvar( q ) y mdeg( p ) < mdeg( q ).     

De esta forma, ( k [ x 1 ,  ..., x n ],< r ) forma un orden parcial adecuado . Sin embargo, el orden de Ritt no es un orden total : existen polinomios p y q tales que ni p < r q ni p > r q . En este caso, decimos que p y q no son comparables. El orden de Ritt consiste en comparar el rango de p y q . El rango, denotado por rank( p ), de un polinomio no constante p se define como una potencia de su variable principal: mvar( p ) mdeg( p ) y los rangos se comparan comparando primero las variables y luego, en caso de igualdad de las variables, los grados.     

Ordenación de Ritt en conjuntos triangulares

Una generalización crucial del ordenamiento de Ritt consiste en comparar conjuntos triangulares. Sean T  =  { t 1 , ..., t u } y S = { s 1 , ..., s v } dos conjuntos triangulares tales que los polinomios en T y S están ordenados de forma creciente según sus variables principales. Decimos que T es menor que S con respecto al ordenamiento de Ritt si se cumple alguna de las siguientes afirmaciones.        

  1. existe k  ≤  min( u , v ) tal que rango( t i ) = rango( s i ) para 1 ≤ i < k y t k < r s k ,         
  2. u  > v y rango( t i ) = rango( s i ) para 1 ≤ i ≤ v .       

Además, existen conjuntos triangulares incomparables con respecto al orden de Ritt.

Conjunto de características de Ritt

Sea I un ideal no nulo de k[x 1 , ..., x n ]. Un subconjunto T de I es un conjunto característico de Ritt de I si se cumple alguna de las siguientes condiciones:

  1. T consta de una única constante no nula de k,
  2. T es un conjunto triangular y T es mínimo con respecto al orden de Ritt en el conjunto de todos los conjuntos triangulares contenidos en I.

Un ideal polinomial puede poseer (infinitos) conjuntos característicos, ya que el orden de Ritt es un orden parcial.

Conjunto de características de Wu

El proceso de Ritt-Wu, ideado inicialmente por Ritt y posteriormente modificado por Wu, no calcula una característica de Ritt, sino una extendida, denominada conjunto de características de Wu o cadena ascendente.

Un subconjunto no vacío T del ideal ⟨ F ⟩ generado por F es un conjunto característico de Wu de F si se cumple alguna de las siguientes condiciones.

  1. T = {a} donde a es una constante distinta de cero,
  2. T es un conjunto triangular y existe un subconjunto G de ⟨ F ⟩ tal que ⟨ F ⟩ = ⟨ G ⟩ y todo polinomio en G se pseudoreduce a cero con respecto a T.

El conjunto característico de Wu se define como el conjunto F de polinomios, en lugar del ideal ⟨ F ⟩ generado por F. También se puede demostrar que un conjunto característico de Ritt T de ⟨ F ⟩ es un conjunto característico de Wu de F. Los conjuntos característicos de Wu se pueden calcular mediante el algoritmo CHRST-REM de Wu, que solo requiere cálculos de pseudoresto y no necesita factorizaciones.

El método de conjunto característico de Wu tiene una complejidad exponencial; se introdujeron mejoras en la eficiencia computacional mediante cadenas débiles, cadenas regulares y cadenas saturadas [ 6 ].

Descomposición de variedades algebraicas

Una aplicación es un algoritmo para resolver sistemas de ecuaciones algebraicas mediante conjuntos característicos. Más precisamente, dado un subconjunto finito F de polinomios, existe un algoritmo para calcular conjuntos característicos T 1 , ..., T e tales que:

V(F)=W(T1)∪⋯∪W(Tmi),{\displaystyle V(F)=W(T_{1})\cup \cdots \cup W(T_{e}),}

donde W ( T i ) es la diferencia de V ( T i ) y V ( h i ), aquí h i es el producto de las iniciales de los polinomios en T i .

Véase también

Referencias

  1. ↑ Corrochano, Eduardo Bayro; Sobczyk, Garret, eds. (2001). Álgebra geométrica con aplicaciones en ciencia e ingeniería . Boston, Mass: Birkhäuser. p.  110. ISBN 9780817641993.
  2. ↑ P. Aubry, D. Lazard , M. Moreno Maza (1999). Sobre las teorías de conjuntos triangulares . Journal of Symbolic Computation, 28(1–2):105–124
  3. ↑ Hubert, E. Algoritmos de descomposición sin factorización en álgebra diferencial . Journal of Symbolic Computation, (mayo de 2000): 641–662.
  4. ↑ Paquete de software Maple difflag .
  5. ↑ Chou, Shang-Ching; Gao, Xiao Shan; Zhang, Jing Zhong. Demostraciones mecánicas en geometría . World Scientific, 1994.
  6. ↑ Chou SC, Gao XS; Algoritmo de descomposición de Ritt-Wu y demostración de teoremas geométricos. Actas de CADE, 10 LNCS, n.º 449, Berlín, Springer Verlag, 1990, 207-220.
  • P. Aubry, M. Moreno Maza (1999) Conjuntos triangulares para la resolución de sistemas polinomiales: una implementación comparativa de cuatro métodos . J. Symb. Comput. 28(1–2): 125–154
  • David A. Cox , John B. Little , Donal O'Shea . Ideales, variedades y algoritmos. 2007.
  • Hua-Shan, Liu (24 de agosto de 2005). "WuRittSolva: Implementación del método del conjunto de características de Wu-Ritt" . Archivo de la biblioteca Wolfram . Wolfram . Recuperado el 17 de noviembre de 2012 .
  • Heck, André (2003). Introducción a Maple (3.ª  ed.). Nueva York: Springer. pp. 105 , 508. ISBN  9780387002309.
  • Ritt, J. (1966). Álgebra diferencial. Nueva York, Dover Publications.
  • Dong Ming Wang (1998). Métodos de eliminación. Springer-Verlag, Viena, Springer-Verlag
  • Dongming Wang (2004). Práctica de eliminación, Imperial College Press, Londres ISBN 1-86094-438-8
  • Wu, WT (1984). Principios básicos de la demostración mecánica de teoremas en geometrías elementales . J. Syst. Sci. Math. Sci., 4, 207–35
  • Wu, WT (1987). Un teorema de estructura cero para la resolución de ecuaciones polinómicas. MM Research Preprints, 1, 2–12
  • Xiaoshan, Gao; Chunming, Yuan; Guilin, Zhang (2009). "Método del conjunto característico de Ritt-Wu para sistemas polinomiales de diferencias ordinarias con ordenación arbitraria". Acta Mathematica Scientia . 29 (4): 1063– 1080. CiteSeerX 10.1.1.556.9549 . doi : 10.1016/S0252-9602(09)60086-2 . 
  • Paquete de Maple wsolve
  • El método del conjunto característico