capítulo 8
250 pág.

capítulo 8


DisciplinaÁlgebra Linear I21.434 materiais306.582 seguidores
Pré-visualização42 páginas
resolver o sistema linear triangular superior RX = QtY , pelo
processo de substituic¸a\u2dco atrasada, descrito no Algoritmo 2.9.2. A fatorac¸a\u2dco H = QR
pode ser obtida pelo Me´todo de Gram\u2013Schmidt Modificado, descrito no Algoritmo 8.13.2.
Fazendo uso dos procedimentos acima mencionados, obtemos a soluc¸a\u2dco do sistema linear
indefinido que e´ dada por:
X\u2217 =
\uf8ee\uf8f0w\u2217
\u3bb\u2217
\uf8f9\uf8fb = 1
4
\uf8ee\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8f0
1
\u22121
1
\u22121
5
\u22122
\u22122
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fb
Desse modo, temos que a projec¸a\u2dco ortogonal do elemento b sobre o subespac¸o N (At),
e a soluc¸a\u2dco de quadrados m\u131´nimos para o sistema linear Ax = b, sa\u2dco dados por:
w\u2217 =
1
4
\uf8ee\uf8ef\uf8ef\uf8ef\uf8f0
1
\u22121
1
\u22121
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fb e \u3bb\u2217 = x\u2217 = 14
\uf8ee\uf8ef\uf8f0 5\u22122
\u22122
\uf8f9\uf8fa\uf8fb ,
respectivamente.
Petronio Pulino 701
Quadrados M\u131´nimos com Restric¸a\u2dco
Considere o espac¸o vetorial real IRn munido do produto interno usual \u3008 · , · \u3009 . Sejam
A \u2208 IMm×n(IR), com m > n e posto(A) = n, b \u2208 IRm, B \u2208 IMp×n(IR), com p < n
e posto(B) = p, e d \u2208 IRp. Considere o problema:
Encontrar uma soluc¸a\u2dco de Quadrados M\u131´nimos para o Sistema Linear So-
bredeterminado Ax = b com a restric¸a\u2dco Bx = d.
Considere o funcional J : IRn \u2212\u2192 IR definido da seguinte forma:
J(x) =
1
2
\u3008Ax \u2212 b , Ax \u2212 b \u3009 = 1
2
\u2016Ax \u2212 b \u201622 .
Representamos nosso problema com o Problema de Programac¸a\u2dco Quadra´tica\uf8f1\uf8f4\uf8f2\uf8f4\uf8f3
min{ J(x) }
sujeito a Bx = d
Utilizando o Me´todo dos Multiplicadores de Lagrange, associamos ao Problema de
Programac¸a\u2dco Quadra´tica com Restric¸a\u2dco um Problema de Otimizac¸a\u2dco Global , considerando
a func¸a\u2dco de Lagrange
F (x, \u3bb) =
1
2
\u3008Ax \u2212 b , Ax \u2212 b \u3009 + \u3008Bx\u2212 d , \u3bb \u3009 ,
onde \u3bb \u2208 IRp e´ o vetor dos multiplicadores de Lagrange.
Sendo assim, temos que determinar os pontos cr´\u131ticos da func¸a\u2dco de Lagrange, isto e´,
encontrar (x\u2217 , \u3bb\u2217) \u2208 IRn × IRp tal que
\u2207F (x\u2217, \u3bb\u2217) =
\uf8f1\uf8f4\uf8f2\uf8f4\uf8f3
\u2207xF (x\u2217, \u3bb\u2217) = 0IRn
\u2207\u3bbF (x\u2217, \u3bb\u2217) = 0IRp
Calculando a primeira variac¸a\u2dco da func¸a\u2dco de Lagrange F com relac¸a\u2dco a` varia´vel x,
obtemos
\u2207xF (x, \u3bb) = AtAx + Bt\u3bb \u2212 Atb ,
e calculando a primeira variac¸a\u2dco da func¸a\u2dco de Lagrange F com relac¸a\u2dco a` varia´vel \u3bb,
obtemos
\u2207\u3bbF (x, \u3bb) = Bx \u2212 d .
702 A´lgebra Linear e suas Aplicac¸o\u2dces: Notas de Aula
Desse modo, temos o seguinte
Problema de Ponto Sela: Encontrar (x\u2217 , \u3bb\u2217) \u2208 IRn × IRp soluc¸a\u2dco do sistema linear
indefinido \uf8f1\uf8f4\uf8f2\uf8f4\uf8f3
AtAx + Bt\u3bb = Atb
Bx = d
(8.208)
que na forma matricial e´ representado por:\uf8ee\uf8f0AtA Bt
B 0p
\uf8f9\uf8fb\uf8ee\uf8f0x
\u3bb
\uf8f9\uf8fb =
\uf8ee\uf8f0Atb
d
\uf8f9\uf8fb ,
onde 0p e´ a matriz nula de ordem p × p. Como A \u2208 IMm×n(IR), com m > n e
posto(A) = n, sabemos que AtA e´ uma matriz positiva\u2013definida.
Por simplicidade, vamos indicar o sistema linear indefinido por HX = Y , onde
X =
\uf8ee\uf8f0x
\u3bb
\uf8f9\uf8fb , Y =
\uf8ee\uf8f0Atb
d
\uf8f9\uf8fb e H =
\uf8ee\uf8f0AtA Bt
B 0p
\uf8f9\uf8fb .
Nesta caso, a matriz do Problema de Ponto Sela H e´ uma matriz sime´trica invert´\u131vel,
de ordem n + m, com n autovalores positivos e m autovalores negativos, isto e´, H e´
uma matriz indefinida, de acordo com os resultados do Exemplo 6.7.8.
Finalmente, calculando a segunda variac¸a\u2dco da func¸a\u2dco de Lagrange F com relac¸a\u2dco a`s
varia´veis x e \u3bb, obtemos a matriz Hessiana de F , que e´ a matriz H. Assim, o ponto
cr´\u131tico (x\u2217 , \u3bb\u2217) e´ um ponto de sela para a func¸a\u2dco de Lagrange.
Petronio Pulino 703
Exemplo 8.16.2 Considere a matriz A \u2208 IM4×3(IR) e o vetor b \u2208 IR4 dados por:
A =
\uf8ee\uf8ef\uf8ef\uf8ef\uf8f0
1 1 0
1 1 1
1 0 1
1 0 0
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fb e b =
\uf8ee\uf8ef\uf8ef\uf8ef\uf8f0
1
0
1
1
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fb .
Determinar a soluc¸a\u2dco de quadrados m\u131´nimos para o sistema linear sobredeterminado
Ax = b com a restric¸a\u2dco x1 + x2 + x3 = 0, isto e´, Bx = d, onde
B =
[
1 1 1
]
, d =
[
0
]
e x =
\uf8ee\uf8ef\uf8f0x1x2
x3
\uf8f9\uf8fa\uf8fb .
Por simplicidade, vamos indicar o sistema linear indefinido por HX = Y , onde os
elementos X, Y \u2208 IR4 sa\u2dco dados por:
X =
\uf8ee\uf8f0x
\u3bb
\uf8f9\uf8fb e Y =
\uf8ee\uf8f0Atb
d
\uf8f9\uf8fb =
\uf8ee\uf8ef\uf8ef\uf8ef\uf8f0
3
1
1
0
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fb ,
e a matriz H \u2208 IM4(IR) e´ dada por:
H =
\uf8ee\uf8f0AtA Bt
B 01
\uf8f9\uf8fb =
\uf8ee\uf8ef\uf8ef\uf8ef\uf8f0
4 2 2 1
2 2 1 1
2 1 2 1
1 1 1 0
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fb .
Como posto(A) = 3, temos que AtA e´ uma matriz positiva\u2013definida. Assim, sabemos
que H e´ uma matriz indefinida.
Utilizando a fatorac¸a\u2dco H = QR, que pode ser obtida pelo Me´todo de Gram\u2013Schmidt
Modificado, obtemos a soluc¸a\u2dco do sistema linear indefinido, e por consequ¨e\u2c6ncia a soluc¸a\u2dco
de quadrados m\u131´nimos com restric¸a\u2dco, dadas por:
X\u2217 =
1
3
\uf8ee\uf8ef\uf8ef\uf8ef\uf8f0
4
\u22122
\u22122
1
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fb e x\u2217 = 13
\uf8ee\uf8ef\uf8f0 4\u22122
\u22122
\uf8f9\uf8fa\uf8fb ,
respectivamente. Note que o multiplicador de Lagrange \u3bb\u2217 =
1
3
.
704 A´lgebra Linear e suas Aplicac¸o\u2dces: Notas de Aula
Me´todo de Uzawa
Considere o Problema de Ponto Sela: encontrar x\u2217 \u2208 IRn e \u3bb\u2217 \u2208 IRm soluc¸a\u2dco do
sistema linear indefinido \uf8f1\uf8f2\uf8f3 Ax + B
t\u3bb = b
Bx = d
onde A \u2208 IMn(IR) positiva\u2013definida, b \u2208 IRn, d \u2208 IRm e B \u2208 IMm×n(IR), com
m < n e posto(B) = m.
O Me´todo de Uzawa com Direc¸o\u2dces de Gradientes3 e´ largamente utilizado para
obter uma soluc¸a\u2dco nume´rica para o Problema de Ponto Sela, que descrevemos a seguir.
Sejam \u3bb0 \u2208 IRm e Ax1 = b \u2212 Bt\u3bb0
qk = d \u2212 Bxk
pk = B
tqk
Ahk = pk
\u3b1k =
\u3008 qk , qk \u3009
\u3008 pk , hk \u3009
\u3bbk = \u3bbk\u22121 \u2212 \u3b1k qk
xk+1 = xk + \u3b1k hk
para k = 1, 2 , 3, · · · .
Devemos obter uma soluc¸a\u2dco nume´rica para o sistema linear positivo\u2013definido
Ahk = pk ,
de maneira eficiente, o que pode ser feito atrave´s do Me´todo dos Gradientes Conjugados,
nos casos em que a matriz A e´ esparsa e de grande porte, ou pelo Me´todo de Cholesky,
caso contra´rio. Note que na aproximac¸a\u2dco inicial temos, tambe´m, de obter uma soluc¸a\u2dco
nume´rica para o sistema linear positivo\u2013definido Ax1 = b \u2212 Bt\u3bb0.
3Dietrich Braess, Finite Elements , Cambridge University Press, 1997.
Petronio Pulino 705
Exemplo 8.16.3 Sabe\u2013se que uma alimentac¸a\u2dco dia´ria equilibrada em vitaminas deve
conter de 950 unidades de vitamina A, 725 unidades de vitamina B, 625 unida-
des de vitamina C, 700 unidades de vitamina D e 850 unidades de vitamina E.
Com o objetivo de analisar como deve ser uma refeic¸a\u2dco equilibrada, foram estudados tre\u2c6s
alimentos. Fixada a mesma quantidade de 1.0 grama de cada alimento, determinou\u2013se
que :
(i) O alimento I conte´m 1 unidade de vitamina A, 1 unidades de vitamina B, 1
unidade de vitamina C, 2 unidades de vitamina D e 2 unidades de vitamina E, e
custa R$ 15, 00 por quilograma.
(ii) O alimento II conte´m 2 unidades de vitamina A, 1 unidade de vitamina B, 1
unidade de vitamina C, 1 unidade de vitamina D e 1 unidades de vitamina E, e
custa R$ 20, 00 por quilograma.
(iii) O alimento III conte´m 2 unidades de vitamina A, 2 unidades de vitamina B, 3
unidades de vitamina C, 1 unidade de vitamina D e 2 unidades de vitamina E, e
custa R$ 10, 00 por quilograma.
Quantos gramas de cada um dos alimentos I, II e III devemos ingerir diariamente para
que nossa alimentac¸a\u2dco seja a mais equilibrada poss´\u131vel e desejamos que cada refeic¸a\u2dco tenha
550 gramas a um custo de R$ 9, 50 ?
Temos um Problema de Quadrados M\u131´nimos com Restric¸a\u2dco, onde
A =
\uf8ee\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8f0
1 2 2
1 1 2
1 1 3
2 1 1
2 1 2
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fb , b =
\uf8ee\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8ef\uf8f0
950
725
625
700
850
\uf8f9\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fa\uf8fb , B =
[
1.000 1.00 1.00
0.015 0.02 0.01
]
e d =
[
550
9.50
]
,
cuja soluc¸a\u2dco obtida pelo Me´todo de Uzawa e´ dada por:
x\u2217 =
\uf8ee\uf8ef\uf8f0167.86316.07
66.07
\uf8f9\uf8fa\uf8fb ,
que representa a quantidade em gramas de cada um dos alimentos I, II e III que devem
compor uma refeic¸a\u2dco.
706 A´lgebra Linear e suas Aplicac¸o\u2dces: Notas de Aula
Considerando somente a soluc¸a\u2dco de quadrados m\u131´nimos para o sistema linear Ax = b,
obtemos a soluc¸a\u2dco
x\u2217 =
\uf8ee\uf8ef\uf8f0179.55328.41
61.36
\uf8f9\uf8fa\uf8fb ,
que representa a quantidade em gramas de cada um dos alimentos I, II e III que devem
compor uma refeic¸a\u2dco mais equilibrada poss´\u131vel.
Neste caso, teremos uma refeic¸a\u2dco contendo 569.32 gramas a um custo de R$ 9, 88, que
possui uma coere\u2c6ncia com a soluc¸a\u2dco do