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:

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

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

Interpretação geométrica

Consideremos o problema de calcular a raiz de uma função ${\textstyle f,}$ conforme a figura ao lado.^[1][2][3][4]

Queremos calcular ${\textstyle x_{1}}$ em função de ${\textstyle x_{0},}$ sabendo que ${\textstyle x_{1}}$ será a cota no eixo das abcissas interceptado pela reta tangente à curva, originada por ${\textstyle x_{0}.}$

A equação da reta tangente ao gráfico da função ${\textstyle f}$ no ponto ${\textstyle (x_{0},f(x_{0})}$) tem inclinação ${\textstyle m=f'(x_{0})}$ e é dada por

Sabendo que essa reta passa por ${\textstyle (x_{1},0),}$ temos que Portanto, De modo geral, temos

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 ${\displaystyle \phi (x)}$ como:^[2][3][4]

${\displaystyle \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 ${\displaystyle \phi (x)}$ por Série de Taylor em torno de x* e obtemos:

${\displaystyle \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:

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

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

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

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

${\displaystyle \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:

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

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

Logo:

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

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

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

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

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

Com isso, observamos que o erro ${\displaystyle (\epsilon _{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:^[2][3][4][6]

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

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:

${\displaystyle 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 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:

${\displaystyle 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:

${\displaystyle 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 do vetor F(x), é a matriz formada pelas derivadas parciais das componentes de F(x):

${\displaystyle F'(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 ${\displaystyle 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:

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

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

${\displaystyle 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 ${\displaystyle F(x)=0}$, para ${\displaystyle 0,x\in \mathbb {R} ^{m},}$ podemos definir outra função

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

em que ${\displaystyle \cdot }$ denota o produto escalar usual.

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

${\displaystyle \min _{x}g(x)=0\Longleftrightarrow F(x)=0}$

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

Definindo a equação diferencial ordinária

${\displaystyle {\begin{cases}J_{F}(u(t))u'(t)&=&-F(u(t))\\u(0)&=&x_{0}\end{cases}}\qquad \qquad (*)}$,

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

${\displaystyle {\frac {d\,g(u(t))}{dt}}=-2g(u(t))}$.

Isso garante que ${\displaystyle g(u(t))}$ decresce, enquanto ${\displaystyle F(u(t))\neq 0}$, e que

${\displaystyle g(u(t))=e^{-2t}g(x_{0})}$.

O uso do método de Euler para determinar uma aproximação para ${\displaystyle u(t)}$, com tamanho de passo ${\displaystyle h=1}$, é equivalente ao método de Newton^[7].

Quando desconfiarmos que a matriz jacobiana ${\displaystyle J_{F}(x)}$ não possui inversa (em algum ponto), podemos usar a equação diferencial ${\displaystyle {\begin{cases}v'(t)&=&-\nabla g(v(t))\\v(0)&=&x_{0}\end{cases}},\qquad \qquad (**)}$

em que

${\displaystyle \nabla g(v(t))=J_{F}(v(t))^{*}F(v(t))}$,

e ${\displaystyle J_{F}(v(t))^{*}}$ denota a matriz transposta da matriz jacobiana ${\displaystyle J_{F}(v(t))}$.

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

Exemplos com uma variável

1. Neste exemplo,^[5] 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,^[5] 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,^[5] 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.^[8]

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.

Referências

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.