Métodos computacionais de resolução de equações não lineares. Métodos computacionais de resolução de equações não lineares.
Página inicialTecnologia e SoftwaresMétodos computacionais de resolução de equações não lineares.
Métodos computacionais de resolução de equações não lineares.
Mestre Blogueiro quarta-feira, setembro 11, 2013
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)/ 2n + 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 (fa*fc) < 0
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 (x0), que pode ou não ser próximo da raiz real. Usando este valor, vai-se calculando correções para os xi'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 x0, se a função é diferenciável, a reta tangente é dada por ytan = f(x0) = a+ f'(x0) ∙ 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(xi) de zero, mas da proximidade entre os valores de x usados nas iterações.
A fórmula iterativa do método de Newton é:
xn+1 = xn – f(xn)/ f'(xn)
E, a cada passo, calcula-se f(xn+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 (x0), 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:
xn+1 = xn – mf(xn)/ f'(xn)
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)
erro = 1 + tol;
while (k< numrep & erro > tol)
fx0 = f(x0);
fx0deriv = fderiv(x0);
x1 = x0 – fx0/fx0deriv;
erro = abs(x1 – 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 limh ® 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'(xn) por aproximadamente [(f(xn) – f(xn-1)) / (xn - xn-1)]. Assim, partindo do Método de Newton para o da Secante, temos:
xn+1 = xn – f(xn)/ [(f(xn) – f(xn-1)) / (xn - xn-1)]
xn+1 = xn – f(xn) ∙ [(xn - xn-1) / (f(xn) – f(xn-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(xn) – f(xn-1)) / (xn - xn-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(xn) – f(xn-1)| / |f(xn)| 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 é: