349A ASSIGNMENT #4

• The total number of points for this assignment is 20.
1
1. Let
A =




0 −2 −2 −4
−1 −1 1 0
2 4 −2 0
1 1 −1 0.5




(a) (4 points) Use Gaussian elimination with partial pivoting to compute the fourth
column vector of A−1
. Do this by hand computation, no programming. (Do not
compute all of A−1
.) Explicitly interchange rows as required, and show all of the
derived linear systems and the back substitution. Do not do any scaling.
(b) (2 points) From the computations in (a), what is the determinant of A? (Show
explicitly how you obtain this, including how the sign of the determinant is obtained.)
2. (a) (2 points) Let A be an n × n nonsingular lower triangular matrix with all of its
nonzero entries on three diagonals of the matrix: the main diagonal, the first subdiagonal and the second sub-diagonal; that is,











a1,1
a2,1 a2,2
a3,1 a3,2 a3,3
a4,2 a4,3 a4,4
.
.
.
.
.
.
.
.
.
an−1,n−3 an−1,n−2 an−1,n−1
an,n−2 an,n−1 an,n











Note that A is nonsingular if and only if all of the entries on its main diagonal are
nonzero, that each row of A contains at most 3 nonzero entries, and that entries on the
first sub-diagonal and the second sub-diagonal may be nonzero or zero. For example,
if n = 6, then
A =








3 0 0 0 0 0
−2 1.1 0 0 0
2.3 0 1 0 0 0
0 2.2 3 −2.11 0 0
0 0 0 2 3.3 0
0 0 0 2.4 1.1 −2.5








is such a lower triangular matrix.
Let b = [b1, b2, . . . , bn]
T denote a (column) vector with n entries. An n × n system
of linear equations Ax = b, where A is as described above, can be efficiently solved
by forward substitution, which is similar to back-substitution but starts with the first
equation. That is, the first equation can be used to solve for x1, the second equation
can be used to solve for x2, the third equation for x3, and so on.
2
Fill in the blanks in the following algorithm (use pseudocode, not MATLAB) so that
it will solve such a system of linear equations.
x1 ←
x2 ←
for i =
←
end
DELIVERABLES: Your complete pseudocode, it can be hand written or typed.
(b) (2 points) Give a floating-point operation (flop) count for this forward substitution algorithm. That is, determine the total number of floating-point additions,
subtractions, multiplications and divisions (as a function of n) that this algorithm will
execute.
DELIVERABLES: All the steps in your count, including your reasoning.
(c) (4 points) Convert your pseudocode to MATLAB code and write a function that
takes as input the nonsingular lower triangular matrix A, and column vector b and
returns the results of “forward” substitution. The input matrix should be the full
matrix including the zeros. Show how your function can be called and what the result
is for the following matrices A and b:
A =




1 0 0 0
2 3 0 0
4 5 6 0
0 7 8 9




, b =




1
5
15
24




DELIVERABLES: A copy of the m-file function, a diary of the steps taken to solve
for the given A and b and the solution x.
3. The following system of linear equations Ax = b
?
−0.2345 2.107
0.1234 −1.115 ? ? x1
x2
?
=
?
−2.345
1.001 ?
has exact solution x =
?
x1
x2
?
=
?
345.404...
37.329... ?
. This problem is ill-conditioned; for
example, if the (2,2)-entry of A is perturbed to be −1.111, then the exact solution of
this perturbed linear system is
3
y =
?
y1
y2
?
=
?
943.861...
103.934... ?
In general, it is very difficult to determine an accurate computed solution to an illconditioned linear system using floating-point arithmetic (even if a good algorithm
such as Gaussian elimination with partial pivoting is used). This is illustrated by the
following computation.
(a) (4 points)
Use base 10, precision k = 4, idealized rounding floating-point arithmetic and
Gaussian elimination with partial pivoting to solve the above linear system. Specifically, using floating-point arithmetic, show the computed approximations for the
multiplier, and the entries a22 and b2 of the first derived system (that is, when A
has been reduced to upper triangular form). (There is no need to compute a21 as
it will become 0.) Then, using floating-point arithmetic and back-substitution to
compute x2 and x1. Explain the results in context of the above.
DELIVERABLES: Your floating-point calculations and results plus the explanation.
(b) (2 points) Use the MATLAB built-in function cond to compute a condition
number for the above coefficient matrix A. We wont be discussing the details
of this condition number in this course, but there is some discussion of this on
page 294 of the 7th edition of the textbook (page 290 of the 6th edition). Roughly
speaking, if this condition number is between 1 and 10, then A is well conditioned,
and if this condition number is greater than 1000, then A is ill-conditioned.
DELIVERABLES: Show your MATLAB input and output.
4