Ограничение, основанное на константах Липшица

Потенциально недорогая, но неточная оценка функции может быть дана следующим выражением

B_{L ,W}¦ = ¦(x ^*) – Lw (W) £ ¦(x) £ ¦(x ^*) + Lw (W) = B^{L ,W}¦,

где x^* Î W, а L есть константа Липшица для функции ¦ на W, и w (W) служит верхней границей диаметра области W. Такая оценка имеет то преимущество, что она проста для вычисления, когда известна константа Липшица. Дополнительно она имеет следующее свойство

lim (B^{L ,W}¦ - B_{L ,W}¦) = 0 при w (W)® 0.

В то же время, главным недостатком этого метода является то, что если константа L велика, то оценка является недопустимо неточной. Также здесь не используется тот факт, что для данной функции константа Липшица сильно меняется на различных областях.

Интервальная арифметика

Интервальная арифметика (IA – interval arithmetic) – естественная тех­ника для оценки границ изменения функции. IA была введена Муром [2] с целью улучшения надежности численных вычислений. С тех пор она успешно приме­нялась для решения многих вычислительных задач, таких как обыкновенные дифференциальные уравнения, системы линейных уравнений и глобальная оптимизация.

В IA вещественное число x представимо парой чисел с плавающей точ­кой (a, b), соответствующих интервалу X = [ a, b ], гарантированно содержащему x, т.е. такому, что a £ x £ b. Таким образом, IA обеспечивает не только оценку для значения x, но и говорит о том, насколько хороша эта оценка. Реальная сила IA состоит в том, что мы можем оперировать интервалами, как если бы они были числами, и получать надежные оценки для результатов числовых вычислений.

Простые формулы легко получены для выполнения примитивных ариф­метических операций над интервалами. Интервальные расширения для сложных функций могут быть вычислены путем составления этих примитивных формул в том же порядке, в каком они составлены при вычислении непосредственно самой функции. Другими словами, любой алгоритм для вычисления функции, использующий примитивные операции может быть легко (и автоматически) пе­реведен в алгоритм для вычисления интервального расширения для этой же функции. Это особенно удобно выполнять в языках программирования, кото­рые поддерживают перегрузку операторов, но может быть выполнено в любом языке программирования, либо вручную, либо при помощи предварительной компиляции. Поскольку также относительно легко найти интервальное расши­рение для элементарных трансцендентных функций, таких как sin, cos, log и exp, класс функций, для которых интервальное расширение может быть легко (и ав­томатически) вычислено гораздо больше, чем класс рациональных полиноми­альных функций. Эти наблюдения иногда объединяют в Фундаментальную Теорему Интервальной Арифметики: каждая вычислимая функция имеет интервальное расширение, т.е. для любой вещественной функции ¦, заданной алгоритмом, существует интервальная функция F, такая, что F (X) Ê ¦(C) = {¦(x): x Î X } для каждого параллелепипеда X в области определения ¦. Причем lim F (X) = ¦(x), при сужении параллелепипеда X к любой точки x из области определения ¦.

Основной недостаток IA в том, что оценки диапазона могут быть намного шире, чем точные границы, иногда по сути бесполезные. Это в основном возникает из-за неявного предположения о том, что операнды в примитивных операциях взаимно независимы. Если это предположение ложно, то не все комбинации значений в интервалах-операндах будут достигнуты, и результирующий интервал, вычисленный в IA, может быть намного шире, чем реальный диапазон результирующей величины. В качестве критического примера рассмотрим расчет функции y(x) = x – x, где x Î [1, 5]. IA правила дают [-4, 4], в то время как реальный диапазон [0, 0]. Это иногда называется “проблемой зависимости” в IA.

Данный недостаток IA особенно сильно проявляется в длинных вычислительных цепях, где часто наблюдается “взрыв ошибки”: поскольку оценка продвигается ниже по цепи, относительная точность вычисленных интервалов уменьшается экспоненциально, и они вскоре становятся слишком широкими для использования. Подходы к решению проблемы зависимости в IA включают использование центрированных форм, обобщенной интервальной арифметики Хансена, и более новой – аффинной арифметики [5].