Método de Newton-Raphson

Teoria Completa

Introdução

Fala meu amigo, tudo certinho ? Nós tivemos um tópico bem bacana só pra explicar o método do PONTO FIXO que basicamente consistia em :

E isso tudo acontecia através da chamada função de iteração. Até aí tudo ok né? E onde é que entra o método de NEWTON-RAPHSON ? Ele é um método de ponto fixo, deeeer! Vamos enteder o porquê :

Vimos no Método do Ponto Fixo que a convergência do método será mais rápida quanto menor for g ' p , onde p é ponto fixo de g x .

O método de Newton-Raphson é um método do ponto fixo que utiliza uma técnica diferente pra refinamento. O que ele faz é escolher uma função de iteração g x tal que g ' p = 0 ! Ou seja, ela minimiza o valor da função de iteração no ponto fixo, acelerando a convergência do MPF.

Método de Newton

Existem algumas abordagens possíveis para chegarmos ao método de Newton. Mas vamos focar na função iteração e como usá-la para convergir até a raiz do problema (ξ) :

Basicamente, o método de Newton-Raphson busca garantir e acelerar a convergência do Método do Ponto Fixo, escolhendo para função de iteração: g ( x ) tal que g ’( ξ ) = 0.

E como calculamos isso matematicamente? Usando a seguinte função de iteração:

g x k = x - f x k f ' x k

Pensando em termos de funções que funcionam por iteração e que cada método depende do anterior. A nossa sequência de iteração será:

x k + 1 = x k - f x k f ' x k

Além disso, existe um teorema que diz algo assim: “No intervalo [a, b] deve conter a raiz x = ξ de f x = 0 . Se a derivada dessa função f ’ (ξ) ≠ 0. Então, a raiz ξ estará dentro do intervalo, que vai convergir ao valor real por meio de iterações de sequências { x k } gerada pela fórmula”.

Geralmente o método de Newton converge desde que nosso palpite inicial ( x 0 ) seja escolhido “suficientemente próximo” da raiz ξ , satisfazendo as hipóteses de convergência do MPF.

O método de Newton também pode ser obtido geometricamente. Dado o ponto x k , f x k , traçamos a reta L k x tangente à curva neste ponto. A fórmula da reta tangente é dada por:

L k x = f x k + f ' x k x - x k

Essa reta L k x funciona como uma aproximação para a função f x na vizinhança de x k . Ou seja, quanto mais próximo de x k estivermos, melhor a reta tangente aproxima a própria função.

E como nosso chute x k deve estar próximo da raiz de f x , consideramos a aproximação L k x como uma aproximação boa o suficiente para encontrar o zero de f x e fazemos:

L k x = f x k + f ' x k x - x k = 0

x k + 1 = x k - f x k f ' x k

Basta fazermos x k + 1 = x e chegamos na nossa fórmula de novo. Ficamos com algo desse tipo:

Basicamente, aplicamos os critérios de convergência e iteração até que o valor de x atenda ao critério de parada!

Beleza, nós já vimos qual a função de iteração desse método, e como ele é uma derivação do MPF, ele necessita exatamente das mesmas coisas! Ele precisa de um chute inicial e o critério de parada será:

x k + 1 - x k < ε

E, novamente, outro critério usado é:

f x k < ε

Bora por a mão na massa e calcular!!!!!

Para testar a velocidade desse método vamos usar aquele exemplo lá de trás do método da Bisseção. Calcular o zero da função   f x = ( x - 2 ) 2 - ln ⁡ x   usando ε = 10 - 6

A primeira coisa que podemos fazer é montar uma tabelinha marota toooodas as informações que precisamos: o número k de iterações (que vai de 0 até n), os valores de x k , e o valor da nossa função f x k , o valor da derivada f ' x k , x k + 1 e pra completar ... o critério de parada né! Fica com essa carinha:

Agora, vou ensinar como se completa a tabela: Sempre começamos em k=0, já que não foi feita nenhuma iteração antes dessa.

Temos uma raiz no intervalo 1,2 , então vamos usar x 0 = 1 .

Primeiro: podemos calcular o valor da função no ponto x 0 = 1 . Se nossa função é:

f x = ( x - 2 ) 2 - ln ⁡ x

No ponto x 0 = 1 :

f x = ( 1 - 2 ) 2 - ln ⁡ 1 = 1

Cálculos Iniciais

f ' x = 2 x - 2 - 1 x

g x = x k + 1 = x k - f x k f ' x k =   x k -   ( x - 2 ) 2 - ln ⁡ x 2 x - 2 - 1 x

x 0 = 1

ε = 10 - 6

Mas não se estresse ta ok? Quando jogarmos as informações na tabela vai ficar bem mais fácil de enxergar e até de calcular essa monstruosidade toda que chamamos de   g x . Então vamos só calcular na mão as 2 primeiras iterações e o resto vou te mostrar como faz usando a tabelinha! Bora lá?

Iteração 1 :

x 1 = g x 0 = 1.333

Critério de Parada:

x 1 - x 0 = 0.333333 > 10 - 6

f x 1 = 0,15683 > 10 - 6

Como não alcançamos o critério de parada, continuamos as iterações.

x 1 = 1.333

ε = 10 6

Iteração 2 :

x 2 = g x 1 = 1,40857

Critério de Parada:

x 2 - x 1 = 0.07557 > 10 - 6

f x 2 = 0.007214 > 10 - 6

Como não alcançamos o critério de parada continuamos as iterações. Pra não cansar a nossa beleza e facilitar nossa organização e vida, vamos jogar naquela tabelinha linda todas as informações que precisamos:

Vamos dar uma analisada na tabela: perceba que quando organizamos as informações assim a lá Edward mãos de tesoura fazendo por partes.

Note que pra calcular x k + 1 fica bem mais fácil quando só jogamos os valores dentro da fórmula. Legal né?

x k + 1   = x k - f x k f ' x k

CARACA! Quatro iterações cara! Sabe o que são 4 iterações? Pra uma precisão de 10 - 6 ?! Pra você ter uma ideia no método da bisseção íamos precisar de 20 iterações pra chegar nisso! Ou seja, todos nós devemos MUITO ao Newton e ao nosso parceiro Raphson, não podemos esquecer do coitado.

Algoritmo

Vamos lá, vou deixar mastigadinho pra vocês:

Passo 1. Dados iniciais (o que seu programa vai receber de você):

a. Aproximação inicial x 0

b. Precisão do resultado final ε 1 e ε 2

Passo 2. Definimos um contador de iterações k = 0 .

Passo 3. Se f x 0 < ε 1 , escolha x 0 como x - e FIM. Caso contrário, continue para o Passo 4.

Passo 4. k = k + 1 , aumentamos uma iteração no contador.

Passo 5. x = g x 0

Passo 6. Se x - x 0 < ε 2 , escolha x como x - e FIM. Caso contrário continue para o Passo 7.

Passo 7. x 0 = x

Passo 8. Voltamos para o Passo 3 .

Como sempre, um bom critério de parada para se adicionar também é um número máximo de iterações.

Percebeu alguma coisa? Sim, é exatamente o mesmo algoritmo do MPF! Mas já era de se esperar né!? Eles são o mesmo método, Newton só nos deu uma forma fixa (e boa pacas) de calcular o g x . Ou seja, para cada função que você quiser aplicar esse método (assim como no MPF) você tem que calcular a derivada e definir a g x e a f x como alguma função no seu programa ;)

Estudo da Convergência

Beleza, e quando que esse método converge? Não adianta nada o negócio ser super poderoso e ser difícil convergir né? Bom, temos um teorema especial só para ele:

Sejam f x , f ' x e f ' ' x contínuas em um intervalo a , b que contém p , tal que f p = 0 e f ' p ≠ 0 . Então existe um intervalo I centrado em p que converge para p para qualquer aproximação inicial x 0 ∈ I .

Ou seja, para uma aproximação suficientemente próxima da raiz, se as condições acima forem satisfeitas, o método vai convergir. A parte do suficientemente próxima é meio subjetiva, já que algumas funções convergem para qualquer valor que for dado (por exemplo, um chute inicial de x 0 = 999999 poderia convergir para uma raiz p = 0 ), enquanto outras convergem apenas em um intervalo restrito de algumas unidades.

Observações

Deu pra perceber que esse método é mega poderoso né? Ele é extremamente rápido se for escolhida uma boa aproximação inicial.

Mas como nada é perfeito, ele também tem uma desvantagem. O cálculo da Derivada! Em alguns casos o cálculo da derivada é bem complicado, e a função que obtemos pode ser bem grande, então encontrar o seu valor numérico a cada iteração pode dar um belo trabalho =/

Além disso o método continua bem mais limitado que o da bisseção por exemplo, tendo condições mais específicas para sua convergência.

Logo, dentre os métodos, o Método de Newton é o mais indicado sempre que for fácil verificar as condições de convergência de  f ( x )  e que o cálculo de sua derivada não seja muito elaborado.

Expandir

Exercício Resolvido #1

Richard L. Burden e J. Douglas Faires, Numerical Analysis, 9ª ed. Brooks/Cole, Cengage Learning, pag 75, exercício 2 adaptado

Seja f x = - x 3 - cos ⁡ x e x 0 = - 1 . Use o Método de Newton para encontrar x 2 . O valor x 0 = 0 poderia ser usado?

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Só aplicar o algoritmo:

Cálculos Iniciais

f ' x = - 3 x 2 + sin ⁡ x

g x = x + x 3 + cos ⁡ x - 3 x 2 + sin ⁡ x

x 0 = - 1

x 1 = g x 0 = - 0.88033

x 2 = g x 1 = - 0.86568

Taí o nosso x 2 .

A próxima pergunta é, x 0 = 0 poderia ser usado? Não poderia pois a derivada nesse ponto vale 0 :

f ' 0 = - 3 0 2 + sin ⁡ 0 = 0

Isso nos criaria uma indeterminação na nossa função de iteração.

Resposta

x 2 = - 0.86568 .

Não poderia pois criaria uma indeterminação na nossa função de iteração.

Exercício Resolvido #2

Lista 2 – Professor Mauro – UFRJ – Questão 2

Dê um exemplo de função f x , que tenha pelo menos uma raiz, onde o Método de Newton-Raphson não converge sempre.

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

-

Um exemplo de função para a qual o método de Newton não converge sempre é f x = a r c t g x . A sequência diverge para valores acima de x ≅ 1.3917 e para valores abaixo de x ≅ - 1.3917 .

Resposta

Exercício Resolvido #3

Richard L. Burden e J. Douglas Faires, Numerical Analysis, 9ª ed. Brooks/Cole, Cengage Learning, pag 75, exercício 6 adaptado

Use o Método de Newton para encontrar soluções com precisão de 10 - 5 para os seguintes problemas:

a e x + 2 - x + 2 cos ⁡ x - 6 = 0