Bernardo, valeu mesmo.Não fui eu quem formulou a pergunta, muito interessante
por sinal.
Escrevo para parabenizá-lo, acima de tudo pela sua atenção, da a questão
formulada pelo denisson .Tudo muito detalhado,legal mesmo.Todos aprendemos.
Um abraço
paulo Barclay
--- Em dom, 5/4/09, Bernardo Freitas Paulo da Costa <bernardo...@gmail.com>
escreveu:
De: Bernardo Freitas Paulo da Costa <bernardo...@gmail.com>
Assunto: [obm-l] Re: [obm-l] Método De Newton
Para: obm-l@mat.puc-rio.br
Data: Domingo, 5 de Abril de 2009, 7:48
2009/4/5 Denisson <denisso...@gmail.com>:
> Estava relendo sobre o método de newton e a demonstração fala que numa
> vizinhança suficientemente próxima da raiz o método converge. Implementei o
> algoritmo em um computador e o polinômio x^2 + 3x + 2 por exemplo de raizes
> -1 e -2 ao tomar uma aproximação inicial de valor 100000 ele encontra a raiz
> -1. Pergunto o que caracteriza exatamente esse intervalo "suficientemente
> próximo".
Bom, isso é realmente um "problema" da demonstração (e provavelmente
de todas as demonstrações que dizem "suficientemente pequeno" ou
"suficientemente grande"). Mas acho que não tem jeito melhor de fazer.
Deixa eu explicar o que eu quero dizer:
Se você leu a demonstração, o cara precisa de duas hipóteses sobre os
valores da derivada de f (uma para f', outra para f'', se a memória
não falha), para garantir que "o próximo ponto" está mais próximo da
raiz do que o "atual". Para isso, o cara usa a continuidade de f, f' e
f'', o que é um método bastante geral para obter que a função não
varia muito, mas em compensação, o resultado que ele dá é somente o
"suficientemente pequeno" que você encontrou, e ainda por cima, a
continuidade não te dá o tamanho desse intervalo. Assim, ele diz
apenas suficientemente pequeno, existe, e o matemático está contente.
Agora, você quer implementar o algoritmo, e gostaria que saber quando
ele funciona. Muito bem, basta reler a demonstração e ver quais são
*exatamente* as hipóteses que a prova exige para a convergência. Se
você lembra do algoritmo de escolha do próximo ponto, temos a_{n+1} =
a_n - f(a_n) / f'(a_n), e a gente testa a convergência usando o único
critério disponível, ou seja, o de Cauchy, e para isso temos que
tentar calcular (a_{n+2} - a_{n+1}) / (a_{n+1} - a_n) e ver se dá um
comportamento de série geométrica. Com a fórmula, isso quer dizer que
é pra calcular f(a_{n+1}) / f(a_n) * f'(a_n) / f'(a_{n+1}). Agora, use
uma aproximação de segunda ordem para a função perto de a_n, ou seja,
diga que f(a_n + x) = f(a_n) + f'(a_n)x + f''(a_n)x^2/2 + erro
pequenininho, e vamos estimar f(a_{n+1}) / f(a_n). Pela definição do
a_{n+1} (lembre da reta tangente batendo no zero !), a distância do
a_{n+1} ao a_n é tal que os dois primeiros termos de taylor
desaparecem, resta portanto só o último, que vale f''(a_n)/2 *
(a_{n+1} - a_n)^2 = f''(a_n)/2 * f(a_n)^2 / f'(a_n)^2. Assim, o
quociente a gente pode estimar com f(a_{n+1}) / f(a_n) ~= f''(a_n)/2 *
f(a_n) / f'(a_n)^2. Daí, resta estimar o quociente das derivadas, e se
eu não me engano, a demonstração simplesmente exige que a f' esteja no
intervalo [a, A], com 0 < a < A, e portanto o quociente é no máximo
A/a que é limitado. Daí, se você começar suficientemente perto, o erro
é menor do que f(a_n) * (f''(a_n)/2 / f'(a_n)^2) * A/a e isso tudo
será menor do que 1 (pro critério de Cauchy, lembra ?) bastando que a
f''(a_n) seja limitada, e que f(a_n) seja muuuuuuuuuuuito pequeno (ou
seja, isso é o "suficientemente perto" da raiz em questão). Bom, isso
é o primeiro passo.
Agora, vamos ver o teu exemplo ! Você pegou um polinômio do segundo
grau para testar, portanto, só pra início de conversa, a f''(x) é
limitada *na reta toda* ! O que já é uma boa mão na roda na hora de
fazer o algoritmo convergir. Se você refizer as contas que eu dei,
simplificando quando puder, vai dar pra ver que o quociente entre as
diferenças sucessivas (o que a gente tem que calcular no critério de
Cauchy) é f(a_n) * f''(a_n) / 2( f'(a_n) * f'(a_{n+1}) = Constante *
f(a_n) / ( f'(a_n) f'(a_{n+1} ) . Desenvolvendo mais uma vez por
Taylor (no denominador agora, a gente quase nunca usa isso na prova
porque não precisa, mas no teu caso é legal ver no que dá), a gente
obtém um treco que é aproximadamente (veja que, na verdade, é
exatamente, porque a aproximação de Taylor de ordem 2 de um polinômio
de ordem dois é *exata* !)
f(a_n) * f''(a_n) / 2 ( f'(a_n) ^2 - f(a_n)*f''(a_n) )
e substituindo o polinômio, você vai ver que dá sempre menor do que 1,
exceto quando você começa entre as raízes. Isso tem também uma
explicação geométrica : como a função é convexa, o método sempre
aproxima quando você está depois das raízes (esse é um excelente
exercício pra você ver que você entendeu direitinho o método !), mas
pode se afastar quando você começa entre. Aliás, a melhor maneira de
tentar começar a solução é justamente fazer o desenho !
> O segundo ponto, o que acontece no método quando você toma como aproximação
> inicial exatamente a média entre duas raizes? Ele vai convergir pra algum
> valor? No computador deu erro mas não tenho certeza ainda se foi erro de
> programação :P
Bom, é um erro dos dois :) Veja bem, lembra da demonstração, que a
gente pedia para a f' estar num intervalo longe do zero (para poder
estimar um quociente ?) Pois é, a gente também precisa que a derivada
seja diferente de zero para poder simplesmente calcular o próximo
passo da iteração (qualquer coisa, dê uma olhada de volta na fórmula
para lembrar !). Ora, numa função do segundo grau, começando no ponto
médio das raízes, a derivada é zero, portanto, você não pode nem dar o
primeiro passo !!! Daí, como você não verificou a hipótese matemática
( f' != 0) o programa se encarregou de xingar você por tentar dividir
por zero :))) O que mostra que é importante verificar todas as
hipóteses antes de começar a fazer as contas, porque senão o resultado
pode ficar sem sentido nenhum.
Ah, se você quiser um exemplo de coisas que não funcionam, tente
calcular as raízes de x(x-1)(x+1) usando o método e começando num
"ponto ruim", x = 0.44721359549995793928183473374625
Repare que eu escolhi um ponto entre as três raízes, porque um ponto
fora delas daria (pela mesma idéia do convexo que eu falei antes, tem
a ver com a monotonicidade de f') sempre convergente pra raíz mais
próxima !
> Obrigado
> --
> Denisson
Qualquer dúvida, é só falar !
--
Bernardo Freitas Paulo da Costa
=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~obmlistas/obm-l.html
=========================================================================
Veja quais são os assuntos do momento no Yahoo! +Buscados
http://br.maisbuscados.yahoo.com
