Método de Newton–Raphson

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 (por meio da derivada) ao gráfico 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 encontrarmos a raiz da função. Em notação matemática, o método de Newton é dado pela seguinte sequência recursiva:

$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)},n\in \mathbb{N}$

onde $x_0$ é uma aproximação inicial dada, $n$ indica a $n$-ésima iteração do algoritmo e $f^{\prime }(x_n)$ é a derivada da função $f$ no ponto $x_n.$

Interpretação geométrica

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_1$ em função de $x_0,$ sabendo que $x_1$ será a cota no eixo das abcissas interceptado pela reta tangente à curva, originada por $x_0.$

A equação da reta tangente ao gráfico da função $f$ no ponto $(x_0,f(x_0)$) tem inclinação $m=f^{\prime }(x_0)$ e é dada por $$y-f(x_0)=f^{\prime }(x_0)(x-x_0)$$ Sabendo que essa reta passa por $(x_1,0),$ temos que $$0-f(x_0)=f^{\prime }(x_0)(x_1-x_0).$$ Portanto, $$x_1=x_0-\frac{f(x_0)}{f^{\prime }(x_0)}.$$ De modo geral, temos $$x_{n+1}=x_n-\frac{f(x_n)}{f^{\prime }(x_n)}.$$

Análise de convergência

Devemos ter em mente que, mesmo 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, definimos uma função $\varphi (x)$ como:

$\varphi (x)=x-\frac{f(x)}{f^{\prime }(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 $\varphi (x)$ por Série de Taylor em torno de x* e obtemos:

$\varphi (x)=\varphi (x^{*})+(x-x^{*}){\varphi }^{\prime }(x^{*})+\frac{(x-x^{*}{)}^2}{2}{\varphi }^{″}(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:

$\varphi (x)\approx \varphi (x^{*})+(x-x^{*}){\varphi }^{\prime }(x^{*})$

Pelo processo iterativo do método do ponto fixo, sabemos que:

$\varphi (x^{*})=x^{*}-\frac{f(x^{*})}{f^{\prime }(x^{*})}=x^{*}$

${\varphi }^{\prime }(x^{*})=1-\frac{f^{\prime }(x^{*})f^{\prime }(x^{*})-f(x^{*})f^{″}(x^{*})}{(f^{\prime }(x){)}^2}=1-1=0$

${\varphi }^{″}(x^{*})=\frac{(f^{\prime }(x^{*})f^{″}(x^{*})+f(x^{*})f^{‴}(x^{*}))(f^{\prime }(x^{*}){)}^2-2f(x^{*})f^{″}(x^{*})f^{\prime }(x^{*})}{(f^{\prime }(x^{*}){)}^4}=\frac{f^{″}(x^{*})}{f^{\prime }(x^{*})}$

Portanto:

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

$\varphi (x)\approx x^{*}+(x-x^{*}{)}^2\frac{{\varphi }^{″}(x^{*})}{2}$

Logo:

$x_{n+1}=\varphi (x_n)$

$x^{*}+(x_n-x^{*}{)}^2\frac{{\varphi }^{″}(x^{*})}{2}$

$(x_{n+1}-x^{*})\approx (x_n-x^{*}{)}^2\frac{{\varphi }^{″}(x^{*})}{2}$

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

${ϵ}_{n+1}\approx {ϵ}_n^2\frac{{\varphi }^{″}(x^{*})}{2}=\frac{1}{2}|\frac{f^{″}(x^{*})}{f^{\prime }(x^{*})}|{ϵ}_n^2$

Com isso, observamos que o erro $({ϵ}_n)$ é de ordem quadrática e, por isso, a iteração convergirá rapidamente para a raiz da função.

Generalização

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:

$$\begin{array}{ccc}{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\\ & ⋮& \\ f_n(x_1,x_2,...,x_n)& =& 0\end{array}$$

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

$$F(x)=\left[\begin{array}{c}{f}_1(x_1,x_2,...,x_n)\\ f_2(x_1,x_2,...,x_n)\\ ⋮\\ f_n(x_1,x_2,...,x_n)\end{array}\right]$$

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^{\prime }(x^{*}),$

sendo x* uma aproximação para a solução de f(x)=0 . De modo equivalente, o problema matricial se resume a resolver a 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^{\prime }(x^{*})$

Portanto, será necessário definirmos a derivada de F(x). Definimos, então, a Matriz Jacobiana por:

$J_F=\left[\begin{array}{ccc}\frac{\partial f_1}{\partial x_1}& \cdots & \frac{\partial f_1}{\partial x_n}\\ ⋮& \ddots & ⋮\\ \frac{\partial f_m}{\partial x_1}& \cdots & \frac{\partial f_m}{\partial x_n}\end{array}\right]$

E percebemos que a Matriz Jacobiana, ou o Jacobiano do vetor F(x), é a matriz formada pelas derivadas parciais das componentes de F(x):

$F^{\prime }(x)=(J_F{)}_{ij}=\frac{\partial f_i}{\partial x_j}$

Logo, podemos reescrever a expansão por 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^{\prime }(x_n)}$

Consequentemente, em problemas envolvendo sistemas de equações, teremos que o método de Newton será dado pela iteração:

$x_{n+1}=x_n-J_F^{-1}(x_n)F(x_n)$

Problemas de otimização

O método de Newton pode ainda ser visto da seguinte forma:

Se $F(x)=0$, para $0,x\in {ℝ}^m,$ podemos definir outra função

$g(x)=\frac{\Vert F(x){\Vert }^2}{2}=\frac{F(x)\cdot F(x)}{2}$,

em que $\cdot$ denota o produto escalar usual.

Então o valor mínimo de $g(x)$ é $0$, ou seja,

$\underset{x}{\min }g(x)=0⟺F(x)=0$

e a equação $F(x)=0$ pode ser resolvida como um problema de otimização.

Definindo a equação diferencial ordinária

$\{\begin{array}{ccc}{J}_F(u(t))u^{\prime }(t)& =& -F(u(t))\\ u(0)& =& x_0\end{array}(*)$,

pode-se mostrar, sob certas condições, que a única solução $u(t)$ dessa equação $(*)$ é tal que

$\frac{dg(u(t))}{dt}=-2g(u(t))$.

Isso garante que $g(u(t))$ decresce, enquanto $F(u(t))\ne 0$, e que

$g(u(t))=e^{-2t}g(x_0)$.

O uso do método de Euler para determinar uma aproximação para $u(t)$, com tamanho de passo $h=1$, é equivalente ao método de Newton.

Quando desconfiarmos que a matriz jacobiana $J_F(x)$ não possui inversa (em algum ponto), podemos usar a equação diferencial $\{\begin{array}{ccc}{v}^{\prime }(t)& =& -\mathrm{\nabla }g(v(t))\\ v(0)& =& x_0\end{array},(**)$

em que

$\mathrm{\nabla }g(v(t))=J_F(v(t){)}^{*}F(v(t))$,

e $J_F(v(t){)}^{*}$ denota a matriz transposta da matriz jacobiana $J_F(v(t))$.

Nesse caso, pode-se mostrar que $g(v(t))$ também é decrescente, enquanto $F(v(t))\ne 0$; e uso do método de Euler para determinar uma aproximação a solução $v(t)$ (da equação $(**)$) é equivalente ao método do gradiente.

Exemplos com uma variável

1. Neste exemplo, mostraremos porque a função f deve ser diferenciável em x_n, para a satisfazer a condição inicial. Considere a função f(x)=|x-3|-1. Essa função possui uma cúspide em (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 em (0,-1); portanto, a derivada de f nesse ponto é 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).
3. Neste exemplo, mostraremos que mesmo escolhendo-se uma aproximação x₀ distante da real raiz da função f, o método de Newton ainda assim poderá convergirá rapidamente para a solução de f(x)=0. 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 convergirá para essa raiz rapidamente.

Isso mostra que a primeira aproximação da raiz não necessita ser um valor próximo dela. Existem casos em que essa aproximação é distante da raiz e mesmo assim o método converge, conforme mostrado no exemplo acima.

Considerações sobre o método

O método de Newton é considerado por muitos autores o melhor método para encontrar sucessivas melhores aproximações de raízes (ou zeros) de uma determinada função real e, portanto, tem sido estudado e utilizado em diversos ramos da ciência (Matemática, Física, Engenharia), sendo também muito utilizado na resolução de sistemas não lineares. Além disso, esse método tem sido alvo de novos estudos e aprimoramentos. Em 1984, Allan J. Macleod mostrou, num artigo da International Journal of Mathematical Education in Science and Technology, que o método iterativo de Newton–Raphson para equações não lineares pode ser considerado um membro da família geral de um parâmetro de métodos de segunda ordem.

Um ponto importante a ser observado diz respeito a praticidade do método de Newton. Caso a função f seja complicada, encontrar sua derivada pode ser muito trabalhoso e o método torna-se improdutivo. Nesses casos, o método das secantes é mais produtivo de ser utilizado, porque não exige que a derivada de f seja conhecida.

Ligações externas

• Roots of a function - Rosetta Code - implementações em diversas linguagens de programação
• Cálculo Numérico - Um Livro Colaborativo - seção sobre o método de Newton para resolver equações algébricas no livro de Cálculo Numérico mantido pelo Instituto de Matemática e Estatística da Universidade Federal do Rio Grande do Sul.
• Cálculo Numérico - Um Livro Colaborativo - seção sobre o método de Newton para resolver sistemas de equações algébricas no livro de Cálculo Numérico mantido pelo Instituto de Matemática e Estatística da Universidade Federal do Rio Grande do Sul.

Predefinição:Isaac Newton Predefinição:Authority control