Embed Size (px)
Citation preview
Resolução de Sistemas Não-Lineares- Parte 1
Sistemas não-lineares
Normalmente, em problemas aplicados temos que resolver sistemas de equações
não-lineares de ordem n
nn
• Dada
• Procuramos a solução do sistema não-linear
• Em notação matricial:
Tnnn fffFRRDF ,...,,,: 21
Sistemas não-lineares
0)( xF
0,...,,,
.....................................
0,...,,,
0,...,,,
321
3211
3211
nn
n
n
xxxxf
xxxxf
xxxxf
EXEMPLO DE SISTEMAS
NÃO-LINEARES nxn
Exemplo1: Intersecção de círculo com hipérbole.
Temos 4 soluções (intersecções)!!!!!!!!!!!!!!!!
019
,
02,222
1211
22
21211
xxxxf
xxxxf
1x
2x
EXEMPLO DE SISTEMAS
NÃO-LINEARES nxn
Exemplo2: Intersecção de duas parábolas.
Não temos soluções!!!!!!!!!!!!!!!!
01,
02.0,
122211
221211
xxxxf
xxxxf
1x
2x
2.0
1
SISTEMAS NÃO-LINEARES nxn
HIPÓTESES
Seja onde
é um aberto de . Em , suponha que
tenha derivadas contínuas. Suponha que exista pelo
menos um tal que .
Tnnn fffFRRDF ,...,,,: 21 D
D
nn x
x
x
x
xf
xf
xf
xF....
com
)(
........
)(
)(
)( 2
1
2
1
Dx 0xF
nR
SISTEMAS NÃO-LINEARES nxn
HIPÓTESES
Seja o vetor gradiente de dado por
e a matriz Jacobiana de :
ni xxxf ,...,, 21
T
n
iiii x
xf
x
xf
x
xfxf
)(,,.........
)(,)(
)(21
)(xF)(xJ
n
nnn
n
n
Tn
T
T
x
xf
x
xf
x
xf
x
xf
x
xf
x
xfx
xf
x
xf
x
xf
xf
xf
xf
xJ
)()()(
)()()(
)()()(
)(
................
)(
)(
)(
21
2
2
2
1
2
1
2
1
1
1
2
1
SISTEMAS NÃO-LINEARES nxn
MÉTODO DE NEWTON
O Método de Newton é método básico. Consiste na linearização local do sistema não-linear Seja a aproximação . Para qualquer ,
existe , tal que:
Aproximando, temos um modelo local linear
Dx k )(
nixxcfxfxf kTii
kii ,..,2,1para)(
DxDci
nixxxfxfxf kTki
kii ,..,2,1para)()(
kkkk xxxJxFxLxF )()()(
SISTEMAS NÃO-LINEARES nxnMÉTODO DE NEWTON
O modelo local linear do sistema não-linear é
Seja , então
Passo 1: Dado , calcule e .Passo 2: Resolve-se o sistema linear .
Neste ponto técnicas de fatoração, pivoteamento e métodos iterativos podem ser utilizadas para determinar .
O Método de Newton com resolução do sistema linear de modo iterativo é chamado de Método de Newton Inexato.
)()()()( 0)( kkkkkkk xFxxxJxxxJxFxL
kkkkk sxxsxx 1
)()( kkk xFsxJ
kx )(kxJ
ks
kk sxx
)(kxF
SISTEMAS NÃO-LINEARES nxn
Comentário 1: Estudaremos os métodos para sistemas não-lineares são iterativos. Dado inicial, gera-se uma seqüência , de modo que
Comentário 2: Critérios de parada
a) norma dos vetores de .
b) norma infinito.
c) tolerância ou número máximo de iterações.
kxF
)0(x )(kx
xxLim k
k
)(
F
ki
ki
kk xxxx 11 max
2010
kxF
SISTEMAS NÃO-LINEARES nxn
MÉTODO DE NEWTON INEXATOAlgoritmo. Dados , , , faça:
Passo1: Calcule e .
Passo 2: Se , faça e pare. Senão,
Passo 3: Obtenha , solução de
Passo 4: Faça
Passo 5: Se faça e pare. Senão
Passo 6: Faça e volte ao passo 1.
kk xFsxJ )(
kxx 1)( kxF
0x
)(kxJ
ks
01 02
)(kxF
kkk sxx 1
2
1 kk xx 1 kxx
1kk
MÉTODO DE NEWTON – Exemplo
Resolva o sistema .
Sabemos que as soluções são
Tomamos , e calculando o
Jacobiano, obtemos .
09
3)(
22
21
21
xx
xxxF
.3
0e
0
3
xx
421 10
5
10x
21 22
11)(
xxxJ
MÉTODO DE NEWTON – Exemplo
Iteração 1:
continue!
métodos diretos ou iterativos
e
continue!!!!!!
17
3
5
1)( 0 FxF
41017kxF
0k
102
11
5
1)( 0 JxJ
17
3
102
110
2
01
s
s
8/11
8/130
2
01
s
s
8/29
8/5
8/11
8/13
5
1001 sxx
401 10625.18/13xx
MÉTODO DE NEWTON – Exemplo
Passo 1:
Comentário: Note que no processo de resolução de sistemas não-lineares, devemos resolver um sistemalinear a cada iteração.
Métodos diretos: Eliminação de Gauss com pivoteamento parcial ou total, fatoração LU ou Cholesky.....
Métodos iterativos: Método de Gauss-Jacobi o Gauss-Seidel
0k
MÉTODO DE NEWTON – Exemplo
CONTINUANDO. Iteração 2:
continue
e
continue!!!!!!
32/145
0
8/29
8/5)( 1 FxF
4105313.432/145kxF
1k
4/294/5
11
8/29
8/5)( 1 JxJ
32/145
0
4/294/5
111
2
11
s
s
533.0
533.01
2
11
s
s
0917.3
092.0
533.0
533.0
625.3
625.0112 sxx
412 10533.0xx
MÉTODO DE NEWTON – Exemplo
1-Continuar o processo até que um dos dois critérios de
parada seja atingido, ou seja
ou
2-Convergência do Método de Newton Inexato é
Quadrática em condições adequadas.
3-Diferentes abordagens do Método de Newton Inexato
geram algoritmos alternativos.
kxF
kk xx 1
MÉTODO DE NEWTON MODIFICADO
O Método de Newton Modificado consiste em
tomar a cada iteração, sempre, , em vez
de . O método iterativo é dado pela
seqüência .
Neste procedimento temos que resolver no
passo o sistema linear:
0xJ kxJ
kkk sxx 1
k kxFsxJ )0(
MÉTODO DE NEWTON MODIFICADO
O Método de Newton Modificado tem a vantagem de calcular uma única vez a matriz Jacobiana .
No caso de resolver por fatoração LU, os fatores L e U também serão calculados uma única vez.
0xJ
MÉTODO DE NEWTON MODIFICADO– EXEMPLO
Resolva o sistema .
Sabemos que as soluções são
Tomamos , e calculando o
Jacobiano, obtemos . Fixado!!!!
09
3)(
22
21
21
xx
xxxF
.3
0e
0
3
xx
421 10
5
10x
21 22
11)(
xxxJ
MÉTODO DE NEWTON MODIFICADO
Iteração 1:
continue!
métodos diretos ou iterativos
e
continue!!!!!!
17
3
5
1)( 0 FxF
41017kxF
0k
102
11
5
1)( 0 JxJ
17
3
102
110
2
01
s
s
8/11
8/130
2
01
s
s
8/29
8/5
8/11
8/13
5
1001 sxx
401 10625.18/13xx
MÉTODO DE NEWTON MODIFICADO
Iteração 2:
continue
Diferença e
continue!!!!!!
32/145
0
8/29
8/5)( 1 FxF
4105313.432/145kxF
1k
102
11)( 0xJ
32/145
0
102
111
2
11
s
s
5664.0
5664.01
2
11
s
s
0586.3
0586.0
5664.0
5664.0
625.3
625.0112 sxx
412 105664.0xx
MÉTODO DE NEWTON
CONVERGÊNCIA
O Método de Newton Modificado, Inexato, perde a propriedade de convergência quadrática, apesar que neste exemplo, aparentemente, o nível de convergência foi semelhante.Verifica-se que o Método de Newton Modificado converge linearmente.
MÉTODOS DE QUASE-NEWTON
Os Métodos de Quase-Newton, Inexatos,
consistem em gerar seqüências , com
Boas propriedades de convergência, sem ter
que avaliar (calcular) a matriz Jacobiana a cada
iteração.
)(kx
MÉTODOS DE QUASE-NEWTON
No Método de Newton Inexato a seqüência é
gerada por
onde é a solução do sistema linear
A idéia é impor condições sobre gerando
a) algum princípio de variação mínima.
b) preservar alguma estrutura (simetria, esparsidade,..) da matriz Jacobiana.
)()()()( 0)( kkkkkkk xFxxxBxxxJxFxL
ks
kk sxx
)(kx
)(kxB )(kxJ
