QR Factorization with column pivoting
Define the matrix b.
b=[1 -1 3 1;-1 3 -5 2;2 -1 5 1;1 -1 3 2]
b =
1 -1 3 1
-1 3 -5 2
2 -1 5 1
1 -1 3 2
Show that b is singular.
det(b)
ans =
0
Initialize pivot vector
p=1:4
p =
1 2 3 4
Compute norms of columns
norms=diag(b'*b)'
norms =
7 12 68 10
Swap columns 1 and 3, to put the column with the largest
norm first.
b(:,[1 3])=b(:,[3 1]);norms([1 3])=norms([3 1]);p([1 3])=p([3 1]);
norms, p
norms =
68 12 7 10
p =
3 2 1 4
1st Householder vector.
v1=b(:,1); v1(1)=v1(1)-norms(1)^(1/2);
Transform b with 1st Housholder matrix.
b=b-(2/(v1'*v1))*v1*v1'*b
b =
8.2462 -3.1530 2.5466 0.4851
0 0.9481 0.4740 1.5092
0 1.0519 0.5260 1.4908
0 0.2312 0.1156 2.2945
norms=norms - b(1,:).*b(1,:)
norms =
0 2.0588 0.5147 9.7647
Swap columns 2 and 4.
b(:,[2 4])=b(:,[4 2]);norms([2 4])=norms([4 2]);p([2 4])=p([4 2]);
2nd Householder vector.
v2=b(:,2); v2(1)=0;v2(2)=v2(2)-norms(2)^(1/2);
Apply 2nd housholder transform to b
b=b-(2/(v2'*v2))*v2*v2'*b
b =
8.2462 0.4851 2.5466 -3.1530
0 3.1249 0.5647 1.1295
0 -0.0000 0.4423 0.8846
0 0 -0.0132 -0.0264
norms=norms - b(2,:).*b(2,:)
norms =
0 0 0.1958 0.7831
Swap columns 3 and 4.
b(:,[3 4])=b(:,[4 3]);norms([3 4])=norms([4 3]);p([3 4])=p([4 3]);
3rd Householder vector.
v3=b(:,3); v3(1:2)=0;v3(3)=v3(3)-norms(3)^(1/2);
Apply 3rd housholder transform to b
b=b-(2/(v3'*v3))*v3*v3'*b
b =
8.2462 0.4851 -3.1530 2.5466
0 3.1249 1.1295 0.5647
0 -0.0000 0.8849 0.4425
0 0.0000 -0.0000 -0.0000
p =
3 4 2 1
MATLAB qr with column pivoting.
[u,v,e]=qr([1 -1 3 1;-1 3 -5 2;2 -1 5 1;1 -1 3 2])
u =
-0.3638 -0.2635 0.1702 -0.8771
0.6063 -0.7342 -0.2927 -0.0877
-0.6063 -0.2259 -0.7420 0.1754
-0.3638 -0.5836 0.5786 0.4385
v =
-8.2462 -0.4851 3.1530 -2.5466
0 -3.1249 -1.1295 -0.5647
0 0 -0.8849 -0.4425
0 0 0 -0.0000
e =
0 0 0 1
0 0 1 0
1 0 0 0
0 1 0 0
Show pivot vector; compare with e above.
p
p =
3 4 2 1
Note that e=I(:,[3 4 2 1]).