Feature #1173
Upper bound for value of poly in an interval
Description
Write a function which accepts a (univariate) polynomial f (with rational coeffs), and an interval [a,b] with rational end points; the functions returns a rational which is an upper bound for max(f(x) | x in [a,b]) and perhaps also a lower bound for min(f(x) | x in [a,b]).
Related issues
History
#1
Updated by John Abbott about 6 years ago
Updated by - Related to Bug #1171: RealRoots: first point is sometimes wrong? added
#2
Updated by John Abbott about 6 years ago
A while ago I read an article about this (perhaps "evaluating a polynomial over an interval"?). I no longer recall many details.
The main idea is to repeatedly subdivide the interval (not necessarily evenly), and recurse on the two "halves", then combine the results. The base case uses "Horner's algorithm" for intervals.
JAA believes that this could also be useful/interesting for the SC-Square project.
#3
Updated by John Abbott about 6 years ago
- Description updated (diff)
#4
Updated by John Abbott about 6 years ago
- Related to Feature #1176: interval arithmetic added