algoritmo y convergencia

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