Demostracion

Convergencia Lineal y el algoritmo de bisecci´n o
Claudio Fern´ndez - Olga Funes a

1

Introducci´n o

El algoritmo de bisecci´n es usualmente el primer algoritmo presentado en un o curso de an´lisis num´rico para hallar ra´ a e ıces de una funci´n continua a valoo res reales definida en un intervalo de la recta real. Es bien conocido que las iteraciones producidas por este algoritmoconvergen a una ra´ y que puede ız calcularse el n´mero de iteraciones requeridas para asegurar un grado de preu cisi´n deseado. Es conveniente finalizar la discusi´n con un an´lisis del orden o o a de convergencia del algoritmo. Analizaremos las propiedades de convergencia del algoritmo de bisecci´n. o Supongamos que f ∈ C[0, 1] tiene una unica ra´ x en (0, 1) y f (0).f (1) < 0. El ´ ız algoritmo debisecci´n genera una sucesi´n de iterados xk de la siguiente mao o nera: sea x1 = 1/2, a1 = 0 y b1 = 1 y supongamos que hemos hallado xi , ai , bi para alg´n i ≥ 1. Entonces u (i) Si f (xi ) = 0, el algoritmo finaliza; (ii) Si f (ai ).f (xi ) < 0, sea xi+1 = (ai + xi )/2 = xi − (1/2)i+1 , ai+1 = ai y bi+1 = xi (fig.1) (iii) Si f (ai ).f (xi ) > 0, sea xi+1 = (bi + xi )/2 = xi + (1/2)i+1 , ai+1 = xi ybi+1 = bi (fig.2) El algoritmo finaliza cuando f (xn ) = 0 para alg´n n, o si la sucesi´n {xk }∞ u o k=1 1 k converge a x, en este caso |xk − x| ≤ ( 2 ) para todo k. Comparemos el orden de convergencia del algoritmo de bisecci´n con tres nociones diferentes de cono vergencia lineal que aparecen en la literatura.

16

geom´trica; esto es limk→∞ |ek |1/k < 1. e Para cada x ∈ (0, 1) existeninnumerables funciones f que satisfacen f (0).f (1) < 0 y para las que x es una ra´ simple. Por lo tanto, describiremos ız el orden de convergencia del algoritmo de bisecci´n para ciertos subconjuntos o del (0, 1) en lugar de las clases asociadas de funciones. En particular, para todo x ∈ (0, 1) para el cual el algoritmo de bisecci´n no finaliza, el algoritmo de o bisecci´n posee convergencia geom´tricaya que limk→∞ |ek |1/k = 1/2. En la o e pr´xima secci´n caracterizaremos aquellos x ∈ (0, 1) para los cuales el algoritmo o o de bisecci´n posee convergencia lineal. o

2

Propiedades de convergencia del algoritmo de bisecci´n o
k i i=2 si (1/2) ,

La k-´sima iteraci´n xk del algoritmo est´ dada por e o a xk = 1/2 +

donde cada si = 1 ´ −1. Esto motiva el siguiente teorema. o Teorema 2.1Todo x ∈ (0, 1) tiene una unica representaci´n de la forma ´ o x = k si (1/2)i si x = p/2k es un racional di´dico, ´, x = ∞ si (1/2)i a o i=1 i=1 si x no es un racional di´dico, donde s1 = 1 y si = 1 ´ −1 para i > 1. a o Demostraci´n: Es sabido que todo x ∈ (0, 1) tiene una unica representaci´n o ´ o binaria x = ∞ ci (1/2)i donde cada ci = 0 o 1 y no est´ permitido que a a i=1 partir de alg´n jlos ci = 1 para todo i ≥ j (de esta manera cualquier racional u di´dico p/2k puede ser expresado como una serie k ci (1/2)i ). El resultado a i=1 se sigue inmediatamente de reemplazar si+1 = 2ci − 1 para todo i. Ahora probaremos un lema el cual es la clave de nuestro principal resultado. Lema 2.2 Supongamos que el algoritmo de bisecci´n no finaliza en xk+2 o o antes, donde k ≥ 1. Supongamos tambi´nque sk+1 = sk+2 = sk+3 . Entonces e |ek+1 | > |ek |. Demostraci´n: Sin p´rdida de generalidad podemos asumir o e sk+1 = 1 y sk+2 = sk+3 = −1, 18

(ii) x es un n´mero racional de forma reducida p/(3.2k ) para enteros p > 0 u y k ≥ 0 si y s´lamente si el algoritmo de bisecci´n no finaliza y converge o o linealmente con factor de convergencia 1/2; (iii) x no tiene ninguna de las formas reducidasanteriores si y s´lamente si o el algoritmo de bisecci´n no finaliza, y no tiene convergencia lineal. o Demostraci´n: o (i) Supongamos que el algoritmo finaliza en xk . Entonces x = xk =
k i i=1 si (1/2)
k i=1

=

2k−i si 2k

= p/2k ,

donde p debe ser un entero impar. Por otro lado, supongamos que x = p/2k en forma reducida. Entonces por el Teorema 2.1 x tiene la representaci´n unica x =...