PDF de programación - Creando fractales con el método de Newton

Imágen de pdf Creando fractales con el método de Newton

Creando fractales con el método de Newtongráfica de visualizaciones

Publicado el 12 de Julio del 2017
641 visualizaciones desde el 12 de Julio del 2017
14,5 MB
9 paginas
Creado hace 12a (18/06/2009)
Creando fractales con el método de Newton

Pablo Santamaría

v0.1 (Junio 2009)

El método de Newton, ideado por Isacc Newton alrededor de 1670, constituye una de las
técnicas numéricas más poderosas para aproximar raíces de una ecuación f(x) = 0. El método
comienza con una aproximación inicial x0 para la raíz y genera una sucesión de aproximaciones
x1, x2, . . . según la fórmula

xn+1 = xn − f(xn)

f0(xn) , n = 1, 2, . . .

sucesión que converge rápidamente a la raíz si la aproximación inicial se encuentra suficientemente
próxima a la misma. Nótese que el método no está restringido a los números reales, sino que,
de hecho, puede ser aplicado por igual a funciones sobre el campo complejo. Consideremos en
particular la ecuación

z4 − 1 = 0.

En el campo real la misma sólo tiene una raíz, a saber, 1. Pero en el campo complejo, la ecuación
tiene cuatro raíces:

ζ1 = 1,

ζ4 = −i.

ζ2 = −1,

ζ3 = i,

Supongamos que, entonces, aplicamos el método de Newton a esta ecuación. En 1876, Arthur
Cayley propuso el siguiente problema: dado un valor inicial z0 cualquiera del plano complejo, ¿a
cual de las cuatro raíces convergerá el método de Newton? La respuesta a este problema conduce
sorprendentemente a una figura de naturaleza fractal. Para ver ésto procederemos como sigue:

En el cuadrado [−2, 2 ]×[−2, 2 ] consideramos un gran número de valores iniciales z0 escogidos
al azar.
Aplicamos el método de Newton a la ecuación z4 − 1 = 0 para cada valor z0 escogido.
Coloreamos el punto z0 en el plano complejo ya sea de rojo, verde, azul o magenta según a
que raíz ζ1, ζ2, ζ3 o ζ4, respectivamente, ha convergido el método.

Un programa en Fortran 77 para realizar tal procedimiento es dado a continuación. En apuntes
anteriores ya hemos implementado el método de Newton en sendas subrutinas de Fortran 77 y
Fortran 951. Llevar tal subrutina al campo complejo no reviste mayor dificultad que reemplazar las
correspondientes variables reales por variables complejas. Esto conduce a la siguiente subrutina.

SUBROUTINE NEWTON(F,DF,XX0,NMAX,TOL,RAIZ,ICLAVE)
---------------------------------------------------
METODO DE NEWTON-RAPHSON para encontrar una
solución de f(x)=0 dada la función derivable
f y una aproximación inicial x0.
---------------------------------------------------
Bloque de identificación de argumentos

*
*
*
*
*
*

1Ver los apuntes Subrutinas para la resolución de ecuaciones de una variable o Subrutinas en Fortran 95 para

la resolución de ecuaciones de una variable

1

*
*
*
*
*
*
*
*
*
*
*
*
*

*

*
*
*

*

---------------------------------------------------
F = Función que define la ecuación (arg entrada)
DF = Función derivada de F (arg entrada)
XX0 = Aproximación inicial (arg entrada)
NMAX = Número máximo de iteraciones (arg entrada)
TOL = Tolerancia del error relativo (arg entrada)
RAIZ = Estimación de la solución (arg salida)
ICLAVE = Clave de éxito (arg salida)

0 = éxito
1 = iteraciones excedidas

---------------------------------------------------
Bloque de declaración de tipo
---------------------------------------------------
IMPLICIT NONE
INTEGER NMAX, ICLAVE
DOUBLE COMPLEX F, DF, XX0, RAIZ
DOUBLE PRECISION TOL
---------------------------------------------------
INTEGER I
DOUBLE COMPLEX X0
---------------------------------------------------
Bloque de procesamiento
---------------------------------------------------
ICLAVE = 0
= XX0
X0
DO I=1,NMAX

= X0 - F(X0)/DF(X0)

RAIZ
IF (ABS((RAIZ-X0)/RAIZ).LT.TOL) RETURN
X0 = RAIZ

END DO
ICLAVE = 1
RETURN
END
---------------------------------------------------

El método de Newton requiere de la función que define a la ecuación y su derivada, las cuales son
implementadas en apropiadas FUNCTION complejas.

DOUBLE COMPLEX FUNCTION F(Z)
IMPLICIT NONE
DOUBLE COMPLEX Z
F = Z**4 -(1.0D0,0.0D0)
RETURN
END

DOUBLE COMPLEX FUNCTION DF(Z)
IMPLICIT NONE
DOUBLE COMPLEX Z
DF = (4.0D0,0.0D0)*Z**3
RETURN
END

Finalmente consideremos el programa principal. En el cuadrado de semilado A = 2, conteniendo el
origen, generamos NPOINTS = 50 0000 números complejos Z0 = (X0,Y0) como condiciones iniciales
para el método de Newton. Para ello utilizamos un generador de números aleatorios, provisto
por las subrutinas intrínsecas RANDOM_SEED, que inicializa el generador, y RANDOM_NUMBER, la cual
devuelve un número al azar entre 0 y 1. Puesto que nosotros queremos números aleatorios en el
rango [-A:A] efectuamos una simple transformación lineal para llevarlos a tal rango. Con el fin de
distinguir a cual de las cuatro raíces converge el método creamos cuatro archivos, uno para cada

2

raíz. Entonces dependiendo la solución obtenida con el método de Newton, la condición inicial es
guardada en el archivo que corresponde a la raíz a la cual ha convergido.

*

PROGRAM FRACTAL_NEWTON
-------------------------------------------------------------------
IMPLICIT NONE

! Número de raíces
! Número de aproximaciones iniciales
! Número máximo de iteraciones en Newton
! Semilado del cuadrado [-A:A][-A:A]
! Cota para el error relativo en Newton

A

INTEGER NROOTS
INTEGER NPOINTS
INTEGER NMAX
REAL
DOUBLE PRECISION TOL
PARAMETER (NROOTS
&
&
&
&

= 4,

NPOINTS = 500000,
NMAX
A
TOL

= 100,
= 2.0,
= 1.0D-8)

DOUBLE COMPLEX ROOTS(NROOTS) ! Raíces de la ecuación
DATA ROOTS/( 1.0D0, 0.0D0),
&
&
&

1
(-1.0D0, 0.0D0), ! -1
( 0.0D0, 1.0D0), ! i
( 0.0D0,-1.0D0)/ ! -i

!

INTEGER CLAVE
INTEGER UNIDAD
INTEGER I,J

DOUBLE COMPLEX F,DF
EXTERNAL F,DF

! Clave de error de la subrutina Newton
! Número de unidad para archivos de salida

! Funcion y derivada de la ecuación

DOUBLE COMPLEX Z0,RAIZ
DOUBLE PRECISION X0,Y0
REAL R

! Aproximación inicial y solución
! Parte real e imaginaria de la aprox. inicial
! Número al azar entre 0 y 1

CHARACTER(7) ARCHIVO
CHARACTER(2) NUMSTRING
LOGICAL SEGUIR
-------------------------------------------------------------------
Crear archivos de salida para cada una de las raíces
-------------------------------------------------------------------
DO J=1,NROOTS

UNIDAD = 10+J
WRITE(NUMSTRING,’(I2.2)’) J
ARCHIVO = ’raiz-’ // NUMSTRING
OPEN(UNIDAD,FILE=ARCHIVO)

ENDDO
-------------------------------------------------------------------
Proceder
-------------------------------------------------------------------
CALL RANDOM_SEED()

! Inicializar semilla

DO I = 1,NPOINTS

----------------------------------------------------------------
Construir una aproximación inicial compleja dentro del
del cuadrado
----------------------------------------------------------------
CALL RANDOM_NUMBER(R)
X0
= DBLE(-A+2.0*A*R)

[-A:A][-A:A]

*
*
*

*
*
*

*
*
*
*

3

*
*
*

*
*
*
*

*
*
*

CALL RANDOM_NUMBER(R)
Y0
= DBLE(-A+2.0*A*R)
Z0
= COMPLEX(X0,Y0)
----------------------------------------------------------------
Resolver la ecuación con el método de Newton con tal aproximación
----------------------------------------------------------------
CLAVE = 0
CALL NEWTON(F,DF,Z0,NMAX,TOL,RAIZ,CLAVE)
----------------------------------------------------------------
Imprimir la condición inicial en el archivo correspondiente
según la raíz obtenida
----------------------------------------------------------------
IF (CLAVE.EQ.0) THEN

= 1

J
SEGUIR = .TRUE.
DO WHILE(SEGUIR.AND.J.LE.NROOTS)

IF (ABS(RAIZ-ROOTS(J)).LE.TOL) THEN

UNIDAD = 10 + J
WRITE (UNIDAD,*) X0, Y0
SEGUIR = .FALSE.

ENDIF
J = J + 1

ENDDO

ENDIF

END DO
----------------------------------------------------------------
Cerrar archivos de salida y terminar
----------------------------------------------------------------
DO J=1,NROOTS

UNIDAD = 10+J
CLOSE(UNIDAD)

END DO
STOP
END

Con los cuatro archivos, raiz-01, raiz-02, raiz-03 y raiz-04, generados por la ejecución del
programa, utilizamos las siguientes sentencias en el programa gnuplot para obtener el mapa de
aproximaciones.

gnuplot> set size square
gnuplot> set xrange [-2:2]
gnuplot> set yrange [-2:2]
gnuplot> plot "raiz-01" w d, "raiz-02" w d, "raiz-03" w d, "raiz-04" w d

El resultado obtenido se ilustra en la figura 1. Las amplias regiones de un solo color corresponden
a puntos que convergen rápidamente a la respectiva raíz. Pero entre tales áreas de convergencia
obtenemos estructuras fractales donde la convergencia no está bien comportada. Estructuras frac-
tales similares resultan para otras ecuaciones. Por ejemplo, la figura 2 ilustra la distribución de
las aproximaciones iniciales para la ecuación z3 − 1 = 0, cuyas raíces son 1, −1/2 ± i

3/2.



Es fácil generalizar el programa para analizar la convergencia de las aproximaciones iniciales

z0 para una ecuación algebraica cualquiera dados los n ceros ζi, i = 1, . . . , n de la misma:

nY

i=1

f(z) =

(z − ζi) = 0.

En este caso, aplicando la regla de derivación de un producto tenemos que:

nX

Y

i=1

j6=i

f0(z) =

(z − ζj) =

nX

1

(z − ζi)

(z − ζj) = f(z)

j=1

i=1

nY

nX

i=1

1

(z − ζi)

4

Figura 1. Distribución en el plano complejo de las aproximaciones
iniciales z0 para la ecuación z4 − 1 = 0 según la convergencia por el
método de Newton a la raíz ζ1 = 1 (en rojo), ζ2 = −1 (en verde),
ζ3 = i (en azul) o ζ4 = −i (en magenta).

con lo cual, un paso del método de Newton puede ser calculado en forma simple como:

xn+1 = xn − f(xn)
f0(xn)

= xn −

1

(xn − ζi)

nX

i=1

−1

.

De este modo no se requiere especificar la función f ni su derivada, sino que simplemente se necesita
especificar los ceros. A continuación presentamos el programa que hace uso de este resultado, donde
la subrutina que implementa el método de Newton ha sido modificada para éste propósito. Como
caso particular consideramos la ecuación:

(z − 3)(z − 2)(z − 1)(z + 1)(z + 2)(z + 3) = 0,

(1)

la cual tiene 6 raíces. La estructura fractal obtenida, ilustrada en la figura 3, es mucho más pequeña
comparada con la estructura general, sin embargo, en los bordes de las zonas de convergencia bien
comportada, ésta se presenta nuevamente.

*

PROGRAM FRACTAL_NEWTON
-------------------------------------------------------------------
IMPLICIT NONE

INTEGER NROOTS
INTEGER NPOINTS
INTE
  • Links de descarga
http://lwp-l.com/pdf5335

Comentarios de: Creando fractales con el método de Newton (0)


No hay comentarios
 

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios...
CerrarCerrar
CerrarCerrar
Cerrar

Tienes que ser un usuario registrado para poder insertar imágenes, archivos y/o videos.

Puedes registrarte o validarte desde aquí.

Codigo
Negrita
Subrayado
Tachado
Cursiva
Insertar enlace
Imagen externa
Emoticon
Tabular
Centrar
Titulo
Linea
Disminuir
Aumentar
Vista preliminar
sonreir
dientes
lengua
guiño
enfadado
confundido
llorar
avergonzado
sorprendido
triste
sol
estrella
jarra
camara
taza de cafe
email
beso
bombilla
amor
mal
bien
Es necesario revisar y aceptar las políticas de privacidad