Autor Tema: Sucesión convergente

0 Usuarios y 1 Visitante están viendo este tema.

21 Diciembre, 2024, 09:16 pm
Leído 1728 veces

Daxito

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 23
  • País: es
  • Karma: +0/-0
Buenas, tengo un problema con el último apartado del siguiente ejercicio:

Sean \( \mathbf{A} \) una matriz de dimensión \( m \times n \), con \( m > n \) y rango \( n \), y \( \mathbf{b} \in \mathbb{R}^m \). Se define la función \( f : \mathbb{R}^n \to \mathbb{R} \) mediante 
\[
f(\mathbf{x}) = \| \mathbf{A}\mathbf{x} - \mathbf{b} \|_2^2.
\]

Dado \( \alpha = \frac{1}{2 \|\mathbf{A}^t \mathbf{A}\|_2} \), donde \( \mathbf{A}^t \) denota la traspuesta de \( \mathbf{A} \) y \( \|\cdot\|_2 \) la norma matricial asociada a la norma euclidiana, se define iterativamente la sucesión \( (\mathbf{x}_m)_{m=0}^\infty \) mediante 
\[
\mathbf{x}_{m+1} = \mathbf{x}_m - \alpha \nabla f(\mathbf{x}_m),
\] 
asegurándonos de que \( \|\mathbf{A}^t \mathbf{A}\|_2 \neq 0 \).

Usando el desarrollo de Taylor de orden 2 de \( f \) en el punto \( \mathbf{x}_m \), demostrar que:

    1. \( f(\mathbf{x}_{m+1}) - f(\mathbf{x}_m) \leq -\frac{\alpha}{2} \|\nabla f(\mathbf{x}_m)\|_2^2 \) para cada \( m \).
    2. La sucesión \( (f(\mathbf{x}_m))_{m=0}^\infty \) es convergente.
    3. Concluir que \( \mathbf{x}_m \to \mathbf{u} \) cuando \( m \to \infty \), siendo \( \mathbf{u} \) el mínimo absoluto de \( f \).

El problema lo tengo en el apartado 3 porque, usando 1 y 2 soy capaz de demostrar que el gradiente tiende a 0 cuando n tiende al infinito, y por tanto, por la definición de \( \mathbf{x}_m \) tenemos que esto implica que \( \mathbf{x}_m \) - \( \mathbf{x}_{m+1} \) tiende a 0 cuando n tiende a infinito, pero la verdad que desde aquí no se como demostrar que tiene la sucesión converge.

Se me había ocurrido tratar de demostrar que es de Cauchy, pero véase que la serie armónica cumple las hipótesis pero no converge (diverge a infinito). 

Saludos


22 Diciembre, 2024, 03:53 pm
Respuesta #1

Masacroso

  • “Lo que oigo, lo olvido; lo que veo, lo recuerdo; lo que hago, lo aprendo” (antiguo proverbio chino)
  • Moderador Global
  • Mensajes: 5,485
  • País: es
  • Karma: +0/-0
No he he encontrado manera de probar ninguno de los puntos del supuesto ejercicio, ¿seguro has copiado bien el ejercicio? En cualquier caso, ¿podrías al menos poner la resolución de la desigualdad \( f(x_{m+1})-f(x_m)\leqslant -\frac{\alpha }{2}\|\nabla f(x_m)\|_2^2 \)? Usando el teorema de Taylor a mí me queda una expresión que no me deja nada en clara tal desigualdad:

\( \displaystyle{
\begin{align*}
f(x_{m+1})-f(x_m)=&-\alpha \|\nabla f(x_m)\|_2^2+\alpha ^2\|A\nabla f(x_m)\|_2^2\\
& +\alpha ^2\int_{0}^1(1-t)[\nabla ^2 f(x_m-\alpha t\nabla f(x_m))-\nabla^2 f(x_m)][\nabla f(x_m),\nabla f(x_m)]\,d t
\end{align*}
} \)

No sé si manipulando el integrando de la última expresión se pueda llegar a lo que te piden.

23 Diciembre, 2024, 04:38 pm
Respuesta #2

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

No he he encontrado manera de probar ninguno de los puntos del supuesto ejercicio, ¿seguro has copiado bien el ejercicio? En cualquier caso, ¿podrías al menos poner la resolución de la desigualdad \( f(x_{m+1})-f(x_m)\leqslant -\frac{\alpha }{2}\|\nabla f(x_m)\|_2^2 \)? Usando el teorema de Taylor a mí me queda una expresión que no me deja nada en clara tal desigualdad:

\( \displaystyle{
\begin{align*}
f(x_{m+1})-f(x_m)=&-\alpha \|\nabla f(x_m)\|_2^2+\alpha ^2\|A\nabla f(x_m)\|_2^2\\
&\color{red} +\alpha ^2\int_{0}^1(1-t)[\nabla ^2 f(x_m-\alpha t\nabla f(x_m))-\nabla^2 f(x_m)][\nabla f(x_m),\nabla f(x_m)]\,d t \color{black}
\end{align*}
} \)

No sé si manipulando el integrando de la última expresión se pueda llegar a lo que te piden.

Pero \( f(x) \) ya es un polinomio de grado dos en \( n \) variables; no hay resto de Taylor si usas la expansión de grado dos. Así que la parte en rojo es cero.

Saludos.

AÑADIDO. Después dado que:

\( \|A\nabla f(x_m)\|_2^2\leq \|A\|_2^2\|\nabla f(x_m)\|_2^2=\|A^tA\|_2\|\nabla f(x_m)\|_2^2=\dfrac{1}{2\alpha}\|\nabla f(x_m)\|_2^2 \)

se obtiene la desigualdad indicada.

23 Diciembre, 2024, 05:33 pm
Respuesta #3

Daxito

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 23
  • País: es
  • Karma: +0/-0
Claro, aquí tienes mi desarrollo de los dos primeros apartados:

Sea \( \alpha = \frac{1}{2 \|A^t A\|_2} \), fijamos \( x_0 \in \mathbb{R}^n \). Definimos \( x_{n+1} = x_n - \alpha \nabla g(x_n) = x_n - \frac{1}{2 \|A^t A\|_2} \nabla g(x_n) \).

Sea el desarrollo de Taylor de orden dos de \( g \) en \( x_n \):

\[ g(x) = g(x_n) + \nabla g(x_n)^t (x - x_n) + \frac{1}{2} (x - x_n)^t \nabla^2 g(x_n) (x - x_n) + \Theta(\|x - x_n\|^3) \]

Ya que \( g \) es una función cuadrática (no tiene términos de orden mayor a dos)

\( g(x_{n+1}) = g(x_n) + \nabla g(x_n)^t (x_{n+1} - x_n) + \frac{1}{2} (x_{n+1} - x_n)^t \nabla^2 g(x_n) (x_{n+1} - x_n). \)

Sustituyendo \( x_{n+1} = x_n - \alpha \nabla g(x_n) \):

\( g(x_{n+1}) = g(x_n) + \nabla g(x_n)^t (-\alpha \nabla g(x_n)) + \frac{1}{2} (-\alpha \nabla g(x_n))^t \nabla^2 g(x_n) (-\alpha \nabla g(x_n)). \)

\[ g(x_{n+1}) = g(x_n) - \alpha \|\nabla g(x_n)\|_2^2 + \frac{\alpha^2}{2} \nabla g(x_n)^t \nabla^2 g(x_n) \nabla g(x_n). \]

\[ g(x_{n+1}) = g(x_n) - \alpha \|\nabla g(x_n)\|_2^2 + \frac{\alpha^2}{2} \|\nabla g(x_n)\|_2^2. \]

Veamos ahora si la siguiente desigualdad es cierta:

\[ g(x_{n+1}) - g(x_n) = -\alpha \|\nabla g(x_n)\|_2^2 + \frac{\alpha^2}{2} \|\nabla g(x_n)\|_2^2 \leq -\frac{\alpha}{2} \|\nabla g(x_n)\|_2^2 \Leftrightarrow \]

\[ \Leftrightarrow 2 \|\nabla g(x_n)\|_2^2 -\alpha \nabla g(x_n)^t \nabla^2 g(x_n) \nabla g(x_n) \leq \|\nabla g(x_n)\|_2^2 \Leftrightarrow \]

\[ \Leftrightarrow \|\nabla g(x_n)\|_2^2 \leq \alpha \nabla g(x_n)^t \nabla^2 g(x_n) \nabla g(x_n) \]

Sea \( c \) el término de la izquierda y \( d \) el de la derecha

\[ c = \|2A^t (Ax - b)\|_2^2 = (2A^t (Ax - b))^t (2A^t (Ax - b)) = 4(Ax - b)^t A^t A (Ax - b), \]

\[ \alpha d = \alpha (2A^t (Ax - b))^t (2A^tA)^2 (2A^t (Ax - b)) = \alpha 16(Ax - b)^t A^t A A^t A(Ax - b) \]
\[ \quad\;\, \leq \alpha 16 \|A^t A\|_2 (Ax - b)^t A^t A (Ax - b) \]

Dividiendo ambos lados por \( 4(Ax - b)^t A^t A (Ax - b) \), se concluye que:

\[ 1 < \alpha \cdot 4 \|A^t A\|_2 \Leftrightarrow 1 < \alpha \frac{1}{2 \|A^t A\|_2} = 2 \]

Para el apartado dos:

Como la sucesión \( g(x_n) \) es estrictamente decreciente y acotada inferiormente por \( g(u) \) (al ser \( g(u) \) mínimo absoluto), esto asegura que \( g(x_n) \) converge a un valor \( L \) con \( L \geq g(u) \). La última desigualdad de \( \alpha d \) se cumple porque \( AA^t \) es simétrica y definida positiva y por tanto \( v^tAA^tv = \|A^t A\|_2 \|v\|_2 \).

Mensaje de la moderación: se ha corregido el \( \LaTeX \) para que las frases tengan ancho adaptable y sean fáciles de leer desde cualquier dispositivo. En la medida de lo posible evita el uso del entorno \text{... }, especialmente para escribir frases.

23 Diciembre, 2024, 08:06 pm
Respuesta #4

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

\[
\text{La última desigualdad de } \alpha \text{d se cumple porque }AA^t \text{es simétrica y definida positiva y por tanto} v^tAA^tv = \|A^t A\|_2 \|v\|_2
\]

Esto no es cierto. Por ejemplo si \( AA^t=\begin{pmatrix}1&0\\0&2\\\end{pmatrix} \) se tiene que \( \|AA^t\|_2=2 \). Si tomas \( v=(1,0) \) se tiene que:

\( v^tA^tAv=1\neq \|A^tA\|_2\|(1,0)\|_2=2 \)

Lo que se cumple es que:

\( v^tA^tAv=\|Av\|_2^2\leq \|A\|_2^2\|v\|_2^2=\|A^tA\|_2\|v\|_2^2 \)

El problema lo tengo en el apartado 3 porque, usando 1 y 2 soy capaz de demostrar que el gradiente tiende a 0 cuando n tiende al infinito, y por tanto, por la definición de \( \mathbf{x}_m \) tenemos que esto implica que \( \mathbf{x}_m \) - \( \mathbf{x}_{m+1} \) tiende a 0 cuando n tiende a infinito, pero la verdad que desde aquí no se como demostrar que tiene la sucesión converge.

El gradiente explícitamente es:

\( \nabla f(x_m)=2A^tAx_m-2A^tb \)

Si pruebas que converge a cero tienes que:

\( A^tAx_m\to A^tb \)

y dado que \( A^tA \) es inversible:

\( x_m\to (A^tA)^{-1}A^tb \)

Saludos.

24 Diciembre, 2024, 01:02 am
Respuesta #5

Masacroso

  • “Lo que oigo, lo olvido; lo que veo, lo recuerdo; lo que hago, lo aprendo” (antiguo proverbio chino)
  • Moderador Global
  • Mensajes: 5,485
  • País: es
  • Karma: +0/-0
Pero \( f(x) \) ya es un polinomio de grado dos en \( n \) variables; no hay resto de Taylor si usas la expansión de grado dos. Así que la parte en rojo es cero.

¡Ostras! No me había dado cuenta que era un polinomio 🤦🏻‍♂️.

24 Diciembre, 2024, 05:21 pm
Respuesta #6

Daxito

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 23
  • País: es
  • Karma: +0/-0
Hola

\[
\text{La última desigualdad de } \alpha \text{d se cumple porque }AA^t \text{es simétrica y definida positiva y por tanto} v^tAA^tv = \|A^t A\|_2 \|v\|_2
\]

Esto no es cierto. Por ejemplo si \( AA^t=\begin{pmatrix}1&0\\0&2\\\end{pmatrix} \) se tiene que \( \|AA^t\|_2=2 \). Si tomas \( v=(1,0) \) se tiene que:

\( v^tA^tAv=1\neq \|A^tA\|_2\|(1,0)\|_2=2 \)

Lo que se cumple es que:

\( v^tA^tAv=\|Av\|_2^2\leq \|A\|_2^2\|v\|_2^2=\|A^tA\|_2\|v\|_2^2 \)

El problema lo tengo en el apartado 3 porque, usando 1 y 2 soy capaz de demostrar que el gradiente tiende a 0 cuando n tiende al infinito, y por tanto, por la definición de \( \mathbf{x}_m \) tenemos que esto implica que \( \mathbf{x}_m \) - \( \mathbf{x}_{m+1} \) tiende a 0 cuando n tiende a infinito, pero la verdad que desde aquí no se como demostrar que tiene la sucesión converge.

El gradiente explícitamente es:

\( \nabla f(x_m)=2A^tAx_m-2A^tb \)

Si pruebas que converge a cero tienes que:

\( A^tAx_m\to A^tb \)

y dado que \( A^tA \) es inversible:

\( x_m\to (A^tA)^{-1}A^tb \)

Saludos.

Es cierto, era una desigualdad.

Acerca de cómo demostrar que xm tiende a u.
¿Valdría con razonar que, como \(u\) es el único punto crítico de la función, si se tiene que
\(\lim \nabla f(x_m) = 0 = \nabla(f(\lim x_m))\), entonces \(u = \lim x_m\)?

25 Diciembre, 2024, 02:29 am
Respuesta #7

Masacroso

  • “Lo que oigo, lo olvido; lo que veo, lo recuerdo; lo que hago, lo aprendo” (antiguo proverbio chino)
  • Moderador Global
  • Mensajes: 5,485
  • País: es
  • Karma: +0/-0
Es cierto, era una desigualdad.

Acerca de cómo demostrar que \(x_m\) tiende a \(u\).
¿Valdría con razonar que, como \(u\) es el único punto crítico de la función, si se tiene que
\(\lim \nabla f(x_m) = 0 = \nabla(f(\lim x_m))\), entonces \(u = \lim x_m\)?

Algo mejor expresado sería así: al ser \( \nabla f \) una función continua entonces \( 0=\lim_{n\to \infty }\nabla f(x_n)=\nabla f(\lim_{n\to \infty }x_n)=\nabla f(u) \), luego \( u \) es un punto crítico de \( f \).

Añadido: me faltó añadir que, para que lo anterior tenga algún sentido, previamente debemos saber que la sucesión \( \{x_n\}_{n\in\mathbb{N}} \) converge a \( u \).

25 Diciembre, 2024, 10:21 pm
Respuesta #8

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 58,907
  • País: es
  • Karma: +0/-0
Hola

Acerca de cómo demostrar que xm tiende a u.
¿Valdría con razonar que, como \(u\) es el único punto crítico de la función, si se tiene que
\(\lim \nabla f(x_m) = 0 = \nabla(f(\lim x_m))\), entonces \(u = \lim x_m\)?

Esto o en todo caso mejor como lo ha redactado Masacroso:

Algo mejor expresado sería así: al ser \( \nabla f \) una función continua entonces \( 0=\lim_{n\to \infty }\nabla f(x_n)=\nabla f(\lim_{n\to \infty }x_n)=\nabla f(u) \), luego \( u \) es un punto crítico de \( f \).

Sirve para probar que si \( x_m\to u \) entonces necesariaente \( \nabla f(u)=0 \) y por tanto \( u \) es punto crítico.

Pero eso funciona si PREVIAMENTE sabemos que \( x_m \) converge, es decir, no sirve para probar la convergencia de \( x_m \).

Para una función constante \( f(x) \), el gradiente sobre cualquier sucesión es trivialmente nulo independientemente de que ésta converja o no.

También en general, que la imagen de una sucesión por una función contina converja no quiere decir que la sucesión original converja.

Saludos.

26 Diciembre, 2024, 05:55 pm
Respuesta #9

Daxito

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 23
  • País: es
  • Karma: +0/-0
Pero no me queda claro, entonces, cómo partiendo de que \( x_m \) converge y de que el gradiente del límite \( \nabla (\lim f(x_m)) = 0 \), ¿cómo pruebo que \( x_m \) converge a \( u \)?

\[
\text{Es decir, yo trato de obtener que xm }\rightarrow{} \text{u, no que u es punto crítico. }
\]