Material de apoio - Introdução a resolução de sistemas não-lineares

Prévia do material em texto

Cálculo numérico 
ST462 B / ST468 B 
 
 
 
 
 
Sistemas não lineares 
 
 No processo de resolução de um problema 
prático, é frequente a necessidade de se obter 
a solução de um sistema de equações não 
lineares. 
 
 
 
 
 
Sistemas não lineares 
 
 Dada uma função não linear 
em que o objetivo é encontrar F(x)=0, ou de 
forma equivalente: 
 
T
n
nn ffFDF ),...,(,: 1










0,...,,(
0,...,,(
0,...,,(
21
212
211
nn
n
n
xxxf
xxxf
xxxf

 
 
 
 
 
Sistemas não lineares 
 Exemplo 
 
 
 
 Este sistema não linear admite 4 soluções, 
que são os pontos onde as curvas 
se interceptam. 
 







01
0
),(
02),(
2
22
1211
2
2
2
1211
x
xxxf
xxxxf
1
9
 e 2
2
22
1
2
2
2
1 
x
xxx
 
 
 
 
 
Sistemas não lineares 
 Cada função fi(x) é uma função não linear em x, fi: , 
e portanto, F(x) é uma função não linear em x, F: 
 O vetor das derivadas parciais da função fi(x1,x2,...,xn) é denominado 
vetor gradiente de fi(x) e é denotado por fi(x), i=1,...n: 
 
 
 A matriz das derivadas parciais de F(x) é chamada de matriz Jacobiana e 
será denominada por J(x): 
 
 
 
nin ,...1, 
nn 

 
 
 
 
 
Sistemas não lineares 
 Os métodos para resolução de sistemas não lineares são 
iterativos, istoé, a partir de um ponto inicial x(0), geram uma 
sequencia {x(k)}de vetores e, na situação de convergência: 
 
onde x* é uma das soluções do sistema não linear. 
 Em qualquer método iterativo, é preciso estabelecer 
critérios de parada para se aceitar um ponto x(k) como 
aproximação para a solução exata x* ou para se detectar a 
divergência do processo. 
 
 
 
*lim )( xx k
k


 
 
 
 
 
Método de Newton 
 É considerado o método mais amplamente estudado para 
resolução de sistemas não lineares. 
 No caso de uma equação não linear a uma variável, o método 
de Newton consiste em se tomar um modelo local linear da 
função f(x) em torno de xk, e este modelo é a reta tangente à 
função em xk.Aproximando, temos: 
 
 A nova aproximação x(k+1) será o zero do modelo local linear 
Lk(x). Portanto: 
 
))(()()( )()()( kkkk xxxJxFLxF 
).())((0)( )()( kkkk xFxxxJxL 
 
 
 
 
 
Método de Newton 
 
 Uma iteração de Newton requer: 
i)A avaliação da matriz Jacobiana em x(k) 
ii) A resolução do sistema linear 
e por este motivo, cada iteração é considerada 
computacionalmente cara. 
 
 
),())(( )()( kkk xFxxxJ 
Método de Newton 
 Algortimo 
Dados x0, ԑ1>0 e ԑ2>0 faça: 
Passo 1: calcule F(x(k)) e J(x(k)); 
Passo 2: se ||Fx(k))|| < ԑ1, faça x = x
(k) e pare; 
Passo 3: obtenha (x-x(k)), solução do sistema linear: J(x(k))(x-x(k))= -F(x(k)); 
Passo4: faça x(k+1) = x(k) + (x-x(k)); 
Passo 5: se ||x(k+1)-x(k)|| < ԑ2, faça x = x
(k+1) e pare; caso contrario vá para o passo 6; 
Passo 6: k = k + 1 e volte ao passo 1. 
Método de Newton - Exemplo 
Considere s = (x-x(k)) 
 
 
 
 Este método consiste na utilização da fatoração LU 
para resolver os sistemas não lineares. 
 Ao utilizar a fatoração LU para resolver o sistema, os 
fatores L e U serão calculados apenas uma vez e, a 
partir da 2ª iteração, será necessário resolver apenas 
dois sistemas triangulares para obter o vetor s(k). 
 
 
 
Método de Newton Modificado 
 
Considere o sistema anterior utilizando o método de Newton 
modificado 
 
 
 
 
 
Método Quase-Newton 
 A motivação central do método quase-Newton é gerar uma seqüência 
{x(k)} com boas propriedades de convergência, sem no entanto avaliar a 
matriz Jacobiana a cada iteração. 
 A seqüência {x(k)}, nos métodos quase-Newton, é gerada através da 
fórmula: 
 
onde s(k) é a solução do sistema linear: 
 
 Existem diversos métodos quase-Newton, e é importante ressaltar que em 
vários deles , além de se evitar o cálculo da matriz Jacobiana, o esforço 
computacional necessário para a resolução do sistema linear é reduzido em 
relação ao esforço realizado no método de Newton. 
 
 
 
 
)()(1 kkk sxx 
)( )()()( kkk xFsB 