Algoritmos y convergencia
Algoritmos y convergencia
Contenido
An
alisis Numerico
Clase 2 Algoritmos y convergencia
CNM-425
Departamento de Matem
aticas
Facultad de Ciencias Exactas y Naturales
Universidad de Antioquia
Algoritmos y convergencia
Algoritmos
Convergencia
c 2008. Reproducci
Copyleft
on permitida bajo los
t
erminos de la licencia de documentaci
on libre GNU.
Algoritmos y convergencia
Algoritmos y convergencia
Algoritmos y convergencia
Estructuras b
asicas
Algoritmo: lista bien definida, ordenada y finita de operaciones que
permite hallar la soluci
on a un problema.
Pseudoc
odigo = pseudo (supuesto) + c
odigo (instrucci
on).
Descripci
on informal y compacta de un algoritmo que utiliza
convenciones estructurales de ciertos lenguajes de programaci
on.
Estructuras de control
Secuencial
Selectiva (decisi
on l
ogica)
Iterativa (repetitiva)
Secuencial
Selectiva (decisi
on l
ogica)
instrucci
on 1
instrucci
on 2
.
.
.
si P entonces
instrucciones 1;
si no
instrucciones 2;
fin si
instrucci
on n
Iterativa (repetitiva)
Iterativa (repetitiva)
mientras P hacer
instrucciones;
fin mientras
para i = inicio hasta f inal
hacer
instrucciones;
fin para
Algoritmos y convergencia
Algoritmos y convergencia
El siguiente algoritmo calcula
n
X
Ejemplos
xi = x1 + x2 + + xn .
i=1
El polinomio de Taylor de f (x) = ln x en torno de x0 = 1 est
a dado por
leer n, x1 , x2 , . . . , xn ;
SU M A = 0;
Pn (x) =
para i = 1 hasta n
SU M A = SU M A + xi ;
fin para
escribir La suma es, SU M A;
El siguiente algoritmo calcula
n
Y
xi = x1 x2 xn .
i=1
n
X
(1)i1
(x 1)i
i
i=1
(1)
y podemos utilizarlo para calcular ln 1,5 cuyo valor aproximado a ocho
cifras decimales es 0,40546511
El siguiente algoritmo calcula el n
umero n de terminos necesarios de
(1) para que
leer n, x1 , x2 , . . . , xn ;
| ln 1,5 Pn (1,5)| < 105
(2)
P RODU CT O = 1;
para i = 1 hasta n
P RODU CT O = P RODU CT O xi ;
fin para
teniendo en cuenta que para series alternantes convergentes
Sn = a1 + a2 + + an S, se cumple que
escribir El prodcuto es, P RODU CT O;
|S Sn | |an+1 |
Algoritmos y convergencia
Algoritmos y convergencia
Ejemplos
Estabilidad
leer x, T OL y M ;
// TOL es la tolerancia y M es el n
umero m
aximo de iteraciones.
N =1;
y = x 1;
SU M A = 0;
P OT EN CIA = y;
T ERM IN O = y;
SIGN O = 1;
mientras N M hacer
SIGN O = SIGN O;
SU M A = SU M A + SIGN O T ERM IN O;
P OT EN CIA = P OT EN CIA y;
T ERM IN O = P OT EN CIA/(N + 1);
si |T ERM IN O| < T OL entonces
escribir T
erminos requeridos: , N );
parar;
fin si
N = N + 1;
fin mientras
Escribir El m
etodo fall
o
parar;
(3)
Un algoritmo recibe unos datos de entrada (input) y produce unos
datos de salida o soluci
on (output).
Un algoritmo es estable si cambios peque
nos en los datos de
entrada producen cambios peque
nos en los datos de salida.
C
omo influyen los errores de redondeo en la estabilidad de un
algoritmo?
Definici
on
Suponga E0 > 0 un error inicial y En el error que se obtiene despues de
ejectuarse n operaciones sucesivas.
Error lineal: si En CnE0 con C una constante positiva, el crecimiento del
error es lineal.
Error exponencial: si En C n E0 con C > 1, el crecimiento del error es
exponencial.
Algoritmos y convergencia
Algoritmos y convergencia
Crecimiento exponencial
Crecimiento exponencial
Ejemplo: consideremos la ecuaci
on en diferencias
xn =
10
xn1 xn2 ,
3
para
Con aritmetica de redondeo a cinco cifras, x
0 = 1,0000 y x
1 = 0,33333
y para las constantes obtenemos c1 = 1,0000 y c2 = 0,12500 105 y
(4) queda
n = 2, 3, . . .
cuya soluci
on est
a dada por
xn = c1
n
1
+ c2 3n
3
x
n = 1,0000
(4)
donde c1 y c2 son constantes que dependen de las condiciones
iniciales x0 y x1 .
n
1
0,12500 105 3n
3
y por tanto el error de redondeo
xn x
n = 0,12500 105 3n
Con x0 = 1 y x1 =
1
3
obtenemos c1 = 1 y c2 = 0 y (4) queda
n
1
xn =
3
crece exponencialmente.
Algoritmos y convergencia
Algoritmos y convergencia
Crecimiento lineal
Crecimiento lineal
Ejemplo: consideremos ahora la ecuaci
on en diferencias
xn = 2xn1 xn2 ,
para
Con aritmetica de redondeo a cinco cifras, x
0 = 1,0000 y x
1 = 0,33333
y para las constantes obtenemos c1 = 1,0000 y c2 = 0,66667 105 y
(5) queda
n = 2, 3, . . .
cuya soluci
on est
a dada por
xn = c1 + c2 n
x
n = 1,0000 0,66667 n
(5)
donde c1 y c2 son constantes que dependen de las condiciones
iniciales x0 y x1 .
y por tanto el error de redondeo
Con x0 = 1 y x1 =
1
3
xn x
n =
obtenemos c1 = 1 y c2 = 32 y (5) queda
xn = 1
2
n
3
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Errores aritmeticos y de redondeo
Definici
on O may
uscula
Sea {n } una suceci
on tal que n 0 y {n } una sucesi
on tal que n .
La suceci
on {n } converge a con rapidez de convergencia O(n ) si
existe una constante K tal que
n :=
1
n
1
n := 2 ,
n
entonces
n = 0 + O
n+3
n + 3n
1
= 4 2 = 4n
n3
n3
n
n = 0 + O
Ejemplo: consideremos
|
n 0| =
y
n =
n+3
0.
n3
Algoritmos y convergencia
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Errores aritmeticos y de redondeo
Definici
on
Suponga lm G(h) = 0 y lm F (h) = L.
h0
h0
De (6),
F (h) = L + O(G(h))
1 h4 0
cos h + 1 h2 1 = 1 h4 cos (h)
24
2
24
si existe una constante positiva K tal que
|F (h) L| K|G(h)|,
para h suficientemente peque
no.
y por tanto
Por lo general G(h) = hp con p > 0.
cos h +
Ejemplo: al utilizar el tercer polinomio de Taylor de coseno,
cos h = 1
con 0 < (h)
< h.
1
n
n+1
n+n
1
= 2 = 2n
n2
n2
n
|n 0| =
1
con p > 0.
np
n+1
0
n2
Ambas sucesiones convergen a cero pero una lo hace m
as r
apido que
otra: si
n = + O(n )
n =
para n grande,
y en tal caso se acostumbra a escribir
Por lo general n =
2
3
crece linealmente.
Algoritmos y convergencia
|n | K|n | ,
0,66667
1 2
1 4
h +
h cos (h)
2
24
(6)
1 2
h = 1 + O(h4 )
2
1
n2
