Download - Aula_7_Métodos numéricos(Descida máxima)
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 1/17
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 2/17
2- Sistemas Não Lineares de Equações
Considere um sistema não linear de n equações com nincógnitas.
Note que como caso particular podemos ter um sistema
linear de equações algébricas:
( , , , )
( , , , ) ou com e
( , , , )
n
n
n nn n
f x x x f x
f x x x f x
f x f x x x
=⎧ ⎡ ⎤ ⎡ ⎤
⎪ ⎢ ⎥ ⎢ ⎥=⎪ ⎢ ⎥ ⎢ ⎥= = =⎨ ⎢ ⎥ ⎢ ⎥⎪ ⎢ ⎥ ⎢ ⎥⎪ = ⎣ ⎦ ⎣ ⎦⎩
f(x) 0 f x
1 1 2 1 1
2 1 2 2 2
1 2
0
0
0
11 1 12 2 1 1
2
1 1 2
2 1 2 1 1 22 2 2 2
1 1 2 21 2
( , , , )
( , , , ) ou
( ,
0
0
, , ) 0
n n
n n
n n nn n
n
n
n nn
a x a x a x b
a x a
f x x x
f x x x x a x b
a x a x f x b x x a x
+ + − =+ + − =
− =
=⎧⎪ =⎪⎨⎪⎪⎩ += + − =
Ax b 0
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 3/17
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 4/17
2.2- Método da Iteração
sistema em , então . O Método da Iteração pode seraplicado também a sistemas de equações na forma:
onde é uma função vetor definida e contínua numavizinhança de uma raiz isolada deste sistema. Entre as
varias maneiras de transformar o sistema (3) no (1)
destacamos a seguinte. Reescreva o sistema (3) na forma
onde é uma matriz não singular . Definindo
segue que e podemos aplicar o método da iteração.
Se a função e sua primeira derivada é contínua em segue
e pode ser provado que o processo iterativo
*
=ξ xΩ
= + Λx x f(x)( ) = + Λφ x x f(x)
( , , , )
( , , , ) ou com e ( )
( , , , )
n
n
n nn n
f x x x f x
f x x x f x
f x f x x x
=⎧ ⎡ ⎤ ⎡ ⎤⎪ ⎢ ⎥ ⎢ ⎥=⎪ ⎢ ⎥ ⎢ ⎥= = =⎨ ⎢ ⎥ ⎢ ⎥⎪ ⎢ ⎥ ⎢ ⎥⎪ = ⎣ ⎦ ⎣ ⎦⎩
f(x) 0 f x
1 1 2 1 1
2 1 2 2 2
1 2
0
0 3
0
Ω *x
)f(x
Λ( )=x φ x
f Ω
'( ) '= + Λφ x E f (x)
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 5/17
2.2- Método da Iteração
converge rapidamente se a norma de é pequena. Logo éconveniente escolher a matriz tal que
e se a matriz é não singular segue que
Aplicando o método da iteração a este sistema segue
Note que (4) coincide com o Método de Newton Modificadopara o sistema (3), já que (Jacobiana). Ou
seja,
Se a matriz é singular ( ), então deve ser
escolhida uma aproximação inicial diferente de .
Λ'( ) '= + Λ =φ x E f (x ) 0
0 0
'( )φ x
0'f (x )
[ ' ] ( ) [ ' ] [ ' ]− − −Λ = − ⇒ = − ⇒ = −f (x ) φ x x f (x ) f(x) x x f (x ) f(x)0 1 0 1 0 1
[ ' ] ( )k k k + −= −x x f (x ) f(x )1 0 1 4
[ ' ]− −=f (x ) W(x )0 1 0 1
( ')k k k + −= −x x W(x ) f(x )1 0 1 4
0'f (x )0det( ' ) 0=f (x )
x0
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 6/17
2.2.1- Convergência do Método da IteraçãoTeorema: Seja um sistema não linear de equações com
funções e continuas em tais que em se verifica a
desigualdade Se todas as
aproximações sucessivas pertencem a , então
este processo iterativo converge e seu limite é uma solução dosistema em .
Ou seja,
Aqui as normas são
Corolário: O Método da Iteração converge se
Estimativa de erro na aproximação k para o Método da Iteração:
Ω
Ω
Ω'( ) ( é uma constante).q q≤ <
Iφ x 1
( )=x φ x
Ω'( )φ x( )φ x
k k + =x φ(x )1
( )=x φ x
* *lim ( ).k
k →∞= =x x φ x
( )'( ) max '( ) e '( ) max
n
im m i
j j x
ϕ
∈Ω=
∂= = ∂∑I x
xφ x φ x φ x
1
( )
, , quando .
ni
j jq i n x
ϕ
=
∂
≤ < ∀ = ∈ Ω∂∑
x
x1 1 1
* ( )k k
k
m m m
q q
q q− ≤ − = −
− −x x x x φ x x
1 0 0 0
1 1 já que ( )=x φ
x1 0
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 7/17
Considere um sistema não linear de n equações com nincógnitas.
e suponha que as são reais e continuamente diferenciavel
no domínio de definição comum. Construa a seguinte função
Note que cada solução do sistema (3) anula a função evice-versa, cada que anula é solução do sistema (3).
Suponha que (3) tem somente uma solução isolada que
corresponde ao ponto de mínimo absoluto de . Logo o
problema se reduze a encontrar o mínimo desta função.
( , , , )
( , , , ) ou com e ( )
( , , , )
n
n
n nn n
f x x x f x
f x x x f x
f x f x x x
=⎧ ⎡ ⎤ ⎡ ⎤⎪ ⎢ ⎥ ⎢ ⎥=⎪ ⎢ ⎥ ⎢ ⎥= = =⎨ ⎢ ⎥ ⎢ ⎥⎪ ⎢ ⎥ ⎢ ⎥⎪ = ⎣ ⎦ ⎣ ⎦⎩
f(x) 0 f x
1 1 2 1 1
2 1 2 2 2
1 2
0
03
0
2.3 – Método do Gradiente (Descida mais Íngreme)
i f
( )( ) [ ( )] , .n
i
i
U f =
= =∑x x f(x) f(x)2
1
( )U x( )U xx
( )U x
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 8/17
Seja a raiz de (3) e a aproximação inicial. Construa umasuperfície de nível para em . Se está suficientemente
perto de esta superfície de nível deve se
assemelhar a um elipsóide. Parta de na direção da normal
da superfície até tocar alguma outras superfície denível tal que . Parta de na direção da
normal da superfície até tocar alguma outras
superfície de nível tal que .
A repetição deste processo nos leva ao ponto
de menor valor de , que corresponde
à raiz do sistema (3).
2.3 – Método do Gradiente (Descida mais Íngreme)
( )U x
( )U x
( ) ( )U U =x x0
x0*
xx
0x
0
*x
x0
( ) ( )U U =x x0
( ) ( ) ( )U U U = <x x x1 0
x1
( ) ( ) ( )U U U = <
x x x
2 1
( ) ( )U U =x x1
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 9/17
Lembrando que o gradiente da função tem a direção danormal da superfície de nível em cada ponto .
Logo . Resta determinar
para cada passo. Para isto considere a função que descreve a
variação contínua da superfície de nível entre o ponto e .
2.3 – Método do Gradiente (Descida mais Íngreme)
( )U xn
k x
( )
n
U
xU
xU
U
x
∂⎡ ⎤⎢ ⎥∂⎢ ⎥∂⎢ ⎥⎢ ⎥∂∇ = ⎢ ⎥
⎢ ⎥⎢ ⎥∂⎢ ⎥
⎢ ⎥∂⎣ ⎦
x
1
2
( ) ( , , )k k k k U k λ + = − ∇ =x x x1 0 1 k λ
( ) ( ( ))k k U U λ λ Φ = − ∇x x
k x
k +x
1
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 10/17
O parâmetro deve ser escolhido para que tenhaum mínimo. Ou seja,
Em geral, esta equação deve ser resolvida por métodos
numéricos. Aqui apresentamos um método para determinar de
forma aproximada o parâmetro . Para isto suponha que é
pequeno e que potencias deste parâmetro podem serdesprezadas se comparada com a parte linear. Logo
expandindo as funções em potencias de e retendo
apenas o termo linear segue
2.3 – Método do Gradiente (Descida mais Íngreme)
k λ
k
λ λ =[ ( ( ))]
( ) ( ( )) ( )
nk k
k k i
i
f U U U
λ λ λ
λ λ λ
=
∂ − ∇∂Φ ∂ − ∇
= = =∂ ∂ ∂
∑ x xx x
2
10 5
i f
( )λ Φ
λ
λ
0
( )
( (0))
( )
( ( )) ( ( ))
( )( )( )
i
k k
i
k i
k k k i
i
k
i i
i
f
f
f f U f
f f f
U
λ
λ λ
λ λ
λ λ
λ
=
∂+∂
∂ ∂∂
+ − ∇∂
= − ∇ ≈ =
=∂ ∂
x xxxx x
x
x
x
x
x x
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 11/17
Note que na equação anterior deve ser entendido por
Logo e
2.3 – Método do Gradiente (Descida mais Íngreme)
( )( ) ( ) ( )k n
k k ii
i
f f U λ λ =
⎛ ⎞∂Φ = − ∇⎜ ⎟∂⎝ ⎠
∑ xx xx
2
1
( ) ( ) ( ) ( ) (um vetor)
k k k k
i i i i
n
f f f f
x x x
⎡ ⎤∂ ∂ ∂ ∂= ⎢ ⎥
∂ ∂ ∂ ∂⎣ ⎦
x x x x
x 1 2
1
1
1
2
( )( ) ( )
=
( ) ( )( )
0 2 ( ) ( ) ( )
o
(
u
( ))
k k n
k n
k k ii
ik
k n
k k k i i
ii
k i
i
f f
f U U
f f U
f U
λ
λ λ
λ =
=
=
⎛ ⎞∂ ∇⎜ ⎟∂⎝ ⎠
⎛ ⎞∂∇⎜ ⎟
⎛ ⎞ ⎛ ⎞∂ ∂∂Φ
= = − − ∇ ∇⎜ ⎟ ⎜ ⎟∂ ∂ ∂⎝ ⎠ ⎝ ⎠
∂⎝ ⎠
∑
∑
∑
xx
x
xx
xx
x
x
x x xx x
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 12/17
Como segue que
2.3 – Método do Gradiente (Descida mais Íngreme)
( )( )
( )( )
( )
( )( )
ni n
i
i
nni
i
i
nni
i
n i n n nn
f f f f U f
x x x x x
f U f f f f
x x x x xU
U f f f f f
x x x x x
=
=
=
∂⎡ ⎤ ∂∂ ∂∂ ⎡⎡ ⎤⎢ ⎥ ⎢⎢ ⎥ ∂ ∂ ∂ ∂∂
⎢ ⎥ ⎢⎢ ⎥ ⎢ ⎥ ∂⎢∂ ∂ ∂⎢ ⎥ ∂⎢ ⎥ ⎢⎢ ⎥∂ ∂ ∂ ∂∂∇ = = =⎢ ⎥ ⎢⎢ ⎥⎢ ⎥ ⎢⎢ ⎥
⎢ ⎥ ⎢⎢ ⎥∂ ∂∂ ∂∂⎢ ⎥ ⎢⎢ ⎥⎢ ⎥ ⎢⎢ ⎥∂ ∂ ∂ ∂∂⎣ ⎦ ⎣⎣ ⎦
∑
∑
∑
xx
xx
x
xx
1 2
1 1 1 1 11
1 2
12 2 2 22
1 2
1
2 2
[ ]
( )
( )
( )n
f
f
f
⎤⎡ ⎤⎥⎢ ⎥
⎥ ⎢ ⎥⎥⎢ ⎥⎥⎢ ⎥⎥⎢ ⎥⎥
⎢ ⎥⎥ ⎢ ⎥⎥⎢ ⎥⎣ ⎦⎥⎦
T
f(x)
W(x)
x
x
x
1
2
( ) [ ( )]
n
i
iU f
== ∑x x2
1
o n d e é a J a c o b i a n a d a f u n ç ã o v e t o r
n
n
n n n
n
f f f x x x
f f f
x x x
f f f x x x
∂ ∂ ∂⎡ ⎤⎢ ⎥∂ ∂ ∂⎢ ⎥
∂ ∂ ∂⎢ ⎥⎢ ⎥∂ ∂ ∂= ⎢ ⎥⎢ ⎥⎢ ⎥
∂ ∂ ∂⎢ ⎥⎢ ⎥∂ ∂ ∂⎣ ⎦
W ( x ) f ( x )
1 1 1
1 2
2 2 2
1 2
1 2
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 13/17
Logo e
Portanto
Note que o parâmetro deve ser calculado para cada passo.
2.3 – Método do Gradiente (Descida mais Íngreme)
( ) [ ]k k k
U ∇ =
T
x W (x ) f(x )2
( )( ) ( ) [ ] [ ]
k nk k k k k k i
i
i
f f U
=
⎛ ⎞∂∇ =⎜ ⎟
∂⎝ ⎠∑ T Tx
x x f(x ) W (x ) W (x ) f(x )x1
2
[ ] [ ]
2 [ ] [ ]
k k k k k
k k k k k k
λ =
⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦
T T
T
T T
f(x ) W(x ) W(x ) f(x )
W(x ) W(x ) f(x ) W(x ) W(x ) f(x )
( )( )
[ ] [ ]
k nk i
i
k k k k k k
f U
=
⎛ ⎞∂∇ =⎜ ⎟
∂⎝ ⎠
⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦
∑T
T T
xx
x
W(x ) W(x ) f(x ) W(x ) W(x ) f(x )
2
1
2 2
[ ] onde ( )k k k k k k k μ μ λ + = − =Tx x W(x ) f(x )
1 2 6
k μ
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 14/17
Resumindo o método, já que
Observe que para otimizar o tempo de computo é conveniente
para cada passo fazer os cálculos na seguinte ordem:
1- Calcule
2- Calcule e termine as outras operações
2.3 – Método do Gradiente (Descida mais Íngreme)
[ ] [ ]
[ ] [ ]
k k k k k
k k k k k k μ = ⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦
T T
TT T
f(x ) W(x ) W(x ) f(x )
W(x ) W(x ) f(x ) W(x ) W(x ) f(x )
[ ]k k k k k μ + = − Tx x W(x ) f(x )
1
, ou [ ]k k k Tf(x ) W(x ) W(x )
[ ] [ ]
k k k k
⎡ ⎤= ⎣ ⎦
TT T
W(x ) f(x ) f(x ) W(x )
[ ]
k k T
W(x ) f(x )
[ ] [ ] [ ]
[ ] [ ]
k k
k
k k k k
k k
k k
k k k
+
⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦= −⎡ ⎤ ⎡ ⎤⎣ ⎦ ⎣ ⎦
T T T
T
T
TT
W(x ) f(x ) W(x ) f(x ) W(x ) f(x )
W(x ) f(x )x x
W(x W(x ) f(x) x )W( )
1
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 15/17
2.1.3- Exemplo 2 pag. 462 do Demidovich
Use o Método da Iteração e do Gradiente para encontrar asolução aproximada positiva
do sistema de equações:
começando com a aproximação inicial
x y z
x y z
x y z
⎧ + + =⎪
+ − =⎨
⎪ − + =⎩
2 2 2
2 2
2 2
1
2 4 0
3 4 0
. . x y z= = =0 0 0 0 5
Visualização gráfica do problema na próxima tela.
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 16/17
2.1.3- Exemplo 2 pag. 462 do DemidovichVisualização gráfica do problema
8/15/2019 Aula_7_Métodos numéricos(Descida máxima)
http://slidepdf.com/reader/full/aula7metodos-numericosdescida-maxima 17/17
Frase do Dia“... the progress of physics will to a large
extent depend on the progress of nonlinearmathematics, of method to solve nonlinear
equations ... and therefore we can learn by
comparing different nonlinear problems.”
Werner Heisenberg