We create a 4-by-4 linear system with the matrix
A = [
2 0 4 3
-4 5 -7 -10
1 15 2 -4.5
-2 0 2 -13
];
and with the right-hand side
b = [ 4; 9; 29; 40 ];
We define an augmented matrix by tacking on the end as a new column.
S = [A, b]
S =
2.0000e+00 0 4.0000e+00 3.0000e+00 4.0000e+00 -4.0000e+00 5.0000e+00 -7.0000e+00 -1.0000e+01 9.0000e+00 1.0000e+00 1.5000e+01 2.0000e+00 -4.5000e+00 2.9000e+01 -2.0000e+00 0 2.0000e+00 -1.3000e+01 4.0000e+01
The goal is to introduce zeros into the lower triangle of this matrix. By using only elementary row operations, we ensure that the matrix always represents a linear system that is equivalent to the original. We proceed from left to right and top to bottom. The first step is to put a zero in the (2,1) location using a multiple of row 1:
mult21 = S(2,1)/S(1,1)
mult21 =
-2
S(2,:) = S(2,:) - mult21*S(1,:)
S =
2.0000e+00 0 4.0000e+00 3.0000e+00 4.0000e+00 0 5.0000e+00 1.0000e+00 -4.0000e+00 1.7000e+01 1.0000e+00 1.5000e+01 2.0000e+00 -4.5000e+00 2.9000e+01 -2.0000e+00 0 2.0000e+00 -1.3000e+01 4.0000e+01
We repeat the process for the (3,1) and (4,1) entries.
mult31 = S(3,1)/S(1,1)
mult31 =
5.0000e-01
S(3,:) = S(3,:) - mult31*S(1,:);
mult41 = S(4,1)/S(1,1)
mult41 =
-1
S(4,:) = S(4,:) - mult41*S(1,:);
S
S =
2 0 4 3 4 0 5 1 -4 17 0 15 0 -6 27 0 0 6 -10 44
The first column has the zero structure we want. To avoid interfering with that, we no longer add multiples of row 1 to anything. Instead, to handle column 2, we use multiples of row 2. We'll also exploit the highly repetitive nature of the operations to write them as a loop.
for i = 3:4
mult = S(i,2)/S(2,2);
S(i,:) = S(i,:) - mult*S(2,:);
end
S
S =
2 0 4 3 4 0 5 1 -4 17 0 0 -3 6 -24 0 0 6 -10 44
We finish out the triangularization with a zero in the (4,3) place. It's a little silly to use a loop for just one iteration, but the point is to establish a pattern.
for i = 4
mult = S(i,3)/S(3,3);
S(i,:) = S(i,:) - mult*S(3,:);
end
S
S =
2 0 4 3 4 0 5 1 -4 17 0 0 -3 6 -24 0 0 0 2 -4
Recall that is an augmented matrix: it represents the system , where
U = S(:,1:4)
U =
2 0 4 3 0 5 1 -4 0 0 -3 6 0 0 0 2
z = S(:,5)
z =
4 17 -24 -4
The solutions to this system are identical to those of the original system, but this one can be solved by backward substitution.
x = backsub(U,z)
x =
-3 1 4 -2
b - A*x
ans =
0 0 0 0