Question

1.

Implement the recursive LU factorization algorithm in Python. Use plenty of

comments to explain your code. While you are coding, it is helpful to break up your code into sub-functions and test the sub-functions as you go along.

Answer 1

Suppose we are given a matrix A, we will compute L ans U in A=LU. We have to use recursive approach, so your recursive function will take original matrix as parameter and slicce it into sub matrices and perform some operations.

We are given a nxn matrix, LU factorization will be written as

We will divide it into submatrices of size.

It can be completed recursively

  

Base case for our recursive function will be

If Akk = 0 then we can not divide the matrix anymore.

Python code

Let us create a function lu_fact(A) this takes A matrix as parameter and return two matrices L and U.

Here L is thee lower triangular matrix with 1 on diagonal and U is the upper triangular matrix, the shape of L and U will be same as shape of A.

We will use the formula A=LU

import numpy as np

def lu_fact(A):

n=A.shape[0]

if (n==1):

L=np.array([[1]])

U=A.copy()

return (L,U)

  

  

  

  

L11 = 1

U11 = A11

L12 = np.zeros(n-1)

U12 = A12.copy()

L21 = A21.copy() / U11

U21 = np.zeros(n-1)

S22 = A22 - np.outer(L21,U12)

(L22,U22) = lu_fact(S22)

L = np.block([[L11,L12],[L21,L22]])

U = np.block([[UU11,U12],[U21,U22]])

return (L,U)