Numerical Analysis (Solution of Non-Linear Equations) part 2
Bisection MethodRegula-Falsi MethodMethod of iterationNewton - Raphson MethodMuller’s MethodGraeffe’s Root Squaring Method
Published on: Mar 3, 2016
Transcripts - Numerical Analysis (Solution of Non-Linear Equations) part 2
Method of iteration
Newton - Raphson Method
Graeffe’s Root Squaring
Definition: The equationDefinition: The equation
f (x) = 0 is called anf (x) = 0 is called an
algebraic, if it is purely aalgebraic, if it is purely a
polynomial in x;polynomial in x;
it is a transcendental if f (x)it is a transcendental if f (x)
contains trigonometric,contains trigonometric,
exponential or logarithmicexponential or logarithmic
For example,For example,
is an algebraic equation,is an algebraic equation,
are transcendental equations.are transcendental equations.
5 6 3 0x x x+ − + =
sinM E e E= −
log( 3) sin 0x
ax x e x+ − + =
To find the solution of anTo find the solution of an
equationequation ff ((xx) = 0, we find) = 0, we find
those values ofthose values of xx for whichfor which
ff ((xx) = 0 is satisfied.) = 0 is satisfied.
Such values ofSuch values of xx are calledare called
the roots ofthe roots of ff ((xx) = 0.) = 0.
Thus a is a root of anThus a is a root of an
equationequation ff ((xx) = 0, if and only) = 0, if and only
if,if, ff ((aa) = 0.) = 0.
Properties of anProperties of an
algebraic equationalgebraic equation
Every algebraic equationEvery algebraic equation
ofof n-thn-th degree, wheredegree, where nn
is a positive integer, hasis a positive integer, has
nn and onlyand only nn roots.roots.
Complex roots occur in pairs.Complex roots occur in pairs.
That is, if (That is, if (a + iba + ib) is a root of) is a root of
ff ((xx) = 0, then () = 0, then (a – iba – ib) is also a) is also a
root of this equation.root of this equation.
IfIf x = ax = a is a root ofis a root of ff ((xx) = 0, a) = 0, a
polynomial of degreepolynomial of degree nn, then, then
((x – ax – a) is a factor of) is a factor of ff ((xx). On). On
dividingdividing ff ((xx) by () by (x – ax – a) we obtain) we obtain
a polynomial of degree (a polynomial of degree (nn – 1).– 1).
Descartes rule of signs:Descartes rule of signs:
The number of positive roots of anThe number of positive roots of an
algebraic equationalgebraic equation ff ((xx) = 0 with real) = 0 with real
coefficients cannot exceed thecoefficients cannot exceed the
number of changes in sign of thenumber of changes in sign of the
coefficients in the polynomialcoefficients in the polynomial ff ((xx) = 0.) = 0.
Similarly, the number of negative rootsSimilarly, the number of negative roots
ofof ff ((xx) = 0 cannot exceed the number) = 0 cannot exceed the number
of changes in the sign of theof changes in the sign of the
coefficients ofcoefficients of ff ((-x-x) = 0.) = 0.
For example, consider anFor example, consider an
As there are three changes inAs there are three changes in
sign, so, the degree of thesign, so, the degree of the
equation is three, and hence theequation is three, and hence the
given equation will have all thegiven equation will have all the
three positive roots.three positive roots.
3 4 5 0x x x− + − =
Intermediate value property:Intermediate value property:
IfIf ff ((xx) is a real valued continuous) is a real valued continuous
function in the closed intervalfunction in the closed interval
IfIf ff ((aa) and) and ff ((bb) have opposite) have opposite
once; that isonce; that is ff ((xx) = 0 has at least) = 0 has at least
one root such thatone root such that
a x b≤ ≤
a bβ< <
Numerical methods for solvingNumerical methods for solving
either a transcendental equation oreither a transcendental equation or
an algebraic equation are classifiedan algebraic equation are classified
into two groups:into two groups:
Direct methodsDirect methods, which require no, which require no
knowledge of the initialknowledge of the initial
approximation of a root of theapproximation of a root of the
equationequation ff ((xx) = 0.) = 0.
Iterative methodsIterative methods, require first, require first
approximation to initiate iteration.approximation to initiate iteration.
How to get the firstHow to get the first
We can find the approximateWe can find the approximate
value of the root ofvalue of the root of ff ((xx) = 0) = 0
either byeither by graphical methodgraphical method
or by anor by an analytical methodanalytical method
Graphical methodGraphical method
The equationThe equation ff ((xx) = 0 can be) = 0 can be
rewritten asrewritten as ff11((xx) =) = ff22((xx) and the first) and the first
approximation to a root ofapproximation to a root of ff ((xx) = 0) = 0
can be taken as the abscissa of thecan be taken as the abscissa of the
point of intersection of the graphspoint of intersection of the graphs
ofof yy == ff11((xx) and) and yy == ff22((xx).).
For example, consider,For example, consider,
( ) sin 1 0f x x x= − − =
It can be written asIt can be written as xx – 1 =– 1 = sin xsin x..
Now, we shall draw the graphsNow, we shall draw the graphs
ofof yy =(=(xx -1) and-1) and y = sin xy = sin x
Answer !Answer !
The approximateThe approximate
value of the rootvalue of the root
is found to be 1.9is found to be 1.9
Analytical methodAnalytical method
This method is based onThis method is based on
‘intermediate value property’.‘intermediate value property’.
( ) 3 1 sin 0f x x x= − + =
(1) 3 1 sin 1 3 1 0.84147 1.64299
= − + × = − + = ÷
HereHere ff (0) and(0) and ff (1) are of(1) are of
opposite signs. Therefore, usingopposite signs. Therefore, using
intermediate value property weintermediate value property we
infer that there is at least oneinfer that there is at least one
root betweenroot between xx = 0 and= 0 and xx = 1.= 1.
This method is often used toThis method is often used to
find the first approximation to afind the first approximation to a
root of either transcendentalroot of either transcendental
equation or algebraic equation.equation or algebraic equation.
Hence, in analyticalHence, in analytical
method, we mustmethod, we must
always start with analways start with an
initial interval (initial interval (a, ba, b),),
so thatso that ff ((aa) and) and ff ((bb))
have opposite signs.have opposite signs.
Suppose, we wish to locate theSuppose, we wish to locate the
root of an equationroot of an equation ff ((xx) = 0 in an) = 0 in an
interval, say (interval, say (xx00,, xx11). Let). Let ff ((xx00) and) and ff
((xx11) are of opposite signs, such) are of opposite signs, such
thatthat ff ((xx00)) ff ((xx11) < 0.) < 0.
Then the graph of the functionThen the graph of the function
crosses thecrosses the xx-axis between-axis between xx00 andand
xx11, which guarantees the existence, which guarantees the existence
of at least one root in the intervalof at least one root in the interval
The desired root isThe desired root is
approximately defined by theapproximately defined by the
IfIf ff ((xx22) = 0, then) = 0, then xx22 is theis the
desired root ofdesired root of ff ((xx) = 0.) = 0.
However, ifHowever, if f (xf (x22) 0) 0 then thethen the
root may be betweenroot may be between xx00 andand xx22
oror xx22 andand xx11..
Now, we define the nextNow, we define the next
approximation byapproximation by
providedprovided ff ((xx00)) ff ((xx22) < 0, then the) < 0, then the
root may be found betweenroot may be found between xx00 andand
xx22 or byor by
providedprovided ff ((xx11)) ff ((xx22) < 0, then the) < 0, then the
root lies betweenroot lies between xx11 andand xx22 etc.etc.
Thus, at each step, we either find theThus, at each step, we either find the
desired root to the requireddesired root to the required
accuracy or narrow the range to halfaccuracy or narrow the range to half
the previous interval.the previous interval.
This process of halving the intervalsThis process of halving the intervals
is continued to determine a smalleris continued to determine a smaller
and smaller interval within which theand smaller interval within which the
desired root lies.desired root lies.
Continuation of this processContinuation of this process
eventually gives us the desired root.eventually gives us the desired root.
– 9– 9xx + 1 = 0+ 1 = 0
for the root betweenfor the root between
xx = 2 and= 2 and xx = 4 by the= 4 by the
bisection method.bisection method.
Solution GivenSolution Given ff ((xx) =) = xx33
– 9– 9xx + 1.+ 1.
HereHere ff (2) = -9,(2) = -9, ff (4) = 29.(4) = 29.
Therefore,Therefore, ff (2)(2) ff (4) < 0 and hence(4) < 0 and hence
the root lies between 2 and 4.the root lies between 2 and 4.
LetLet xx00 = 2,= 2, xx11 = 4. Now, we define= 4. Now, we define
as a first approximation to a root ofas a first approximation to a root of
ff ((xx) = 0 and note that) = 0 and note that ff (3) = 1, so(3) = 1, so
thatthat ff (2)(2) ff (3) < 0.(3) < 0. Thus the root liesThus the root lies
between 2 and 3between 2 and 3
= = =
We further define,We further define,
and note thatand note that ff ((xx33) =) = ff (2.5) < 0, so that(2.5) < 0, so that ff
(2.5)(2.5) ff (3) < 0. Therefore, we define the(3) < 0. Therefore, we define the
Similarly,Similarly, xx55 = 2 . 875 and= 2 . 875 and xx66 = 2.9375= 2.9375
and the process can be continued untiland the process can be continued until
the root is obtained to the desiredthe root is obtained to the desired
= = =
= = =
These results are presented in the table.These results are presented in the table.
nn xxnn f ( xf ( xnn ))
22 33 1.01.0
33 2.52.5 -5.875-5.875
44 2.752.75 -2.9531-2.9531
55 2.8752.875 -1.1113-1.1113
66 2.93752.9375 -0.0901-0.0901