Java Program to Implement Gauss Jordan Elimination

This is java program to find the solution to the linear equations of any number of variables using the method of Gauss-Jordan algorithm.

Here is the source code of the Java Program to Implement Gauss Jordan Elimination. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a sample program to find the solution to the linear equations using the method of Gauss-Jordan algorithm
  2. import java.util.Scanner;
  3.  
  4. public class Gauss_Jordan_Elimination 
  5. {
  6.     private static final double EPSILON = 1e-8;
  7.  
  8.     private final int N;      // N-by-N system
  9.     private double[][] a;     // N-by-N+1 augmented matrix
  10.  
  11.     // Gauss-Jordan elimination with partial pivoting
  12.     public Gauss_Jordan_Elimination(double[][] A, double[] b) 
  13.     {
  14.         N = b.length;
  15.  
  16.         // build augmented matrix
  17.         a = new double[N][N+N+1];
  18.         for (int i = 0; i < N; i++)
  19.             for (int j = 0; j < N; j++)
  20.                 a[i][j] = A[i][j];
  21.  
  22.         // only need if you want to find certificate of infeasibility (or compute inverse)
  23.         for (int i = 0; i < N; i++)
  24.             a[i][N+i] = 1.0;
  25.  
  26.         for (int i = 0; i < N; i++) 
  27.             a[i][N+N] = b[i];
  28.  
  29.         solve();
  30.  
  31.         assert check(A, b);
  32.     }
  33.  
  34.     private void solve() 
  35.     {
  36.         // Gauss-Jordan elimination
  37.         for (int p = 0; p < N; p++) 
  38.         {
  39.             int max = p;
  40.             for (int i = p+1; i < N; i++) 
  41.             {
  42.                 if (Math.abs(a[i][p]) > Math.abs(a[max][p])) 
  43.                 {
  44.                     max = i;
  45.                 }
  46.             }
  47.  
  48.             // exchange row p with row max
  49.             swap(p, max);
  50.  
  51.             // singular or nearly singular
  52.             if (Math.abs(a[p][p]) <= EPSILON) 
  53.             {
  54.                 continue;
  55.                 // throw new RuntimeException("Matrix is singular or nearly singular");
  56.             }
  57.  
  58.             // pivot
  59.             pivot(p, p);
  60.         }
  61.         // show();
  62.     }
  63.  
  64.     // swap row1 and row2
  65.     private void swap(int row1, int row2) 
  66.     {
  67.         double[] temp = a[row1];
  68.         a[row1] = a[row2];
  69.         a[row2] = temp;
  70.     }
  71.  
  72.  
  73.     // pivot on entry (p, q) using Gauss-Jordan elimination
  74.     private void pivot(int p, int q) 
  75.     {   // everything but row p and column q
  76.         for (int i = 0; i < N; i++) {
  77.             double alpha = a[i][q] / a[p][q];
  78.             for (int j = 0; j <= N+N; j++) 
  79.             {
  80.                 if (i != p && j != q) a[i][j] -= alpha * a[p][j];
  81.             }
  82.         }
  83.  
  84.         // zero out column q
  85.         for (int i = 0; i < N; i++)
  86.             if (i != p) a[i][q] = 0.0;
  87.  
  88.         // scale row p (ok to go from q+1 to N, but do this for consistency with simplex pivot)
  89.         for (int j = 0; j <= N+N; j++)
  90.             if (j != q) a[p][j] /= a[p][q];
  91.         a[p][q] = 1.0;
  92.     }
  93.  
  94.     // extract solution to Ax = b
  95.     public double[] primal() 
  96.     {
  97.         double[] x = new double[N];
  98.         for (int i = 0; i < N; i++) 
  99.         {
  100.             if (Math.abs(a[i][i]) > EPSILON)
  101.                 x[i] = a[i][N+N] / a[i][i];
  102.             else if (Math.abs(a[i][N+N]) > EPSILON)
  103.                 return null;
  104.         }
  105.         return x;
  106.     }
  107.  
  108.     // extract solution to yA = 0, yb != 0
  109.     public double[] dual() 
  110.     {
  111.         double[] y = new double[N];
  112.         for (int i = 0; i < N; i++) 
  113.         {
  114.             if ( (Math.abs(a[i][i]) <= EPSILON) && (Math.abs(a[i][N+N]) > EPSILON) ) 
  115.             {
  116.                 for (int j = 0; j < N; j++)
  117.                     y[j] = a[i][N+j];
  118.                 return y;
  119.             }
  120.         }
  121.         return null;
  122.     }
  123.  
  124.     // does the system have a solution?
  125.     public boolean isFeasible() 
  126.     {
  127.         return primal() != null;
  128.     }
  129.  
  130.     // print the tableaux
  131.     private void show() 
  132.     {
  133.         for (int i = 0; i < N; i++) 
  134.         {
  135.             for (int j = 0; j < N; j++) 
  136.             {
  137.                 System.out.print(" "+a[i][j]);
  138.             }
  139.             System.out.print("| ");
  140.             for (int j = N; j < N+N; j++) 
  141.             {
  142.             	System.out.print(" "+a[i][j]);
  143.             }
  144.             System.out.print("| \n"+a[i][N+N]);
  145.         }
  146.         System.out.println();
  147.     }
  148.  
  149.  
  150.     // check that Ax = b or yA = 0, yb != 0
  151.     private boolean check(double[][] A, double[] b) 
  152.     {
  153.  
  154.         // check that Ax = b
  155.         if (isFeasible()) 
  156.         {
  157.             double[] x = primal();
  158.             for (int i = 0; i < N; i++) 
  159.             {
  160.                 double sum = 0.0;
  161.                 for (int j = 0; j < N; j++) 
  162.                 {
  163.                      sum += A[i][j] * x[j];
  164.                 }
  165.                 if (Math.abs(sum - b[i]) > EPSILON) 
  166.                 {
  167.                 	System.out.println("not feasible");
  168.                 	System.out.println(i+" = "+b[i]+", sum = "+sum+"\n");
  169.                    return false;
  170.                 }
  171.             }
  172.             return true;
  173.         }
  174.  
  175.         // or that yA = 0, yb != 0
  176.         else 
  177.         {
  178.             double[] y = dual();
  179.             for (int j = 0; j < N; j++) 
  180.             {
  181.                 double sum = 0.0;
  182.                 for (int i = 0; i < N; i++) 
  183.                 {
  184.                      sum += A[i][j] * y[i];
  185.                 }
  186.                 if (Math.abs(sum) > EPSILON) 
  187.                 {
  188.                     System.out.println("invalid certificate of infeasibility");
  189.                     System.out.println("sum = "+sum+"\n");
  190.                     return false;
  191.                 }
  192.             }
  193.             double sum = 0.0;
  194.             for (int i = 0; i < N; i++) 
  195.             {
  196.                 sum += y[i] * b[i];
  197.             }
  198.             if (Math.abs(sum) < EPSILON) 
  199.             {
  200.             	System.out.println("invalid certificate of infeasibility");
  201.             	System.out.println("yb  = "+sum+"\n");
  202.  
  203.                 return false;
  204.             }
  205.             return true;
  206.         }
  207.     }
  208.  
  209.  
  210.     public static void test(double[][] A, double[] b) 
  211.     {
  212.         Gauss_Jordan_Elimination gaussian = new Gauss_Jordan_Elimination(A, b);
  213.         if (gaussian.isFeasible()) 
  214.         {
  215.         	System.out.println("Solution to Ax = b");
  216.             double[] x = gaussian.primal();
  217.             for (int i = 0; i < x.length; i++) 
  218.             {
  219.             	System.out.println(" "+x[i]+"\n");
  220.             }
  221.         }
  222.         else 
  223.         {
  224.         	System.out.println("Certificate of infeasibility");
  225.             double[] y = gaussian.dual();
  226.             for (int j = 0; j < y.length; j++) 
  227.             {
  228.             	System.out.println(" "+y[j]+"\n");
  229.             }
  230.         }
  231.         System.out.println();
  232.     }
  233.  
  234.     public static void main(String[] args) 
  235.     {
  236.  
  237.     	Scanner input = new Scanner(System.in);
  238.     	System.out.println("Enter the number of variables in the equations: ");
  239.     	int n = input.nextInt();
  240.         System.out.println("Enter the coefficients of each variable for each equations");
  241.         System.out.println("ax + by + cz + ... = d");
  242.         double [][]mat = new double[n][n];
  243.         double []constants = new double[n];
  244.         //input
  245.         for(int i=0; i<n; i++)
  246.         {
  247.             for(int j=0; j<n; j++)
  248.             {
  249.                 mat[i][j] = input.nextDouble();
  250.             }
  251.             constants[i] = input.nextDouble();
  252.         }
  253.         test(mat, constants);          
  254.     }
  255. }

Output:

$ javac Gauss_Jordan_Elimination.java
$ java Gauss_Jordan_Elimination
Enter the number of variables in the equations: 
2
Enter the coefficients of each variable for each equations
ax + by + cz + ... = d
1 2 3
6 5 4
Solution to Ax = b
 -1.0
 
  2.0

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.