f(x) is assumed to be a continuous function defined on an interval [a,b] satisfying f(a)<0 and f(b)>0 (or the other way around). The algorithm generates a sequence of nested intervals [an,bn] ⊃ [an+1,bn+1]⊃… starting from [a1,b1]= [a,b] and converging an→c and bn→c as n→∞. The midpoint of each interval is at most half the width of the interval to the common limiting point, so this is used as error bound.
/*****************************************************************************
Treibergs Feb. 24, 2006
Bisection Method
Assumes f(x) is continuous on an interval a to b and that f is positive
on one endpoint and negative on the other. It generates nested intervals
that converge to the zero. If the midpoint happens to be zero we stop.
The theoretical root of the function, used to test the algorithm, is printed.
bisect.c
*****************************************************************************/
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
double
f ( double x );
int
main ( void )
{
double a, b, c, m, error;
int i=1;
printf ( "Bisection Algorithm\n\n" );
printf ( " Enter the left and right endpoints : " );
scanf ( "%lf %lf", &a, &b );
if( f(a)*f(b) >= 0.0 ) /* Bad inputs condition */
{
if ( f(a)*f(b) > 0.0)
printf(" Redo; The function takes the same sign at the endpoints.\n");
else
{
if ( f(a) == 0.0 )
printf(" The function is zero at %25.15g \n",a);
if ( ( a != b ) && (f(b) == 0.0) )
printf(" The function is zero at %25.15g \n",b);
}
}
else
{
if( b < a ) /* Swap a and b if b < a */
{
c = a;
a = b;
b = c;
}
error = b - a;
printf ( "\n\t Left\t\t Middle\t\t\tRight\t\tError\n");
for(i=1; i <= 20; i++)
{
m = (a + b)/2.0;
error = error / 2.0;
printf ("%19.15f%19.15f%19.15f %g\n", a, m, b, error );
if( f(m) == 0.0 )
{
printf(" The function is zero at %20.15g \n", m);
break;
}
else if ( f(a)*f(m) < 0.0 )
b = m;
else
a = m;
}
printf(" Actual root is %22.15f\n", sqrt(2.0) );
}
return EXIT_SUCCESS;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
double
f ( double x )
{
return 2.0 - x*x ;
}
/* Milicic's Program
bisection.c */
#include <stdio.h>
#define epsilon 0.0000001
double f (double x) {
return (x*x - 3) ;
}
int main() {
double L,M,R;
printf("Enter the left (L) and right (R) end of the interval\n");
printf("where the zero lies: ");
scanf("%lf %lf", &L, &R);
printf(" [%lf,%lf]\n",L,R);
if (f(L)*f(R) > 0)
printf(" No sign change ... exit!\n");
else {
do {
M = (L+R)/2.0;
if (f(L)*f(M) > 0)
L = M;
else
R = M;
printf(" [%lf,%lf]\n",L,R);
} while(R-L > epsilon);
printf("A zero is equal %lf\n",L);
}
}
/*****************************************************************************
Treibergs Feb. 24, 2006
Newton's Method.
If f is a differentiable function, then we seek a sequence x_n which gets
closer and closer to a zero of the function. Starting from an initial guess
x_n, a better approximation of the zero is derived as follows. We draw the
tangent line through the point on the graph (x_n,f(x_n)) with slope f'(x_n).
Then x_{n+1} is the point of intersection of the tangent line with the y-axis.
Once the approximations get close to the zero, the method superconverges:
the number of digits of accuracy doubles each iteration.
newton.c
*****************************************************************************/
# include <stdio.h>
# include <stdlib.h>
# include <math.h>
double
f ( double x );
double
df ( double x );
int
main ( void )
{
double x, y, d, t, tol;
int i=1;
printf ( "Newton's Method\n\n" );
printf ( " Enter the first approximation of the zero, tolerance : " );
scanf ( "%lf %lf", &x, &tol );
printf ( " n\t\t x_n\t\t\t |x_n - x_{n-1}|\n" );
printf ( "%4d %25.15f\n", i++, x );
do
{
d = df ( x );
if ( d == 0.0 )
{
printf ( "Derivative vanishes at %21.15f\n", x);
break;
}
y = x - f(x)/d;
t = fabs ( x - y );
printf ( "%4d %25.15f%25.15f\n", i++, y ,t);
if ( t < tol )
printf ( "\t\t\t\t\t |x_n - x_{n-1}| < Tolerance value.\n" );
x=y;
}
while ( ( t >= tol ) && ( i <= 20 ) );
printf ( "Actual ans=%19.15f\n", pow(7.0,1.0/3.0) );
return EXIT_SUCCESS;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
double /* Any function */
f ( double x )
{
return 7.0 - x*x*x ;
}
/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
double /* The derivative of the same function */
df ( double x )
{
return -3.0*x*x ;
}
/* Milicic's Program
Newton's Method */
#include <stdio.h>
#include <math.h>
#define epsilon 0.0000001
/* function */
double f(double x) {
return(x*x - 3);
}
/* derivative of f */
double df(double x) {
return(2*x);
}
int main() {
double x, oldx;
printf("Give an initial estimate of zero > ");
scanf("%lf",&x);
do {
oldx = x;
x = x - f(x)/df(x);
printf("%f\n",x);
} while (fabs(x-oldx) > epsilon);
printf("A zero is equal to: %lf", x);
}
/* Treibergs 2-27-6
Bisection
today.c */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
double
f( double x );
int
main ( void )
{
double a, b, m, error;
int i;
printf ( "Bisection Algorithm\n\n Enter left and right endpoints : ");
scanf ( "%lf %lf", &a, &b );
if( f(a)*f(b) > 0.0 )
printf (" The function must take different signs at the endpoints.\n");
else
{
error = b - a;
printf ("\t\tLeft\t\tMiddle\t\tRight\t\tError\n");
for ( i = 1; i <= 20; i++ )
{
m = (a + b)/2.0;
error = error/2.0;
printf ( "%19.15f%19.15f%19.15f %g\n", a, m, b, error );
if( f(a)*f(m) <= 0.0 )
b=m;
else
a=m;
}
printf ( " The actual root = %19.15f\n", sqrt(2.0) );
}
return EXIT_SUCCESS;
}
double
f ( double x )
{
return 2.0 - x*x;
}