Dada uma função $f:I\to \mathbb{R}$ contínua, queremos encontrar um elemento $x\in I$ tal que $f(x)=0$. Se encontramos $a,b$ tais que $f(a)f(b)\lt 0$, podemos garantir a existência de, pelo menos, uma raiz da equação (por causa da continuidade). Determinar um intervalo onde exista uma única raiz não é tão simples e requer mais regularidade da função $f$.
O algoritmo mais simples para se encontrar esta solução é ir repartindo o intervalo ao meio. Testando de que lado está a raiz, e repetir o processo até que o tamanho do intervalo. Podemos descrever este algoritmo assim:
O algoritmo em python pode ser:
def dicotomia(f,a,b,n):
""" Calcula a raiz de f(x)=0 usando o método da dicotomia
a: inicio do intervalo
b: fim do intervalo
n: numero de iterações """
# por uma mensagem de erro depois se f(a)*f(b)>=0
if f(a)*f(b)>= 0:
raise ValueError( "f(a) e f(b) têm mesmo sinal" )
raiz = (a+b)/2
for i in range(n):
if f(a)*f(raiz) < 0:
a,b = a,raiz
else : a,b = raiz,b
raiz =(a+b)/2
return raiz
f = lambda x : (x-1)**3
print(f(0),f(5))
-1 64
dicotomia(f,0,5, 10)
0.99853515625
dicotomia(f,2,4,10)
--------------------------------------------------------------------------- ValueError Traceback (most recent call last) <ipython-input-4-584a7602291b> in <module>() ----> 1 dicotomia(f,2,4,10) <ipython-input-1-294d71ef7606> in dicotomia(f, a, b, n) 6 # por uma mensagem de erro depois se f(a)*f(b)>=0 7 if f(a)*f(b)>= 0: ----> 8 raise ValueError( "f(a) e f(b) têm mesmo sinal" ) 9 raiz = (a+b)/2 10 for i in range(n): ValueError: f(a) e f(b) têm mesmo sinal
O erro inicial no método da dicotomia é $|x_1-x_r|\leq |b-a|/2$. A cada passo a estimativa desse erro é dividida por 2, assim $|x_n-x_r|\leq |b-a|/2^n$.
Agora $f: [a,b] \to \mathbb{R}$ é uma função diferenciável com um único zero neste intervalo. Podemos produzir uma sequência de estimativas $x_n$ deste zero, baseado na aproximação linear da função $f$, ou de seu polinômio de primeira ordem.
Suponha que $x_e$ seja uma estimativa do zero que queremos melhorar. A série de Taylor em torno de $x_e$ é
$$ f(x) = f(x_e) + f^\prime(x_e)(x-x_e) + O(|x-x_e|^2)$$se fizermos $f(x)=0$, e desprezarmos o $o(|x-x_e|^2)$ temos
$$ 0 = f(x_e) + f^\prime(x_e)(x_n - x_e)$$sendo $x_n$ a nova estimativa. Resolvendo para $x_n$ temos:
$$ x_n = x_e - \frac{f(x_e)}{f^\prime(x_e)} $$e esta relação é a base do método de Newton.
da mesma forma que anteriormente, produzimos uma sequência de estimativas, escolhendo um $x_0$ arbritário e, a partir dele, calculando
$$x_{k+1} = x_k - \frac{f(x_k)}{f^\prime(x_k)} $$E esperemos que esta sequência convirja!!
from math import *
def met_Newton(f,flinha,x0,epsilon):
x1=x0 - f(x0)/flinha(x0)
erro = max(abs(x1-x0),abs(f(x1)))
while erro > epsilon:
x0=x1
x1=x0 - f(x0)/flinha(x0)
erro = max(abs(x1-x0),f(x1))
return x1
g= lambda x: (x-1.)*(x-5.)**2
glinha = lambda x: (x-5.)**2 + 2.*(x-1)*(x-5)
met_Newton(g,glinha,1.5,0.00001)
0.9999999999999999