Matrix Forward and Back Substitution
A square matrix is transformed into a Lower triangular matrix L or an Upper triangular matrix U by applying elementary row operation (Gaussian elimination) for solving system linear of equations.
A solution vector X of system of linear equations is obtained by applying substitution method.
- The forward substitution method is applied to matrix L
- The back substitution method is applied to matrix U
Algorithm steps for forward substitution to matrix L
Input : a square matrix, A
a non-homogeneous vector b
Output : Solution vector, X
read matrix A
read vector b
L = transform_to_L(A,b)
X = substitute-forward(L);
Example of forward substitution to matrix L
substitute unknown variables top to bottom approach
0.4286x = 1.7143
3.6667x + 2.3334y = 10.0
2.0x+ + 4.0y + 6.0z = 18.0
find x, from equation 1
0.4286x = 1.7143
x = 1.7143/0.4286
x = 3.999
substitute x = 20.998 in equation 2
3.6667(3.999) + 2.3334y = 10.0
2.3334y = 10.0 - 14.665
y = -1.9996
substitute x = 3.999,y=-1.9996 in equation 3
2.0(3.999)+ + 4.0(-1.9996) + 6.0z = 18
7.9992 - 7.9984 + 6.0z = 18
6.0z = 18 - 0.0008
z = 17.9992 / 6
z = 2.999
solution vector x=3.999,y=-1.9996,z=2.999
Algorithm steps for back substitution to matrix U
Input - a square matrix A
a non-homogeneous vector b
Output - solution vector X
read matrix A
read vector b
U = transform_to_U(A,b)
X = substitute-back(U);
Example of back substitution to matrix U
substitute unknown variables from bottom to top approach
1.0x + 2.0y + 3.0z = 9
1.0y + 2.0z = 4
+ 1.0z = 3
find z, from equation 3
1.0z = 3
z = 3
find y, substitute z = 3 in equation 2
1.0y + 2.0(3) =4
1.0y = 4-6
y = -2
find x, substitute z=3, y=-2 in equation 1
1.0x + 2.0(-2) + 3.0(3) = 9
1.0x - 4 + 9 = 9
x = 4
solution vector x=4,y=-2,z=4
Java programming code - Forward and Backward Substitution
import java.util.Arrays;
public class Substitution {
public static double[] forward(Matrix mat,double b[]) {
int nrow =mat.getNrow();
double sol[] =new double[nrow];
for (int r=0;r<nrow; r++)
{
double val =0;
for (int c=0;c<r; c++) {
val =val + sol[c] *mat.getElement(r, c);
}
val = b[r] - val;
sol[r] = val/mat.getElement(r, r);
}
return sol;
}
public static double[] backward(Matrix Umat,double b[]) {
int nrow =Umat.getNrow();
int ncol = Umat.getNcol();
double sol[] =new double[nrow];
for(int r=nrow-1; r>=0; r--)
{
double val =0;
for(int c=ncol-1;c>r;c--) {
val =val + sol[c] *Umat.getElement(r, c);
}
val = b[r] - val;
sol[r] = val/Umat.getElement(r, r);
}
return sol;
}
public static void main(String[] args) {
double u[][]={{1,2,3},{0,1,2},{0,0,1}};
double b[] = {9,4,3};
Matrix U = new Matrix(u);
System.out.println("Upper Triangular matrix U");
System.out.println(U.toString());
double sol[]=Substitution.backward(U, b);
System.out.println("Solution of UX=b");
System.out.println(Arrays.toString(sol));
double l[][]={{0.4286, 0.0, 0.0},{3.6667, 2.3334, 0.0},
{2.0,4.0,6.0}};
double b2[] = {1.7143,10.0,18.0};
Matrix L = new Matrix(l);
System.out.println("Lower Triangular matrix L");
System.out.println(L.toString());
double sol2[]=Substitution.forward(L, b2);
System.out.println("Solution of LX=b");
System.out.println(Arrays.toString(sol2));
}
}
Java programming output of Forward and Backward Substitution
Upper Triangular matrix U 1.0 2.0 3.0 0.0 1.0 2.0 0.0 0.0 1.0 b vector [9 4 3] Solution of UX=b [4.0, -2.0, 3.0] Lower Triangular matrix L 0.4286 0.0 0.0 3.6667 2.3334 0.0 2.0 4.0 6.0 b vector [1.7143 10.0 18.0] Solution of LX=b [3.9997666822211855, -1.9996333649183253, 2.9998333492051548]
Comments
Post a Comment