Numerical Analysis 01

Dr. Boukhelkhal Ikram

2025-2026
Contents

1 Error Analysis 2

2 Numerical solution of non linear equation 3

3 Polynomial interpolation and Approximation 4

3.1 Interpolation Polynomials . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.1.1 Lagrange Interpolation polynomial . . . . . . . . . . . . . . . . . . . . . 5
3.2 Divided differences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2.1 equidistant Case (equal space case ) . . . . . . . . . . . . . . . . . . . . 11
3.2.2 Evaluation of errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12

1
Chapter 1
Error Analysis

2
Chapter 2
Numerical solution of non linear equation

3
Chapter 3
Polynomial interpolation and
Approximation

Introduction

In the following, we will denote by Pn the vector space of real-coefficient polynomial func-
tions on R of degree less than or equal to n. We therefore have:

dim(Pn ) = n + 1.

And, if f be a function defined and bounded on an interval [a, b] with values in R. The
uniform norm of f on the interval [a, b] will be denoted by:

∥f ∥∞ = sup |f (x)|.
x∈[a,b]

Polynomials Pn ∈ Pn are among the most fundamental and useful tools in mathematics.
Their importance stems from the following theorem

Theorem 3.1 (Weirstras Approximation Theorem ) suppose that f is defined and continuous on
[a, b]. For each ϵ > 0 there exists a polynomials P (x) with the property that

∥f (x) − P (x)∥∞ < ϵ (3.1)

3.1 Interpolation Polynomials

Theorem 3.2 Let (xi , yi ), i = 0, . . . , n, be n + 1 distinct points with xi ̸= xj for i ̸= j. There exists
a unique polynomial pn of degree at most n such that pn (xi ) = yi for all i = 0, . . . , n.

4
Proof. One way to solve this problem is a direct method based on solving a linear system.
Let
pn (x) = an xn + an−1 xn−1 + · · · + a1 x + a0 .

Write explicitly pn (xi ) = yi , i = 0, . . . , n:





 an xn0 + an−1 xn−1 0 + · · · + a1 x0 + a0 = y0 ,



an xn1 + an−1 xn−1

1 + · · · + a1 x1 + a0 = y1 ,
..
.







n
+ an−1 xn−1 + · · · + a1 xn + a0 = yn .

a
n xn n

Since the values xi , yi , i = 0, . . . , n are known, these relations form a linear system of n + 1
equations in the n + 1 unknowns ai , i = 0, . . . , n that can be written in matrix form:
    
1 x0 · · · xn0 a y
   0  0
1 x1 · · · xn1   a1   y1 
    
 .. .. . .

.  .  =  . .
    (2.2)
. . . ..   ..   .. 
    
n
1 xn · · · xn an yn
| {z }
V

The matrix of this system is called the Vandermonde matrix. Indeed, the determinant of the
Vandermonde matrix is given by the formula:
Y
det(V ) = (xj − xi )
0≤i<j≤n

The determinant of the matrix V is nonzero if the xi , i = 0, . . . , n are distinct. Therefore,

we obtain the existence and uniqueness of the interpolation polynomial.
Let f : [a, b] 7→ R be a continuous function, and given a set of distinct data point (nodes)
x0 , x1 , · · · , xn in [a, b] and the problem is to find a polynomial Pn ∈ Pn such that

Pn (xi ) = f (xi ), ∀i = 0, n (3.2)

This polynomial will be called the interpolation polynomial of f at the points x0 , x1 , · · · , xn .

3.1.1 Lagrange Interpolation polynomial

The polynomial Li is called the characteristic Lagrange polynomial and is defined as:
n
Y (x − xj )
Li (x) = , 0≤i≤n (3.3)
j=0
(x i − x j )
j̸=i

5
where the product is taken over all indices j from 0 to n such that j ̸= i.

Proposition 3.1 The polynomial Li satisfy

• Li ∈ Pn

• Li (xi ) = 1

• Li (xj ) = 0 if i ̸= j

Theorem 3.3 The interpolation problem Pn (xi ) = f (xi ), ∀i = 0, 1, . . . , n has a unique solution
given by the formula:
n
X
Pn (x) = f (xi )Li (x) (3.4)
i=0

where Li (x) are the Lagrange fundamental polynomials. Pn is called the Lagrange interpolation
polynomial.

Proof.
Existance :
It can be verified directly that the polynomial defined in 3.4 solves the problem 3.2. By using
the proposition 3.1.
Uniqueness
Suppose we have two interpolation polynomials Pn and Qn such that

Pn (xi ) = f (xi ),

∀i = 0, 1, . . . , n. (3.5)
Qn (xi ) = f (xi ),


Then, by subtracting the two equations, we have

Pn (xi ) − Qn (xi ) = 0

It’s mean
(Pn − Qn )(xi ) = 0

The polynomial Pn − Qn has a degree less than or equal to n and has n + 1 roots. So it is clear
that Pn − Qn = 0, which means Pn = Qn .

11
Example 3.1 • Use the nodes x0 = 2,, x1 = 4
and x2 = 4 to find the second lagrange interpo-
1
lation for f (x) = x

6
 • use the polynomial to approximate f (3).

Theorem 3.4 Suppose x0 , x1 , · · · , xn are distinct numbers in the interval [a, b] and f ∈ C n+1 [a, b].
Then for each x ∈ [a, b] a number α(x) btween x0 , x1 , · · · , xn and hence in (a, b) exists with
f n+1 (α(x))
f (x) − Pn (x) = (x − x0 )(x − x1 ) · · · (x − xn ) (3.6)
(n + 1)!
Proof. We know that for all i = 0, n then f (xi ) = P (xi ), so if x = xi choosing any α(x) in (a, b) the
equation 3.6 hold. Now in the case x ̸= xi , let define the function h for t in [a, b] by
(t − x0 )(t − x1 ) · · · (t − xn )
h(t) = f (t) − Pn (t) − (f (x) − Pn (x))
(x − x0 )(x − x1 ) · · · (x − xn )
we have f ∈ C n+1 [a, b] so it follows h ∈ C n+1 [a, b].

• for t = xi for all i = 0, n so we have

h(xi ) = 0

• for t = x so we have
h(x) = 0

so the function h have n+2 distinct roots. so by the Generalized Rolle’s Theorem, there exist a number
α(x) between xi and hence in (a, b) for which

hn+1 (c) = 0

and
dn+1
 
n+1 n+1 (t − x0 )(t − x1 ) · · · (t − xn )
h (t) = f (t) − Pnn+1 − [f (x) − Pn (x)] n+1
dt (x − x0 )(x − x1 ) · · · (x − xn )
So
(n + 1)!
f n+1 (α(x)) − [f (x) − Pn (x)] Qn =0
i=0 (x − xi )

then Qn
i=0 (x− xi ) n+1
f (x) = Pn (x) + f (α(x)) (3.7)
(n + 1)!

Remark 3.1 The error formula for Lagrange polynomials is a key theoretical tool. These polynomials
are widely used to develop numerical methods for differentiation and integration, and their error
formula are obtained from the Lagrange error formula.
Notice the similarity between the error term for the Lagrange polynomial and the one for the Taylor
polynomial:

7
 • The Taylor polynomial of degree n uses information at a single point x0 . Its error term is:

f (n+1) (ξ(x))
(x − x0 )n+1 .
(n + 1)!

• The Lagrange polynomial of degree n uses information at distinct points x0 , x1 , . . . , xn . Its

error term uses a product of terms instead of a single power:

f (n+1) (ξ(x))
(x − x0 )(x − x1 ) · · · (x − xn ).
(n + 1)!

Example 3.2 Back to the example 3.1, determine the error of interpolation and the maximum error
when the polynomial is used to approximate f (x) for x ∈ [2, 4]

3.2 Divided differences

The Lagrange interpolation polynomial is usually expressed in terms of the Lagrange ba-
sis polynomials. However, this representation has a significant drawback: when new data
points are added, the entire interpolation must be recalculated from scratch. Therefore, it is
advantageous to seek an alternative formulation or basis that remains stable and does not
require re-computation when additional points are introduced.
Let wi (x)ni=0 be a basis of Pn defined as:

 w (x) = 1
0
wi (x) = (3.8)
 w (x) = Qk−1 (x − x ), k = 1, n
k i=0 i

Suppose that Pn (x) is the nth Lagrange interpolation polynomial that agrees with the func-
tion f at the distinct nodes x0 , x1 , . . . , xn . We saw in Section 1 that Pn is unique. Since the
family {wi (x)}ni=0 forms a basis of Pn , we can write the polynomial as
n
X
Pn (x) = αi wi (x) (3.9)
i=0

To determine α0 we have to evaluating Pn (x) at x0 gives

α0 = Pn (x0 ) = f (x0 )

then
n
X
Pn (x) = f (x0 ) + αi wi (x)
i=1

8
now for α1 , we have to evaluate Pn (x) at x1 so

f (x0 ) + α1 (x1 − x0 ) = Pn (x1 ) = f (x1 )

Thus
f (x1 ) − f (x0 )
α1 =
x1 − x 0
now we can introduce the definition of Divided differences

Definition 3.1 The relations of system (D) are called the pth divided difference relative to xi , xi+1 , . . . , xi+p
of the function f at the points xi , xi+1 , . . . , xi+p




 D(xi ) = f (xi ),


 f (xi ) − f (xi+1 ) D(xi ) − D(xi+1 )
D(xi , xi+1 ) = = ,


xi − xi+1 xi − xi+1




D(xi , xi+1 ) − D(xi+1 , xi+2 )

(D) D(xi , xi+1 , xi+2 ) = , (3.10)

 xi − xi+2
..


.





D(xi , xi+1 , . . . , xi+p−1 ) − D(xi+1 , xi+2 , . . . , xi+p )



D(xi , xi+1 , . . . , xi+p ) =
 .
xi − xi+p

The interpolation polynomial

n
X
Pn (x) = D(x0 , x1 , · · · , xk )wk (x) (3.11)
k=0

called the the newton’s Divided difference

Remark 3.2 The Divided difference D(xi , xi+1 , . . . , xi+p ) is invariante to permutation of the nodes
xi , xi+1 , . . . , xi+p .

The following table explains how to calculate divided differences

Example 3.3 Given the following numerical values: use Newton’s formula to determine the polyno-
mial that interpolates the function f defined by its values, and then evaluate f (1.8) .

Theorem 3.5 Suppose that f ∈ C n ([a, b]) and x0 , x1 x · · · , xn are distinct numbers in [a, b]. Then a
number α exist in (a, b) with
f (n) (α)
D(x0 , x1 , · · · , xn ) = (3.12)
n!

9
 xi fi D1 D2 ... Dn−1 Dn

x0 f (x0 )
D(x0 )−D(x1 )
D(x0 , x1 ) = x0 −x1

x1 f (x1 ) D(x0 , x1 , x2 )
D(x1 )−D(x2 )
D(x1 , x2 ) = x1 −x2

x2 f (x2 ) D(x1 , x2 , x3 )

D(x0 , x1 , · · · xn−1 )

.. .. .. .. .. D(x0 , x1 , · · · xn )

D(x1 , x2 , · · · xn )

xn−2 f (xn−2 ) D(xn−3 , xn−2 , xn−1 )

D(xn−1 )−D(xn−2 )
D(xn−1 , xn−2 ) = xn−1 −xn−2

xn−1 f (xn−1 ) D(xn−2 , xn−1 , xn )

D(xn−1 )−D(xn )
D(xn−1 , xn ) = xn−1 −xn

xn f (xn )

xi 1 1.5 2 2.5
f (xi ) 0 1 2 -1.5

Proof. Let
h(x) = f (x) − Pn (x)

We know that f (xi ) − Pn (xi ) = 0 for each i = 0, n, that means that the function h has n + 1
distinct zeros in [a, b]. Since f ∈ C n ([a, b]), so h ∈ C n ([a, b]). According to the generalized
Rolle’s theorem, there exists α ∈ (a, b) such that

h(n) (α) = 0

Thus
f (n) (x) − Pn(n) (x) = 0 ⇒ f (n) (x) = Pn(n) (x)

since Pn (x) is polynomial of the form

n
X
D(x0 , x1 , · · · , xk )wk (x)
k=0
(n)
then Pn (x) = n!D(x0 , x1 , · · · , xn ) for all x ∈ [a, b] this implies
f (n) (α)
D(x0 , x1 , · · · , xn ) =
n!

10
3.2.1 equidistant Case (equal space case )

we introduce h = xi+1 − xi for all i = 0, n − 1 and xi = x0 + ih using the variable change

x−x0
t= h
we get

Pn (x) = Pn (x0 + th) =D(x0 ) + thD(x0 , x1 ) + t(t − 1)h2 D(x0 , x1 , x2 )+

· · · + t(t − 1) · · · (t − n + 1)hn D(x0 , x1 , · · · , xn ) (3.13)

now, making the notation fi = f (xi ), we define the Forward Finite Differences of first order
by
∆fi = fi+1 − fi ∀i = 0, n − 1 (3.14)

For the second order

∆2 fi = ∆fi+1 − ∆fi ∀i = 0, n − 2 (3.15)

In general for an k th order

∆k fi = ∆k−1 fi+1 − ∆k−1 fi ∀i = 0, n − k (3.16)

Remark 3.3
∆0 fi = fi ∀i = 0, n (3.17)

Proposition 3.2 The pth divided difference D(xi , ..., xi+p ) of a function f in the equally spaced case
and using the forward finite differences can be written as

∆p fi
D(xi , ..., xi+p ) = (3.18)
p!hp

Proof. during the lecture

The First interpolation Formula of Newton Forward or it called Newton Forward-Difference
formula is given as
n
X ∆k f0
Pn (x) = P̃n (t) = f0 + t(t − 1) · · · (t − k + 1) (3.19)
k=1
k!

Remark 3.4 If we take the initial point xn so h = xi+1 − xi for all i = 0, n − 1 and we set the
x−xn
variable change t = h
we obtain

x − xn = th; x − xn−1 = h(t + 1) ;··· ; x − x1 = h(t + n − 1)

11
So we have

Pn (x) = P̃n (t) =D(xn ) + thD(xn , xn−1 ) + t(t + 1)h2 D(xn , xn−1 , xn−2 )+

· · · + t(t + 1) · · · (t + n − 1)hn D(xn , xn−1 , xn−2 , · · · , x0 ) (3.20)

so, The second interpolation Formula of Newton backward or it called Newton bachward-Difference
formula is given as
n
X ∆k fn−1
P̃n (t) = fn + t(t + 1) · · · (t + k − 1) (3.21)
k=1
k!
√
Example 3.4 Let the following table of the function f (x) = x

xi 1.00 1.05 1.10 1.15 1.20 1.25 1.30

f (xi ) 1.00000 1.02469 1.04881 1.07238 1.09544 1.11803 1.14017

√ √ √
• interpolate 1.01, 1.12, 1.28

3.2.2 Evaluation of errors

For the equally spaced points xi+1 − xi = h for all i = 0, n − 1, applying the interpolation
x−x0
error equation 3.6, and if set t = h
. So the error of the first Newton’s formula is

t(t − 1) · · · (t − n) n+1
hn+1 f (α) (3.22)
(n + 1)!
x−xn
and if set t = h
. So the error of the second Newton’s formula is

t(t + 1) · · · (t + n) n+1
hn+1 f (α) (3.23)
(n + 1)!

where α is a number between xi and hence in (a, b).

Exercice :
Let denote by M = maxx∈[x0 ,xn ] |f n+1 (x)|, so the error estimation of the first Newton’s for-
mula is given by
M hn+1
|Rn (x)| = |f (x) − Pn (x)| ≤ |Φ(t)|
(n + 1)!
where Φ(t) = t(t − 1) · · · (t − n) for t ∈ [0, n].

1. Proove that |Φ(n − t)| = |Φ(t)|, and conclude.

|Φ(t−1)|
2. show that |Φ(t)|
> 1 for t ∈]0, n2 ], and conclude.

12
 3. Proove now that maxt∈(0,1] Φ(t) ≤ n!

Remark 3.5 The error formula in the previous exercise shows that increasing the order n does not
necessarily guarantee convergence. This occurs when the (n + 1)-th derivative is unbounded or when
increasing n produces a highly oscillatory polynomial (Runge phenomenon).

Example 3.5 Consider the function defined by

1
f (x) =
1 + x2

on the interval [−5, 5]. Let pn denote the interpolation polynomial of f at n + 1 equally spaced points
in [−5, 5].
As shown in the figure below, when n increases, significant issues arise near the endpoints of the
interval.

13