FOR FREE MATERIALS

Lu factorization is also known as the triangular decomposition method. It is often called Crout’s method also. This method is based on the fact that every square matrix can be expressed as the product of a lower and an upper triangular matrix provided the principal minors of the given square matrix $\mathbf{A}\mathbf{ }\mathbf{=}\mathbf{ }\mathbf{\left(}{\mathbf{a}}_{\mathbf{ij}}\mathbf{\right)}\mathbf{ }\mathbf{m}\mathbf{ }\mathbf{x}\mathbf{ }\mathbf{n}$ are non-singular i.e.

Then we can also assure that the factorization is unique.

DERIVATION

Let us assume that the matrix A is factorized as the product of a lower triangular matrix L and upper triangular matrix U so that A = LU

Where, 

Here the system of equation AX = b can be written as LUX = b

Putting UX = Y

Now LU = A will give us

From the above equation, we get,

Generalizing the above equation we get,

For j > 1,

And for i > 1 but i < j,

All ${\mathrm{l}}_{\mathrm{ij}}$ , ${\mathrm{u}}_{\mathrm{ij}}$ can be determined by applying the above relations, and hence L and U will be known.

Now ${\mathrm{y}}_1, {\mathrm{y}}_2, .... , {\mathrm{y}}_{\mathrm{n}}$can be determined by forwarding substitution from LY = b and all unknown ${\mathrm{x}}_1, {\mathrm{x}}_2, .... , {\mathrm{x}}_{\mathrm{n}}$ will be found by back substitution from the equation UX = Y

Alternatively, we can find ${\mathrm{L}}^{-1}$ and ${\mathrm{U}}^{-1}$ and we can write $\mathrm{Y} = {\mathrm{L}}^{-1}\mathrm{b}$, $\mathrm{X} = {\mathrm{U}}^{-1}\mathrm{Y}$. The inverse of A can be determined from the following relation:

We now discuss the particular case of 3 × 3 matrices of the form.

We get, 

INPUT: 

A matrix 

OUTPUT: 

The value after factorization.

PROCESS:

Step1: [taking the inputs]
	Read n [the order of the matrix]
	for i = 0 to n - 1 repeat
		for j = 0 to n - 1 repeat
			Read arr[i][j]
		[End of ‘for’ loop]
	[End of ‘for’ loop]
	[reading the constant terms]
	for i = 0 to n - 1 repeat
		Read constant[i]
	[End of ‘for’ loop]

Step 2: [LU Factorization]
	for j = 0 to n - 1 repeat
	for i = 0 to n - 1 repeat
		If i ≤ j then
		Set u[i][j] ← arr[i][j]
		for k = 0 to i - 2 repeat
			Set u[i][j] ← u[i][j] - l[i][k] × u[k][j]
			[End of ‘for’ loop]
		If i = j then
			Set l[i][j] ← 1.0
		else
			Set l[i][j] ← 0.0
			[End of ‘if’]
		[End of ‘if’]
		else
		Set l[i][j] ← arr[i][j]
		for k = 0 to j - 1 repeat
			Set l[i][j] = l[i][j] - l[i][k] × u[k][j]
			[End of ‘for’ loop]
		Set l[i][j] = l[i][j] / u[j][j]
		Set u[i][j] ← 0.0
		[End of ‘if’]
	[End of ‘for’ loop]
[End of ‘for’ loop]
Print "the values of matrix L"
	for i = 0 to n - 1 repeat
		for j = 0 to n - 1 repeat
			Print l[i][j]
		[End of ‘for’ loop]
    			Move to the next line
   	[End of ‘for’ loop]
		Print "the values of matrix U:"
	for i = 0 to n - 1 repeat
		for j = 0 to n - 1 repeat
			Print u[i][j]
		[End of ‘for’ loop]
 			Move to the next line
	[End of ‘for’ loop]
	for i = 0 to n - 1 repeat
		Set y[i] ← constant[i]
		for j = 0 to i - 1 repeat
			Set y[i] ← y[i] - l[i][j] × y[j]
		[End of ‘for’ loop]
	[end of ‘for’ loop]
		Print "the value of matrix Y"
	for i = 0 to n - 1 repeat
		Print y[i]
	[End of ‘for’ loop]
	for i = n - 1 to 0 repeat
		Set x[i] ← y[i]
		for j = i + 1 to n - 1 repeat
			Set x[i] ← x[i] - u[i][j] × x[j]
		[End of ‘for’ loop]
		Set x[i] ← x[i]/u[i][i]
	[End of ‘for’ loop]
		Print "the value of matrix X: "
	for i = 0 to n - 1 repeat
		Print x[i]
	[End of ‘for’ loop]
[End of ‘LU Factorization’ method]