TARDÍGRADOS

Ciencia en español -ʟᴀ ʀᴀᴢóɴ ᴇsᴛá ᴀʜí ғᴜᴇʀᴀ-

Posts Tagged ‘convergencia’

Mejorando el método de Newton-Raphson para el cálculo aproximado de raices (ceros) de una función

Posted by Albert Zotkin en enero 4, 2016

El otro día, mientras probaba el método de Newton-Raphson, se me ocurrió que quizás podría mejorarlo un poco. Este método se usa para el cálculo aproximado de las raíces de una función f(x), y es el siguiente:

\displaystyle x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} (1)
Donde f ‘(x) es la primera derivada de f(x). Es decir, partimos de un punto fijo xn, que suponemos está cerca de una de las raices, y desde él iteramos tantas veces como deseemos hasta aproximarnos más a dicha raíz. Este método tiene el riesgo de que las iteraciones no converjan hacia ninguna raíz, y por lo tanto resulte ineficaz para algunas funciones. Supongamos que queremos hallar alguna raíz de la función f(x) = 3x4 + x2 – 2 y aplicamos seis veces la iteracíon del método de Newton-Raphson partiendo del punto x0 = 1, y si calculamos con una precisión de 40 dígitos, tendremos:

\displaystyle \begin{matrix}   x_1 & = & x_0 - \frac{f(x_0)}{f'(x_0)} & = & 1 - \frac{2}{14} & = & \underline{0.8}571428571428571428571428571428571428571 \\   x_2 & = & x_1 - \frac{f(x_1)}{f'(x_1)} & & \vdots & = & \underline{0.81}89577717879604672057502246181491464510\\   x_3 & & \vdots & & \vdots & = & \underline{0.816}5061857602031922330590601328993201490\\   x_4 & & \vdots & & \vdots & = & \underline{0.81649658}10746056647328219979558653427309 \\   x_5 & & \vdots & & \vdots & = & \underline{0.8164965809277260327}667768695067608172972 \\   x_6 & & \vdots & & \vdots & = & \underline{0.81649658092772603273242802490196379732}39 \end{matrix}

los dígitos correctos están subrayados.

A continuación presento la mejora que hice para este método de Newton-Raphson:

\displaystyle x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)} +\sqrt{\frac{f'(x_n)^2}{f''(x_n)^2}-2\frac{f(x_n)}{f''(x_n)}} (2)

Donde f ”(x) es la segunda derivada de f(x). Obviamente esta mejora debería de funcionar para f ”(xn) ≠ 0. Hagamos el cálculo para la función anterior usando esta mejora:

\displaystyle \begin{matrix}   x_1 & = & \underline{0.8}061381468608105183744701440352992991541 \\   x_2 & = & \underline{0.81649}79024576970617429931359189802359533\\   x_3 & = & \underline{0.8164965809277260}299628549775875861636275\\   x_4 & = & \underline{0.8164965809277260327324280249019637973220} \\   x_5 & = & \underline{0.8164965809277260327324280249019637973220} \\   x_6 & = & \underline{0.8164965809277260327324280249019637973220} \end{matrix}
Vemos cómo con esta mejora la iteración converge más rápidamente hacia la raíz. En concreto, para este ejemplo, vemos cómo a partir de x3 la aproximación sobrepasa con creces la precisión de 40 digitos.

Pero, ¿Cómo he obtenido la ecuación de mejora (2)?. La serie de Taylor de la función f(x) centrada en xn es

\displaystyle f(x)=f(x_n)+f'(x_n) (x-x_n)+ (x-x_n)^2 \frac{f''(x_n)}{2!} + ... \,

Si evaluamos para xn+1 obtenemos

\displaystyle f(x_{n+1})=f(x_n)+f'(x_n) (x_{n+1}-x_n)+ (x_{n+1}-x_n)^2 \frac{f''(x_n)}{2!} + ... \,

Como para el cálculo de las raices f(xn+1) debe ser igual a 0, si consideramos hasta el término cuadrático, tendremos

\displaystyle f(x_{n+1})=f(x_n)+f'(x_n) (x_{n+1}-x_n)+ (x_{n+1}-x_n)^2 \frac{f''(x_n)}{2!}= 0,

Y resolviendo esa ecuación cuadrática para xn+1, tendremos:

\displaystyle x_{n+1} = x_n - \frac{f'(x_n)}{f''(x_n)} \pm \sqrt{\frac{f'(x_n)^2}{f''(x_n)^2}-2\frac{f(x_n)}{f''(x_n)}} (3)
Observemos el signo ± delante de la raíz cuadrada del discriminante. Ese signo ± quiere decir que tenemos dos posibles caminos de iteración en la mejora de este método, y los dos deben conducir a una buena aproximación de una de las raices de la función. Obviamente, si en la serie de Taylor consideramos sólo hasta el termino cuadrático excluido, obtenemos el método original de Newton-Raphson. Podríamos considerar mejoras hasta el término cúbico o grados superiores, y veríamos cómo la rapidez de convergencia (o divergencia) aumentaría notablemente.

Este método de Newton-Raphson también puede extenderse a funciones de variable compleja. Así, si partimos de un punto fijo del plano complejo, veríamos cómo sus siguientes puntos de dicho plano, al ir aplicando la iteración, se aproximarían a un punto atractor, el cual sería una de las raíces (ceros) de esa función compleja.

Anuncios

Posted in Fractales, Matemáticas | Etiquetado: , , , , , , , , , , , , , , , , | Leave a Comment »

¿Es la Hipótesis de Riemann un problema indecidible?: empecemos con la Conjetura de Collatz

Posted by Albert Zotkin en diciembre 11, 2015

Quizás la dificultad en resolver la Hipótesis de Riemann tenga que ver con el hecho de que pueda ser un problema indecidible. Si esa hipótesis (o conjetura) es cierta o no, pero sabemos que es indecidible, entonces nunca tendremos una prueba matemática de ella.

Podemos divagar un poco sobre este tema y presentar una conjetura menos compleja (aparentemente) que la de Riemann. Se trata de la Conjetura de Collatz, o tambien conocida como el problema 3n+1. Aquí tenemos un video de Eduardo Sáenz de Cabezón que nos la explica muy sencillamente:

Para esta conjetura se define la siguiente iteración:
flow1

es decir, tenemos una función sobre los enteros positivos definida así:

\displaystyle f(n) = \begin{cases} \tfrac{n}{2}, & \mbox{si }n\mbox{ es par} \\ 3n+1, & \mbox{si }n\mbox{ es impar} \end{cases} (1)

Por ejemplo, para n=2781 tendriamos la siguiente sucesión, la cual terminaría en el 1:


2781➞8344➞4172➞2086➞1043➞3130➞1565➞4696➞2348➞1174➞587➞1762➞881➞2644
➞1322➞661➞1984➞992➞496➞248➞124➞62➞31➞94➞47➞142➞71➞214➞107➞322➞161
➞484➞242➞121➞364➞182➞91➞274➞137➞412➞206➞103➞310➞155➞466➞233➞700➞
350➞175➞526➞263➞790➞395➞1186➞593➞1780➞890➞445➞1336➞668➞334➞167➞
502➞251➞754➞377➞1132➞566➞283➞850➞425➞1276➞638➞319➞958➞479➞1438➞
719➞2158➞1079➞3238➞1619➞4858➞2429➞7288➞3644➞1822➞911➞2734➞1367➞
4102➞2051➞6154➞3077➞9232➞4616➞2308➞1154➞577➞1732➞866➞433➞1300➞
650➞325➞976➞488➞244➞122➞61➞184➞92➞46➞23➞70➞35➞106➞53➞160➞80➞
40➞20➞10➞5➞16➞8➞4➞2➞1

Se sabe ya que la conjetura de Collatz es un problema indecidible, es decir, no se puede probar matemáticamente. Pero eso no quiere decir que la conjetura sea falsa o cierta.

Yo me he animado a crear una función tipo Collatz, que posee la siguiente forma:

\displaystyle h(n) = \begin{cases} 3n+1, & \mbox{si }n\mbox{ es par} \\ \tfrac{n+1}{2}, & \mbox{si }n\mbox{ es impar} \end{cases} (2)

Esta función tipo Collatz da, por ejemplo, para n=101:

101➞51➞26➞79➞40➞121➞61➞31➞16➞49➞25➞13➞7➞4

y para cualquier entero positivo siempre parece que tenemos que la sucesión termina en 4, no en 1 como la anterior. Pero, se trata de ver si la Hipótesis de Riemann es indecidible y qué relación tiene con la conjetura generalizada de Collatz. Lo primero que observamos en toda función de Collatz es que siempre entran en juegos los números pares e impares positivos. Y si nos fijamos, la sucesión de los números primos, nace precisamente de ir cribando los números pares y los números impares (y dentro de los impares se va cribando los múltiplos de 3, de 5, etc), como en la famosa Criba de Eratóstenes. Se me ocurre esta función de Collatz, donde los números primos tienen un papel central:

\displaystyle g(n) = \begin{cases} 3n+1, & \mbox{si }n\mbox{ es primo} \\ f(n), & \mbox{si }n\mbox{ no es primo} \end{cases} (3)
y donde f(n) es la función de Collatz que primero presenté (1). Esta función, así definida, parece que converge siempre hace el número 2, para cualquier n desde el que empecemos la sucesión. Por ejemplo, para n=2710, tendremos:

2710➞1355➞4066➞2033➞6100➞3050➞1525➞4576➞2288➞1144➞572➞286➞143➞430➞
215➞646➞323➞970➞485➞1456➞728➞364➞182➞91➞274➞137➞412➞206➞103➞
310➞155➞466➞233➞700➞350➞175➞526➞263➞790➞395➞1186➞593➞1780➞890➞
445➞1336➞668➞334➞167➞502➞251➞754➞377➞1132➞566➞283➞850➞425➞1276➞
638➞319➞958➞479➞1438➞719➞2158➞1079➞3238➞1619➞4858➞2429➞7288➞3644
➞1822➞911➞2734➞1367➞4102➞2051➞6154➞3077➞9232➞4616➞2308➞1154➞577➞
1732➞866➞433➞1300➞650➞325➞976➞488➞244➞122➞61➞184➞92➞46➞23➞70➞
35➞106➞53➞160➞80➞40➞20➞10➞5➞16➞8➞4➞2

o para n=3001, que es un número primo, tendremos la sucesión siguiente:

3001➞1624➞812➞406➞203➞610➞305➞916➞458➞229➞688➞344➞172➞86➞43➞130➞65➞
196➞98➞49➞148➞74➞37➞112➞56➞28➞14➞7➞22➞11➞34➞17➞52➞26➞13➞40➞
20➞10➞5➞16➞8➞4➞2

De igual forma que las anteriores funciones de Collatz, esta g(n), donde los números primos juegan un papel predominante, da lugar a otra conjetura que también es un problema indecidible, es decir, no se puede demostrar que para cualquier entero positivo n siempre se obtiene una sucesión que converge hacia el número 2. Puesto que la hipótesis de Riemann tiene mucho que ver con los números primos, parece evidente suponer que esta ultima conjetura de Collatz que he propuesto tenga algo que ver con la de Riemann. Y no resultaria una gran sorpresa el descubrimiento de que la propia Hipótesis de Riemann es simple y llanamente un problema indecidible.

Saludos

Posted in curiosidades y analogías, Matemáticas | Etiquetado: , , , , , , , , , , , , | Leave a Comment »

No es cierto que 1+2+3+4+5+…=-1/12

Posted by Albert Zotkin en enero 22, 2014

Se habla mucho últimamente de una curiosa suma: Dicen que la suma de todos los números enteros positivos (naturales) es igual a -1/12., y a eso le llaman regularización. Cualquier persona con un mínimo de sentido común sabe que la suma de todos los números enteros positivos es infinito, es decir, esa suma diverge. Ramanujan sabía eso, por eso supo ver más lejos que nadie y supo que cuando una regularización se basa en una divergencia no se pueden extraer conclusiones sólidas. Los que defienden el absurdo resultado

\displaystyle \sum_{n=1}^\infty n = 1+2+3+\dots =-\frac{1}{12} (1)

están representados por estos dos tios del siguiente video de youtube en el que pretenden convencernos de esa absurda suma mediante cálculos incorrectos. Toda la demostración que se puede ver en ese video se basa en la siguiente serie que diverge:

\displaystyle S_1= 1-1+1-1+1-1+... (2)

y nos quieren colar algo falso, a saber, que dicha suma S1 es igual a 1/2. ¿En qué se basan?. Veamos. Si empiezas a sumar términos de S1 emparejándolos desde el primer 1, se ve claramente que cada par se anula,

\displaystyle S_1= (1-1)+(1-1)+(1-1)+... =0 (3)

con lo cual la suma sería igual a cero. Pero si empiezas a emparejar desde el segundo término entonces la suma daría 1,

\displaystyle S_1= 1+(-1+1)+(-1+1)+(-1+1)... =1 (4)
ese hecho dispar nos está diciendo que la serie S1 es divergente. De hecho, esa disparidad de resultados se usa muy a menudo para demostrar que una serie diverge. Pero, en este caso, puesto que en la mitad de los casos dispares obtenemos 1 y en la otra mitad obtenemos cero, no sé por qué regla de tres, afirman entonces que la suma debe ser regularizada a 1/2 = (0 + 1)/2. Es decir, es regularizada a la media aritmética del conjunto de sus sumas dispares. Después de hacer esa horrible cosa pasa lo que pasa: que podemos, por ejemplo, demostrar que los elefantes verdes voladores existen. Lo honesto en este caso es decir que la serie divergente S1 posee dos ramas, es decir dos valores finitos distintos. (1, 0).

Seguidamente en el video de arriba, Ed Copeland, que es quien nos está mostrando los cálculos sobre el papel, nos presenta la siguiente serie S2:

\displaystyle S_2= 1-2+3-4+5-6+... (5)
Ahora se trata de ver si esa serie S2 puede ser sumada, es decir, si podemos obtener algún número real finito que represente su suma. Lo primero que hacemos es multiplicar S2 por 2:

\displaystyle 2S_2= 1-2+3-4+5-6+... + \\  \mathrm{\hspace{1.42cm}} 1-2+3-4+5-6+... (6)
pero, en lugar de empezar a sumar como se hace arriba, empecemos dejando el primer elemento (el 1) a la izquierda, es decir:

\displaystyle 2S_2= 1-2+3-4+5-6+... + \\  \mathrm{\hspace{2.3cm}} 1-2+3-4+5-6+... (7)

con lo cual tenemos:

\displaystyle 2S_2= 1-1+1-1+1-1+... \\  (8)

es decir, tenemos

\displaystyle 2S_2=S_1 \\ \\  \mathrm{\hspace{0.28cm}} S_2=\frac{S_1}{2} (9)

Esto quiere decir que la serie S2 puede ser expresada en función de la serie S1, y si afirmamos que el valor regularizado de la suma de S1 es 1/2, entonces el valor regularizado de la suma de S2 es:

\displaystyle  S_2=\frac{1}{4} (10)

pero como S1 es divergente y posee dos ramas, en realidad S2 también diverge y posee también dos ramas:

\displaystyle S_2=0 \\ \\   S_2=\frac{1}{2} (11)
Seguidamente Ed Copeland nos presenta la serie:

\displaystyle S= 1+2+3+4+5+6+7+ \dots  (12)
esta es la serie que supuestamente nos daría -1/12, el resultado que he puesto en el título de este post. Veamos cómo en realidad eso no es así. Restemos S2 de S:

\displaystyle S-S_2= 1+2+3+4+5+6+7+ \dots \\ \\  \mathrm{\hspace{1.42cm}} -[1-2+3-4+5-6+\dots] =\\ \\  \mathrm{\hspace{2.1cm}}  0+4+0+8+0+12- \dots (13)

es decir, tenemos que:

\displaystyle S-S_2= 4[1+2+3+4+5+6+7+ \dots ] = 4S \\ \\  S= -\frac{S_2}{3} (14)
o sea, podemos expresar S en función de S2, y como también podemos expresar S2 en función de S1, tenemos que si regularizamos la suma, hallamos el sorprendente ( y equívoco) resultado de

\displaystyle S= -\frac{S_2}{3} = -\frac{S_1}{2 \times 3} = -\frac{1}{4 \times 3} =-\frac{1}{12}   (15)
pero, está claro que S diverge también, igual que S1, y por lo tanto, puesto que es S = -S1/6, tendremos también dos ramas:

\displaystyle \boxed{S= 0 \; ; S=-\frac{1}{6}} (16)
Es decir, la suma de todos los números enteros positivos no es -1/12, sino que diverge hacia infinito porque posee dos ramas, una hacia cero y la otra hacia hacia -1/6.

Saludos

Posted in Matemáticas | Etiquetado: , , , , , , | 15 Comments »

 
A %d blogueros les gusta esto: