C Program to Implement Gauss Seidel Method

The Gauss Seidel Method is an iterative method to solve a system of linear equations when the number of iterations is specified. In numerical linear algebra, the Gauss–Seidel method, also known as the Liebmann method or the method of successive displacement.

Problem Description:

Write a C program to implement the Gauss Seidel Method.

Problem Solution

A system of linear equations can be solved iteratively using the Gauss-Seidel method if the number of iterations is known. For each iteration we solve the equation and the final values of the variables is our answer.

Example:

Let us apply the Gauss seidel method for the following system of linear equations:

2x + 3y + z = 2
5x + 4y + 6z = 3
8x + 7y + 9z = 4

For First Iteration:

x = 1.000000 y = -0.500000 z = -0.055556

For Second Iteration:

x = 1.777778 y = -1.388889 z = -0.055556

For Third Iteration:

x = 3.111111 y = -3.055555 z = 0.055555

For Fourth Iteration:

x = 5.555555 y= -6.277777 z= 0.388889

Algorithm:
Step 1: Start the program.
Step 2: Input no of equations(size of 2-d array).
Step 3: Input left hand and right hand side of each equations.
Step 4: Input no of iterations.
Step 5: For each iteration, calculate Xni using the formula of Gauss Seidel Method.
Step 6: Print the solution
Step 7: End the Program.

Program/Source Code

Here is source code of the C program to solve a system of linear equations using Gauss Seidel Method. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `/*`
2. ` * C program to implement Gauss Seidel Method`
3. ` */`
4. `#include<stdio.h>`
5. ` `
6. `int main()`
7. `{`
8. `    float a[10][10], b[10], x[10], y[10];`
9. `    int n = 0, m = 0, i = 0, j = 0;`
10. `    printf("Enter size of 2d array(Square matrix) : ");`
11. `    scanf("%d",&n);`
12. ` `
13. `    //Input values of left side of equations`
14. `    for (i = 0; i < n; i++)`
15. `    {`
16. `        for (j = 0; j < n; j++)`
17. `        {`
18. `           printf("Enter values no :( %d , %d ) ",i,j);`
19. `            scanf("%d",&a[i][j]);`
20. `        }`
21. `    }`
22. ` `
23. `    //Input right side of equations`
24. `    printf("\nEnter Values to the right side of equation\n");`
25. `    for (i = 0; i < n; i++)`
26. `    {`
27. `        printf("Enter values no :( %d , %d ) ",i,j);`
28. `        scanf("%d",&b[i]);`
29. `    }`
30. ` `
31. `    //Input initial values of x`
32. `    printf("Enter initial values of x\n");`
33. `    for (i = 0; i < n; i++)`
34. `    {`
35. `        printf("Enter values no. :( %d ):",i);`
36. `        scanf("%d",&x[i]);`
37. `    }`
38. ` `
39. `    //Input number of iterations`
40. `    printf("\nEnter the no. of iteration : ");`
41. `    scanf("%d",&m);`
42. ` `
43. `    //Iterating a loop for no of iterations`
44. `    while (m > 0)`
45. `    {`
46. `        for (i = 0; i < n; i++)`
47. `        {`
48. `            y[i] = (b[i] / a[i][i]);`
49. `            for (j = 0; j < n; j++)`
50. `            {`
51. `                if (j == i)`
52. `                    continue;`
53. `                y[i] = y[i] - ((a[i][j] / a[i][i]) * x[j]);`
54. `                x[i] = y[i];`
55. `            }`
56. `            printf("x%d = %f    ", i + 1, y[i]);`
57. `        }`
58. `        printf("\n");`
59. `        m--;`
60. `    }`
61. `    return 0;`
62. `}`
Program Explanation

1. First input the no of equations and then input the left hand and right hand side of each equation and the no of operations.
2. Then, for each iteration, calculate the values of variables and print them.
3. Iterating through a loop until the condition is met.
4. The value of variables in the last iteration is the final solution of the equation.

Time Complexity: O(m*n)
As for each iteration, a task is performed(each task individually has n iterations), so time complexity is O(m*n).

Space Complexity: O(n2)
Since Space is required to store the coefficients of equations, the space complexity is O(n2).

Run Time Testcases

In this case, we enter “3” as the size of the matrix and the linear equations “2x + 3y + z = 2”, “5x + 4y + 6z = 3”, and “8x + 7y + 9z = 4”, and conduct up to 4 iterations.

```Enter size of 2d array(Square matrix) : 3
Enter values no :( 0 , 0 ) 2
Enter values no :( 0 , 1 ) 3
Enter values no :( 0 , 2 ) 1
Enter values no :( 1 , 0 ) 5
Enter values no :( 1 , 1 ) 4
Enter values no :( 1 , 2 ) 6
Enter values no :( 2 , 0 ) 8
Enter values no :( 2 , 1 ) 7
Enter values no :( 2 , 2 ) 9
Enter Values to the right side of equation
Enter values no :( 0 , 3 ) 2
Enter values no :( 1 , 3 ) 3
Enter values no :( 2 , 3 ) 4
Enter initial values of x
Enter values no. :( 0 ):0
Enter values no. :( 1 ):0
Enter values no. :( 2 ):0
Enter the no. of iteration : 4
x1 = 1.000000    x2 = -0.500000    x3 = -0.055556
x1 = 1.777778    x2 = -1.388889    x3 = -0.055556
x1 = 3.111111    x2 = -3.055555    x3 = 0.055555
x1 = 5.555555    x2 = -6.277777    x3 = 0.388889```
Gauss Seidel Method using a Brute-force Technique

This C program implements iterative version of Gauss Seidel Method. In this method, a system of linear equations is solved by iteration, using a brute-force kind of technique, to reach the actual solution.

Program/Source Code

Here is the source code of the C program to solve a system of linear equations. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

1. `#include <stdio.h> `
2. ` `
3. `int main()`
4. `{ `
5. `    //a sparse way of representing the equations `
6. `    float eq[3][4];`
7. `    int i;`
8. `    float x ,y , z; `
9. `    x = 1; y = 1; z = 2; //initial guess`
10. `    eq[0][0] = 7/4.0; `
11. `    eq[0][1] = 0; `
12. `    eq[0][2] = 1/4.0; `
13. `    eq[0][3]= -1/4.0;`
14. `    eq[1][0] = 21/8.0; `
15. `    eq[1][1] = 4/8.0;`
16. `    eq[1][2] = 0;`
17. `    eq[1][3]= 1/8.0;`
18. `    eq[2][0] = 15/5.0;`
19. `    eq[2][1] = 2/5.0;`
20. `    eq[2][2] = -1/5.0;`
21. `    eq[2][3]= 0;`
22. ` `
23. `    //10 iterations of gauss-seidel `
24. `    for (i = 0;i < 10; i++)`
25. `    {`
26. `        x = eq[0][0] + eq[0][2] * y + eq[0][3] * z;`
27. `        y = eq[1][0] + eq[1][1] * x + eq[1][3] * z;`
28. `        z = eq[2][0] + eq[2][1] * x + eq[2][2] * y;`
29. `        printf("Output: \n%f %f %f\n", x, y, z); `
30. `    } `
31. ` `
32. `    return 0; `
33. `}`
Run Time Testcases
```\$ gcc gauss_seidel.c -o gauss_seidel
\$ ./gauss_seidel

1.500000 3.625000 2.875000
1.937500 3.953125 2.984375
1.992188 3.994141 2.998047
1.999023 3.999268 2.999756
1.999878 3.999908 2.999969
1.999985 3.999989 2.999996
1.999998 3.999999 3.000000
2.000000 4.000000 3.000000
2.000000 4.000000 3.000000
2.000000 4.000000 3.000000```

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.