dilluns, 10 de gener de 2011

Fes el teu fractal de Newton

Les imatges dels fractals de Newton de l'entrada passada els vaig fer amb el Mathematica. Ara bé, hi ha mètodes alternatius que són més ràpids, i còmodes de fer anar. L'únic inconvenient que té és que s'ha d'introduir la derivada a mà.

El mètode alternatiu implica el programa Ultra Fractal 5. Aquest és un programa que cal comprar o intal·lar-ne una versió de prova. La meva recomanació és que instal·leu la versió de prova ja que quan acaba el termini es pot seguir utilitzant. L'únic problema és que té inhabilitades algunes opcions de renderització i que deixa marques d'aigua a les exportacions d'imatges. Tanmateix és el programa ideal per jugar amb el pla complex.

Si us decidiu per intal·lar el programa podreu navegar pels conjunts de Julia i Mandelbrot i crear-vos els conjunts de Newton que vulgueu. I no només navegar ja que podreu jugar amb les opcions de coloració dels fractals, capes de colors, etc. Amb ell surt la vena artística de la gent de ciències!!

Acabada la publicitat (ara és quan aquella gent m'hauria de donar una llicència gratuïta pel programa) toca començar a fer fractals.

Si teniu ja el programa (i després d'obrir-lo i explorar el conjunt de Mandelbrot) es pot provar de fer fractals de Newton. Per a fer-ho només cal seguir les instruccions següents.

1.- Aneu a File, New, Fractal Formula File.

2.- Entreu a Insert, New Formula..

3.- Introduïu el nom de l'arxiu "Newton", per exemple. Després d'accepta apareix un text base amb comentaris. Ara només caldrà donar algunes instruccions bàsiques.

4.- A l'apartat init: s'ha d'introduir la intrucció z=#pixel. Això dóna a la variable z el valor del píxel en què es troba (punt inicial pel mètode de Newton).

5.- A l'apartat loop: s'ha d'introduir l'expressió del mètode de Newton per exemple z=z-(z^3+2*z^2+z+1)/(3*z^2+4*z+1). Això generarà el fractal de Newton corresponent a la funció $f(z)=z^3+2*z^2+z+1$.

6.- A l'apartat bailout: s'hi ha d'introduir la condició que atura el loop:. En el nostre cas volem que deixi de calcular quan f(z) sigui proper a zero. |x^3+2*z^2+z+1|>0.005 farà que el mètode deixi d'aplicar-se quan f(z) sigui més petita que 0.005.

7.- Ara només cal guardar la fórmula File, Save as, Formulas, My Formulas.

8.- Per obrir el fractal File, New, Fractal, My Formulas, Newton.ufm.

9.- I a explorar!

En un dels comentaris de l'article anterior en Sheldon va preguntar cap a on convergia cada punt ja que els dibuixos els vaig fer en funció de la velocitat de convergència. He estat explorant l'Ultra Fractal i aquí ve el resultat. Les zones estan pintades en funció de la solució a la que convergeixen.

Per la funció $f(z)=z^3+2z^2+z+1$ teníem clarament 3 zones de convergència i una frontera fractal, per tant obtenim aquestes figures:



Per $f(z)=z^3+2z^2+\sqrt{z}+1$:




I per $f(z)=z^3+2z^2+ln(z)+1$:




I ara un dibuix fet amb $f(z)=z^3+2z^2+tan(z)+1$:

divendres, 7 de gener de 2011

Fractals i mètode de Newton

En l'entrada anterior vaig parlar del mètode de Newton per tal de trobar zeros de funcions i resoldre equacions. Com a exemple vaig trobar la solució real de $x^3+2x^2+x+1=0$. A més a més, vaig comentar que n'hi havia dues més i que eren complexes. Per tant, el més raonable és ficar-se a treballar amb els nombres complexos.

Per tenir una idea aproximada d'on es troben les solucions he anat avaluant la funció polinòmica en diferents punts del pla complex (propers a l'origen) i he pintat cada punt depenent del valor del seu mòdul. Els punts més foscos es corresponen als valors més alts.


Els tres zeros es corresponen a les zones blanques i són $x_1=-1.755$ (a l'esquerra), $x_2=-0.123+0.745i$ (a la part superior) i $x_3=-0.123-0.745i$ (a la part inferior). Fins aquí l'únic que s'ha hagut de fer és fer ús del mètode de Newton. El mètode de Newton necessita un punt d'inici, cap a quina solució anem depenent d'aquest punt? O són tots els punts igual de bons??

El que he fet a continuació és anar aplicant el mètode de Newton a diferents punts del pla complex i pintar-los en funció del nombre d'iteracions que necessiten per convergir a una solució.

Pintades de colors més foscos (lila) es mostren les zones per les quals la convergència és més ràpida. Com era d'esperar el pla queda clarament dividit en 3 regions els punts de les quals convergeixen cap a cada un dels zeros. El més interessant, però, és la frontera! Si ampliem una mica la imatge a prop de la frontera que separa les arrels imaginàries ens trobem amb formes molt curioses:


Podem apreciar l'autosimilitud que caracteritza moltes estructures fractals. Aquestes figures es coneixen com els fractals de Newton. Ara doncs, l'únic que fa falta és trobar una equació i provar de resoldre-la.

L'equació $sin(x)+x=0$ només té un zero real ($x=0$). Ara bé el sinus d'un nombre complex pot prendre valors més grans que 1 (cosa que no passa amb els reals). Si es representa el valor de la funció per a diferents punts del pla podem veure el zero real i els zeros complexos (sempre aparellats amb el seu complex conjugat):

Els primers 4 zeros complexos es troben a $x_1=4.212+2.251i$, $x_2= 4.212-2.251i$, $x_3=-4.212+2.251i$ i $x_4=-4.212-2.251i$. Un cop localitzats els zeros pintem els punts en funció de la convergència a les arrels i ampliem algunes zones.




Si canviem la funció per $f(x)=sin(x)+x^2$ obtenim altres estructures:

Si ens fixem amb funcions més complicades com les arrels quadrades i els logaritmes podem trobar-nos amb estructures més problemàtiques. Per exemple, si a l'equació inicial de tercer grau substituïm la $x$ per $\sqrt{x}$ obtenim una nova funció $f(x)=x^3+2x^2+\sqrt{x}+1$ que porta a un fractal de Newton molt diferent.


I fent $f(x)=x^3+2x^2+ln(x)+1$ obtenim aquestes figures:






Ara només és qüestió de trobar funcions interessants i anar-les representant. I encara hi ha qui diu que les matemàtiques són avorrides!! És una llàstima que les matemàtiques les pugui gaudir tan poca gent...

dimarts, 4 de gener de 2011

El mètode de Newton

Un dels capítols importants de les matemàtiques als instituts és la resolució d'equacions. Allà s'ensenyen fórmules per poder arribar a resoldre equacions de segon grau del tipus $ax^2+bx+c=0$.

Si un es fica a inventar-se equacions veu que de seguida passen a ser més complicades de fer. Per exemple, per una equació de tercer grau la fórmula ja és espantosa. Com que recordar aquests desenvolupaments (o saber-los deduir) és feixuc els matemàtics han buscat i trobat camins alternatius.

El que ens interessa és trobar el que s'anomenen zeros d'una funció. Es a dir els valors de $x$ pels que la funció s'anul·la ($f(x)=0$) aquesta és la nostra equació). Per fer això hi ha mètodes força elementals (anar provant valors (més o menys com la loteria de Nadal)) i d'altres de més refinats com el de Newton-Raphson (també anomenat de la tangent).

El mètode de Newton necessita una funció $f(x)$ (que descriu una corba en el pla) i un valor qualsevol $x_1$. El que hem de fer és trobar la recta tangent a la corba en $x_1$ i mirar on talla l'eix de les x: aquest punt de tall serà el valor $x_2$. Amb el segon valor de x hem de fer el que hem fet amb $x_1$ per tal de trobar punt $x_3$. I així successivament.

L'expressió que es fa servir per calcular el punt de tall amb l'eix de les x és la següent:
$x_{n+1}=x_{n}-\frac{f(x_n)}{f\prime(x_n)}$.
On $f'(x_n)$ és la derivada de la funció en el punt $x_n$ (la derivada d'una funció en un punt dóna el pendent de la recta tangent a la funció en aquell punt, es a dir, com de ràpid creix).

En l'animació es mostra com donada una corba se'n troba el zero. La gràcia del mètode és que és ràpid i el podem fer servir en moltes situacions.

Si volem resoldre una equació de tercer grau com la següent $x^3+2x^2+x+1=0$ el primer que hem de fer és construir la funció $f(x)$ i la seva derivada:

$f(x)=x^3+2x^2+x+1$
$f\prime(x)=3x^2+4x+1$

Si representem la funció podem veure que el zero es troba al voltant de -1.8.


Començarem amb $x_1=2$ per veure com funciona el mètode i anirem avaluant la funció després de cada pas.

$x_1=2$
$f(x_1)=19$

$x_2=1.09523$
$f(x_2)= 5.80805$

$x_3=0.44842$
$f(x_3)=1.94075$

$x_4=-0.12290$
$f(x_4)= 0.90545$

$x_5=-1.75814$
$f(x_5)= -0.0105$

$x_6=-1.75489$
$f(x_6)= 0.00004$

Com podem veure amb pocs passos hem obtingut un nombre que fa f(x) molt propera a 0. El punt $x_6$ és una bona aproximació de la solució de l'equació.

Tanmateix, les equacions de tercer grau tenen sempre 3 solucions tot i que poden no ser entre els nombres reals. La que tenim nosaltres només presenta un punt de tall amb l'eix x i, per tant, només té una solució real (les altres dues es troben en els nombres complexos). Per trobar les dues restants també es pot fer ús del mètode de Newton. Depenent de quin sigui el punt inicial anirem cap a zeros diferents!

Les preguntes que un sempre s'ha de fer amb els mètodes numèrics són les següents:

1.- Realment dóna el valor que volem??
2.- En cas de donar el valor correcte quan triga a arribar-hi?

Per tal de respondre aquestes preguntes ara que disposem d'ordinadors la resposta és òbvia. Agafem una regió i anem provant diferents nombres i ens anotem els passos que fan falta per obtenir un valor determinat. Però això ja és del proper article.