Aula 14 - Equações Não Lineares - Algoritmos

Prévia do material em texto

Sumário
3. Equações e Sistemas Não-Lineares3. Equações e Sistemas Não-Lineares
• Enumeração, localização e separação de raízes
• Métodos iterativos para a resolução de equações 
polinomiais ou transcendentes
• Métodos de quebra
• Métodos de ponto fixo
• Resolução de sistemas de equações não-lineares
• Algoritmos
Aula 14 1Cálculo Numérico Computacional
Equações Não Lineares
 Assumiremos que o algoritmo do método da bisseção recebe como 
entrada uma função F, e dois valores a e b (sendo a<b) que 
representam o intervalo [a,b] que contém uma raiz de f(x)
 A cada iteração, o ponto médio xm do intervalo entre a e b é 
calculado; porém, antes de atualizar o valor de xm, armazenamos o 
valor prévio em uma variável chamada xp:
xp = xm;
xm = (a+b)/2;
Aula 14 Cálculo Numérico Computacional 2
Algoritmo do Método da Bisseção
Equações Não Lineares
 Verificamos se a troca de sinal ocorre entre a e xm; em caso 
afirmativo, utilizamos o valor de xm como b na próxima iteração; caso 
contrário, utilizamos o valor de xm como a:
if F(xm)*F(a)<0
 b = xm;
else
 a = xm;
end
 Como qualquer método iterativo, precisamos de um critério de 
exatidão (utilizaremos dois possíveis: Tolerância e Magnitude da 
Função) e um número máximo de iterações kmax
Aula 14 Cálculo Numérico Computacional 3
Algoritmo do Método da Bisseção
Aula 14 Cálculo Numérico Computacional 4
function [x,k] = bissecao(f,a,b,criterio,limiar,kmax)
xm = a;
for k=1:kmax,
 xp = xm;
 xm = (a+b)/2;
% critério de convergência:
 if (isequal(criterio,'MagnitudeFuncao') && abs(F(xm))<limiar)
 break;
 end
 if (isequal(criterio,'Tolerancia') && abs(xm-xp)/abs(xm)<limiar)
 break;
 end
% atualiza intervalo:
 if F(xm)*F(a)<0
 b = xm;
 else
 a = xm;
 end 
end
x = xm;
Equações Não Lineares
 O algoritmo do método da Falsa Posição é idêntico ao algoritmo do 
método da Bisseção, exceto pela forma com que o intervalo [a,b] é 
dividido:
xs = a - ((b-a)*F(a))/(F(b)-F(a));
Aula 14 Cálculo Numérico Computacional 5
Algoritmo do Método da Falsa Posição
Aula 14 Cálculo Numérico Computacional 6
function [x,k] = falsa_posicao(f,a,b,criterio,limiar,kmax)
xs = a;
for k=1:kmax,
 xp = xs;
 xs = a - ((b-a)*F(a))/(F(b)-F(a));
% verifica critério de convergência:
 if (isequal(criterio,'MagnitudeFuncao') && abs(F(xs))<limiar)
 break;
 end
 if (isequal(criterio,'Tolerancia') && abs(xs-xp)/abs(xs)<limiar)
 break;
 end
% atualiza intervalo: 
 if F(xs)*F(a)<0
 b = xs;
 else
 a = xs;
 end 
end
x = xs;
Equações Não Lineares
 Assumiremos que o algoritmo do método de Newton-Raphson recebe 
como entrada duas funções F e DF, que representam a função f(x) e a 
sua derivada f’(x), respectivamente, assim como uma estimativa inicial 
x0 da raiz
 A cada iteração, a estimativa da raiz x é atualizada; porém, antes de 
disso armazenamos o valor prévio em uma variável chamada xp:
xp = x;
x = x - F(x)/DF(x);
Aula 14 Cálculo Numérico Computacional 7
Algoritmo do Método de Newton-Raphson
Aula 14 Cálculo Numérico Computacional 8
function [x,k] = newton_raphson(F,DF,x0,criterio,limiar,kmax)
x = x0;
for k=1:kmax
 xp = x;
 x = x - F(x)/DF(x);
% verifica critério de convergência: 
 if (isequal(criterio,'MagnitudeFuncao') && abs(F(x))<limiar)
 break;
 end
 if (isequal(criterio,'Tolerancia') && abs(x-xp)/abs(x)<limiar)
 break;
 end
end
Equações Não Lineares
 Para calcular uma raiz de um polinômio, ao invés de definir sequências 
de caracteres que representam a função f(x) e a sua derivada, 
podemos apenas definir um vetor de coeficientes
 Por exemplo, o polinômio p(x) = x3 + 4x2 – 2x + 10 poderia ser definido 
pelo vetor:
coefs = [1 4 -2 10];
 A função polyval pode ser utilizada para avaliar o polinômio em um 
determinado valor x:
polyval(coefs,x)
 E os coeficientes da derivada p’(x) podem ser computados facilmente 
para um vetor qualquer de coeficientes:
order = length(coefs)-1:-1:1;
deriv = coefs(1:end-1).*order;
Aula 14 Cálculo Numérico Computacional 9
Algoritmo do Método de Newton-Raphson
Aula 14 Cálculo Numérico Computacional 10
function [x,k] = newton_raphson_poly(coefs,x0,criterio,limiar,kmax)
order = length(coefs)-1:-1:1;
deriv = coefs(1:end-1).*order;
x = x0;
for k=1:kmax
 xp = x;
 x = x - polyval(coefs,x)/polyval(deriv,x);
% verifica critério de convergência:
 if (isequal(criterio,'MagnitudeFuncao') && 
abs(polyval(coefs,x))<limiar)
 break;
 end
 if (isequal(criterio,'Tolerancia') && abs(x-xp)/abs(x)<limiar)
 break;
 end
end
Equações Não Lineares
 Para o método das Secantes, assumiremos que são dadas duas 
estimativas iniciais x0 e x1 (sendo x0≠x1) da raiz
 Uma nova estimativa x2 é dada por:
x2 = x1 - (F(x1)*(x0-x1))/(F(x0)-F(x1));
 Para a próxima iteração, atualizamos os valores de x0 e x1:
x0 = x1;
x1 = x2;
Aula 14 Cálculo Numérico Computacional 11
Algoritmo do Método das Secantes
Aula 14 Cálculo Numérico Computacional 12
function [x,k] = secantes(F,x0,x1,criterio,limiar,kmax)
for k=1:kmax,
 x2 = x1 - (F(x1)*(x0-x1))/(F(x0)-F(x1));
% verifica critério de convergência:
 if (isequal(criterio,'MagnitudeFuncao') && abs(F(x2))<limiar)
 break;
 end
 if (isequal(criterio,'Tolerancia') && abs(x2-x1)/abs(x2)<limiar)
 break;
 end
% atualiza x0 e x1:
 x0 = x1;
 x1 = x2;
end
x = x2;
Equações Não Lineares
 Para resolver um sistema de n equações não-lineares com n 
incógnitas através do método de Newton-Raphson, temos que definir a 
nossa função f(x): ℝn→ ℝn e o jacobiano j(x): ℝn→ ℝnn nossa 
 Por exemplo, para o sistema abaixo:
 assumindo que , temos que:
 Que podem ser definidos pelos comandos:
F = @(x) [x(1).^2+x(2).^2-1 ; exp(x(1))-x(2)-1.5];
J = @(x) [2*x(1) 2*x(1) ; exp(x(1)) -1];
Aula 14 Cálculo Numérico Computacional 13
Algoritmo do Método de Newton-Raphson para Sistemas
Equações Não Lineares
 Dada uma estimativa inicial x0 (vetor de n elementos), inicializamos o 
vetor x com x0:
x = x0;
 A cada iteração o vetor xp armazena o valor de x da última iteração e 
então x é atualizado:
xp = x;
delta = J(x)\-F(x);
x = x + delta;
 Como x e xp são vetores, os critérios de convergência devem ser 
verificados para todos os elementos do vetor:
max(abs(F(x)))<limiar (para o critério da magnitude da função)
max(abs(x-xp)./abs(x))<limiar (para o critério de tolerância)
Aula 14 Cálculo Numérico Computacional 14
Algoritmo do Método de Newton-Raphson para Sistemas
Aula 14 Cálculo Numérico Computacional 15
function [x,k] = newton_raphson_system(F,J,x0,criterio,limiar,kmax)
x = x0;
for k=1:kmax
 xp = x;
 delta = J(x)\-F(x);
 x = x + delta;
% verifica critério de convergência:
 if (isequal(criterio,'MagnitudeFuncao') && max(abs(F(x)))<limiar)
 break;
 end
 if (isequal(criterio,'Tolerancia') && max(abs(x-xp)./abs(x))<limiar)
 break;
 end
end
Equações Não Lineares
 Exercício 1: Determine a raiz da equação abaixo através dos métodos 
de Bisseção, Falsa Posição, Newton-Raphson e Secantes, utilizando 
os algoritmos vistos anteriormente
 Exercício 2: Determine a raiz real do polinômio p(x) = x3 + 4x2 – 2x + 10 
através do método de Newton-Raphson, utilizando o algoritmo 
específico para polinômios
 Exercício 3: Determine a solução do sistema abaixo através do 
método de Newton-Raphson, utilizando o algoritmo visto anteriormente 
Aula 14 Cálculo Numérico Computacional 16
	Sumário
	Equações Não Lineares
	Equações Não Lineares
	Slide 4
	Equações Não Lineares
	Slide 6
	Equações Não Lineares
	Slide 8
	Equações Não Lineares
	Slide 10
	Equações Não Lineares
	Slide 12
	Equações Não Lineares
	Equações Não Lineares
	Slide 15
	Equações Não Lineares