MA 204 Numerical Methods

Dr. Debopriya Mukherjee

Lecture-1

January 9, 2024
Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence, solution of a
system of nonlinear equations.
Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence, solution of a
system of nonlinear equations.
Interpolation by polynomials, divided differences, error of the
interpolating polynomial, piecewise linear and cubic spline
interpolation.
Motivation

Nonlinearity
One of the most frequent problem in engineering and science is to
find the root(s) of a non-linear equation

f (x) = 0. (1)

Here,
f : [a, b] → R is a nonlinear function in x;
f ∈ C 1 [a, b];
Roots are isolated.
Root of the equation

Definition 1
Given a nonlinear function f : [a, b] → R, find a value of r for
which f (r ) = 0. Such a solution value for r is called a root of the
equation
f (x) = 0,
or zero of the function f .
Root of the equation

Definition 1
Given a nonlinear function f : [a, b] → R, find a value of r for
which f (r ) = 0. Such a solution value for r is called a root of the
equation
f (x) = 0,
or zero of the function f .

Problem
Given f : [a, b] → R continuous. Find r ∈ R such that f (r ) = 0.
Root of the equation

Definition 1
Given a nonlinear function f : [a, b] → R, find a value of r for
which f (r ) = 0. Such a solution value for r is called a root of the
equation
f (x) = 0,
or zero of the function f .

Problem
Given f : [a, b] → R continuous. Find r ∈ R such that f (r ) = 0.

Approximation to a root
A point x ? ∈ R such that
|r − x ? | is very small, and
f (x ? ) is very close to 0.
Examples

Example 2
f (x) = x 2 + 5x + 6
Examples

Example 2
f (x) = x 2 + 5x + 6

f (x) = 0 =⇒ x 2 + 5x + 6 = 0 =⇒ (x + 2)(x + 3) = 0
=⇒ r1 = −2, r1 = −3.

Roots are not unique.

Examples

Example 2
f (x) = x 2 + 5x + 6

f (x) = 0 =⇒ x 2 + 5x + 6 = 0 =⇒ (x + 2)(x + 3) = 0
=⇒ r1 = −2, r1 = −3.

Roots are not unique.

Example 3
f (x) = x 2 + 4x + 10
Examples

Example 2
f (x) = x 2 + 5x + 6

f (x) = 0 =⇒ x 2 + 5x + 6 = 0 =⇒ (x + 2)(x + 3) = 0
=⇒ r1 = −2, r1 = −3.

Roots are not unique.

Example 3
f (x) = x 2 + 4x + 10

f (x) = 0 =⇒ x 2 + 4x + 10 = 0 =⇒ (x + 2)2 + 6 = 0.

As (x + 2)2 + 6 ≥ 6 ∀ x ∈ R. So, f (x) = 0 has no real roots.

Overview of Chapter

Example 4
√
f (x) = x 2 + cos(x) + e x + x +1

The equation f (x) = 0 might have real root/roots but the point is
that it is very difficult to find the analytic expression of x.
Types of Iterative Methods

In this course, we find the root/root(s) upto some precission.

1 Closed Domain Methods (Bracketing Methods)
Types of Iterative Methods

In this course, we find the root/root(s) upto some precission.

1 Closed Domain Methods (Bracketing Methods)
Bisection method
Regular Falsi method (Method of False position)
Types of Iterative Methods

In this course, we find the root/root(s) upto some precission.

1 Closed Domain Methods (Bracketing Methods)
Bisection method
Regular Falsi method (Method of False position)
Advantages: Always converges
Disadvantages: Locating the root initially
2 Closed Domain Methods (Bracketing Methods)
Types of Iterative Methods

In this course, we find the root/root(s) upto some precission.

1 Closed Domain Methods (Bracketing Methods)
Bisection method
Regular Falsi method (Method of False position)
Advantages: Always converges
Disadvantages: Locating the root initially
2 Closed Domain Methods (Bracketing Methods)
Secant method
Fixed point theorem
Newton’s method (Newton Raphson method)
Types of Iterative Methods

In this course, we find the root/root(s) upto some precission.

1 Closed Domain Methods (Bracketing Methods)
Bisection method
Regular Falsi method (Method of False position)
Advantages: Always converges
Disadvantages: Locating the root initially
2 Closed Domain Methods (Bracketing Methods)
Secant method
Fixed point theorem
Newton’s method (Newton Raphson method)
Advantages: No need to locate the root initially
Disadvantages: May not converge
For each of the method, we study the following:
Description of the method/ Basic idea
For each of the method, we study the following:
Description of the method/ Basic idea
Error analysis of the iteration and convergence
For each of the method, we study the following:
Description of the method/ Basic idea
Error analysis of the iteration and convergence
Rate/Order of convergence
For each of the method, we study the following:
Description of the method/ Basic idea
Error analysis of the iteration and convergence
Rate/Order of convergence
Geometry of the method (iteration) process
For each of the method, we study the following:
Description of the method/ Basic idea
Error analysis of the iteration and convergence
Rate/Order of convergence
Geometry of the method (iteration) process
Computational Scheme
For each of the method, we study the following:
Description of the method/ Basic idea
Error analysis of the iteration and convergence
Rate/Order of convergence
Geometry of the method (iteration) process
Computational Scheme
Application and example
Bisection Method: Basic idea

This method is based on Intermediate Value Theorem.

Theorem
If f ∈ C [a, b] and K is any number between f (a) and f (b), then
there exists c ∈ (a, b) such that f (c) = K .
Bisection Method: Basic idea

This method is based on Intermediate Value Theorem.

Theorem
If f ∈ C [a, b] and K is any number between f (a) and f (b), then
there exists c ∈ (a, b) such that f (c) = K .

Bisection Method
Suppose that f (x) is continuous on given interval [a, b].
The function f satisfies the property f (a)f (b) < 0 with
f (a) 6= 0 and f (b) 6= 0.
By Intermediate Value Theorem, there exists a number c such
that f (c) = 0.
Bisection Method: Description of the method

The Bisection method consists of the following steps:

Step 1: Given an initial interval [a0 , b0 ], set n = 0.
(an + bn )
Step 2: Define cn = , the mid-point of interval [an , bn ].
2
Step 3: If f (cn ) = 0, then x ? = cn is the root.
If f (cn ) 6= 0, then either

f (an )f (cn ) < 0 or f (an )f (cn ) > 0.

If f (an )f (cn ) < 0, then an+1 = an , bn+1 = cn and the root

x ? ∈ [an+1 , bn+1 ].
If f (an )f (cn ) > 0, then f (bn )f (cn ) < 0, this implies an+1 = cn ,
bn+1 = bn and the root x ? ∈ [an+1 , bn+1 ].
Bisection Method

Step 4: Repeat
Step 5: If the root is not achieved in Step 3, then, find the length of
new reduced interval [an+1 , bn+1 ]. If the length of the interval
bn+1 − an+1 is less than a recommended positive number ε,
then take the mid-point of this interval
(x ? = (bn+1 − an+1 )/2) as the approximate root of the
equation f (x) = 0, otherwise go to Step 2.
Convergence and error in Bisection Method

Let [a0 , b0 ] = [a, b] be the initial interval with f (a)f (b) < 0.
Define the approximate root as cn = (an + bn )/2. Then, there
exists a root x ? ∈ [a, b] such that

1
|cn − x ? | ≤ ( )n (b − a). (2)
2
Moreover, to achieve the accuracy of |cn − x ? | ≤ ε, it is sufficient
to take
|b − a| log (|b − a|) − log (ε)
n
≤ ε i.e. n ≥ . (3)
2 log 2
Error analysis in Bisection Method

1
bn+1 − an+1 = (bn − an ), n ≥ 1. (4)
2

1
bn − an = (bn−1 − an−1 )
2
1 1
= 2 (bn−2 − an−2 ) = n−1 (b1 − a1 ). (5)
2 2

1
|cn − x ? | ≤ cn − an = bn − cn = (bn − an )
2
1 n 1 n
= ( ) (b1 − a1 ) = ( ) (b − a). (6)
2 2
1
Therefore, |cn − x ? | ≤ ( )n (b − a). This implies that the iterates
2
cn converge to x ? as n → ∞.
How many iterations?

Our goal is to have |cn − x ? | ≤ ε. This will be satisfied if

1 b−a
( )n (b − a) ≤ ε =⇒ 2n ≥
2 ε
b−a
=⇒ nlog10 2 ≥ log10 ( )
ε
log (|b − a|) − log (ε)
=⇒ n ≥ . (7)
log 2
Stop criteria

First select some tolerance ε > 0.

1 Small enough interval i.e., bn − an ≤ ε;
2 Small enough difference of consecutive approximations i.e.,

|cn+1 − cn |
|cn+1 − cn | ≤ ε or ≤ ε;
|cn |

3 Small enough functional value |f (cn )| ≤ ε;

4 Maximum number of iterations;
5 Any combination of the above.
Pros and Cons

Pros
1 This method is very easy to understand.
2 The sequence forms a cauchy sequence, and always converge
to a solution.
3 It is often used as a starter for the more efficient methods.

Cons
1 This method is relatively slow to converge.

2 Choosing a guess close to the root may result in requiring

many iterations to converge.
MA 204 Numerical Methods

Dr. Debopriya Mukherjee

Lecture-2

January 11, 2024

Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence, solution of a
system of nonlinear equations.
Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence, solution of a
system of nonlinear equations.
Interpolation by polynomials, divided differences, error of the
interpolating polynomial, piecewise linear and cubic spline
interpolation.
Motivation

Nonlinearity
One of the most frequent problem in engineering and science is to
find the root(s) of a non-linear equation

f (x) = 0. (1)

Here,
f : [a, b] → R is a nonlinear function in x;
f ∈ C 1 [a, b];
Roots are isolated.
Root of the equation

Definition 1
Given a nonlinear function f : [a, b] → R, find a value of r for
which f (r ) = 0. Such a solution value for r is called a root of the
equation
f (x) = 0,
or zero of the function f .
Root of the equation

Definition 1
Given a nonlinear function f : [a, b] → R, find a value of r for
which f (r ) = 0. Such a solution value for r is called a root of the
equation
f (x) = 0,
or zero of the function f .

Problem
Given f : [a, b] → R continuous. Find r ∈ R such that f (r ) = 0.
Root of the equation

Definition 1
Given a nonlinear function f : [a, b] → R, find a value of r for
which f (r ) = 0. Such a solution value for r is called a root of the
equation
f (x) = 0,
or zero of the function f .

Problem
Given f : [a, b] → R continuous. Find r ∈ R such that f (r ) = 0.

Approximation to a root
A point x ? ∈ R such that
|r − x ? | is very small, and
f (x ? ) is very close to 0.
Types of Iterative Methods

In this course, we find the root/root(s) upto some precission.

1 Open Domain Methods (Bracketing Methods)
Types of Iterative Methods

In this course, we find the root/root(s) upto some precission.

1 Open Domain Methods (Bracketing Methods)
Bisection method
Regular Falsi method (Method of False position)
Types of Iterative Methods

In this course, we find the root/root(s) upto some precission.

1 Open Domain Methods (Bracketing Methods)
Bisection method
Regular Falsi method (Method of False position)
Advantages: Always converges
Disadvantages: Locating the root initially
2 Closed Domain Methods (Non- Bracketing Methods)
Types of Iterative Methods

In this course, we find the root/root(s) upto some precission.

1 Open Domain Methods (Bracketing Methods)
Bisection method
Regular Falsi method (Method of False position)
Advantages: Always converges
Disadvantages: Locating the root initially
2 Closed Domain Methods (Non- Bracketing Methods)
Secant method
Fixed point theorem
Newton’s method (Newton Raphson method)
Types of Iterative Methods

In this course, we find the root/root(s) upto some precission.

1 Open Domain Methods (Bracketing Methods)
Bisection method
Regular Falsi method (Method of False position)
Advantages: Always converges
Disadvantages: Locating the root initially
2 Closed Domain Methods (Non- Bracketing Methods)
Secant method
Fixed point theorem
Newton’s method (Newton Raphson method)
Advantages: No need to locate the root initially
Disadvantages: May not converge
For each of the method, we study the following:
Description of the method/ Basic idea
For each of the method, we study the following:
Description of the method/ Basic idea
Error analysis of the iteration and convergence
For each of the method, we study the following:
Description of the method/ Basic idea
Error analysis of the iteration and convergence
Rate/Order of convergence
For each of the method, we study the following:
Description of the method/ Basic idea
Error analysis of the iteration and convergence
Rate/Order of convergence
Geometry of the method (iteration) process
For each of the method, we study the following:
Description of the method/ Basic idea
Error analysis of the iteration and convergence
Rate/Order of convergence
Geometry of the method (iteration) process
Computational Scheme
For each of the method, we study the following:
Description of the method/ Basic idea
Error analysis of the iteration and convergence
Rate/Order of convergence
Geometry of the method (iteration) process
Computational Scheme
Application and example
Secant Method: Basic idea

This method is based on Mean Value Theorem.

Assume that two initial guesses to α are known. Let these be
x0 and x1 . They may occur on opposite side of α or on the
same side of α.
Secant Method: Basic idea

This method is based on Mean Value Theorem.

Assume that two initial guesses to α are known. Let these be
x0 and x1 . They may occur on opposite side of α or on the
same side of α.
The two points (x0 , f (x0 )) and (x1 , f (x1 )) on the graph
determine a straight line called a secant line.
Secant Method: Basic idea

This method is based on Mean Value Theorem.

Assume that two initial guesses to α are known. Let these be
x0 and x1 . They may occur on opposite side of α or on the
same side of α.
The two points (x0 , f (x0 )) and (x1 , f (x1 )) on the graph
determine a straight line called a secant line.
Equation of the secant line

f (x1 ) − f (x0 )
y − f (x1 ) = (x − x1 ) (2)
x1 − x0
Secant Method: Basic idea

This method is based on Mean Value Theorem.

The intersection of this line with x-axis is the next
approximation to α. Let us denote it by x2 .
Secant Method: Basic idea

This method is based on Mean Value Theorem.

The intersection of this line with x-axis is the next
approximation to α. Let us denote it by x2 .
The root x2 or (x2 , 0) lies on the line (2). So, we have
Secant Method: Basic idea

This method is based on Mean Value Theorem.

The intersection of this line with x-axis is the next
approximation to α. Let us denote it by x2 .
The root x2 or (x2 , 0) lies on the line (2). So, we have

f (x1 ) − f (x0 )
0 − f (x1 ) = (x2 − x1 )
x1 − x0
f (x1 ) − f (x0 )
=⇒ x2 = x1 − (x2 − x1 ) . (3)
x1 − x0
Secant Method: Basic idea

This method is based on Mean Value Theorem.

The intersection of this line with x-axis is the next
approximation to α. Let us denote it by x2 .
The root x2 or (x2 , 0) lies on the line (2). So, we have

f (x1 ) − f (x0 )
0 − f (x1 ) = (x2 − x1 )
x1 − x0
f (x1 ) − f (x0 )
=⇒ x2 = x1 − (x2 − x1 ) . (3)
x1 − x0

Having found x2 , we can drop x0 and use x1 , x2 as a new set

of approximate value for α. This leads to an improved value
x3 ; and this process can be continued indefinitely.
Secant Method: General Iteration

The general iteration formula for the secant method is

xn − xn−1
xn+1 = xn − f (xn ) n ≥ 1. (4)
f (xn ) − f (xn−1 )
Secant Method: General Iteration

The general iteration formula for the secant method is

xn − xn−1
xn+1 = xn − f (xn ) n ≥ 1. (4)
f (xn ) − f (xn−1 )

The sequence of iterates does not need to converge to root of

the function. In fact it might also diverge.Then, why does
one use secant method instead of bisection method,
which gives the security of convergence?
Secant Method: General Iteration

The general iteration formula for the secant method is

xn − xn−1
xn+1 = xn − f (xn ) n ≥ 1. (4)
f (xn ) − f (xn−1 )

The sequence of iterates does not need to converge to root of

the function. In fact it might also diverge.Then, why does
one use secant method instead of bisection method,
which gives the security of convergence?
It is called a two-point method, since two approximation
values are needed to obtain an improved value.
Secant Method: General Iteration

The general iteration formula for the secant method is

xn − xn−1
xn+1 = xn − f (xn ) n ≥ 1. (4)
f (xn ) − f (xn−1 )

The sequence of iterates does not need to converge to root of

the function. In fact it might also diverge.Then, why does
one use secant method instead of bisection method,
which gives the security of convergence?
It is called a two-point method, since two approximation
values are needed to obtain an improved value.
The Bisection method is also a two-point method, but the
Secant method will almost always converge faster than
bisection.
Note that only one function evaluation is needed per step for
the Secant method after x2 has been determined. In contrast,
each step of Newton’s method requires an evaluation of both
the function and its derivative.
Note that only one function evaluation is needed per step for
the Secant method after x2 has been determined. In contrast,
each step of Newton’s method requires an evaluation of both
the function and its derivative.
Newton’s method or the Secant method is often used to refine
an answer obtained by another technique, such as the
bisection method, since these methods requires good first
approximation but generally give rapid convergence.
How fast is the convergence?

Definition 2
Let {xn }n≥1 be a sequence that converges to α. If positive
constants λ and p exist with

|xn+1 − α|
lim = λ,
n→∞ |xn − α|p

then {xn }n≥1 is said to converge to α of order p, with

assymptotic error constant λ. If p = 1, the method is called
linear. If p = 2, the method is called quadratic.
How fast is the convergence?

Can we find the exponent p such that

|xn+1 − α| ≈ |xn − α|p ? (5)

1 √
Answer: p = (1 + 5) ≈ 1.62. This is called super linear
2
convergence (1 < p < 2).
Error analysis of the iteration and convergence

The general iteration formula for the secant method is

xn − xn−1
xn+1 = xn − f (xn ) n ≥ 1. (6)
f (xn ) − f (xn−1 )
Error analysis of the iteration and convergence

The general iteration formula for the secant method is

xn − xn−1
xn+1 = xn − f (xn ) n ≥ 1. (6)
f (xn ) − f (xn−1 )

Let εn = xn − α and εn+1 = xn+1 − α. So, εn and εn+1 denote

the errors in the root at the nth and (n+1)th iterations.
Error analysis of the iteration and convergence

The general iteration formula for the secant method is

xn − xn−1
xn+1 = xn − f (xn ) n ≥ 1. (6)
f (xn ) − f (xn−1 )

Let εn = xn − α and εn+1 = xn+1 − α. So, εn and εn+1 denote

the errors in the root at the nth and (n+1)th iterations.
(6) =⇒

f (α + εn )(εn+1 − εn )
εn+1 = εn − (7)
f (α + εn ) − f (α + εn−1 )
Error analysis of the iteration and convergence

Assume that f is twice differentiable and f 0 (α), f 00 (α) 6= 0. By

Taylor’s formula (with very small ε)

ε2 00
f (α + ε) = f (α) + εf 0 (α) + f (α) + R2 (ε).
2
Error analysis of the iteration and convergence

Assume that f is twice differentiable and f 0 (α), f 00 (α) 6= 0. By

Taylor’s formula (with very small ε)

ε2 00
f (α + ε) = f (α) + εf 0 (α) + f (α) + R2 (ε).
2
Now, f (α) = 0, and ε is very small, and R2 (ε) is the
remainder term. R2 (ε) vanishes as ε → 0 at a faster rate than
ε2 . Therefore,

ε2 00
f (α + ε) ≈ εf 0 (α) + f (α).
2
Error analysis of the iteration and convergence

f 00 (α)
Let M = .
2f 0 (α)
 
f (α + εn ) ≈ εn f 0 (α) 1 + εn M .

f 00 (α)
εn+1 ≈ εn−1 εn (8)
2f 0 (α)

(8) tells us that, as n → ∞, the error tends to zero faster

than a linear function but not quadratically!
Error Estimate
By Mean Value Theorem,

f (α) − f (xn ) = f 0 (cn )(α − xn ) (9)

where cn lies between xn and α. So, if xn → α, then cn ≈ xn for

large n, and we have

f (xn )
α − xn ≈ −
f 0 (cn )
f (xn )
≈− 0
f (xn )
xn − xn−1
≈ −f (xn )
f (xn ) − f (xn−1 )
≈ xn+1 − xn .

Thus, α − xn ≈ xn+1 − xn .
MA 204 Numerical Methods

Dr. Debopriya Mukherjee

Lecture-3

January 11, 2024

Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence, solution of a
system of nonlinear equations.
Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence, solution of a
system of nonlinear equations.
Interpolation by polynomials, divided differences, error of the
interpolating polynomial, piecewise linear and cubic spline
interpolation.
Newton Raphson Method
Order of Convergence of Secant method: 1.62
Newton Raphson Method
Order of Convergence of Secant method: 1.62
Can this method be modified to have a quadratic
convergence?
Newton Raphson Method
Order of Convergence of Secant method: 1.62
Can this method be modified to have a quadratic
convergence? How?
Newton Raphson Method
Order of Convergence of Secant method: 1.62
Can this method be modified to have a quadratic
convergence? How?
In Secant method, if the iterative sequence converges, then
As n increases, xn−1 approaches xn .
f (xn ) − f (xn−1 )
=⇒ f 0 (xn ) ≈ , as n increases
xn − xn−1
Newton Raphson Method
Order of Convergence of Secant method: 1.62
Can this method be modified to have a quadratic
convergence? How?
In Secant method, if the iterative sequence converges, then
As n increases, xn−1 approaches xn .
f (xn ) − f (xn−1 )
=⇒ f 0 (xn ) ≈ , as n increases
xn − xn−1

Recall the Secant method is

xn − xn−1
xn+1 = xn − f (xn ) ,
f (xn ) − f (xn−1 )
Newton Raphson Method
Order of Convergence of Secant method: 1.62
Can this method be modified to have a quadratic
convergence? How?
In Secant method, if the iterative sequence converges, then
As n increases, xn−1 approaches xn .
f (xn ) − f (xn−1 )
=⇒ f 0 (xn ) ≈ , as n increases
xn − xn−1

Recall the Secant method is

xn − xn−1
xn+1 = xn − f (xn ) ,
f (xn ) − f (xn−1 )

The iterative procedure (given below) is called the Newton

Raphson’s method.
f (xn )
xn+1 = xn − 0 , n = 0, 1, 2, · · · .
f (xn )
History

In numerical analysis, Newton’s method, also known as the

Newton–Raphson method, named after Isaac Newton and
Joseph Raphson, is a root-finding algorithm which produces
successively better approximations to the roots (or zeroes) of
a real-valued function.
History

In numerical analysis, Newton’s method, also known as the

Newton–Raphson method, named after Isaac Newton and
Joseph Raphson, is a root-finding algorithm which produces
successively better approximations to the roots (or zeroes) of
a real-valued function.
The most basic version starts with a real-valued function f , its
derivative f , and an initial guess x0 for a root of f .
History

In numerical analysis, Newton’s method, also known as the

Newton–Raphson method, named after Isaac Newton and
Joseph Raphson, is a root-finding algorithm which produces
successively better approximations to the roots (or zeroes) of
a real-valued function.
The most basic version starts with a real-valued function f , its
derivative f , and an initial guess x0 for a root of f .
This is one of the most powerful methods for solving a
root-finding problem. There are many ways of introducing
Newton’s method.
Method Description
Consider the sample graph of y = f (x). Let the estimate of
the root α be x0 (initial guess).
Method Description
Consider the sample graph of y = f (x). Let the estimate of
the root α be x0 (initial guess).
To improve on this estimate, consider the straight line that is
tangent to the graph at (x0 , f (x0 )).
Method Description
Consider the sample graph of y = f (x). Let the estimate of
the root α be x0 (initial guess).
To improve on this estimate, consider the straight line that is
tangent to the graph at (x0 , f (x0 )).
If x0 is near α, the tangent line at x0 cuts the x-axis at x1 ,
which is near to α.
Method Description
Consider the sample graph of y = f (x). Let the estimate of
the root α be x0 (initial guess).
To improve on this estimate, consider the straight line that is
tangent to the graph at (x0 , f (x0 )).
If x0 is near α, the tangent line at x0 cuts the x-axis at x1 ,
which is near to α.
To find a formula for x1 , consider the equation of tangent to
the graph of y = f (x) at (x0 , f (x0 )). It is simply the graph of
y = f (x0 ) + f 0 (x0 )(x − x0 ).
Method Description
Consider the sample graph of y = f (x). Let the estimate of
the root α be x0 (initial guess).
To improve on this estimate, consider the straight line that is
tangent to the graph at (x0 , f (x0 )).
If x0 is near α, the tangent line at x0 cuts the x-axis at x1 ,
which is near to α.
To find a formula for x1 , consider the equation of tangent to
the graph of y = f (x) at (x0 , f (x0 )). It is simply the graph of
y = f (x0 ) + f 0 (x0 )(x − x0 ).

(x1 , 0) lies on this line:

=⇒ 0 = f (x0 ) + f 0 (x0 )(x1 − x0 )
f (x0 )
=⇒ x1 = x0 − 0 .
f (x0 )
Method Description
Since x1 is expected to be an improvement over x0 as an
estimate of α, this entire procedure can be repeated with x1
as the initial guess.
Method Description
Since x1 is expected to be an improvement over x0 as an
estimate of α, this entire procedure can be repeated with x1
as the initial guess.
This leads to the new estimate
f (x1 )
x2 = x1 − .
f 0 (x1 )
Method Description
Since x1 is expected to be an improvement over x0 as an
estimate of α, this entire procedure can be repeated with x1
as the initial guess.
This leads to the new estimate
f (x1 )
x2 = x1 − .
f 0 (x1 )

Repeating this process, we obtain a sequence of numbers

x1 , x2 , · · · that we hope will approach the root α. These
numbers are called iterates, and they are defined recursively
by the following general iteration formula:
Method Description
Since x1 is expected to be an improvement over x0 as an
estimate of α, this entire procedure can be repeated with x1
as the initial guess.
This leads to the new estimate
f (x1 )
x2 = x1 − .
f 0 (x1 )

Repeating this process, we obtain a sequence of numbers

x1 , x2 , · · · that we hope will approach the root α. These
numbers are called iterates, and they are defined recursively
by the following general iteration formula:
f (xn )
xn+1 = xn − , n = 0, 1, 2, · · · (1)
f 0 (xn )
This is Newton’s method for solving f (x) = 0.
Convergence Analysis

Assume that f (x) has atleast two continuous derivatives for

all x in some interval about the root α.
Convergence Analysis

Assume that f (x) has atleast two continuous derivatives for

all x in some interval about the root α.Further assume that

f 0 (α) 6= 0 (2)
Convergence Analysis

Assume that f (x) has atleast two continuous derivatives for

all x in some interval about the root α.Further assume that

f 0 (α) 6= 0 (2)

This says that the graph of y = f (x) is not tangent to the

x-axis when the graph intersects it x = α.
Convergence Analysis

Assume that f (x) has atleast two continuous derivatives for

all x in some interval about the root α.Further assume that

f 0 (α) 6= 0 (2)

This says that the graph of y = f (x) is not tangent to the

x-axis when the graph intersects it x = α. This case when
f 0 (α) = 0 will be discussed later.
Convergence Analysis

Assume that f (x) has atleast two continuous derivatives for

all x in some interval about the root α.Further assume that

f 0 (α) 6= 0 (2)

This says that the graph of y = f (x) is not tangent to the

x-axis when the graph intersects it x = α. This case when
f 0 (α) = 0 will be discussed later.
Combining (2) with the continuity of f 0 (x) implies

f 0 (x) 6= 0 ∀ x near α.
Convergence Analysis

By Taylor’s theorem,

f (α) = f (xn + α − xn )
(α − xn )2 00
= f (xn ) + (α − xn )f 0 (xn ) + f (cn ) (3)
2
where cn is an unkown point between α and xn .
Convergence Analysis

f (xn )
Note that f (α) = 0. Using xn+1 = xn − This implies
f 0 (xn )

1
0 = f (xn ) + (α − xn )f 0 (xn ) + (α − xn )2 f 00 (cn )
2
f (xn ) 1 f 00 (cn )
=⇒ 0 = 0 + (α − xn ) + (α − xn )2 0
f (xn ) 2 f (xn )
f 00 (cn )
=⇒ 0 = xn − xn+1 + α − xn + (α − xn )2 0 (4)
f (xn )
h f 00 (c ) i
n
α − xn+1 = (α − xn )2 − 0
2f (xn )
Error Analysis

This formula says that the error in xn+1 is nearly proportional

to the square of the error in xn .
Error Analysis

This formula says that the error in xn+1 is nearly proportional

to the square of the error in xn .
When the initial error is sufficiently small, this shows that the
error in the succeeding iterates will decrease very rapidly.
When to stop iterations?

Noting that f (α) = 0, by Mean Value Theorem

f (xn ) = f (xn ) − f (α) = f 0 (ξn )(xn − α).

f (xn )
Thus, error εn = α − xn = − provided that xn is close
f 0 (xn )
to α that f 0 (xn ) ≈ f 0 (ξn ). This implies α − xn ≈ xn+1 − xn .
When to stop iterations?

Noting that f (α) = 0, by Mean Value Theorem

f (xn ) = f (xn ) − f (α) = f 0 (ξn )(xn − α).

f (xn )
Thus, error εn = α − xn = − provided that xn is close
f 0 (xn )
to α that f 0 (xn ) ≈ f 0 (ξn ). This implies α − xn ≈ xn+1 − xn .
This is the standard error estimation formula for Newton’s
method and it is usually fairly accurate. However, this formula
is not valid if f 0 (α) = 0.
Multiple Root

The zero of the function f is said to be of multiplicity m if

f (x) = (x − α)m g (x)

for some continuous function g with g (α) 6= 0, m is a positive

integer.
Multiple Root

The zero of the function f is said to be of multiplicity m if

f (x) = (x − α)m g (x)

for some continuous function g with g (α) 6= 0, m is a positive

integer.
If we assume that f is sufficiently differentiable, an equivalent
definition is that

f (α) = f 0 (α) = · · · = f (m−1) (α) = 0, f (m) (α) 6= 0.

Multiple Root

The zero of the function f is said to be of multiplicity m if

f (x) = (x − α)m g (x)

for some continuous function g with g (α) 6= 0, m is a positive

integer.
If we assume that f is sufficiently differentiable, an equivalent
definition is that

f (α) = f 0 (α) = · · · = f (m−1) (α) = 0, f (m) (α) 6= 0.

A zero of multiplicity 1 is called a simple root or a simple zero.

Remedy
One method of handling the problem of multiple roots of a
function f is to define
f (x)
µ(x) = 0 .
f (x)
Remedy
One method of handling the problem of multiple roots of a
function f is to define
f (x)
µ(x) = 0 .
f (x)

If α is a zero of f of multiplicity m. Then, one can write

f (x) = (x − α)m g (x), g (α) 6= 0.
Remedy
One method of handling the problem of multiple roots of a
function f is to define
f (x)
µ(x) = 0 .
f (x)

If α is a zero of f of multiplicity m. Then, one can write

f (x) = (x − α)m g (x), g (α) 6= 0.

This implies
(x − α)m g (x)
µ(x) =
m(x − α)m−1 g (x) + (x − α)m g 0 (x)
g (x)
= (x − α)
mg (x) + (x − α)g 0 (x)
also has a zero at α. However, g (α) 6= 0.
Newton’s method for multiple roots

1
Thus, µ0 (α) = 6= 0, hence α is called a simple zero of µ.
m
Newton’s method can be applied to µ(x) to give

f (xn )f 0 (xn )
xn+1 = xn −
[f 0 (xn )]2 − f (xn )f 00 (xn )

This is called Newton’s modified method. This has quadratic

convergence regardless of multiplicity of the zeros of f.
For a simple zero, the original Newton’s method requires
significantly low computations.
Newton versus Secant

Note that only one function evaluation is needed per step for
the Secant method after x2 has been determined. In contrast,
each step of Newton’s method requires an evaluation of both
the function and its derivative.
Newton versus Secant

Note that only one function evaluation is needed per step for
the Secant method after x2 has been determined. In contrast,
each step of Newton’s method requires an evaluation of both
the function and its derivative.
Newton’s method or the Secant method is often used to refine
an answer obtained by another technique, such as the
bisection method, since these methods requires good first
approximation but generally give rapid convergence.
MA 204 Numerical Methods

Dr. Debopriya Mukherjee

Lecture-4

January 17, 2024

Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence.
Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence.
Interpolation by polynomials, divided differences, error of the
interpolating polynomial, piecewise linear and cubic spline
interpolation.
Polynomial Interpolation
Polynomial Interpolation

Problem Description
Given, (n + 1) points, say (xi , yi ) where i = 0, 1, 2, · · · , n with
distinct xi , not necessarily sorted, we want to find a polynomial of
degree n,
Polynomial Interpolation

Problem Description
Given, (n + 1) points, say (xi , yi ) where i = 0, 1, 2, · · · , n with
distinct xi , not necessarily sorted, we want to find a polynomial of
degree n,

Pn (x) = an x n + an−1 x n−1 + · · · + a1 x + a0

such that it interpolates these points, i.e.,

Pn (xi ) = yi , i = 0, 1, 2, · · · , n.
Polynomial Interpolation

Problem Description
Given, (n + 1) points, say (xi , yi ) where i = 0, 1, 2, · · · , n with
distinct xi , not necessarily sorted, we want to find a polynomial of
degree n,

Pn (x) = an x n + an−1 x n−1 + · · · + a1 x + a0

such that it interpolates these points, i.e.,

Pn (xi ) = yi , i = 0, 1, 2, · · · , n.

Our goal: is to determine the coefficients an , an−1 , · · · , a1 , a0 .

Polynomial Interpolation

Problem Description
Given, (n + 1) points, say (xi , yi ) where i = 0, 1, 2, · · · , n with
distinct xi , not necessarily sorted, we want to find a polynomial of
degree n,

Pn (x) = an x n + an−1 x n−1 + · · · + a1 x + a0

such that it interpolates these points, i.e.,

Pn (xi ) = yi , i = 0, 1, 2, · · · , n.

Our goal: is to determine the coefficients an , an−1 , · · · , a1 , a0 .

Note: The total number of data points is 1 larger than the
degree of the polynomial.
Example
Example

Let the following data represent the values of f:

x 0 0.5 1
f (x) 1.0000 0.5242 -0.9037
Example

Let the following data represent the values of f:

x 0 0.5 1
The questions are the
f (x) 1.0000 0.5242 -0.9037
following:
What is the exact expression for the function f?
Example

Let the following data represent the values of f:

x 0 0.5 1
The questions are the
f (x) 1.0000 0.5242 -0.9037
following:
What is the exact expression for the function f?
What is the value of f (0.75)?
Example

Let the following data represent the values of f:

x 0 0.5 1
The questions are the
f (x) 1.0000 0.5242 -0.9037
following:
What is the exact expression for the function f?
What is the value of f (0.75)?
Answer:
Example

Let the following data represent the values of f:

x 0 0.5 1
The questions are the
f (x) 1.0000 0.5242 -0.9037
following:
What is the exact expression for the function f?
What is the value of f (0.75)?
Answer:
We cannot get the exact expression for the function f just
from the given data: infintely many functions possible
Example

Let the following data represent the values of f:

x 0 0.5 1
The questions are the
f (x) 1.0000 0.5242 -0.9037
following:
What is the exact expression for the function f?
What is the value of f (0.75)?
Answer:
We cannot get the exact expression for the function f just
from the given data: infintely many functions possible
On the other hand: look for an interpolating polynomial.
Importance and Limitations
Importance and Limitations
The interpolating polynomial happens to be
p2 (x) = −1.9042x 2 + 0.0005x + 1
and we have
p2 (0.75) = −0.0707375.
Importance and Limitations
The interpolating polynomial happens to be
p2 (x) = −1.9042x 2 + 0.0005x + 1
and we have
p2 (0.75) = −0.0707375.
The function used to generate the above table of data is
π
f (x) = sin( e x ).
2
Importance and Limitations
The interpolating polynomial happens to be
p2 (x) = −1.9042x 2 + 0.0005x + 1
and we have
p2 (0.75) = −0.0707375.
The function used to generate the above table of data is
π
f (x) = sin( e x ).
2
With this expression of f, we have (using seven-digit rounding)
f (0.75) ≈ −0.1827504.
Importance and Limitations
Importance and Limitations
The interpolating polynomial happens to be
p2 (x) = −1.9042x 2 + 0.0005x + 1
and we have
p2 (0.75) = −0.0707375.
The function used to generate the above table of data is
π
f (x) = sin( e x ).
2
With this expression of f, we have (using seven-digit rounding)
f (0.75) ≈ −0.1827504.
The relative error is given by
f (0.75) − p2 (0.75)
Er (p2 (0.75) = ≈ 0.6129283.
f (0.75)
Why should we do this? Here are some reasons:
Why should we do this? Here are some reasons:

Find the values between the points for discrete data set;
Why should we do this? Here are some reasons:

Find the values between the points for discrete data set;
To approximate a (probably complicated) function by a
polynomial;
Why should we do this? Here are some reasons:

Find the values between the points for discrete data set;
To approximate a (probably complicated) function by a
polynomial;
Then, it is easier to do computations such as derivative,
integration etc.
Interpolation

xi 0 1 2/3
Example 1
yi 1 0 0.5
Interpolation

xi 0 1 2/3
Example 1 Let
yi 1 0 0.5

P2 (x) = a2 x 2 + a1 x + a0 .
Interpolation

xi 0 1 2/3
Example 1 Let
yi 1 0 0.5

P2 (x) = a2 x 2 + a1 x + a0 .

We need to find the coefficients a2 , a1 , a0 . By the interpolating

properties, we have 3 questions:
Interpolation

xi 0 1 2/3
Example 1 Let
yi 1 0 0.5

P2 (x) = a2 x 2 + a1 x + a0 .

We need to find the coefficients a2 , a1 , a0 . By the interpolating

properties, we have 3 questions:
i. x = 0, y = 1 : P2 (0) = a0 = 1
ii. x = 1, y = 0 : P2 (1) = a2 + a1 + a0 = 0
2 2 4 2
iii. x = , y = 0.5 : P2 ( ) = ( )a2 + ( )a1 + a0 = 0.5
3 3 9 3
Interpolation

xi 0 1 2/3
Example 1 Let
yi 1 0 0.5

P2 (x) = a2 x 2 + a1 x + a0 .

We need to find the coefficients a2 , a1 , a0 . By the interpolating

properties, we have 3 questions:
i. x = 0, y = 1 : P2 (0) = a0 = 1
ii. x = 1, y = 0 : P2 (1) = a2 + a1 + a0 = 0
2 2 4 2
iii. x = , y = 0.5 : P2 ( ) = ( )a2 + ( )a1 + a0 = 0.5
3 3 9 3
We have 3 linear equations and 3 unknowns (a2 , a1 , a0 ).
Interpolation

a0 = 1
a2 + a1 + a0 = 0
4 2
a2 + a1 + a0 = 0.5
9 3
Interpolation

a0 = 1
a2 + a1 + a0 = 0
4 2
a2 + a1 + a0 = 0.5
9 3
In matrix-vector form
 
0 0 1 a   1 
2
1 1 1 a 1 =  0 
4 2
 
1 a0 0.5
9 3
Interpolation

a0 = 1
a2 + a1 + a0 = 0
4 2
a2 + a1 + a0 = 0.5
9 3
In matrix-vector form
 
0 0 1 a   1 
2
1 1 1 a 1 =  0 
4 2
 
1 a0 0.5
9 3
Easy to solve:
3 1
a2 = − , a1 = − , a0 = 1.
4 4
Then,
3 1
P2 (x) = − x 2 − x + 1.
4 4
The general Case
The general Case
For the general case with (n + 1) points, we have
Pn (xi ) = yi , i = 0, 1, 2, · · · , n.
The general Case
For the general case with (n + 1) points, we have
Pn (xi ) = yi , i = 0, 1, 2, · · · , n.
We will have (n + 1) equations and (n + 1) unknowns:
Pn (x0 ) = y0 : x0n an + x0n−1 an−1 + · · · + x0 a1 + a0 = y0
Pn (x1 ) = y1 : x1n an + x1n−1 an−1 + · · · + x1 a1 + a0 = y1
..
.
Pn (xn ) = yn : xnn an + xnn−1 an + · · · + xn a1 + a0 = yn .
The general Case
For the general case with (n + 1) points, we have
Pn (xi ) = yi , i = 0, 1, 2, · · · , n.
We will have (n + 1) equations and (n + 1) unknowns:
Pn (x0 ) = y0 : x0n an + x0n−1 an−1 + · · · + x0 a1 + a0 = y0
Pn (x1 ) = y1 : x1n an + x1n−1 an−1 + · · · + x1 a1 + a0 = y1
..
.
Pn (xn ) = yn : xnn an + xnn−1 an + · · · + xn a1 + a0 = yn .
Putting this in matrix-vector form
x0 x0n−1 · · · x0 1
 n    
an y0
x n x n−1 · · · x1 1 an−1  y1 
 1 1
  ..  =  .. 
   
 .. .. ..
. . .   .  .
xnn xnn−1 · · · xn 1 a0 yn
X~a = ~y
 X~a = ~y

X : (n + 1) × (n + 1) matrix, given (Van der Monde

matrix)
 X~a = ~y

X : (n + 1) × (n + 1) matrix, given (Van der Monde

matrix)
~a : unknown vector, with length (n + 1)
 X~a = ~y

X : (n + 1) × (n + 1) matrix, given (Van der Monde

matrix)
~a : unknown vector, with length (n + 1)
~y : given vector, with length (n + 1)
 X~a = ~y

X : (n + 1) × (n + 1) matrix, given (Van der Monde

matrix)
~a : unknown vector, with length (n + 1)
~y : given vector, with length (n + 1)

Theorem 1
If xi ’s are distinct, then X is invertible, therefore ~a has a unique
solution.
 X~a = ~y

X : (n + 1) × (n + 1) matrix, given (Van der Monde

matrix)
~a : unknown vector, with length (n + 1)
~y : given vector, with length (n + 1)

Theorem 1
If xi ’s are distinct, then X is invertible, therefore ~a has a unique
solution.
In other words,

Given n + 1 distinct points x0 , x1 , · · · , xn and n + 1 ordinates

y0 , · · · , yn , there is a polynomial p(x) of degree ≤ n that
interpolates yi at xi , i = 0, 1, · · · , n. This polynomial p(x) is
unique among the set of all polynomials of degree at most n.
Proofs
Recall the Vandermonde matrix X is given by
x02 x0n
 
1 x0 ···
 .. 
Vn (x) = det  . (1)
 
2 n

1 xn−1 xn−1 ··· xn−1 
1 x x2 ··· xn
Proofs
Recall the Vandermonde matrix X is given by
x02 x0n
 
1 x0 ···
 .. 
Vn (x) = det  . (1)
 
2 n

1 xn−1 xn−1 ··· xn−1 
1 x x2 ··· xn

One can show that Vn (x) is a polynomial of degree n, and

that its roots are x0 , · · · , xn−1 . We can obtain the formula
Vn (x) = (x − x0 ) · · · (x − xn−1 )Vn−1 (xn−1 ).
Proofs
Recall the Vandermonde matrix X is given by
x02 x0n
 
1 x0 ···
 .. 
Vn (x) = det  . (1)
 
2 n

1 xn−1 xn−1 ··· xn−1 
1 x x2 ··· xn

One can show that Vn (x) is a polynomial of degree n, and

that its roots are x0 , · · · , xn−1 . We can obtain the formula
Vn (x) = (x − x0 ) · · · (x − xn−1 )Vn−1 (xn−1 ).

Expand the last row of Vn (x) by minors to show that Vn (x) is

a polynomial of degree n and to find the coefficient of the
term x n .
One can show that
Y
det(X ) = Vn (xn ) = (xi − xj )
Bad news: X has a very large condition number for large n,
therefore, not effective to solve if n is large.
Bad news: X has a very large condition number for large n,
therefore, not effective to solve if n is large. Other more efficient
and elegant methods include
Lagrange polynomials
Newton’s divided differences
Lagrange Interpolation
Given points: x0 , x1 , · · · , xn
Lagrange Interpolation
Given points: x0 , x1 , · · · , xn
Define the cardinal functions l0 , l1 , · · · , ln :∈ P n , satisfying the
properties
Lagrange Interpolation
Given points: x0 , x1 , · · · , xn
Define the cardinal functions l0 , l1 , · · · , ln :∈ P n , satisfying the
properties
(
1, i = j
li (xj ) = δij = i = 0, 1, · · · , n.
0, i 6= i,
Lagrange Interpolation
Given points: x0 , x1 , · · · , xn
Define the cardinal functions l0 , l1 , · · · , ln :∈ P n , satisfying the
properties
(
1, i = j
li (xj ) = δij = i = 0, 1, · · · , n.
0, i 6= i,

Here, δij is called the Kronecker’s delta.

Lagrange Interpolation
Given points: x0 , x1 , · · · , xn
Define the cardinal functions l0 , l1 , · · · , ln :∈ P n , satisfying the
properties
(
1, i = j
li (xj ) = δij = i = 0, 1, · · · , n.
0, i 6= i,

Here, δij is called the Kronecker’s delta.

Locally supported in discrete sense. The cardinal functions li (x)
can be written as
n x −x 
j
Y
li (x) =
xi − xj
j=0,j6=i
x − x0 x − x1 x − xi+1 x − xn
= ··· ··· .
xi − x0 xi − x1 xi − xi+1 xi − xn
Lagrange Interpolation
Verify:

li (xi ) = 1 and for i 6= k li (xk ) = 0.

Lagrange Interpolation
Verify:

li (xi ) = 1 and for i 6= k li (xk ) = 0.

Lagrange form of the interpolation polynomial

Lagrange form of the interpolation polynomial can be simply
expressed as
n
X
Pn (x) = li (x)yi .
i=0

It is easy to check the interpolating property:

n
X
Pn (xj ) = li (x)yi = yj , for every j.
i=0
Example
Example 2. Write the Lagrange polynomial for the given data
xi 0 2/3 1
yi 1 0.5 0
Example
Example 2. Write the Lagrange polynomial for the given data
xi 0 2/3 1
Answer. The data set corresponds to
yi 1 0.5 0
2
x0 = 0, x1 = , x2 = 1, y0 = 1 y1 = 0.5, y2 = 0.
3
We first compute the cardinal functions
3 2
l0 (x) = (x − )(x − 1)
2 3
9
l1 (x) = − x(x − 1)
2
2
l2 (x) = 3x(x − ).
3
Thus,
3 2 9
P2 (x) = (x − )(x − 1) − x(x − 1)(0.5) + 0.
2 3 2
Pros and cons of Lagrange polynomial:
Elegant formula
Pros and cons of Lagrange polynomial:
Elegant formula
Slow to compute, each li (x) is different,
Pros and cons of Lagrange polynomial:
Elegant formula
Slow to compute, each li (x) is different,
Not flexible: if one changes a points xj , or add on an
additional point xn+1 , one must re-compute all li ’s.
Newton’s Divided Differences

Given (n + 1) data set, we will describe an algorithm in a recursive

form.
Main idea: Given Pk (x) that interpolates k + 1 data points
{xi , yi }, i = 0, 1, 2, · · · , k, compute Pk+1 (x) that interpolates one
extra point, {xk+1 , yk+1 }, by using Pk and adding an extra term.
For n = 0, we set P0 (x) = y0 . Then, P0 (x) = y0 .
For n = 1, we set

P1 (x) = P0 (x) + a1 (x − x0 )

where a1 is to be determined.
For n = 0, we set P0 (x) = y0 . Then, P0 (x) = y0 .
For n = 1, we set

P1 (x) = P0 (x) + a1 (x − x0 )

where a1 is to be determined.
Then, find a1 by the interpolation property y1 = P1 (x1 ), we
have

y1 = P0 (x1 ) + a1 (x1 − x0 )
= y0 + a1 (x1 − x0 ).

This gives us
y1 − y0
a1 = .
x1 − x0
For n = 2 : we set

P2 (x) = P1 (x) + a2 (x − x0 )(x − x1 ).

Then,
P2 (x0 ) = P1 (x0 ) = y0 , P2 (x1 ) = P1 (x1 ) = y1 .
Determine a2 by the interpolating property y2 = P2 (x2 ).

y2 = P1 (x2 ) + a2 (x2 − x0 )(x2 − x1 ),

y2 − y1 y1 − y0
−
x2 − x1 x1 − x0
a2 = .
x2 − x0
Newton’s form for the interpolation polynomial:

Pn (x) = a0 + a1 (x − x0 ) + a2 (x − x0 )(x − x1 ) + · · ·
+ an (x − x0 )(x − x1 ) · · · (x − xn−1 ).
MA 204 Numerical Methods

Dr. Debopriya Mukherjee

Lecture-6

January 23, 2024

Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence.
Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence.
Interpolation by polynomials, divided differences, error of the
interpolating polynomial, piecewise linear and cubic spline
interpolation.
Errors in Polynomial Interpolation

Given a function f (x) on x ∈ [a, b], and a set of distinct points

xi ∈ [a, b], i = 0, 1, · · · , n. Let Pn (x) ∈ Pn s.t.

Pn (xi ) = f (xi ), i = 0, 1, 2, · · · , n.
Errors in Polynomial Interpolation

Given a function f (x) on x ∈ [a, b], and a set of distinct points

xi ∈ [a, b], i = 0, 1, · · · , n. Let Pn (x) ∈ Pn s.t.

Pn (xi ) = f (xi ), i = 0, 1, 2, · · · , n.

Error function: e(x) = f (x) − Pn (x), x ∈ [a, b].

Theorem 1
There exists some value ξ ∈ (a, b), such that
n
1 Y
e(x) = f (n+1) (ξ) (x − xi ), for all x ∈ [a, b]. (1)
(n + 1)!
i=0
Proof. If f ∈ Pn , then, by Uniqueness Theorem of polynomial
interpolation, we must have f (x) = Pn (x). Then, e(x) = 0 and
the proof is trivial.
Proof. If f ∈ Pn , then, by Uniqueness Theorem of polynomial
interpolation, we must have f (x) = Pn (x). Then, e(x) = 0 and
the proof is trivial.
Now assume, f ∈ / Pn . If x = xi for some i, we have

e(xi ) = f (xi ) − Pn (xi ) = 0,

and the result holds.

Proof. If f ∈ Pn , then, by Uniqueness Theorem of polynomial
interpolation, we must have f (x) = Pn (x). Then, e(x) = 0 and
the proof is trivial.
Now assume, f ∈ / Pn . If x = xi for some i, we have

e(xi ) = f (xi ) − Pn (xi ) = 0,

and the result holds.

Now consider x 6= xi for any i.
n
Y
W (x) = (x − xi ) ∈ Pn+1 ,
i=0
Proof. If f ∈ Pn , then, by Uniqueness Theorem of polynomial
interpolation, we must have f (x) = Pn (x). Then, e(x) = 0 and
the proof is trivial.
Now assume, f ∈ / Pn . If x = xi for some i, we have

e(xi ) = f (xi ) − Pn (xi ) = 0,

and the result holds.

Now consider x 6= xi for any i.
n
Y
W (x) = (x − xi ) ∈ Pn+1 ,
i=0

it holds

W (xi ) = 0, W (x) = x n+1 + · · · , W (n+1) = (n + 1)!

Fix an x such that a ≤ x ≤ b and x 6= xi for any i. We define a
constant
f (x) − Pn (x)
c= ,
W (x)
Fix an x such that a ≤ x ≤ b and x 6= xi for any i. We define a
constant
f (x) − Pn (x)
c= ,
W (x)
and another function

ϕ(y ) = f (y ) − Pn (y ) − cW (y ).
Fix an x such that a ≤ x ≤ b and x 6= xi for any i. We define a
constant
f (x) − Pn (x)
c= ,
W (x)
and another function

ϕ(y ) = f (y ) − Pn (y ) − cW (y ).

We find all the zeros for ϕ(y ). We see that xi0 s are zeros since

ϕ(xi ) = f (xi ) − Pn (xi ) − cW (xi ) = 0.

Also, x is a zero because

ϕ(x) = f (x) − Pn (x) − cW (x) = 0.

Here goes our deduction:
ϕ(x) has atleast (n + 2) zeros on [a, b].
ϕ0 (x) has atleast (n + 1) zeros on [a, b].
ϕ00 (x) has atleast n zeros on [a, b].
···
ϕ(n+1) (x) has atleast 1 zero on [a, b].
Call it ξ s.t. ϕ(n+1) (ξ) = 0. So, we have

ϕ(n+1) (ξ) = f (n+1) (ξ) − 0 − cW (n+1) (ξ) = 0.

Recall W n+1 = (n + 1)!, we have, for every y,

f (y ) − Pn (y )
f (n+1) (ξ) = cW (n+1) (ξ) = (n + 1)!
W (y )
 n
1 Y
e(x) = f (x) − Pn (x) = f (n+1) (ξ) (x − xi ),
(n + 1)!
i=0

for some ξ ∈ [a, b].

Disadvantages of polynomial interpolation Pn (x)
n− times differentiable; We do not need such high
smoothness;
big error in certain intervals (esp. near the ends);
no convergence result;
heavy to compute for large n.
MA 204 Numerical Methods

Dr. Debopriya Mukherjee

Lecture-7

January 23, 2024

Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence.
Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence.
Interpolation by polynomials, divided differences, error of the
interpolating polynomial, piecewise linear and cubic spline
interpolation.
Disadvantages of polynomial interpolation Pn (x)
n− times differentiable; We do not need such high
smoothness;
Disadvantages of polynomial interpolation Pn (x)
n− times differentiable; We do not need such high
smoothness;
big error in certain intervals (esp. near the ends);
Disadvantages of polynomial interpolation Pn (x)
n− times differentiable; We do not need such high
smoothness;
big error in certain intervals (esp. near the ends);
no convergence result;
Disadvantages of polynomial interpolation Pn (x)
n− times differentiable; We do not need such high
smoothness;
big error in certain intervals (esp. near the ends);
no convergence result;
heavy to compute for alrge n.
Suggestion: use piecewise polynomial interpolation.
Usage:
visualization of discrete data
graphic design
Requirement:
interpolation
certain degree of smoothness
Problem Setting

x t0 t1 · · · tn
y y0 y1 · · · yn
Problem Setting

x t0 t1 · · · tn
y y0 y1 · · · yn

Find a function S(x) which interpolates the point (ti , yi )ni=0 .

Problem Setting

x t0 t1 · · · tn
y y0 y1 · · · yn

Find a function S(x) which interpolates the point (ti , yi )ni=0 . The
set t0 < t1 < · · · < tn are called knots. Note that they need to be
ordered. S(x) consists of piecewise polynomial


 S0 (x), t0 ≤ x ≤ t1

S1 (x), t1 ≤ x ≤ t2

S(x) = . (1)
..



Sn−1 (x), tn−1 ≤ x ≤ tn .

Definition for a spline of degree k

S(x) is called a spline of degree k, if

Si (x) is a polynomial of degree k;
Definition for a spline of degree k

S(x) is called a spline of degree k, if

Si (x) is a polynomial of degree k;
S(x) is (k − 1) times continuously differentiable, i.e., for
i = 1, 2, · · · , k − 1 we have
Definition for a spline of degree k

S(x) is called a spline of degree k, if

Si (x) is a polynomial of degree k;
S(x) is (k − 1) times continuously differentiable, i.e., for
i = 1, 2, · · · , k − 1 we have

Si−1 (ti ) = Si (ti ),

0
Si−1 (ti ) = Si0 (ti ),
..
.
(k−1) (k−1)
Si−1 (ti ) = Si (ti ).
Commonly used splines:
n = 1 : linear spline (simplest)
n = 2 : quadratic spline (less popular)
n = 3 : cubic spline (most used)
Problem 1. Determine whether this function is a first-degree
spline function:

 x, x ∈ [−1, 0],
S(x) = 1 − x, x ∈ (0, 1), (2)
2x − 2, x ∈ [1, 2].


Answer: Check all the properties of a linear spline.

Linear polynomial for each piece: OK!
Problem 1. Determine whether this function is a first-degree
spline function:

 x, x ∈ [−1, 0],
S(x) = 1 − x, x ∈ (0, 1), (2)
2x − 2, x ∈ [1, 2].


Answer: Check all the properties of a linear spline.

Linear polynomial for each piece: OK!
S(x) is continuous at inner knots:
Problem 1. Determine whether this function is a first-degree
spline function:

 x, x ∈ [−1, 0],
S(x) = 1 − x, x ∈ (0, 1), (2)
2x − 2, x ∈ [1, 2].


Answer: Check all the properties of a linear spline.

Linear polynomial for each piece: OK!
S(x) is continuous at inner knots:
At x = 0, S(x) is discontinuous, because from the left we get
0 and from the right we get 1.
Problem 1. Determine whether this function is a first-degree
spline function:

 x, x ∈ [−1, 0],
S(x) = 1 − x, x ∈ (0, 1), (2)
2x − 2, x ∈ [1, 2].


Answer: Check all the properties of a linear spline.

Linear polynomial for each piece: OK!
S(x) is continuous at inner knots:
At x = 0, S(x) is discontinuous, because from the left we get
0 and from the right we get 1.
Therefore, this is NOT a linear spline.
Problem 1. Determine whether the following function is a
quadratic spline:

x 2,

 x ∈ [−10, 0],
S(x) = −x 2 , x ∈ (0, 1), (3)
1 − 2x, x ≥ 1.


Answer: Let us label each piece:

Q0 (x) = x 2 , Q1 (x) = −x 2 , Q2 (x) = 1 − 2x.

We now check all the conditions, i.e., the continuity of Q and Q 0

at inner knots 0, 1 :

Q0 (0) = 0, Q1 (0) = 0, OK!

Q1 (1) = −1, Q2 (1) = −1, OK!
Q00 (0) = 0, Q10 (0) = 0, OK!
Q10 (1) = −2, Q20 (1) = −2, OK!
It passes all the test, so it is a quadratic spline.
Linear Spline

n = 1 : piecewise linear interpolation, i.e., straight line between 2

neighboring points.
Linear Spline

n = 1 : piecewise linear interpolation, i.e., straight line between 2

neighboring points.
Requirements:

S0 (t0 ) = y0 (4)
Si−1 (ti ) = Si (ti ) = yi , i = 1, 2, · · · , n − 1 (5)
Sn−1 (tn ) = yn . (6)
Linear Spline

n = 1 : piecewise linear interpolation, i.e., straight line between 2

neighboring points.
Requirements:

S0 (t0 ) = y0 (4)
Si−1 (ti ) = Si (ti ) = yi , i = 1, 2, · · · , n − 1 (5)
Sn−1 (tn ) = yn . (6)

Easy to find: write the equation for a line through two points:
(ti , yi ) and (ti+1 , yi+1 )
yi+1 − yi
Si (x) = yi + (x − ti ), i = 0, 1, · · · , n − 1. (7)
ti+1 − ti
Accuracy Theorem for linear spline
Assume t0 < t1 < · · · < tn , and let hi = ti+1 − ti ,
h = maxi hi .
f (x) : given function, S(x) : a linear spline
S(ti ) = f (ti ), i = 0, 1, · · · , n.
Accuracy Theorem for linear spline
Assume t0 < t1 < · · · < tn , and let hi = ti+1 − ti ,
h = maxi hi .
f (x) : given function, S(x) : a linear spline
S(ti ) = f (ti ), i = 0, 1, · · · , n.
We have the following, for x ∈ [t0 , tn ].
(a) If f 00 exists and is continuous, then,
n1 o 1
|f (x) − S(x)| ≤ max hi2 , max |f 00 (x)| ≤ h2 max |f 00 (x)|.
8 ti ≤x≤ti+1 8 x
Accuracy Theorem for linear spline
Assume t0 < t1 < · · · < tn , and let hi = ti+1 − ti ,
h = maxi hi .
f (x) : given function, S(x) : a linear spline
S(ti ) = f (ti ), i = 0, 1, · · · , n.
We have the following, for x ∈ [t0 , tn ].
(a) If f 00 exists and is continuous, then,
n1 o 1
|f (x) − S(x)| ≤ max hi2 , max |f 00 (x)| ≤ h2 max |f 00 (x)|.
8 ti ≤x≤ti+1 8 x

(b) If f 0 exists and is continuous, then

n1 o 1
|f (x) − S(x)| ≤ max h, max |f 0 (x)| ≤ h max |f 0 (x)|.
i 2 ti ≤x≤ti+1 2 x
To minimize the error, it is obvious that one should add more
knots where the function has large first or second derivative.
MA 204 Numerical Methods

Dr. Debopriya Mukherjee

Lecture-8

January 24, 2024

Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence.
Contents

Solution of a nonlinear equation, bisection and secant

methods, Newton’s method, rate of convergence.
Interpolation by polynomials, divided differences, error of the
interpolating polynomial, piecewise linear and cubic spline
interpolation.
Natural Cubic Spline

Given t0 < t1 < · · · < tn , we define the cubic spline, with

S(x) = Si (x) for ti ≤ x ≤ ti+1 .

Write

Si (x) = ai x 3 + bi x 2 + ci x + di , i = 0, 1, · · · , n − 1.

Total number of unknowns=4.n

Natural Cubic Spline

Equations we have:
equation number
Si (ti ) = yi , i = 0, 1, · · · , n − 1 n
Si+1 (ti+1 ) = yi+1 , i = 0, 1, · · · , n − 1 n
Si0 (ti+1 ) = Si+1
0 (t
i+1 ), i = 0, 1, · · · , n − 2 n−1
Si00 (ti+1 ) = Si+1
00 (t
i+1 ), i = 0, 1, · · · , n − 2 n−1
00 00
S0 (t0 ) = 0, Sn−1 (tn ) = 0, 2
| {z }
Natural
How to compute Si (x)? We know:

Si : polynomial of degree 3

Si0 : polynomial of degree 2

Si00 : polynomial of degree 1

Procedure:

Start with Si00 (x), they are all linear, one can use Lagrange form,

Integrate Si00 (x) twice to get Si (x), you will get two integration
constants.

Determine these constants.