Created
July 16, 2015 17:52
-
-
Save kitsook/74039addca1b051c4e40 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package net.clarenceho.util; | |
import java.util.function.UnaryOperator; | |
import java.math.BigDecimal; | |
import java.math.RoundingMode; | |
/** | |
* Given equation y = f(x), find successively better approximations to the roots | |
* (or zeroes) of a real-valued function (i.e. find x where y = 0) | |
* <p> | |
* Example of using the method: <br> | |
* | |
* <pre> | |
* {@code | |
* FindZero fz = new FindZero(); | |
* assertTrue(closeEnough(fz.newtonMethod( | |
* // fx = x^2 - 2 * x - 4 | |
* (x) -> { | |
* return x.multiply(x).subtract(new BigDecimal("2.0").multiply(x)).subtract(new BigDecimal("4.0")); | |
* } , | |
* // dfx = 2 * x - 2 | |
* (x) -> { | |
* return new BigDecimal("2.0").multiply(x).subtract(new BigDecimal("2.0")); | |
* } , new BigDecimal("100")), new BigDecimal("3.23607"))); | |
* } | |
* </pre> | |
* | |
* @author Clarence Ho (clarenceho at gmail dot com) | |
* | |
*/ | |
public class FindZero { | |
private int count = 100; | |
private BigDecimal margin = new BigDecimal("0.0000000001"); | |
private int scale = 20; | |
/** | |
* Use default parameters | |
* <p> | |
* count = 100<br> | |
* margin = 0.0000000001<br> | |
* scale = 20<br> | |
*/ | |
public FindZero() { | |
} | |
/** | |
* Specify parameters for Newton's method | |
* | |
* @param count | |
* maximum loop count | |
* @param margin | |
* how close to zero we want to get to | |
* @param scale | |
* precision when doing BigDecimal division | |
*/ | |
public FindZero(int count, BigDecimal margin, int scale) { | |
this.count = count; | |
this.margin = margin; | |
this.scale = scale; | |
} | |
/** | |
* Using Newton's method to solve the equation | |
* | |
* @param fx | |
* implementation of function f(x) | |
* @param dfx | |
* implementation of function f'(x) | |
* @param init | |
* the initial guess of x | |
* @return result found, or null if exhausted the loop count but the result | |
* is not within margin | |
*/ | |
public BigDecimal newtonMethod(UnaryOperator<BigDecimal> fx, UnaryOperator<BigDecimal> dfx, BigDecimal init) { | |
BigDecimal x = init; | |
for (int i = 0; i < count; i++) { | |
// calculate value at this point | |
BigDecimal y = fx.apply(x); | |
if (y.abs().compareTo(margin) == -1) { | |
break; | |
} | |
BigDecimal yPrime = dfx.apply(x); | |
try { | |
x = x.subtract(y.divide(yPrime, this.scale, RoundingMode.HALF_UP)); | |
} catch (ArithmeticException e) { | |
return null; | |
} | |
} | |
if (fx.apply(x).abs().compareTo(margin) != -1) { | |
// no result found | |
return null; | |
} | |
return x; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment