NUMERICAL METHODS
Bahar Ayhan, Ph.D.
Civil Engineering Department
Office: 352
E-mail : ayhanb@itu.edu.tr
Phone: +90 212 285 7410
Numerical Methods
CONTENTS
Chapter 2 Solving a System of Linear Equations
• Background
• Gauss elimination method
• Gauss elimination with pivoting
• Gauss-Jordan elimination method
• LU decomposition method
• Inverse of a Matrix
• Iterative methods (Jacobi, Gauss-Seidel)
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Inverse of a Matrix
The inverse of a square matrix [a] is the matrix [a]-1 such that the product
of the two matrices gives the identity matrix [I].
a a = a a = I
−1 −1
• The process of calculating the inverse matrix is essentially the same as
the process of solving a system of linear equations. This is illustrated
for the case of a (4x4) matrix.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Inverse of a Matrix
If [a] is a given matrix and [x] is the unknown inverse of [a], then:
a11 a12 a13 a14 x11 x12 x13 x14 1 0 0 0
a a22 a23
a24 x21 x22 x23 x24 0 1 0 0
21 =
a31 a32 a33 a34 x31 x32 x33 x34 0 0 1 0
a41 a42 a43 a44 x41 x42 x43 x44 0 0 0 1
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Inverse of a Matrix
a11 a12 a13 a14 x11 x12 x13 x14 1 0 0 0
This equation can be written as four separate a a22 a23 a24 x21 x22 x23 x24 0 1 0 0
21 =
systems of equations, where in each system one a31 a32 a33 a34 x31 x32 x33 x34 0 0 1 0
column of the matrix [x] is the unknown. a41 a42 a43 a44 x41 x42 x43 x44 0 0 0 1
1 a11 a12 a13 a14 x11 1 2 a11 a12 a13 a14 x12 0
a a24 x21 0 a
21
a22 a23
= a22 a23 a24 x22 1
21 =
a31 a32 a33 a34 x31 0 a31 a32 a33 a34 x32 0
a41 a42 a43 a44 x41 0 a41 a42 a43 a44 x42 0
3 a11 a12 a13 a14 x13 0 4 a11 a12 a13 a14 x14 0
a a a24 x24 0
a22 a23 a24 x23 0 21
a22 a23
=
21 =
a31 a32 a33 a34 x33 1 a31 a32 a33 a34 x34 0
a41 a42 a43 a44 x43 0 a41 a42 a43 a44 x44 1
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Inverse of a Matrix
Solving the four systems of equations gives the four
columns of the inverse of [a].
The systems of equations can be solved by using any of the
methods that have been introduced earlier.
LU decomposition and Gauss-Jordan elimination method
are described in more detail next.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Inverse of a Matrix
Calculating the Inverse with the LU Decomposition.
The LU decomposition method is especially
suitable for calculating the inverse of a matrix.
The LU decomposition of the matrix [a] is
calculated once.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Inverse of a Matrix
Calculating the Inverse with the LU Decomposition.
First,each of the systems is solved by using the equation below
(forward substitution)
L y = b
Secondly, each of the systems is solved by using the equation below
(back substitution)
U x = y Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Inverse of a Matrix
Calculating the Inverse with the Gauss-Jordan Method.
The Gauss-Jordan method is easily adapted for calculating the inverse of a
square (nxn) matrix [a].
This is done by appending an identity matrix [I] of the same size as the matrix
[a] to [a] itself.
This is shown schematically for a (4x4) matrix:
Calculating the inverse with the Gauss-Jordan method.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Inverse of a Matrix
Calculating the Inverse with the Gauss-Jordan Method.
The Gauss-Jordan procedure is applied such that the elements of the matrix [a]
are converted to 1’s along the diagonal and 0’s elsewhere.
During the process, the terms of the identity matrix are changed and become
the elements [a`], which constitute the inverse of [a].
Calculating the inverse with the Gauss-Jordan method.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods
A system of linear equations can be solved by using an iterative approach.
The process is the same as in the fixed-point iteration method used for
solving a single nonlinear equation.
In an iterative process for solving a system of equations, the equations are
written in an explicit form in which each unknown is written in terms of
the other unknown.
The explicit form for a system of four equations is illustrated:
Bahar
Standard (a) and explicit (b) forms of a system of four equations. Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods
The solution process starts by assuming initial values for the unknowns (first estimated
solution)
In the first iteration, the first assumed solution is substituted on the right-hand side of the
equations, and the new values that are calculated for the unknowns are the second estimated
solution.
In the second iteration, the second solution is subsituted back in the equations to give new
values for the unknowns, which are the third estimated solution.
The iterations continue in the same manner, and when the method does work, the solutions that
are obtained as successive iterations converge toward the actual solution.
For system with n equations, the explicit equations for the [xi] unknowns are:
j =n
1
xi = bi − aij x j i = 1, 2,..., n
aii j =1
Bahar
j i Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods
Condition for convergence
For a system of n equations [a][x]=[b], a sufficient condition for convergence is that in each row of the
matrix of coefficient [a] the absolute value of the diagonal element is greater than the sum of the
absolute values of the off-diagonal elements.
j =n
aii aij i = 1, 2,..., n
j =1
j i
❑ This condition is sufficient but not necessary for convergence when the iteration method is used.
❑ When this condition is satisfied, the matrix [a] is classified as diagonally dominant, and the iteration
process convergences toward the solution. The solution, however, might converge even the condition is
not satisfied.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods
Two specific iterative methods for executing the iterations,
➢ Jacobi method
➢ Gauss-Seidel method
are represented.
❑ The difference between the two methods is in the way that the new calculated values of
the unknown are used.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods
❑ In the Jacobi method, the estimated values of the unknowns that are used on the right-hand side of
equation
j =n
1
xi = bi − aij x j i = 1, 2,..., n
aii j =1
j i
are updated all at once at the end of each iteration.
❑ In the Gauss-Seidel method, the value of each unknown is updated (and used in the calculation of the
new estimate of the rest of the unknowns in the same iteration) when a new estimate for this unknown is
calculated.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods > Jacobi Iterative Method
❑ In the Jacobi method, an initial (first) value is assumed for each of the unknowns,
(1) (1) (1)
x , x ,...., x
1 2 n
❑ If no information is available regarding the approximate values of the unknown, the
initial value of all the unknowns can be assumed to be zero.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods > Jacobi Iterative Method
❑ The second estimate of the solution
x1(2) , x2(2) ,...., xn(2)
is calculated by substituting the first estimate in the right-hand side of equation:
j =n
1
xi(2) = bi − aij x j i = 1, 2,..., n
aii j =1
j i
In general, the (k+1)th estimate of the solution is calculated from the (k)th estimate by
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods > Jacobi Iterative Method
❑ In general, the (k+1)th estimate of the solution is calculated from the (k)th estimate by
j =n
1
xi( k +1) = bi − aij x (jk ) i = 1, 2,..., n
aii j =1
j i
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods > Jacobi Iterative Method
The iterations continue until the difference between the values that are obtained in
successive iterations are small.
The iterations can be stopped when the absolute value of the estimated relative error
of all the unknowns is smaller than some predetermined value.
( k +1)
x −x (k )
i
(k )
i
i = 1, 2,..., n
x i
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods > Gauss-Seidel Iterative Method
In the Gauss-Seidel method, initial (first) values are assumed for the unknowns x2, x3,
....,xn (all of the unknowns except x1)
If no information is available regarding the approximate value of the unknowns, the
initial value of all the unknowns can be assumed to be zero.
The first assumed values of the unknowns are substituted in the equation
j =n
1
xi = bi − aij x j i = 1, 2,..., n
aii j =1
j i
with i=1 to calculate the value of x1.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods > Gauss-Seidel Iterative Method
j =n
1
The equation xi = bi − aij x j i = 1, 2,..., n
aii j =1
j i
with i=2 is used for calculating a new value of x2.
This is followed by using same equation above with i=3 for calculating a new value
for x3.
The process continue until i=n, which is the end of the first iteration.
The second iteration starts with i=1 where a new value for x1 is calculated.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods > Gauss-Seidel Iterative Method
In the Gauss-Seidel method, the current values of the unknowns are used for
calculating the new value of the next unknown.
As a new value of an unknown is calculated, it is immediately used for the next
application of equation
j =n
1
xi = bi − aij x j i = 1, 2,..., n
aii j =1
j i
(In the Jacobi method, the values of the unknowns obtained in one iteration are used as a complete set
for calculating the new values of the unknowns in the next iteration. The values of the unknowns are not
updated in the middle of the iteration.)
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods > Gauss-Seidel Iterative Method
Applying the equation to the Gauss-Seidel method gives the iteration formula
1 j =n
x1( k +1) = b1 − a1 j x j
(k )
a11 j =2
1 j =i −1 j =n
bi − aij x j + a
( k +1) ( k +1)
x i = 1j x (k )
j + i = 1, 2,..., n − 1
aii j =1 j =1+1
1 j = n −1
xn( k +1) bn − anj x j
( k +1)
=
ann j =1
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Iterative Methods > Gauss-Seidel Iterative Method
Notice that values of the unknowns in the (k+1) iteration, xi( k +1) , are calculated
by using the values x (jk +1) obtained in the (k+1) iteration for j<i and using the values x (jk )
for j>i
The criterion for stopping the iterations is the same as in the Jacobi method
xi( k +1) − xi( k )
(k )
i = 1, 2,..., n
xi
The Gauss-Seidel method converges faster than the Jacobi method and
requires less computer memory when programmed.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Error, Residual, Norms, Condition Number
A numerical solution of a system of equations is seldom an exact solution.
Even though direct methods (Gauss, Gauss-Jordan, LU decomposition)
can be exact, they are still susceptible to round-off errors when
implemented on a computer.
This is especially true with large systems and with ill-conditioned systems.
Solutions that are obtained with iterative methods are approximate by
nature.
This section describes measures that can be used for quantifying the
accuracy, or estimating the magnitude of the error of a numerical solution.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Error and Residual
If [xNS] is a computed approximate numerical solution of a system of n equations
[a][x]= [b] and [xTS]is the true (exact) solution, then the true error is the vector:
e = [ xTS ] − [ xNS ]
The true error, however, cannot in general be calculated because the true solution is not
known.
An alternative measure of the accuracy of a solution is the residual [r], which is defined by:
r = a [ xTS ] − a [ xNS ] = b − a [ xNS ]
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Error and Residual
[r] measures how well the system of equations is satisfied when [xNS] is substituted for
[x].
(This is equivalent to the tolerance in f(x) when the solution of a single equation is considered.)
The vector [r] has n elements, and if the numerical solution is close to the true solution,
then all the elements of [r] are small.
It should be remembered that [r] does not really indicate how small the error is in the
solution [x].
[r] only shows how well the right-hand side of the equations is satisfied when [xNS] is
substituted for [x] in the original equations.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
II. Solving a System of Linear Equations: Error and Residual
This depends on the magnitude of the elements of the matrix [a].
It is possible to have an approximate numerical solution that has a large true error but
gives a small residual.
A more accurate estimate of the error in numerical solution can be obtained by using
quantities that measure the size, or magnitude, of vectors and matrices.
For numbers, it is easy to determine which one is large or small by comparing their
absolute values.
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
Numerical Methods
Thank you for your attention !!
Bahar
Ayhan
Numerical Methods
Civil Engineering Department
