Primeiro uma forma de calcular a raiz quadrada de um número $M$ usando o método de Newton. Neste caso queremos encontrar a raiz positiva da equação $$ x^2 -M =0 $$ Fazendo $f(x) = x^2 - M$ e usando o método de Newton para achar o zero desta função obtemos a sequência: $$ x_{n+1} = \frac{1}{2}\left(x_n +\frac{M}{x_n}\right)$$
a função $f(x) = \text{sgn}(x-1)\sqrt{(x-1)}$ tem, evidentemente uma única raiz em $r=1.0$ e é derivável em todos os pontos diferentes de $1.0$. A sequência produzida pelo método de Newton é: $$ x_{n+1} = -x_n + 2 $$ Note que $x_{n+2} = -(x_{n+1})+2 = x_n -2 +2 = x_n$. A sequência tem período $2$, portanto não converge. Faremos o grafico desta função.
%matplotlib inline
from matplotlib.pyplot import plot # gosto de usar a função plot
import numpy as np
x=np.arange(0,2,0.001)
# defino a função:
def f(x):
return np.sign(x-1)*sqrt(abs(x-1))
plot(x,f(x))
grid()
O método de Newton é, em geral, bastante eficiente e utilizado. Além disso é um caso especial de uma família de métodos para se encontrar o zero de uma função chamado método do ponto fixo. Seja $\Phi:[a,b] \to \mathbb{R}$ uma função. Um ponto $x_f\in [a,b]$ será chamado de ponto fixo de $\Phi$ se ele satisfaz $\Phi(x_f) = x_f$. Note que se a função $\Phi : [a,b] \to [a,b]$ puder ser iterada (composta com ela mesma), então $\Phi(\Phi(x_f))= \Phi(x_f) = x_f$. De forma geral $\Phi^n(x_f)=x_f$. Desta forma, se definirmos a sequência $x_n = \Phi^n(x_0)$, para algum $x_0\in [a,b]$ e $\Phi$ contínua, e ela convergir para algum ponto $x_f$, este será um ponto fixo de $\Phi$.
Suponha que valham as seguintes hipóteses:
Neste caso a sequência $x_n = \Phi^n(x0)$ converge para um único ponto $x_f$ em $[a,b]$, para qualquer $x_0$.
def PontoFixo(phi,x0,epsilon,N):
"""Procura um ponto fixo da função Phi por iteração.
o- começa em x0
o- com precisao |xnew-xold| menor que epsilon
o- para depois de N iterações"""
xnew = phi(x0)
xold = x0
iteracao = 0
while (iteracao <= N) and (abs(xnew-xold)>epsilon):
xnew, xold = phi(xnew), xnew
iteracao = iteracao + 1
print("{0:>3} | {1} ".format(iteracao,xnew))
return xnew
f = lambda x : 0.5*(x+2./x)
f(1.42)
1.414225352112676
PontoFixo(f,3, 0.00001,10)
1 | 1.4621212121212122 2 | 1.414998429894803 3 | 1.4142137800471977 4 | 1.4142135623731118
1.4142135623731118
%pastebin '