¿Podemos realmente encontrar algún punto fijo con el teorema de Brouwer?

Question

Antecedentes

A riesgo de simplificar demasiado las cosas, permítanme exponer una heurística de la hermosa obra de Granas y Dugundji libro : Los teoremas de punto fijo se dividen en dos grandes categorías . La primera clase suele ser funcionalmente analítica e impone fuertes condiciones a la mapa $f:X \to X$ mientras que la segunda clase suele ser topológica algebraica e impone fuertes condiciones a la espacio $X$ sí mismo.

Un ejemplo típico de la primera clase de teoremas es el teorema del punto fijo de Banach . Aunque los espacios a los que se aplica son bastante generales (espacios métricos completos), la función debe tener una constante de Lipschitz estrictamente menor que $1$ . Por otro lado, Teorema de Brouwer pertenece a la segunda clase. Cualquier mapa continuo sirve, pero el dominio debe ser un subconjunto compacto y convexo del espacio euclidiano (originalmente un disco). Por supuesto, ambos teoremas han sido ampliamente generalizada de las versiones que expongo aquí.

Pregunta

Una ventaja fundamental del teorema de Banach es que realmente proporciona una receta para converger al punto fijo como parte de la prueba estándar: basta con empezar en un punto inicial e iterar. Las pruebas del teorema de Brouwer que he visto no hacen tal cosa. La prueba más conocida (creo) es la de la contradicción: suponiendo que el dominio es un disco, si $f(x)$ y $x$ son siempre distintos, entonces el rayo de $f(x)$ a través de $x$ a la frontera de dicho disco proporciona una deformación-retracción del disco a su frontera, ¡ajá!

Esta es mi pregunta:

¿Hay alguna forma de encontrar realmente un punto fijo cuando se utiliza el teorema de Brouwer?

Una idea posible

Un esquema que lamentablemente falla es el siguiente. Consideremos la secuencia de iterados $f^n(x)$ para $n \in \mathbb{N}$ y cualquier $x$ en el dominio. Tenemos una secuencia infinita en un conjunto compacto, y por tanto una subsecuencia convergente, por lo que el punto límite es un candidato. Esto no funcionará ya que a ) no hemos utilizado la convexidad en absoluto, y b ) uno puede simplemente converger a una órbita periódica de $f$ .

Answer 1

Existe una versión constructiva del teorema de Brouwer a través del teorema de Sperner. Esto da una forma real de calcular los puntos fijos. (No es muy eficiente, pero es un algoritmo)

Answer 2

El artículo "Exponential lower bounds for finding Brouwer fixed points"

Adenda del cartel original: No fue fácil encontrar una copia de este gran artículo de Hirsch, Papadimitriou y Vavasis. Responde a mi pregunta general con bastante claridad: encontrar puntos fijos de Brouwer es exponencialmente difícil en el peor de los casos, independientemente del algoritmo que se utilice. Aquí es un enlace a este artículo para todos aquellos que estén interesados y no quieran toparse con muchos, muchos muros de pago. Lo quitaré en unos días. -VN

Answer 3

Tal vez sea una tontería, pero el algoritmo obvio para $\mathbb R^1$ es calcular $f(1/2)$ . Si es mayor que $1/2$ , computa $f(3/4)$ . Si es menor, calcula $f(1/4)$ . Siga díada y calculará los dígitos binarios de un punto fijo con un nivel de precisión arbitrario. Pero no está muy claro cómo generalizar esto.

Si todo lo que podemos hacer es muestrear la función en un número finito de puntos, debería ser imposible adivinar la ubicación de un punto fijo con algún grado de precisión. Para ver esto, tomemos una función con un único punto fijo, como $f(x)=.99x$ . Toma un tubo largo pero muy delgado que contenga ese punto y otro punto, y cambia la función en el tubo para que el otro punto sea ahora el punto fijo.

Como la medida del tubo puede hacerse arbitrariamente pequeña, y el tubo puede elegirse para evitar cualquier conjunto finito, cualquier estrategia de muestreo de puntos finitos será, con alta probabilidad, incapaz de distinguir la función de $.99x$ y por lo tanto será incapaz de adivinar la ubicación del punto fijo.

Por lo tanto, se necesita alguna forma de demostrar que la función no es malévola, como alguna comprensión de la $\epsilon$ s y $\delta$ s en la continuidad uniforme de la función, o quizás un modelo probabilístico de una función aleatoria.

Answer 4

Hay otras pruebas constructivas Aquí es un artículo con un método que, según los autores, no requiere una descomposición simplicial, es similar al método de Newton y se ha aplicado hasta la dimensión $60$ .

Answer 5

(Esta respuesta va en una dirección similar a la de Johannes Hahn y a la de Will Sawin)

Creo (no estoy 100% seguro) que se puede prescindir de la triangulación y de la aproximación simplicial (de la prueba "habitual" del lema de Sperner) si se adopta el enfoque de la versión de van Maaren del lema de Sperner (hay un esquema de la prueba en el libro de Schechter Manual de análisis y sus fundamentos con algunas erratas).

Primero se obtiene la versión de van Maaren del lema de Sperner, que es puramente combinatoria/teórica del orden y es una afirmación constructiva sobre conjuntos finitos (la prueba sólo da el algoritmo).

Usando esto se obtiene una declaración aproximada del punto fijo (aproximadamente para cada $\epsilon$ se encuentra un punto que es $\epsilon$ de ser un punto fijo). Para obtener el punto fijo aproximado en el tamaño $1/k, k\in\mathbb{N}$ sólo hay que tener en cuenta el subconjunto finito formado por la red de espacios $1/(3kn)$ donde $n$ es la dimensión. En este paso entra en juego la convexidad (pero no la continuidad; la compacidad sólo entra a través de Heine-Borel como acotación).

Nótese que esto no requiere poder aproximar la función $f$ : sólo requiere ser capaz de evaluar $f(x)$ para un determinado $x$ con una precisión arbitraria (en particular, necesita saber si el $i$ -coordenada de $f(x)$ es menor o igual que el $i$ -coordenada de $x$ ).

Entonces se toma el límite como $k\to \infty$ (y aquí se utiliza la continuidad y la compacidad, ya que la convexidad ya no es relevante) (la practicidad de este último paso, por supuesto, es cuestionable; y como Noam Elkies y Michael Greinecker aludieron, este método no da ninguna tasa de convergencia, por lo que cortar el cómputo en una $k$ no garantiza en absoluto que estés cerca de un punto fijo de buena fe).