Description

The following document contains the solutions to the theory-based questions for

We have m systems of, say, n equations each. We can represent this as:
Axi = bi ∀i ∈ {1,2,⋯,m}
where A ∈ Rn×n and xi,bi ∈ Rn∀i ∈ {1,⋯,m} i.e. only a and b change for each system.
a) Using Gaussian elimination involves the following steps:
Creation and echelonisation of the augmented matrix
Forward elimination for the ith row involves n − i − 1 row subtractions. Each row subtraction takes O(n) time. Thus, forward elimination takes O(n2) time.
We need to perform these row subtractions for all the equations in the system.
Thus, forward elimination takes O(n3) time.
We need to perform the above for all the m systems. Thus, forward elimination takes O(mn3) time.
Back Substitution
For the ith row we need to perform O(i) operations. Thus, back substitution takes O(n2) time. We have to perform this for all the m systems. Thus, back substitution takes O(mn2) time.
Thus, the total time complexity of Gaussian elimination is O(mn2) + O(mn3) = O(mn3).
b) Using LU Decomposition involves the following steps:
LU Decomposition
We need to perform the LU Decomposition only one time as the matrix A doesn’t change. Thus, LU Decomposition takes O(n3) time.
Calculating L−1
We need to compute the matrix inverse only once as the matrix L doesn’t change.
Thus, calculating L−1 takes O(n3) time.
Calculating L−1x (matrix vector product)
For multiplying a matrix and a vector, we need to perform n dot products. Each dot product takes O(n) time. Thus, the matrix vector product takes O(n2) time.
Forward substitution
Forward substitution is same as the backward substitution in Gaussian elimination. Thus, forward substitution takes O(n2) time. We need to perform this every time for the m systems. Thus, forward substitution takes O(mn2) time.
Thus, the total time complexity of LU Decomposition is O(n3) + O(n3) + O(mn2) = O(mn2). Here, we want to analyze the complexity for solving m systems. Hence, one can consider that m ≫ n.
Consider the given system of linear equations:
⎡
1 2 2 1⎤⎡x1⎤ ⎡1⎤
2 1 1 2 x2 1
=
⎣
2 1 2 1 x3 1
1 2 1 2⎦⎣x4⎦ ⎣1⎦
a) We start by performing an LU Decomposition on matrix A
1 i ∈ 1,2,⋯,p
(Lp)i,i = {(Ap−1)p,p otherwise
−(A
(Lp)i,j = {0 p−1)i,j ojth=erpw ainsed i > j
⎡ 1 0 0 0⎤ −2 1 0 0
L1 =
−2 0 1 0
⎣−1 0 0 1⎦
⎡1 2 2 1 ⎤
0 −3 −3 0
⟹ A1 = L1A =
0 −3 −2 −1
⎣0 0 −1 1 ⎦
⎡1 0 0 0 ⎤ 0 1 0 0
L2 =
0 3 −3 0
⎣0 0 0 −3⎦
⎡1 2 2 1 ⎤
0 −3 −3 0
⟹ A2 = L2A1 =
⎣0 0 3 −3⎦ 0 0 −3 3
⎡1 0 0 0 ⎤ 0 1 0 0
L3 =
0 0 1 0
⎣0 0 −3 −3⎦
⎡1 2 2 1⎤ 0 −3 −3 0
⟹ A3 = L3A2 =
0 0 −3 3 ⎣0 0 0 0⎦
U = A3 = L3L2L1A = L−1A
⎡1 2 2 1⎤ 0 −3 −3 0
⟹ U =
0 0 −3 3
⎣0 0 0 0 ⎦
⎡1 0 0 0 ⎤⎡1 0 0 0 ⎤⎡1 0 0 0⎤
L−1 = L3L2L1 = 0 1 0 0 0 1 0 0−2 1 0 0
0 0 1 0 0 3 −3 0−2 0 1 0
⎣
0 0 −3 −3⎦⎣0 0 0 −3⎦⎣−1 0 0 1⎦
⎡ 1 0 0 0⎤
⟹ −1 = −2 1 0 0
L
0 3 −3 0
⎣−9 −9 9 9⎦
⟹ L = L−1 1L−2 1L−3 1
−11 i ∈ 1,2,⋯,p
(L p)i,i =(Ap−11)p,p otherwise
{
(Ap−1)i,j
(L−p 1)i,j =(Ap−1)j,j j = p and i > j
0 otherwise
⎡
1 0 0 0⎤ ⎡1 0 0 0 ⎤⎡1 0 0 0 ⎤
⟹ −1L−1L−1 =2 1 0 0 0 1 01 0000 10 10 00
L = L1 2 3 2 0 1 0 0 1 − 3
⎣1 0 0 1⎦ ⎣1 0 0 −⎦⎣0 0 −1 −⎦
⎡
1 000⎤
2 100
⟹ L = 2 1− 130 ⎣1 0 ⎦
NOTE: The LU Decomposition performed is based off the generalised expression used while computing Lp. This is not the only method that can be used to compute L and U. Another standardised method gives the following results:
⎡1 0 00⎤
2 1 00
L =
2 1 10
⎣1 0 −11⎦
⎡1 2 21 ⎤
0 −3 −3 0 U =
0 0 1−1
⎣0 0 00 ⎦
b) We now compute the solution to the system of linear equations.
We have A = LU and Ax = b, so:
LUx = b
⟹ Ux = L−1b
⎡
1 2 2 1⎤⎡x1⎤ ⎡ 10 0 0⎤⎡1⎤
0 −3 −3 0 x2−21 0 0 1
⟹=
0 0 −3 3 x303 −3 0 1
⎣
0 0 0 0⎦⎣x4⎦ ⎣−9−9 9 9⎦⎣1⎦
⎡1 2 2 1⎤⎡x1⎤ ⎡ 1 ⎤
0 −3 −3 0 x2−1
⟹= 0 0 −3 3 x30
⎣
0 0 0 0⎦⎣x4⎦ ⎣ 0 ⎦
On performing Back Substitution, we see that the last equation results in infinite solutions.
We find the solution in parametric form i.e., let x4 = α
−3×3 + 3α = 0
⟹ x3 =α
−3×2 − 3×3 =−1
⟹ x2 = − α
x1 + 2×2+2×3 + x4 = 1
⟹ x1 = − α ⟹ x = [ − α − α α α]T
c) We now compute the solution to the system of linear equations by replacing b with z
We have A = LU and Ax = z, so:
LUx = z
⟹ Ux = L−1z
⎡
1 2 2 1⎤⎡x1⎤ ⎡ 1 0 0 0⎤⎡1⎤
0 −3 −3 0 x2 −2 1 0 0 2
⟹=
⎣
0 0 −3 3 x3 0 3 −3 0 3
0 0 0 0⎦⎣x4⎦ ⎣−9 −9 9 9⎦⎣4⎦
⎡1 2 2 1⎤⎡x1⎤ ⎡ 1 ⎤
0 −3 −3 0 x2 0
⟹=
0 0 −3 3 x3 −3
⎣
0 0 0 0⎦⎣x4⎦ ⎣36⎦
Now perform Back Substitution. As the last equation has no solution, we can conclude that no solution exists.
The given matrix is positive definite. THus, we can perform a Cholesky Decomposition. We will solve this via LU decomposition first:
⎡ 6 15 55 ⎤
M = 15 55 225
⎣55 225 979⎦
Step1: R2 = R2 − (5/2)R1
1 ⎡ 6 15 55 ⎤
M = 0 35/2 175/2
⎣55 225 979 ⎦
Step2: R3 = R3 − (55/6)R1
⎡6 15 55 ⎤
M2 = 0 35/2 175/2
⎣0 525/6 2849/6⎦
Step3: R3 = R3 − 5R2
3 ⎡6 15 55 ⎤
M = 0 35/2 175/2 = U ⎣0 0 112/3⎦
We can use the subtraction coefficients to find L.
We consider the matrix
⎡1 0 0⎤
I = 0 1 0
⎣0 0 1⎦
and fill the entries I21,I31,I32 with (5/2),(55/6), and 5 respectively. This gives us L.
⎡ 1 00⎤
L = 5/2 10
⎣55/6 51⎦
It might not be immediately apparent that L = UT. This is simply beacuse of the method used to calculate the LU decomposition. If the identity matrix is used to fill the entries of L, then barring some special cases, we won’t get the required result. Instead, let’s try to algebraically solve for the values:
⎡a11 0 0 ⎤
L =a21 a22 0
a31 a32 a33⎦
⎡a11 a21 a31⎤
⟹ U = 0 a22 a32
⎣ 0 0 a33⎦
⎡ a211 a11a21a11a31 ⎤
⟹ LU = a21a11 a221 + a222 a21a31 + a22a32
⎣a31a11 a31a21 + a32a22 a231 + a322 + a233 ⎦
On comparing and solving, we get: ⎡ ⎤⎡ ⎤ M = ⎣ ⎦⎣ ⎦
Could we have reached this conclusion from the LU decomposition itself? Yes, using the standard method for LU decomposition, if we perform the following operations, we get the required result.
L
L
L
L
12 21 √U11
L
13 31 √U11
L
Food for thought…how to extend this idea for n × n matrices?