Revision sheet 2

Question 1

When does the system of linear equations 𝐴x = 𝑏 have a unique solution? No solutions? Infinitely many solutions?

Answer 1

Unique solution: Rank(A) = Rank([A|b]) = Number of unknowns
No Solution: Rank(A) ≠ Rank([A|b])
Infinitely Many Solutions: Rank(A) = Rank([A|b]) < number of variables and
rank(A)

Question 2

Explain how Gaussian Elimination algorithm produces the LU factorisation of a matrix

Answer 2

GE algorithm converts a full matrix A into a upper-triangle matrix U through a series of multiplications by elementary transformation matrices: Mj = M(n-1) M(n-2)….M1 A = U, Mj = I -mjej^+

The lower traingle part L of LU factorisation is given by L = M1^-1 M2^-2 … M(n-1)^-1 = I sum mjej^+ from j = 1 to n-1

Question 3

Show how LU factorisation of A can be used to solve the system 𝐴x = b

Answer 3

Use Lz = Pb
and then use that to find x using
Ux = z

Question 4

Explain the difference between partial pivoting and complete pivoting

Answer 4

Partial pivoting considers only the current column for selecting the pivot.
Complete pivoting considers the entire remaining submatrix, including both rows and columns, for selecting the pivot. (PAQ = LU where p and q are permutation matrices that reorder the rows and columns)

Question 5

Show how the LU factorisation with partial pivoting can be used to solve 𝐴x = 𝑏.

Answer 5

Ly = Pb by forward substitution
and then Uz = y by backwards substitution
then reorder solution to get x = Qz

Question 6

Under what conditions an iterative method for solving a system of linear equations is faster than a direct method?

Answer 6

The cost of direct (GE) method is proportional to n^3.

The cost of one step of iterations is proportional to n^2

If the number of required iterations Kmx is smaller than n, then the iterative solver is faster (more efficient) than direct solver

Question 7

Compute the LU factorisation of the matrix A. using Gaussian elimination with scaled partial pivoting. Show your work. Your final answer should be matricesL, U, and P. Verify that PA = LU

Answer 7

P1 = swap row matrix based on the biggest |a1n/sn|
p1A
M1 = identity matrix with first collumn - an1/ (new a11)
M1P1A
P2 = swap rows with biggest matrix based on new an2/ old sn (making sure you use the right one, don’t forget you swapped rows but use original)
M2P2M1P1A = U
P = P2P1
L^~ = P1^T M1^-1 P2^T M2^2
L = PL^~

Question 8

Cholesky Factorisation

Answer 8

lkk = sqrt(akk - sum (from j = 1 to k-1) l(kj)^2

lik = (aik - sum(from j = 1 to k-1) lijlkj))/lkk for i = K+1,…,N

l11 = sqrt(a11)
l21 = a21/l11
l31 = a31/l11

l22 = sqrt(a22 - l21^2))

l32 = (a32-l31l21)/l22

l33 = sqrt(a33 - l32^2 - l31^2)

Question 9

jacobi iteration

Answer 9

Dx(k+1) = (D-A)x_k +b

(same as Richardson but instead of I is D)

Question 10

Richardson Iteration

Answer 10

x_k+1 = (I-A)x_k + b
(same as jacobi but instead of D is I)

x_(k+1) = aii^-1 [ bi - sum(j=1,j=/i to n a_ii (x_k)_j, i = 1,…,n

Question 11

Guass-Seidel Iteration

Answer 11

Q = D + L (diagonal + lower triangle)

(D+L)x_k+1 = b - Ux_k