2008 г., Том 13, № 6, с.5-16

Во многих реальных ситуациях мы не знаем вероятностного распределения погрешностей, знаем только верхние границы для этих погрешностей. В таких случаях можно лишь заключить, что реальные (неизвестные) значения принадлежат некоторому интервалу. Базируясь на этой интервальной неопределенности, мы хотим найти возможные значения искомой функции неопределенных переменных. В общем, расчет этих значений - трудная задача, но в линейном приближении, справедливом для малых значений ошибок, существует линейный алгоритм такого расчета. В других ситуациях известен эллипсоид, содержащий искомые значения. В этом случае мы тоже имеем линейный по времени алгоритм расчета линейной функции. Иногда имеет место комбинация интервальной и эллипсоидной неопределенности, тогда искомые значения принадлежат пересечению эллипсоида и прямоугольника. В общем случае вычисление этого пересечения позволяет сузить поиск искомой функции. В этой статье мы приводим два алгоритма для оценки интервала линейной функции на пересечении в линейном времени: простой и более сложный линейно-временной алгоритмы. Оба алгоритма могут быть расширены на l^p случай, когда вместо эллипсоида мы имеем набор, определяемый l^p нормой.