[go: up one dir, main page]
Scribd
Upload
19 views6 pages

2-Basic Def. and Bisection Method

The document discusses root finding methods for algebraic and transcendental equations, defining exact and approximate roots. It outlines various techniques such as direct, graphical, trial & error, and iterative methods, including the bisection method, and emphasizes the importance of convergence and order of convergence. Additionally, it covers the intermediate value theorem and properties of polynomial equations regarding the number of roots.

Uploaded by

devangivarshnay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
19 views6 pages

2-Basic Def. and Bisection Method

The document discusses root finding methods for algebraic and transcendental equations, defining exact and approximate roots. It outlines various techniques such as direct, graphical, trial & error, and iterative methods, including the bisection method, and emphasizes the importance of convergence and order of convergence. Additionally, it covers the intermediate value theorem and properties of polynomial equations regarding the number of roots.

Uploaded by

devangivarshnay
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 6

Session-2

Root finding
Algebraic Equation: An equation f(x) = 0 is called an algebraic equation if f(x) is a
polynomial. Otherwise, it is considered a transcendental equation, which includes
equations involving elementary functions such as non-polynomials, logarithmic,
trigonometric, exponential, or hyperbolic functions.
x3 x 2
Examples: 3x  11x  14  0,
5 2
 50 are algebraic equations whereas
4 7
x1/2  3x5/3  1  0, x 2  3cos x  1  0, xe x  2  0, x ln x  1.2  0 are transcendental
equation.

In this course, we will solve both algebraic and transcendental equations.

Exact Zeros/Roots of f(x) = 0: A number  , which may be real or complex, is said to


be exact zero (or root) of an equation if f ( )  0 .
3
Examples: 2 is a root of x 2  3x  10  0 whereas is a root of 1  sin x  0 .
2
x
sin x  2 has no solution, sin x  0.5 has infinitely many solutions and sin x  has
2
x
three solutions because y  sin x and y  intersects only at three points.
2
Geometrically, a root of the equation f(x) = 0 is a value of x at which the graph of f(x)
crosses the x-axis.

Approximate Number: A number  , which may be real or complex, is said to be


approximate root of an equation f ( x)  0 if x    0 .

Example: 1.999 and 2.001 are approximate roots of x 2  3x  10  0


Aim : To find a root of the equation f(x) = 0.

There are several methods to find the roots of both algebraic and transcendental
equations. These include: (1) Direct Methods, (2) Graphical Methods, (3) Trial & Error
Methods, (4) Iterative Methods.

In direct methods, the root of the equation is obtained directly without the need for
any initial approximations. These methods can provide all the roots exactly in a finite
number of steps.

In iterative methods, an initial approximation to the root of the equation 𝑓(𝑥) = 0 is


assumed, and this approximation is successively improved using an iterative formula
until the desired accuracy is achieved. These methods may give only one root at a time.

Example: To solve x3 + x2 – 1 = 0, we may choose any one of the following iterative


formula:

xn1  (1  xn )1/2 or xn1  (1  xn3 )1/2 or xn1  (1  xn 2 )1/3 for n  0, 1, 2, . . .


The convergence of the sequence  xn  to a number  , the root of the equation

depends on the rearrangement of above iterative formula and the choice of starting
initial approximation x0 .

Convergence of Method: Let  xn  be a sequence of approximations of a root 

obtained by a method. Then the method is said to be convergent if lim xn    0 .


n

Example: The following are the successive approximations of x log10 x  1.2  0 : 2.8,
2.741, 2.74068, 2.74065, 2.74065, . . . Thus, the obtained approximations converge to
an exact root of x log10 x  1.2  0 .
Order of Convergence: A method is said to be of order p if p is the largest number
(need not be an integer) for which there exists a finite constant c such that

xn1    c xn   i.e.,  n1  c n p where xn are successive approximations of the


p

root  .

Note: In practice, except in rare cases, it is not possible to find  which satisfies the

given equation exactly. We, therefore, attempt to find an approximate root  * such that

either  
f *   or xn1  xn   , where xn1 and xn are two successive

approximates and  is the prescribed error tolerance.

Intermediate value theorem :


If f(a) f(b) < 0, then there exists one real root to the equation f(x) = 0 lies in the interval
(a, b).
Example :
1. To find a root of x3 + x2 – 1 = 0.
Here f(x) = x3 + x2 – 1 and f(0)f(1) < 0.
There exists a real root lies between 0 and 1 to the equation f(x) = 0.
2. To find a root of x3 – 9x-1 + 1 = 0.
Here f(x) = x3 – 9x + 1 and f(0)f(1) < 0.
There exists a real root lies between 0 and 1 to the equation f(x) = 0.

Note : - Let the polynomial equation to be solved is


f(x) = anxn + an-1xn-1 + an-2xn-2 + …+ a1x + a0 = 0
(1) The number of positive roots of f(x) = 0 cannot exceed the number of sign
changes (p) in f(x)
(2) The number of negative roots of f(x) = 0 cannot exceed the number of sign
changes (q) in f(-x)
(3) With the points (1) and (2), the number of real roots will not exceed p+q.
(4) The number of roots of an nth degree polynomial equation has exactly n roots.
(This is the fundamental theorem on algebra)
(5) Imaginary roots occur in pairs.
(6) An odd degree polynomial equation has at least one real root.
Method of bisection :
If the function f(x) satisfies f(a0)f(b0) < 0, then the equation f(x) = 0 has a real root lies
in the interval (a0, b0).
Let m1 = (a0 + b0 )/2.
If f(m1) = 0, then m1 is the required root.
If f(m1) ≠ 0, then the required root of f(x) = 0 lies either in (a0, m1) or (m1, b0).
Replacing this procedure a number of times, we obtain the bisection method as
ak  bk
mk 1  , k  0,1,2,...
2
 a , m  if f (ak ) f  mk 1   0
where  ak 1, bk 1    k k 1
  mk 1, bk  if f (mk 1 ) f  bk   0

Repeat the above procedure until required accuracy is met.


That means, the successive mid point values meet the required accuracy.

Ex : - Find a root of the equation x3 – x – 4 =0 by bisection method upto 3 decimal


accuracy.
Solution : - Here f(x) = x3 – x – 4, f(0) = -4, f(1) = -4, f(2) = 2
Since f(1)f(2) < 0, then there exists a root lies between 1 and 2.
ak  bk
In the following table, f(ak)f(bk) < 0 and mk 1 
2
k (ak, bk) mk+1
0 (1, 2) 1.5
1 (1.5, 2) 1.75
2 (1.75, 2) 1.875
3 (1.75, 1.875) 1.8125
4 (1.75, 1.8125) 1.78125
5 (1.78125, 1.8125) 1.796875
6 (1.78125, 1.796875) 1.7890625
7 (1.7890625, 1.796875) 1.792969
8 (1.792969, 1.796875) 1.794922
9 (1.794922, 1.796875) 1.795898

You might also like