Solution of Week 7 Lab (Prepared by Yuan Yin)
December 22, 2019
1 Exercise 1: LU Factorization:
(a).
Read the Tute sheet.
(b).
Read the Tute sheet.
(c).
The matrix, P, is the permutation matrix which performs pivoting. For example, if A is a 3 × 3 matrix and we want to switch the first and the third rows of A to get A’, then
and P * A = A’.
Why we nee to use y = L \ (P ∗ b)?
001 P=0 1 0,
100
—— This is because [L, U, P ] = lu(A) returns a unit lower triangular matrix L, an upper triangular matrix U, and a permutation matrix P such that PA = LU.
⇒ P ∗ A ∗ x = P ∗ b;
⇒ L ∗ U ∗ x = P ∗ b;
⇒ L ∗ y = P ∗ b by setting y = U ∗ x;
⇒ y = L \ P ∗ b;
⇒ x = U \ y.
(d).
Note that p here is a permutation vector, and it permutes the rows of A as follows:
1st row of A p1th row of A p1 2nd row of A p2th row of A p2
A= . ⇒A(p,:)= . , where P = . . nth row of A pnth row of A pn
1
[3]:
2 Exercise 2: Operation Counts:
%%file TestEfficiency.m
function TestEfficiency %% PART A
n = 1000;
fprintf(‘When n is %d:\n’, n);
% We construct A, x, b in the way such that Ax = b:
A = rand(n, n);
x = rand(n, 1);
b = A * x;
fprintf(‘\nUsing LU Factorisation: ‘);
tic
x_LU = A\b;
toc
fprintf(‘\nUsing Inverse Matrix: ‘);
tic
x_Inv = inv(A) * b;
toc
%% PART B
fprintf(‘\n\n————————————————————\n\n’);
nn = 1000;
fprintf(‘When n is %d:\n’, nn);
% We construct AA, xx, bb in the way such that AA * xx = bb, also, AA needs % to be positive definite since we want to use the command ‘chol’:
I = rand(nn);
AA = I’ * I;
xx = rand(nn, 1);
bb = AA * xx;
fprintf(‘\nUsing Backslash: ‘);
tic
xx_LU = AA\bb;
toc
fprintf(‘\nUsing “LU” command: ‘)
tic
2
[L,U,P] = lu(AA);
xx_lu = U\(L\P * bb);
toc
fprintf(‘\nUsing Cholesky Factorization: ‘)
tic
R = chol(AA);
xx_chol = R\(R’\bb);
toc
end
Created file ‘/Users/RebeccaYinYuan/MAST30028 Tutorial Answers Yuan Yin/WEEK
7/TestEfficiency.m’.
[4]: TestEfficiency When n is 1000:
Using LU Factorisation: Elapsed time is 0.134665 seconds.
Using Inverse Matrix: Elapsed time is 0.090224 seconds.
————————————————————
When n is 1000:
Using Backslash: Elapsed time is 0.032485 seconds.
Using “LU” command: Elapsed time is 0.068457 seconds.
Using Cholesky Factorization: Elapsed time is 0.020645 seconds.
3 Exercise 3: Backslash:
(a).
One way to generate symmetric, positive definite matrix, A, is multiplying one random matrix with its transpose. The MATLAB codes can be written as follows:
n = 1000;
I = rand(n);
AA = I′ ∗ I;
In ‘CholScalar.m’, A being symmetric means that it can be decomposed into A = U′ΛU, where U is an orthogonal matrix and Λ is a diagonal matrix with eigenvalues of A as its diagonal elements.
3
If A is not positive definite, its eigenvalues may be ZERO, and this will cause SINGULAR Cholesky factorisation.
(b).
Check out the MATLAB file “bslashtx.m”.
4 Exercise 4: Vector and Matrix Norms:
(a).
known: b = (3, −5, 2)
⇒ ||b||1 = |3|+|−5|+|2| = 10;
√√
⇒ ||b||2 = 32 +(−5)2 +22 = 38 = 6.1644;
⇒ ||b||∞ = | − 5| = 5; (b).
known:
33 −17 22 A = 11 −12 −1
0 −9 24 ⇒ ||A||1 = Max.Col.Sum = |22|+|−1|+|24| = 47
⇒ ||A||M = Max.Entry = 33 √
⇒ ||A||F = 332 +(−17)2 +222 +112 +(−12)2 +(−1)2 +02 +(−9)2 +242 = 52.7731 ⇒ ||A||∞ = Max.Row.Sum = |33|+|−17|+|22| = 72
NOTE: (Run ‘CheckNorms.m’ to check your answers!)
[6]:
%%file CheckNorms.m
function CheckNorms
%% PART A: Check Vector norms: clc
b = [3, -5, 2];
one_norm_vec = norm(b, 1)
two_norm_vec = norm(b)
inf_norm_vec = norm(b, Inf)
%% PART B: Check Matrix norms:
fprintf(‘\n\n———————————-\n\n’);
A = [33, -17, 22; 11, -12, -1; 0, -9, 24];
4
one_norm_matrix = norm(A, 1)
max_norm_matrix = max(abs(A(:)))
frob_norm_matrix = norm(A, ‘fro’)
inf_norm_matrix = norm(A, Inf)
two_norm_matrix = norm(A)
end
Created file ‘/Users/RebeccaYinYuan/MAST30028 Tutorial Answers Yuan Yin/WEEK
7/CheckNorms.m’.
[7]: CheckNorms one_norm_vec =
10
two_norm_vec =
6.1644
inf_norm_vec =
5
———————————-
one_norm_matrix =
47
max_norm_matrix =
33
frob_norm_matrix =
5
52.7731
inf_norm_matrix =
72
two_norm_matrix =
48.0399
6