001: /*
002: * Copyright 2004 The Apache Software Foundation.
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016:
017: package org.apache.commons.math.analysis;
018:
019: import java.io.IOException;
020: import org.apache.commons.math.ConvergenceException;
021: import org.apache.commons.math.FunctionEvaluationException;
022:
023: /**
024: * Implements <a href="http://mathworld.wolfram.com/NewtonsMethod.html">
025: * Newton's Method</a> for finding zeros of real univariate functions.
026: * <p>
027: * The function should be continuous but not necessarily smooth.
028: *
029: * @version $Revision: 348791 $ $Date: 2005-11-24 12:50:36 -0700 (Thu, 24 Nov 2005) $
030: */
031: public class NewtonSolver extends UnivariateRealSolverImpl {
032:
033: /** Serializable version identifier */
034: private static final long serialVersionUID = 2606474895443431607L;
035:
036: /** The first derivative of the target function. */
037: private transient UnivariateRealFunction derivative;
038:
039: /**
040: * Construct a solver for the given function.
041: * @param f function to solve.
042: */
043: public NewtonSolver(DifferentiableUnivariateRealFunction f) {
044: super (f, 100, 1E-6);
045: derivative = f.derivative();
046: }
047:
048: /**
049: * Find a zero near the midpoint of <code>min</code> and <code>max</code>.
050: *
051: * @param min the lower bound for the interval
052: * @param max the upper bound for the interval
053: * @return the value where the function is zero
054: * @throws ConvergenceException if the maximum iteration count is exceeded
055: * @throws FunctionEvaluationException if an error occurs evaluating the
056: * function or derivative
057: * @throws IllegalArgumentException if min is not less than max
058: */
059: public double solve(double min, double max)
060: throws ConvergenceException, FunctionEvaluationException {
061: return solve(min, max, UnivariateRealSolverUtils.midpoint(min,
062: max));
063: }
064:
065: /**
066: * Find a zero near the value <code>startValue</code>.
067: *
068: * @param min the lower bound for the interval (ignored).
069: * @param max the upper bound for the interval (ignored).
070: * @param startValue the start value to use.
071: * @return the value where the function is zero
072: * @throws ConvergenceException if the maximum iteration count is exceeded
073: * @throws FunctionEvaluationException if an error occurs evaluating the
074: * function or derivative
075: * @throws IllegalArgumentException if startValue is not between min and max
076: */
077: public double solve(double min, double max, double startValue)
078: throws ConvergenceException, FunctionEvaluationException {
079:
080: clearResult();
081: verifySequence(min, startValue, max);
082:
083: double x0 = startValue;
084: double x1;
085:
086: int i = 0;
087: while (i < maximalIterationCount) {
088: x1 = x0 - (f.value(x0) / derivative.value(x0));
089: if (Math.abs(x1 - x0) <= absoluteAccuracy) {
090:
091: setResult(x1, i);
092: return x1;
093: }
094:
095: x0 = x1;
096: ++i;
097: }
098:
099: throw new ConvergenceException(
100: "Maximum number of iterations exceeded " + i);
101: }
102:
103: /**
104: * Custom deserialization to initialize transient deriviate field.
105: *
106: * @param in serialized object input stream
107: * @throws IOException if IO error occurs
108: * @throws ClassNotFoundException if instantiation error occurs
109: */
110: private void readObject(java.io.ObjectInputStream in)
111: throws IOException, ClassNotFoundException {
112: in.defaultReadObject();
113: derivative = ((DifferentiableUnivariateRealFunction) f)
114: .derivative();
115: }
116: }
|