Fractais e o método de Newton
Como a convergência do método de Newton pode ser fascinante
Vamos lá?
Nesta aula mostro um resultado de convergência para o método de Newton. Depois, em um exemplo de aplicação do método de Newton a uma função bem simples, vamos ver a relação do método de Newton com Fractais.
- 1
- 2
- 3
Suponha que é o zero de O que o teorema de convergência do método de Newton não deixa claro?
No exemplo do vídeo, a função ...
O que representa cada cor na figura do vídeo?
Apesar do método de Newton datar do século XVII, o teorema de convergência do método de Newton, em sua forma mais geral, foi demonstrado apenas em 1948, por Leonid Kantorovich . No vídeo, apresentei o teorema mais simples.
Teorema: Sejam
Duas observações importantes devemos fazer a respeito deste teorema. A primeira é que
Como exemplo, considere
Outra observação sobre o teorema é que está assegurada a existência dessa vizinhança
Após a metade do século XX, com o advento dos computadores, pesquisadores começaram a identificar numericamente (e visualmente) essas regiões de convergência. O experimento era escolher diversos pontos iniciais para o método de Newton e observar para qual zero da função o método convergia. O ponto inicial era então marcado com a cor que identificava o zero atingido. O teorema nos garante o que acontece quando
Para ir além, recomendo o livro Greenbaum e Chartier (2012).
Fractal no Octave
Podemos fazer um experimento no Octave para tentar produzir um fractal como exibido no vídeo. Naquele exemplo, estávamos interessados em estimar os zeros de
Inicie definindo a função e sua derivada, assim como uma malha sobre a região
f = @(z) z^3-1; g = @(z) 3*z^2; n = 200; # quantidade de pontos na malha em cada direção x = linspace(-1.5, 1.5, n); y = linspace(-1.5, 1.5, n); sol = [1; (-1 + sqrt(3)*i)/2; (-1 - sqrt(3)*i)/2];
Para este exemplo simples, vamos rodar uma quantidade fixa de iterações do método de Newton.
C = zeros(n,n); # matriz para guardar os resultados for ix = 1:n for iy = 1:n z = x(ix) + y(iy) * i; # ponto inicial for k = 1:20 # 20 iterações de Newton z = z - f(z)/g(z); endfor [err, I] = min( z - sol ); # De qual zero de f, z está mais próximo? C(iy,ix) = I; # Guarda o índice da raiz mais próxima endfor endfor imagesc(x,y,C); axis("xy"); colorbar;
Experimente o código acima e veja a figura produzida. Depois brinque com ele. Por exemplo, experimente-o com outras funções
Referência
Anne Greenbaum e Timothy P. Chartier. Numerical Methods: Design, Analysis, and Computer Implementation of Algorithm. Princeton University Press, 2012.
1. Construa a iteração de Newton para estimar o zero da função
2. A convergência do método de Newton só pode ser garantida numa vizinhança da solução. Grafique as funções abaixo e observe o comportamento das iterações produzidas pelo método de Newton a partir do ponto inicial
3. Seja
- Faça o gráfico de
e tente "adivinhar" o que acontece quando o método de Newton é usado para estimar esse zero, para diferentes escolhas de - Compute a sequência produzida pelo método de Newton, partindo de
- Compute a sequência produzida pelo método de Newton, partindo de
- Tente empiricamente descobrir o valor de
que está no limite entre os dois casos observados acima. - Mostre que para
solução de , a sequência gerada pelo método de Newton é
4. Seja
- Aplique o método de Newton para encontrar os primeiros dois zeros positivos de
digamos e , e os primeiros dois zeros negativos de digamos e - Estime numericamente
e