Métodos computacionais de resolução de equações não lineares.

Tecnologia

 

Para se encontrar raízes de uma determinada função, há métodos analíticos que permitem a fácil obtenção, o que nem sempre ocorre. Por exemplo: em y = x² - 1, basta efetuar operações com coeficientes para a obtenção de raízes. Já com a função f(x) = [ln (x – sen(2x³)) ]/ x, por exemplo, não é tão fácil assim ‘isolar o x’. Então, parte-se para o uso de métodos numéricos para a obtenção destas raízes, considerados os erros durante os processos. Uma ideia interessante, para funções pequenas e portando uma calculadora científica, seria fazer uma tabela e ir jogando valores de domínio até buscar as raízes. Porém, como todo método repetitivo, (que pode ser necessário centenas de vezes) o homem deixa que o seu computador o faça.

Raiz ou zero de uma função é todo valor pertencente ao domínio tal que g(x) = 0. Ela também pode indicar a intersecção entre curvas, onde a função diferença entre elas possui como raiz o valor do domínio em que ocorre a intersecção.

O conhecimento das funções abordadas é extremamente importante para a resolução de equações não lineares, de forma que os métodos usados promovam a convergência (encontro de valor próximo à raiz). Os três métodos principais de resolução são: Bisseção, Newton-Raphson e Secante, sendo necessário sempre, ao menos uma aproximação inicial da raiz, e o estabelecimento de uma tolerância, onde os resultados são refinados até que o erro máximo fique abaixo dessa tolerância. Essa aproximação pode ser obtida por meio de softwares gráficos, pela pesquisa do Google ou também pelos próprios ambientes de programação, como o Octave.

Seja uma função f(x) contínua em um intervalo [a,b]. Se f(a) > 0 e f(b) < 0, ou vice versa, sendo f(a) ∙ f(b) < 0, obrigatoriamente, em algum ponto do eixo x neste intervalo, a curva do gráfico de f irá interceptá-lo. Esta raiz terá multiplicidade ímpar. Em caso de raízes com multiplicidade múltipla, pode ocorrer apenas o toque do gráfico no gráfico de uma h(x), como, por exemplo h(x) = x².

O método da bisseção consiste em arbitrar um intervalo [a, b], que após a análise da função ou que já se saiba ser onde se encontra a raiz, de preferência um intervalo próximo, o que contribui para a agilidade de resultados. Arbitrado o valor, começam as iterações, iniciando pelo cálculo do valor médio deste intervalo, que chamaremos de c (c = (a+b)/2). Depois, calculam-se os valores de f(a), f(b) e f(c). Tendo estes valores, a cada iteração, a raiz obtida pelo método da bisseção será considerada como o valor c, em que o menor erro de estimativa será dado por (b - a)/2. O passo seguinte, ao obtermos estes valores, é realizar o produto f(a) ∙ f(c).

Se f(a) ∙ f(c) < 0, f(a) e f(c) possuem sinais diferentes, ou seja, a raiz está na primeira metade do intervalo [a,b]. Na iteração seguinte, portanto, atribuiremos o valor de c para b, e o novo ponto central será calculado.

Se f(a) ∙ f(c) > 0, f(a) e f(c) possuem o mesmo sinal, ou seja, a curva da função f esta interceptando o eixo dos x no intervalo [c,b]. Na próxima iteração, atribuiremos o valor de c para a, e o novo ponto central será calculado.

Se f(c) exatamente igual a zero, a raiz foi obtida diretamente.

Por exemplo: na função f(x) = x² + 3x – 22, como se pode ver no gráfico, a raiz da função f(x) fica entre 3 e 4. Sem iteração alguma, para [a,b], a raiz seria c = 3,5 com erro máximo de 0,5, pelo método da bisseção. Com uma primeira iteração, teríamos, apenas olhando o gráfico, que f(a) < 0, f(b) e f(c) > 0. Então, o produto f(a) ∙ f(c) < 0, e não é necessário mais considerar o intervalo [c, b], pois a raiz está na primeira metade. Assim, atribuímos c à b, e a nova estimativa para a raiz será do novo ponto médio do novo intervalo conhecido. 

[Detalhe de gráfico de x² + 3x – 22. Imagem: Gerador de gráficos do Google]

A cada nova estimativa, o erro segue sendo de (b - a)/ 2, para a e b da iteração. Estipulado um erro máximo para a raiz desejada, terminam as iterações quando este ainda for maior do que (b – a)/ 2^{n + 1}, para os valores de a e b iniciais, e n o número de iterações realizadas. Sendo assim, sempre é possível saber o valor mínimo de iterações para a obtenção de tantas casas decimais desejadas, dentro das configurações da máquina. n > [log (b –a) – log (2E) / log 2], sendo E o erro máximo (tolerância) proposta para a raiz. Se desejamos seis casas decimais exatas, por exemplo, E = 10^-6.

O método da Bisseção é um método lento, mas sempre converge. Pela fórmula das iterações, se pode dizer quantas casas decimais são ganhas a cada iteração. Vejamos abaixo um modelo de algoritmo para a linguagem Octave:

function [c, erro] = bissecao(a, b, t)

fa = f(a);                     fb = 1;

c = (a+b)/2;               fc = f(c);

erro = (b-a)/2;

while (erro > t)

if (fc == 0)

break;

end

if (fa*fc) < 0

b = c; fb = fc;

else

a = c; fa = fc;

end

c = (a+b)/2;   fc = f(c);

erro = (b-a)/2;

end

As expressões f(a) indicam uma função que deve ser predefinida. São fornecidos, ao chamar a função bissecao os valores de a, b e t (que indicará a nossa tolerância). Usou-se fa e fc ao invés de f(a) e f(c) como forma de ganho de tempo, pois há uma pequena demora à cada chamada da função pelo computador, o que pode resultar em ganhos significativos de tempo em cálculos muito grandes.

O método de Newton, por sua vez, que também pode ser chamado de método das tangentes, consiste em um valor arbitrado inicialmente (x₀), que pode ou não ser próximo da raiz real. Usando este valor, vai-se calculando correções para os x_i’s seguintes, com base na derivada da função no ponto. A derivada, por definição, é a inclinação das retas tangentes à curva. No ponto x₀, se a função é diferenciável, a reta tangente é dada por y_tan = f(x₀) = a+ f’(x₀) ∙ x, para a qual é muito mais fácil encontrar um x (raiz desta reta tangente NO PONTO) que será a aproximação seguinte desta iteração. O erro não fica por conta da proximidade de f(x_i) de zero, mas da proximidade entre os valores de x usados nas iterações.

A fórmula iterativa do método de Newton é:

x_n+1 = x_n – f(x_n)/ f’(x_n)

E, a cada passo, calcula-se f(x_n+1), de forma a sabermos se o método está convergindo ou não. Os problemas desta fórmula são um chute errado, onde a inclinação da derivada pode direcionar para um local distante da raiz desejada, ou a derivada pode ser igual a zero para tal valor de x inicial (x₀), Para isso, novamente vale a dica de que é preciso conhecer a forma da função. A cada iteração, praticamente dobra o número de dígitos decimais corretos, até que seja atingida a precisão máxima do computador. O método de Newton exige duas funções a serem usadas pelo computador , f e f’, permite o encontro de raízes complexas e múltiplas, Neste caso, sabendo-se a multiplicidade m da raiz desejada, a fórmula iterativa se torna:

x_n+1 = x_n – mf(x_n)/ f’(x_n)

Um modelo de função no Octave para a aplicação do Método de Newton, havendo uma função f e outra f’ disponíveis em máquina, é:

function r = metodnewton(x0 ,numrep, tol)

k = 0;

erro = 1 + tol;

while (k< numrep & erro > tol)

fx0 = f(x0);

fx0deriv = fderiv(x0);

x1 = x0 – fx0/fx0deriv;

erro = abs(x1 – x0);

x0 = x1;

k = k+1;

end

r = x0

A falta do ponto e vírgula faz com que a raiz r seja demonstrada pelo programa ao fim da execução. O erro será dado pela diferença entre os x’s finais do método. Como há a possibilidade de não convergência, adicionou-se um contador para limitar o processo, pois todo algoritmo precisa ser finito.

O terceiro método a ser abordado é o método da Secante. Ele consiste em um procedimento semelhante ao do Método de Newton, porém é usada apenas uma função – é como se esquecêssemos da existência de uma função derivada pronta, mas acabamos precisando de um segundo chute inicial.

A fórmula da derivada consiste em lim_{h ® 0} [(f(x+h) – f(x)) / h] ou lim _{b ® a}  [(f(b) – f(a)) / (b - a)]. A variação h é uma pequena variação infinitesimal de x. Porém, um computador não consegue abstrair estes conceitos, então se adota simplesmente a substituição de f’(x_n) por aproximadamente [(f(x_n) – f(x_n-1)) / (x_n - x_n-1)]. Assim, partindo do Método de Newton para o da Secante, temos:

x_n+1 = x_n – f(x_n)/ f’(x_n)

x_n+1 = x_n – f(x_n)/ [(f(x_n) – f(x_n-1)) / (x_n - x_n-1)]

x_n+1 = x_n – f(x_n) ∙ [(x_n - x_n-1) / (f(x_n) – f(x_n-1))],

que é a fórmula iterativa nesse caso.

Os problemas apresentados pelo método de Newton são iguais, pois, à medida que h se torna pequeno, o valor de [(f(x_n) – f(x_n-1)) / (x_n - x_n-1)] se aproxima do valor real da função derivada. A obtenção de dígitos decimais exatos ocorre em ritmo mais rápido do que o método da bisseção. Também é necessário, deste modo, criar um critério de parada, cuja expressão é dada por:

|f(x_n) – f(x_n-1)| / |f(x_n)| b E, sendo E o erro ou precisão máxima.

Também se pode usar um número predeterminado de repetições, sem o uso desta fórmula. Um algoritmo para Octave do Método da Secante é:

function x2 = metodsecante(x0, numrep, tol)

fx0 = f(x0)

x1 = x0 + 1e-4

erro = 3 * tol

k = 0

while (k < numrep & erro > tol)

fx1 = f(x1)

x2 = x1 - fx1 * (x1 - x0) / (fx1 - fx0)

erro = abs(x2 - x1)

x0 = x1; fx0 = fx1;

x1 = x2;

k = k + 1;

end

□

 

Você também pode gostar de: (Tecnologia) Princípios de Construção de Programas no Octave.

 

 

Þ Gostou desta postagem? Usando estes botões, compartilhe com seus amigos!