Построение единой программной среды для решения задач глобальной оптимизации (стр. 4 из 9)
= x0 + x1e1 + x2e2 + … + xnen,
= y0 + y1e1 + y2e2 + … + ynen, и aÎR, то:
± = (x0± y0) + (x1 ± y1)e1 + (x2± y2)e2 + … + (xn± yn)en, a
= (ax0) + (ax1)e1 + (ax2)e2 + … + (axn)en,
± a = (x0 + a) + x1e1 + x2e2 + … + xnen Заметим, что разность
– равна 0, – полезное свойство, которое не верно в IA (или даже в GIA). Отсутствие таких тривиальных сокращений в IA является одним из источников взрыва ошибки. Когда примитивная операция Ф нелинейна, значение
не может быть выражено непосредственно как линейная комбинация ei. В этом случае, мы подбираем хорошую линейную аппроксимацию для Ф (“хорошую” в чебышевском смысле минимизации максимальной ошибки), и добавляем дополнительный член zkek для представления ошибки этой аппроксимации:
= z0 + z1e1 + z2e2 + … + znen + zkek. Здесь ek – новый шумовой символ и zk – верхняя граница ошибки аппроксимации. Выбор линейной аппроксимации должен принимать во внимание диапазоны операндов, которые подразумеваются аффинными формами
и , и, возможно, также их взаимосвязь. Отметим, что в отличие от GIA, число членов, используемых в аффинных формах, растет во время оценки формулы. (При необходимости, лишние члены могут быть объединены и заменены новыми шумовыми символами ценою некоторой потери точности) Важно заметить, что для дифференцируемой операции Ф граница ошибки zk хорошей чебышевской аппроксимации зависит квадратично от диапазонов операндов ||
|| и || ||. Т.о., если функция ¦ использует только дифференцируемые операции, то различие между действительным диапазоном ¦ и диапазоном, вычисленном в AA стремится к нулю в относительном смысле при сужении области. Напротив, внутренние ошибки IA (следствие неучтенных взаимосвязей) зависят линейно от размеров области; поэтому различие будет уменьшаться только в абсолютном смысле. Адекватные аппроксимационные алгоритмы были разработаны для основных арифметических операций и трансцендентных функций [5]. Например, при умножении двух аффинных форм
и мы можем использовать аппроксимацию z0 = x0y0, zi = x0yi + y0xi, zk = ||
||×|| ||. Граница ошибки ||
||×|| || не точна, а более чем в два раза больше максимальной ошибки. Для получения более точной границы, мы должны принять во внимание связь x и y, следующую из их аффинных форм, но еще не ясно, получим ли мы от этого выигрыш. Как описывалось применительно к IA, формулы для оценки примитивных функций в AA могут быть автоматически объединены в формулы для произвольно сложных функций. Этот факт и возможность преобразования позволяют AA просто заменить IA.
В качестве простого примера того, как AA обрабатывает проблему зависимости, рассмотрим оценку z = x(10 – x) в AA для x в интервале [4, 6]:
= 5 + 1e1 10 –
= 5 - 1e1
= (10 – ) = 25 + 0e1 + 1e2 [
] = [25 - 1, 25 + 1] = [24,26]. Т.о. AA вычисляет оценку очень близкую к [24, 25] – действительному диапазону z. С другой стороны, IA оценка есть [16, 36]. Если выражение x(10 – x) раскрыто в 10x – x2, то IA оценка становится значительно хуже, [4, 44], в то время как оценка в AA точна – [24, 25].
Смешанная интервально-аффинная арифметика
Преимущество аффинной арифметики над интервальной арифметикой всецело зависит от ее способности определить и использовать зависимости между операндами. Когда такая зависимость отсутствует, или случайно согласуется с консервативными предположениями IA, AA оценки могут быть шире, чем в IA – даже не смотря на то, что аффинная арифметика более точна, чем интервальная.
Объяснением этого парадоксального факта служит то, что IA пытается окружить график каждой элементарной функции ортогональным параллелепипедом минимального вертикального размера, в то время как AA ищет наклонный параллелепипед минимального объема. Например, рассмотрим операцию возведения в квадрат z = x2, для xÎ[1, 3]. IA дает (узкий) диапазон [1, 9] для z; а AA представляет x как
= 2+1e1, и производит = 4.5 + 4e1 + 0.5e2, чей диапазон [0, 9]. Заметим, что IA говорит только то, что пара (x, z) лежит в прямоугольнике площади 2 * 8 = 16, в то время как результат AA ограничен параллелограммом площади 2 * 1 = 2. Этот недостаток оценок диапазонов в AA, к сожалению, имеет тенденцию проявляться, когда в функции ¦ преобладают члены, подобные квадрату, оцениваемые возле своего минимума – именно там, где нам нужны точные нижние границы.
Эта проблема может быть решена путем объединения IA с AA. В этой смешанной модели каждая величина x представлена и аффинной формой
и стандартным интервалом [x]. Каждая операция z = Ф(x, y) выполняется в обеих вычислительных моделях . Интервальная часть [z] результата – это множество, являющееся пересечением диапазонов, вычисленных в IA и в AA; и AA-процедура использует интервалы [x] и [y] при выборе чебышевской аппроксимации для Ф. Таким образом, IA и AA находятся во взаимодействии на каждом шаге: явные интервалы, полученные IA, приводят к лучшим выборам для самых лучших линейных аппроксимаций и к меньшим значениям для члена ошибки zk; в то время как аффинные формы в AA позволяют сокращать связанные ошибки, и, следовательно, приводить к более узким интервалам. В частности, смешанная AAIA (affine arithmetic – interval arithmetic) схема вычисляет неотрицательные диапазоны для Ф(x) = x2, без потери информации о зависимости, обеспеченной AA. Управление ошибкой округления
Когда используется точная арифметика, IA и AA всегда вычисляют математически допустимые границы для диапазона значений последовательности операций. Эти границы могут включать реальный диапазон, но они всегда правильны. Однако IA и AA, будут выполняться на цифровом компьютере, который использует арифметику с плавающей точкой, которая подвержена ошибкам округления. Но все же IA и AA способны произвести математически допустимые границы на любом вычислительном устройстве, поддерживающем контроль над округлением. Наиболее современные вычислительные архитектуры обеспечивают контроль над ошибками округления, реализуя IEEE стандарт чисел с плавающей точкой [4].