Lecture Notes on Numerical Methods

Error & Convergence

[Link] Ghora

IIITDM Kancheepuram, Chennai, India

07 January 2025
Evaluation (Tentative)

Mid-semester: 25

Project: 25 = 10 (probelem presentation) + 15 (final deliverables)

End - semester : 50
Textbooks and References

Textbooks:
1. David Kincaid, Ward Cheney; Numerical Analysis:
Mathematics of Scientific Computing, Third Edition.
American Mathematical Society, 2012. (ISBN:
978-0-8218-4788-6).
2. Brian Bradie; A Friendly Introduction to Numerical Analysis;
Pearson Education India. 2007.(ISBN: 9788131709429)

References:
1. Kendall E. Atkinson. “An Introduction to Numerical
Analysis.” John Wiley & Sons, Inc., 1988.
2. Curtis F. Gerald, Patrick O. Wheatley; “Applied Numerical
Analysis”, Pearson Education India; 7th edition (2007).
Syllabus
Error and Convergence: Type of error, Computer representation of
numbers, rate of convergence, and order of convergence.

Root findings: Bisection, Newtons, Secant Method, Newtons

Method, Fixed-point Iterations, Methods for multiple root case.

Interpolations: Lagrange, Newton, Divided Difference, Chebyshev

polynomials. Piecewise interpolations and extrapolations.

Linear Equation and Eigenvalue: Direct and Iterative methods,

Norms, Orthogonality, QR Decomposition, Power Method.

Difference and Differential Equations: Difference formula, Methods

for ODE, Stability, and error analysis.

Integrations: Trapezoidal, Simpson and Gauss Quadrature, .

Finite Difference Method: Two point BVPs.

Floating Point Approximation

Definition (n-digit Floating Point)

Let β ∈ N & β ≥ 2, an n-digit floating point number in base β is
of the form:

±q × β e = (−1)s × (·d1 d2 · · · dn )β × β e

where
d1 d2 dn
(·d1 d2 · · · dn )β = + 2 + ··· + n
β β β
where di ∈ {0, 1, · · · , β − 1} with d1 ̸= 0 and q is mantissa.
s = 0 or 1 and appropriate exponent e. β is called the radix.
▶ β = 2 is Binary
▶ β = 10 is Decimal
Note: Computer works internally in the Binary system but
communicates with its human users in the Decimal system.
Example

1. x = 6 · 238 = (−1)0 × 0 · 6238 × 101

here s = 0, β = 10, e = 1, d1 = 6, d2 = 2, d3 = 3, d4 = 8 is
decimal floating point representation.
2. x = −0.0014 = (−1)1 × 0 · 14 × 10−2 is represented in the
decimal floating point where
s = 1, β = 10, e = −2, d1 = 1 and d2 = 4.
1
Remark:- Floating point representation of
3
1
= 0 · 333 · · · = (−1) × (0 · 333 · · · )10 × 100
0
3
Limitations:-
▶ Number of digit in Mantissa (n)
▶ Range of Exponent (e)
Underflow and Overflow of Memory

m≤e≤M
where e is an exponent.
▶ e > M → Memory Overflow → inf and NaN (Not a Number)
▶ e < m → Memory Underflow → (0 × ∞, ∞ − ∞, 0/0, · · · )
Output NaN
X is sufficiently large (Overflow)
x is sufficiently small (Underflow)

X · x = NaN (Not a Number)

▶ Single Precision: β = 2, n = 24
(
m = −126
e-range =
M = 127
 ▶ Double Precision: β = 2, n = 53
(
m = −1022
e-range =
M = 1023

m = −∞ and M = ∞ for the representation of any conceivable

real number.
m & M is finite for Finite Precision numbers

Exercise:-
Show that Number of floating - point numbers for a normalized
system with parameters (β, n, m, M) is

N = 2(β − 1)β n−1 (M − m + 1) + 1

Definition of Normalized Floating - point System
The system is said to be normalized when d1 = 0 if and only if
x =0
Rounding of a Decimal Number

x is a positive decimal number of the form 0 · □□ · · · □ with m

digits to the right of the decimal point.
One rounds x to the n-decimal (n < m) in a manner that depends
on the value of the (n + 1)th digit.
▶ If (n + 1)th digit is 0, 1, 2, 3 or 4 the nth digit is not changed.
▶ If it is 5, 6, 7, 8 or 9 then the nth digit is increased by 1- unit
and remaining digits are discarded.
Note 1
x is rounded → x̃, which is an n-digit approximation, then
1
|x − x̃| ≤ × 10−n . (1)
2
Proof
Case I: If (n + 1)th number of x is 0, 1, 2, 3 or 4, then

x = x̃ + ϵ
|x − x̃| < ϵ × 10−n .
So, Eq (1) follows.

Case II: If (n + 1)th number of x is 5, 6, 7, 8 or 9 then

x̃ = x̂ + 10−n

Where x̂ is a number with same n-decimal digits as x and all digits

beyond the nth are 0.
1
x = x̂ + δ × 10−n with δ ≥ .
2
x̃ − x = (1 − δ) × 10−n
Proof contd.

Again
1 1
δ − 1 ≥ −1 + ⇒1−δ ≤
2 2
Hence
1
x̃ − x ≤ × 10−n (2)
2
So, Eq (2) follows Eq (1)
□

Note 2
Chopped or Truncated n - digit approximation

|x − x̂| < 10−n

Prove this.
Error
Error = True Value - Approximated Value
If x is true value and x̃ is approximated value then Error,
E (x) = x - x̃
Types of Errors
1. Absolute Error: Ea (x) = |x − x̃| = |E (x)|
E (x)
2. Relative Error: Er (x) = for x ̸= 0
x
3. Percentage of Error : EP (X ) = 100 × |Er (x)|
Example 1
let x = 100000 and x̃ = 99999
then Ea (x) = 1, Er (x) = 10−5 , EP (x) = 10−3 %
Example 2
let x = 1 and x̃ = 21
then Ea (x) = 21 , Er (x) = 21 , EP (x) = 50 %
Error contd.
Theorem (Roundoff error on adding)
Let x0 , x1 , . . . , xn be positive machine number and each have unit
roundoff error is ϵ, then relative error is computed by
n
X
(xi ) is usual way is at most (1 + ϵ)n − 1 ≈ nϵ
i=0

Proof:
Let Sk = x0 + x1 + · · · + xk and Sk∗ be what computer calculated
instead of Sk .
The recursive formula

S0 = x0 and Sk+1 = Sk + xk+1

S0∗ = (x0 ) and Sk+1

∗
= fl(Sk∗ + xk+1 )
Proof contd.
For the analysis we define ρk and δk

Sk∗ − Sk S ∗ − (S ∗ + xk+1 )
ρk = and δk = k+1 ∗ k
Sk Sk + xk+1

Thus |ρk | is the relative error in approximating the k th partial sum

Sk∗ and
|δk | is relative error in approximating Sk∗ + xk+1 by quantity
fl(Sk∗ + xk+1 )

SK∗ +1 − SK +1
ρk+1 =
SK +1
∗
(S + xk+1 )(1 + δk ) − SK +1
= k
SK +1
Proof contd.

(Sk (1 + ρk ) + xk+1 )(1 + δk ) − (Sk + xk+1 )

ρk+1 =
Sk+1
(Sk + Sk ρk + xk+1 )(1 + δk ) − (Sk + xk+1 )
=
Sk+1
Sk + Sk ρk +   + Sk δk + Sk ρk δk + xk+1 δk − Sk − 
xk+1 xk+1


=
Sk+1
δk (Sk + xk+1 ) ρk Sk (1 + δk )
= +
Sk+1 Sk+1
 
Sk
= δk + ρk (1 + δk ) Here Sk + xk+1 = Sk + 1
Sk+1

Since Sk < Sk+1 and |δk | ≤ ϵ

|ρk+1 | ≤ ϵ + ρk (1 + ϵ)
= ϵ + θ(ρk ) and set θ = 1 + ϵ
Proof contd.

|ρk+1 | ≤ ϵ + θ(ρk )
Put k = 0, 1, 2, . . ..
We have the following successive inequalities:

|ρ0 | = 0
|ρ1 | ≤ ϵ
|ρ2 | ≤ ϵ + θϵ
|ρ3 | ≤ ϵ + θ(ϵ + θϵ)
..
.

The general result is

|ρn | ≤ ϵ + θϵ + θ2 ϵ + · · · + θn−1 ϵ

= ϵ(1 + θ + θ2 + · · · + θn−1 ).
Proof contd.

θn − 1
 
|ρn | ≤ ϵ put θ = 1 + ϵ
θ−1

(1 + ϵ)n − 1
=ϵ
ϵ
= (1 + ϵ)n − 1
   
n n 2
=1+ ϵ+ ϵ + · · · + ϵn − 1 (by the binomial therom)
1 2
= nϵ + o(ϵ2 )
≈ nϵ

□
Convergence

Definition
The sequence {x n } converges to the value L provided

lim x n = L
n→∞

or, equivalently

lim |x n − L| = 0
n→∞

Type of Measure of Convergence: There are two measure of

convergence.(Related to Speed)
1. Order of convergence
2. Rate of Convergence
Order Of Convergence

Example
1
cos x − 1 + x 2
f (x) = 2
x4
What is the limit of f(x) as x → 0 ?

Solution:
1
cos x − 1 + x 2
f (x) = 2 = 1 − 1 x 2 cos ζ
x 4 24 720
for some ζ between 0 and x.
Order Of Convergence

Solution Contd.
1
cos x − 1 + x 2
2 − 1 = 1 |x 2 cos ζ| ≤ 1 |x 2 |
x 4 24 720 720

1
it follows that lim f (x) = and the rate of convergence is
n→∞ 24
O(x 2 ).
□
Note: Let {pn } → p and en = pn − p then Rate of convergence
deal with pn and p while Order of convergence deal with successive
error value
Big O Notation
▶ Big O notation is a mathematical concept used to describe
the asymptotic behavior of functions.
▶ It classifies functions according to their growth rates and is
widely used in calculus, numerical analysis, and computer
science.
Definition: A function f (x) is said to be O(g (x)) (read as “big
O” of g (x)) if there exist constants C > 0 and x0 such that:

|f (x)| ≤ C · |g (x)| for all x ≥ x0 .

▶ Algorithm Analysis: Big O is used to describe the time or

space complexity of algorithms.
▶ Example: A sorting algorithm with time complexity O(n2 )
means the runtime grows quadratically with input size n.
▶ Approximation: In numerical analysis, big O describes the
error behavior of approximations.
3
▶ Example: The Taylor expansion sin(x) = x − x6 + O(x 5 ) shows
the error is bounded by a term proportional to x 5 for small x.
Understanding of Big O

▶ Growth Comparison: Big O measures how the magnitude of

f (x) compares to g (x) as x → ∞.
▶ Upper Bound: It represents an asymptotic upper bound on
the growth rate of f (x), ignoring constant factors and
lower-order terms.
1. Suppose f (x) = 3x 2 + 5x + 7. The dominant term as x → ∞
is 3x 2 . Therefore, f (x) is O(x 2 ), because for large x,
|f (x)| ≤ C · |x 2 | with C ≥ 3.
2. For f (x) = sin(x), f (x) is O(1), because | sin(x)| ≤ 1 for all x.
Properties

▶ Additivity: If f (x) = O(g (x)) and h(x) = O(g (x)), then

f (x) + h(x) = O(g (x)).
▶ Multiplication by Constants: If f (x) = O(g (x)), then
c · f (x) = O(g (x)) for any constant c.
▶ Transitivity: If f (x) = O(g (x)) and g (x) = O(h(x)), then
f (x) = O(h(x)).
Order Of Convergence
Definition (Order of convergence)
Let {pn } be a sequence that converges to a number p. Let
en = pn − p for n ≥ 0. If there exists positive constant λ and α
such that
|pn+1 − p| |en+1 |
lim α
= lim =λ
n→∞ |pn − p| n→∞ |en |α

then {pn } is said to converge to p of order ′ α′ with asymptotic

error constant ′ λ′

Remark 1: A sequence that converges of order ′ α′ , the error

satisfies the asymptotic relation |en+1 | ≈ λ|en |α .
Remark 2:
▶ α = 1 : Linear Convergence
▶ α = 2 : Quadratic Convergence
▶ α = 3 : Cubic Convergence
Comparison between Linear, Quadratic, and Cubic order of
convergence

Let each method has an asymptotic error constant as λ = 0.5 and

error in initial approximation e0 = 1
Approx Linear Quadratic Cubic
(|en+1 | ≈ 0.5|en |) (|en+1 | ≈ 0.5|en |2 ) (|en+1 | ≈ 0.5|en |3 )
|e1 | 0.5 0.5 0.5
|e2 | 0.25 0.125 0.0625
|e3 | 0.125 7.185 × 10−3 1.2207 × 10−4
|e4 | 0.0625 3.0518 × 10−5 9.0949 × 10−13
|e5 | 0.03125 4.6566 × 10−10 3.7616 × 10−37

Table 1: Error approximations for different convergence rates

asymptotic error constant

Definition
The asymptotic error constant, denoted C , appears in the error
expression for iterative methods when analyzing the behavior of
errors in consecutive iterations. For an iterative sequence {xk }
converging to a solution x ∗ , the error ek = |xk − x ∗ | satisfies:

ek+1 ≈ C · ekp ,

where:
▶ ek = |xk − x ∗ | is the error at the k-th iteration,
▶ p is the order of convergence,
▶ C is the asymptotic error constant.
Interpretation
▶ Error Scaling: The constant C quantifies how much the error
is scaled during each iteration. Smaller values of C imply
faster error reduction.
▶ Relationship to p: While p indicates the overall speed of
convergence (e.g., linear, quadratic), C gives the
proportionality factor governing the actual size of the errors.
1. Linear Convergence (p = 1):

ek+1 ≈ C · ek .

Here, C directly determines how quickly the error reduces. For

example, if C = 0.5, the error halves with each iteration.
2. Quadratic Convergence (p = 2):

ek+1 ≈ C · ek2 .

The error decreases more rapidly, but C influences the speed

of this quadratic reduction.
How it helps

▶ Algorithm Efficiency: Understanding C helps compare

iterative methods with the same order of convergence. A
method with a smaller C will perform better in practice.
▶ Stopping Criteria: Knowing C aids in estimating the number
of iterations required to achieve a desired error tolerance.
Determine The Order Of Convergence

Recursive scheme  
1 a
xn+1 = xn +
2 xn
is used to compute an approximation to the square root of positive
real number a.
Order of convergence = ?
√
Error at the (n + 1)th term = xn+1 − a
√
Error at the nth term = xn − a

√ √
 
1 a
xn+1 − a = xn + − a
2 xn
√
√ xn 2 − 2xn a + a
xn+1 − a =
2xn
Determine The Order Of Convergence

√
√ (xn − a)2
xn+1 − a =
2xn
√
xn+1 − a 1
√ 2 =
(xn − a) 2xn
taking lim on both sides.
n→∞
√
|xn+1 − a| 1 1 √
lim √ 2 = lim = √ (since xn → a)
n→∞ |xn − a| n→∞ 2xn 2 a

Order of convergence = 2
1
Asymptotic error constant = √
2 a
Exercise:

1 
The sequence xn+1 = xn + x9n converges to 3 (Take a = 9).
2
en
Compute en and for n = 1, 2, 3, 4, 5 and 6.
|en−1 |2
Rate of Convergence

Definition
Let the sequence {xn } converges to a number L. If there exists a
sequence {βn } that converges to zero and a positive constant λ,
independent of n, such that

|xn − L| ≤ λ|βn |

for all sufficiently large value of n, then {xn } is said to converge to

L with Rate of Convergence O(βn ) .

The sequence {βn } is taken to be of the form 1/na or 1/an for

some positive constant a.
Comparing Rates of Convergence
n+3 2n + 3
Consider the sequences, an = and bn = n
n+7 2 +7
n an bn
1 0.5000000000 0.5555555556
2 0.5555555556 0.6363636364
3 0.6000000000 0.7333333333
4 0.6363636364 0.8260869565
5 0.6666666667 0.6666666667
6 0.6923076923 0.9436619718
7 0.7142857143 0.9703703704
8 0.7333333333 0.9847908745
9 0.7500000000 0.9922928709
Table 2: Corresponding Terms in Two Sequences that Converge to 1
Comparing Rates of Convergence

n+3
an =
n+7

so lim an = 1
n→∞

n+3 4 1
now, |an − 1| = −1 = ≤ 4.
n+7 n+7 n

1
Hence, we take λ = 4 amd β = in the definition of rate of
n
convergence. It follows that the sequence {an } converges to 1 with
rate of convergence O( n1 )
Comparing Rates of Convergence

2n + 3
bn =
2n + 7
calculate the rate of convergence and λ.
Comparing Rates of Convergence

2n + 3
bn =
2n + 7
calculate the rate of convergence and λ.

so lim bn = 1
n→∞

2n + 3 4 1
now, |bn − 1| = −1 = n ≤ 4. n
2n + 7 2 +7 2
Comparing Rates of Convergence

2n + 3
bn =
2n + 7
calculate the rate of convergence and λ.

so lim bn = 1
n→∞

2n + 3 4 1
now, |bn − 1| = −1 = n ≤ 4. n
2n + 7 2 +7 2

1
Hence, we take λ = 4 amd β = in the definition of rate of
2n
convergence. It follows that sequence {bn } converges to 1 with
rate of convergence O( 21n )
Rate of Convergence of a Function

Definition
Let f be a function defined on [a, b] ∋ x = 0 and suppose that
lim f (x) = L. If there exists a function g for which lim g (x) = 0
x→0 x→0
and a positive constant k such that

|f (x) − L| ≤ k|g (x)|

for sufficiently large value of x, then f (x) is said to converge to L

with rate of convergence O(g (x)).

Example
1
cos x − 1 + x 2
Consider the function f (x) = 2 . Find the lim f (x)
x4 x→0
and rate of convergence of f .
solution
We know that
1 1 1 6
cos x = 1 − x 2 + x 4 − x cos ζ
2 24 720
for some ζ between 0 and x. Hence,

cos x − 1 + 21 x 2 1 1 2
4
= − x cos ζ.
x 24 720
Finally,

cos x − 1 + 12 x 2 1 1 2 1 2
4
− = |x cos ζ| ≤ |x |,
x 24 720 720

1 1
Hence, lim f (x) = 24 , we take k = 720 and g (x) = x 2 in the
n→∞
definition of rate of convergence. It follows that rate of
convergence of f (x) is O(x 2 ). □