Resolvendo sistemas lineares compatíveis

Prévia do material em texto

Resolvendo sistemas lineares
compatíveis.
Definindo o problema.
Vamos resolver um problema na forma Ax = b, 
com A ( (m(n, n > m, posto(A) = m.
Como caracterizar as soluções de Ax = b?
Achando uma solução particular, x0.
Achando uma base para N(A), Z ( (n((n-m).
Escrevendo as soluções na forma x = x0 + Zv, 
onde v ( ((n-m) é um vetor qualquer.
Um exemplo:
A=[1 2 3 4; 2 4 -1 1]
A =
 1 2 3 4
 2 4 -1 1
b=[2;-3]
b =
 2
 -3
Usando a decomposição LU com permutações de linhas e de colunas.
Podemos decompor A na forma:
PAQ = LU,
onde L ( (m(m é triangular inferior unitária, U ( (m(n é trapezoidal superior, P ( (m(m é uma matriz de permutação de linhas e Q ( (n(n é uma matriz de permutação de colunas.
Neste caso, se Ax = b, então PAQQTx = Pb.
Podemos definir z = QTx, obtendo LUz = Pb.
Dividimos, agora, a matriz U na forma U = [U1 U2], onde U1 ( (m(m é triangular superior e U2 ( (m((n-m).
Dividimos, também, o vetor z em 
, onde z1 ( (m e z2 ( ((n-m).
Obtemos assim, o sistema 
.
Escolhendo z2 = 0, obtemos z1 resolvendo o sistema
LU1z1 = Pb.
Finalmente, calculamos x0 fazendo 
.
Para nosso exemplo, temos:
[L,U,P,Q]=lu(sparse(A));
L=full(L)
L =
 1 0
 2 1
U=full(U)
U =
 1 4 3 2
 0 -7 -7 0
P=full(P)
P =
 1 0
 0 1
Q=full(Q)
Q =
 1 0 0 0
 0 0 0 1
 0 0 1 0
 0 1 0 0
U1=U(:,1:2)
U1 =
 1 4
 0 -7
U2=U(:,3:4)
U2 =
 3 2
 -7 0
y=L\(P*b)
y =
 2
 -7
z1=U1\y
z1 =
 -2
 1
z2=zeros(2,1)
z2 =
 0
 0
z=[z1;z2]
z =
 -2
 1
 0
 0
x=Q*z
x =
 -2
 0
 0
 1
norm(A*x-b)
ans =
 0
O vetor x que obtivemos é a solução de Ax = b que tem o maior número de elementos nulos.
Agora, vamos encontrar uma base Z para N(A).
Para tanto, devemos observar que AZ = 0.
Assim, PAQQTZ = 0, ou seja, LUQTZ = 0.
Lembrando que U = [U1 U2] e escrevendo 
, onde W1 ( (m((n-m) e W2 ( ((n-m)((n-m), obtemos 
Para que esse sistema seja satisfeito, tomamos 
 e W2 = In-m.
Assim, 
.
Observe, entretanto que esta base não é ortonormal.
Para nosso exemplo, temos:
Z=Q*[-inv(U1)*U2;eye(2)]
Z =
 1 -2
 0 1
 1 0
 -1 0
A*Z
ans =
 0 0
 0 0
Usando a decomposição QR com permutações de colunas.
Podemos decompor A na forma:
AP = QR,
onde Q ( (m(m é ortogonal, R ( (m(n é trapezoidal superior e P ( (n(n é uma matriz de permutação de colunas.
Neste caso, se Ax = b, então APPTx = b.
Podemos definir z = PTx, obtendo QRz = b.
Dividimos, agora, a matriz R na forma R = [R1 R2], onde R1 ( (m(m é triangular superior e R2 ( (m((n-m).
Dividimos, também, o vetor z em 
, onde z1 ( (m e z2 ( ((n-m).
Obtemos assim, o sistema 
.
Escolhendo z2 = 0, obtemos z1 resolvendo
R1z1 = QTb.
Finalmente, calculamos x0 fazendo 
.
Para nosso exemplo, temos:
[Q,R,P]=qr(A)
Q =
 -0.44721 -0.89443
 -0.89443 0.44721
R =
 -4.4721 -0.44721 -2.2361 -2.6833
 0 -3.1305 2.2204e-016 -3.1305
P =
 0 0 1 0
 1 0 0 0
 0 1 0 0
 0 0 0 1
R1=R(:,1:2)
R1 =
 -4.4721 -0.44721
 0 -3.1305
R2=R(:,3:4)
R2 =
 -2.2361 -2.6833
 2.2204e-016 -3.1305
z1=R1\(Q'*b)
z1 =
 -0.5
 1
z2=zeros(2,1)
z2 =
 0
 0
z=[z1;z2]
z =
 -0.5
 1
 0
 0
x=P*z
x =
 0
 -0.5
 1
 0
norm(A*x-b)
ans =
 8.8818e-016
Mais uma vez, o vetor x que obtivemos é a solução de Ax = b que tem o maior número de elementos nulos.
Como no caso da decomposição LU, uma base (não ortonormal) de N(A) é dada por
.
Para nosso exemplo, temos:
Z=P*[-inv(R1)*R2;eye(2)]
Z =
 1 0
 -0.5 -0.5
 7.093e-017 -1
 0 1
A*Z
ans =
 2.1279e-016 8.8818e-016
 -7.093e-017 3.3307e-016
Usando a decomposição QR de AT.
Podemos decompor AT na forma:
AT = QR,
onde Q ( (n(n é ortogonal e R ( (n(m é triangular superior.
Neste caso, se Ax = b, então RTQTx = b.
Podemos definir z = QTx, obtendo RTz = b.
Dividimos, agora, a matriz R na forma 
, onde R1 ( (m(m é triangular superior.
Dividimos, também, o vetor z em 
, onde z1 ( (m e z2 ( ((n-m).
Obtemos assim, o sistema 
.
Escolhendo z2 = 0, obtemos z1 resolvendo
.
Finalmente, calculamos x0 fazendo 
.
Como Q é ortogonal, 
. 
Assim, como z1 é a única solução de 
, a norma de z e, conseqüentemente, de x0 será mínima se z2 = 0.
Dizemos, então, que 
 é a solução de norma mínima de Ax = b.
Para nosso exemplo, temos:
[Q,R]=qr(A')
Q =
 -0.18257 -0.38534 -0.53949 -0.72604
 -0.36515 -0.77067 0.50733 0.12388
 -0.54772 0.49543 0.47517 -0.47829
 -0.7303 0.1101 -0.47517 0.47829
R =
 -5.4772 -2.0083
 0 -4.2387
 0 0
 0 0
R1=R(1:2,:)
R1 =
 -5.4772 -2.0083
 0 -4.2387
z1=(R1')\b
z1 =
 -0.36515
 0.88077
z2=zeros(2,1)
z2 =
 0
 0
z=[z1;z2]
z =
 -0.36515
 0.88077
 0
 0
x=Q*z
x =
 -0.27273
 -0.54545
 0.63636
 0.36364
norm(A*x-b)
ans =
 8.8818e-016
Uma base ortonormal de N(A) pode ser obtida fazendo-se Q = [Q1 Q2], onde Q1 ( (n(m e Q2 ( (n((n-m). 
Neste caso,
Z = Q2.
Para nosso exemplo, temos:
Z2=Q(:,3:4)
Z =
 -0.53949 -0.72604
 0.50733 0.12388
 0.47517 -0.47829
 -0.47517 0.47829
A*Z
ans =
 -4.4409e-016 6.6613e-016
 -1.6653e-016 4.996e-016
Usando a SVD de A.
Podemos decompor A na forma:
A = USVT,
onde U ( (m(m é ortogonal, V ( (n(n é ortogonal e S ( (m(n é diagonal (com sii > 0, i=1,...,m, pois posto(A) = m).
Neste caso, se Ax = b, então USVTx = b.
Podemos definir z = VTx, obtendo Sz = UTb.
Dividimos, agora, a matriz S na forma S = [S1 0], onde S1 ( (m(m é diagonal.
Dividimos, também, o vetor z em 
, onde z1 ( (m e z2 ( ((n-m).
Obtemos assim, o sistema 
.
Escolhendo z2 = 0, obtemos z1 resolvendo
.
Finalmente, calculamos x0 fazendo 
.
Como no caso da decomposição QR de AT, V é ortogonal e 
. 
Assim, 
 é solução de norma mínima de Ax = b.
Para nosso exemplo, temos:
[U,S,V]=svd(A)
U =
 -0.81907 -0.5737
 -0.5737 0.81907
S =
 6.1404 0 0 0
 0 3.7809 0 0
V =
 -0.32025 0.28153 -0.53949 -0.72604
 -0.6405 0.56306 0.50733 0.12388
 -0.30674 -0.67184 0.47517 -0.47829
 -0.62699 -0.39031 -0.47517 0.47829
S1=S(:,1:2)
S1=
 6.1404 0
 0 3.7809
z1=S1\(U'*b)
z1 =
 0.01351
 -0.95337
z2=zeros(2,1)
z2 =
 0
 0
z=[z1;z2]
z =
 0.01351
 -0.95337
 0
 0
x=V*z
x =
 -0.27273
 -0.54545
 0.63636
 0.36364
norm(A*x-b)
ans =
 1.7342e-015
Uma base ortonormal de N(A) pode ser obtida fazendo-se V = [V1 V2], onde V1 ( (n(m e V2 ( (n((n-m). 
Neste caso,
Z = V2.
Para nosso exemplo, temos:
Z=V(:,3:4)
Z =
 -0.53949 -0.72604
 0.50733 0.12388
 0.47517 -0.47829
 -0.47517 0.47829
A*Z
ans =
 -4.4409e-016 6.6613e-016
 -1.6653e-016 4.996e-016
_1145207331.unknown
_1145209204.unknown
_1145212262.unknown
_1145213331.unknown
_1145213407.unknown
_1145213469.unknown
_1145213385.unknown
_1145212676.unknown
_1145212201.unknown
_1145212225.unknown
_1145209499.unknown
_1145208221.unknown
_1145208729.unknown
_1145208858.unknown
_1145208298.unknown
_1145207934.unknown
_1145207973.unknown
_1145207467.unknown
_1145207047.unknown