3.1 Gaussian Elimination
In Exercises 1 – 5, write out the augmented matrix for the indicated linear
system of equations and then obtain the solution using Gaussian elimination
with back substitution.
1.
2x1−x2+x3=−1
4x1+ 2x2+x3= 4
6x1−4x2+ 2x3=−2
The corresponding augmented matrix is
Using Gaussian elimination, we obtain
By back substitution, we find
2.
1
3x1+2
3x2+ 2x3=−1
x1+ 2x2+3
2x3=3
2
1
2x1+ 2x2+12
5x3=1
10
2Section 3.1
The corresponding augmented matrix is
Using Gaussian elimination, we obtain
By back substitution, we find
3.
x1+ 2x2−x3= 1
2x1−x2+x3= 3
−x1+ 2x2+ 3x3= 7
The corresponding augmented matrix is
Using Gaussian elimination, we obtain
By back substitution, we find
Gaussian Elimination 3
x2=1−3(2)
−5= 1;
x1=1 + 1(2) −2(1)
1= 1.
Therefore, x=112T.
4.
x2+x3+x4= 0
3x1+ 3x3−4x4= 7
x1+x2+x3+ 2x4= 6
2x1+ 3x2+x3+ 3x4= 6
The corresponding augmented matrix is
Using Gaussian elimination, we obtain
h0i1 1 1 0
h1i1 1 2 6
By back substitution, we find
x4=−40/3
4Section 3.1
5.
3x1−x2+ 3x3+x4= 6
6x1+ 9x3−2x4= 13
−12x1−10x3+ 5x4=−17
72x1−8x2+ 48x3−19x4= 93
The corresponding augmented matrix is
Using Gaussian elimination, we obtain
h3i −1 3 1 6
3−1 3 1 6
By back substitution, we find
x4=−5
6. Let Ube an n×nupper triangular matrix. Show that det(U) = u11u22 u33 ···unn.
Gaussian Elimination 5
Thus, we find
det(U) = det
u11 u12 u13 · · · u1n
0u22 u23 u2n
0 0 u33 u3n
· · ·
· · ·
· · ·
0 0 0 · · 0unn
=u11 det
u22 u23 u24 · · · u2n
0u33 u34 u3n
0 0 u44 u4n
· · ·
· · ·
· · ·
0 0 0 · · 0unn
=u11u22 det
u33 u34 u35 · · · u3n
0u44 u45 u4n
0 0 u55 u5n
· · ·
· · ·
· · ·
0 0 0 · · 0unn
=···
=u11u22 u33 ···un−1,n−1det ([unn])
=u11u22 u33 ···unn.
7. Suppose we had not assigned the value 0 to the element arow,pass in our Gaus-
sian elimination pseudocode and had instead computed the value inside the
innermost loop. How many arithmetic operations would that have added to the
operation count for the elimination phase?
6Section 3.1
8. (a) Construct an algorithm to carry out Gauss-Jordan elimination; i.e., during
each pass through the matrix, generate zeros both above and below the
pivot element; after all npasses, place ones along the diagonal.
(b) Show that the total number of arithmetic operations needed to solve a
system of nequations in nunknowns using Gauss-Jordan elimination is
n3+n2−n.
(a) The pseudocode below carries out Gauss-Jordan elimination.
%
Gaussian Elimination 7
(b) The number of arithmetic operations needed to generate zeros below the di-
agonal is
whereas the number of arithmetic operations needed to generate zeros above
the diagonal is
9. The inverse of an n×nmatrix can be computed by performing Gauss-Jordan
elimination on an n×2naugmented matrix, where the last ncolumns are the
n×nidentity matrix.
(a) Show that if one naively applies Gauss-Jordan elimination without taking
into account the structure of the identity matrix, then computation of the
inverse requires 3n3−2n2arithmetic operations.
(b) Show that if one takes into account the structure of the identity matrix
(and does not perform multiplication when the matrix element is a one and
does not perform addition/subtraction when one of the elements is known
to be zero), then computation of the inverse can be reduced to 2n3−2n2+n
operations.
8Section 3.1
(a) The pseudocode below naively applies Gauss-Jordan elimination to determine
the inverse of a matrix without taking into account the structure of the identity
matrix.
%
%
Gaussian Elimination 9
(b) The pseudocode below applies Gauss-Jordan elimination to determine the in-
10 Section 3.1
%
%
Gaussian Elimination 11
10. (a) Solve the system
3.02x1−1.05x2+ 2.53x3=−1.61
4.33x1+ 0.56x2−1.78x3= 7.23
−0.83x1−0.54x2+ 1.47x3=−3.38
using Gaussian elimination with back substitution.
(b) Change the coefficient of x1in the first equation to 3.01 and solve the
resulting system. By what percentage have the three components of the
solution vector changed?
(c) Return the coefficient of x1in the first equation to 3.02, but change the
right-hand side of the last equation to −3.39 and solve the resulting sys-
tem. By what percentage have the three components of the solution vector
changed from their values in part (a)?
(a) Let’s first write each coefficient and right-hand side value as a rational number.
(b) After changing the coefficient of x1in the first equation to 3.01 = 301
100 , Gaus-
12 Section 3.1
(c) After returning the coefficient of x1in the first equation to 3.02 = 151
The percentage change in each component of the solution vector is
11. (a) Solve the system
6x1−2x2+ 3x3= 5
x1−1
3x2+1
3x3= 2
x1+ 3x2−x3= 5
using Gaussian elimination with back substitution.
(b) Change the coefficient of x1in the first equation to 6.01 and solve the
resulting system. By what percentage have the three components of the
solution vector changed?
(c) Return the coefficient of x1in the first equation to 6, but change the right-
hand side of the second equation to 1.99 and solve the resulting system. By
what percentage have the three components of the solution vector changed
from their values in part (a)?
Gaussian Elimination 13
(a) Gaussian elimination applied to the augmented matrix for the given system of
(b) After changing the coefficient of x1in the first equation to 6.01 = 601
100 , Gaus-
sian elimination produces the augmented matrix
The percentage change in each component of the solution vector is
(c) After returning the coefficient of x1in the first equation to 6 and changing the
14 Section 3.1
12. Let Abe the n×nmatrix whose entries are given by aij = 1/(i+j−1) for
1≤i, j ≤n.
(a) For n= 5,6 and 7, solve the system Ax=busing single precision arith-
metic. In each case, take bas the vector that corresponds to an exact
solution of xi= 1 for each i= 1,2,3, …, n. Calculate the maximum
component-wise error between the computed solution and the exact so-
lution for each n.
(b) For n= 11,12 and 13, solve the system Ax=busing double precision
arithmetic. In each case, take bas the vector that corresponds to an ex-
act solution of xi= 1 for each i= 1,2,3, …, n. Calculate the maximum
component-wise error between the computed solution and the exact solu-
tion for each n.
(a) The components of the solution for each system are listed in the table below.
n= 5 n= 6 n= 7
x11.00008 1.00039 1.00083
(b) The components of the solution for each system are listed in the table below.
n= 11 n= 12 n= 13
x21.00000 1.00000 0.999984
x41.00016 1.00112 0.989763
x61.00329 1.03538 0.501003
x81.00973 1.17542 −3.03606
x10 1.00373 1.14866 −5.49353
x12 1.01102 −0.618191
13. The circuit shown below could be used as part of a system for charging a car
battery. Assuming that the internal resistance of the generator and the battery
are negligible and applying Kirchoff’s loop equation around the left and right
loops of the circuit (traveling counterclockwise about the left loop and clockwise
around the right loop) produces the equations
−4I2+ 15I3= 12 and 10I1+ 15I3= 100.
Balancing the current flowing into and out from the junction between the 4 Ω
and 10 Ω resistors yields the equation I1=I2+I3. Determine the current
flowing through each branch of the circuit.
12 V
15 Ω
4 Ω
10 Ω
DC
Generator
100 V
I1
I2
I3
We organize the equations into the augmented matrix
14. Consider a simple economy which consists of three sectors: food, clothing and
shelter. The production of one unit of food requires 0.43 units of food, 0.17 units
of clothing and 0.18 units of shelter. The production of one unit of clothing
16 Section 3.1
15. Suppose the coefficient matrix and the control vector for the longitudinal dy-
namics of an aircraft are given by
A=
−0.0507 −3.861 0 −32.17
−0.00117 −0.5164 1 0
−0.000129 1.4168 −0.4932 0
0 0 1 0
and b=0−0.0717 −1.645 0 T, respectively. In order to change the
open loop coefficient vector a=1.0603 −1.115 −0.0565 −0.0512 Tinto
the closed loop coefficient vector ˆ
a=2.52 6.31 0.150 0.0625 T, the gain
vector, g, in the feedback control law must satisfy the equation
(QW )Tg=ˆ
a−a.
The matrix Qtakes the form Q=bAbA2bA3b, and
W=
1 1.0603 −1.115 −0.0565
0 1 1.0603 −1.115
0 0 1 1.0603
0 0 0 1
.
Gaussian Elimination 17
Compute g.
With the given matrix Aand vector b, we calculate
The right-hand side vector is
16. Solve the system of equations associated with the “Forces in a Plane Truss”
problem capsule presented in the Chapter 3 Overview (see page 138).
The augmented matrix for the system can be written as
In order, the columns represent the forces F1,F2,F3,F4,F5,FR,FHand FV.