2 votos

Complejidad de la búsqueda del punto fijo

Supongamos que tengo un $n$ -espacio vectorial de dimensiones $V$ sobre un campo $F$ y tengo una secuencia de $n'$ -transformaciones lineales $G_i:V\rightarrow V$ , $i \leq n'$ . Supongamos además que sé que existe un subespacio (único) $V^*\subseteq V$ (de dimensión digamos $m$ ) tal que para todo $i \leq n'$ , $G_i|_{V^*}:V^* \rightarrow V^*$ es decir, cada $G_i$ mapea el subespacio $V^*$ a sí mismo.

¿Se conocen buenos algoritmos para encontrar $V^*$ y si es así cuál es el mejor algoritmo conocido (en cualquiera de los parámetros $n, n', m$ ) para encontrar tal $V^*$ ?

¿Y si ya no asumimos $F$ es un campo, sino que permite cualquier semirrecta.

Gracias.

2voto

minar Puntos 619

Genéricamente, esto debería ser fácil de hacer, especialmente sabiendo que $V^*$ es único de dimensión $m$ . Una herramienta útil para abordar este problema es el Forma normal de Jordania de una matriz (véase http://en.wikipedia.org/wiki/Jordan_normal_form ). El hecho relevante es que para cualquier transformación lineal $L$ cada bloque de Jordan en la descomposición de la forma normal de Jordan es invariante por $L$ y a la inversa, cada subespacio invariante de $L$ es una suma directa de bloques de Jordan.

De hecho, como sus transformaciones lineales están definidas sobre un campo arbitrario (no necesariamente cerrado algebraicamente), algunos valores propios pueden pertenecer a una extensión de campo base. Para evitar trabajar con campos de extensión, es necesario utilizar la forma de Jordan generalizada (está implementada en magma).

Como tienes varias transformaciones lineales $G_i$ con $V^*$ como subespacio invariante, cualquier combinación lineal de $G_i$ s también tiene $V^*$ como subespacio invariante. Yo propondría el siguiente algoritmo: Tomar $G$ una combinación lineal aleatoria de $G_i$ s y calcular su forma de Jordan generalizada. Con un poco de suerte, se obtiene un bloque de Jordan generalizado de dimensión $m$ (invariante bajo $G$ ) que es un buen candidato para $V^*$ y se puede comprobar fácilmente.

Caveat : No he programado el enfoque y probablemente es posible idear casos especiales en los que $V^*$ nunca aparecerá como un único bloque Jordan, lo que complicaría las cosas. Sin embargo, en general, esta parece ser una solución agradable y bastante eficiente para su problema.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X