Física Computacional - FSC-5705

só um divisor

Raízes de equações

Em muitas ocasiones estamos interessados em saber onde uma dado conjunto de dados corta o eixo das abscisas, ou seja, queremos resolver mediante um método numérico:

$ f(x) = 0 $

Do ponto de vista da matemática, somente se exige uma condição expressa pelo seguinte teorema:

Teorema:
Se uma função contínua $f(x)$ assume valores de sinais opostos nos pontos extremos do intervalo $[a,b]$, isto é, se $f(a) \, f(b) < 0$, então existe pelo menos um ponto $\bar{x} \in [a,b]$, tal que $f(\bar{x}) = 0$

Tomando como base esse teorema, foram desenvolvidos métodos diversos que permitem a obtenção da raiz (zero) a partir dos dados

Método de Bisseção

Ainda que o método funciones para o caso em que existe mais de uma raiz no intervalo, vamos considerar o caso na qual somente temos uma raiz. Basicamente, o método consiste em:

  1. selecionar o intervalo onde possivelmente está a raiz (isto é procurar onde os dados mudam de sinal)
  2. Dividir continuamente o intervalo até atingir o valor, $\bar{x}$, da raiz procurada com o erro relativo $\epsilon$, desejado, isto é:
    \[ \dfrac{|x_{k+1} - x_k|}{|x_k|} < \epsilon \nonumber \] onde $\epsilon$ é um valor prefixado; $x_{k+1}$ e $x_k$ são duas aproximações consecutivas para o valor para $\bar{x}$.

Método de Newton-Rapson

O método de Newton-Raphson é um método aberto, no sentido de que sua convergência global não está garantida. A única maneira de atingir a convergência é selecionar um valor inicial suficientemente próximo à raiz procurada. Assim, se tem de começar a iteração com um valor razoavelmente próximo ao zero ou raiz (denominado ponto de arranque ou valor suposto). Quão perto o ponto inicial deve estar da raiz vai depender da natureza da própria função que estamos a analisar; se esta apresenta múltiplos pontos de inflexão ou inclinações grandes no meio entre o ponto de partida e a raiz procurada, estes fatos aumentam a probabilidade de que o algoritmo diverga, assim devemos selecionar um valor suposto bem próximo da raiz. Uma vez feito isto, o método lineariza a função pela reta tangente nesse valor suposto. A abscisa na origem de dita recta será, segundo o método, uma melhor aproximação da raiz que o valor anterior. Assim, serão realizadas sucessivas iterações até que o método tenha convergido o suficiente.

Seja f : [a, b] -> R função derivável definida no intervalo real [a, b]. Começamos com um valor inicial x0 e definimos para a cada número natura $n$
$\displaystyle{ x_{n+1}=x_n+\frac{f(x_n)}{f'(x_n)} }$
onde $f'(x_n)$ é a derivada de $f(x_n)$ avaliada no ponto $x_n$.

Note-se que o método descrito é de aplicação exclusiva para funções de uma variável com forma analítica ou implícita conhecida. Existem variantes do método aplicáveis a sistemas discretos que permitem estimar as raízes da tendência, bem como algoritmos que estendem o método de Newton a sistemas multivariables, sistemas de equações, etc.

Interpretação geométrica do método

Interpretação geométrica do método de Newton

O método de Newton tem uma interpretação geométrica que está na origem da sua dedução inicial, conforme a figura. Geometricamente, a ideia consiste em usar a recta tangente

$\displaystyle{ y = f(x_n) + f'(x_n)(x-x_n) }$

como aproximação da função $f$ em $x_n$ (é a aproximação de primeira ordem, na expansão de Taylor). Deduzindo o valor $x$ tal que $y = 0$ obtemos a mesma expressão

$\displaystyle{ \begin{array}{rcl} 0 & =& f(x_n)+ f'(x_n)(x-x_n)\\ x & = & x_n - \frac{f(x_n)}{f'(x_n)}\\ \end{array} }$

e esse valor $x$ constitui a nova aproximação $x_{x+1}$.

Podem deduzir-se aproximações superiores considerando expansões de Taylor de ordem superior. Aumenta-se a ordem de convergência, mas perde-se em eficácia computacional.

É importante realçar que n-iterações do método de Newton são normalmente mais eficazes do que uma iteração de outro método de ordem $2n$.

Tarefa

  1. Implementar o método da bisseção e encontrar a raiz de $f(x) = \sin 10x - \cos 3x$ no intervalo $x=0$ e $x =5$
  2. Encontre a raiz positiva da função $f(x) = x^2 |\cos \sqrt{x}| = 5$ ($x$ está em radianos) que está entre $x = 0$ e $x=5$.
  3. Implemente os algoritmos Newton-Rapson e encontre a raiz do polinômio $f(x)=e^{-x}-x$. Utilize como ponto de partida $x_0=0$
  4. Localize a primeira raiz positiva de $f(x)=\sin x + \cos (1-x^2) - 1$