Root Finding Method

A root finding algorithm is a numerical method of finding an x for a given function f such that f(x)=0. This particular value of x is the root. There are many different methods of finding roots of a function. Below are sum of them.

Bisection Method:

Bisection method is a simple root finding method. It requires prior knowledge of the value of a continuous function f at the endpoints of a given interval [a,b] where the root exist. The function value at the endpoints must have different signs (i.e (f(a)*f(b))<0). Using the Intermediate Value Theorem, bisection method iterates and reduces the interval [a,b] into halves, disregarding the \frac{1}{2} [a,b] where no sign change occurs. It will iterate until it converges to the root or the level of desired accuracy is reached.

Bisection_method
Bisection Method

Bisection Method Algorithm:

  1. Input \epsilon (i.e level of accuracy)
  2. Set a, b, (The interval)
  3. Compute midpoint=\frac{a+b}{2}
  4. If f(midpoint)=0, midpoint=root
  5. If f(midpoint)>0 (i.e function is positive at the midpoint), replace midpoint with the endpoint where function was positive
  6. If f(midpoint)<0 (i.e negative), replace midpoint with endpoint where function was negative
  7. If (b-a)>\epsilon (if root is not found and level of desired accuracy is not reached, repeat 3-6)

The bisection method algorithm constructs the sequence {c_n} that will converge to a root of the given function that is \lim_{k \rightarrow \infty} c_n =r

The following is a python code to find the root of a given function using bisection method:

#Bisection Method
#Sidafa Conde
#MTH 361
from math import*
def F(x):
#Defines the function here
f=pow(x,2)-4
return f
def bisection():
a=float(input(“Left Interval: “))
b=float(input(“Right Interval: “))
N=int(input(“How many iterations? “))
Fleft=F(a) #computes the left function value
Fright=F(b) #computes the right function value
if Fleft*Fright<0: #when a sign change occur
for i in range (0,N,1): #Iteration
a=a
b=b
c=(a+b)/2 #computes the midpoint of the interval
print(c)
Fmid=F(c) #Midpoint interval value
Fleft=F(a) #Left interval value
Fright=F(b) #right interval value
#print(Fmid)
if  Fleft*Fmid<0: #if the sign change happens on the first half of the interval
a=a
b=c
elif Fmid*Fright<0:#if the sign change happens on the second half of the interval
a=c
b=b
elif math.fabs(a-b)<10**-10:
print(“root is:”)
print(c)

This code is written to compute the optimal maximum number of iteration. You only need to give it a tolerance level.

Multiple Partitioning Method

Many question arises. If we can bisect the interval [a,b] on which f(x) is continuous on, is it not better to do multiple partitions? To answer this question, one must define ‘better’. Let k=2,3,4.... be the number of partitions. Is it better to do k partitions in terms of number of iterations required? Is it better to do k partitions in terms of work?

let n \geq 1 be the number of iterations and a_{n},b_{n},c_{n} denote the n^{th} value of a, b, c.

b_{n+1}-a_{n+1}=\frac{1}{k}(b_n-a_n)b_n-a_n =\frac{1}{k^{n-1}}(b-a), (b-a) is the original interval.

\exists a root= \alpha in [a_n,c_n] or [c_n,b_n] (i.e the new interval where sign change occur). Hence: ( \alpha - c_n) \leq (c_n-a_n) =(b_n-c_n) = \frac{1}{k} (b_n - a_n) . Combining the two equations together, we get:

|\alpha -c_n| \leq (c_n-a_n) = (b_n-c_n) = \frac{1}{k} [\frac{1}{k^{n-1}} (b-a)]. Simplifies to

|\alpha -c_n| \leq (c_n-a_n) = b_n-c_n=\frac{1}{k^n}(b-a). From calculus 2, we know that \frac{1}{k^n} will converge when n >1. Therefore, c_n \Rightarrow \alpha as n \Rightarrow \infty.

If \frac{1}{k^n}(b-a) \geq \epsilon \Rightarrow |\alpha -c_n| \geq \epsilon. Solving for n, we get:

n \leq \frac{\log( \frac{\epsilon}{b-a})}{\log(k)}.

By the property of the inequality above, as k \Rightarrow \infty the number of iteration required to find the root x= \alpha will decrease. Bisection (i.e k=2) requires more iterations to find the root of a given function f(x) then Trisection(i.e k=3).

The graph above shows the number of iterations decreasing as the number of partitions increase.

Which method is better with respect to how much work done(i.e what is the cost)?

We know that there are (k-1) function evaluation. If we multiply this by the number of iteration, we should get the cost. With just some algebra, work \leq \frac{\log( \frac{\epsilon}{b-a})}{\log(k)}(K-1). By the property of this inequality, as the number of partitions increase (i.e k \Rightarrow \infty) it would require more work, more computation to converge to a root.

The following is the modified bisection method code into multi-partition method:

%To find the root of f(x)=0 in the interval of (a,b) using n partition
clear all, close all, clc
f = @(x) x.^3; %given function
a=10; %left endpoint of the interval
b=-10; %right endpoint of the interval
n= 4; % number of partitions (2 for bisection, 3 for trisection, etc…)
ep=10e-15; %tolerance lebvel
nmax=abs(log(ep/(b-a))/log(2)); %calculates the number of iteration needed
Nmax=ceil(nmax); %number of iteration
ya=f(a); yb=f(b); %computes the function value at the endpoint of the given interval
if ya*yb > 0,display ‘no root in this interval’,break,end %if no sign change
%while abs(b-a)>ep %iterate the program until the level of desired accuracy is achieved
for j=1:Nmax
x= linspace(a,b,n+1);% divide the interval into equal section with respect to n
for i=1:(n);
if (f(x(i))*f(x(i+1)))<=0; %when a sign change occur
tempa=x(i); %lower endpoint of the interval assignment
tempb=x(i+1); % upper endpoint of the interval assignment
end
end

a=tempa; b=tempb;
end
root=a

The partition methods (i.e bisection, trisection, etc…) are guarantee to find a root to a given function on interval.

The above methods of root finding are also refered to as Two-Point Methods. The following methods will be One-Point Method, requiring only one initial guess.

Fixed-Iteration Method:

A fixed point x^* of a given function g(x) satisfies g(x^*)=x^*. Given a continuous function g(x) \in [a,b], x \in [a,b] & g(x) \in [a,b] (i.e the function maps it domain onto itself g: [a,b] \Rightarrow [a,b]

Proof (fixed point)

  1. If g(a)=a, fixed point is a
  2. If g(b)=b, fixed point is b
  3. If g(x) satisfy a \leq g(x) \leq b, \forall a\leq x \leq b, then g(x) has a fixed point in [a,b].

When is fixed point unique?

Given that the same conditions above are satisfied:

if g'(x) exist on [a,b] and that \exists 0 < k < 1 \forall x \in [a,b], the fixed point x^* is unique.

Proof: suppose that p and q are fixed point of g(x) (i.e g(p)=p & g(q)=q).

By the Mean Value theorem of derivative, |p-q| = |g(p)-g(q)| = |g'( \xi)(p-q)| \leq |g'( \xi)||p-q| \leq k|p-q|, where \xi \in [p,q].

|p-q| \leq k|p-q|<|p-q|, \therefore p=q. p=q is a unique point.

How to find fixed point?

It needs an initial point p_0. p_1=g(p_0), p_2=g(p_1) \hdots p_{n+1}=g(p_n) this is the fixed point iteration.

Proof:

let p=g(p) (i.e fixed point). p_0, p_1, P_2 \hdots p_n, p_{n+1} are the sequence of guesses.

|p_{n+1}-p|=|g(p_n)-g(p)| \Rightarrow MVT \Rightarrow |g'( \xi)(p+n-p)|=|g'( \xi)||p_n-p| \leq k|p_n-p|.

\frac{g(p_n)-g(p)}{p_n-p}=g'( \xi) where \xi is b/n p_n and p.

“]cosinefixedpoint
f(x)=cos( p*x) on [-pi/2, pi/2 Courtesy of Andrew Perry's code

Fixed point is the solution of the equation x=g(x), as shown on the image above. The fixed point iteration algorithm  will generate the sequence p is the fixed point of the given function (i.e p=g(p)).

I am trying to learn Python. So I’ve written a fixed point iteration code in Python as well.

#Fixed Iteration Method
#Sidafa Conde
#MTH 361
import math
def F(x): #Defines the function here
f=8/(x+2)
return f
def fixedpoint():
p=[]
p.insert(0,4) #initial condition
for i in range(0,19,1):
t=p[i]
x=F(t)
p.insert(i+1,x)
print(p[i])

To find the root of a given function f(x)=0, this can be written in the fixed point iteration (x=g(x)) for some g(x) so that the fixed-point of g(x) become the root of the f(x). A good g(x) is very important.

Example: Say you wish to find the root of f(x)=x^3-2x-5. You may use g_1(x)=\frac{x^3-5}{2} or g_2(x)=(2x+5)^{\frac{1}{3}} (just solving f(x) for x). Using the code above, you will the following output with initial condition of x_0=2:

g_1(x) does not converge:

2
1.5
-0.8125
-2.76818847656
-13.1061306749
-1128.12436634
-717861967.275
-1.84966397745e+26
-3.16408775755e+78

Whereas g_2(x) will converge:

2
2.08008382305
2.0923506778
2.09421699601
2.09450065219
2.09454375753
2.09455030781
2.09455130318
2.09455145444
2.09455147742
2.09455148092
2.09455148145
2.09455148153
2.09455148154

This selection of g_1(x)=\frac{x^3-5}{2} is not a good choice. f(2.09455148154)=-2.596856063519226e-11

Newton Method:

Given a function f(x) and whose f'(x) continuous near a root r, then the newton’s method can be used to produce a sequence {{p_k}} that converges faster than Bisection method. Newton method is also a one-point method (i.e it only requires one initial guess), whereas the bisection is a two-point method.

Newton method uses the tangent line at one point, the initial guess x_0, on the given function y=f(x). The equation of the tangent at the initial guess is the  written as the following:

y-f(x_0)=f'(x_0)(x-x_0)

Newton’s Method Theorem:

Assume that f(x) \in C[a,b] & \exists root r \in [a,b] such that f(r)=0. The Newton’s Method sequence is defined by the following iteration:

x_{k+1}=f(x)={x_k}-\frac{f(x_k)}{f'(x_k)} for k \geq 0

This is x_{k+1} is the intersection about the x-axis of the tangent line above. For the next iteration, our initial guess is replaced by the x-intercept obtain in the first calculation. This iteration will continue until the root r is found or the user is satisfied with level of accuracy.

The Newton Method iteration, similar to the fixed point iteration, will converge to the root r for any initial guess close to the root and if f'(x) \neq 0 on [a,b].

Python Code for Newton Method:

#Sidafa Conde
#Newton Method
#MTH 361
from math import*
def F(x): #Defines the function here
f=pow(x,3)+2*x-4
return f
def F1(x): #derivative function
f=3*pow(x,2)+2
return f
def newtonmethod():
p=[]
p.insert(0,1) #initial condition
for i in range(0,10,1):
t=p[i]
x=p[i]-(F(t)/F1(t)) #newton method formula
p.insert(i+1,x)
print(p[i])

I will test this code to find sqrt(2)=1.41421356237 with 20 iterations. I will the function as f(x)=x^2-2. x_0=5. Here is the program output:

5
2.7
1.72037037037
1.44145536818
1.41447098137
1.4142135858
1.41421356237
1.41421356237
1.41421356237
1.41421356237
1.41421356237
1.41421356237
1.41421356237
1.41421356237
1.41421356237
1.41421356237
1.41421356237
1.41421356237
1.41421356237

There are times when Newton Method’s starting point enters a cycle. Lets take f(x)= x^3 -2x +2 and start it at x_0 = 0

0
1.0
0.0
1.0
0.0
1.0
0.0
1.0
0.0
1.0
0.0
1.0
0.0
1.0
0.0
1.0
0.0
1.0
0.0
The sequence will oscillate between the two without converging to a root.

3 Responses to Root Finding Method

  1. daFeda says:

    Hi, our blogs are rather similar. It seems as you have stopped posting though, which is a real shame as it is high-quality stuff!
    I’ve only read your discussion on the bisection method, and it is really nice.
    Thanks for sharing.

  2. mustafa says:

    find the root of y= x 3 + 2x – 5 using bisection method ? please help

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: