Decomposição LU e Resolução de Sistemas Lineares

Prévia do material em texto

MAT 012 versa˜o 2018.1 Prof. Rodrigo Lima
Decomposic¸a˜o LU
Na aula de hoje vamos estudar a decomposic¸a˜o LU de uma matriz quadrada A. Veremos
tambe´m como esta decomposic¸a˜o pode ser utilizada na resoluc¸a˜o de um sistema linear Ax = b
e, por fim, investigaremos situac¸o˜es onde e´ conveniente usar a decomposic¸a˜o LU ao inve´s da
Eliminac¸a˜o Gaussiana na resoluc¸a˜o de sistemas lineares.
Caracter´ısticas
Uma matriz quadrada A de ordem n admite decomposic¸a˜o LU se puder ser escrita como o
produto de duas matrizes
A = L · U, (1)
onde L e´ triangular inferior com diagonal unita´ria e U e´ triangular superior, ambas de ordem
n, ou seja,
L =

1 0 0 · · · 0
`21 1 0 · · · 0
`31 `32 1 · · · 0
...
...
...
. . .
...
`n1 `n2 `n3 · · · 1
 , U =

u11 u12 u13 · · · u1n
0 u22 u23 · · · u2n
0 0 u33 · · · u3n
...
...
...
. . .
...
0 0 0 · · · unn
 . (2)
Exemplo 1
Obtenha, se poss´ıvel, a decomposic¸a˜o LU das seguintes matrizes:
A1 =
(
0 1
1 0
)
, A2 =
(
2 0
2 0
)
, A3 =
 1 2 −12 3 −2
1 −2 1

Resoluc¸a˜o:
1. Supondo que A1 admite esta decomposic¸a˜o, escrevemos:
A1 =
(
0 1
1 0
)
=
(
1 0
`21 1
)
·
(
u11 u12
0 u22
)
.
Devemos enta˜o resolver a equac¸a˜o matricial acima na tentativa de encontrar os ele-
mentos desconhecidos das matrizes L e U . Multiplicando a primeira linha de L pela
primeira coluna de U e igualando o resultado ao elemento a11 de A1 obtemos u11 = 0.
Se agora multiplicarmos a segunda linha de L pela primeira coluna de U e igualarmos
o resultado ao elemento a21 de A1 vamos obter uma inconsisteˆncia:
`21 · u11 = 1, mas u11 = 0.
Conclusa˜o: A1 na˜o admite decomposic¸a˜o LU.
1
2. Procedendo de forma semelhante com a matriz A2, podemos escrever:
A2 =
(
2 0
2 0
)
=
(
1 0
`21 1
)
·
(
u11 u12
0 u22
)
.
Efetuando a multiplicac¸a˜o das matrizes L e U e forc¸ando o resultado ser igual a A2,
obtemos as seguintes equac¸o˜es:
� 1 · u11 + 0 · 0 = 2⇒ u11 = 2,
� 1 · u12 + 0 · u22 = 0⇒ u12 = 0,
� `21 · u11 + 1 · 0 = 2⇒ `21 = 1,
� `21 · u12 + 1 · u22 = 0⇒ u22 = 0.
Conclusa˜o: A2 admite decomposic¸a˜o LU pois L =
(
1 0
1 1
)
e U =
(
2 0
0 0
)
.
3. Ao inve´s de tentarmos resolver a equac¸a˜o matricial A3 = LU , vamos proceder de forma
semelhante ao que fizemos no me´todo da Eliminac¸a˜o Gaussiana, isto e´, vamos aplicar
operac¸o˜es elementares na matriz A3 para transforma´-la em uma matriz triangular
superior.
� Na primeira etapa da transformac¸a˜o, eliminamos os elementos da primeira coluna
abaixo do pivoˆ a11:
A3 =
 1 2 −12 3 −2
1 −2 1
 ⇒

m21 = a21/a11 = 2
aˆ22 = a22 −m21a12 = 3− 2 · 2 = −1
aˆ23 = a23 −m21a13 = −2− 2 · (−1) = 0
m31 = a31/a11 = 1
aˆ32 = a32 −m31a12 = −2− 1 · 2 = −4
aˆ33 = a33 −m31a13 = 1− 1 · (−1) = 2
� Em seguida, eliminamos o elemento abaixo do pivoˆ aˆ22 na matriz que resultou da
etapa anterior:
Aˆ3 =
 1 2 −10 −1 0
0 −4 2
 ⇒ { m32 = aˆ32/aˆ22 = 4
a˜33 = aˆ33 −m32aˆ23 = 2− 4 · 0 = 2
2
� A matriz A˜ obtida ao final das transformac¸o˜es sera´ a matriz U da decomposic¸a˜o.
A matriz L e´ constru´ıda com os multiplicadores m21, m31 e m32 calculados durante
o processo.
Conclusa˜o: A3 admite decomposic¸a˜o LU pois
L =
 1 0 02 1 0
1 4 1
 e U =
 1 2 −10 −1 0
0 0 2
 .
Observando os ca´lculos realizados neste exemplo, notamos que a matriz A1 e´ invert´ıvel
(det(A1) = −1) mas na˜o admite uma decomposic¸a˜o LU. Ja´ a matriz A2 na˜o possui inversa
(pois det(A2) = 0) mas admite uma decomposic¸a˜o LU. Por fim, conseguimos encontrar os
fatores L e U para a matriz A3. Esta u´ltima matriz tambe´m e´ invert´ıvel pois det(A3) = −2.
Com base nestes resultados surge a questa˜o: qual deve ser a condic¸a˜o para que uma matriz
quadrada admita decomposic¸a˜o LU? A resposta para esta pergunta vem a seguir.
Propriedades da Decomposic¸a˜o LU
Teorema: Seja A uma matriz quadrada de ordem n e suponha que os determinantes das
submatrizes principais (tambe´m chamados de menores principais) de A ate´ a ordem n − 1
sa˜o todos diferentes de zero. Enta˜o, A admite uma decomposic¸a˜o LU . Ale´m disso,
� se A possui uma decomposic¸a˜o LU , det(A) = det(U).
� se A e´ invert´ıvel e admite decomposic¸a˜o LU, os fatores L e U sa˜o u´nicos.
Prova: a demonstrac¸a˜o desse resultado pode ser consultada em Matrix Computations - G.
Golub, C. Van Loan - The John Hopkins University Press - 3a edic¸a˜o - pa´g. 97.
Agora somos capazes de entender o que acontece com a matriz A1 do Exemplo 1: a subma-
triz principal de ordem 1 de A1 (formada apenas pelo elemento a11 = 0) possui determinante
nulo. Isso e´ suficiente para que na˜o consigamos decompor A1 em um produto L · U .
Resoluc¸a˜o de Sistemas Lineares via Decomposic¸a˜o LU
Considere Ax = b um sistema linear e suponha que A e´ invert´ıvel e admite decomposic¸a˜o LU.
Para resolver este sistema utilizando a decomposic¸a˜o da matriz A procedemos do seguinte
modo:
1. Escrevemos o sistema como LUx = b e introduzimos a mudanc¸a de varia´veis Ux = y.
2. Resolvemos o sistema triangular inferior Ly = b para encontrar o vetor soluc¸a˜o y.
3. Resolvemos, finalmente, o sistema triangular superior Ux = y para encontrar a soluc¸a˜o
final x. Note que o lado direito desse sistema e´ a soluc¸a˜o obtida no sistema linear
descrito no item 2.
3
Exemplo 2
Resolva o sistema linear Ax = b utilizando a decomposic¸a˜o LU de A. Considere
A =
 1 2 −12 3 −2
1 −2 1
 e b =
 23
0
 .
Resoluc¸a˜o: a matriz de coeficientes deste sistema e´ a matriz A3 que apareceu no Exemplo
1. Enta˜o, basta resolvermos os sistemas Ly = b e Ux = y uma vez que ja´ realizamos a
decomposic¸a˜o LU de A e conhecemos os fatores L e U .
� resoluc¸a˜o de Ly = b: de cima para baixo 1 0 02 1 0
1 4 1
 ·
 y1y2
y3
 =
 23
0
⇒ y =
 2−1
2
 .
� resoluc¸a˜o de Ux = y: de baixo para cima 1 2 −10 −1 0
0 0 2
 ·
 x1x2
x3
 =
 2−1
2
⇒ x =
 11
1
 .
Decomposic¸a˜o LU com Estrate´gia de Pivoteamento Parcial
Para aplicar a decomposic¸a˜o LU em uma matriz utilizando a estrate´gia de pivoteamento
parcial, devemos proceder de forma semelhante aos ca´lculos que ja´ fizemos no me´todo da
Eliminac¸a˜o Gaussiana. Vejamos mais detalhadamente como este procedimento funciona no
exemplo a seguir.
Exemplo 3
Obtenha a decomposic¸a˜o LU da matriz A =
 3 −4 11 2 2
4 0 −3
 aplicando a estrate´gia de
pivoteamento parcial.
Resoluc¸a˜o:
� Inicialmente trocamos as linhas 1 e 3 de posic¸a˜o. Em seguida, eliminamos os elementos
4
abaixo do novo pivoˆ aˆ11 = 4:
Aˆ =
 4 0 −31 2 2
3 −4 1
 ⇒

m21 = aˆ21/aˆ11 = 1/4
a¯22 = aˆ22 −m21aˆ12 = 2− (1/4) · 0 = 2
a¯23 = aˆ23 −m21aˆ13 = 2− (1/4) · (−3) = 11/4
m31 = aˆ31/aˆ11 = 3/4
a¯32 = aˆ32 −m31aˆ12 = −4− (3/4) · 0 = −4
a¯33 = aˆ33 −m31aˆ13 = 1− (3/4) · (−3) = 13/4
� A matriz que resultou da etapa anterior e´ dada por
A¯ =
 4 0 30 2 11/4
0 −4 13/4
 .
Como estamos aplicando a estrate´gia de pivoteamento parcial, devemos trocar as linhas
2 e 3 da matriz A¯ antes de iniciarmos o processo de eliminac¸a˜o.
A˜ =
 4 0 30 −4 13/4
0 2 11/4
 ⇒ { m32 = a˜32/a˜22 = −1/2
a
′
33 = a˜33 −m32a˜23 = 11/4− (−1/2) · 13/4 = 35/8
Portanto, as matrizes L e U ao final da decomposic¸a˜o sa˜o dadas por:
L =
 1 0 0m31 1 0
m21 m32 1
 =
 1 0 03/4 1 0
1/4 −1/2 1
 e U =
 4 0 −30 −4 13/4
0 0 35/8
 .
Note que foi necessa´rio trocar os elementos m31 e m21 de posic¸a˜o na matriz L porque
tivemos que alterar as linhas 2 e 3 da matriz A¯. Se efetuarmos o produto L·U utilizando
as matrizes L e U acima na˜o obteremos a matriz inicial A. De fato, a matriz
L · U =
 4 0 −33 −41
1 2 2
 ,
pode ser obtida de A realizando algumas troca de linhas: na etapa 1 do processo
trocamos as linhas 1 e 3 de posic¸a˜o e, depois, realizamos a troca das linhas 2 e 3. Estas
operac¸o˜es equivalem a pre´-multiplicarmos A pela seguinte matriz de permutac¸a˜o:
P =
 0 0 11 0 0
0 1 0
 .
Isto significa que realizamos a decomposic¸a˜o LU na matriz PA, ou seja, PA = LU .
5
Resoluc¸a˜o de Sistemas Lineares via LU com Pivoteamento Parcial
Para resolver um sistema linear Ax = b atrave´s da decomposic¸a˜o LU com estrate´gia de
pivoteamento parcial procedemos da seguinte forma:
1. Pre´-multiplicamos ambos os lados da igualdade Ax = b pela matriz de permutac¸a˜o
responsa´vel pela troca de linhas de A durante o processo de decomposic¸a˜o, ou seja,
PAx = Pb.
2. Substitu´ımos a matriz PA pela decomposic¸a˜o LU encontrada, isto e´, LUx = Pb.
3. Fazemos a mudanc¸a de varia´veis Ux = y e resolvemos os dois sistemas triangulares:
primeiro resolvemos Ly = Pb e, depois, resolvemos Ux = y.
E´ importante observar que a mesma troca de linhas realizadas na matriz de coeficientes do
sistema deve ser realizada nas componentes do vetor b. Por isso, o lado direito do sistema
triangular inferior e´ Pb.
Uso de softwares
No exemplo a seguir, utilizaremos comandos espec´ıficos do software Mathematica para enten-
der como a decomposic¸a˜o LU com estrate´gia de pivoteamento parcial e´ utilizada na resoluc¸a˜o
de um sistema linear 3× 3.
Exemplo 4
Resolva o sistema linear Ax = b utilizando a decomposic¸a˜o LU com estrate´gia de pivotea-
mento parcial. Considere
A =
 3 −4 11 2 2
4 0 −3
 e b =
 93
−2
 .
Resoluc¸a˜o: Observe primeiramente que a matriz A e´ a mesma utilizada no Exemplo 3.
No entanto, faremos os ca´lculos da decomposic¸a˜o no software Mathematica.
� A decomposic¸a˜o LU de A pode ser obtida com o aux´ılio do comando LUDecompo-
sition[ ]. Para que o Mathematica trabalhe com aritme´tica de ponto flutuante nos
ca´lculos, basta declararmos a11 = 3.0 (treˆs ponto zero), mas poder´ıamos escolher qual-
quer outra das entradas de A para colocar um zero apo´s o ponto. Assim, o software
na˜o fara´ operac¸o˜es supondo que A possui entradas inteiras. A Figura 1 mostra como
declarar a matriz A e acionar o comando que fornece a decomposic¸a˜o LU. A sa´ıda do
comando LUDecomposition[ ] e´ uma lista contendo treˆs elementos: o primeiro e´ a
decomposic¸a˜o LU de A com as entradas de L e U armazenadas na mesma matriz (ob-
serve na Figura 1 as treˆs primeiras chaves na sa´ıda do comando). O segundo elemento
e´ um vetor que especifica as linhas utilizadas no pivoteamento parcial. Aqui o vetor
6
e´ {3, 1, 2} significando que foram realizadas treˆs trocas de linha durante o processo,
exatamente como vimos na resoluc¸a˜o do Exemplo 3. Por fim, o terceiro elemento e´
um paraˆmetro chamado nu´mero de condic¸a˜o da matriz A que neste caso e´ igual a
3.2.
������� �����[�� ��]�
� = {{���� -�� �}� {�� �� �}� {�� �� -�}}�
�� = ���������������[�]
������� {{{��� ��� -��}� {����� -��� ����}� {����� -���� �����}}� {�� �� �}� ���}
Figura 1: LUDecomposition[ ] realiza pivoteamento parcial em A.
A Figura 2 mostra a declarac¸a˜o das matrizes L e U resultantes da decomposic¸a˜o e o
produto L ·U que fornece como resultado uma matriz obtida de A pela troca de linhas.
�������
�����[�� �]�
� = {{�� �� �}� {����� �� �}� {����� -���� �}}�
� = {{�� �� -�}� {�� -�� ����}� {�� �� �����}}�
��� // ����������
��������������������� �� -��
�� -�� ��
�� �� ��
Figura 2: L · U = PA, onde P e´ matriz de permutac¸a˜o.
Por fim, resolvemos os sistemas triangulares Ly = Pb e Ux = y com o comando
LinearSolve[ ]. Este procedimento esta´ indicado na Figura 3.
�������
�� = {-�� �� �}�
� = �����������[�� ��]�
� = �����������[�� �]
�������� {��� -��� ��}
Figura 3: Resoluc¸a˜o dos sistemas triangulares com LinearSolve[ ].
7
Eliminac¸a˜o Gaussiana ou Decomposic¸a˜o LU?
Suponha uma situac¸a˜o em que devemos resolver n sistemas lineares da forma Ax(k) = b(k)
para k = 1, . . . , n, com A invert´ıvel. Isto e´, os sistemas possuem a mesma matriz de coe-
ficientes A mas teˆm lados direitos diferentes. Se quisermos implementar um algoritmo que
ao mesmo tempo resolva todos os n sistemas e seja computacionalmente eficiente, devemos
utilizar Eliminac¸a˜o Gaussiana ou Decomposic¸a˜o LU?
� Supondo que A admite uma decomposic¸a˜o LU, o melhor a ser feito neste caso e´ aplicar
esta decomposic¸a˜o, pois uma vez encontrados os fatores L e U de A podemos utiliza´-
los para resolver todos os n sistemas tomando o cuidado apenas de alterar os termos
independentes b(k) para k = 1, . . . , n. Deste modo, um modelo de algoritmo que resolva
esta situac¸a˜o pode ser dado por:
0: Calcule a decomposic¸a˜o LU de A.
1: Para k = 1, . . . , n fac¸a:
2: resolva Ly(k) = b(k) e encontre y(k)
3: resolva Ux(k) = y(k) e encontre x(k)
4: fac¸a k ← k + 1 e volte ao passo 1
5: Fim
� E se a matriz A na˜o admitir decomposic¸a˜o LU? Como A possui inversa por hipo´tese
(det(A) 6= 0), e´ poss´ıvel provar que existe uma matriz de permutac¸a˜o P que faz com
que PA admita decomposic¸a˜o LU. Portanto, neste caso, podemos resolver os n sistemas
lineares utilizando a decomposic¸a˜o LU da matriz PA tomando o cuidado de usar P para
alterar o lado direito dos sistemas triangulares, ou seja, Ly(k) = Pb(k) para k = 1, . . . , n.
� Embora o me´todo da Eliminac¸a˜o Gaussiana possa ser utilizado para resolver a situac¸a˜o
proposta, ele na˜o e´ computacionalmente adequado, uma vez que devemos realizar nas
n matrizes ampliadas [A | b(k)] os mesmos ca´lculos que poder´ıamos fazer uma u´nica
vez para triangularizar A.
Ainda sobre os dois me´todos de resoluc¸a˜o de sistemas lineares devemos notar que:
� Tanto a Eliminac¸a˜o Gaussiana quanto a Decomposic¸a˜o LU gastam da ordem de n3
operac¸o˜es para resolver um sistema linear quadrado Ax = b.
� Ambos os me´todos na˜o sa˜o indicados para resoluc¸a˜o de sistemas lineares esparsos, ou
seja, sistemas em que a matriz de coeficientes possui mais entradas nulas do que na˜o
nulas. Estes me´todos na˜o preservam a estrutura de esparsidade dessas matrizes.
8
Exerc´ıcios
1. Mostre que a matriz
A =
 2 2 11 1 1
3 2 1

e´ invert´ıvel e que A na˜o pode ser escrita como o produto de uma matriz triangular
inferior por uma matriz triangular superior sem pivoteamento parcial.
2. Resolva o sistema linear abaixo aplicando a decomposic¸a˜o LU com estrate´gia de pivo-
teamento parcial: 
x1 + 4x2 − x3 = 0
4x1 + x2 + 2x3 = 1
4x2 − 5x3 = 3
3. Sejam A =
 1 4 54 18 26
3 10 30
, b =
 60
−6
 e c =
 66
12
.
a) Determine a decomposic¸a˜o PA = LU .
b) Resolva os sistemas lineares Ax = b e Ay = c.
c) Determine A−1.
4. Sejam A =
 1 −3 21 −4 3
1 −5 4
, b =
 −10
0
 e c =
 −4−5
−6
. Usando a decomposic¸a˜o LU
de A, mostre que Ax = b na˜o tem soluc¸a˜o e que Ax = c tem infinitas soluc¸o˜es.
5. Sejam A uma matriz invert´ıvel de ordem n e X,B matrizes n×m.
a) Mostre que resolver a equac¸a˜o matricial AX = B e´ o mesmo que resolver m
sistemas lineares do tipo Ax = b, onde b e´ um vetor n× 1.
b) Usando o item anterior, verifique que A−1 pode ser obtida atrave´s da resoluc¸a˜o
de n sistemas lineares.
c) Entre os me´todos da Eliminac¸a˜o Gaussiana e a Decomposic¸a˜o LU, qual o mais
indicado para o ca´lculo de A−1? Justifique.
9
d) Utilizando o me´todo escolhido no item anterior, obtenha a 5a coluna da inversa
da seguinte matriz:
A =

4 −1 0 −1 0 0
−1 4 −1 0 −1 0
0 −1 4 0 0 −1
−1 0 0 4 −1 0
0 −1 0 −1 4 −1
0 0 −1 0 −1 4
 .
6. Considere a matriz real T =

b1 c1 0 0
a1 b2 c2 0
0 a2 b3 c3
0 0 a3 b4
.
a) Quais as condic¸o˜es para que T tenha decomposic¸a˜o LU?
b) Sob as condic¸o˜es do item a), encontre adecomposic¸a˜o LU de T .
c) Generalize o resultado do item b) para matrizes T de tamanho n× n.
7. Suponha um sistema linear em que a matriz de coeficientes A tem tamanho 3n× 3n e
possui uma estrutura de blocos, isto e´,
A =

0 M 0
0 0 M
M 0 0
 ,
onde M e´ uma submatriz n×n, invert´ıvel e “0” sa˜o submatrizes nulas n×n. Supondo
que M admite decomposic¸a˜o LU, explique como esta decomposic¸a˜o pode ser utilizada
na resoluc¸a˜o do sistema Ax = b, onde b tem tamanho 3n× 1.
8. Seja A uma matriz invert´ıvel e suponha que A = LU .
a) Mostre que e´ poss´ıvel escrever A = LDUˆ , onde D e´ uma matriz diagonal e Uˆ e´
triangular superior com diagonal unita´ria.
b) Explique como resolver um sistema linear Ax = b utilizando a decomposic¸a˜o
A = LDUˆ .
10
9. Prove ou deˆ um contra-exemplo para a seguinte afirmac¸a˜o: Na fatorac¸a˜o LU obtida com
estrate´gia de pivoteamento parcial, todos os elementos da matriz L sa˜o, em mo´dulo,
menores ou iguais a 1.
10. Uma matriz quadrada A e´ chamada idempotente se A2 = A.
a) Mostre que se A e´ idempotente, det(A) = 0 ou det(A) = 1.
b) Sendo w um vetor n × 1 tal que wTw = 1, mostre que a matriz A = wwT e´
idempotente.
11. Considerando a decomposic¸a˜o LU com estrate´gia de pivoteamento parcial, isto e´,
PA = LU , onde P e´ uma matriz de permutac¸a˜o, escreva uma fo´rmula para det(A).
12. Uma matriz A de ordem n e´ chamada definida-positiva se xTAx > 0 para todo x ∈ Rn
na˜o nulo (xT e´ o transposto do vetor x de tamanho n× 1).
a) Mostre que se A e´ definida-positiva, os elementos da diagonal principal de A sa˜o
todos positivos, ou seja, aii > 0 para todo i = 1, 2, . . . , n.
b) Mostre que a matriz A =
(
4 −1
−1 4
)
e´ definida-positiva.
c) Mostre que a matriz A = I +wwT e´ definida-positiva, onde w e´ um vetor n× 1 e
I e´ a matriz identidade de ordem n.
d) A Decomposic¸a˜o de Cholesky diz que uma matriz A sime´trica e definida-
positiva de ordem n pode ser decomposta na forma A = GGT , onde G e´ uma
matriz triangular inferior com diagonal estritamente positiva. Obtenha a decom-
posic¸a˜o de Cholesky da matriz A do item b). Confiram sua resposta utilizando o
comando CholeskyDecomposition[ ] do software Mathematica.
e) No caso em que wTw = 1, obtenha todos os elementos da decomposic¸a˜o de Cho-
lesky de A.
f) Seja A uma matriz de ordem n sime´trica e definida-positiva. Explique como
utilizar a decomposic¸a˜o de Cholesky de A para resolver um sistema linear do tipo
Ax = b.
13. Seja A uma matriz n× n invert´ıvel e suponha que A = L · U . Descreva uma maneira
eficiente de resolver cada problema abaixo para que o nu´mero de operac¸o˜es realizadas
seja o menor poss´ıvel e o ca´lculo expl´ıcito da inversa de A seja evitado. Justifique os
procedimentos adotados.
a) problema 1: calcule a soma
∑m
i=1 v
TA−1wi, onde v e wi sa˜o vetores de tamanho
n× 1 para todo i = 1, 2, . . . ,m.
11
b) problema 2: calcule o vetor x = (A−1 + (A−1)2)b, onde b possui tamanho n× 1.
c) problema 3: resolva o sistema linear com a seguinte estrutura de blocos
A B 0
0 AT B
0 0 A
 ·

x1
x2
x3
 =

b
c
d
 ,
onde B tem tamanho n×n (na˜o e´ necessariamente invert´ıvel) e b, c e d sa˜o vetores
de tamanho n×1. Observe que x1, x2 e x3 tambe´m sa˜o vetores de tamanho n×1.
14. Considere um sistema linear Ax = b com infinitas soluc¸o˜es onde A possui tamanho
m × n com m < n. O Problema de Norma Mı´nima consiste em encontrar x que
satisfaz Ax = b e possui a menor norma poss´ıvel. Esta situac¸a˜o pode ser formulada
como um problema de otimizac¸a˜o da forma
minimizar ‖x‖2 restrito a Ax = b.
A soluc¸a˜o o´tima desse problema e´ dada por x∗ = AT (AAT )−1b. Considerando
A =
(
1 −1 2
1 1 −1
)
e b =
(
1
0
)
,
a) Interprete este problema geometricamente, ou seja, descreva o conjunto soluc¸a˜o
do sistema Ax = b. O que representa a soluc¸a˜o de norma mı´nima neste caso?
b) Proponha uma forma de obter a soluc¸a˜o de norma mı´nima associada ao sistema
Ax = b sem que seja necessa´rio calcular explicitamente qualquer inversa de matriz.
15. Um modelo simples para um ve´ıculo que se movimenta em uma dimensa˜o e´ dado por s1(t + 1)
s2(t + 1)
 =
 1 1
0 0.95
 ·
 s1(t)
s2(t)
+
 0
0.1
u(t),
onde s1(t), s2(t) sa˜o, respectivamente, a posic¸a˜o e a velocidade no instante de tempo t
e u(t) e´ a energia fornecida no instante t que afeta tanto a posic¸a˜o quanto a velocidade
do carro. Considerando o intervalo de tempo [0, N ] discretizado com ∆t = 1, isto e´,
tk = k∆t, supomos que o ve´ıculo esta´ inicialmente em respouso, isto e´, s1(0) = 0 e
s2(0) = 0. Desejamos determinar os valores u(0), u(1), . . . , u(N) para que o carro seja
trazido ate´ a configurac¸a˜o final s1(N) = 10, s2(N) = 0 gastando a menor quantidade de
energia poss´ıvel durante o trajeto percorrido. Definindo a quantidade total de energia
consumida por
E =
N−1∑
t=0
u(t)2,
12
a) formule esta situac¸a˜o como um problema de norma mı´nima do tipo
minimizar ‖x‖2 restrito a Ax = b.
Identifique claramente o vetor de varia´veis x, a matriz A e o vetor b em sua
formulac¸a˜o.
b) utilize comandos espec´ıficos do software Mathematica para resolver o problema
formulado considerando os seguintes valores de N : N = 2, N = 10 e N = 30.
Observe que e´ poss´ıvel resolver o problema de duas formas: atrave´s da rotina
LinearSolve[ ] com a fo´rmula para x∗ apresentada no exerc´ıcio 11 e usando o
comando FindMinimum[ ], resolvendo o exer´ıcio como um problema de oti-
mizac¸a˜o. Resolva da maneira que achar mais adequada.
c) Fac¸a um gra´fico tk × u(tk) para cada soluc¸a˜o o´tima obtida no item b).
16. Seja A uma matriz m× n com m < n e considere o conjunto
S = {x ∈ Rn | Ax = 0}.
Em um computador, a projec¸a˜o ortogonal w de um vetor v ∈ Rn sobre o conjunto S
pode ser determinada atrave´s dos seguintes passos:
Passo 1: calcule z = (AAT )−1Av,
Passo 2: fac¸a w = v − AT z,
onde AT e´ a transposta da matriz A.
a) Mostre que w ∈ S.
b) Para evitar o ca´lculo da inversa (AAT )−1 no Passo 1, podemos obter o vetor z
atrave´s da resoluc¸a˜o de um sistema linear. Que sistema e´ esse?
c) Considerando
A =
(
1 2 1
−1 1 2
)
,
determine a decomposic¸a˜o de Cholesky de AAT . Em seguida, explique como
utilizar esta decomposic¸a˜o para calcular o vetor z no Passo 1 do procedimento
acima.
13