Linear equations 85
004
x3
1
which gives
x3
1/4
So the inverse is
−1/4 1/4 1/4
or, if you prefer nicer numbers
(2.43) While you do Gauss elimination, you can get the entries to L. The augmented matrix
2 4 6 8
For the first step of forward elimination, m21 =2 and m31 =1, which gives
0233
For the second step of elimination, m32 =2 and we get the upper-triangular matrix
0011
Back-substitution gives
x1=5−3x3−2x2
2=1
From Gauss elimination, we know that
223
001
100
121
86 Linear equations
The first equation to solve is Ly =b
121
y3
8
which we compute by forward substitution to get
The back substitution for Ux =yis identical to Gauss elimination.
(2.44) (a) We need to compute 3 determinants:
The unknowns are
and
(b) There is no pivot so we just need to eliminate
which gives
“2 3 3
Using back substitution gives
and
2=0
(c) For LU decomposition, we use the result from (b) to know that
Linear equations 87
and
The forward substitution of
gives
and
2=1/2
The rest of the problem is identical to part (b), using back substitution to solve
0 1/2#” x
y#=“3
1/2#
(2.45) (a) For naive Gauss elimination, the augmented matrix is
1 3 2 6
One step of elimination gives
0 1 −1 0
The second step gives
0 0 −3−3
Back substitution gives
and
−3=1
and
88 Linear equations
(b) For Gauss elimination with pivoting, we start with
1 3 2 6
The biggest entry is the second row, so we swap
132 6
and then eliminate the first column
0 7/4 1/23/2
In the second column, we see that we have to pivot again because the bottom
entry is bigger than the second row. (Remember that you don’t have to pivot,
only if the diagonal is the biggest entry.)
0 3/4 3/23/2
Eliminating the second column gives
0 0 9/79/7
The back-substitution gives the same result as above.
(c) For LU decomposition, we just need to know the values we used for the naive
Gauss elimination. For the first elimination we used m21 =4/1 and m31 =1/1.
For the second elimination we used m32 =1/−3. This means that the lower
triangular matrix is
1 0 0
We already know the upper triangular matrix
If you want to be sure that this is correct, just check that
1−1/3 1
0 0 −3
132
Linear equations 89
For the forward substitution we have
3=−3
(2.46) ||A||1=max1≤i≤nPn
j=1|ai j|=max(8,28,20) =28
(2.47) To find the condition number, we need to compute
(2.48) For the Euclidian norm, we get
||A|| =p22+42+(−1)2+x2=√x2+21 ≡z1/2
90 Linear equations
which we could also write as
(2.49) ||x||1=Pn
i=1|xi|=10 +3+4+1+5=23
||x||2=qPix2
i=√100 +9+16 +1+25 =√151 =12.3
||x||∞=max |xi|=10
0−4−2−401
Linear equations 91
Put 1 on the diagonal:
1 1 1 1 0 0
0−4−2−401
Eliminate the 2nd column:
1 1 1 100
0 0 −24−4 1
Put 1 on the diagonal:
Eliminate up the third column:
Eliminate up the second column:
The inverse is then
and its 1-norm is 5 (from the first column). So
(2.54) To compute the condition number, we first need the inverse of the matrix. We can
compute this using simultaneous Gauss elimination on the identity matrix:
112100
0 1 2 0 0 1
92 Linear equations
(2.55) We first need to compute the inverse of the matrix:
“1 2 1 0
(2.56) The 1-norm is the maximum of (3,5), which is 5. The ∞-norm is the maximum of
(5,3), which is also 5. The Euclidian norm is √4+9+1+4=√18 =4.24. For the
Linear equations 93
(2.57) The first step of Jacobi’s method is
x(1)
1=4−x(0)
2
2=4−0
2=2
(2.58) The first iteration of Jacobi’s method is simple
(2.59) The first iteration of Gauss-Seidel gives
x(1)
1=−3/2
Linear equations 95
(2.64) To be diagonally dominant, we require that |aii|>Pj,j,i|ai j|on each row i. For
each row, we have
9>2+1+3=6 (i=4)
(2.65) The components for linear regression are sx=9.8, sxx =20.9, sy=25.3 and sxy =
55.04 for n=5 elements. The coefficients are
(2.66) (a) First we need to calculate how many numbers we can store in the memory
1MB ∗1024 KB
1MB ∗1024 bytes
1KB ∗8bits
1byte ∗1number
64 bits =131,072 numbers
96 Linear equations
(2.67) 104(p=2, ratio of time is n3/np2=(n/p)2)
(2.68) For a banded matrix, Jacobi’s method requires nvalues of xi,pevaluations per sum,
which gives tJacobi =2×10−5sec. Jacobi’s method is preferred.
(2.69) (a) n3scaling gives t=103=1000 sec.
(b) np2scaling gives
t=1k
n=0.1 sec
(2.70) Gauss elimination is n3and Jacobi’s method is n2k. So we need k≪n. OK if they
(2.72) The trace is τ=2 and the determinant is ∆ = 3. So the eigenvalues are
λ=2±√4−4(3)
(2.73) (a) 1
(b) p=4, q=0, so the bandwidth is p+q+1=5
(c) Column j=3 has the biggest sum: 53 +π=56.14157
(2.74) (a) 15.
(b) No because it is not diagonally dominant.
(2.77) (a) This program solves the linear algebraic system
3x1+2x2=2
x1−x2=−1
98 Linear equations
(2.78) (a)
det
213
421
111
If they say det Athat’s OK too.
(b) Gauss elimination with pivoting
(c) The size of the matrix
111
Doing the forward elimination gives
0 0.5 0.75
We really need to pivot on the next step (s=1 now) because the diagonal is
zero!
Linear equations 99
(2.79) (a) The problem is
Computer Problems
(2.80) (a) The files for this problem are contained in the folder s15c4p2 matlab.
The Matlab script is:
1function s15h4p2
2clc
3
4A = zeros(12);
100 Linear equations
19 A(2,11) = 1;
20 b(2) = 0;
21
22 %balance on #3
23 A(3,5) = -1;
24 A(3,6) = 1;
25 A(3,7) = 1;
30 A(4,4) = 1;
31 A(4,7) = 1;
32 A(4,11) = 1;
43 b(6) = 0;
44
45 %spec on 4, 7, 12
46 A(7,4) = 1;
47 A(7,7) = 1;
58 A(9,1) = -0.55;
59 A(9,9) = 1;
60 A(9,12) = 1;
61 b(9) = 0;
62
73
74 %spec on 6, 7, 8
Linear equations 101
75 A(12,6) = 3.2;
76 A(12,7) = -1;
87
88 fprintf(‘\n\n’)
89 fprintf(‘The vector b = \n’)
90 for i = 1:12
91 fprintf(‘%4.2f\n’,b(i))
92 end
(b) The files for this problem are contained in the folder s15c4p3 matlab.
The Matlab script is:
6xGaussNaive = linear ngaussel(A,b) %solve with naive Gauss …
elimination
7
18 %balance on #1
19 A(1,1) = -1;
20 A(1,2) = 1;
21 A(1,3) = 1;
22 A(1,4) = 1;
102 Linear equations
33 %balance on #3
34 A(3,5) = -1;
35 A(3,6) = 1;
36 A(3,7) = 1;
47 %spec on m1
48 A(5,1) = 1;
49 b(5) = 100;
50
51 %spec on 8 and 5
62 %spec on 1, 2, 3
63 A(8,1) = -0.7;
64 A(8,2) = 1;
65 A(8,3) = 1;
66 b(8) = 0;
77 b(10) = 0;
78
79 %spec on 2, 11, 9
80 A(11,2) = -0.85;
81 A(11,9) = 1;
91 fprintf(‘The matrix A = \n’)
92 for i = 1:12
93 for j = 1:12
94 fprintf(‘%4.2f\t’,A(i,j))
95 end
106
107
108 function x = linear gauss pivot(A,b)
109 % A = n x n matrix
110 % b = column vector, n x 1
121 swap row = i;
122 end
123 end
124 %exchange rows if true
125 if swap row ~= k
136 for i = 1:12
137 for j = 1:12
138 fprintf(‘%4.2f\t’,A(i,j))
139 end
140 fprintf(‘\n’)
150 end
151 b(i)=b(i)-m*b(k);
152 end
153 end
154 % Perform the back substitution
165 % A = n x n matrix
166 % b = column vector, n x 1
167 n=length(b);
168 x=zeros(n,1);
169 % Perform the forward elimination
180 x(n)=b(n)/A(n,n);
181 for i=n-1:-1:1
182 S=b(i);
183 for j=i+1:n
184 S=S-A(i,j)*x(j);
(2.81) The files for this problem are contained in the folder s12c4p2 matlab.
The Matlab script is: