Lecture on

Numerical Methods Unit 5

SOLUTIONS TO LINEAR ALGEBRIC

EQUATIONS (Part I)

Prepared By: Er. Sarbesh Chaudhary

H.O.D (Electronics Department)
MMP
CONTENTS
• Basic Fundamentals
• Systems of Linear equations
• Solutions of Linear Equations
• Direct or EliminationMethods
• Basic Gauss Elimination
• Gauss Elimination with partial pivoting
• Gauss Jordon method
• LU decomposition methods
– Do Little Algorithm
– Crout Algorithm
• Matrix Inversion Method
• Cholesky’s Method
 BASIC FUNDAMENTALS
• VECTORS
Vector : a one dimensional array of numbers
Examples :
 2
row vector 1 4 2 column vector  
1 
1 0  0  0 
0  1 0  0 
Identity vectors e1   , e2   , e3   , e4   
0  0  1 0 
       
0  0  0  1
 BASIC FUNDAMENTALS
• MATRICES
Matrix : a two dimensional array of numbers
Examples :
0 0 0 1 0
zero matrix   identity matrix  
0 0 0 0 1
1 0 0 0 1 2 0 0
0 4 0 0 3 4 1 0
diagonal  , Tridiagona l 
0 0 0 0 0 1 4 1
   
0 0 0 6 0 0 2 1
 BASIC FUNDAMENTALS
• Upper and Lower Triangular Matrix

• Upper Triangular Matrix • Lower Triangular Matrix

• It is a square matrix in which all the items • It is a square matrix in which all the
under the main diagonal are zero. elements above the main diagonal are
zero.
 BASIC FUNDAMENTALS
• Augmented Matrix
• It is called extended or augmented matrix that is formed by the Coefficient
matrix and the vector of independent terms, which are usually separated
with a dotted line

• The augmented matrix A|B is represented as follows:

 BASIC FUNDAMENTALS
• Transpose Matrix
Let any matrix A=(aij) of mxn order, then AT is its transpose if the A rows are
the AT columns
 BASIC FUNDAMENTALS
• Symmetric Matrix
It is a square matrix in which the elements are symmetric about the main
diagonal
Example:
If A is a symmetric matrix, then:
a. The product A x AT is defined and is a symmetric
matrix.
b. The sum of symmetric matrices is a symmetric matrix.
c. The product of two symmetric matrices is a symmetric matrix if the
matrices commute
 BASIC FUNDAMENTALS
• Determinant of a MATRICES
• If a matrix has a line (row or column) of zeros, the determinant is zero.
• If a matrix has two equal rows or proportional, the determinant is null
• If we permute two parallels lines of a square matrix, its determinant changes sign.
• If we multiply all elements of a determinant line by a number, the determinant is
multiplied by that number.
• If a matrix line is added another line multiplied by a number, the determinant does
not change.
• The determinant of a matrix is equal to its transpose,
• If A has inverse matrix, A-1, it is verified that: det(A-1 ) = 1/det(A )
BASIC FUNDAMENTALS

Example :
 2 3  1
 
det  1 0 5   2
0 5 3 -1 3 -1
-1 -1
5 4 5 4 0 5
 1 5 4 
 2(25)  1(12  5)  1(15  0)  82
 BASIC FUNDAMENTALS 95
• Addition of Matrices
The addition of two matrices A and B is possible only if
they have the same size
C  A  B  cij  a ij  b ij i, j

• Multiplication of Matrices
Multiplication of two matrices A(n  m) and B(p  q)
The product C  AB is defined only if m  p
m
C  A B  cij   a ik b kj i, j
k 1
BASIC FUNDAMENTALS
• Suppose that we want to multiply [X] by [Y ] to yield [Z ],
3 1
5 9
• [Z] = [X][Y] = 8 6 x
7 2
0 4

• A simple way to visualize the computation of [Z ] is to raise [Y ],as in

SYSTEMS OF LINEAR EQUATIONS
A system of linear equations can be presented
in different forms

2 x1  4 x2  3x3  3  2 4  3  x1  3

2.5 x1  x2  3x3  5   2.5  1 3   x2   5
x1  6 x3  7   1 0  6  x3  7
Standard form Matrix form
SOLUTIONS OF LINEAR EQUATIONS
 x1  1 
 x   2 is a solution to the following equations :
 2  
x1  x2  3
x1  2 x2  5
• A set of equations is inconsistent if there exists no solution to the system of
equations:

x1  2 x2  3
2 x1  4 x2  5
These equations are inconsistent
SOLUTIONS OF LINEAR EQUATIONS
• Some systems of equations may have infinite number of solutions

x1  2 x2  3
2 x1  4 x2  6
have infinite number of solutions
 x1    
 x   0.5(3  ) is a solution for all 
 2  
 SOLUTIONS OF LINEAR EQUATIONS
• There are two classes of methods for solving system of linear, algebraic equations:
1.Direct methods.
2. Indirect or Iterative methods
• Direct methods
• They transform the original equation into equivalent equations (equations that have
the same solution) that can be solved more easily.
• The transformation is carried out by applying certain operations.
• The solution does not contain any truncation errors but the round off errors is
introduced due to floating point operations.
 SOLUTIONS OF LINEAR EQUATIONS
• Indirect methods
• Iterative or indirect methods, start with a guess of the solution x, and then repeatedly refine
the solution until a certain convergence criterion is reached.

• Generally less efficient than direct methods since, large number of operations or iterations
required.

• Iterative procedures are self-correcting, meaning that round off errors (or even arithmetic
mistakes) in one iteration cycle are corrected in subsequent cycles.

• The solution contains truncation error.

• A serious drawback of iterative methods is that they do not always converge to the solution.
 SOLUTIONS OF LINEAR EQUATIONS
• Some of the Direct & Indirect Methods are Listed below:
• Direct Methods:
1. Gauss Elimination with partial pivoting
2. Gauss Jordon method
3. LU decomposition methods
4. Do Little Algorithm
5. Crout Algorithm
6. Matrix Inversion Method
7. Cholesky’s Method
• Indirect or Iterative Methods:
1. Jacobi’s Iteration Method
2. Gauss-Seidal Iteration Method
DIRECT METHODS
GAUSS ELIMINATION METHOD
• Gaussian Elimination Method procedure:
1. Write the augmented matrix for the system of linear equations.

2. Use elementary row operations on the augmented

matrix [A|B] to transform A into upper triangular form. If
a zero is located on the diagonal, switch the rows until a
nonzero is in that place. If you are unable to do so, stop;
Karl Friedrich Gauss
the system has either infinite or no solutions.
Great mathematician 19th century

3. Use back substitution to find the solution of the problem.

 GAUSS ELIMINATION METHOD
• We illustrate the method using the 3 × 3 system
a11x1 + a12x2 + a13 x3 = b1
a21x1 + a22 x2 + a23 x3 = b2 .............. (1)
a31x1 + a32 x2 + a33 x3 = b3
Step 1:The augmented matrix of the system is …….(2)

Step 2: Transform A into upper triangular form

a)First stage of elimination
We assume a11 ≠ 0. This element a11 in the 1 × 1 position is called
the first pivot. Performing the elementary row operations
R2 – (a21/a11)R1 and R3 –(a31/a11)R1 respectively.
We obtain the new augmented matrix as ……………(3)
 GAUSS ELIMINATION METHOD
b) Second stage of elimination
• We assume a22 (1) ≠ 0 . This element a22(1) in the 2 × 2 position is called the second pivot.
• performing the elementary row operation R3 – ( a32(1) / a22(1) )R2. We obtain the new
augmented matrix as
……….(4)

• The element a33 (2) ≠ 0 is called the third pivot.

Step 3: Back Substitution
From Equation 4 we have
• From the third row, we get x3 = b3 ( 2 ) / a33 (2)
• From the second row, we get x2 = (b2(1) − a23(1) x3 )/a22 (1)
• From the first row, we get x1 = (b1 – a12x2 – a13 x3)/a11
GAUSS ELIMINATION METHOD
GAUSS ELIMINATION METHOD

3. Use back substitution to find the solution of the problem

The last row in the augmented matrix represents the equation:

The second row of the augmented matrix represents the equation:

Finally, the first row of the augmented matrix represents the equation
 GAUSS ELIMINATION METHOD
• Gaussian Elimination Method with Partial Pivoting
• Gauss elimination method fails if any one of the pivots in the equations becomes zero.
• To overcome this difficulty, the equations are to be rewritten in a slightly different
order such that the pivots are not zero.
Partial pivoting Procedure:
Step 1: The numerically largest coefficient of x1 is selected from all the equations as pivot
and the corresponding equation becomes the first equation.
Step 2: The numerically largest coefficient of x2 is selected from all the remaining
equations as pivot and the corresponding equation becomes the second equation.
• This process is repeated till an equation into a simple variable is obtained.
• Remaining 1st and last method is same as GEM.
 GAUSS ELIMINATION METHOD
• Example : Solve the system of equations using the Gauss elimination with partial pivoting.
x1 + 10x2 – x3 = 3
2x1 + 3x2 + 20x3 = 7
10x1 – x2 + 2x3 = 4
• Solution:
Step 1: We have the augmented matrix as

Step 2: We perform the following elementary row transformations and do the eliminations.
 GAUSS ELIMINATION METHOD
Step 3:Back substitution gives the solution.
Third equation gives x3 = 5.37624/ 19.98020 = 0.26908.
Second equation gives x2 = (1/10.1)(2.6 + 1.2x3) =(1/10.1)(2.6 + 1.2(0.26908)) = 0.28940.
First equation gives x1 = (1/10)(4 + x2 – 2x3) = (1/10)(4 + 0.2894 – 2(0.26908)) = 0.37512.
PRACTICE QSN:
1) Solve the following equations by Gauss elimination method:
a) 2x + 4y – 6z = –4 b)
x + 5y + 3z = 10
x + 3y + 2z = 5 Ans: x=-3, y=-2, z=1 Ans: x1=1, x2=2, x3=-1, x4=0
2) Solve the following equations using the Gauss elimination with partial pivoting.
a) b) 5x +12y + 9z = 5
8x +11y + 20z = 35
16x + 5y + 7z = 29
Ans: x1=5, x2=6, x3=-10,x4=8 Ans: x = 1.426, y = -1.808, z = 2.174
 GAUSS JORDAN METHOD
• Gauss-Jordan method is a modification of Gauss elimination method.
• The series of operations performed are quite similar to the Gauss elimination method.
• In the Gauss elimination method, an upper triangular matrix is derived while in the
Gauss-Jordan method an identity matrix is derived. Hence, back substitutions are not
required.

Wilhelm Jordan
Famous German Geodesist
 GAUSS JORDAN METHOD
• PROCEDURE:
1. Write the augmented matrix for the system of linear equations.

2. Use elementary row operations on the augmented matrix [A|b] to transform A into
diagonal form. If a zero is located on the diagonal, switch the rows until a nonzero is in that
place. If you are unable to do so, stop; the system has either infinite or no solutions.

3. By dividing the diagonal element and the right-hand-side element in each row by the
diagonal element in that row, make each diagonal element equal to one.
 GAUSS JORDAN METHOD
• Example:
• Step 1: Write the augmented matrix for the system of linear equations.

• Step 2: Use elementary row operations on the augmented matrix [A|b] to transform A
into diagonal form.
 GAUSS JORDAN METHOD
• Step 3: By dividing the diagonal element and the right-hand-side element in each row
by the diagonal element in that row, make each diagonal element equal to one.

• Hence,
PRACTICE QSN: Use to Gauss-Jordan method solve the system
• b) x + 3y + 2z = 17
x + 2y + 3z = 16
Ans: x=y=z=1 2x – y + 4z = 13 Ans: x=4,y=3,z=2
 LU DECOMPOSITION METHOD
• Linear algebraic notation can be rearranged to give
A X- B = 0 eq1
• Suppose that this equation could be expressed as an upper triangular
system:
eq2

• Elimination is used to reduce the system to upper triangular form. The

above equation can also be expressed in matrix notation and rearranged to
give
U X- D= 0 eq3
 LU DECOMPOSITION METHOD
• Now, assume that there is a lower diagonal matrix with 1’s on the diagonal,

• That has the property that when Eq. 3 is pre-multiplied by it, Eq. 1 is the result. That
is, L U X- D =A X- B eq5

• If this equation holds, it follows from the rules for matrix multiplication that
L U =A eq6
L D= B eq7
 LU DECOMPOSITION METHOD
• A two-step strategy for obtaining solutions can be based on Eqs. 3, 6 & 7.
• LU decomposition step. [A] is factored or “decomposed” into lower [L] and upper [U]
triangular matrices.

• 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. 7 is used to generate an intermediate
vector {D} by forward substitution.

• Then, the result is substituted into Eq. 3, which can solved by back substitution for
[X].In the other hand, Gauss Elimination can be implemented in this way.
 LU DECOMPOSITION METHOD
• LU-decomposition of a non-singular matrix (when it exists) is not unique. In practice we
use one of the following alternatives to get unique factorization:
(a) Crout’s formalism: All the diagonal elements of U is chosen 1.
(b) Dolittle’s formalism: All the diagonal elements of L is chosen 1.
Crout’s Method
• Consider the matrix equation of the system of 3 equations in 3 unknowns
𝐴𝑋 = 𝐵
• We write matrix A as a product of an Upper and Lower Triangular matrices[1]
𝐴 = 𝐿𝑈
Prescott Durand Crout
American Mathematician
 LU DECOMPOSITION METHOD
• Since 𝑨 = 𝑳𝑼 ∴ 𝑨𝑿 = 𝑩 eq(1) Gives 𝑳𝑼𝑿 = 𝑩 eq(2)
• Let us take 𝑼𝑿 = 𝒀 eq(3)
• 𝑌 is some unknown matrix which is to be evaluated
• Then 𝐋𝐘 = 𝐁 eq(4)
• Therefore to find the solution of the system (1) we will have to solve (4) and then (3), but
before that we will have to evaluate the values of L and U
PROCEDURE:
• Use the following steps to solve the System of Linear algebraic equations.
 LU DECOMPOSITION METHOD
• Step 2: Calculate the Product of L and U

• • Step 3: write 𝐿 and 𝑈

• • Step 4: Solve 𝐿𝑌 = 𝐵 by forward substitution
• • Step 5: Solve 𝑈𝑋 = 𝑌 by backward substitution
 LU DECOMPOSITION METHOD
Example: Given that

• (i) Determine a lower triangular matrix L and an upper triangular matrix U such that
L U = A using Crout’s algorithm.
• (ii) Use the above factorization to solve the equation A X = B.

Solution: i)
 LU DECOMPOSITION METHOD
• Equating the corresponding elements of the two matrices, we have

• Thus,
 LU DECOMPOSITION METHOD
• (ii) The equation can be written as AX = LUX = LY = B

Where, UX = Y and

• Consider the solution of LY = B

• Using forward elimination, we have y1 = 5, y2 = -3, y3 = 2

• Now consider the solution of UX = Y
 LU DECOMPOSITION METHOD

• Using backward elimination, we have x =1, y = -1, z = 2

and hence

PRACTICE QSN: Solve the following system of equations by Crout’s Method

2𝑥1 − 4𝑥2 + 𝑥3 = 4,
6𝑥1 + 2𝑥2 − 𝑥3 = 10,
−2𝑥1 + 6𝑥2 − 2𝑥3 = −6
 MATRIX INVERSION METHOD
• Consider a set of three simultaneous linear algebraic equations
a11x1 + a12x2 + a13x3 = b1
a21x1 + a22x2 + a23x3 = b2
a31x1 + a32x2 + a33x3 = b3 eq(1)
• Equation (1) can be expressed in the matrix form
Ax = b eq(2)
• Pre-multiplying by the inverse A–1, we obtain the solution of x as
x = A–1b eq(3)
• If the matrix A is non-singular, that is, if det (A) is not equal to zero, then Eq. (3) has a
unique solution.
MATRIX INVERSION METHOD
• The solution for x1 is

• where A is the determinant of the coefficient matrix A, and C11, C21 and C31 are the
cofactors of A corresponding to element 11, 21 and 31.
• We can also write similar expressions for x2 and x3 by replacing the second and third
columns by the y column respectively. Hence, the complete solution can be written in
matrix form as follows:
 MATRIX INVERSION METHOD

• Although this method is quite general but it is not quite suitable for large systems
because evaluation of A–1 by co-factors becomes very cumbersome.
Example: Obtain the solution of the following linear simultaneous equations by the matrix
inversion method.
 MATRIX INVERSION METHOD

• Hence
MATRIX INVERSION METHOD
PRACTICE QSN: Obtain the solution of the following linear simultaneous equations by the
matrix inversion method.

Ans: x1 = 0, x2 = 1, x3 = 2.
 Cholesky’s Method
• Cholesky’s decomposition method is faster than the LU decomposition. There is no
need for pivoting. If the decomposition fails, the matrix is not positive definite.
• Consider the system of linear equations:
a11x1 + a12x2 + a13x3 = b1
a21x1 + a22x2 + a23x3 = b2
a31x1 + a32x2 + a33x3 = b3
• The above system can be written as
Ax = b eq(1) Andre Louis Cholesky
Where French Military & Mathematician
eq(2)
Cholesky’s Method
• Let A = LU

• Equation (1) can be written as LUX = b eq(3)

• If we write UX = V
• Equation (3) becomes LV = b eq(4)
• Equation (4) is equivalent to the system
v1 = b1
l21v1 + v2 = b2
l31v1 + l32v2 + v3 = b3 eq(5)
 Cholesky’s Method
• The above system can be solved to find the values of v1, v2 and v3 which give us the
matrix V.
UX = V
• then becomes
u11x1 + u12x2 + u13x3 = v1
u22x2 + u23x3 = v2
u33x3 = v3 eq(6)
• which can be solved for x3, x2 and x1 by the backward substitution process.
• In order to compute the matrices L and U, we write Eq. (1) as
 Cholesky’s Method
• Multiplying the matrices on the left and equating the corresponding elements of both
sides, we obtain

• The value of u33 can be computed from last eq above

 Cholesky’s Method
• To obtain the elements of L and U, we first find the first row of U and the first column
of L.
• Then, we determine the second row of U and the second column of L. Finally, we
compute the third row of U.

EXAMPLE:
2x + y + 4z = 12
8x – 3y + 2z = 20
4x + 11y – z = 33
Solution:
We have
 Cholesky’s Method
Let

Multiplying and equating we get:

l × u11 = 2⇒ u11 = 2
l × u12 = 1⇒ u12 = 1
l × u13 = 4⇒ u13 = 4
l21 × u11 = 8 ⇒ l21=8 /u11=8/2=4
 Cholesky’s Method

We get,

and the given system can be written as,

 Cholesky’s Method
• Writing: LV = B, we get From backward substitution we have

2x + y + 4z = 12
–7y – 14z = –28
–27z = –27 ⇒z=1
• Which gives, Substituting z in eq b we get,

7y = 28 – 14 × 1 ⇒ y =14/7 ⇒y=2
Now substituting y & z value in eq a we get,
• The solution to the original system is given by:
2x = 12 – y – 4z = 12 – 2 – 4 × 1
UX = V
or, x= 6/2 ⇒x=2
 Cholesky’s Method
PRACTICE QSN:

b) 2x – 6y + 8z = 24
a) x1 + x2 + x3 – x4 = 2
5x + 4y – 3z = 2
x1 – x2 – x3 + 2x4 = 0 3x + y + 2z = 16
4x1 + 4x2 + x3 + x4 = 11
2x1 + x2 + 2x3 – 2x4 = 2
Ans: x4 = 0, x3 = –1, x2 = 2, x1 = 1. Ans: x=1, y=3, z=5