[Prévia] [Próxima] [Prévia por assunto] [Próxima por assunto]
[Índice cronológico]
[Índice de assunto]
Gabarito da lista 04 de exercícios
- Subject: Gabarito da lista 04 de exercícios
- From: Paulo Feofiloff <pf@ime.usp.br>
- Date: Mon, 09 Apr 2001 16:10:24 -0300
Gabarito da Lista 04 de exercícos
---------------------------------
1. Seja A a matriz da figura. Calcule uma matriz G tal que GA
seja escalonada.
0 1 2 7 -2 -1 3
1 1 1 4 2 -2 3
2 1 1 3 6 -3 4
0 1 -1 1 -2 -1 0
Diga explicitamente qual a base de linhas e a base de colunas de GA.
Exiba também uma matriz F tal que FG = I. Supondo
5
b = 4
1
8 ,
encontre um vetor x tal que Ax = b ou prove que tal x não existe.
Repita com
4
b = 4
5
1 .
SOLUÇÃO ---------------------------------------------------------
Eis a matriz G (à esquerda) e a matriz escalonada GA (à direita):
-1 4 -2 0 0 1 0 3 -2 -1 1
0 -1 1 0 1 0 0 -1 4 -1 1
1 -2 1 0 0 0 1 2 0 0 1
2 -6 3 1 0 0 0 0 0 0 0
[É possível que suas matrizes sejam diferentes, porque você pode
ter executado pivotações em posições diferentes da matriz.]
Como as linhas da matriz A estão implicitamente indexadas por
1,2,3,4 de cima para baixo e as colunas estão indexadas por 1,..,7
da esquerda para a direita, a base linhas da matriz escalonada GA
é {1,2,3} e a base de colunas é {1,2,3}.
Para comprovar que G é inversível pela esquerda, basta verificar
que FG = I, onde F é a matriz abaixo:
1 0 2 0
1 1 1 0
1 2 1 0
1 0 -1 1
(Não é difícil determinar F olhando para GA e A.)
Para o primeiro vetor b, não existe x tal que Ax = b. Eis a prova
dessa afirmação:
gA = 0 enquanto gb = -8,
onde g é a linha 4 de G. Para o segundo vetor b, existe x tal que
Ax = b. Um tal vetor é
x = 1 2 1 0 0 0 0 ,
mas existem muitos outros.
-----------------------------------------------------------------
2. [2.12, p.25 das notas de aula]
Encontre números x_1,..,x_4 que satisfaçam as equações abaixo.
x_1 + x_2 + x_3 + 3x_4 = 6
3x_1 + 4x_2 + x_3 + 8x_4 = 18
-x_1 + x_2 - 4x_3 - 4x_4 = -5
SOLUÇÃO ---------------------------------------------------------
Basta aplicar o algoritmo de Gauss-Jordan:
x_1 + x_2 + x_3 + 3x_4 = 6
x_2 - 2x_3 - x_4 = 0
2x_2 - 3x_3 - x_4 = 1
x_1 + 3x_3 + 4x_4 = 6
x_2 - 2x_3 - x_4 = 0
x_3 + x_4 = 1
x_1 + x_4 = 3
x_2 + x_4 = 2
x_3 + x_4 = 1
x_1 = 3
x_2 = 2
x_3 = 1
x_4 = 0
-----------------------------------------------------------------
3. Escreva um algoritmo que receba uma matriz D com uma só linha
e devolva matrizes F e G tais que FG = I e GD é escalonada.
Repita o exercício para o caso em que D tem suas linhas.
SOLUÇÃO, para matriz de uma linha -------------------------------
Se D tem uma só linha então as matrizes F e G têm um só componente,
digamos f e g respectivamente.
O algoritmo recebe uma matriz D sobre {m}xN e devolve números
f e g e uma matriz E tais que fg = 1, E = gD e E é escalonada.
CASO 1: D != 0.
Escolha k em N tal que D[m,k] != 0.
Seja f = D[m,k], d = D[m,k], g = 1/d e E[m, ] = D[m, ]/d.
Devolva f, g, E e pare.
CASO 2: D = 0.
Adote f = g = 1. Devolva f, g, D e pare.
SOLUÇÃO, para matriz com duas linhas ----------------------------
O algoritmo recebe uma matriz D sobre MxN com |M|=2 e devolve
matrizes F e G sobre MxM tais que FG = I e GD é escalonada.
CASO 1: D[h, ] != 0 para algum h em M.
Escolha k em N tal que D[h,k] != 0.
Seja m o único elemento de M-h.
Seja d = D[h,k] e d' = D[m,k].
Defina F, G e E da seguinte maneira:
F[ ,h] = D[ ,k] e F[ ,m] = I[ ,m],
G[h, ] = I[h, ]/d e G[m, ] = I[m, ] - d'I[h, ]/d.
E[h, ] = D[h, ]/d e E[m, ] = D[m, ] - d'D[h, ]/d.
SUBCASO 1.1: E[m, ] != 0.
Escolha k em N tal que E[m,k] != 0.
Seja e = E[m,k] e e' = E[h,k].
Defina F' e G' da seguinte maneira:
F'[ ,m] = E[ ,k] e F'[ ,h] = F[ ,h],
G'[m, ] = G[m, ]/e e G'[h, ] = G[h, ] - e'G[m, ]/e.
Devolva F', G' e pare.
SUBCASO 1.2: E[m, ] = 0.
Devolva F, G e pare.
CASO 2: D = 0.
Adote F = G = I. Devolva F, G e pare.
-----------------------------------------------------------------
4. [2.7, p. 24 das notas de aula]
Suponha que a execução do algoritmo de Gauss-Jordan é interrompida
no início de uma iteração e que uma pivotação é executada em torno
de um elemento h de P (e não de M-P, como é usual) e um elemento
k de N-Q. É claro que isso só faz sentido se E[h,k] != 0. [Estou
usando notação C: ``!='' significa ``diferente de''.]
Qual o efeito de tal pivotação? A execução do algoritmo pode ser
retomada depois da pivotação excepcional?
SOLUÇÃO ---------------------------------------------------------
A pivotação não altera a base de linhas mas "muda de lugar" uma das
colunas da base de colunas Q. Mais especificamente, se q é o
elemento de Q para o qual E[h,q]=1 então a pivotação troca Q por
Q-q+k.
O algoritmo é bastante "robusto": a execução do algoritmo pode ser
retomada, sem qualquer sobressalto, depois da pivotação excepcional.
-----------------------------------------------------------------
5. [OPCIONAL] [2.3+2.4+2.5+2.6, p. 24 das notas de aula]
Escreva o algoritmo de Gauss-Jordan em uma linguagem mais formal,
mais próxima de PASCAL ou C. Faça com que seu algoritmo devolva
não somente a matrizes F e G mas também a matriz escalonada E e
suas bases P e Q.
Para tornar o algoritmo um pouco mais eficiente, calcule a matriz
F somente no fim da última iteração. Além disso, execute apenas
implicitamente a parte da operação de pivotação que afeta a base de
colunas Q e a coluna k.
SOLUÇÃO ---------------------------------------------------------
Alguém resolveu este?
-----------------------------------------------------------------
-----------------------------------------------------------------
CONFIRA minhas soluções (eu tenho o hábito de cometer erros)!
Mande seus comentários sobre o gabarito para lista de discussão!
Quando voltar a SP, o Coelho colocará esse gabarito no lugar
apropriado da sítio da disciplina.
--Paulo
- Follow-Ups:
- Gauss-Jordan
- From: "Humberto Goulart Rigotti" <hrigotti@uol.com.br>