Automatic evaluation of slope expansions

[eeshan9815]

ping @dpsanders Reference - Dietmar Ratz - An Optimized Interval Slope Arithmetic and its Application (http://www2.math.uni-wuppertal.de/~xsc/preprints/rep9604.pdf)

[codecov-io]

Codecov Report

Merging #69 into master will increase coverage by 2.8%. The diff coverage is 80.95%.

@@            Coverage Diff            @@
##           master      #69     +/-   ##
=========================================
+ Coverage   62.52%   65.33%   +2.8%     
=========================================
  Files          10       11      +1     
  Lines         467      551     +84     
=========================================
+ Hits          292      360     +68     
- Misses        175      191     +16

Impacted Files	Coverage Δ
src/IntervalRootFinding.jl	4.65% <ø> (ø)	:arrow_up:
src/slopes.jl	80.95% <80.95%> (ø)

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 5b7a8ab...9b0dfb4. Read the comment docs.

[lbenet]

Naive question: this seems very close to automatic differentiation. Can you explain the difference?

[eeshan9815]

@lbenet Slope Expansion usually returns much smaller intervals as compared to AD, especially as the interval size increases. Given below are the benchmarking results run on seven functions on the interval 0.75..1.75, and the slope is expanded about the mid of the interval.

│ Row │ Function │ Automatic Differentiation │ Slope Expansion       │
├─────┼──────────┼───────────────────────────┼───────────────────────┤
│ 1   │ f1       │ [-5.44573, 0.886249]      │ [-2.79917, 0.0521429] │
│ 2   │ f2       │ [-87.6875, 77.0625]       │ [-43.875, 38.25]      │
│ 3   │ f3       │ [-0.474861, 0.787211]     │ [-0.159199, 0.432842] │
│ 4   │ f4       │ [-2.97001, 21.0701]       │ [0.04, 0.326667]      │
│ 5   │ f5       │ [2.63258, 74.8333]        │ [6.03135, 33.2205]    │
│ 6   │ f6       │ [-94.5871, 115.135]       │ [-38.9908, 65.5595]   │
│ 7   │ f7       │ [-279.639, 167.667]       │ [-146.852, 67.0665]   │

[dpsanders]

As a general comment, it would be useful to provide more comments / documentation about the basic idea of the algorithm etc. And a link to the PDF if it's freely available.

[dpsanders]

Why do slopes usually perform better?

[eeshan9815]

There's a theorem given in the book by Kearfott (Theorem 1.10) which proves that the slope expansion always gives a tighter bound than the derivative even when w(x) approaches 0.

[dpsanders]

Sorry, forgot to send the review comments :/

[eeshan9815]

@dpsanders Updated the PR with the multidimensional slope function

[eeshan9815]

I have removed the multidim slope function from this PR and unified tests for Float64 and BigFloat

[eeshan9815]

Rebased on current master

[dpsanders]

Please add some documentation.

[dpsanders]

@eeshan9815 Is this ready?

[eeshan9815]

Yes, definitely.

[dpsanders]

Sorry, needs a rebase now.

[eeshan9815]

Done!

[dpsanders]

Thanks!