Usuário(a):3bach/Testes

Em análise numérica, o Método de Newton (ou Método de Newton-Raphson), desenvolvido por Isaac Newton e Joseph Raphson, tem o objetivo de estimar as raízes de uma função. Para isso, escolhe-se uma aproximação inicial para esta. Após isso, calcula-se a equação da reta tangente (derivada) da função nesse ponto e a interseção dela com o eixo das abcissas, a fim de encontrar uma melhor aproximação para a raiz. Repetindo-se o processo, cria-se um método iterativo para encontramos a raiz da função. Em notação matemática, o Método de Newton é representado da seguinte forma:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$,

onde n indica a n-ésima iteração do algoritmo e f'(x_n) é a derivada da função f em x_n.

Para que se obtenha sucesso na iteração, devemos respeitar a seguinte condição:

• A função f deve ser diferenciável em x_n e seu valor deve ser não nulo;

Exemplos

1) Neste exemplo, mostraremos porque a função f deve ser diferenciável em x_n. Considere a função f(x)=|x-3|-1. Essa função possui uma cúspide no ponto (3,-1); portanto, f não é diferenciável nesse ponto. Analisando o gráfico dessa função, percebemos que x=2 e x=4 são suas raízes. Caso iniciemos o Método de Newton com x=3, o processo iterativo falhará porque a derivada de f em x=3 não é definida.

2) Neste exemplo, mostraremos porque a função f deve ter derivada não nula em x_n. Considere a função f(x)=x²-1. Essa função possui uma reta tangente horizontal no ponto (0,-1); portanto, a derivada de f em x=0 é nula. Como a reta tangente é horizontal, logo ela nunca interceptará o eixo das abcissas e, assim, o Método de Newton falhará, pois ocorrerá uma indeterminação matemática (divisão por zero).

Demonstração do Método de Newton

Consideremos o problema de calcular a raiz de uma função f, conforme a figura ao lado.

As três primeiras iterações do método de Newton.

Queremos calcular x₁ em função de x₀, sabendo que x₁ será a cota no eixo das abcissas interceptado pela reta tangente à curva, originada por x₀.

A equação da reta que passa por (x₀,f(x₀)) e é tangente à curva em (x₀,f(x₀)) tem inclinação m=f'(x₀) e sua equação é:

$y-f(x_{0})=f'(x_{0})(x_{n}-x_{0})$

Sabendo que essa reta passa por (x₁,0), temos que:

$0-f(x_{0})=f'(x_{0})(x_{1}-x_{0})$

Portanto,

$x_{1}=x_{0}-{\frac {f(x_{0})}{f'(x_{0})}}$

De modo geral, teremos:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$

Análise de Convergência

Devemos ter em mente que se a condição estabelecida na introdução for satisfeita, o Método de Newton poderá não convergir para a raiz. Seja f(x) uma função e sua derivada diferente de zero. Seja uma função $\phi (x)$ definida como:

$\phi (x)=x-{\frac {f(x)}{f'(x)}}$

Consideramos x* uma aproximação da solução x de f(x)=0 tal que f'(x*)≠0 e |x – x*| seja “pequeno”. Expandimos em Série de Taylor em torno de x* e obtemos:

$\phi (x)=\phi (x^{*})+(x-x^{*})\phi (x^{*})+{\frac {(x-x^{*})^{2}}{2}}\phi ''(x^{*})+O((x-x^{*})^{3})$

Para a dedução do Método de Newton, vamos supor que |x - x*| é pequeno, logo, o termo (x - x*)² será muito menor. Com isso, dizemos que:

$0\approx \phi (x^{*})+(x-x^{*})\phi (x^{*})$

Sabemos que:

$\phi (x^{*})=x^{*}-{\frac {f(x^{*})}{f'(x^{*})}}=x^{*}$

$\phi '(x^{*})=1-{\frac {f'(x^{*})f'(x^{*})-f(x^{*})f''(x^{*})}{(f'(x))^{2}}}=1-1=0$

$\phi ''(x^{*})={\frac {(f'(x^{*})f''(x^{*})+f(x^{*})f'''(x^{*}))(f'(x^{*}))^{2}-2f(x^{*})f''(x^{*})f'(x^{*})}{(f'(x^{*}))^{4}}}={\frac {f''(x^{*})}{f'(x^{*})}}$

Portanto:

$\phi (x)=x^{*}+(x-x^{*})^{2}{\frac {\phi ''(x^{*})}{2}}+O((x-x^{*})^{3})$

$\phi (x)\approx x^{*}+(x-x^{*})^{2}{\frac {\phi ''(x^{*})}{2}}$

Logo:

$x_{n+1}=\phi (x_{n})$

$x^{*}+(x_{n}-x^{*})^{2}{\frac {\phi ''(x^{*})}{2}}$

$(x_{n+1}-x^{*})\approx (x_{n}-x^{*})^{2}{\frac {\phi ''(x^{*})}{2}}$

Considerando (x_n - x*) o erro absoluto, obtemos:

$\epsilon _{n+1}\approx \epsilon ^{2}{\frac {\phi ''(x^{*})}{2}}={\frac {1}{2}}|{\frac {f''(x^{*})}{f'(x^{*})}}|\epsilon _{n}^{2}$

Com isso, observamos que o erro $(\epsilon )$ é de ordem quadrática. Quando $\epsilon <1$, teremos uma convergência rápida. De modo geral, quando $\epsilon >=1$, o Método de Newton poderá convergir, mas a convergência será lenta. Considere a função f(x)=sen(x), se arbitrarmos x₀=10,85 rad, valor relativamente distante da primeira raiz x=π rad, o Método de Newton convergirá para a raiz rapidamente. Isso mostra que a primeira aproximação da raiz deve, preferencialmente, ser um valor próximo da raiz, mas existe casos em que essa aproximação é distante da raiz e mesmo assim o método converge.

Generalização do Método de Newton

Percebemos que o Método de Newton é uma poderosa ferramenta para resolvermos equações de uma variável (f(x)=0). Esse método, contudo, pode ser utilizado em problemas mais complexos, como na solução de equações do tipo Ax=b, em que x e b são vetores e A é uma matriz. Queremos, portanto, generalizar o Método de Newton para resolvermos um sistema de equações da forma:

$f_{1}(x_{1},x_{2},...,x_{n})=0$

$f_{2}(x_{1},x_{2},...,x_{n})=0$

$f_{3}(x_{1},x_{2},...,x_{n})=0$

$\vdots$

$f_{n}(x_{1},x_{2},...,x_{n})=0$

Podemos analisar esse sistema de equações na forma vetorial, definindo o vetor e o vetor F(x) tal que

$F(x)={\begin{bmatrix}f_{1}(x_{1},x_{2},...,x_{n})\\f_{2}(x_{1},x_{2},...,x_{n})\\\vdots \\f_{n}(x_{1},x_{2},...,x_{n})\end{bmatrix}}$

Para resolvermos o problema de uma variável (f(x)=0), nós expandíamos a função f(x) em torno de x* por sua Série de Taylor de modo a obtermos $f(x)\approx f(x^{*})+(x-x^{*})f'(x^{*})$, sendo x* uma aproximação para a solução de f(x)=0 . De modo equivalente, o problema matricial se resume a resolver e equação F(x)=0 e devemos expandir a função F(x) em torno de x*, sendo x* uma aproximação para a solução de F(x)=0. Efetuando-se essa expansão, obteremos $F(x)\approx F(x^{*})+(x-x^{*})F'(x^{*})$. Portanto, será necessário definirmos a derivada de F(x). Definimos, então, a Matriz Jacobiana por:

$J_{F}={\begin{bmatrix}{\frac {\partial f_{1}}{\partial x_{1}}}&\cdots &{\frac {\partial f_{1}}{\partial x_{n}}}\\\vdots &\ddots &\vdots \\{\frac {\partial f_{m}}{\partial x_{1}}}&\cdots &{\frac {\partial f_{m}}{\partial x_{n}}}\end{bmatrix}}$

E percebemos que a matriz jacobiana, ou o Jacobiano da função F(x), é a matriz formada pelas derivadas parciais de F(x):

$F'(x)=(J_{F})_{ij}={\frac {\partial f_{i}}{\partial x_{j}}}$

Logo, podemos reescrever a expansão em Série de Taylor de F(x) como $F(x)\approx F(x^{*})+(x-x^{*})J_{F}(x^{*})$. Também de acordo com o problema de uma variável, tínhamos que o Método de Newton era dado pela iteração:

$x_{n+1}=x_{n}-{\frac {f(x_{n})}{f'(x_{n})}}$

Consequentemente, em problema envolvendo sistemas lineares, teremos que o Método de Newton será dado pela iteração:

$x_{n+1}=x_{n}-{\frac {F(x_{n})}{J_{F}(x_{n})}}$

Referências

1. Howard Anton, Irl Bivens, Stephen Davis, Cálculo Volume 1, Bookman, 8° ediçao.
2. Richard L. Burden, J. Douglas Faires, Análise Numérica, CENGAGE Learning, 8° ediçao.

Ligações externas

• Roots of a function - Rosetta Code - implementações em diversas linguagens de programação
• Análise Numérica
• Algorítimo