Equações não lineares
Elementos de Análise Numérica
Resolução de equações não lineares
Pontos mais importantes:
-número de raízes
-métodos iterativos
-ordem de convergência
-métodos intervalares
-bissecções sucessivas
-falsa posição
-métodos abertos
-iteração de ponto fixo
-Newton-Raphson
-Secante
-critérios de paragem
-caso especial: multiplicidade de zeros
1
Elementos de Análise Numérica
Equações não lineares
Raízes das funções
Raíz(es):
f(x)=ax2+bx+c
f(x)=log(2x)+sinh(3x)
x= ? tal como f(x)=0
x= ? tal como f(x)=0
explícito
implícito
métodos numéricos
2
Elementos de Análise Numérica
Equações não lineares
ct

gm
v( t ) 
(1  e m )
c
-exemplo de queda livre:
velocidade, m/s
m=0.5 kg, c=0.29, g=9.81 m/s2
18
16
14
12
analitica
10
8
numérica (dt=1 sec)
6
numérica (dt=0.5 sec)
4
2
0
0
2
4
6
8
10
12
tempo, s
ct

gm
- se for c uma incognita? -------> f (c) 
(1  e m )  v  0
c
3
Elementos de Análise Numérica
Equações não lineares
Exemplos de problemas em engenharia
Lei fundamental
B. térmico
B. mássico
B. de força
B. de energia
Leis de Newton
var. dep.
T
C
F
E
a, v
var. indep.
t,x,y,z
t,x,y,z
t,x,y,z
t,x,y,z
t,x,y,z
parâmetros
, k, , etc.
D, etc.
E, etc.
, k, , etc.
m, c, etc
4
Equações não lineares
Elementos de Análise Numérica
Número de zeros
-f(x) é uma função contínua no intervalo [a,b], o número de zeros é:
-ímpar (pelo menos uma) se f(a)*f(b)<0
-par (pode ser 0) se f(a)*f(b)>0
-se mais do que um f ’(x) também tem pelo menos uma raíz
5
Elementos de Análise Numérica
Equações não lineares
Métodos iterativos
-carácter iterativo: a partir de alguns valores iniciais (x1, x2,...xs-1)
da raiz (z) construímos uma nova aproximação xs supostamente
melhor:
lim x k  z
k 
ou
lim e k  0
k 
6
Elementos de Análise Numérica
Equações não lineares
Ordem (velocidade) de convergência
-comparação de dois métodos iterativos: se xk e Xk convergem
para o mesmo limite, e:
Xk  z
lim
0
k  x  z
k
Xk converge mais rapidamente.
-ordem de convergência (p):
0 m
e k 1
ek
p
M
-comentários:
ou
e k+1 ~ c e k
p
com k  
-quanto maior for p mais rápida a convergência
-p=1 -----------> M<1
-p>1 -----------> e0 suficientemente pequeno
7
Equações não lineares
Elementos de Análise Numérica
Métodos de localização de zeros
1, Métodos intervalares: -mudança de sinais na vizinhança de zero
-duas estimativas iniciais
-método gráfico
-bissecções sucessivas
-falsa posição
8
Elementos de Análise Numérica
Equações não lineares
Método gráfico
ct
-exemplo de queda livre:
f(c)

gm
f (c) 
(1  e m )  v  0
c
6
5
4
3
c
2
1
0
0
-1
0.1
0.2
0.3
0.4
0.5
c
9
Elementos de Análise Numérica
Equações não lineares
Bissecções Sucessivas (BS)
-f é uma função contínua no intervalo [a,b] e f(a)*f(b)<0; existe pelo
menos um zero neste intervalo.
-divisões sucessivas a meio de [a,b] para subintervalos [ak,bk] tal que
f(ak)*f(bk)<0.
Algoritmo:
1. passo: escolha xl (limite inferior) e xu (limite superior) tal que
f(xl)*f(xu)<0
2. passo:
3. passo:
xl  x u
xr 
2
a, se f(xl)*f(xr)<0 -----> xu = xr
b, se f(xu)*f(xr)<0 -----> xl = xr
c, se f(xu)*f(xr)=0 -----> z= xr , fim
4. passo: volta 2.
10
Elementos de Análise Numérica
Equações não lineares
Exemplo queda livre:
ct

gm
f (c) 
(1  e m )  v  0
c
k
1
2
3
4
5
6
7
8
9
10
c_l
0.1000
0.1000
0.1000
0.2125
0.2688
0.2969
0.2969
0.2969
0.3004
0.3004
f(c_l)
8.5308
8.5308
8.5308
3.0324
1.0121
0.1393
0.1393
0.1393
0.0359
0.0359
c_u
1.0000
0.5500
0.3250
0.3250
0.3250
0.3250
0.3109
0.3039
0.3039
0.3021
m= 0,5 kg; t= 3s; v= 13,6 m/s
f(c_u)
-8.7072
-5.0107
-0.6549
-0.6549
-0.6549
-0.6549
-0.2671
-0.0663
-0.0663
-0.0153
c_r
0.5500
0.3250
0.2125
0.2688
0.2969
0.3109
0.3039
0.3004
0.3021
0.3013
f(c_r)
-5.0107
-0.6549
3.0324
1.0121
0.1393
-0.2671
-0.0663
0.0359
-0.0153
0.0103
e_a, %
-69.23
-52.94
20.93
9.47
4.52
-2.31
-1.17
0.58
-0.29
c= 0,3013 (ea=-0,29%)
11
Elementos de Análise Numérica
Equações não lineares
c estimado
0.6000
0.5000
0.4000
f(c_r)
0.3000
4.0000
0.2000
3.0000
2.0000
0.1000
1.0000
0.0000
0.0000
0
2
4
6
8
10
12
k
-1.0000
0
2
4
6
8
10
-2.0000
-3.0000
erro estimado, %
-4.0000
-5.0000
80.00
-6.0000
70.00
60.00
50.00
40.00
30.00
20.00
10.00
0.00
0
1
2
3
4
5
6
7
8
9
10
k
12
k
12
Equações não lineares
Elementos de Análise Numérica
-explicação gráfica: http://www.cse.illinois.edu/iem/nonlinear_eqns/Bisection/
Critério de paragem
xrnovo  xranterior
ea 
*100
novo
xr
1,
2,
E k 1
1
1
 a k  bk  Ek
2
2
E k+1 1
0

Ek
2
- convergência linear (p=1)
- c=0.5
13
Elementos de Análise Numérica
Equações não lineares
Falsa Posição(FAP)
-o método de BS não utiliza a informação sobre o valor f(a) e f(b)
xl
f(xu)
xr
f(x l )
f(x u )
=
xl  x r x u  x r
ou
f(xl)
z
xu
f(xr)
xr =
x u f ( xl )  xl f ( x u )
f ( xl )  f ( x u )
f ( x u )( x l  x u )
ou x r = x u 
f ( xl )  f ( x u )
-algoritmo igual a BS excepto passo 2.
14
Elementos de Análise Numérica
Equações não lineares
Características do método FAP
-só um dos limites são alterados: -função convexa: xl
-função côncava: xu
-no caso de conv., o limit [xl, xu] aproxima uma constante com k-->inf.:
-função convexa: xu-z
-função côncava: xl-z
-ordem de convergência:
-p=1
-c<1
-normalmente mais rápido que BS mas não sempre (exemplo: f(x)=x10-1)
Critério de paragem
anterior
x novo

x
r
ea  r
*100
novo
xr
f(x)<e
15
Elementos de Análise Numérica
Equações não lineares
ct
Exemplo queda livre:
k
1
2
3
4
5
6
7
8
9
10
c_l
0.1000
0.1000
0.1000
0.1000
0.1000
0.1000
0.1000
0.1000
0.1000
0.1000

gm
f (c) 
(1  e m )  v  0
c
f(c_l)
8.5308
8.5308
8.5308
8.5308
8.5308
8.5308
8.5308
8.5308
8.5308
8.5308
c_u
1.0000
0.5454
0.3819
0.3272
0.3096
0.3041
0.3024
0.3019
0.3017
0.3016
f(c_u)
-8.7072
-4.9475
-2.0552
-0.7133
-0.2305
-0.0727
-0.0227
-0.0071
-0.0022
-0.0007
m= 0,5 kg; t= 3s; v= 13,6 m/s
c_r
0.5454
0.3819
0.3272
0.3096
0.3041
0.3024
0.3019
0.3017
0.3016
0.3016
f(c_r)
-4.9475
-2.0552
-0.7133
-0.2305
-0.0727
-0.0227
-0.0071
-0.0022
-0.0007
-0.0002
e_a, %
42.81
16.73
5.66
1.81
0.57
0.18
0.06
0.02
0.01
c= 0,3016 (ea=0,01%)
16
Elementos de Análise Numérica
Equações não lineares
c_r
0.6000
0.5500
0.5000
0.4500
0.4000
0.3500
f(c_r)
0.3000
k
0.0000
0.2500
0
2
4
6
8
10
0.2000
0
2
4
6
8
10
12
-1.0000
k
-2.0000
e_a, %
45
-3.0000
40
35
-4.0000
30
25
-5.0000
20
15
10
5
0
1
2
3
4
5
6
7
8
9
10
k
17
12
Equações não lineares
Elementos de Análise Numérica
Métodos de localização de zeros
1, Métodos abertos:
-uma ou duas estimativas iniciais
-Iteração de ponto fixo
-Newton-Raphson
-Secante
18
Elementos de Análise Numérica
Equações não lineares
Iteração de ponto fixo(IPF)
-métodos iterativos em forma geral:
xk+1=G(xk)
-no caso de convergência (f(z))=0:


z  lim x k 1  lim(G( x k ))  G lim( x k )  G(z)
k 
k 
k 
ou seja
z=G(z)
-o ponto z é um ponto que a função G transforma-se nela própria.
-em geral, para uma dada f(x)=0 é possível escolher várias G(x)
-x=x+f(x)=G(x)
f(x)=sin(x) ---> G(x)=sin(x)+x
-outros exemplos para f(x)=x3-x-1, G(x)=:
x  x 1
3
1
ou x = 2
x 1
ou
x = 3 x +1
19
Elementos de Análise Numérica
Equações não lineares
Convergência de IPF
-não é sempre convergente para a solução
-critério de convergência:
xk+1=G(xk)
e
z=G(z)
z- xk+1= G(z)- G(xk)
aplicando o teorema do valor médio conduz-nos a:
G( x k )  G( z)
G  ( ) 
xk  z
com  (x k  z)
e
z- xk+1= (z- xk)G´ () ou Ek+1= G´() Ek
---->
|G´()|<1
-convergência linear (p=1),
lim
k 
E k 1
Ek
 lim G ()  G ( z)
k 
onde
G  ( z)  0
20
Elementos de Análise Numérica
Equações não lineares
0<G´(x)<1
y
y=x
y
y=G(x)
0>G´(x)>-1
y=x
y=G(x)
x2 x1
x0
x1
x
y=G(x)
y
y
y=x
x
x0
x2
G´(x)<-1
y=x
y=G(x)
x0 x1
G´(x)>1
x
x0
x1
x2
x
21
Elementos de Análise Numérica
Equações não lineares
ct

gm
f (c) 
(1  e m )  v  0
c
c t
 k
gm
c k 1  G (c k ) 
(1  e m )
v
Exemplo:
k
1
2
3
4
5
6
7
8
9
10
c_k
0.1000
0.1627
0.2248
0.2671
0.2880
0.2966
0.2998
0.3010
0.3014
0.3015
f(c_k)
8.5308
5.1885
2.5559
1.0674
0.4054
0.1475
0.0527
0.0188
0.0067
0.0024
m= 0,5 kg; t= 3s; v= 13,6 m/s
c_k+1=G(c_k)
0.16273
0.22481
0.26706
0.28802
0.29660
0.29982
0.30098
0.30139
0.30154
0.30159
e_a, %
27.62
15.82
7.28
2.89
1.07
0.39
0.14
0.05
0.02
c= 0,3016 (ea=0,02%)
22
Elementos de Análise Numérica
Equações não lineares
c_k
0.3500
0.3000
0.2500
0.2000
0.1500
0.1000
f(c_k)
9.0000
0.0500
0.0000
0
2
4
6
8
10
12
8.0000
k
7.0000
6.0000
5.0000
4.0000
3.0000
e_a 30.00
2.0000
25.00
1.0000
20.00
0.0000
0
15.00
10.00
5.00
0.00
0
2
4
6
8
10
k
2
4
6
8
10
12
Elementos de Análise Numérica
Equações não lineares
Método de Newton-Raphson(NR)
-talvez o mais popular, só precisamos de uma (boa) estimativa inicial
-algoritmo:
1, escolha x0
2,
x k 1  x k 
f (xk )
f ( x k )
3, continua 2 até que o critério de paragem seja satisfeito
Expansão de Taylor:
f (xk 1 )  f (xk )  f (1) (xk )(xk 1  xk )  0
f(x0)
x2 x1
x0
24
Elementos de Análise Numérica
Equações não lineares
Convergência de NR
aproximação:
exacto:
subtracção:
f ( xk 1 )  f (xk )  f (1) (xk )( xk 1  xk )
f ( 2 ) ( )
(1)
0  f ( x k )  f ( x k )( z  x k ) 
(z  xk )2
2
(2)
f
( )
(1)
0  f ( x k )( z  x k 1 ) 
(z  xk )2
2
f ( 2 ) ( )
( E k 1 )  f ( 2) ( z)
2
0  f ( x k )( E k 1 ) 
( E k ) ou

2
( E k ) 2 2f (1) ( z)
(1)
-não converge sempre (exemplos gráficos)
f ( x )f ( x )
 c 1
2

(f ( x ))
http://www.cse.illinois.edu/iem/nonlinear_eqns/Newton/
-não é conveniente programar a derivada
25
Elementos de Análise Numérica
Equações não lineares
ct
Exemplo:

gm
f (c) 
(1  e m )  v  0
c
m= 0,5 kg; t= 3s; v= 13,6 m/s
c t
c t
 k 
gt  mk gm 
f (ck )  e  2 1  e m 
ck
ck

k
1
2
3
4
5
6
7
8
9
10
c_k
0.1000
0.2427
0.2960
0.3016
0.3016
0.3016
0.3016
0.3016
0.3016
0.3016
f(c_k)
8.531
1.900
0.164
0.002
0.000
0.000
0.000
0.000
0.000
0.000
f ' (c_k)
-59.79
-35.59
-29.67
-29.12
-29.12
-29.12
-29.12
-29.12
-29.12
-29.12
c= 0,3016 (ea=0,00%)
c_k+1
0.2427
0.2960
0.3016
0.3016
0.3016
0.3016
0.3016
0.3016
0.3016
0.3016
e_a
18.03
1.83
0.02
0.00
0.00
0.00
0.00
0.00
0.00
26
Elementos de Análise Numérica
Equações não lineares
Método de Secante (SEC)
-duas estimativas iniciais, modificação de NR
-algoritmo:
1, escolha x0 e x1
2,
x k 1
f ( x k )( x k 1  x k )
 xk 
f ( x k 1 )  f ( x k )

f ( x k 1 )  f ( x k ) 
 f (x k ) 

(
x

x
)


k 1
k
3, continua 2 até o critério de paragem ser satisfeito
f(x0)=a* x0 +b
f(x1)=a* x1 +b
0=a x2 +b
f(x0)
x2 x1 x0
27
Elementos de Análise Numérica
Equações não lineares
Convergência de SEC
-pode ser demonstrado que o erro Ek+1:
E k 1
f ( k )

E k E k-1
2 f ( k )
E k 1
M2

E E
2 m1 k k-1
M2
onde M =
2 m1
ou u k +1  u k u k-1
; u k  ME k
; u 0  1 ; u1    1
-ordem de convergência p é apróx. 1.618
-diferenças entre os métodos de FAP e SEC
28
Elementos de Análise Numérica
Equações não lineares
f ( x u )(x l  x u )
f (x l )  f (x u )
FAP:
xr = x u 
SEC:
x k 1  x k 
f ( x k )(x k 1  x k )
f ( x k 1 )  f ( x k )
-explicação gráfica: http://www.cse.illinois.edu/iem/nonlinear_eqns/Secant/
29
Elementos de Análise Numérica
Equações não lineares
ct

gm
f (c) 
(1  e m )  v  0
c
Exemplo:
k
1
2
3
4
5
6
7
8
9
10
c_k-1
0.1000
0.0900
0.2400
0.2819
0.2996
0.3016
0.3016
0.3016
0.3016
0.3016
f(c_k-1)
8.531
9.140
1.996
0.594
0.058
0.002
0.000
0.000
0.000
0.000
c_k
0.0900
0.2400
0.2819
0.2996
0.3016
0.3016
0.3016
0.3016
0.3016
#DIV/0!
f(c_k)
9.140
1.996
0.594
0.058
0.002
0.000
0.000
0.000
0.000
#DIV/0!
m= 0,5 kg; t= 3s; v= 13,6 m/s
c_k+1
0.2400
0.2819
0.2996
0.3016
0.3016
0.3016
0.3016
0.3016
#DIV/0!
#DIV/0!
f(c_k+1)
-38.00
-6.841
-1.701
0.1081
0.2953
0.3016
0.3016
0.3016
#DIV/0!
#DIV/0!
e_a, %
14.87
5.93
0.63
0.02
0.00
0.00
0.00
#DIV/0!
#DIV/0!
c= 0,3016 (ea= 0,00%)
30
Equações não lineares
Elementos de Análise Numérica
Critérios de paragem
1, Número de iterações:
k<kmax
2, Valor da função:
f(x)<e
3, Amplitude de intervalo: [xl,xu]<
4, Diferença entre it. consecutivas:
x novo  x anterior
x
novo
e
31
Elementos de Análise Numérica
Equações não lineares
Sumário
Método
Função
Nº X 0
Ordem de
conv.
Conv.
2
1
sempre
2
1
sempre
1
1
|G´(  )|<1
1
2
f ( x ) f  ( x )
 k 1
( f  ( x )) 2
2
1<p<2
Intervalares:
BS
FP
xr 
xr = xu 
xl  xu
2
f (xu )(xl  xu )
f (xl )  f (xu )
Abertos:
IPF
NR
SEC
x k+1 =G(x k )
x k 1  x k 
x k 1  x k 
f (xk )
f ( x k )
f ( x k )( x k  1  x k )
f ( x k 1 )  f ( x k )
u k +1  u k u k -1
32
Elementos de Análise Numérica
Equações não lineares
100
10
1
80
BS
FP
IPF
NR
SEC
70
60
50
e_a, %
e_a, %
0.1
0.01 0
2
4
6
8
10
12
0.001
0.0001
BS
FP
IPF
NR
SEC
0.00001
0.000001
0.0000001
0.00000001
0.000000001
k
40
30
20
10
0
-10 0
2
4
6
8
10
12
k
33