Algoritmos y convergencia
Analisis NumericoClase 2 – Algoritmos y convergencia
CNM-425
Departamento de MatematicasFacultad de Ciencias Exactas y Naturales
Universidad de Antioquia
Copyleft c© 2008. Reproduccion permitida bajo los
terminos de la licencia de documentacion libre GNU.
Algoritmos y convergencia
Contenido
1 Algoritmos y convergenciaAlgoritmosConvergencia
Algoritmos y convergencia
Algoritmos y convergencia
Algoritmo: lista bien definida, ordenada y finita de operaciones quepermite hallar la solucion a un problema.
Pseudocodigo = pseudo (supuesto) + codigo (instruccion).Descripcion informal y compacta de un algoritmo que utilizaconvenciones estructurales de ciertos lenguajes de programacion.
Estructuras de control
Secuencial
Selectiva (decision logica)
Iterativa (repetitiva)
Algoritmos y convergencia
Estructuras basicas
Secuencial
instruccion 1
instruccion 2...
instruccion n
Selectiva (decision logica)
si P entonces
instrucciones 1;
si no
instrucciones 2;
fin si
Iterativa (repetitiva)
mientras P hacer
instrucciones;
fin mientras
Iterativa (repetitiva)
para i = inicio hasta finalhacer
instrucciones;
fin para
Algoritmos y convergencia
Estructuras basicas
Secuencial
instruccion 1
instruccion 2...
instruccion n
Selectiva (decision logica)
si P entonces
instrucciones 1;
si no
instrucciones 2;
fin si
Iterativa (repetitiva)
mientras P hacer
instrucciones;
fin mientras
Iterativa (repetitiva)
para i = inicio hasta finalhacer
instrucciones;
fin para
Algoritmos y convergencia
Estructuras basicas
Secuencial
instruccion 1
instruccion 2...
instruccion n
Selectiva (decision logica)
si P entonces
instrucciones 1;
si no
instrucciones 2;
fin si
Iterativa (repetitiva)
mientras P hacer
instrucciones;
fin mientras
Iterativa (repetitiva)
para i = inicio hasta finalhacer
instrucciones;
fin para
Algoritmos y convergencia
Estructuras basicas
Secuencial
instruccion 1
instruccion 2...
instruccion n
Selectiva (decision logica)
si P entonces
instrucciones 1;
si no
instrucciones 2;
fin si
Iterativa (repetitiva)
mientras P hacer
instrucciones;
fin mientras
Iterativa (repetitiva)
para i = inicio hasta finalhacer
instrucciones;
fin para
Algoritmos y convergencia
El siguiente algoritmo calcula
nXi=1
xi = x1 + x2 + · · ·+ xn.
leer n, x1, x2, . . . , xn;
SUMA = 0;
para i = 1 hasta nSUMA = SUMA + xi;
fin para
escribir ’La suma es’, SUMA;
El siguiente algoritmo calcula
nYi=1
xi = x1 · x2 · · ·xn.
leer n, x1, x2, . . . , xn;
PRODUCTO = 1;
para i = 1 hasta nPRODUCTO = PRODUCTO · xi;
fin para
escribir ’El prodcuto es’, PRODUCTO;
Algoritmos y convergencia
El siguiente algoritmo calcula
nXi=1
xi = x1 + x2 + · · ·+ xn.
leer n, x1, x2, . . . , xn;
SUMA = 0;
para i = 1 hasta nSUMA = SUMA + xi;
fin para
escribir ’La suma es’, SUMA;
El siguiente algoritmo calcula
nYi=1
xi = x1 · x2 · · ·xn.
leer n, x1, x2, . . . , xn;
PRODUCTO = 1;
para i = 1 hasta nPRODUCTO = PRODUCTO · xi;
fin para
escribir ’El prodcuto es’, PRODUCTO;
Algoritmos y convergencia
El siguiente algoritmo calcula
nXi=1
xi = x1 + x2 + · · ·+ xn.
leer n, x1, x2, . . . , xn;
SUMA = 0;
para i = 1 hasta nSUMA = SUMA + xi;
fin para
escribir ’La suma es’, SUMA;
El siguiente algoritmo calcula
nYi=1
xi = x1 · x2 · · ·xn.
leer n, x1, x2, . . . , xn;
PRODUCTO = 1;
para i = 1 hasta nPRODUCTO = PRODUCTO · xi;
fin para
escribir ’El prodcuto es’, PRODUCTO;
Algoritmos y convergencia
El siguiente algoritmo calcula
nXi=1
xi = x1 + x2 + · · ·+ xn.
leer n, x1, x2, . . . , xn;
SUMA = 0;
para i = 1 hasta nSUMA = SUMA + xi;
fin para
escribir ’La suma es’, SUMA;
El siguiente algoritmo calculanY
i=1
xi = x1 · x2 · · ·xn.
leer n, x1, x2, . . . , xn;
PRODUCTO = 1;
para i = 1 hasta nPRODUCTO = PRODUCTO · xi;
fin para
escribir ’El prodcuto es’, PRODUCTO;
Algoritmos y convergencia
El siguiente algoritmo calcula
nXi=1
xi = x1 + x2 + · · ·+ xn.
leer n, x1, x2, . . . , xn;
SUMA = 0;
para i = 1 hasta nSUMA = SUMA + xi;
fin para
escribir ’La suma es’, SUMA;
El siguiente algoritmo calculanY
i=1
xi = x1 · x2 · · ·xn.
leer n, x1, x2, . . . , xn;
PRODUCTO = 1;
para i = 1 hasta nPRODUCTO = PRODUCTO · xi;
fin para
escribir ’El prodcuto es’, PRODUCTO;
Algoritmos y convergencia
El siguiente algoritmo calcula
nXi=1
xi = x1 + x2 + · · ·+ xn.
leer n, x1, x2, . . . , xn;
SUMA = 0;
para i = 1 hasta nSUMA = SUMA + xi;
fin para
escribir ’La suma es’, SUMA;
El siguiente algoritmo calculanY
i=1
xi = x1 · x2 · · ·xn.
leer n, x1, x2, . . . , xn;
PRODUCTO = 1;
para i = 1 hasta nPRODUCTO = PRODUCTO · xi;
fin para
escribir ’El prodcuto es’, PRODUCTO;
Algoritmos y convergencia
El siguiente algoritmo calcula
nXi=1
xi = x1 + x2 + · · ·+ xn.
leer n, x1, x2, . . . , xn;
SUMA = 0;
para i = 1 hasta nSUMA = SUMA + xi;
fin para
escribir ’La suma es’, SUMA;
El siguiente algoritmo calculanY
i=1
xi = x1 · x2 · · ·xn.
leer n, x1, x2, . . . , xn;
PRODUCTO = 1;
para i = 1 hasta nPRODUCTO = PRODUCTO · xi;
fin para
escribir ’El prodcuto es’, PRODUCTO;
Algoritmos y convergencia
El siguiente algoritmo calcula
nXi=1
xi = x1 + x2 + · · ·+ xn.
leer n, x1, x2, . . . , xn;
SUMA = 0;
para i = 1 hasta nSUMA = SUMA + xi;
fin para
escribir ’La suma es’, SUMA;
El siguiente algoritmo calculanY
i=1
xi = x1 · x2 · · ·xn.
leer n, x1, x2, . . . , xn;
PRODUCTO = 1;
para i = 1 hasta nPRODUCTO = PRODUCTO · xi;
fin para
escribir ’El prodcuto es’, PRODUCTO;
Algoritmos y convergencia
Ejemplos
El polinomio de Taylor de f(x) = lnx en torno de x0 = 1 esta dado por
Pn(x) =
nXi=1
(−1)i−1
i(x− 1)i (1)
y podemos utilizarlo para calcular ln 1,5 cuyo valor aproximado a ochocifras decimales es 0,40546511
El siguiente algoritmo calcula el numero n de terminos necesarios de(1) para que
| ln 1,5− Pn(1,5)| < 10−5 (2)
teniendo en cuenta que para series alternantes convergentesSn = a1 + a2 + · · ·+ an → S, se cumple que
|S − Sn| ≤ |an+1| (3)
Algoritmos y convergencia
Ejemplos
El polinomio de Taylor de f(x) = lnx en torno de x0 = 1 esta dado por
Pn(x) =
nXi=1
(−1)i−1
i(x− 1)i (1)
y podemos utilizarlo para calcular ln 1,5 cuyo valor aproximado a ochocifras decimales es 0,40546511
El siguiente algoritmo calcula el numero n de terminos necesarios de(1) para que
| ln 1,5− Pn(1,5)| < 10−5 (2)
teniendo en cuenta que para series alternantes convergentesSn = a1 + a2 + · · ·+ an → S, se cumple que
|S − Sn| ≤ |an+1| (3)
Algoritmos y convergencia
Ejemplos
leer x, TOL y M;// TOL es la tolerancia y M es el numero maximo de iteraciones.
N=1;y = x− 1;SUMA = 0;POTENCIA = y;TERMINO = y;SIGNO = −1;
mientras N ≤M hacer
SIGNO = −SIGNO;SUMA = SUMA + SIGNO × TERMINO;POTENCIA = POTENCIA× y;TERMINO = POTENCIA/(N + 1);
si |TERMINO| < TOL entoncesescribir ’Terminos requeridos: ’, N);parar;
fin si
N = N + 1;
fin mientras
Escribir ’El metodo fallo’parar;
Algoritmos y convergencia
Ejemplos
leer x, TOL y M;// TOL es la tolerancia y M es el numero maximo de iteraciones.
N=1;y = x− 1;SUMA = 0;POTENCIA = y;TERMINO = y;SIGNO = −1;
mientras N ≤M hacer
SIGNO = −SIGNO;SUMA = SUMA + SIGNO × TERMINO;POTENCIA = POTENCIA× y;TERMINO = POTENCIA/(N + 1);
si |TERMINO| < TOL entoncesescribir ’Terminos requeridos: ’, N);parar;
fin si
N = N + 1;
fin mientras
Escribir ’El metodo fallo’parar;
Algoritmos y convergencia
Ejemplos
leer x, TOL y M;// TOL es la tolerancia y M es el numero maximo de iteraciones.
N=1;y = x− 1;SUMA = 0;POTENCIA = y;TERMINO = y;SIGNO = −1;
mientras N ≤M hacer
SIGNO = −SIGNO;SUMA = SUMA + SIGNO × TERMINO;POTENCIA = POTENCIA× y;TERMINO = POTENCIA/(N + 1);
si |TERMINO| < TOL entoncesescribir ’Terminos requeridos: ’, N);parar;
fin si
N = N + 1;
fin mientras
Escribir ’El metodo fallo’parar;
Algoritmos y convergencia
Ejemplos
leer x, TOL y M;// TOL es la tolerancia y M es el numero maximo de iteraciones.
N=1;y = x− 1;SUMA = 0;POTENCIA = y;TERMINO = y;SIGNO = −1;
mientras N ≤M hacer
SIGNO = −SIGNO;SUMA = SUMA + SIGNO × TERMINO;POTENCIA = POTENCIA× y;TERMINO = POTENCIA/(N + 1);
si |TERMINO| < TOL entoncesescribir ’Terminos requeridos: ’, N);parar;
fin si
N = N + 1;
fin mientras
Escribir ’El metodo fallo’parar;
Algoritmos y convergencia
Ejemplos
leer x, TOL y M;// TOL es la tolerancia y M es el numero maximo de iteraciones.
N=1;y = x− 1;SUMA = 0;POTENCIA = y;TERMINO = y;SIGNO = −1;
mientras N ≤M hacer
SIGNO = −SIGNO;SUMA = SUMA + SIGNO × TERMINO;POTENCIA = POTENCIA× y;TERMINO = POTENCIA/(N + 1);
si |TERMINO| < TOL entoncesescribir ’Terminos requeridos: ’, N);parar;
fin si
N = N + 1;
fin mientras
Escribir ’El metodo fallo’parar;
Algoritmos y convergencia
Ejemplos
leer x, TOL y M;// TOL es la tolerancia y M es el numero maximo de iteraciones.
N=1;y = x− 1;SUMA = 0;POTENCIA = y;TERMINO = y;SIGNO = −1;
mientras N ≤M hacer
SIGNO = −SIGNO;SUMA = SUMA + SIGNO × TERMINO;POTENCIA = POTENCIA× y;TERMINO = POTENCIA/(N + 1);
si |TERMINO| < TOL entoncesescribir ’Terminos requeridos: ’, N);parar;
fin si
N = N + 1;
fin mientras
Escribir ’El metodo fallo’parar;
Algoritmos y convergencia
Estabilidad
Un algoritmo recibe unos datos de entrada (“input”) y produce unosdatos de salida o solucion (“output”).
Un algoritmo es estable si cambios “pequenos” en los datos deentrada producen cambios “pequenos” en los datos de salida.
¿Como influyen los errores de redondeo en la estabilidad de unalgoritmo?
Definicion
Suponga E0 > 0 un error inicial y En el error que se obtiene despues deejectuarse n operaciones sucesivas.
Error lineal: si En ≈ CnE0 con C una constante positiva, el crecimiento delerror es lineal.
Error exponencial: si En ≈ CnE0 con C > 1, el crecimiento del error esexponencial.
Algoritmos y convergencia
Estabilidad
Un algoritmo recibe unos datos de entrada (“input”) y produce unosdatos de salida o solucion (“output”).
Un algoritmo es estable si cambios “pequenos” en los datos deentrada producen cambios “pequenos” en los datos de salida.
¿Como influyen los errores de redondeo en la estabilidad de unalgoritmo?
Definicion
Suponga E0 > 0 un error inicial y En el error que se obtiene despues deejectuarse n operaciones sucesivas.
Error lineal: si En ≈ CnE0 con C una constante positiva, el crecimiento delerror es lineal.
Error exponencial: si En ≈ CnE0 con C > 1, el crecimiento del error esexponencial.
Algoritmos y convergencia
Estabilidad
Un algoritmo recibe unos datos de entrada (“input”) y produce unosdatos de salida o solucion (“output”).
Un algoritmo es estable si cambios “pequenos” en los datos deentrada producen cambios “pequenos” en los datos de salida.
¿Como influyen los errores de redondeo en la estabilidad de unalgoritmo?
Definicion
Suponga E0 > 0 un error inicial y En el error que se obtiene despues deejectuarse n operaciones sucesivas.
Error lineal: si En ≈ CnE0 con C una constante positiva, el crecimiento delerror es lineal.
Error exponencial: si En ≈ CnE0 con C > 1, el crecimiento del error esexponencial.
Algoritmos y convergencia
Estabilidad
Un algoritmo recibe unos datos de entrada (“input”) y produce unosdatos de salida o solucion (“output”).
Un algoritmo es estable si cambios “pequenos” en los datos deentrada producen cambios “pequenos” en los datos de salida.
¿Como influyen los errores de redondeo en la estabilidad de unalgoritmo?
Definicion
Suponga E0 > 0 un error inicial y En el error que se obtiene despues deejectuarse n operaciones sucesivas.
Error lineal: si En ≈ CnE0 con C una constante positiva, el crecimiento delerror es lineal.
Error exponencial: si En ≈ CnE0 con C > 1, el crecimiento del error esexponencial.
Algoritmos y convergencia
Crecimiento exponencial
Ejemplo: consideremos la ecuacion en diferencias
xn =10
3xn−1 − xn−2, para n = 2, 3, . . .
cuya solucion esta dada por
xn = c1
„1
3
«n
+ c23n (4)
donde c1 y c2 son constantes que dependen de las “condicionesiniciales” x0 y x1.
Con x0 = 1 y x1 = 13
obtenemos c1 = 1 y c2 = 0 y (4) queda
xn =
„1
3
«n
Algoritmos y convergencia
Crecimiento exponencial
Ejemplo: consideremos la ecuacion en diferencias
xn =10
3xn−1 − xn−2, para n = 2, 3, . . .
cuya solucion esta dada por
xn = c1
„1
3
«n
+ c23n (4)
donde c1 y c2 son constantes que dependen de las “condicionesiniciales” x0 y x1.
Con x0 = 1 y x1 = 13
obtenemos c1 = 1 y c2 = 0 y (4) queda
xn =
„1
3
«n
Algoritmos y convergencia
Crecimiento exponencial
Con aritmetica de redondeo a cinco cifras, x0 = 1,0000 y x1 = 0,33333y para las constantes obtenemos c1 = 1,0000 y c2 = 0,12500× 10−5 y(4) queda
xn = 1,0000
„1
3
«n
− 0,12500× 10−5 3n
y por tanto el error de redondeo
xn − xn = 0,12500× 10−5 3n
crece exponencialmente.
Algoritmos y convergencia
Crecimiento lineal
Ejemplo: consideremos ahora la ecuacion en diferencias
xn = 2xn−1 − xn−2, para n = 2, 3, . . .
cuya solucion esta dada por
xn = c1 + c2n (5)
donde c1 y c2 son constantes que dependen de las “condicionesiniciales” x0 y x1.
Con x0 = 1 y x1 = 13
obtenemos c1 = 1 y c2 = − 23
y (5) queda
xn = 1− 2
3n
Algoritmos y convergencia
Crecimiento lineal
Ejemplo: consideremos ahora la ecuacion en diferencias
xn = 2xn−1 − xn−2, para n = 2, 3, . . .
cuya solucion esta dada por
xn = c1 + c2n (5)
donde c1 y c2 son constantes que dependen de las “condicionesiniciales” x0 y x1.
Con x0 = 1 y x1 = 13
obtenemos c1 = 1 y c2 = − 23
y (5) queda
xn = 1− 2
3n
Algoritmos y convergencia
Crecimiento lineal
Con aritmetica de redondeo a cinco cifras, x0 = 1,0000 y x1 = 0,33333y para las constantes obtenemos c1 = 1,0000 y c2 = 0,66667× 10−5 y(5) queda
xn = 1,0000− 0,66667n
y por tanto el error de redondeo
xn − xn =
„0,66667− 2
3
«n
crece linealmente.
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Definicion “O mayuscula”
Sea {βn} una sucecion tal que βn → 0 y {αn} una sucesion tal que αn → α.La sucecion {αn} converge a α con rapidez de convergencia O(βn) siexiste una constante K tal que
|αn − α| ≤ K|βn| , para n grande,
y en tal caso se acostumbra a escribir
αn = α+O(βn)
Por lo general βn =1
npcon p > 0.
Ejemplo: consideremos
αn =n+ 1
n2→ 0 y αn =
n+ 3
n3→ 0.
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Definicion “O mayuscula”
Sea {βn} una sucecion tal que βn → 0 y {αn} una sucesion tal que αn → α.La sucecion {αn} converge a α con rapidez de convergencia O(βn) siexiste una constante K tal que
|αn − α| ≤ K|βn| , para n grande,
y en tal caso se acostumbra a escribir
αn = α+O(βn)
Por lo general βn =1
npcon p > 0.
Ejemplo: consideremos
αn =n+ 1
n2→ 0 y αn =
n+ 3
n3→ 0.
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Definicion “O mayuscula”
Sea {βn} una sucecion tal que βn → 0 y {αn} una sucesion tal que αn → α.La sucecion {αn} converge a α con rapidez de convergencia O(βn) siexiste una constante K tal que
|αn − α| ≤ K|βn| , para n grande,
y en tal caso se acostumbra a escribir
αn = α+O(βn)
Por lo general βn =1
npcon p > 0.
Ejemplo: consideremos
αn =n+ 1
n2→ 0 y αn =
n+ 3
n3→ 0.
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Ambas sucesiones convergen a cero pero una lo hace mas “rapido” queotra: si
βn :=1
ny βn :=
1
n2,
entonces
|αn − 0| = n+ 1
n2≤ n+ n
n2= 2 · 1
n= 2βn =⇒ αn = 0 +O
„1
n
«
y
|αn − 0| = n+ 3
n3≤ n+ 3n
n3= 4 · 1
n2= 4βn =⇒ αn = 0 +O
„1
n2
«
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Ambas sucesiones convergen a cero pero una lo hace mas “rapido” queotra: si
βn :=1
ny βn :=
1
n2,
entonces
|αn − 0| = n+ 1
n2≤ n+ n
n2= 2 · 1
n= 2βn =⇒ αn = 0 +O
„1
n
«
y
|αn − 0| = n+ 3
n3≤ n+ 3n
n3= 4 · 1
n2= 4βn
=⇒ αn = 0 +O
„1
n2
«
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Ambas sucesiones convergen a cero pero una lo hace mas “rapido” queotra: si
βn :=1
ny βn :=
1
n2,
entonces
|αn − 0| = n+ 1
n2≤ n+ n
n2= 2 · 1
n= 2βn =⇒ αn = 0 +O
„1
n
«
y
|αn − 0| = n+ 3
n3≤ n+ 3n
n3= 4 · 1
n2= 4βn =⇒ αn = 0 +O
„1
n2
«
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Ambas sucesiones convergen a cero pero una lo hace mas “rapido” queotra: si
βn :=1
ny βn :=
1
n2,
entonces
|αn − 0| = n+ 1
n2≤ n+ n
n2= 2 · 1
n= 2βn =⇒ αn = 0 +O
„1
n
«
y
|αn − 0| = n+ 3
n3≤ n+ 3n
n3= 4 · 1
n2= 4βn =⇒ αn = 0 +O
„1
n2
«
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Definicion
Suponga lımh→0
G(h) = 0 y lımh→0
F (h) = L.
F (h) = L+O(G(h))
si existe una constante positiva K tal que
|F (h)− L| ≤ K|G(h)|, para h suficientemente pequeno.
Por lo general G(h) = hp con p > 0.
Ejemplo: al utilizar el tercer polinomio de Taylor de coseno,
cosh = 1− 1
2h2 +
1
24h4 cos ξ(h) (6)
con 0 < ξ(h) < h.
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Definicion
Suponga lımh→0
G(h) = 0 y lımh→0
F (h) = L.
F (h) = L+O(G(h))
si existe una constante positiva K tal que
|F (h)− L| ≤ K|G(h)|, para h suficientemente pequeno.
Por lo general G(h) = hp con p > 0.
Ejemplo: al utilizar el tercer polinomio de Taylor de coseno,
cosh = 1− 1
2h2 +
1
24h4 cos ξ(h) (6)
con 0 < ξ(h) < h.
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Definicion
Suponga lımh→0
G(h) = 0 y lımh→0
F (h) = L.
F (h) = L+O(G(h))
si existe una constante positiva K tal que
|F (h)− L| ≤ K|G(h)|, para h suficientemente pequeno.
Por lo general G(h) = hp con p > 0.
Ejemplo: al utilizar el tercer polinomio de Taylor de coseno,
cosh = 1− 1
2h2 +
1
24h4 cos ξ(h) (6)
con 0 < ξ(h) < h.
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Definicion
Suponga lımh→0
G(h) = 0 y lımh→0
F (h) = L.
F (h) = L+O(G(h))
si existe una constante positiva K tal que
|F (h)− L| ≤ K|G(h)|, para h suficientemente pequeno.
Por lo general G(h) = hp con p > 0.
Ejemplo: al utilizar el tercer polinomio de Taylor de coseno,
cosh = 1− 1
2h2 +
1
24h4 cos ξ(h) (6)
con 0 < ξ(h) < h.
Algoritmos y convergencia
Errores aritmeticos y de redondeo
De (6), ˛„cosh+
1
2h2
«− 1
˛=
˛1
24h4 cos ξ(h)
˛≤ 1
24h4 → 0
y por tanto
cosh+1
2h2 = 1 +O(h4)
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Algoritmos y convergencia
Errores aritmeticos y de redondeo
Algoritmos y convergencia
Errores aritmeticos y de redondeo