//==========================================
// Numerical Analysis WorkSheet Bisection Approximation
//==========================================
// Bisection approximation for solving a single variable
// equation. This applet applies the Bisection Method to find>
// a root x of an equation of the form f(x)=0, for a given
// function f. The inputs to the applet are the function f(x),
// interval endpoints [a,b], tolerance e > 0, and the number
// of iterations. Subclass of Numerical Worksheet.
//
//
<< Bisection.java >>
//
//===========================================
// Copyright (C) 1999-2005 Dana M. Proctor
// Version 2.8 5/11/2005
//
// This program is free software; you can redistribute it and/or
// modify it under the terms of the GNU General Public License
// as published by the Free Software Foundation; either version
// 2 of the License, or (at your option) any later version. This
// program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied
// warranty of MERCHANTABILITY or FITNESS FOR A
// PARTICULAR PURPOSE. Seebr the GNU General Public
// License for more details. You should have received a copy
// of the GNU General Public License along with this program;
// if not, write to the Free Software Foundation, Inc., 59 Temple
// Place, Suite 330, Boston, MA 02111-1307 USA
// (http://opensource.org)
//
//============================================
// Revision History
// Changes to the code should be documented here and reflected
// in the present version number. Author information should
// also be included with the original copyright author.
//=============================================
// Version 1.0 Original Stand Alone Applet.
//
1.1 Additional Error Checking of Input Data.
//
1.2 Sub-Division into Numerical WorkSheet.
//
1.3 Addition of Code to Save Output List Data.
//
1.4 Additional Error Checking of Input Data
//
and Elimination of Clearing the TextField
//
Upon Errors.
// 1.5 Intermediate Output.
// 1.6 Package Creation/Inclusion.
//
1.7 Minor Change check_data to getCheck_Data.
//
1.8 mainBisection Class Method b=null Finished.
//
1.9 Creation of Two Constructor Methods.
//
2.0 Creation of Class Method getBisection_Root.
//
2.1 GPL Inclusion & Basic JavaDoc Information.
//
2.2 getFunctionValue Changed to NA_Utils Class.
// 2.3 Algorithm Source Documentation.
// 2.4 Format Intermediate Output Data.
// 2.5 Fix for Invalid Decimal Place in Tolerance
//
2.6 Output Data Column Spacing via the Format Menu.
// 2.7 Fraction Input Implementation for Doubles.
//
2.8 Correction of NA_Utils.convertFractionString.
//
//--------------------------------------------------------------------
//
danap_n_mt@users.sourceforge.net
//=============================================
package net.danap.numericalworksheet;
/**
* The Bisection root approximation method implementation class.
*
* @author Dana M. Proctor
* @version 2.8 5/11/2005
*/
class Bisection
{
//=============================================
// Creation of the class and instance field data types needed
// to perform the Bisection Algorithm.
//=============================================
private static double bisectionRoot;
private static boolean externalRoot=false;
private int n, colWidth, decimalPlaces;
private double endPointA, endPointB, tolerance;
//=============================================
// Bisection constructor used during normal access by the
// Worksheet User. Default constructor object creation only
// allowed by the class method:
//
<< mainBisection() >>
//=============================================
private Bisection()
{
super();
}
//=============================================
// Bisection constructor that will allowed an outside class
// access to the bisection approximation. Constructor new
// object creation must be accessed through:
// << getBisection_Root() >>
//=============================================
private Bisection(double A, double B)
{
endPointA = A;
endPointB = B;
tolerance = 0.0000001;
n = 100;
}
//==============================================
// Instance method for checking user's input and returning a
// error response to the output List in the Numerical
// Worksheet if the data is incorrect.
//==============================================
private boolean getCheck_Data()
{
// Instance Method Local Variables.
String pass_string;
String error_string1 = ("Input data format incorrect.");
String error_string2 = ("Endpoint A needs to be less than Endpoint B.");
String error_string3a = ("The input interval, [A,B], endpoints evaluate in the function with");
String error_string3b = ("the same sign. Try smaller or alternate interval.");
String error_string4 = ("The number of interations needs to larger than zero.");
// Obtaining Input Data from Appropriate Panel
if (!externalRoot)
{
try
{
pass_string = BisectionPanel.getData("endPointA");
if (pass_string.indexOf('/') != -1)
pass_string =
NA_Utils.convertFractionString(pass_string);
endPointA = (Double.valueOf(pass_string)).doubleValue();
pass_string = BisectionPanel.getData("endPointB");
if (pass_string.indexOf('/') != -1)
pass_string = NA_Utils.convertFractionString(pass_string);
endPointB = (Double.valueOf(pass_string)).doubleValue();
pass_string = BisectionPanel.getData("tolerance");
if (pass_string.indexOf('/') != -1)
pass_string = NA_Utils.convertFractionString(pass_string);
tolerance = (Double.valueOf(pass_string)).doubleValue();
// Determining the formatting of the output data with
// dependence on tolerance. Allow for at least SSXXXX.d
int pos = pass_string.index(".");
decimalPlaces = pos == -1 ? 0: pass_string.substring(pos).length();
colWidth =
decimalPlaces + OutputPanel.getOutputColumnSpacing();
pass_string =
BisectionPanel.getData("iterations");
n = Integer.parseInt(pass_string);
}
catch (NumberFormatException e)
{
OutputPanel.clearOutputData();
OutputPanel.setOutputDataln(error_string1);
return false;
}
}
// Checking Endpoint A Less Than Endpoint B.
if (endPointA >= endPointB)
{
OutputPanel.clearOutputData();
OutputPanel.setOutputDataln(error_string2);
return false;
}
// Checking f(A) and f(B) Opposite Sign.
if (NA_Utils.getFunctionValue(endPointA)*
NA_Utils.getFunctionValue(endPointB) > 0)
{
OutputPanel.clearOutputData();
OutputPanel.setOutputDataln(error_string3a);
OutputPanel.setOutputDataln(error_string3b);
return false;
}
// Checking Iterations Larger than Zero.
if (n <= 0)
{
OutputPanel.clearOutputData();
OutputPanel.setOutputDataln(error_string4);
return false;
}
return true;
}
//===============================================
// Processing the input data with the Bisection Algorithm
// to find the root. Also outputs values in the process
// to the List output in the Numerical Worksheet.
//===============================================
private void process_data()
{
// Instance Method Local Variables.
double p, fa, fp, fx;
boolean intermediateData = false;
boolean iterationsExceeded = true;
String error_string5 = ("Iterations completed without finding root within Tolerance.");
// Determining and Setting Intermediate Data Identification.
if (!externalRoot)
{
OutputPanel.clearOutputData();
intermediateData = BisectionPanel.getStateCheckbox();
if (intermediateData)
{
// Providing some heaser information about the
// intermediate data.
String
colWidthSpace = "";
for (int i=1; i<(colWidth-2); i++)
colWidthSpace = colWidthSpace + " ";
OutputPanel.setOutputDataln(" n" + colWidthSpace + "A" +
colWidthSpace + "B" +
colWidthSpace + "x" +
colWidthSpace + "f(x)");
}
}
// Actual Algorithm for Bisection.
// Numerical Analsis 6th Edition
// By Richard L. Burden & J. Douglas Faires
// 1997, Algorithm 2.1
int i = 1;
fa = NA_Utils.getFunctionValue(endPointA);
while (i <= n)
{
p = endPointA + (endPointB-endPointA)/2;
fp = NA_Utils.getFunctionValue(p);
// Test for Termination fp!=0?
//if ((Math.abs(p - fp) < tolerance) |
//(Math.abs(p-fp)/Math.abs(p)
//(Math.abs(fp) < tolerance))
// Original Algorithm Termination
if ((fp == 0) || ((endPointB - endPointA)/2 < tolerance))
{
bisectionRoot = p;
if (intermediateData & !externalRoot)
OutputPanel.setOutputDataln(NA_Utils.format(i, 4, 0) +
NA_Utils.format(endPointA, colWidth, decimalPlaces) +
NA_Utils.format(endPointB, colWidth, decimalPlaces) +
NA_Utils.format(p, colWidth, decimalPlaces) +
NA_Utils.format(fp, colWidth, decimalPlaces));
if (!externalRoot)
OutputPanel.setOutputDataln(" Root = "+p);
i = n;
iterationsExceeded = false;
}
else if (intermediateData & !externalRoot)
OutputPanel.setOutputDataln(NA_Utils.format(i, 4, 0) +
NA_Utils.format(endPointA, colWidth, decimalPlaces) +
NA_Utils.format(endPointB, colWidth, decimalPlaces) +
NA_Utils.format(p, colWidth, decimalPlaces) +
NA_Utils.format(fp, colWidth, decimalPlaces));
if (fa * fp > 0)
{
endPointA = p;
fa = fp;
}
else
endPointB = p;
i++;
}
// Outputting Error if Iterations Completed Without
// Finding a Root.
if (iterationsExceeded & !externalRoot)
OutputPanel.setOutputData(error_string5);
// Misc. Format for Intermediate Data Output.
if (intermediateData & !externalRoot)
OutputPanel.setOutputData("");
}
//==============================================
// Class method for an outside class to call in order to
// obtain the root of the input equation at a specific
// point using the Bisection algorithmn.
//==============================================
/**
* A public class for the implementation of a the bisection
* polynomial root approximation given input values of
* type double.
*
* @param A Endpoint approximation less than root.
* @param B Endpoint approximation larger than root.
* @return Root
*/
public static double getBisection_Root(double A, double B)
{
// Non-Standard Bisection WorkSheet Panel
// Root Approximation.
externalRoot = true;
// Calling the Constructor for External
// Root Approximation.
Bisection b1 = new Bisection(A, B);
b1.getCheck_Data();
b1.process_data();
// Return State of Bisection Class Field
// and Root that was Found.
externalRoot = false;
return bisectionRoot;
}
//=================================================
// Creation of the main Bisection class method to be called
// from the Numerical Worksheet when this method is selected
// and the execute approximation button is pressed.
//=================================================
protected static void mainBisection()
{
int ID = 0;
Bisection b = new Bisection();
if (b.getCheck_Data())
{
b.process_data();
OutputPanel.saveOutputData(ID);
}
b = null;
}
}