CPE 252:
Numerical Methods and
Probability
Introduction
• Numerical Analysis is used to solve problems that have no analytical
solution or are difficult to solve in other ways
• It uses approximations to the true analytical solutions.
• As a result of the approximations, there is always an error associated
with numerical methods
• Analysis of errors is an important and integral part of the subject of
Numerical Analysis
• For example, integration. Graphically, it represents the area under a
curve.
• Instead of using analytical integration, the physical area under the
curve can be determined in a variety of ways.
Taylor Series
The Taylor series is the foundation of numerical methods because
1. Most of the numerical methods are derived directly from it
2. It is used to estimate the error involved in employing numerical
methods
If the value of a function can be expressed in a region of x close to x=a
by the infinite power series
(1)
then, f(x) is said to be analytic in the region near x=a, and the series is
unique and it’s called the Taylor series expansion of f(x) in the
neighborhood of x=a.
The following conclusions can be made:
a) all derivatives of f(x) at x=a must exist and be finite
b) If the series exists, then knowing f(a) and all derivatives of f at x=a,
we can find the value of f(x) at some x different from a, as long as
we remain ‘sufficiently close’ to x=a. ‘Sufficiently close’ means
working within the radius of convergence.
Some series converge for all |x-a| and are said to have an infinite radius
of convergence, while others converge only for |x-a| values below a
certain limit.
• A convergent series will be exact only if an infinite number of terms
are taken in the series.
• However, since it is much more useful and interesting to take a few
terms, the practice of error analysis become necessary.
• The approximations resulting from the Taylor series can be
represented graphically as follows:
• Suppose we wish to find f(b), i.e.
(2)
f(x)
f(x) Two Terms
One Term
f(b)
f(b)
f(a)
f(a)
a b x
a b x
f(x) Three Terms
f(b)
2
′ (𝑏 −𝑎 ) ′ ′
𝑓 ( 𝑏 ) = 𝑓 ( 𝑎 ) + ( 𝑏 − 𝑎 ) 𝑓 ( 𝑎 )+ 𝑓 (𝑎)
f(a) 2!
a b x
Error Representation
The error in the Taylor series for f(x) when the series is truncated after
the term containing is not greater than
(3)
where the subscript ‘max’ denotes the maximum magnitude of the
derivative on the interval from a to x. The magnitude of the error is
identified with the quantity , since this is the term over which one has
control.
Thus the error is said to be of the order of or designated as O if the
series is truncated as . If a series expression is truncated after the first
three term, we say that f(x) is accurate to O i.e.
(4)
Since more terms give a better representation of a function, one can
say of a series truncated after three and four terms that
O< O (5)
as long as we are within the radius of convergence.
Homework
1. Find the Taylor series expansion for sin x near x=0, a=0
2. Using the Taylor series expansion of about x=0, find to O Bound
the error using the error expression Eq. (3), and compare your
results with the actual error. a=0.
3. Find the Taylor series expansion about x=0 for . What is the radius
of convergence of this series?
Numerical Differentiation
Numerical differentiation is done for 2 reasons:
1. to get the derivative of discrete experimental data
2. as part of the solution of differential equations
• Finite difference calculus, which is the discretization of derivatives,
begins with the definition of the derivative.
• The derivative of a function f(x) is defined as:
• In the approximation of finite difference, the denominator is finite, i.e.
it does not get to zero, so
(6)
where,
This approximate expression may be compared to the mean-value theorem
which states that within the interval of interest (a, b), there exist and such that
(7)
gives the exact value of the derivative.
• If one is using discrete values (as obtained with experimental data) to
approximate the derivative, there are 3 ways in which the data can be
manipulated
(i) 2-point forward difference
𝑓 ( 𝑥) 𝑓 𝑖 +1
𝑓𝑖
𝑓 𝑖− 1
(ii) 2-point backward difference
(𝑖)
(𝑖𝑖)
(𝑖𝑖𝑖) (iii) 2-point central difference
𝑥𝑖 −1 𝑥𝑖 𝑥𝑖 +1 x
• Analytically, there are three ways of deriving the difference equations.
• These methods are:
1) using Taylor series
2) using difference operators
3) differentiating interpolating polynomials
Finite Difference Methods – Using Taylor’s series expansion
Consider a function which is analytic in the neighborhood of a point x.
We find f(x+h) by expanding f(x) in a Taylor series about x:
(1)
Solving for :
(2)
If series (2) is truncated after the first term, then it can be written as:
(3)
which means an expression has been found for with respect to x,
which is accurate to within an error of order h.
Now, let
Thus
If we define, first forward difference
then
Graphically, the first forward difference approximates the slope of the
function of f at the point x with a straight line passing through f(x+h)
and f(x).
Using f(x-h):
(4)
Solving for :
i.e. (5)
or
and (6)
where first backward difference
Higher Order Derivatives
• In this case, we are interested in derivative of derivatives, and so we
need two line segments or three points, i.e.
1st 1st
2nd etc
So, we have expansions for and , we need expansion for .
Now, (7)
and (8)
Subtracting 2 x Eq. (7) from Eq. (8), and solving from , gives
or
Defining the second forward difference of f at j as:
gives
A similar expression can be obtained for the second backward
difference as:
where
In general any forward or backward difference may be obtained by
starting from the first forward and backward differences, and by using
the following recurrence formulas:
For example, the second backward difference of f at j may be found as:
And the forward and backward difference expressions for derivatives of
any order are given by
and
Higher Order Forward and Backward Difference Expressions
• If you want to increase the accuracy of an infinite series, what do you
do, in terms of the number of terms? Ans: you increase the number of
terms.
• Consider the series
(1)
• Solving from gives:
(2)
Now, (3)
Substituting for in Eq. (2) gives:
Collecting terms,
i.e. (4)
This is the forward difference representation for the first derivative
which is accurate to .
• A similar expression could be derived for the backward difference to
order , starting with the expansion for and replacing
by the backward difference expression of
• Forward and backward difference expressions of for higher
derivatives can be derived.
Central Differences
From (5)
and (6)
Subtracting (6) from (5) gives:
And solving for ,
i.e.
or - central differences
By adding (5) and (6) and solving for gives:
Differences and Polynomials
Difference expressions for derivative (since they reduce to polynomials)
and polynomials in general have a distinct relationship which can be
useful. This arises from the fact that the error term of an nth difference
will involve only derivatives of order n+1 or higher in an nth order
polynomial will all be zero.
Suppose there is an unknown polynomial but known measured values
at ,
𝑓 𝑥 𝑗 𝑓 𝑥 𝑗+ 1 𝑓 𝑥 𝑗+ 2 𝑓 𝑥 𝑗+ 3 𝑓 𝑥 𝑗+ 4
- 𝑓 𝑥𝑗 - 𝑓 𝑥 𝑗+ 1
Now it turns out that the nth differences are constant or zero. What
does it tell you?
Ans: That the required function is a polynomial of order n, i.e. … whose
coefficients need to be determined. For example for the forward
difference expression for f’(x) of O() should be exact for a parabola
since the first error term involves f’’’(x). Thus we should be able to find
this difference expression by fitting the parabola
to the points, x=0, h, 2h and then evaluating f’(0)
Fitting the parabola to the three points gives
(x=h)
(x=2h)
Solving for B:
[ (4)]
Homework
Given the following equally spaced data
x 0 1 2 3 4
f(x) 30 33 28 12 -22
Find f’(0), f’(2), f’(4) and f’’(0) using difference representations which
are of O()
