Function part 2
Bisection method for finding roots
• Root of function f: Value x such that f(x)=0
• E.g: square root of w=root of f(x) = x^2 - w
• If f(x)=0, then x^2-w=0, i.e. x= square root of (w)
• Requirement for bisection method:
• f must be continuous
• We must be given points xl and xr such that f(xl)
and f(xr) are not both positive or both negative
Bisection method- Basic iteration
• Basic iteration will bring xl and xr closer, while
maintaining invariant:
• Xl and xr have different signs or are zero
• Invariant is true initially
• Invariant + continuity = root exist between xl
and xr(both inclusive)
• We iterate till xl-xr less than or equal to ‘e’
• ‘e’-our desired error bound
Iteration
• Let xm=(xl+xr)/2
• Xm=midpoint of the interval (xl,xr)
• If f(xm) has same sign as f(xl) then set xl=xm
• Sign of xl did not change. Sign of xl continuous
to remain different from sign of xr.
• Else set xr=xm
Bisection method for finding square root of
2
• Double xl=0, //f(xl)=0-2 is negative
xr=2, //f(xr)=4-2 is positive
Xm, epsilon=0.00001;
While (xr-xl>=epsilon){
Xm=(xl+xr)/2;
If((xl*xl-2> 0 && xm*xm-2>0)||(xl*xl-2< 0 && xm*xm-
2<0)) xl=xm;
Else xr=xm;
}
Cout<<xl<<endl;
Remarks
• In each iteration, the interval (xl,xr) halves in
size.
• The size of the interval gives the error in the
root
• Thus the error in root halves in each iteration
Passing function as argument to
other functions
The function bisection to find square root
of 2
Double bisection (double xl, double xr, double epsilon)
{ bool xlis=(xl*xl-2)>0;
While(xr-xl>=epsilon){
Double xm=(xl+xr)/2;
Bool xmis=(xm*xm-2)>0;
If(xlis==xmis) xl=xm;
Else
Xr=xm;
}
Return xl;
}
• If we want to find cube root of three , what should we write?
A C++ function to find the root of any
mathematical function
• Passing an extra argument to bisection
• Argument specifies the mathematical function
whose root we want to find
• Representation of mathematical function
o Double f(double x){return x*x-2}
o Double g(double x){return x*x*x-3}
• Passing C++ function as argument to another
C++ function
Actual program
• Double f(double x) {return x*X-2}
Double g(double x){return x*x*X/3}
Int main()
{
Cout<<bisection(1,2,0.0001,f)<<endl;
Cout<<bisection(1,3,0.0001,g)<<endl;
}
//should print the square root of two and cube root
of three
How to pass a function to another ‘h’ to
another function ’B’
• Suppose ‘h’ has declaration
return type h(parameter1-type,..)
• In the parameter list of B we need to put the type of ‘h’
• The type of ‘h’ is
function <return type(parameter 1-type,...)>
• The function that we want to pass to bisection take a single double
argument and return a double.
• Hence their type is function<double(double)>
• So, bisection will have the declaration
Double bisection(double xl, double xr, double epsilon,
function<double(double)>h)
• Inside bisection we can write calls to h
#include<functional>
Double bisection (double xl, double xr, double epsilon,
function<double(double)>h)
{ bool xlis=(h(xl)>0);
While(xr-xl>=epsilon){
Double xm=(xl+xr)/2;
Bool xmis=(h(xm)>0);
If(xlis==xmis) xl=xm;
Else
Xr=xm;
}
Return xl;
}
Exercise
Default arguments
• When a function is called with less parameters
or without parameters, default values are
used for the operations.
• Variables lacking default values are written
first, followed by variables containing default
values.
• Default values are specified in function
prototype definition.
Function overloading
• C++ allows you to define multiple functions
with the same name, provided they have
different argument list.
• Functional polymorphism
