ESO 208A: Computational
Methods in Engineering
Arghya Das
Department of Civil Engineering
IIT Kanpur
Copyright clause
“The instructor of this course owns the copyright of all the course materials.
This lecture material was distributed only to the students attending the course
ESO208A: Computational Methods in Engineering of IIT Kanpur, and should
not be distributed in print or through electronic media without the consent of
the instructor. Students can make their own copies of the course materials for
their use
Acknowledgement
Profs. Abhas Singh and Shivam Tripathi (CE)
Roots of Nonlinear
Equations
Roots of Equations
Not trivial to determine
the roots!
Roots of Non-Linear Equations:
f(x) = 0
f may be a function belonging to any class: algebraic, trigonometric, hyperbolic,
polynomials, logarithmic, exponential, etc.
Five types of methods can broadly be classified:
Graphical method
Bracketing methods: Bisection, Regula-Falsi
Open methods: Fixed point, Newton-Raphson, Secant, Muller
Special methods for polynomials: Bairstow’s
Hybrid methods: Brent’s
Background assumed (MTH 101): intermediate value theorem; nested interval
theorem; Cauchy sequence and convergence; Taylor’s and Maclaurin’s series; etc.
5
Graphical Method
Involves plotting f(x) curve and finding the
solution at the intersection of f(x) with x-axis.
6
Bracketing Methods
Intermediate value theorem: Let f be a continuous fn on [a, b]
and let f(a) < s < f(b), then there exists at least one x such that
a < x < b and f(x) = s.
Bracketing methods are application of this theorem with s = 0
Nested interval theorem: For each n, let In = [an, bn] be a
sequence of (non-empty) bounded intervals of real numbers
such that and ,
then contains only one point.
This guarantees the convergence of the bracketing methods to the root.
In bracketing methods, a sequence of nested interval is generated
such that each interval follows the intermediate value theorem with s
= 0. Then the method converges to the root by the one point specified
by the nested interval theorem. Methods only differ in ways to
generate the nested intervals.
7
Intermediate Value Theorem
8
Mean Value Theorem
If f(x) is defined and continuous on the interval [a,b] and
differentiable on (a,b), then there is at least one number c in the
interval (a,b) (that is a < c < b) such that
A special case of Mean
Value Theorem is Roll’s
Theorem when
Bisection Method
Principle: Choose an initial interval based on intermediate value
theorem and halve the interval at each iteration step to generate
the nested intervals.
Initialize: Choose a0 and b0 such that, f(a0)f(b0) < 0. This is done
by trial and error.
Iteration step k:
Compute mid-point mk+1 = (ak + bk)/2 and functional value f(mk+1)
If f(mk+1) = 0, mk+1 is the root. (It’s your lucky day!)
If f(ak)f(mk+1) < 0: ak+1 = ak and bk+1 = mk+1; else, ak+1 = mk+1 and
bk+1 = bk
After n iterations: size of the interval dn = (bn – an) = 2-n (b0 – a0),
stop if dn ≤ ε
Estimate the root (x = α say!) as: α = mn+1 ± 2-(n+1) (b0 – a0)
10
Bisection Method
11
Regula-Falsi or Method of False Position
Principle: In place of the mid point, the function is assumed to be
linear within the interval and the root of the linear function is chosen.
Initialize: Choose a0 and b0 such that, f(a0)f(b0) < 0. This is done by
trial and error.
Iteration step k:
A straight line passing through two points (ak, f(ak)) and (bk, f(bk)) is
given by:
Root of this equation at f(x) = 0 is:
If f(mk+1) = 0, mk+1 is the root. (It’s your lucky day!)
If f(ak)f(mk+1) < 0: ak+1 = ak and bk+1 = mk+1; else, ak+1 = mk+1 and bk+1 =
bk
After n iterations: size of the interval dn = (bn – an), stop if dn ≤ ε
Estimate the root (x = α say!) as:
12
Regula-Falsi or Method of False Position
y = f(x)
f(ak)
mk+1
bk
ak
f(bk)
13
