Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.1
Lecture 4
Numerical Techniques : Root
Searching
Blackbody Radiation
IKC-MH.55 Scientific Computing with Python at November 03,
2023
Dr. Cem Özdo
˘
gan
Engineering Sciences Department
˙
Izmir Kâtip Çelebi University
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.2
Contents
1 Solving Nonlinear Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation Methods-The Secant Method
Newton’s Method
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.3
Main Topics I
•
Solve “f(x) = 0”
•
where f(x) is a function of x.
•
The values of x that make f (x) = 0 are called th e
roots of the equation
.
•
The following non-linear equation can compute the friction
factor,f:
1
√
f
=
1
k
ln(RE
p
f ) +
14 −
5.6
k
•
The equation for f is not solvable except by the numerical
procedures.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.4
Main Topics II
1 Interval Halving (Bisection). Describes a method that is
very simple and foolproof but is not very efficient. We
examine how the error decreases as the method
continues.
2 Linear Interpolation Methods. Tells how approximating
the function in the vicinity of the root with a straight line
can find a root more efficiently. It has a better "rate of
convergence".
3 Newton-Raphson Method. Explains a still more efficient
method that is very widely used but there are pitfalls that
you should know about. Complex roots can be found if
complex arithmetic is employed.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.5
Blackbody Radiation I
•
Some observations in physics experiments at the
beginning of the 20
th
century could not be explained by
classical theories (Blackbody Radiation, The Photoelectric
Effect, The Hydrogen Atom, . . .).
•
Among them, the phenomenon called Blackbody
Radiation has a special place.
•
By definition, a blackbody is an object that absorbs any
heat radiation falling on it.
•
Rayleigh and Jean proposed that infinitesimal amounts of
energy were continuously added to the system when the
frequency was increased.
•
Classical physics assumed that energy emitted by
atomic oscillations could have any continuous value.
•
If we try and sum the energies at each frequency we find
that there is an in finite energy in this system!
•
This paradox was called the ULTRAVIOLET
CATASTROPHE.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.6
Blackbody Radiation II
Figure: Variation of energy
density with
wavelength/frequency in
blackbody radiation.
•
Spectrum of the radiation
inside the blackbody can be
measured experimentally.
dU = u(λ, T )dλ
•
The experimentally
observed curve u(λ, T ) at
T=5000 K is shown in the
upper figure.
•
It has not been possible to
explain this observed
spectrum of blackbody
radiation w ith classical
theories ( in the classical
limit of large λ,
Rayleigh-Jeans Law).
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.7
Blackbody Radiation III
•
Later, in 1901, Planck was able to come up with the
formula that fully explained this curve, with an assumption
that predicted the quantum nature of light:
u(λ, T ) =
8πhc
λ
5
1
e
hc/λk
B
T
− 1
(1)
Here c is the speed of light and h = 6.63 × 10
−34
joule.s
becomes a new constant in physics by the name of
Planck’s constant.
•
Planck’s assumption was as follows: The energy was
quantized and co uld be emitted or ab so rbed only in
integral multiples of a small u nit of energy, known as a
quantum.
•
The energy distribution of a radiation with a frequency
ν = hc/λ is a multiple of an amount of hν:
E = nhν (n = 1, 2, 3, . . .)
•
Blackbody radiation helped to move our understanding in
physics from a classic al approach to a quantum one.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.8
Blackbody Radiation IV
•
Some notable features of the Planck distribution are:
1 To tal radiant energy (ie the area under the curve in the
Figure)
Z
∞
0
u(λ, T )dλ = σT
4
is p r oportional to the 4
th
power of the temperature T. This is
called th e Stefan-Boltzmann formula.
2 There is a simple relation bet ween the wavelength λ
max
at
which each curve has a maximum value and t he equilibrium
temperature T
λ
max
T = 0.0029 m.K
This equation is called t he Wien’s displacement law.
•
Here we will obtain the Wien’s displacement law by
numerical method.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.9
Blackbody Radiation V
•
To find the maximum wavelength, it is sufficient to take the
derivative of Equation 1 with respect to the wavelength λ
and s et it to zero. However, it is convenient to do this
based on the dimensionless variable x = hc/k
B
T λ:
u(x) = A
x
5
e
x
− 1
(x = hc/k
B
T λ and A = 8π(k
B
T )
5
/(hc)
4
)
du
dx
= A
5x
4
(e
x
− 1) − x
5
e
x
(e
x
− 1)
2
= 0
(5 − x ) − 5e
−x
= 0 (2)
•
If this equation is solved, x
max
and then λ
max
can be found.
However, Equation 2 has no analytical solution.
•
We can find the answer with the numerical root finding
methods.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.10
Bisection I
•
Interval halving (bisection), an ancient but effective
method for finding a zero of f (x).
•
It begins with two values for x that bracket a root.
•
The fu nction f (x ) changes sign s at t hese two x-values
and, if f (x) is c ontinuous, there must be at least one
root between the values
.
•
The test to see that f (x) does change sign between points
a and b is to see if f (a) ∗ f (b) < 0 (see Fig. ).
Figure: Testing for a change in sign
of f(x) will bracket either a root or
singularity.
The bisection method then
•
successively divides the ini tial
interval in half,
•
finds in which half the root(s)
must lie,
•
and repeats with the endpoints
of the smaller interval.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.11
Bisection II
•
A plot of f (x) is useful to know where to start.
•
Example: The function; f (x) = 3x + sin(x) − e
x
•
Look at to the plot of the function to learn where the
function crosses the x-axis.
1 imp ort numpy as np
2 from math i mpo rt
*
3 def f ( x ) :
4 r et ur n 3
*
x+s in ( x )−exp ( x )
5 x va l = [ ]
6 fu n va l = [ ]
7 k f i r s t =0. 0; k las t =2 .0; kincrem ent =0.01
8 f o r j i n np . arange ( k f i r s t , k l a s t +
kincr ement , kinc rement ) :
9 xv al . append ( j )
10 f un va l . append( f ( j ) )
11 i mport m at p lo t li b . p y pl ot as p l t
12 p l t . t i t l e ( ’ $ f ( x ) =3x+ sin ( x )−e^ x$ ’ )
13 p l t . x la be l ( ’X Value ’ )
14 p l t . y la be l ( ’ Func tion Value ’ )
15 p l t . p l o t ( x val , f un val , ’− ’ )
16 p l t . g ri d ( )
17 p l t . s ave fig ( ’ f u nc t io n_ plo t . eps ’ )
18 p l t . show( )
Figure: Code and plot of the
function:
f (x) = 3x + sin(x) − e
x
•
We see from the figure that indicates there ar e zeros at
about x = 0.35 and 1.9.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.13
Bisection IV
The root is (almost) never known exactly, since it is extremely
unlikely that a numerical procedure will find the precise value of
x that makes f (x) exactly zero in floating-point arithmetic.
•
The main advantage of
interval halving is that it is
guaranteed to work
(continuous & bracket).
•
The algorithm must decide
how close to the root the
guess should be before
stopping the search (see
Fig.).
•
The major objection of
interval halving has been
that it is slow to converge.
Figure: The stopping criterion for a
root-finding procedure should
involve a tolerance on x, as well as
a tol erance on f (x).
Bisection is generally recommended for finding an approximate
value for the root, and then this value is refined by more
efficient methods.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.14
Linear Interpolation Methods - The Secant Method I
•
Bisection is simple to understand but it is not the most
efficient way to find where f (x) is zero.
•
Most functions can be approximated by a straight line over
a small interval.
Figure: Graphi ca l illustration of the
Secant Method.
•
The secant method begins
by finding two points on the
curve of f (x), hopefully near
to the root.
•
As Figure illustrates, we
draw the line through these
two points and find where it
intersects the x-axis.
•
If f (x ) were truly linear, the
straight line would intersect
the x-axis at the root.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.15
Linear Interpolation Methods - The Secant Method II
•
From the obvious similar triangles we can write
(x
1
− x
2
)
f (x
1
)
=
(x
0
− x
1
)
f (x
0
) − f (x
1
)
=⇒ x
2
= x
1
− f (x
1
)
(x
0
− x
1
)
f (x
0
) − f (x
1
)
•
Because f(x) is not exactly linear, x
2
is not equal to r,
•
but it should be closer than either of the two points we
began with. If we repeat this, we have:
x
n+1
= x
n
− f (x
n
)
(x
n−1
− x
n
)
f (x
n−1
) − f (x
n
)
, n = 1, 2, . . .
•
The net effect of this rule is to set x
0
= x
1
and x
1
= x
2
,
after each iteration.
The technique we have descr ibed is known as, the
secant method because the line through two points on the
curve is called the secant line.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.16
Linear Interpolation Methods - The Secant Method III
•
Apply Secant method to f (x) = 3x + sin(x) − e
x
.
(Example py-file: mysecant.py)
Table: The Secant method for f (x) = 3x + sin(x) − e
x
, starting
from x
0
= 1, x
1
= 0, using a tolerance value of 1 E-16.
•
Table shows the results from the secant method for the
same function that was used to illustrate bisection method.
•
If f (x ) is far from linear near the root or not continuous, the
method may fail. A plot of f (x) is useful to know
where/how to start.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.17
Newton’s Method I
Figure: Graphi ca l illustration of the
Newton’s Method.
•
One of the
most widely used methods
of solving equations is
Newton’s method.
•
Like the previous ones, this
method is also based on a
linear approximation of the
function, but does so using
a tangent to the curve
(see
Figure).
•
Starting from a single initial estimate, x
0
, that is not too far
from a root, we move along the tangent to its intersection
with the x-axis, and take that as the next approximation.
•
This is continued until either the successive x-values are
sufficiently close or the value of the function is sufficiently
near zero.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.18
Newton’s Method II
•
The calculation scheme follows immediately from the right
triangle shown in Figure.
tanθ = f
′
(x
0
) =
f (x
0
)
x
0
− x
1
⇒ x
1
= x
0
−
f (x
0
)
f
′
(x
0
)
and the general ter m is:
x
n+1
= x
n
−
f (x
n
)
f
′
(x
n
)
, n = 0, 1, 2, . . .
•
Newton’s algorithm is widely used because, it is more
rapidly convergent than any of the methods discussed so
far. Quadratically convergent
•
The error of each step approaches a constant K times the
square of the error of the previous step.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.19
Newton’s Method III
•
The number of decimal places of accuracy nearly
doubles at each iteration
.
•
There is the need for two functions evaluations at each
step, f (x
n
) and f
′
(x
n
) and we must obtain the derivative
function at the start.
•
If a difficult problem requires many iterations to converge,
the number of function evaluations with Newton’s method
may be many more than with linear iteration methods.
Because Newton’s method always uses two per iteration
whereas the others take only one.
•
The method may converge to a root different from the
expected one or diverge if the starting value is not close
enough to the root.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.20
Newton’s Method IV
•
Apply Newton’s method to f (x) = 3x + sin(x) − e
x
.
(Example py-file: mynewton.py)
•
Table shows the results from Newton’s method for the
same function that was used to illustrate bisection and
secant methods.
Table: Newton’s method for f (x) = 3x + sin(x) − e
x
, starting fr om
x
0
= 0, using a tolerance value of 1E-16.
Numerical Techniques:
Root Searching
Dr. Cem Özdo
˘
gan
LOGIK
Solving Nonlinear
Equations
Blackbody Radiation
Interval Halving (Bisection)
Linear Interpolation
Methods-The Secant
Method
Newton’s Method
4.21
Blackbody Radiation V
(Example py-file: blackbodyradiation.py )
0.0 2.5 5.0 7.5 10.0 12.5 15.0 17.5 20.0
X Value
−15.0
−12.5
−10.0
−7.5
−5.0
−2.5
0.0
2.5
Function Value
x
max
= 4.965114
λ
max
T
=
hc
/
k
B
x
max
= 0.002898
m
.
K
f
(
x
) = (5 −
x
) − 5
e
−
x
