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
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
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)