MetNum-2S: Convergencia de un MIG

Buenas, para asegurar la convergencia de un MIG es necesario que la norma de g' sea menor a 1 en un entorno de x*, pero si tengo g' mayor o igual a 1 se asegura la no convergencia del método?

Gracias!

Re: Convergencia de un MIG

de Juan Pablo Borthagaray - lunes, 4 de diciembre de 2023, 09:06

Hola Leandro,

Creo que tu pregunta se solapa un poco con esta otra:
https://eva.fing.edu.uy/mod/forum/discuss.php?d=278966

En concreto, si

$|g'(x^*)| > 1$ y

$g'$ es continua en un entorno de

$x^*$ , entonces

$|g'(x)|>1$ para todo

$x$ en algún entorno de

$x^*$ y la iteración no va a converger. Probá pensar un ejemplo en el que

$|g'(x^*)| = 1$ y la iteración sea convergente, y otro en el que no lo sea. Lo lindo de este curso es que después de pensar los ejemplos, los podés implementar y experimentar.

Re: Convergencia de un MIG

de Nicolas Grosso San Roman - jueves, 7 de diciembre de 2023, 10:59

Hola, entonces se podría decir que un MIG converge si y solo si |g'(x*)|<1? Porque como dijo Leandro, en las notas solo está la implicancia hacia un lado.

Re: Convergencia de un MIG

de Juan Pablo Borthagaray - jueves, 7 de diciembre de 2023, 11:45

Hola Nicolás,

No, no es un si y sólo si. Podés tener convergencia incluso si

$|g'(x^*) = 1|$ , pero si

$|g'(x^*) = 1|$ no podés garantizar la convergencia.

Un par de ejemplos sencillos es aproximar la raíz

$x^*=0$ para las iteraciones

$g(x) = x - x^3$ y

$g(x) = x + x^3$ . En ambos casos tenés

$g'(x^*) = 1$ , pero en uno la derivada es menor a 1 en un entorno de

$x^*$ y en el otro es mayor. Probá (implementando) qué pasa con esas iteraciones si las inicializás cerca de

$x^*=0$ . Creo que eso puede ayudar a entender un poco mejor.

Re: Convergencia de un MIG

de Nicolas Grosso San Roman - jueves, 7 de diciembre de 2023, 13:57

Gracias. Entiendo que cuando es igual a 1 no se puede asegurar nada, pero en el mensaje anterior pusiste que si |g'(x*)|>1 entonces no converge, eso si se cumple?

Re: Convergencia de un MIG

de Juan Manuel Rivara De Leon - viernes, 8 de diciembre de 2023, 03:15

Hola, a lo mejor ayuda ponerlo de esta manera:

$g'(x)$ es continua y

$|g'(x^*)| < 1$ , por continuidad va a haber un entorno de

$x^*$ en donde

$|g'(x)| < 1$ . En este caso la función

$g$ es contractiva en ese entorno, y por lo tanto para los

$x$ en ese entorno se tiene

$|x^* - x| > |g(x^*) - g(x)| = |x^* - g(x)|$ . Es decir las sucesivas aplicaciones de

$g$ acercan los puntos del entorno al punto fijo. Por eso converge el MIG.

$g'(x)$ es continua y

$|g'(x^*)| > 1$ , por continuidad va a haber un entorno de

$x^*$ en donde

$|g'(x)| > 1$ . En este caso la función

$g$ es expansiva en ese entorno, y por lo tanto para los

$x$ en ese entorno se tiene

$|x^* - x| < |g(x^*) - g(x)| = |x^* - g(x)|$ . Es decir las sucesivas aplicaciones de

$g$ alejan los puntos del entorno del punto fijo. Por ese diverge el MIG.

$|g'(x^*)| = 1$ , entonces hay que ver bien el entorno para ver si en el entorno del punto fijo la función

$g$ es contractiva o expansiva (por ejemplo, si es

$g$ es suficientemente suave podés tomar las siguientes derivadas para analizar el comportamiento en el entorno, considerando que quisieras que la derivada primera tendiera a decrecer en su entorno).
Por las dudas, para ser más exhaustivo: si

$|g'(x)| = 1$ en todo un entorno de

$x^*$ entonces

$g$ es casi seguramente igual a la función identidad en ese entorno, y por lo tanto las sucesivas iteraciones no mueven el punto de iteración, es decir no converge.

Saludos.

Re: Convergencia de un MIG

de Juan Manuel Rivara De Leon - viernes, 8 de diciembre de 2023, 03:48

Aclaración/corrección: si

$|g'(x^*)| = 1$ , entonces quisieras que el valor absoluto de la derivada primera tendiera a decrecer en su entorno.

Re: Convergencia de un MIG

de Nicolas Grosso San Roman - viernes, 8 de diciembre de 2023, 09:00

Se entendió perfecto. Muchas gracias!!

Re: Convergencia de un MIG

de Juan Pablo Borthagaray - viernes, 8 de diciembre de 2023, 09:25

Hola,

A lo que dice Juan Manuel (que comparto) agrego un comentario. Si mirás la demostración del Teorema 4.7.4 de las notas, la cuenta que se hace (para el recíproco y poniendo

$i=0$ ) funciona independientemente de si

$|g'(x^*)|$ es mayor o menor que

$1$ . Lo que pasa es que si es mayor a

$1$ , te termina quedando que si

$x^k$ estuviera cerca de

$x^*$ , entonces el cociente

$|e^{k+1}|/|e^k|$ sería mayor a

$1$ , lo que implica que los iterados se estarían alejando de

$x^*$ .

Aprovecho también a aclarar por qué no ponemos un resultado de no-convergencia. Por más que

$|g'(x^*)| > 1$ , si justo te pasa que

$g(x^k) = x^*$ entonces vas a tener convergencia: te queda

$x^j = x^*$ para todo

$j > k$ . Puede pasar que

$x^k$ esté lejos de

$x^*$ y que pase eso.

Como estamos trabajando con lápiz y papel, no tenemos problemas de representación de números ni para evaluar

$g$ . Ahora, esto es como dejar parado un huevo: puede pasar, pero en la práctica cualquier perturbación te lo va a hacer caer. Al trabajar con punto flotante, lo esperable (salvo que

$x^*$ sea representable exactamente) es que tengas algún errorcito de representación al escribir

$g(x^k) = x^*$ . Si

$|g'(x^*)| > 1$ , entonces el argumento de Juan Manuel aplica y lo que vas a observar es que

$x^{k+1}$ se aleja de

$x^*$ .

Por eso decimos que si

$|g'(x^*)| > 1$ es "esperable" que el MIG no converja (y en la práctica no va a converger salvo algún caso patológico), pero no podemos asegurar (escribir en forma de teorema) la no-convergencia.