EP4210/EP24040 - Computational Physics
Kirit Makwana
Department of Physics, IIT Hyderabad
Kirit MakwanaDepartment of Physics, IIT Hyderabad
EP4210/EP24040 - Computational Physics 1 / 10
Root finding
Kirit MakwanaDepartment of Physics, IIT Hyderabad
EP4210/EP24040 - Computational Physics 2 / 10
Motivation
A common example is solving dispersion relation, which is a function
of frequency and wavevector
f(ω, k) = 0 (1)
If we take k as a parameter of the equation, then we have to solve for
an ω such that f(ω) = 0
Energy levels in Quantum Mechanics come from such equations
If an object is moving in a gravitational potential well ϕ(r), its energy
is
1
E = mv2 + mϕ(r) (2)
2
In polar co-ordinates this becomes
[ ]
2 2 2 2 L2
ṙ = Er + mr ϕ(r) − (3)
mr2 2m
The apogee and perigee will be where the right hand side becomes
zero - root finding
Kirit MakwanaDepartment of Physics, IIT Hyderabad
EP4210/EP24040 - Computational Physics 3 / 10
Bisection method
If we know two points a and b such that f(a)f(b) < 0, and if the
function is continuous, then it is certain that there is a point xr ,
a < xr < b, which is a root of the equation f(x) = 0
Lets build successive steps of approximation to find the solution
Kirit MakwanaDepartment of Physics, IIT Hyderabad
EP4210/EP24040 - Computational Physics 4 / 10
Algorithm
d e f i n e a convergence t h r e s h o l d eps
define function f (x)
define a & b
while ( e r r o r l e s s than eps )
x0 = ( a+b ) / 2
e r r o r = abs ( f ( x0 ) )
i f e r r o r < eps , t h e n we h av e f o u n d s o l u t i o n
e x i t loop
e l s e i f f ( x0 ) ∗ f ( a ) < 0 t h e n
b=x0
else
a=x0
end i f
print solution
Implement this to find root of tan x = ex
Kirit MakwanaDepartment of Physics, IIT Hyderabad
EP4210/EP24040 - Computational Physics 5 / 10
Newton’s method (Newton-Raphson method)
Suppose you are near a root of f(x) which is xr
df
f(x) = f(xr ) + (x − xr ) |x=xr + O(x − xr )2 (4)
dx
By definition, f(xr ) = 0, so
f(x)
xr ≈ x − (5)
df/dx
This allows us to develop an approximation
f(xn )
xn+1 = xn − (6)
f′ (xn )
Kirit MakwanaDepartment of Physics, IIT Hyderabad
EP4210/EP24040 - Computational Physics 6 / 10
Geometric interpretation
Newton’s method is like drawing a tangent to the function and
estimating the root
Kirit MakwanaDepartment of Physics, IIT Hyderabad
EP4210/EP24040 - Computational Physics 7 / 10
Algorithm
d e f i n e a convergence t h r e s h o l d eps
define function f (x)
d e f i n e t h e d e r i v a t i v e f u n c t i o n d f / dx
d e f i n e a s t a r t i n g p o i n t x0
c a l c u l a t e e r r = abs ( f ( x0 ) )
while ( e r r > eps )
x1 = x0 −( f ( x0 ) / ( d f / dx ( x0 ) ) )
e r r = abs ( f ( x1 ) )
x0 = x1
x1 i s t h e s o l u t i o n
Exercise: Implement Newton-Raphson method for f(x) = tan(x) − ex
Kirit MakwanaDepartment of Physics, IIT Hyderabad
EP4210/EP24040 - Computational Physics 8 / 10
Convergence
Unlike bisection method, Newton method is not guranteed to
converge
It will converge only if you are close enough to the root
It can be shown that Newton method converges quadratically from a
starting point in a certain range under certain conditions complicated
conditions
However, these conditions are not easy to identify practically
Kirit MakwanaDepartment of Physics, IIT Hyderabad
EP4210/EP24040 - Computational Physics 9 / 10
Failure to converge
Kirit MakwanaDepartment of Physics, IIT Hyderabad
EP4210/EP24040 - Computational Physics 10 / 10