Eq nao lin

1. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Capítulo 4 - Equações Não-Lineares
Carlos Balsa
[email protected]
Departamento de Matemática
Escola Superior de Tecnologia e Gestão de Bragança
2
o
Ano - Eng. Civil, Química e Gestão Industrial
Carlos Balsa Métodos Numéricos 1/ 24

2. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Outline
1
Equações Não-Lineares
Equações Não-Lineares
Soluções e Sensibilidade
Convergência
2
Métodos Numéricos para uma Dimensão
Método da Bissecção
Método de Newton-Raphson
3
Sistemas de Equações Não-Lineares
Método de Newton
Carlos Balsa Métodos Numéricos 2/ 24

3. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Equações Não-Lineares
Soluções e Sensibilidade
Convergência
Equações Não-Lineares
Dada uma funçãof, procuramosx, tal que
f(x) =0
Soluçãoxé f
Pelo que o problema é conhecido como
equação ou
Carlos Balsa Métodos Numéricos 3/ 24

4. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Equações Não-Lineares
Soluções e Sensibilidade
Convergência
Equações Não-Lineares
Dois casos importantes
Equação não-linear única sobre uma única incógnita, em que
f:IR!IR
Solução é o escalarxpara o qualf(x) =0
Sistema denequações simultâneas emnincógnitas, em que
f:IR
n
!IR
n
Solução é o vectorxpara o qual todas as componentes def
são nulas simultâneamente,f(x) =0
Carlos Balsa Métodos Numéricos 4/ 24

5. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Equações Não-Lineares
Soluções e Sensibilidade
Convergência
Existência e Unicidade da Solução
Existência e unicidade da solução são mais difíceis de averiguar
para equações não-lineares em comparação com as equações
lineares
Sefé contínua e sinal(f(a))6=sinal(f(b)), então o Teorema do
Valor Médio implica que existax

2[a;b]tal quef(x

) =0
Não existe um resultado análogo tão simples para o caso den
dimensões
Carlos Balsa Métodos Numéricos 5/ 24

6. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Equações Não-Lineares
Soluções e Sensibilidade
Convergência
Exemplos: Uma Dimensão
Equações não-lineares podem ter um numero variado de
soluções
exp(x) +1=0 não tem solução exp(x)x=0 tem uma solução x
2
4 sin(x) =0 tem duas solução x
3
6x
2
+11x6=0 tem três solução sin(x) =0 tem innitas solução
Carlos Balsa Métodos Numéricos 6/ 24

7. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Equações Não-Lineares
Soluções e Sensibilidade
Convergência
Multiplicidade
Sef(x

) =f
0
(x

) =f
00
(x

) =: : :=f
(m1)
(x

) =0 mas
f
(m)
(x

)6=0, então a raizxtem m
Sem=1 (f(x

) =0 ef
0
(x

)6=0), entãox

é uma raiz
Carlos Balsa Métodos Numéricos 7/ 24

8. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Equações Não-Lineares
Soluções e Sensibilidade
Convergência
Sensibilidade e Condicionamento
Numero de condição do problema de cálculo da raízesx

de
f:IR!IRé 1=jf
0
(x

)j
Raiz é mal condicionada se a linha tangente for
aproximadamente horizontal
Em particular, raízes múltiplas (m>1) são mal condicionadas Numero de condição do problema de cálculo da raízesx

de
f:IR
n
!IR
n
é


J
1
f
(x

)


, comJfa matriz Jacobiana dej,
fJf(x)g
ij
=@fi(x)=@xj
Raiz mal condicionada se a matriz Jacobiana for
aproximadamente singular
Carlos Balsa Métodos Numéricos 8/ 24

9. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Equações Não-Lineares
Soluções e Sensibilidade
Convergência
Sensibilidade e Condicionamento
Bem Condicionado Mal Condicionado
Carlos Balsa Métodos Numéricos 9/ 24

10. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Equações Não-Lineares
Soluções e Sensibilidade
Convergência
Sensibilidade e Condicionamento
Que entendemos por solução aproximada de um sistema
não-linear,
kf(^x)k 0 ou k^xx

k 0?
Primeira medida corresponde a um “resíduo pequeno”, segunda
mede a proximidade em relação à (geralmente desconhecida)
solução verdadeirax

Critérios de solução não são necessariamente pequenos em
simultâneo
Resíduo pequeno implica solução exacta apenas se o problema
for bem condicionado
Carlos Balsa Métodos Numéricos 10/ 24

11. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Equações Não-Lineares
Soluções e Sensibilidade
Convergência
Taxa de Convergência, continuação
Para um método iterativo genérico, dene-se o erro na iteração
kpor
ek=xkx

em quexké a solução aproximada ex

a solução verdadeira
Para métodos que mantêm o intervalo onde se situa a solução
conhecido, em vez de se utilizar uma aproximação especica à
solução verdadeira, considera-se que o erro é igual ao
comprimento do intervalo que contém a solução
Sequência dos erros converge com uma taxarse
lim
k!1
kek+1k
kekk
r
=C
para alguma constante nita e não-nulaC
Carlos Balsa Métodos Numéricos 11/ 24

12. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Equações Não-Lineares
Soluções e Sensibilidade
Convergência
Taxa de Convergência, continuação
Alguns casos particulares com interesse
r=1: C<1) r>1: r=2:
Taxa de convergênciaDígitos ganhos por iteração
linear constante
superlinear aumenta
quadrática duplica
Carlos Balsa Métodos Numéricos 12/ 24

13. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Método da Bissecção
Método de Newton-Raphson
Método da Bissecção
Método da
meio o intervalo onde está situada a raiz até que a solução seja
isolada com a correcção pretendida
ALGORITMO: MÉTODO DABISSECÇÃO
Input:aebtal quex

2[a;b]
Output:^x(solução aproximada)
while((ba)>tol)
m= (a+b)=2
sef(a)f(b)>0
a=m
else
b=m
end
end
Carlos Balsa Métodos Numéricos 13/ 24

14. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Método da Bissecção
Método de Newton-Raphson
Exemplo: Método da Bissecção
Aproxime, com uma exactidão de duas casas decimais (tol0:5e2),
a raiz da equação
f(x) =x
2
4 sin(x) =0
sabendo quex

2[1;3]
Vericamos quef(1) =2:365884 e quef(3) =8:435520
k a b m f (m) x
0 1 3 2 0.362810
1 1 2 1.5 -1.739980
2 1.5 2 1.75 -0.873444
3 1.75 2 1.875 -0.300718
4 1.875 2 1.9375 0.019849
5 1.875 1.9375 1.906250 -0.143255 0.125
6 1.906250 1.9375 1.929688 -0.143255 0.0625
7 1.921875 1.9375 1.929688 -0.021454 0.0313
7 1.929688 1.9375 1.933594 -0.000846 0.0156
8 1.933594 1.9375 1.935547 0.009491 0.0079
9 1.933594 1.935547 0.0040 <tol
Carlos Balsa Métodos Numéricos 14/ 24

15. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Método da Bissecção
Método de Newton-Raphson
Método da Bissecção, continuação
Método da bissecção converge de certeza, mas é lento
Em cada iteração o cumprimento do intervalo contendo a
solução é reduzido a metade, taxa de convergência é,
comr=1 eC=0:5
Dado um intervalo de partida[a;b], o cumprimento do intervalo
depois dekiterações é(ba)=2
k
, pelo que a redução do erro
abaixo de certo valortolimplica que
klog
2

ba
tol

independentemente da funçãofenvolvida
Carlos Balsa Métodos Numéricos 15/ 24

16. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Método da Bissecção
Método de Newton-Raphson
Método de Newton-Raphson
Desenvolvimento de uma função em Série de Taylor
f(x+h)f(x) +f
0
(x)h+f
00
(x)
h
2
2!
+f
000
(x)
h
3
3!
+: : :
Truncando a série de Taylor a partir do termo de primeira ordem
f(x+h)f(x) +f
0
(x)h
obtemos uma função linear emhque aproximafem torno dex
Substituindo a função não-linear pela função linear, cujo zero é
h=f(x)=f
0
(x), obtemos uma aproximação do zero def
Como os zeros das duas funções não são exactamente os
mesmo repete-se este processo sucessivamente, originando o
método de
xk+1=xk
f(xk)
f
0
(xk)
Carlos Balsa Métodos Numéricos 16/ 24

17. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Método da Bissecção
Método de Newton-Raphson
Método de Newton-Raphson, continuação
Método de Newton-Raphson aproxima a função não-linearf, na
vizinhança dexk, pela f(x) Carlos Balsa Métodos Numéricos 17/ 24

18. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Método da Bissecção
Método de Newton-Raphson
Exemplo: Método de Newton-Raphson
Aproximar com uma exactidão de duas casas decimais (tol0:5e2)
a raiz da equação
f(x) =x
2
4 sin(x) =0
sabendo quex

2[1;3]
Derivada é
f
0
(m) =2x4 cos(x)
pelo que o esquema iterativo é
xk+1=xk
x
2
k4 sin(xk)
2xk4 cos(xk)
Escolhendox0=3 como valor de partida, obtemos
k x f (x) f
0
(x) h x
0 3.000000 8.435520 9.959970 -0.846942
1 2.153058 1.294772 6.505771 -0.199019 0.846942
2 1.954039 0.108438 5.403795 -0.020067 0.199019
3 1.933972 0.001152 5.288919 -0.000218 0.020067
4 1.933754 0 :000218<tol
Carlos Balsa Métodos Numéricos 18/ 24

19. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Método da Bissecção
Método de Newton-Raphson
Convergência do Método de Newton-Raphson
Para raízes simples (f(x

) =0 ef
0
(x

)6=0) a convergência do
método de Newton-Raphson é r=2)
Mas as iterações tem de ser iniciadas sucientemente próximas
da raiz para convergir
No caso de raízes múltiplas, a convergência é apenas linear,
com constanteC=1(1=m), em quemé multiplicidade da raiz
k f(x) =x
2
1f(x) =x
2
2x+1
0 2.0 2.0
1 1.25 1.5
2 1.025 1.25
3 1.0003 1.125
4 1.00000005 1.0625
5 1.0 1.03125
Carlos Balsa Métodos Numéricos 19/ 24

20. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Método de Newton
Sistemas de Equações Não-Lineares
Resolução de sistemas de equações não-lineares é mais difícil
do que resolver uma única equação porque
Existe uma maior variedade de comportamento, pelo que a
determinação da existência e do numero de soluções ou uma
boa estimativa inicial é muito mais complicado
Em geral, não existe uma maneira simples de garantir a
convergência para a solução pretendida ou simplesmente de a
localizar a solução
Numero de cálculos a efectuar cresce rapidamente com a
dimensão do problema
Carlos Balsa Métodos Numéricos 20/ 24

21. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Método de Newton
Método de Newton
Parandimensões, o
xk+1=xkJ(xk)
1
f(xk)
em queJ(xk)é a matriz Jacobiana def
fJ(x)g
ij
=@fi(x)=@xj
Na pratica, não se inverte explicitamente a matrizJ(xk), em vez
disso resolve-se o sistema linear
J(xk)k=f(xk)
em ordem ao passoke denimos a nova iteração como
xk+1=xk+k
Carlos Balsa Métodos Numéricos 21/ 24

22. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Método de Newton
Exemplo: Método de Newton
Aproximar a solução do sistema não-linear
f(x) =0,

x1+2x22
x
2
1
+4x
2
2
4

=

0
0

efectuando duas iterações do método de Newton
Matriz Jacobiana é
Jf(xk) =
"
@f1(x1;x2)
@x1
@f1(x1;x2)
@x2
@f2(x1;x2)
@x1
@f2(x1;x2)
@x2
#
=

1 2
2x18x2

PRIMEIRA ITERAÇÃO: Escolhendox0= [1 2]
T
como
aproximação inicial obtemos
f(x0) =

3
13

;Jf(x0) =

1 2
2 16

Carlos Balsa Métodos Numéricos 22/ 24

23. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Método de Newton
Exemplo, continuação
Resolução do sistema linear

1 2
2 16

0=

3
13

origina0=

1:83
0:58

, pelo quex1=x0+0=

0:83
1:42

SEGUNDA ITERAÇÃO : Recalculando para um novo ponto
f(x1) =

0
4:72

;Jf(x1) =

1 2
1:67 11:3
Resolução do sistema linear

1 2
1:67 11:3

1=

0
4:72

obtemos1= [0:640:32], pelo que
x2=x1+1= [0:19 1:10]
T
(continuando a iterar iriamos
aproximar-nos dex

= [0 1]
T
)
Carlos Balsa Métodos Numéricos 23/ 24

24. Equações Não-Lineares
Métodos Numéricos para uma Dimensão
Sistemas de Equações Não-Lineares
Método de Newton
Critério de paragem
Na prática, os dois critérios de paragem mais usuais são:
Erro: impondo que uma certa aproximação do erro
absoluto seja inferior a um valor tolerado
kxk+1xk+1k=kkk<tol
ou então impondo o mesmo critério ao erro relativo
aproximado
kxk+1xk+1k
kxk+1k
=
kkk
kxk+1k
<tol
Resíduo: em vez de obter uma aproximação do erro,
verica-se a proximidade de zero da norma da função
kf(xk+1)k<tol
sabendo que este critério é um bom indicador da
proximidade da solução apenas quando o problema é bem
condicionado
Carlos Balsa Métodos Numéricos 24/ 24