Об эффективности автоматизированного поиска оптимальных приближений с гарантированной точностью в системах с плавающей точкой
Представлен метод автоматизированной параллельной минимаксной аппроксимации функций R полиномами Zbp из Zbp[x] – т. е. определенными над подмножеством рациональных b-ичных чисел конечной точности p. Такие полиномы гарантируют существование верхней границы абсолютной ошибки приближения, однако эти гарантии в литературе формулируются относительно всего множества действительных чисел R, что делает их, строго говоря, применимыми лишь в области абстрактного анализа в противоположность реализуемым численно, в конечной точности, систем нелинейных уравнений с помощью многомерного метода Хаусхолдера. Использование многомерного метода позволяет обобщить существующие реализации поиска минимаксных полиномов на случаи произвольных дифференцируемых на области определения функций. Цель публикации заключается в обеспечении заданной точности аппроксимации в наихудших случаях, поэтому расчет минимаксных полиномов выполняется с помощью длинной рациональной арифметики; его результаты округляются до чисел с плавающей запятой выбранной точности, и при этом обеспечиваются гарантии относительно численных ошибок не более половины единицы-на-последнем-месте (ULP) [1]. Полученные результаты, включающие в себя реализацию алгоритма Ремеза на основе многомерного метода Хаусхолдера и методов длинной рациональной арифметики, реализованы экспериментально и доступны читателю для верификации.
Авторы: А. А. Чусов, Ю. И. Ефимова
Направление: Информатика, вычислительная техника и управление
Ключевые слова: гарантии точности, многомерный метод Хаусхолдера, длинная рациональная арифметика, численные ошибки и гарантии ULP, алгоритм Ремеза, неравномерная аппроксимация функций
Открыть полный текст статьи