6.4 Linear Systems 171
b 11 x 1 +b 12 x 2 +b 13 x 3 +b 14 x 4 =y 1
b 22 x 2 +b 23 x 3 +b 24 x 4 =y 2
b 33 x 3 +b 34 x 4 =y 3
b 44 x 4 =y 4.We can solve this system of equations recursively starting fromxn(in our casex 4 ) and proceed
with what is called a backward substitution. This process can be expressed mathematically
as
xm=1
bmm(
ym−n
∑
k=m+ 1bmkxk)
m=n− 1 ,n− 2 ,..., 1.To arrive at such an upper triangular system of equations, westart by eliminating the un-
knownx 1 for j= 2 ,n. We achieve this by multiplying the first equation byaj 1 /a 11 and then
subtract the result from thejth equation. We assume obviously thata 116 = 0 and thatAis not
singular. We will come back to this problem below.
Our actual 4 × 4 example reads after the first operation
a 11 a 12 a 13 a 14
0 (a 22 −a^21 a 11 a^12 ) (a 23 −a^21 a 11 a^13 ) (a 24 −a^21 a 11 a^14 )
0 (a 32 −a^31 a 11 a^12 ) (a 33 −a^31 a 11 a^13 ) (a 34 −a^31 a 11 a^14 )
0 (a 42 −a^41 a 11 a^12 ) (a 43 −a^41 a 11 a^13 ) (a 44 −a^41 a 11 a^14 )
x 1
x 2
x 3
x 4
=
y 1
w( 22 )
w( 32 )
w( 42 )
.
or
b 11 x 1 +b 12 x 2 +b 13 x 3 +b 14 x 4 = y 1
a( 222 )x 2 +a( 232 )x 3 +a( 242 )x 4 =w( 22 )
a( 322 )x 2 +a( 332 )x 3 +a( 342 )x 4 =w( 32 )
a( 422 )x 2 +a( 432 )x 3 +a( 442 )x 4 =w( 42 ),
(6.17)with the new coefficients
b 1 k=a( 11 k) k= 1 ,...,n,
where eacha( 11 k)is equal to the originala 1 kelement. The other coefficients are
a(jk^2 )=a(jk^1 )−a(j^11 )a( 11 k)
a( 111 )j,k= 2 ,...,n,with a new right-hand side given by
y 1 =w( 11 ),w(j^2 )=w(j^1 )−a(j^11 )w( 11 )
a( 111 )j= 2 ,...,n.We have also setw( 11 )=w 1 , the original vector element. We see that the system of unknowns
x 1 ,...,xnis transformed into an(n− 1 )×(n− 1 )problem.
This step is called forward substitution. Proceeding with these substitutions, we obtain the
general expressions for the new coefficients
a(jkm+^1 )=a(jkm)−a(jmm)a(mkm)
a(mmm)j,k=m+ 1 ,...,n,