 |
- Author:
- Don Clugston (IP: 217.5.157.100)
- Timestamp:
- 06/11/08 15:18:05 (16 years ago)
- Comment:
Code formatting fix
Legend:
- Unmodified
- Added
- Removed
- Modified
-
ChapterMath
| v32 |
v33 |
|
| 226 | 226 | |
|---|
| 227 | 227 | The classic one dimensional ''root finding'' problem is: given a, b, and a real function f(real), find x such that f(x)==0 and a<=x<=b. |
|---|
| 228 | | If you can provide a range [a..b], such that f(a) and f(b) have opposite signs, the root can be found efficiently within that range. ('Efficiently' means with as few calls to f() as possible). Math.Bracket.findRoot uses an algorithm originally based on TOMS478 (Alefeld et. al.) which uses cubic interpolation where possible, degrading to slower-convergence methods when necessary. Significant speed and robustness enhancements have been made. |
|---|
| 229 | | TOMS478 and almost all other publically available algorithms suffer from extremely poor worst-case performance (the "industry standard" algorithm due to R.P. Brent can require ~40000 calls to f() for 80-bit reals); this implementation avoids such problems, making it 1.5X faster in the average case, and 200X faster in the worst case. Typically 10-15 calls to f are required to achieve full 80-bit precision. |
|---|
| | 228 | If you can provide a range [a..b], such that f(a) and f(b) have opposite signs, the root can be found efficiently within that range. ('Efficiently' means with as few calls to f() as possible). |
|---|
| | 229 | |
|---|
| | 230 | Math.Bracket.findRoot uses an algorithm originally based on TOMS478 (Alefeld et. al.) which uses cubic interpolation where possible, degrading to slower-convergence methods when necessary. Significant speed and robustness enhancements have been made. TOMS478 and almost all other publically available algorithms suffer from extremely poor worst-case performance (the "industry standard" algorithm due to R.P. Brent can require ~40000 calls to f() for 80-bit reals); this implementation avoids such problems, making it 1.5X faster in the average case, and 200X faster in the worst case. Typically 10-15 calls to f are required to achieve full 80-bit precision. |
|---|
| 230 | 231 | |
|---|
| 231 | 232 | For example, to solve x^5^ = 0.2 for x, knowing that x is between 0 and 5, use: |
|---|
| 232 | | --- |
|---|
| | 233 | {{{ |
|---|
| | 234 | #!d |
|---|
| 233 | 235 | real root = findRoot( (real x) { return pow(x, 5) - 0.2; }, 0.0, 5.0); |
|---|
| 234 | | --- |
|---|
| | 236 | }}} |
|---|
| | 237 | |
|---|
| 235 | 238 | This algorithm works more quickly if the bracket doesn't include zero. |
|---|
| 236 | 239 | By observing the IEEE number line again, you can see that if you can specify a range like 1e-5..5.0, you're giving this algorithm a lot less work to do than if you give a range including 0. |
|---|
|
 |
 |
|
 |
Copyright © 2006-2024 Tango. All Rights Reserved. | Page Width:
Static or
Dynamic
