Naïve Gaussian Elimination method for solving systems of linear equations using Matlab

 

Gaussian Elimination

Naïve Gaussian Elimination is a widely used algorithm for solving systems of linear equations. The basic idea is to transform the system of equations into an equivalent upper triangular system, and then solve for the unknowns by back substitution. Here are the steps:

1. Write the augmented matrix of the system of equations.
2. Perform row operations to transform the matrix into an upper triangular form, i.e., all elements below the main diagonal are zero.
3. Solve for the unknowns by back substitution, starting with the last equation and working upward.

Let's consider an example to illustrate the steps.

Suppose we have the following system of equations:

x + y + z = 6 2x - y + z = 3 -3x + 4y + z = 13

Step 1: Write the augmented matrix

We can write the augmented matrix as follows:

| 1 1 1 | 6 | | 2 -1 1 | 3 | |-3 4 1 |13 |

Step 2: Perform row operations

We want to eliminate the x-coefficient in the second and third rows. We can do this by subtracting twice the first row from the second row, and adding three times the first row to the third row:

| 1 1 1 | 6 | | 0 -3 -1 | -9 | | 0 7 4 | 31|

Now we want to eliminate the y-coefficient in the third row. We can do this by adding 7/3 times the second row to the third row:

| 1 1 1 | 6 | | 0 -3 -1 | -9 | | 0 0 19/3| 4/3|

Step 3: Solve for the unknowns by back substitution

From the third row, we can solve for z as z = 4/3 * 3/19 = 4/19. Plugging this back into the second row, we can solve for y as y = (-9 + z)/(-3) = 5/19. Finally, plugging in the values of y and z into the first row, we can solve for x as x = 6 - y - z = 16/19.

Therefore, the solution to the system of equations is x = 16/19, y = 5/19, and z = 4/19

Now let us solve using Matlab solver: consider the following example, we will have the following simple Matlab code. The code takes inputs after pivoting.

% The method of Gaussian method to solve a system of equations

% Define the coefficient matrix A and the constant vector B with Pivoting

A = [5 -2 0; 1 2 -1;0 -3 7 ];

B = [2 ; 3 ; 2];

% Combine A and B into an augmented matrix AB

AB = [A B] % Joins A and B to from A|B

% Get the size of the matrix AB

[m, n] = size(AB) % Defines the size of the matrix AB

% Perform row operations to reduce the matrix AB to upper triangular form

for i = 1:m-1 % loop over each row except the last row

for j = i+1:m % loop over each row below the current row

% Compute the factor to multiply the current row by

factor = AB(j,i) / AB(i,i)

% Subtract a multiple of the current row from the lower row

AB(j,:) = AB(j,:) - factor * AB(i,:)

end

end

% Back-substitute to solve for x

x = zeros(m, 1) % initialize x as a column vector of zeros

x(m) = AB(m,n) / AB(m,m) % compute the last element of x ||column

for i = m-1:-1:1 % loop over each row in reverse order

sum = AB(i,n) % initialize sum as the right-hand side constant

for j = i+1:m % loop over each column to the right of the current row

sum = sum - AB(i,j) * x(j) % subtract the product of the coefficient and

                                    %the corresponding element of x

end

x(i) = sum / AB(i,i) % divide the remaining constant by the coefficient

end

fprintf('x(i+1) =\t%f\n',x)

Result

The following is the result of the code. It shows the result in each line of code for simple understanding. In a formal way, we need to suppress unnecessary things using a semi-colon. If you do it in hand the same result can be obtained.

Gauss

AB =
5 -2 0 2
1 2 -1 3
0 -3 7 2
m =
3
n =
4
factor =
0.2000
AB =
5.0000 -2.0000 0 2.0000
0 2.4000 -1.0000 2.6000
0 -3.0000 7.0000 2.0000
factor =
0
AB =
5.0000 -2.0000 0 2.0000
0 2.4000 -1.0000 2.6000
0 -3.0000 7.0000 2.0000
factor =
-1.2500
AB =
5.0000 -2.0000 0 2.0000
0 2.4000 -1.0000 2.6000
0 0 5.7500 5.2500
x =
0
0
0
x =
0
0
0.9130
sum =

2.6000
sum =
3.5130
x =
0
1.4638
0.9130
sum =
2
sum =
4.9275
sum =
4.9275
x =
0.9855
1.4638
0.9130

x(i+1) = 0.985507
x(i+1) = 1.463768
x(i+1) = 0.913043