sigma  1.0.0
Loading...
Searching...
No Matches
taylor_model.hpp
Go to the documentation of this file.
1#pragma once
2#include <algorithm>
3#include <cmath>
4#include <functional>
8#include <utility>
9
13
14namespace sigma {
15
50template<typename ValueType>
52public:
54 using size_type = std::size_t;
55
57 using value_t = ValueType;
58
61
64
67
69 using coeffs_t = typename taylor_t::coeffs_t;
70
73
76 using Order = typename taylor_t::Order;
77
79 static constexpr Order default_max_order() {
81 }
82
83 // --- Constructors and Assignment ----------------------------------------
84
92 TaylorModel() = default;
93
105 TaylorModel(interval_t(center, center), order) {}
106
117 TaylorModel(interval_t(lo, hi), order) {}
118
139 explicit TaylorModel(const interval_t& interval,
140 Order order = default_max_order()) :
141 m_polynomial_(interval, order) {
142 if(interval.empty()) { return; }
143 auto radius = interval.radius();
144 if(radius > 0 && m_polynomial_.coefficients().empty()) {
145 m_remainder_ = interval_t(-radius, radius);
146 } else {
147 m_remainder_ = interval_t(value_t{0}, value_t{0});
148 }
149 }
150
166 m_polynomial_(std::move(polynomial)),
167 m_remainder_(std::move(remainder)) {}
168
170 TaylorModel(const TaylorModel& other) = default;
171
173 TaylorModel(TaylorModel&& other) noexcept = default;
174
176 TaylorModel& operator=(const TaylorModel& other) = default;
177
179 TaylorModel& operator=(TaylorModel&& other) noexcept = default;
180
181 // -- State Accessors -----------------------------------------------------
182
189 const taylor_t& polynomial() const noexcept { return m_polynomial_; }
190
197 const interval_t& remainder() const noexcept { return m_remainder_; }
198
200 size_type max_order() const noexcept { return m_polynomial_.max_order(); }
201
203 value_t constant() const { return m_polynomial_.constant(); }
204
206 const coeffs_t& coefficients() const noexcept {
207 return m_polynomial_.coefficients();
208 }
209
211 size_type n_terms() const noexcept { return m_polynomial_.n_terms(); }
212
219 bool empty() const noexcept { return m_polynomial_.empty(); }
220
232 interval_t range() const { return m_polynomial_.bound() + m_remainder_; }
233
242 bool contains(value_t value) const {
243 if(empty()) { return false; }
244 return range().contains(value);
245 }
246
255 bool contains(const interval_t& interval) const {
256 if(interval.empty()) { return true; }
257 if(empty()) { return false; }
258 return range().contains(interval);
259 }
260
270 bool contains(const TaylorModel& other) const {
271 if(other.empty()) { return true; }
272 return contains(other.range());
273 }
274
285 std::string print_polynomial_form() const {
286 return m_polynomial_.print_polynomial_form();
287 }
288
299 std::string print_interval_form() const {
300 return range().print_interval_form();
301 }
302
305
306 // -- Arithmetic Operators ------------------------------------------------
307
319 if(empty()) { return *this; }
320 return TaylorModel(-m_polynomial_, -m_remainder_);
321 }
322
336 if(empty()) {
337 m_polynomial_ = taylor_t(value, Order(m_polynomial_.max_order()));
338 m_remainder_ = interval_t(value_t{0}, value_t{0});
339 return *this;
340 }
341 m_polynomial_ += value;
342 return *this;
343 }
344
363
376 return TaylorModel(*this) += value;
377 }
378
390 TaylorModel operator+(const TaylorModel& other) const {
391 return TaylorModel(*this) += other;
392 }
393
403 if(empty()) {
404 m_polynomial_ = taylor_t(-value, Order(m_polynomial_.max_order()));
405 m_remainder_ = interval_t(value_t{0}, value_t{0});
406 return *this;
407 }
408 m_polynomial_ -= value;
409 return *this;
410 }
411
425 return *this += -other;
426 }
427
440 return TaylorModel(*this) -= value;
441 }
442
454 TaylorModel operator-(const TaylorModel& other) const {
455 return TaylorModel(*this) -= other;
456 }
457
470 if(empty()) { return *this; }
471 m_polynomial_ *= value;
472 m_remainder_ *= value;
473 return *this;
474 }
475
505
518 return TaylorModel(*this) *= value;
519 }
520
532 TaylorModel operator*(const TaylorModel& other) const {
533 return TaylorModel(*this) *= other;
534 }
535
545 if(value == 0) { throw std::domain_error("Division by zero"); }
546 return *this *= value_t(1.0 / value);
547 }
548
564 return *this *= other.multiplicative_inverse();
565 }
566
578 return TaylorModel(*this) /= value;
579 }
580
593 TaylorModel operator/(const TaylorModel& other) const {
594 return TaylorModel(*this) /= other;
595 }
596
611
649 const std::vector<value_t>& outer_coeffs,
650 const std::function<interval_t(const interval_t&)>& nth_derivative) const;
651
652 // -- Rigorous Term Control (no Affine analogue) ---------------------------
653
672
693
694 // -- Comparison Operators ------------------------------------------------
695
708 bool operator==(const TaylorModel& other) const {
709 if(empty() != other.empty()) { return false; }
710 if(empty()) { return true; }
711 return m_polynomial_ == other.m_polynomial_ &&
712 m_remainder_ == other.m_remainder_;
713 }
714
724 bool operator!=(const TaylorModel& other) const {
725 return !(*this == other);
726 }
727
728private:
730 void assert_not_empty_() const {
731 if(empty()) { throw std::domain_error("TaylorModel is empty"); }
732 }
733
735 taylor_t m_polynomial_;
736
738 interval_t m_remainder_;
739};
740
741// -- Non-member functions -------------------------------------------------
742
761template<typename ValueType>
762std::ostream& operator<<(std::ostream& os, const TaylorModel<ValueType>& t) {
763 if(t.empty()) {
764 os << "∅";
765 return os;
766 }
767 os << t.range();
768 return os;
769}
770
786template<typename ValueType>
788 const TaylorModel<ValueType>& t) {
789 return t * value;
790}
791
792// -- Out-of-line definitions ------------------------------------------------
793
794template<typename ValueType>
796 -> TaylorModel& {
797 if(empty()) { return *this = other; }
798 if(other.empty()) { return *this; }
799 auto new_order = std::min(max_order(), other.max_order());
800 auto lhs = sweep_to_order(new_order);
801 auto rhs = other.sweep_to_order(new_order);
802 return *this = TaylorModel(lhs.m_polynomial_ + rhs.m_polynomial_,
803 lhs.m_remainder_ + rhs.m_remainder_);
804}
805
806template<typename ValueType>
808 -> TaylorModel& {
809 if(empty() || other.empty()) { return *this = TaylorModel(); }
810 auto new_order = std::min(max_order(), other.max_order());
811 auto lhs = sweep_to_order(new_order);
812 auto rhs = other.sweep_to_order(new_order);
813
814 const auto& p1 = lhs.m_polynomial_;
815 const auto& p2 = rhs.m_polynomial_;
816
817 value_t new_constant = p1.constant() * p2.constant();
818 coeffs_t kept, tail;
819 auto insert = [&](const monomial_t& mono, value_t coeff) {
820 if(mono.degree() <= new_order) {
821 kept[mono] += coeff;
822 } else {
823 tail[mono] += coeff;
824 }
825 };
826 for(auto&& [mono, coeff] : p2.coefficients()) {
827 insert(mono, p1.constant() * coeff);
828 }
829 for(auto&& [mono, coeff] : p1.coefficients()) {
830 insert(mono, coeff * p2.constant());
831 }
832 for(auto&& [mono1, coeff1] : p1.coefficients()) {
833 for(auto&& [mono2, coeff2] : p2.coefficients()) {
834 insert(mono1 * mono2, coeff1 * coeff2);
835 }
836 }
837
838 // Every term of tail has degree <= order(p1) + order(p2) == 2*new_order.
839 taylor_t tail_poly(value_t{0}, std::move(tail), Order(2 * new_order));
840 interval_t new_remainder =
841 tail_poly.bound() + p1.bound() * rhs.m_remainder_ +
842 p2.bound() * lhs.m_remainder_ + lhs.m_remainder_ * rhs.m_remainder_;
843 taylor_t new_poly(new_constant, std::move(kept), Order(new_order));
844 return *this = TaylorModel(std::move(new_poly), std::move(new_remainder));
845}
846
847template<typename ValueType>
849 const std::vector<value_t>& outer_coeffs,
850 const std::function<interval_t(const interval_t&)>& nth_derivative) const
851 -> TaylorModel {
852 assert_not_empty_();
853 auto order = max_order();
854 taylor_t new_poly = m_polynomial_.compose_(outer_coeffs);
855 interval_t bar_bound = m_polynomial_.bound() - m_polynomial_.constant();
856 interval_t enclosure = bar_bound + m_remainder_;
857 interval_t xi_range =
858 m_polynomial_.constant() + interval_t(value_t{0}, value_t{1}) * enclosure;
859 interval_t deriv_val = nth_derivative(xi_range);
860 value_t fact = detail::factorial<value_t>(order + 1);
861 interval_t new_remainder =
862 deriv_val * pow(enclosure, static_cast<int>(order + 1)) / fact;
863 return TaylorModel(std::move(new_poly), std::move(new_remainder));
864}
865
866template<typename ValueType>
868 assert_not_empty_();
869 if(range().contains(value_t{0})) {
870 throw std::domain_error("Division by zero");
871 }
872 auto order = max_order();
873 auto outer_coeffs =
874 detail::reciprocal_outer_coeffs(m_polynomial_.constant(), order);
875 return compose_(outer_coeffs, [order](const interval_t& xi) {
876 value_t sign = ((order + 1) % 2 == 0) ? value_t{1} : value_t{-1};
877 return sign * detail::factorial<value_t>(order + 1) /
878 pow(xi, static_cast<int>(order + 2));
879 });
880}
881
882template<typename ValueType>
884 -> TaylorModel {
885 assert_not_empty_();
886 coeffs_t kept, tail;
887 for(auto&& [mono, coeff] : m_polynomial_.coefficients()) {
888 if(mono.degree() <= new_order) {
889 kept[mono] = coeff;
890 } else {
891 tail[mono] = coeff;
892 }
893 }
894 taylor_t tail_poly(value_t{0}, std::move(tail),
895 Order(m_polynomial_.max_order()));
896 auto new_remainder = m_remainder_ + tail_poly.bound();
897 taylor_t new_poly(m_polynomial_.constant(), std::move(kept),
898 Order(new_order));
899 return TaylorModel(std::move(new_poly), std::move(new_remainder));
900}
901
902template<typename ValueType>
904 -> TaylorModel {
905 assert_not_empty_();
906 auto total_r = range().radius();
907 coeffs_t kept, swept;
908 for(auto&& [mono, coeff] : m_polynomial_.coefficients()) {
909 if(total_r != value_t{0} && std::fabs(coeff) / total_r < threshold) {
910 swept[mono] = coeff;
911 } else {
912 kept[mono] = coeff;
913 }
914 }
915 taylor_t swept_poly(value_t{0}, std::move(swept),
916 Order(m_polynomial_.max_order()));
917 auto new_remainder = m_remainder_ + swept_poly.bound();
918 taylor_t new_poly(m_polynomial_.constant(), std::move(kept),
919 Order(m_polynomial_.max_order()));
920 return TaylorModel(std::move(new_poly), std::move(new_remainder));
921}
922
923// -- Elementary functions ---------------------------------------------------
924
949template<typename T>
951 if(a.empty()) { return a; }
952 auto a_range = a.range();
953 if(a_range.lower() >= T(0.0)) { return a; }
954 if(a_range.upper() <= T(0.0)) { return -a; }
955 auto m = std::max(std::fabs(a_range.lower()), a_range.upper());
956 return TaylorModel<T>(typename TaylorModel<T>::interval_t(T(0.0), m),
957 typename TaylorModel<T>::Order(a.max_order()));
958}
959
975template<typename T>
977 return abs(a);
978}
979
999template<typename T>
1001 if(a.empty()) { return a; }
1002 if(a.range().lower() <= T(0.0)) {
1003 throw std::domain_error("TaylorModel has non-positive values.");
1004 }
1005 auto order = a.max_order();
1006 auto outer_coeffs = detail::sqrt_outer_coeffs(a.constant(), order);
1007 using interval_t = typename TaylorModel<T>::interval_t;
1008 return a.compose_(outer_coeffs, [order](const interval_t& xi) {
1009 T coeff = detail::half_falling_factorial<T>(order + 1);
1010 return coeff * pow(xi, T(0.5) - static_cast<T>(order + 1));
1011 });
1012}
1013
1032template<typename T>
1034 if(a.empty()) { return a; }
1035 auto order = a.max_order();
1036 auto outer_coeffs = detail::exp_outer_coeffs(a.constant(), order);
1037 using interval_t = typename TaylorModel<T>::interval_t;
1038 return a.compose_(outer_coeffs,
1039 [](const interval_t& xi) { return sigma::exp(xi); });
1040}
1041
1060template<typename T>
1062 if(a.empty()) { return a; }
1063 if(a.range().lower() <= T(0.0)) {
1064 throw std::domain_error("TaylorModel has non-positive values.");
1065 }
1066 auto order = a.max_order();
1067 auto outer_coeffs = detail::log_outer_coeffs(a.constant(), order);
1068 using interval_t = typename TaylorModel<T>::interval_t;
1069 return a.compose_(outer_coeffs, [order](const interval_t& xi) {
1070 T sign = (order % 2 == 0) ? T{1} : T{-1};
1071 return sign * detail::factorial<T>(order) /
1072 pow(xi, static_cast<int>(order + 1));
1073 });
1074}
1075
1106template<typename T, typename U>
1108 auto order = a.max_order();
1109 return detail::pow_impl(a, exp, [order](T v) {
1110 return TaylorModel<T>(v, typename TaylorModel<T>::Order(order));
1111 });
1112}
1113
1116
1119
1120} // namespace sigma
Pairs a Taylor polynomial with a remainder interval to guarantee Eq. .
Definition taylor_model.hpp:51
TaylorModel & operator+=(const TaylorModel &other)
Overwrites *this with the sum of *this and other.
Definition taylor_model.hpp:795
TaylorModel(value_t lo, value_t hi, Order order=default_max_order())
Constructs a TaylorModel from a lower and upper bound.
Definition taylor_model.hpp:116
typename taylor_t::interval_t interval_t
Definition taylor_model.hpp:72
float value_t
Definition taylor_model.hpp:57
TaylorModel compose_(const std::vector< value_t > &outer_coeffs, const std::function< interval_t(const interval_t &)> &nth_derivative) const
Evaluates a Taylor-model outer series about constant(), with a Lagrange remainder bound.
Definition taylor_model.hpp:848
TaylorModel operator*(const TaylorModel &other) const
Returns the product of *this and other.
Definition taylor_model.hpp:532
TaylorModel(const TaylorModel &other)=default
Makes a deep copy of other.
TaylorModel< T > abs(const TaylorModel< T > &a)
Absolute value of a TaylorModel.
Definition taylor_model.hpp:950
size_type max_order() const noexcept
Forwards to polynomial().max_order().
Definition taylor_model.hpp:200
std::string print_polynomial_form() const
Creates a string of the polynomial form of *this.
Definition taylor_model.hpp:285
TaylorModel operator*(value_t value) const
Returns the product of *this and value.
Definition taylor_model.hpp:517
TaylorModel< T > fabs(const TaylorModel< T > &a)
Absolute value of a TaylorModel.
Definition taylor_model.hpp:976
bool contains(const TaylorModel &other) const
Checks if *this contains other.
Definition taylor_model.hpp:270
TaylorModel operator+(value_t value) const
Returns the sum of *this and value.
Definition taylor_model.hpp:375
size_type n_terms() const noexcept
Forwards to polynomial().n_terms().
Definition taylor_model.hpp:211
typename taylor_t::monomial_t monomial_t
Definition taylor_model.hpp:66
typename taylor_t::coeffs_t coeffs_t
Definition taylor_model.hpp:69
TaylorModel operator-(value_t value) const
Returns the difference of *this and value.
Definition taylor_model.hpp:439
TaylorModel operator/(const TaylorModel &other) const
Returns the quotient of *this and other.
Definition taylor_model.hpp:593
TaylorModel & operator/=(const TaylorModel &other)
Overwrites *this with the quotient of *this and other.
Definition taylor_model.hpp:563
const taylor_t & polynomial() const noexcept
Definition taylor_model.hpp:189
TaylorModel multiplicative_inverse() const
Returns the multiplicative inverse of *this.
Definition taylor_model.hpp:867
const interval_t & remainder() const noexcept
Definition taylor_model.hpp:197
TaylorModel sweep_small(value_t threshold) const
Removes individually small coefficients, bounding them into the remainder.
Definition taylor_model.hpp:903
TaylorModel & operator=(const TaylorModel &other)=default
Assigns the value of other to this model.
TaylorModel(taylor_t polynomial, interval_t remainder)
Constructs a TaylorModel by re-wrapping a polynomial and a remainder.
Definition taylor_model.hpp:165
const coeffs_t & coefficients() const noexcept
Forwards to polynomial().coefficients().
Definition taylor_model.hpp:206
value_t constant() const
Forwards to polynomial().constant().
Definition taylor_model.hpp:203
bool operator!=(const TaylorModel &other) const
Checks if *this and other represent different models.
Definition taylor_model.hpp:724
TaylorModel operator/(value_t value) const
Returns the quotient of *this and value.
Definition taylor_model.hpp:577
TaylorModel operator-() const
Returns the additive inverse of *this.
Definition taylor_model.hpp:318
std::string print_interval_form() const
Creates a string of the interval form of *this.
Definition taylor_model.hpp:299
TaylorModel & operator-=(const TaylorModel &other)
Overwrites *this with the difference of *this and other.
Definition taylor_model.hpp:424
TaylorModel operator-(const TaylorModel &other) const
Returns the difference of *this and other.
Definition taylor_model.hpp:454
typename taylor_t::deviation_t deviation_t
Definition taylor_model.hpp:63
std::size_t size_type
Definition taylor_model.hpp:54
TaylorModel(const interval_t &interval, Order order=default_max_order())
Constructs a TaylorModel from an interval.
Definition taylor_model.hpp:139
bool empty() const noexcept
Checks if this TaylorModel represents the empty set.
Definition taylor_model.hpp:219
TaylorModel< T > pow(const TaylorModel< T > &a, const U &exp)
Power of a TaylorModel.
Definition taylor_model.hpp:1107
TaylorModel & operator+=(value_t value)
Overwrites *this with the sum of *this and value.
Definition taylor_model.hpp:335
TaylorModel & operator-=(value_t value)
Overwrites *this with the difference of *this and value.
Definition taylor_model.hpp:402
static deviation_t make_deviation()
Forwards to Taylor::make_deviation().
Definition taylor_model.hpp:304
TaylorModel(TaylorModel &&other) noexcept=default
Constructs a TaylorModel by moving other.
TaylorModel sweep_to_order(size_type new_order) const
Reduces *this to a lower truncation order, bounding the removed terms into the remainder.
Definition taylor_model.hpp:883
TaylorModel< ValueType > operator*(ValueType value, const TaylorModel< ValueType > &t)
Multiplies a scalar by a TaylorModel.
Definition taylor_model.hpp:787
Taylor< float > taylor_t
Definition taylor_model.hpp:60
TaylorModel & operator*=(value_t value)
Overwrites *this with the product of *this and value.
Definition taylor_model.hpp:469
TaylorModel & operator=(TaylorModel &&other) noexcept=default
Moves the value of other to this model.
TaylorModel & operator/=(value_t value)
Overwrites *this with the quotient of *this and value.
Definition taylor_model.hpp:544
bool contains(const interval_t &interval) const
Checks if *this contains interval.
Definition taylor_model.hpp:255
TaylorModel()=default
Constructs an empty TaylorModel.
interval_t range() const
Returns an interval enclosing the values *this models.
Definition taylor_model.hpp:232
std::ostream & operator<<(std::ostream &os, const TaylorModel< ValueType > &t)
Outputs the range of a TaylorModel to an output stream.
Definition taylor_model.hpp:762
TaylorModel< T > sqrt(const TaylorModel< T > &a)
Square root of a TaylorModel.
Definition taylor_model.hpp:1000
bool operator==(const TaylorModel &other) const
Checks if *this and other represent the same model.
Definition taylor_model.hpp:708
TaylorModel operator+(const TaylorModel &other) const
Returns the sum of *this and other.
Definition taylor_model.hpp:390
typename taylor_t::Order Order
Definition taylor_model.hpp:76
TaylorModel< T > log(const TaylorModel< T > &a)
Natural logarithm of a TaylorModel.
Definition taylor_model.hpp:1061
TaylorModel(value_t center, Order order=default_max_order())
Constructs a TaylorModel from a constant value.
Definition taylor_model.hpp:104
TaylorModel< T > exp(const TaylorModel< T > &a)
Exponential of a TaylorModel.
Definition taylor_model.hpp:1033
TaylorModel & operator*=(const TaylorModel &other)
Overwrites *this with the product of *this and other.
Definition taylor_model.hpp:807
bool contains(value_t value) const
Checks if *this contains value.
Definition taylor_model.hpp:242
static constexpr Order default_max_order()
The truncation order used when none is specified.
Definition taylor_model.hpp:79
Implements truncated multivariate polynomial algebra.
Definition taylor.hpp:46
Monomial monomial_t
Definition taylor.hpp:58
static deviation_t make_deviation()
Definition taylor.hpp:721
Interval< value_t > interval_t
Definition taylor.hpp:64
std::map< monomial_t, value_t > coeffs_t
Definition taylor.hpp:61
static constexpr Order default_max_order()
The truncation order used when none is specified.
Definition taylor.hpp:85
Monomial::variable_t deviation_t
Definition taylor.hpp:55
The primary namespace for the sigma library.
Definition affine.hpp:12
Affine< T > exp(const Affine< T > &a)
Calculate the exponential of an affine form.
Definition exponents.ipp:31
TaylorModel< float > TMFloat
Typedef for a Taylor model of floats.
Definition taylor_model.hpp:1115
TaylorModel< double > TMDouble
Typedef for a Taylor model of doubles.
Definition taylor_model.hpp:1118
Shared implementation of pow() for Affine, Taylor, and TaylorModel.
X pow_impl(const X &a, const U &power, MakePoint &&make_point)
Implements x^y, shared by Affine::pow, Taylor::pow, and TaylorModel::pow.
Definition pow.hpp:55
Shared helpers for building the outer Taylor series of the elementary functions (exp,...
T half_falling_factorial(std::size_t k)
Definition series_detail.hpp:48
T factorial(std::size_t k)
Returns k! as a value_t.
Definition series_detail.hpp:25
std::vector< T > log_outer_coeffs(T c, std::size_t order)
Definition series_detail.hpp:72
std::vector< T > reciprocal_outer_coeffs(T c, std::size_t order)
Outer-series coefficients of 1/x about c: (-1)^k / c^(k+1).
Definition series_detail.hpp:86
std::vector< T > exp_outer_coeffs(T c, std::size_t order)
Definition series_detail.hpp:60
std::vector< T > sqrt_outer_coeffs(T c, std::size_t order)
Outer-series coefficients of sqrt(x) about c: sqrt(c) * C(1/2,k) / c^k.
Definition series_detail.hpp:99
Defines the Taylor class.