FOR FREE CONTENT

In numerical analysis, this method is an LU decomposition in which a matrix is decomposed into the lower triangular matrix, an upper triangular matrix, and sometimes a permutation matrix. This method was developed by Prescott Durand Crout. After decomposition, the method can be used to solve linear equations.

DERIVATION

Let the linear equations be:

This equation can be written as AX = B where A is the coefficient matrix, X is the solution matrix and B is the constant matrix.

Now the matrix A can be expressed as the product of upper triangular and lower triangular matrix as

A = LU

Where

Now as A = LU and AX = B, from these equations we get:

LUX = B

If we consider UX = Y where Y is an unknown matrix then we can write 

LY = B

Now the product of L and U will be calculated.

After that LY = B will be solved by the forward substitution method and then the equation UX = Y will be solved by the backward substitution method.

INPUT: 

The linear equations.

OUTPUT: 

The value of the unknowns

PROCESS:

Step 1: [taking the inputs from the user]
	Read n [order of the matrix]
	[taking the co-efficient 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]
	[taking the constants]
	for i = 0 to n - 1 repeat
		Read arr[i][n]
	[End of ‘for’ loop]
	for i = 0 to n - 1 repeat
		Set b[i][0] ← arr[i][0]
	[End of ‘for’ loop]
	for j =1 to n repeat
		Set u[0][j] ← (arr[0][j]/b[0][0])
	[End of ‘for’ loop]
	for p = 1 to n - 1 repeat
		for i = p to n - 1 repeat
			for k = 0 to p - 1 repeat
			Set arr[i][p] ← arr[i][p] - b[i][k] × u[k][p]
			[End of ‘for’ loop]
			Set b[i][p] ← arr[i][p]
		[End of ‘for’ loop]
		for j = p + 1 to n repeat
			for k = 0 to p - 1 repeat
			Set arr[p][j] ← arr[p][j] - b[p][k] × u[k][j]
			[End of ‘for’ loop]
			Set u[p][j] ← arr[p][j]/b[p][p]
		[End of ‘for’ loop]
	[End of ‘for’ loop]

	for k = 0 to n - 1 repeat
		Set i ← (n - k - 1)
		Set x[i] ← u[i][n]
		for j = i + 1 to n - 1 repeat
			Set x[i] ← x[i] - u[i][j] × x[j]
		[End of ‘for’ loop]
	[End of ‘for’ loop]
	for i = 0 to n - 1 repeat
		Print i, x[i]
	[End of ‘for’ loop]