Convergência


Dado um problema de solução z em Rn , e um método de solução que produz uma seqüência x0 , x1 , ... xk convergindo para a solucao, xk -> z, queremos estudar a velocidade com que | xk - z | -> 0.

 

Problema:Encontrar a raíz da função f(x) , z | f(z) = 0

 

1. Método da Bissecção:

f(a0) < 0, f(b0) > 0

ck = (ak + bk) / 2

If f(ck ) < 0

Then ak+1 = ck; bk+1 = bk; % z em [ck, bk]

Else ak+1 = ak; bk+1 = ck; % z em [ak, bk]

 

1.1 Convergência:

| z - ck | <= Ek = (bk - ak)

= (bk-1 - ak-1) / 2

= (b0 - a0) / 2n

 

2. Método de Newton

 

2.1 Série de Taylor:

Para uma função f suficientemente regular no intervalo [x, x+h], existem pontos médios m1, m2, m3 ... em [x,x+h] tais que
    1. f(x+h) = f(x) + h*f'(m1)
    2. f(x+h) = f(x) + h*f'(x) + (h2/2) * f''(m2)
    3. f(x+h) = f(x) + h*f'(x) + (h2/2) * f''(x) + (h3/3!) * f'''(m3)

Raíz z de f(x) em [a,b], z tal que f(z) = 0

f'(x) e f''(x) contínuas e de mesmo sinal

Idéia para nos aproximarmos da raíz z ~= x + h:

f(x+h) = 0 (de 2) => h = -f(x) / f'(x) + O(h2)

 

2.2 Algoritmo de Newton

    1. xk+1 = xk + hn onde hn = -f(xk) / f'(xk)

 

2.3 Convergência:

De (2) e (4) vem

f(xk+1) = (hn2 / 2) * f''(m) = ((f(x k) / f'(x k)) 2 / 2) * f''(m)

| f(xk+1) | <= (1/2) * (f''(m) / f'(x k)) 2 * f(xk)2

<= K1 * f(xk)2

Para um x0 próximo da raíz, f(xk) -> 0

Também xk -> z pois de (1)

f(x) = f(z) + f'(m) * (x - z) =>

(x - z) = f(x) / f'(m) =>

Para k >= N teremos | xk+1 - z | <= K2 * f(xk)