CHAPTER -II

LINEAR ALGEBRAIC
EQUATIONS
we will deal with the case of determining the values of x1, x2 ,..., xn that simultaneously satisfy the set of equations

where the a 's are constant coefficients, the b 's are constants, and n is the number of equations. The above system of
linear equations may also be written in matrix form as

where [A] is an n by n square matrix of coefficients (called the coefficient matrix),

{B} is an n by 1 column vector of constants

and {X} is an n by 1 column vector of unknowns

11/15/2025 Weyneshet G. 2
 Non - Computer methods
There are some non-computer methods which are used to solve small ( n < 3 ) sets of simultaneous equations
that do not require a computer.
The Graphical Method
A graphical solution is obtainable for two equations by plotting them on Cartesian coordinates with one axis
corresponding to x1 and the other to x2. Because we are dealing with linear systems, each equation is a straight
line. This can be easily illustrated for the general equations

the equations are now in the form of straight lines; that is, x2 = (slope) x1 + intercept. These lines can be
graphed on Cartesian coordinates with x2 as the ordinate and x1 as the abscissa. The values of x1 and x2 at
the intersection of the lines represent the solution

11/15/2025 Weyneshet G. 3
For a system of linear equations, representing every equation graphically i.e
• Lines for 2 variables
• Planes for 3 variables
• For n variables, holding m variables constants and studying behavior graphically by
varying the rest of the variables(n-m <3)

Example {-2x+4y=10; 2x-y=11} solution ={x=9.0, y=7.0}

11/15/2025 Weyneshet G. 4
Advantages Help in visualizing the nature of such systems
systems that are very close to being singular can also cause problems. These systems are
said to be ill-conditioned

It is difficult to identify the exact point at which the lines intersect. Ill-conditioned systems will
also pose problems when they are encountered during the numerical solution of linear equations.
This is because they will be extremely sensitive to round-off error

Singular
No solution Infinite solutions Ill-Conditioned
11/15/2025 Weyneshet G. 5
 Disadvantages
• Useless for systems with rank >=3

• 4D and 5D systems aren’t what you’d think.

Cramer's Rule
Cramer’s rule is another solution technique that is best suited to small numbers of equations.

• The determinant can be illustrated for a set of three equations:

where [A] is the coefficient matrix:

11/15/2025 Weyneshet G. 6
 The determinant D of this system is formed from the coefficients of the equation

singular systems had zero

determinants
• where the 2 by 2 determinants are called minors.

This rule states that each unknown in a system of linear algebraic equations may be expressed as a fraction
of two determinants with denominator D and with the numerator obtained from D by replacing the column
of coefficients of the unknown in question by the constants b1, b2, . . . , bn.

11/15/2025 Weyneshet G. 7
Example 2.1 Use Cramer’s rule to solve

D = 0.3(-0.07) - 0.52(0.06) + 1(0.05) = -0.0022

11/15/2025 Weyneshet G. 8
11/15/2025 Weyneshet G. 9
 Elimination of Unknowns
The procedure consisted of two steps:
1. The equations were manipulated to eliminate one of the unknowns from the equations. The result of
this elimination step was that we had one equation with one unknown.
2. Consequently, this equation could be solved directly and the result back-substituted into one of the
original equations to solve for the remaining unknown.

Gauss Elimination
The approach is designed to solve a general set of n equations:
The naive Gauss elimination method consists of two phases

------------------- a
------------------- b

------------------- c
11/15/2025 Weyneshet G. 10
Forward Elimination of Unknowns: The first phase is designed to reduce the set of equations to an upper
triangular system .The initial step will be to eliminate the first unknown, x1, from the second through the nth
equations. To do this, multiply equation a by a21/a11 to give

------------------- d

this equation d can be subtracted b

11/15/2025 Weyneshet G. 11
 Back Substitution

Example 2.2 Use Gauss elimination to solve

------------------- a

------------------- b
------------------- c

The first part of the procedure is forward elimination. Multiply a by (0.1)/3 and subtract the result
from b
0.1x1-(0.1)2x2/3-0.02x3/3=0.785/3
0.1x1 +7x2 -0.3x3 = -19.3

11/15/2025 Weyneshet G. 12
 ------------------- a

------------------- b
------------------- c

To complete the forward elimination, x2 must be removed from c .To accomplish this, multiply b by
-0.190000/7.00333 and subtract the result from c. This eliminates x2 from the third equation and reduces the
system to an upper triangular form, as in

back substitution

11/15/2025 Weyneshet G. 13
 Pitfalls of Elimination Methods
There are some pitfalls that must be explored before writing general computer program to implement the method
Division by Zero
During both elimination and back-substitution phases, it is possible that a division by zero can occur.
Problems also arise when the coefficient is very close to zero. pivoting

Round-off Errors
The problem of round-off errors can become particularly important when large numbers of equations are to be
solved. A rough rule of thumb is that round-off errors may be important when dealing with 100 or more
equations.
Ill conditioned Systems
well-conditioned systems are those where a small change in one or more of the coefficients results in a
similar small change in the solution. Ill-conditioned systems are those where a small change in coefficients in
large changes in the solution. An alternative interpretation of ill-conditioning is that a wide range of answers
can approximately satisfy the equations.
An ill-conditioned system is one with a determinant of the coefficient matrix close to zero.

11/15/2025 Weyneshet G. 14
 iv, Singular Systems
The system is singular when at least two of the equations are identical. In such cases, we would lose one
degree of freedom, and would be dealing with impossible case of n -1 equations in n unknowns.
Techniques for Improving Solutions
1,Use of more significant figures
2,Pivoting: can be partial or complete
Partial Pivoting: Determine the largest available coefficient in the column below the pivot
element. The rows are then switched so that the largest element is the pivot element.

Example 2.3 Use Gauss elimination to solve

Note that in this form the first pivot element, a11 = 0.0003, is
very close to zero. Then repeat the computation, but partial
pivot by reversing the order of the equations. The exact
solution is x1 = 1/3 and x2 = 2/3.

11/15/2025 Weyneshet G. 15
 Multiplying the first equation by 1/(0.0003) yields

which can be used to eliminate x1 from the second equation:

which can be solved for

This result can be substituted back into the first equation to evaluate x1:

------- 1

However, due to subtractive cancellation, the result is very sensitive to the number of significant figures
carried in the computation

11/15/2025 Weyneshet G. 16
Note how the solution for x1 is highly dependent on the number of significant figures. This is because in
Eq 1 we are subtracting two almost-equal numbers. On the other hand, if the equations are solved in
reverse order, the row with the larger pivot element is normalized.

Elimination and substitution yield x2 = 2/3. For different numbers of significant figures,
x1 can be computed from the first equation, as in

11/15/2025 Weyneshet G. 17
Complete Pivoting: If columns as well as rows are searched for the largest element and then switched, then
procedure is called complete pivoting. Complete pivoting is rarely used because switching columns changes
the order of the x’s
3. Scaling: Scaling is the process by which the maximum element in a row is made to be 1 by dividing the
equation by the largest coefficient.

Example 2.4 Solve the following set of equations using Gauss elimination and a pivoting
strategy

11/15/2025 Weyneshet G. 18
A, Without scaling, forward elimination is applied to give

Although x2 is correct, x1 is 100 percent in error because of round-off.

B, Repeat the solution after scaling the equations so that the maximum coefficient in each row is 1.
Scaling transforms the original equations to

Therefore, the rows should be pivoted to put the greatest value on the diagonal

Forward elimination yields

Thus, scaling leads to the correct answer

As in the previous example, scaling has utility in minimizing round-off. However, it should be noted that scaling
itself also leads to round-off.
11/15/2025 Weyneshet G. 19
 GAUSS-JORDAN

The Gauss-Jordan method is a variation of Gauss elimination. The major difference is that
• when an unknown is eliminated in the Gauss-Jordan method, it is eliminated from all other equations rather
than just the subsequent ones.
• all rows are normalized by dividing them by their pivot elements. Thus, the elimination step results in an
identity matrix rather than a triangular matrix . Consequently, it is not necessary to employ back
substitution to obtain the solution.

Example 2.5 Use the Gauss-Jordan technique to solve the same system as in

11/15/2025 Weyneshet G. 20
First, express the coefficients and the
right-hand side as an augmented matrix:

Next, normalize the second row by dividing it by

7.00333:
Then normalize the first row by dividing
it by the pivot element, 3, to yield

Reduction of the x2 terms from the first and third equations

gives

The x1 term can be eliminated from the second

row by subtracting 0.1 times the first row from
the second row. Similarly, subtracting 0.3 times
the first row from the third row will eliminate the The third row is then normalized by dividing it by
x1 term from the third row: 10.0120:

11/15/2025 Weyneshet G. 21
 Finally, the x3 terms can be reduced from the first and the second equations to give

the coefficient matrix has been transformed to the identity matrix, and the solution is obtained in
the right-hand-side vector.

11/15/2025 Weyneshet G. 22
 LU Decomposition
Gauss elimination is designed to solve systems of linear algebraic equations ,

Although it certainly represents a sound way to solve such systems, it becomes inefficient when solving
equations with the same coefficients [A], but with different right-hand-side constants
LU decomposition methods separate the time-consuming elimination of the matrix [A] from the
manipulations of the right-hand side {B}. Thus, once [A] has been “decomposed,” multiple right-hand-side
vectors can be evaluated in an efficient manner

Overview of LU Decomposition

------- i

11/15/2025 Weyneshet G. 23
 Now, assume that there is a lower diagonal matrix with 1’s on the
diagonal
------- ii

------- iii

------- iv

------- v

A two-step strategy for obtaining solutions can be based on Eqs. (i), (iv), and (v):
1. LU decomposition step. [A] is factored or “decomposed” into lower [L] and upper [U] triangular matrices.

2. Substitution step. [L] and [U] are used to determine a solution {X} for a right-hand side {B}. This step itself
consists of two steps. First, Eq. (v) is used to generate an intermediate vector {D} by forward substitution.
Then, the result is substituted into Eq. (i), which can be solved by back substitution for {X}.

11/15/2025 Weyneshet G. 24
11/15/2025 Weyneshet G. 25
Example 2.6 Derive an LU decomposition based on the Gauss elimination

After forward elimination, the following upper triangular matrix was obtained :

11/15/2025 Weyneshet G. 26
 Cheak

11/15/2025 Weyneshet G. 27
 Complete the problem

That the forward-elimination phase of conventional Gauss elimination resulted in

11/15/2025 Weyneshet G. 28
11/15/2025 Weyneshet G. 29
 Iterative Solution of Linear Systems
GAUSS-SEIDEL
The Gauss-Seidel method is the most commonly used iterative method. Assume that we are given a set of n
equations:

Now, we can start the solution process by

• choosing guesses for the x’s. A simple way to obtain initial guesses is to assume that they are all zero.
• These zeros can be substituted into the equation for x 1 which can be used to calculate a new value for x1 =
b1/a11.
• Then, we substitute this new value of x1 along with the previous guess of zero for x3 into the equation for x2 to
compute a new value for x2.
• The process is repeated for equation for x3 to calculate a new estimate for x3. Then we return to the first
equation and repeat the entire procedure until our solution converges closely enough to the true values .

11/15/2025 Weyneshet G. 30
 Example 2.7 use Gauss-Seidel Method to solve the following system of equations

By assuming that x2 and x3 are zero,

This value, along with the assumed value of x3 = 0,

11/15/2025 Weyneshet G. 31
The first iteration is completed by substituting the calculated values for x1 and
x2

For the second iteration, the same process is repeated to compute

How do we determine if the iteration will converge

to a solution ??

11/15/2025 Weyneshet G. 32
 Diagonally dominant.
This criterion is sufficient but not necessary for convergence. convergence is guaranteed if the condition is
satisfied. That is, the diagonal coefficient in each of the equations must be larger than the sum of the
absolute values of the other coefficients in the equation.
• An nxn matrix is called diagonally dominant, if the diagonal element in every row is greater in
magnitude(Absolute Values) than the sum of the elements in that row excluding the diagonal
element.

Example 2.8 check if the matrix is diagonally dominant

11/15/2025 Weyneshet G. 33
 is not diagonally dominant.
The matrix can be made diagonally dominant by exchanging rows

Can be used to facilitate convergence for iterative methods

11/15/2025 Weyneshet G. 34
 Jacobi method
An alternative approach, called Jacobi iteration, utilizes a somewhat different tactic. Rather than using
the latest available x’s as Gauss-Seidel Method ,this technique uses the equations below, to compute a set
of new x’s on the basis of a set of old x’s. Thus, as new values are generated, they are not immediately
used but rather are retained for the next iteration.

The Conjugate Gradient Method

The difference between the Gauss-Seidel method and Jacobi iteration is depicted in fig below. Although
there are certain cases where the Jacobi method is useful, Gauss-Seidel’s utilization of the best available
estimates usually makes it the method of preference

11/15/2025 Weyneshet G. 35
 The Gauss-Seidel The Jacobi iterative

11/15/2025 Weyneshet G. 36
Example 2.9 use Jacobi iterative Method to solve the following system of equations

11/15/2025 Weyneshet G. 37
 1,Given the system of equations

(a) Compute the determinant.

(b) Use Cramer’s rule to solve for the x’s.
(c) Use Gauss elimination with partial pivoting to solve for
the x’s. As part of the computation, calculate the determinant in order to verify the value computed in (a).
(d) Substitute your results back into the original equations
to check your solution

11/15/2025 Weyneshet G. 38
2, A civil engineer involved in construction requires 4800, 5800, and 5700 m3 of sand, fine gravel, and
coarse gravel, respectively, for a building project. There are three pits from which these materials can be
obtained. The composition of these pits is

How many cubic meters must be hauled from each pit in order to meet the engineer’s needs?

11/15/2025 Weyneshet G. 39
11/15/2025 Weyneshet G. 40