Método de Newton-Raphson
Teoria
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 , onde é ponto fixo de .
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 tal que ! 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: tal que ’( ξ ) = 0.
E como calculamos isso matematicamente? Usando a seguinte função de iteração:
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á:
Além disso, existe um teorema que diz algo assim: “No intervalo [a, b] deve conter a raiz = ξ de . Se a derivada dessa função ’ (ξ) ≠ 0. Então, a raiz ξ estará dentro do intervalo, que vai convergir ao valor real por meio de iterações de sequências {} gerada pela fórmula”.
Geralmente o método de Newton converge desde que nosso palpite inicial 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 , traçamos a reta tangente à curva neste ponto. A fórmula da reta tangente é dada por:
Essa reta funciona como uma aproximação para a função na vizinhança de . Ou seja, quanto mais próximo de estivermos, melhor a reta tangente aproxima a própria função.
E como nosso chute deve estar próximo da raiz de , consideramos a aproximação como uma aproximação boa o suficiente para encontrar o zero de e fazemos:
Basta fazermos 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 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á:
E, novamente, outro critério usado é:
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 usando
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 , e o valor da nossa função , o valor da derivada , 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, então vamos usar .
Primeiro: podemos calcular o valor da função no ponto . Se nossa função é:
No ponto :
Cálculos Iniciais
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 . 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 :
Critério de Parada:
Como não alcançamos o critério de parada, continuamos as iterações.
Iteração :
Critério de Parada:
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 fica bem mais fácil quando só jogamos os valores dentro da fórmula. Legal né?
CARACA! Quatro iterações cara! Sabe o que são iterações? Pra uma precisão de ?! Pra você ter uma ideia no método da bisseção íamos precisar de 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
b. Precisão do resultado final e
Passo 2. Definimos um contador de iterações .
Passo 3. Se , escolha como e FIM. Caso contrário, continue para o Passo 4.
Passo 4. , aumentamos uma iteração no contador.
Passo 5.
Passo 6. Se , escolha como e FIM. Caso contrário continue para o Passo 7.
Passo 7.
Passo 8. Voltamos para o Passo .
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 . 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 e a 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 , e contínuas em um intervalo que contém , tal que e . Então existe um intervalo centrado em que converge para para qualquer aproximação inicial .
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 poderia convergir para uma raiz ), 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 e que o cálculo de sua derivada não seja muito elaborado.
Algoritmo
Estudo da Convergência
Observações
Exercícios Resolvidos
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 e . Use o Método de Newton para encontrar . O valor poderia ser usado?
Passo 1
Só aplicar o algoritmo:
Cálculos Iniciais
Taí o nosso .
A próxima pergunta é, poderia ser usado? Não poderia pois a derivada nesse ponto vale :
Isso nos criaria uma indeterminação na nossa função de iteração.
Resposta
.
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 , que tenha pelo menos uma raiz, onde o Método de Newton-Raphson não converge sempre.
Passo 1
Um exemplo de função para a qual o método de Newton não converge sempre é . A sequência diverge para valores acima de e para valores abaixo de .
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 para os seguintes problemas:
para
para e
para e
para e
Passo 1
Intervalo
Cálculos Iniciais
Iteração :
Critério de Parada:
Como não alcançamos o critério de parada continuamos as iterações.
Iteração :
Critério de Parada:
Como não alcançamos o critério de parada continuamos as iterações.
Iteração :
Critério de Parada:
Alcançamos nosso critério de parada. Então .
Passo 2
Intervalo
Cálculos Iniciais
Iteração :
Critério de Parada:
Como não alcançamos o critério de parada continuamos as iterações.
Iteração :
Critério de Parada:
Como não alcançamos o critério de parada continuamos as iterações.
Iteração :
Critério de Parada:
Alcançamos nosso critério de parada. Então .
Passo 3
Intervalo
Cálculos Iniciais
Iteração :
Critério de Parada:
Como não alcançamos o critério de parada continuamos as iterações.
Iteração :
Critério de Parada:
Como não alcançamos o critério de parada continuamos as iterações.
Iteração :
Critério de Parada:
Alcançamos nosso critério de parada. Então .
Passo 4
Intervalo
Cálculos Iniciais
Iteração :
Critério de Parada:
Como não alcançamos o critério de parada continuamos as iterações.
Iteração :
Critério de Parada:
Como não alcançamos o critério de parada continuamos as iterações.
Iteração :
Critério de Parada:
Como não alcançamos o critério de parada continuamos as iterações.
Iteração :
Critério de Parada:
Alcançamos nosso critério de parada. Então .
Passo 5
Intervalo
Cálculos Iniciais