Introduction to Numerical Analysis

( Arithmetic Errors: Stable computation;

Linear Systems: Gaussian elimination method)

MA 214, Spring 2023-24.

MA 214 - NA Spring 2022-23 1 / 42

Error Analysis: Types of Errors
Definition (Errors)
1 The error in a computed quantity is defined as
Error = True Value - Approximate Value.

MA 214 - NA Spring 2022-23 2 / 42

Error Analysis: Types of Errors
Definition (Errors)
1 The error in a computed quantity is defined as
Error = True Value - Approximate Value.
2 Absolute value of an error is called the absolute error.

MA 214 - NA Spring 2022-23 2 / 42

Error Analysis: Types of Errors
Definition (Errors)
1 The error in a computed quantity is defined as
Error = True Value - Approximate Value.
2 Absolute value of an error is called the absolute error.
3 The relative error is a measure of the error in relation to the size of
the true value as given by
Error
Relative Error = ; True Value ̸= 0
True Value

MA 214 - NA Spring 2022-23 2 / 42

Error Analysis: Types of Errors
Definition (Errors)
1 The error in a computed quantity is defined as
Error = True Value - Approximate Value.
2 Absolute value of an error is called the absolute error.
3 The relative error is a measure of the error in relation to the size of
the true value as given by
Error
Relative Error = ; True Value ̸= 0
True Value
4 The percentage error is defined as
Percentage Error = 100 × |Relative Error|.
MA 214 - NA Spring 2022-23 2 / 42
Error Analysis: Types of Errors (contd.)

Remark: Let xA denote the approximation to the real number x. We use

the following notations:

E(xA ) := Error(xA ) = x − xA .
Ea (xA ) := Absolute Error(xA ) = |E(xA )|
E(xA )
Er (xA ) := Relative Error(xA ) = , x ̸= 0.
x

MA 214 - NA Spring 2022-23 3 / 42

Error Analysis: Significant Digits

Definition (Significant β-Digits)

Let β be a radix.
If xA is an approximation to x, then we say that xA approximates x to r
significant β-digits if r is the largest non-negative integer such that
|x − xA | 1
|Er (xA )| := ≤ β −r+1 .
|x| 2
Here we assume that x ̸= 0.

MA 214 - NA Spring 2022-23 4 / 42

Error Analysis: Loss of Significant Digits

Example: Consider the function

√ √
f (x) = x( x + 1 − x).

MA 214 - NA Spring 2022-23 5 / 42

Error Analysis: Loss of Significant Digits

Example: Consider the function

√ √
f (x) = x( x + 1 − x).

The value of f (100000) using six-digit rounding is 100.

True value is 158.113.

MA 214 - NA Spring 2022-23 5 / 42

Error Analysis: Loss of Significant Digits

Example: Consider the function

√ √
f (x) = x( x + 1 − x).

The value of f (100000) using six-digit rounding is 100.

True value is 158.113.

There is a drastic error in the value of the function, which is due to the
loss of significant digits.

MA 214 - NA Spring 2022-23 5 / 42

Example

Instead of using the true values xT = 0.71456371 and yT = 0.71456238

in calculating zT = xT − yT , if we use the approximate values
xA = 0.71456414 and yA = 0.71456103, and calculate zA = xA − yA , find
the loss of significant digits in the process of calculating zA when
compared to the significant digits in xA .

MA 214 - NA Spring 2022-23 6 / 42

Solution
We have zT = 0.00000133 and zA = 0.00000311. Therefore
zT − zA
0.5 × 100 < ≈ 1.3383458648 ≤ 0.5 × 101 .
zT
⇒ −r + 1 = 1 ⇒ Number of significant digits = 0.
Also, we have xT = 0.71456371 and xA = 0.71456414. Therefore
xT − xA
0.5 × 10−6 < ≈ 0.0000006018 ≤ 0.5 × 10−5 .
xT
⇒ −r + 1 = −5 ⇒ Number of significant digits = 6.
Therefore the loss of significance in zA when compared to xA is 6
(number of significant digits in xA when compared to xT − number of
significant digits in zA when compared to zT ).
MA 214 - NA Spring 2022-23 7 / 42
Condition Number (contd.)

Definition (Condition number of a function)

The condition number of a continuously differentiable function f at a
point x = c is given by
f ′ (c)
c .
f (c)

MA 214 - NA Spring 2022-23 8 / 42

Condition Number (contd.)

Definition (Well-Conditioned and Ill-Conditioned)

The process of evaluating a continuously differentiable function f at a
point x = c is said to be well-conditioned if the condition number

f ′ (c)
c
f (c)
at c is small.
The process of evaluating a function at x = c is said to be
ill-conditioned if it is not well-conditioned.

“How small the condition number should be?”

MA 214 - NA Spring 2022-23 9 / 42
Stable and Unstable Computations

Definition (Stability and Instability in Evaluating a Function)

Suppose there are n steps to evaluate a function f (x) at a point x = c.
Then the total process of evaluating this function is said to have
instability if atleast one of the n steps is ill-conditioned. If all the steps
are well-conditioned, then the process is said to be stable.

MA 214 - NA Spring 2022-23 10 / 42

Error Analysis: Propagated Error in Addition and Subtraction
Let xT = xA + ϵ

MA 214 - NA Spring 2022-23 11 / 42

Error Analysis: Propagated Error in Addition and Subtraction
Let xT = xA + ϵ and yT = yA + η
are positive real numbers.

MA 214 - NA Spring 2022-23 11 / 42

Error Analysis: Propagated Error in Addition and Subtraction
Let xT = xA + ϵ and yT = yA + η
are positive real numbers.
The relative error Er (xA ± yA ) is given by
(xT ± yT ) − (xA ± yA )
Er (xA ± yA ) =
xT ± yT

MA 214 - NA Spring 2022-23 11 / 42

Error Analysis: Propagated Error in Addition and Subtraction
Let xT = xA + ϵ and yT = yA + η
are positive real numbers.
The relative error Er (xA ± yA ) is given by
(xT ± yT ) − (xA ± yA )
Er (xA ± yA ) =
xT ± yT
(xT ± yT ) − (xT − ϵ ± (yT − η))
=
xT ± yT

MA 214 - NA Spring 2022-23 11 / 42

Error Analysis: Propagated Error in Addition and Subtraction
Let xT = xA + ϵ and yT = yA + η
are positive real numbers.
The relative error Er (xA ± yA ) is given by
(xT ± yT ) − (xA ± yA )
Er (xA ± yA ) =
xT ± yT
(xT ± yT ) − (xT − ϵ ± (yT − η))
=
xT ± yT
ϵ±η
= .
xT ± yT

MA 214 - NA Spring 2022-23 11 / 42

Error Analysis: Propagated Error in Addition and Subtraction
Let xT = xA + ϵ and yT = yA + η
are positive real numbers.
The relative error Er (xA ± yA ) is given by
(xT ± yT ) − (xA ± yA )
Er (xA ± yA ) =
xT ± yT
(xT ± yT ) − (xT − ϵ ± (yT − η))
=
xT ± yT
ϵ±η
= .
xT ± yT
This shows that relative error propagates slowly with addition, whereas
amplifies drastically with subtraction when xT ≈ yT .
MA 214 - NA Spring 2022-23 11 / 42
Error Analysis: Propagated Error in Multiplication
The relative error Er (xA × yA ) is given by
(xT × yT ) − (xA × yA )
Er (xA × yA ) =
xT × yT

MA 214 - NA Spring 2022-23 12 / 42

Error Analysis: Propagated Error in Multiplication
The relative error Er (xA × yA ) is given by
(xT × yT ) − (xA × yA )
Er (xA × yA ) =
xT × yT
(xT × yT ) − ((xT − ϵ) × (yT − η))
=
xT × yT

MA 214 - NA Spring 2022-23 12 / 42

Error Analysis: Propagated Error in Multiplication
The relative error Er (xA × yA ) is given by
(xT × yT ) − (xA × yA )
Er (xA × yA ) =
xT × yT
(xT × yT ) − ((xT − ϵ) × (yT − η))
=
xT × yT
ηxT + ϵyT − ϵη
=
xT × yT

MA 214 - NA Spring 2022-23 12 / 42

Error Analysis: Propagated Error in Multiplication
The relative error Er (xA × yA ) is given by
(xT × yT ) − (xA × yA )
Er (xA × yA ) =
xT × yT
(xT × yT ) − ((xT − ϵ) × (yT − η))
=
xT × yT
ηxT + ϵyT − ϵη
=
xT × yT
  
ϵ η ϵ η
= + −
xT yT xT yT

MA 214 - NA Spring 2022-23 12 / 42

Error Analysis: Propagated Error in Multiplication
The relative error Er (xA × yA ) is given by
(xT × yT ) − (xA × yA )
Er (xA × yA ) =
xT × yT
(xT × yT ) − ((xT − ϵ) × (yT − η))
=
xT × yT
ηxT + ϵyT − ϵη
=
xT × yT
  
ϵ η ϵ η
= + −
xT yT xT yT

⇒ Er (xA × yA ) = Er (xA ) + Er (yA ) − Er (xA )Er (yA ).

This shows that relative error propagates slowly with multiplication.
MA 214 - NA Spring 2022-23 12 / 42
Error Analysis: Propagated Error in Division
The relative error Er (xA /yA ) is given by
(xT /yT ) − (xA /yA )
Er (xA /yA ) =
xT /yT

MA 214 - NA Spring 2022-23 13 / 42

Error Analysis: Propagated Error in Division
The relative error Er (xA /yA ) is given by
(xT /yT ) − (xA /yA )
Er (xA /yA ) =
xT /yT
(xT /yT ) − ((xT − ϵ)/(yT − η))
=
xT /yT

MA 214 - NA Spring 2022-23 13 / 42

Error Analysis: Propagated Error in Division
The relative error Er (xA /yA ) is given by
(xT /yT ) − (xA /yA )
Er (xA /yA ) =
xT /yT
(xT /yT ) − ((xT − ϵ)/(yT − η))
=
xT /yT
xT (yT − η) − yT (xT − ϵ)
=
xT (yT − η)

MA 214 - NA Spring 2022-23 13 / 42

Error Analysis: Propagated Error in Division
The relative error Er (xA /yA ) is given by
(xT /yT ) − (xA /yA )
Er (xA /yA ) =
xT /yT
(xT /yT ) − ((xT − ϵ)/(yT − η))
=
xT /yT
xT (yT − η) − yT (xT − ϵ)
=
xT (yT − η)
ϵyT − ηxT
=
xT (yT − η)

MA 214 - NA Spring 2022-23 13 / 42

Error Analysis: Propagated Error in Division
The relative error Er (xA /yA ) is given by
(xT /yT ) − (xA /yA )
Er (xA /yA ) =
xT /yT
(xT /yT ) − ((xT − ϵ)/(yT − η))
=
xT /yT
xT (yT − η) − yT (xT − ϵ)
=
xT (yT − η)
ϵyT − ηxT
=
xT (yT − η)
yT
= (Er (xA ) − Er (yA ))
yT − η
MA 214 - NA Spring 2022-23 13 / 42
Error Analysis: Propagated Error in Division
The relative error Er (xA /yA ) is given by
(xT /yT ) − (xA /yA )
Er (xA /yA ) =
xT /yT
(xT /yT ) − ((xT − ϵ)/(yT − η))
=
xT /yT
xT (yT − η) − yT (xT − ϵ)
=
xT (yT − η)
ϵyT − ηxT
=
xT (yT − η)
yT
= (Er (xA ) − Er (yA ))
yT − η

1
⇒ Er (xA /yA ) = (Er (xA ) − Er (yA )).
1 − Er (yA )
=⇒ relative error propagates slowly with division, unless Er (yA ) ≈ 1.
MA 214 - NA Spring 2022-23 14 / 42
Example

Let xA = 3.14 and yA = 2.651 be obtained from xT and yT using 4-digit

rounding. Find the smallest interval that contains
(i) xT (ii) yT (iii) xT + yT (iv) xT /yT .

MA 214 - NA Spring 2022-23 15 / 42

Solution

Given xA = 3.14 and yA = 2.651. Since these numbers are obtained

using 4-digit rounding from their respective true values, we can see that
(i) 3.1395 ≤ xT < 3.1405.
(ii) 2.6505 ≤ yT < 2.6515.

(iii) From (i) and (ii), we can see that

3.1395+2.6505 ≤ xT +yT < 3.1405+2.6515 =⇒ 5.79 ≤ xT +yT < 5.792.

MA 214 - NA Spring 2022-23 16 / 42

Solution contd..

(iv) From (ii),

1 1 1
2.6505 ≤ yT < 2.6515 =⇒ < ≤
2.6515 yT 2.6505
Now using (i), we get
3.1395 xT 3.1405
< <
2.6515 yT 2.6505

MA 214 - NA Spring 2022-23 17 / 42

Linear System: General Form

General form of a system of n linear equations in n variables is

a11 x1 + a12 x2 + · · · + a1n xn = b1

a21 x1 + a22 x2 + · · · + a2n xn = b2
···
···
···
an1 x1 + an2 x2 + · · · + ann xn = bn

MA 214 - NA Spring 2022-23 18 / 42

General Form of Linear System (contd.)
These equations can be written in the matrix notation as
 
a11 a12 · · · a1n
a21 a22 · · · a2n 
 . .. .. 
 .. . ··· . 
an1 an2 · · · ann

MA 214 - NA Spring 2022-23 19 / 42

General Form of Linear System (contd.)
These equations can be written in the matrix notation as
  
a11 a12 · · · a1n x1
a21 a22 · · · a2n  x2 
 . .. ..  .=
 .. . ··· .   .. 
an1 an2 · · · ann xn

MA 214 - NA Spring 2022-23 19 / 42

General Form of Linear System (contd.)
These equations can be written in the matrix notation as
    
a11 a12 · · · a1n x1 b1
a21 a22 · · · a2n  x2  b2 
 . .. ..  .= .
 .. . ··· .   ..   .. 
an1 an2 · · · ann xn bn

MA 214 - NA Spring 2022-23 19 / 42

General Form of Linear System (contd.)
These equations can be written in the matrix notation as
    
a11 a12 · · · a1n x1 b1
a21 a22 · · · a2n  x2  b2 
 . .. ..  .= .
 .. . ··· .   ..   .. 
an1 an2 · · · ann xn bn
The last equation is usually written in the following short form
Ax = b,

MA 214 - NA Spring 2022-23 19 / 42

General Form of Linear System (contd.)
These equations can be written in the matrix notation as
    
a11 a12 · · · a1n x1 b1
a21 a22 · · · a2n  x2  b2 
 . .. ..  .= .
 .. . ··· .   ..   .. 
an1 an2 · · · ann xn bn
The last equation is usually written in the following short form
Ax = b,
where
A stands for the n × n matrix with entries aij ,

MA 214 - NA Spring 2022-23 19 / 42

General Form of Linear System (contd.)
These equations can be written in the matrix notation as
    
a11 a12 · · · a1n x1 b1
a21 a22 · · · a2n  x2  b2 
 . .. ..  .= .
 .. . ··· .   ..   .. 
an1 an2 · · · ann xn bn
The last equation is usually written in the following short form
Ax = b,
where
A stands for the n × n matrix with entries aij ,
x = (x1 , x2 , · · · , xn )T

MA 214 - NA Spring 2022-23 19 / 42

General Form of Linear System (contd.)
These equations can be written in the matrix notation as
    
a11 a12 · · · a1n x1 b1
a21 a22 · · · a2n  x2  b2 
 . .. ..  .= .
 .. . ··· .   ..   .. 
an1 an2 · · · ann xn bn
The last equation is usually written in the following short form
Ax = b,
where
A stands for the n × n matrix with entries aij ,
x = (x1 , x2 , · · · , xn )T
the right hand side vector b = (b1 , b2 , · · · , bn )T .
MA 214 - NA Spring 2022-23 19 / 42
General Form of Linear System (contd.)
Let us now state a result concerning the solvability of the system
Ax = b.

MA 214 - NA Spring 2022-23 20 / 42

General Form of Linear System (contd.)
Let us now state a result concerning the solvability of the system
Ax = b.

Theorem
Let A be an n × n matrix and b ∈ Rn .

MA 214 - NA Spring 2022-23 20 / 42

General Form of Linear System (contd.)
Let us now state a result concerning the solvability of the system
Ax = b.

Theorem
Let A be an n × n matrix and b ∈ Rn . Then the following statements
concerning the system of linear equations Ax = b are equivalent.

MA 214 - NA Spring 2022-23 20 / 42

General Form of Linear System (contd.)
Let us now state a result concerning the solvability of the system
Ax = b.

Theorem
Let A be an n × n matrix and b ∈ Rn . Then the following statements
concerning the system of linear equations Ax = b are equivalent.
1 det(A) ̸= 0

MA 214 - NA Spring 2022-23 20 / 42

General Form of Linear System (contd.)
Let us now state a result concerning the solvability of the system
Ax = b.

Theorem
Let A be an n × n matrix and b ∈ Rn . Then the following statements
concerning the system of linear equations Ax = b are equivalent.
1 det(A) ̸= 0
2 For each right hand side vector b, the system Ax = b has a unique
solution x.

MA 214 - NA Spring 2022-23 20 / 42

General Form of Linear System (contd.)
Let us now state a result concerning the solvability of the system
Ax = b.

Theorem
Let A be an n × n matrix and b ∈ Rn . Then the following statements
concerning the system of linear equations Ax = b are equivalent.
1 det(A) ̸= 0
2 For each right hand side vector b, the system Ax = b has a unique
solution x.
3 For b = 0, the only solution of the system Ax = b is x = 0.
MA 214 - NA Spring 2022-23 20 / 42
Side Remark

Let Mn (R) denote the set of all n × n matrices and GLn (R) denote the
subset of Mn (R) consisting of all invertible matrices. Similarly one
denotes matrices with complex entries by Mn (C) and GLn (C).

An interesting fact is that GLn (R) is dense in Mn (R). In fact, for a

singular matrix A, A + ϵId is invertible for any small ϵ.

MA 214 - NA Spring 2022-23 21 / 42

Side Remark

Let Mn (R) denote the set of all n × n matrices and GLn (R) denote the
subset of Mn (R) consisting of all invertible matrices. Similarly one
denotes matrices with complex entries by Mn (C) and GLn (C).

An interesting fact is that GLn (R) is dense in Mn (R). In fact, for a

singular matrix A, A + ϵId is invertible for any small ϵ.

The same density result is true with GLn (C) ⊂ Mn (C).

MA 214 - NA Spring 2022-23 21 / 42

Side Remark

Let Mn (R) denote the set of all n × n matrices and GLn (R) denote the
subset of Mn (R) consisting of all invertible matrices. Similarly one
denotes matrices with complex entries by Mn (C) and GLn (C).

An interesting fact is that GLn (R) is dense in Mn (R). In fact, for a

singular matrix A, A + ϵId is invertible for any small ϵ.

The same density result is true with GLn (C) ⊂ Mn (C).

Diagonalizable n × n complex matrices are dense in Mn (C). However its

not true that diagonalizable real n × n matrices are dense in Mn (R).

MA 214 - NA Spring 2022-23 21 / 42

Side Remark

Let Mn (R) denote the set of all n × n matrices and GLn (R) denote the
subset of Mn (R) consisting of all invertible matrices. Similarly one
denotes matrices with complex entries by Mn (C) and GLn (C).

An interesting fact is that GLn (R) is dense in Mn (R). In fact, for a

singular matrix A, A + ϵId is invertible for any small ϵ.

The same density result is true with GLn (C) ⊂ Mn (C).

Diagonalizable n × n complex matrices are dense in Mn (C). However its

not true that diagonalizable real n × n matrices are dense in Mn (R).

Reason ??
MA 214 - NA Spring 2022-23 21 / 42
Linear Systems: Naive Gaussian Elimination Method

Carl Friedrich Gauss (1777–1855) German mathematician

MA 214 - NA Spring 2022-23 22 / 42

Linear Systems: Naive Gaussian Elimination Method

Carl Friedrich Gauss (1777–1855) German mathematician

MA 214 - NA Spring 2022-23 22 / 42

Linear Systems: Naive Gaussian Elimination Method

Carl Friedrich Gauss (1777–1855) German mathematician

Consider the following system:

a11 x1 + a12 x2 + a13 x3 = b1

a21 x1 + a22 x2 + a23 x3 = b2 ⇐⇒ Upper triangular System
a31 x1 + a32 x2 + a33 x3 = b3 .

MA 214 - NA Spring 2022-23 22 / 42

Linear Systems: Naive Gaussian Elimination Method (contd.)
Step 1: If a11 ̸= 0, then define
a21 a31
m21 = , m31 = .
a11 a11

MA 214 - NA Spring 2022-23 23 / 42

Linear Systems: Naive Gaussian Elimination Method (contd.)
Step 1: If a11 ̸= 0, then define
a21 a31
m21 = , m31 = .
a11 a11
We will now obtain a new system that is equivalent to the given system
a11 x1 + a12 x2 + a13 x3 = b1
a21 x1 + a22 x2 + a23 x3 = b2
a31 x1 + a32 x2 + a33 x3 = b3
.

MA 214 - NA Spring 2022-23 23 / 42

Linear Systems: Naive Gaussian Elimination Method (contd.)
Step 1: If a11 ̸= 0, then define
a21 a31
m21 = , m31 = .
a11 a11
We will now obtain a new system that is equivalent to the given system
a11 x1 + a12 x2 + a13 x3 = b1
a21 x1 + a22 x2 + a23 x3 = b2
a31 x1 + a32 x2 + a33 x3 = b3
.
The first equation will be retained as it is.

MA 214 - NA Spring 2022-23 23 / 42

Linear Systems: Naive Gaussian Elimination Method (contd.)
Step 1: If a11 ̸= 0, then define
a21 a31
m21 = , m31 = .
a11 a11
We will now obtain a new system that is equivalent to the given system
a11 x1 + a12 x2 + a13 x3 = b1
a21 x1 + a22 x2 + a23 x3 = b2
a31 x1 + a32 x2 + a33 x3 = b3
.
The first equation will be retained as it is.
The second equation will be replaced by the equation E2 − m21 E1 .

MA 214 - NA Spring 2022-23 23 / 42

Linear Systems: Naive Gaussian Elimination Method (contd.)
Step 1: If a11 ̸= 0, then define
a21 a31
m21 = , m31 = .
a11 a11
We will now obtain a new system that is equivalent to the given system
a11 x1 + a12 x2 + a13 x3 = b1
a21 x1 + a22 x2 + a23 x3 = b2
a31 x1 + a32 x2 + a33 x3 = b3
.
The first equation will be retained as it is.
The second equation will be replaced by the equation E2 − m21 E1 .
The third equation will be replaced by the equation E3 − m31 E1 .
MA 214 - NA Spring 2022-23 23 / 42
Linear Systems: Naive Gaussian Elimination Method (contd.)
m21 E1 =⇒

MA 214 - NA Spring 2022-23 24 / 42

Linear Systems: Naive Gaussian Elimination Method (contd.)
a12 a21 a13 a21 b1 a21
m21 E1 =⇒ a21 x1 + x2 + x3 =
a11 a11 a11

MA 214 - NA Spring 2022-23 24 / 42

Linear Systems: Naive Gaussian Elimination Method (contd.)
a12 a21 a13 a21 b1 a21
m21 E1 =⇒ a21 x1 + x2 + x3 =
a11 a11 a11
E2 − m21 E1 =⇒ 0 + (a22 − m21 a12 )x2 + (a23 − m21 a13 )x3 = b2 − m21 b1 .

MA 214 - NA Spring 2022-23 24 / 42

Linear Systems: Naive Gaussian Elimination Method (contd.)
a12 a21 a13 a21 b1 a21
m21 E1 =⇒ a21 x1 + x2 + x3 =
a11 a11 a11
E2 − m21 E1 =⇒ 0 + (a22 − m21 a12 )x2 + (a23 − m21 a13 )x3 = b2 − m21 b1 .
The new system is given by
a11 x1 + a12 x2 + a13 x3 = b1
(2) (2) (2)
0 + a22 x2 + a23 x3 = b2
(2) (2) (2)
0 + a32 x2 + a33 x3 = b3 ,
(2) (2)
where the coefficients aij , and bk are given by
(2)
aij = aij − mi1 a1j , i, j = 2, 3
(2)
bk = bk − mk1 b1 , k = 2, 3.
MA 214 - NA Spring 2022-23 24 / 42
Naive Gaussian Elimination Method (contd.)
(2)
(2) a32
Step 2: If a22 ̸= 0, then define m32 = (2)
.
a22

MA 214 - NA Spring 2022-23 25 / 42

Naive Gaussian Elimination Method (contd.)
(2)
(2) a32
Step 2: If a22 ̸= 0, then define m32 = (2)
.
a22
We will now obtain a new system that is equivalent to the system
a11 x1 + a12 x2 + a13 x3 = b1
(2) (2) (2)
0 + a22 x2 + a23 x3 = b2
(2) (2) (2)
0 + a32 x2 + a33 x3 = b3 ,

as follows:

MA 214 - NA Spring 2022-23 25 / 42

Naive Gaussian Elimination Method (contd.)
(2)
(2) a32
Step 2: If a22 ̸= 0, then define m32 = (2)
.
a22
We will now obtain a new system that is equivalent to the system
a11 x1 + a12 x2 + a13 x3 = b1
(2) (2) (2)
0 + a22 x2 + a23 x3 = b2
(2) (2) (2)
0 + a32 x2 + a33 x3 = b3 ,

as follows:
The first two equations are retained.

MA 214 - NA Spring 2022-23 25 / 42

Naive Gaussian Elimination Method (contd.)
(2)
(2) a32
Step 2: If a22 ̸= 0, then define m32 = (2)
.
a22
We will now obtain a new system that is equivalent to the system
a11 x1 + a12 x2 + a13 x3 = b1
(2) (2) (2)
0 + a22 x2 + a23 x3 = b2
(2) (2) (2)
0 + a32 x2 + a33 x3 = b3 ,

as follows:
The first two equations are retained.
The third equation will be replaced by the equation E3 − m32 E2 .
MA 214 - NA Spring 2022-23 25 / 42
Naive Gaussian Elimination Method (contd.)
Note the new system is given by
a11 x1 + a12 x2 + a13 x3 = b1
(2) (2) (2)
0 + a22 x2 + a23 x3 = b2
(3) (3)
0 + 0 + a33 x3 = b3 ,

MA 214 - NA Spring 2022-23 26 / 42

Naive Gaussian Elimination Method (contd.)
Note the new system is given by
a11 x1 + a12 x2 + a13 x3 = b1
(2) (2) (2)
0 + a22 x2 + a23 x3 = b2
(3) (3)
0 + 0 + a33 x3 = b3 ,
(3) (3)
where the coefficient a33 , and b3 are given by
(3) (2) (2)
a33 = a33 − m32 a23 ,
(3) (2) (2)
b3 = b3 − m32 b2 .

MA 214 - NA Spring 2022-23 26 / 42

Naive Gaussian Elimination Method (contd.)
Note the new system is given by
a11 x1 + a12 x2 + a13 x3 = b1
(2) (2) (2)
0 + a22 x2 + a23 x3 = b2
(3) (3)
0 + 0 + a33 x3 = b3 ,
(3) (3)
where the coefficient a33 , and b3 are given by
(3) (2) (2)
a33 = a33 − m32 a23 ,
(3) (2) (2)
b3 = b3 − m32 b2 .

This phase is called Forward elimination phase.

MA 214 - NA Spring 2022-23 26 / 42
Naive Gaussian Elimination Method (contd.)
Finally, we obtained the system

a11 x1 + a12 x2 + a13 x3 = b1

(2) (2) (2)
0 + a22 x2 + a23 x3 = b2 ⇐⇒ Given system
(3) (3)
0 + 0 + a33 x3 = b3 ,

MA 214 - NA Spring 2022-23 27 / 42

Naive Gaussian Elimination Method (contd.)
Finally, we obtained the system

a11 x1 + a12 x2 + a13 x3 = b1

(2) (2) (2)
0 + a22 x2 + a23 x3 = b2 ⇐⇒ Given system
(3) (3)
0 + 0 + a33 x3 = b3 ,

(3)
a33 ̸= 0 ⇒ x3

MA 214 - NA Spring 2022-23 27 / 42

Naive Gaussian Elimination Method (contd.)
Finally, we obtained the system

a11 x1 + a12 x2 + a13 x3 = b1

(2) (2) (2)
0 + a22 x2 + a23 x3 = b2 ⇐⇒ Given system
(3) (3)
0 + 0 + a33 x3 = b3 ,

(3)
a33 ̸= 0 ⇒ x3
Put x3 in (E2 ) gives x2

MA 214 - NA Spring 2022-23 27 / 42

Naive Gaussian Elimination Method (contd.)
Finally, we obtained the system

a11 x1 + a12 x2 + a13 x3 = b1

(2) (2) (2)
0 + a22 x2 + a23 x3 = b2 ⇐⇒ Given system
(3) (3)
0 + 0 + a33 x3 = b3 ,

(3)
a33 ̸= 0 ⇒ x3
Put x3 in (E2 ) gives x2
Put x2 and x3 in (E1 ) gives x1 .

MA 214 - NA Spring 2022-23 27 / 42

Naive Gaussian Elimination Method (contd.)
Finally, we obtained the system

a11 x1 + a12 x2 + a13 x3 = b1

(2) (2) (2)
0 + a22 x2 + a23 x3 = b2 ⇐⇒ Given system
(3) (3)
0 + 0 + a33 x3 = b3 ,

(3)
a33 ̸= 0 ⇒ x3
Put x3 in (E2 ) gives x2
Put x2 and x3 in (E1 ) gives x1 .
This solution phase is called
Backward substitution phase.
MA 214 - NA Spring 2022-23 27 / 42
Naive Gaussian Elimination Method (contd.)
Gaussian elimination ⇒ LU-factorization.

MA 214 - NA Spring 2022-23 28 / 42

Naive Gaussian Elimination Method (contd.)
Gaussian elimination ⇒ LU-factorization.
 
a11 a12 a13
 (2) (2) 
U =  0 a22 a23  .
(3)
0 0 a33

MA 214 - NA Spring 2022-23 28 / 42

Naive Gaussian Elimination Method (contd.)
Gaussian elimination ⇒ LU-factorization.
 
a11 a12 a13
 (2) (2) 
U =  0 a22 a23  .
(3)
0 0 a33

Define a lower triangular matrix L by

 
1 0 0
L = m21 1 0 .
m31 m32 1

MA 214 - NA Spring 2022-23 28 / 42

Naive Gaussian Elimination Method (contd.)
Gaussian elimination ⇒ LU-factorization.
 
a11 a12 a13
 (2) (2) 
U =  0 a22 a23  .
(3)
0 0 a33

Define a lower triangular matrix L by

 
1 0 0
L = m21 1 0 .
m31 m32 1

It is easy to verify that LU = A.

MA 214 - NA Spring 2022-23 28 / 42
Naive Gaussian Elimination Method (contd.)

Remark:
Why Naive?

MA 214 - NA Spring 2022-23 29 / 42

Naive Gaussian Elimination Method (contd.)

Remark:
Why Naive?

1 May not be successful even for invertible systems.

MA 214 - NA Spring 2022-23 29 / 42

Naive Gaussian Elimination Method (contd.)

Remark:
Why Naive?

1 May not be successful even for invertible systems.

2 May increase rounding error drastically.

MA 214 - NA Spring 2022-23 29 / 42

Naive Gaussian Elimination Method (contd.)

Example:
Consider the linear system

6x1 + 2x2 + 2x3 = −2

2 1
2x1 + x2 + x3 = 1
3 3
x1 + 2x2 − x3 = 0.

Let us compute using 4-digit rounding.

MA 214 - NA Spring 2022-23 30 / 42

Naive Gaussian Elimination Method (contd.)
The system to be solved is
6.000x1 + 2.000x2 + 2.000x3 = −2.000
2.000x1 + 0.6667x2 + 0.3333x3 = 1.000
1.000x1 + 2.000x2 − 1.000x3 = 0.000

MA 214 - NA Spring 2022-23 31 / 42

Naive Gaussian Elimination Method (contd.)
The system to be solved is
6.000x1 + 2.000x2 + 2.000x3 = −2.000
2.000x1 + 0.6667x2 + 0.3333x3 = 1.000
1.000x1 + 2.000x2 − 1.000x3 = 0.000
After eliminating x1 from the second and third equations, we get (with
m21 = 0.3333, m31 = 0.1667).

MA 214 - NA Spring 2022-23 31 / 42

Naive Gaussian Elimination Method (contd.)
The system to be solved is
6.000x1 + 2.000x2 + 2.000x3 = −2.000
2.000x1 + 0.6667x2 + 0.3333x3 = 1.000
1.000x1 + 2.000x2 − 1.000x3 = 0.000
After eliminating x1 from the second and third equations, we get (with
m21 = 0.3333, m31 = 0.1667).
6.000x1 + 2.000x2 + 2.000x3 = −2.000
0.000x1 + 0.0001x2 − 0.3333x3 = 1.667
0.000x1 + 1.667x2 − 1.333x3 = 0.3334
MA 214 - NA Spring 2022-23 31 / 42
Naive Gaussian Elimination Method (contd.)
After eliminating x2 from the third equation, we get (with m32 = 16670)

MA 214 - NA Spring 2022-23 32 / 42

Naive Gaussian Elimination Method (contd.)
After eliminating x2 from the third equation, we get (with m32 = 16670)
6.000x1 + 2.000x2 + 2.000x3 = −2.000
0.000x1 + 0.0001x2 − 0.3333x3 = 1.667
0.000x1 + 0.0000x2 + 5555x3 = −27790

MA 214 - NA Spring 2022-23 32 / 42

Naive Gaussian Elimination Method (contd.)
After eliminating x2 from the third equation, we get (with m32 = 16670)
6.000x1 + 2.000x2 + 2.000x3 = −2.000
0.000x1 + 0.0001x2 − 0.3333x3 = 1.667
0.000x1 + 0.0000x2 + 5555x3 = −27790
Using back substitution, we get
x1 = 1.335, x2 = 0 and x3 = −5.003,

MA 214 - NA Spring 2022-23 32 / 42

Naive Gaussian Elimination Method (contd.)
After eliminating x2 from the third equation, we get (with m32 = 16670)
6.000x1 + 2.000x2 + 2.000x3 = −2.000
0.000x1 + 0.0001x2 − 0.3333x3 = 1.667
0.000x1 + 0.0000x2 + 5555x3 = −27790
Using back substitution, we get
x1 = 1.335, x2 = 0 and x3 = −5.003,
whereas the actual solution is
x1 = 2.6, x2 = −3.8 and x3 = −5.

MA 214 - NA Spring 2022-23 32 / 42

Naive Gaussian Elimination Method (contd.)
After eliminating x2 from the third equation, we get (with m32 = 16670)
6.000x1 + 2.000x2 + 2.000x3 = −2.000
0.000x1 + 0.0001x2 − 0.3333x3 = 1.667
0.000x1 + 0.0000x2 + 5555x3 = −27790
Using back substitution, we get
x1 = 1.335, x2 = 0 and x3 = −5.003,
whereas the actual solution is
x1 = 2.6, x2 = −3.8 and x3 = −5.
Reason?

MA 214 - NA Spring 2022-23 32 / 42

Naive Gaussian Elimination Method (contd.)
After eliminating x2 from the third equation, we get (with m32 = 16670)
6.000x1 + 2.000x2 + 2.000x3 = −2.000
0.000x1 + 0.0001x2 − 0.3333x3 = 1.667
0.000x1 + 0.0000x2 + 5555x3 = −27790
Using back substitution, we get
x1 = 1.335, x2 = 0 and x3 = −5.003,
whereas the actual solution is
x1 = 2.6, x2 = −3.8 and x3 = −5.
Reason?
The coefficient of x2 in (E2 ) should have been zero, but rounding
approximation prevented it.
MA 214 - NA Spring 2022-23 32 / 42
Naive Gaussian Elimination Method (contd.)

The above examples highlight the inadequacy of the Naive Gaussian

elimination method. These inadequcies can be overcome by modifying
the procedure of Naive Gaussian elimination method. There are many
kinds of modification. We will discuss one of the most popular modified
methods which is called
Modified Gaussian elimination method with partial pivoting

MA 214 - NA Spring 2022-23 33 / 42

Modified Gaussian elimination method with partial pivoting

Consider the following system of three linear equations in three variables

x1 , x2 , x3 :

a11 x1 + a12 x2 + a13 x3 = b1

a21 x1 + a22 x2 + a23 x3 = b2
a31 x1 + a32 x2 + a33 x3 = b3 .

For convenience, we call the first, second, and third equations by names
E1 , E2 , and E3 respectively.

MA 214 - NA Spring 2022-23 34 / 42

Modified Gaussian elimination method with partial pivoting
Step 1: Define s1 = max { |a11 |, |a21 |, |a31 | } .

MA 214 - NA Spring 2022-23 35 / 42

Modified Gaussian elimination method with partial pivoting
Step 1: Define s1 = max { |a11 |, |a21 |, |a31 | } .
Note that s1 ̸= 0 : why?

MA 214 - NA Spring 2022-23 35 / 42

Modified Gaussian elimination method with partial pivoting
Step 1: Define s1 = max { |a11 |, |a21 |, |a31 | } .
Note that s1 ̸= 0 : why?
Let k be the least number such that s1 = |ak1 |.

MA 214 - NA Spring 2022-23 35 / 42

Modified Gaussian elimination method with partial pivoting
Step 1: Define s1 = max { |a11 |, |a21 |, |a31 | } .
Note that s1 ̸= 0 : why?
Let k be the least number such that s1 = |ak1 |.
Interchange the first row and the kth row.

MA 214 - NA Spring 2022-23 35 / 42

Modified Gaussian elimination method with partial pivoting
Step 1: Define s1 = max { |a11 |, |a21 |, |a31 | } .
Note that s1 ̸= 0 : why?
Let k be the least number such that s1 = |ak1 |.
Interchange the first row and the kth row. Rewritten system is
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(1) (1) (1) (1)
a21 x1 + a22 x2 + a23 x3 = b2
(1) (1) (1) (1)
a31 x1 + a32 x2 + a33 x3 = b3 .

MA 214 - NA Spring 2022-23 35 / 42

Modified Gaussian elimination method with partial pivoting
Step 1: Define s1 = max { |a11 |, |a21 |, |a31 | } .
Note that s1 ̸= 0 : why?
Let k be the least number such that s1 = |ak1 |.
Interchange the first row and the kth row. Rewritten system is
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(1) (1) (1) (1)
a21 x1 + a22 x2 + a23 x3 = b2
(1) (1) (1) (1)
a31 x1 + a32 x2 + a33 x3 = b3 .
where (1) (1) (1)
a11 = ak1 , a12 = ak2 , a13 = ak3 ,
(1) (1) (1)
ak1 = a11 , ak2 = a12 , ak3 = a13 ;
(1) (1)
b1 = bk , bk = b1
MA 214 - NA Spring 2022-23 35 / 42
Modified Gaussian elimination method with partial pivoting

Now eliminate the x1 variable from the second and third equations of
the system
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(1) (1) (1) (1)
a21 x1 + a22 x2 + a23 x3 = b2
(1) (1) (1) (1)
a31 x1 + a32 x2 + a33 x3 = b3 .

MA 214 - NA Spring 2022-23 36 / 42

Modified Gaussian elimination method with partial pivoting

Now eliminate the x1 variable from the second and third equations of
the system
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(1) (1) (1) (1)
a21 x1 + a22 x2 + a23 x3 = b2
(1) (1) (1) (1)
a31 x1 + a32 x2 + a33 x3 = b3 .

Proceed as in naive Gaussian elimination method.

MA 214 - NA Spring 2022-23 36 / 42

Modified Gaussian elimination method with partial pivoting
Note the new system is given by
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(2) (2) (2)
0 + a22 x2 + a23 x3 = b2
(2) (2) (2)
0 + a32 x2 + a33 x3 = b3 ,

MA 214 - NA Spring 2022-23 37 / 42

Modified Gaussian elimination method with partial pivoting
Note the new system is given by
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(2) (2) (2)
0 + a22 x2 + a23 x3 = b2
(2) (2) (2)
0 + a32 x2 + a33 x3 = b3 ,
(2) (2)
where the coefficients aij , and bk are given by
(2) (1) (1)
aij = aij − mi1 a1j , i, j = 2, 3
(2) (1) (1)
bi = bi − mi1 b1 , i = 2, 3.

MA 214 - NA Spring 2022-23 37 / 42

Modified Gaussian elimination method with partial pivoting
n o
(2) (2)
Step 2: Define s2 = max |a22 |, |a32 | .

MA 214 - NA Spring 2022-23 38 / 42

Modified Gaussian elimination method with partial pivoting
n o
(2) (2)
Step 2: Define s2 = max |a22 |, |a32 | .
(2)
Let l be the least number such that sl = |al2 |.

MA 214 - NA Spring 2022-23 38 / 42

Modified Gaussian elimination method with partial pivoting
n o
(2) (2)
Step 2: Define s2 = max |a22 |, |a32 | .
(2)
Let l be the least number such that sl = |al2 |.
Interchange the second row and the lth rows. The rewritten system is
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(3) (3) (3)
0 + a22 x2 + a23 x3 = b2
(3) (3) (3)
0 + a32 x2 + a33 x3 = b3 ,

MA 214 - NA Spring 2022-23 38 / 42

Modified Gaussian elimination method with partial pivoting
n o
(2) (2)
Step 2: Define s2 = max |a22 |, |a32 | .
(2)
Let l be the least number such that sl = |al2 |.
Interchange the second row and the lth rows. The rewritten system is
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(3) (3) (3)
0 + a22 x2 + a23 x3 = b2
(3) (3) (3)
0 + a32 x2 + a33 x3 = b3 ,
(3) (3)
where the coefficients aij , and bi are given by
(3) (2) (3) (2) (3) (2) (3) (2)
a22 = al2 , a23 = al3 , al2 = a22 , al3 = a23 ,
(3) (2) (3) (2)
b2 = bl , bl = b2
MA 214 - NA Spring 2022-23 38 / 42
Modified Gaussian elimination method with partial pivoting
Note the new system is given by
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(3) (3) (3)
0 + a22 x2 + a23 x3 = b2
(4) (4)
0 + 0 + a33 x3 = b3 ,

MA 214 - NA Spring 2022-23 39 / 42

Modified Gaussian elimination method with partial pivoting
Note the new system is given by
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(3) (3) (3)
0 + a22 x2 + a23 x3 = b2
(4) (4)
0 + 0 + a33 x3 = b3 ,
(4) (4)
where the coefficient a33 , and b3 are given by

MA 214 - NA Spring 2022-23 39 / 42

Modified Gaussian elimination method with partial pivoting
Note the new system is given by
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(3) (3) (3)
0 + a22 x2 + a23 x3 = b2
(4) (4)
0 + 0 + a33 x3 = b3 ,
(4) (4)
where the coefficient a33 , and b3 are given by
(4) (3) (3)
a33 = a33 − m32 a23 ,
(4) (3) (3)
b3 = b3 − m32 b2 .

MA 214 - NA Spring 2022-23 39 / 42

Modified Gaussian elimination method with partial pivoting
Note the new system is given by
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(3) (3) (3)
0 + a22 x2 + a23 x3 = b2
(4) (4)
0 + 0 + a33 x3 = b3 ,
(4) (4)
where the coefficient a33 , and b3 are given by
(4) (3) (3)
a33 = a33 − m32 a23 ,
(4) (3) (3)
b3 = b3 − m32 b2 .
Note that the variable x2 has been eliminated from the last equation.

MA 214 - NA Spring 2022-23 39 / 42

Modified Gaussian elimination method with partial pivoting
Note the new system is given by
(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(3) (3) (3)
0 + a22 x2 + a23 x3 = b2
(4) (4)
0 + 0 + a33 x3 = b3 ,
(4) (4)
where the coefficient a33 , and b3 are given by
(4) (3) (3)
a33 = a33 − m32 a23 ,
(4) (3) (3)
b3 = b3 − m32 b2 .
Note that the variable x2 has been eliminated from the last equation.
This phase is called Forward elimination phase with partial
MA 214 - NA Spring 2022-23 39 / 42
Modified Gaussian elimination method with partial pivoting

The reduced system is

(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(3) (3) (3)
0 + a22 x2 + a23 x3 = b2
(4) (4)
0 + 0 + a33 x3 = b3 ,

MA 214 - NA Spring 2022-23 40 / 42

Modified Gaussian elimination method with partial pivoting

The reduced system is

(1) (1) (1) (1)
a11 x1 + a12 x2 + a13 x3 = b1
(3) (3) (3)
0 + a22 x2 + a23 x3 = b2
(4) (4)
0 + 0 + a33 x3 = b3 ,

Now do the Backward substitution phase.

MA 214 - NA Spring 2022-23 40 / 42

Modified Gaussian elimination method with partial pivoting
Recall the system
6x1 + 2x2 + 2x3 = −2
2 1
2x1 + x2 + x3 = 1
3 3
x1 + 2x2 − x3 = 0.
was solved using Gaussian Elimination method with four digit rounding
arithmetic.

MA 214 - NA Spring 2022-23 41 / 42

Modified Gaussian elimination method with partial pivoting
Recall the system
6x1 + 2x2 + 2x3 = −2
2 1
2x1 + x2 + x3 = 1
3 3
x1 + 2x2 − x3 = 0.
was solved using Gaussian Elimination method with four digit rounding
arithmetic. Recall the reduced system after Step 1 was
6.000x1 + 2.000x2 + 2.000x3 = −2.000
0.000x1 + 0.0001x2 − 0.3333x3 = 1.667
0.000x1 + 1.667x2 − 1.333x3 = 0.3334
MA 214 - NA Spring 2022-23 41 / 42
Modified Gaussian elimination method with partial pivoting
The final system is (with m32 = 0.00005999)
6.000x1 + 2.000x2 + 2.000x3 = −2.000
0.000x1 + 1.667x2 − 1.333x3 = 0.3334
0.000x1 + 0.0000x2 − 0.3332x3 = 1.667

MA 214 - NA Spring 2022-23 42 / 42

Modified Gaussian elimination method with partial pivoting
The final system is (with m32 = 0.00005999)
6.000x1 + 2.000x2 + 2.000x3 = −2.000
0.000x1 + 1.667x2 − 1.333x3 = 0.3334
0.000x1 + 0.0000x2 − 0.3332x3 = 1.667
with back substitution, we obtain the approximate solution as
x1 = 2.602, x2 = −3.801 and x3 = −5.003.

MA 214 - NA Spring 2022-23 42 / 42

Modified Gaussian elimination method with partial pivoting
The final system is (with m32 = 0.00005999)
6.000x1 + 2.000x2 + 2.000x3 = −2.000
0.000x1 + 1.667x2 − 1.333x3 = 0.3334
0.000x1 + 0.0000x2 − 0.3332x3 = 1.667
with back substitution, we obtain the approximate solution as
x1 = 2.602, x2 = −3.801 and x3 = −5.003.
Recall, the solution obtained without pivoting was
x1 = 1.335, x2 = 0 and x3 = −5.003,

MA 214 - NA Spring 2022-23 42 / 42

Modified Gaussian elimination method with partial pivoting
The final system is (with m32 = 0.00005999)
6.000x1 + 2.000x2 + 2.000x3 = −2.000
0.000x1 + 1.667x2 − 1.333x3 = 0.3334
0.000x1 + 0.0000x2 − 0.3332x3 = 1.667
with back substitution, we obtain the approximate solution as
x1 = 2.602, x2 = −3.801 and x3 = −5.003.
Recall, the solution obtained without pivoting was
x1 = 1.335, x2 = 0 and x3 = −5.003,
whereas the actual solution is
x1 = 2.6, x2 = −3.8 and x3 = −5.
MA 214 - NA Spring 2022-23 42 / 42