Numerical Methods

KOM2722-
AVE3842

Week 3

Asst. Prof. Bilal Erol

Rolle’s Theorem
𝑦
Suppose that 𝑦 = 𝑓(𝑥) is continuous at every
point of the closed interval [𝑎, 𝑏] and 𝑓′ 𝑐 = 0
differentiable at every point of its interior (𝑎, 𝑏). If
𝑓 𝑎 =𝑓 𝑏 𝑦=𝑓 𝑥
then there is at least one number 𝑐 in 𝑎, 𝑏 at
which
𝑓 ′ 𝑐 = 0. 0 𝑎 𝑐 𝑏
𝑥

Thus, there should be one place where tangent

line should be horizontal
Note that it is also satisfied for functions intersect
the x axis at two points; 𝑓 𝑎 = 𝑓 𝑏 = 0.

2
The Mean Value Theorem
𝑦
Let 𝑓 be a given function, continuous on closed
interval [𝑎, 𝑏] and differentiable at every point of 𝑓′ 𝜁
𝐵
its interior (𝑎, 𝑏). Then there exists a point 𝜁 ∈
𝑦=𝑓 𝑥
[𝑎, 𝑏] such that
𝐴
′
𝑓 𝑏 − 𝑓(𝑎)
𝑓 𝜁 =
𝑏−𝑎 𝑥
0 𝑎 ζ 𝑏

The mean value theorem (MVT) states that between any two points on the
graph of a differentiable function 𝑓 there at least one place where the
tangent line to the graph is parallel to line joining.

3
Intermediate Value Theorem
Let 𝑓 ∈ 𝐶([𝑎, 𝑏]) be given, and assume that 𝑊 is a value between 𝑓(𝑎)
and 𝑓(𝑏), that is, either f 𝑎 ≤ 𝑊 ≤ 𝑓(𝑏), or 𝑓(𝑏) ≤ 𝑊 ≤ 𝑓(𝑎). Then
there exists a point 𝑐 ∈ [𝑎, 𝑏] such that 𝑓(𝑐) = 𝑊.
* This theorem says that a certain point exists does not give us much
information about its numerical value.
-> We will use this theorem as the basis for finding the roots.

Note: 𝐶([𝑎, 𝑏]) — The set of functions 𝑓 which are defined on the
interval [𝑎, 𝑏], continuous on all of (𝑎, 𝑏), and continuous from the
interior of [𝑎, 𝑏] at the endpoints.

4
Extreme Value Theorem
Let 𝑓 ∈ 𝐶 𝑎, 𝑏 be given; then there exists a point 𝑚 ∈ [𝑎, 𝑏] such
that 𝑓(𝑚) ≤ 𝑓(𝑥) for all 𝑥 ∈ [𝑎, 𝑏], and a point 𝑀 ∈ [𝑎, 𝑏] such that
𝑓(𝑀) ≥ 𝑓(𝑥) for all 𝑥 ∈ [𝑎, 𝑏]. Moreover, 𝑓 achieves its maximum
and minimum values on [𝑎, 𝑏] either at the endpoints 𝑎 or 𝑏, or at a
critical point.

The student should recall that a critical point is a point where the first
derivative is either undefined or equal to zero.

5
Integral Mean Value Theorem
Let 𝑓 and 𝑔 both be in 𝐶([𝑎, 𝑏]), and assume further that 𝑔 does not
change sign on [𝑎, 𝑏]. Then there exists a point 𝜁 ∈ [𝑎, 𝑏] such that

𝑏 𝑏

න 𝑔 𝑡 𝑓 𝑡 𝑑𝑡 = 𝑓(𝜁) න 𝑔 𝑡 𝑑𝑡
𝑎 𝑎

6
Discrete Average Value Theorem
Let 𝑓 ∈ 𝐶([𝑎, 𝑏]) and consider the sum, 𝑛

𝑆 = ෍ 𝑎𝑘 𝑓(𝑥𝑘 ) ,
𝑘=1
Where each point 𝑥𝑘 ∈ 𝑎, 𝑏 , and the coefficients satisfy
𝑛

𝑎𝑘 ≥ 0, ෍ 𝑎𝑘 = 1
𝑘=1
Then there exists a point 𝜂 ∈ [𝑎, 𝑏] such that 𝑓(𝜂)𝑛 = 𝑆, i.e.,
𝑓(𝜂) = ෍ 𝑎𝑘 𝑓(𝑥𝑘 )
𝑘=1
Proof: 𝑛 𝑛

𝑓 𝑥𝑘 ≤ 𝑓𝑀 ⇒ 𝑆 = ෍ 𝑎𝑘 𝑓 𝑥𝑘 ≤ 𝑓𝑀 ෍ 𝑎𝑘 = 𝑓𝑀
𝑘=1 𝑘=1

7
Linear Interpolation Methods
Tells how approximating the function with straight lines for example,
almost all graphs produced by computers are actually the results of
piecewise linear interpolation in which the machine draws very large
number of very small straight lines represent the curve.

Given a set of data points 𝑥𝑘 : (called as nodes),

We say the function 𝑝 interpolates the function 𝑓 at these nodes,
if 𝒑(𝒙𝒌 ) = 𝒇(𝒙𝒌 ) for all 𝒌.
We are most interested in the extent to 𝒑 ≈ 𝒇

8
Linear interpolation methods based on using straight line to
approximate a given function.
⇒ 2 points to determine a straight line
𝑥0 , 𝑥1 and a function 𝑓 ⇒ we want to find the equation of a straight
line that passes through these two points: (𝑥0, 𝑓(𝑥0)) , (𝑥1, 𝑓(𝑥1))

𝑥1 − 𝑥 𝑥 − 𝑥0
𝑝1 𝑥 = 𝑓 𝑥0 + 𝑓 𝑥1
𝑥1 − 𝑥0 𝑥1 − 𝑥0

9
Let us investigate how accurate the linear interpolation using Rolle’s
Theorem ⇒ Special case of mean value theorem if 𝑓 𝑐 = 𝑓 𝑏 ⇒
there exists 𝜁 such that 𝑓’(𝜁) = 0.

Define,
𝐸 𝑥 = 𝑓 𝑥 – 𝑝1 𝑥 ,
𝑤 𝑥 = 𝑥 − 𝑥0 𝑥 − 𝑥1 ,
𝑤(𝑥)
𝐺(𝑥) = 𝐸(𝑥) − 𝐸(𝑡)
𝑤(𝑡)
𝑡 some fixed value in (𝑥0, 𝑥1) where ( (𝑥0 < 𝑡 < 𝑥1) )
𝐺(𝑥0) = 0, 𝐺(𝑥1) = 0, 𝐺(𝑡) = 0

10
Then the Rolle’s Theorem states that;
There exists a point 𝑧0 between 𝑥0 and 𝑡 such that 𝐺 ′ 𝑧0 = 0
and a point 𝑧1 , between 𝑥1 and 𝑡, such that 𝐺 ′ (𝑧1 ) = 0.
Let’s apply Rolle’s Theorem to 𝐺 ′ and assert that there exists
a point 𝜁 between 𝑧0 and 𝑧1 such that 𝐺’’(𝜁) = 0.
But,
′′ ′′
2
𝐺 𝑥 =𝐹 𝑥 − 𝐸(𝑡)
𝑤(𝑡)
′′ ′′
2
𝐺 𝜁 = 0 => 𝐹 𝜁 − 𝐸 𝑡 =0
𝑤 𝑡
𝑤(𝑡)

1
And we have 𝑓 𝑡 − 𝑝1 (𝑡) = (𝑡 − 𝑥0 )(𝑡 − 𝑥1 )𝑓′′(𝜁)
2

= 𝐸(𝑡) because we defined (𝐸(𝑥) = 𝑓(𝑥) – 𝑝1(𝑥))

11
For any 𝑡 ∈ [𝑥0 , 𝑥1 ],
The error in the approximation will grow rapidly outside the interval [𝑥0 , 𝑥1 ].
⇒ Let us take absolute values, investigate for the worst case for the second derivative
term.
1
|𝑓(𝑥) − 𝑝1 (𝑥)| ≤ | 𝑥 − 𝑥0 𝑥 − 𝑥1 | max |𝑓 ′′ (𝑡)|
2 𝑥0 ≤𝑡≤𝑥1
1
≤ max 𝑡 − 𝑥0 𝑡 − 𝑥1 max 𝑓 ′′ 𝑡
2 𝑥0 ≤𝑡≤𝑥1 𝑥0 ≤𝑡≤𝑥1
So the upper bound on the error depends on the maximum of the function:
𝑔 𝑥 = | 𝑥 − 𝑥0 𝑥 − 𝑥1 | = (𝑥1 − 𝑥)(𝑥 − 𝑥0 )
𝑔(𝑥0 ) = 𝑔(𝑥1 ) = 0 , the Extreme Value Theorem says that the maximum value of 𝑔 on
the interval [𝑥0 , 𝑥1 ] will be on critical point.
𝑔′ (𝑥) = 𝑥1 − 𝑥 − 𝑥 + 𝑥0 = 𝑥1 + 𝑥0 − 2𝑥
1 1
𝑥𝑐 = (𝑥0 + 𝑥1 ) => 𝑔(𝑥𝑐 ) = 𝑥1 − 𝑥0 2
2 4
12
Finally our error is bounded
1
𝑓 𝑥 − 𝑝1 𝑥 ≤ 𝑥1 − 𝑥0 2 ( max |𝑓 ′′ (𝑥)|)
8 𝑥0 ≤𝑡≤𝑥1
Theorem (Linear Interpolation Error)
Let 𝑓 ∈ 𝐶 2 ([𝑥0 , 𝑥1 ]) and let 𝑝1 𝑥 be linear polynomials that
interpolates 𝑓 at 𝑥0 and 𝑥1 , then for all 𝑥 ∈ [𝑥0 , 𝑥1 ],
1
𝑓 𝑥 − 𝑝1 𝑥 ≤ |(𝑥 − 𝑥0 )(𝑥 − 𝑥1 )| max |𝑓 ′′ (𝑥)|
2 𝑥0 ≤𝑡≤𝑥1
1
≤ 𝑥1 − 𝑥0 2 max |𝑓 ′′ (𝑥)|
8 𝑥0 ≤𝑡≤𝑥1

Note: 𝐶 𝑘 ([𝑎, 𝑏]) — The set of functions 𝑓 such that 𝑓 and its first k
derivatives are all in C([𝑎, 𝑏])
13
Example: Consider the problem of constructing a piecewise linear
approximation to 𝑓(𝑥) = log 2 (𝑥) using the nodes 1/4, 1/2, 1.

1 1
− x 1 𝑥 −
𝑄1 𝑥 = 2 𝑙𝑜𝑔2 + 4 𝑙𝑜𝑔 1 = 4𝑥 − 3
1 1 1 1 2
− 4 − 2
2 4 2 4

1
1−x 1 𝑥−2
𝑄2 𝑥 = 𝑙𝑜𝑔2 + 𝑙𝑜𝑔2 1 = 2𝑥 − 2
1 2 1
1−2 1−2

1 1
4𝑥 − 3, ≤ 𝑥≤
𝑞 𝑥 = 4 2
1
2𝑥 − 2, ≤ 𝑥≤1
2

14
The error:
2
1 1 1 1 1
|𝑙𝑜𝑔2 𝑥 − 𝑄1 𝑥 | ≤ − max 𝑙𝑜𝑔2 𝑒 𝑡 −2 = 0.1803368801 𝑓𝑜𝑟 𝑥 ∈ [ , ]
8 2 4 1 1
𝑡∈[ , ] 4 2
4 2
not always the same
2
1 1 1
| 𝑙𝑜𝑔2 𝑥 − 𝑄2 𝑥 | ≤ 1− max 𝑙𝑜𝑔2 𝑒 𝑡 −2 = 0.1803368801𝑓𝑜𝑟 𝑥 ∈ [ , 1]
8 2 1
𝑡∈[2,1] 2

⇒ |log2(x) – q(x)| ≤ 0.1803368801

15