Алгоритм Remez представляет собой методологию определения минимаксного рационального приближения к функции. Эта статья дает краткий обзор метода, но его не следует рассматривать как тщательное теоретическое лечение, для чего следует обратиться к любимому учебнику.

Представьте, что вы хотите аппроксимировать некоторую функцию f(x) посредством рациональной функции R(x), где R(x) может быть либо многочленом P(x), либо соотношением двух многочленов P(x)/Q(x) (рациональная функция). Сначала мы сосредоточимся на полиномиальном случае, поскольку с ним намного легче справиться, а затем перейдем к полностью рациональному функциональному случаю.

Мы хотим найти «лучшее» рациональное приближение, где «лучшее» определяется как приближение, имеющее наименьшее отклонение от f(x). Мы можем измерить отклонение с помощью функции ошибки:

E_abs(x) = f(x) - R(x)

это выражается в терминах абсолютной ошибки, но мы можем также использовать относительную ошибку:

E_rel(x) = (f(x) - R(x)) / |f(x) |

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

Затем минимаксная рациональная функция R(x) определяется как функция, которая дает наименьшее максимальное значение функции ошибки. Чебышев показал, что для R(x) существует уникальное решение minimax, обладающее следующими свойствами:

Это означает, что если мы знаем местоположение экстремумы функции ошибки, то мы можем написать N+2 одновременные уравнения:

R(x_i) + (-1)ⁱE = f(x_i)

где E - максимальный термин ошибки, а x_i - значения абсциссы N+2 экстрема функции ошибки. Затем тривиально решить одновременные уравнения для получения полиномиальных коэффициентов и термина ошибки.

К сожалению, мы не знаем, где находится экстремум функции ошибки!

The Remez Method

Метод Ремеза представляет собой итеративную технику, которая, учитывая широкий спектр предположений, будет сходиться на крайности функции ошибки и, следовательно, минимаксного решения.

В следующем обсуждении мы будем использовать конкретный пример для иллюстрации метода Ремеза: приближение к функции e^x   в диапазоне [-1, 1].

Прежде чем мы сможем начать метод Ремеза, мы должны получить начальное значение для местоположения экстремумы функции ошибки. Мы могли бы «угадать» их, но гораздо более близкое первое приближение может быть получено путем первого построения интерполированного полиномиального приближения к f(x).

Для получения коэффициентов N+1 интерполированного полинома нам нужны точки N+1 (x₀...x_N): при прохождении нашей интерполированной формы через каждую из тех точек, которые дают одновременные уравнения N+1:

f(x_i) = P(x_i) = c₀ + c₁x_i ... + c_Nx_i^N

Что может быть решено для коэффициентов c₀...c_N в P(x).

Очевидно, что это не минимакс-решение, на самом деле наша единственная гарантия заключается в том, что f(x) и P(x) касаются точек N+1, вдали от этих точек ошибка может быть произвольно большой. Однако мы бы хотели, чтобы это первоначальное приближение было как можно ближе к f(x), и оказывается, что использование нулей ортогонального полинома в качестве начальных точек интерполяции является хорошим выбором. В нашем примере мы будем использовать нули чебышевского полинома, поскольку их особенно легко вычислить, интерполируя для полинома 4 степени, и измерив относительную ошибку , получим следующую функцию ошибки:

Что имеет пиковую относительную погрешность 1,2x10^-3.

Хотя это уже довольно хорошее приближение, судя по форме функции ошибки, мы можем явно сделать лучше. Перед тем, как приступить к работе над методом Ремеза, у нас есть еще один шаг: найти все экстремумы функции ошибки и сохранить эти местоположения в качестве начальных точек управления Чебышева.

Note

В простом случае полиномиального приближения путем интерполяции через корни чебышевского полинома мы фактически создали Чебышевское приближение к функции: с точки зрения абсолютная ошибка это лучший априорный выбор для интерполированной формы, который мы можем достичь, и, как правило, очень близок к минимаксному решению. Однако если мы хотим оптимизировать для относительную ошибку, или если приближение является рациональной функцией, то исходное решение Чебышева может быть довольно далеко от идеального решения minimax. Более техническое обсуждение теории можно найти в этом курсе online.

Remez Step 1

Первым шагом в методе Ремеза, учитывая наш текущий набор контрольных точек Н+2 Чебышева x_i, является решение одновременных уравнений N+2:

P(x_i) + (-1)ⁱE = f(x_i)

Для получения погрешности используют термин E и коэффициенты полинома P(x).

Это дает нам новое приближение к f(x), которое имеет ту же ошибку E в каждой из контрольных точек, и чья функция ошибки изменяется в знаке в контрольных точках. Однако это не обязательно решение минимакса, так как контрольные точки могут находиться не на пределе функции ошибки. После этого первого шага вот как выглядит функция ошибки приближения:

Очевидно, что это все еще не минимаксное решение, так как контрольные точки не расположены на экстремуме, но максимальная относительная ошибка теперь снизилась до 5,6x10^-4.

Remez Step 2

Второй шаг состоит в том, чтобы найти экстремумы нового приближения, что мы делаем в два этапа: во-первых, поскольку функция ошибки изменяет знак в каждой контрольной точке, мы должны иметь корни ошибки N+1, расположенные между каждой парой контрольных точек N+2. Как только эти корни найдены стандартными методами поиска корней, мы знаем, что N экстрема заключены в скобки между каждой парой корней, плюс еще два между конечными точками диапазона и первым и последним корнями. Экстрему N+2 можно найти, используя стандартные методы минимизации функций.

Теперь у нас есть выбор: многоточечный обмен или одноточечный обмен.

В одноточечном обмене мы перемещаем контрольную точку, ближайшую к наибольшей экстремуме, к значению абсиссы экстремы.

В многоточечной бирже мы меняем все текущие контрольные точки на места экстрема.

В нашем примере мы осуществляем многоточечный обмен.

Iteration

Затем метод Ремеза выполняет этапы 1 и 2 выше итеративно до тех пор, пока контрольные точки не будут расположены в экстремуме функции ошибки: это затем решение minimax.

В нашем текущем примере еще две итерации сходятся в решении minimax с пиковой относительной ошибкой 5x10^-4 и функцией ошибки, которая выглядит следующим образом:

Rational Approximations

Если мы хотим распространить метод Ремеза на рациональное приближение формы

f(x) = R(x) = P(x) / Q(x)

где P(x) и Q(x) являются многочленами, то мы действуем как прежде, за исключением того, что теперь у нас есть N+M+2 неизвестных, если P(x) имеет порядок N, а Q(x) имеет порядок M. Это предполагает, что Q(x) нормализуется таким образом, что его ведущий коэффициент равен 1, что дает полиномиальные коэффициенты N+M+1 в целом, плюс термин ошибки E.

Одновременные уравнения, которые необходимо решить, теперь:

P(x_i) / Q(x_i) + (-1)ⁱE = f(x_i)

Оценивается на контрольных точках N+M+2 x_i.

К сожалению, эти уравнения нелинейны в термине ошибки E: мы можем решить их, только если знаем E, и все же E является одним из неизвестных!

Метод, обычно используемый для решения этих уравнений, является итеративным: мы угадываем значение E, решаем уравнения, чтобы получить новое значение для E (а также полиномиальные коэффициенты), а затем используем новое значение E в качестве следующего предположения. Метод повторяется до тех пор, пока Е не сходится на стабильном значении.

Эти осложнения значительно увеличивают время работы, необходимое для разработки рациональных приближений. Часто желательно получить рациональное, а не полиномиальное приближение не менее: рациональные приближения часто будут соответствовать более сложным для приближения функциям, с большей точностью и с большей эффективностью, чем их полиномиальные альтернативы. Например, если мы возьмем наш предыдущий пример приближения к e^x, мы получим точность 5x10^-4 с полиномом порядка 4. Если мы переместим два неизвестных в знаменатель, чтобы дать пару полиномов порядка 2 и повторно свести к минимуму, то пиковая относительная ошибка упадет до 8,7x10^-5. Это в 5 раз больше точности для того же количества терминов в целом.

Practical Considerations

Большинство трактатов по теории приближения останавливаются на этом. Однако с практической точки зрения большая часть работы включает в себя поиск правильной аппроксимирующей формы, а затем убеждение метода Ремеза сходится на решении.

До сих пор мы использовали прямое приближение:

f(x) = R(x)

Но это сойдется к полезному приближению только в том случае, если f(x) будет гладким. Кроме того, ошибки округления при оценке рациональной формы означают, что это никогда не приблизится, чем в пределах нескольких эпсилонов точности машины. Поэтому эта форма прямого приближения часто используется для ситуаций, когда мы хотим эффективности, а не точности.

Первым шагом в улучшении ситуации является, как правило, разделение f(x) на доминирующую часть, которую мы можем точно вычислить другим методом, и медленно меняющийся остаток, который может быть приближен рациональным приближением. У нас может возникнуть соблазн написать:

f(x) = g(x) + R(x)

где g(x) является доминирующей частью f(x), но если f(x)/g(x) приблизительно постоянны в интервале интереса, то:

f(x) = g(x)(c + R(x))

Здесь c является константой, которая является приблизительным значением f(x)/g(x) и R(x) обычно крошечным по сравнению с c. В этой ситуации, если R(x) оптимизирован для абсолютной ошибки, то до тех пор, пока его ошибка невелика по сравнению с постоянной c, эта ошибка будет эффективно устранена при добавлении R(x) к c.

Трудная часть, очевидно, заключается в том, чтобы найти правильный g(x) для извлечения из вашей функции: часто асимптотическое поведение функции даст подсказку, поэтому, например, функция erfc становится пропорциональной e^-x2/x по мере того, как x становится большим. Следовательно, используя:

erfc(z) = (C + R(x)) e^-x2/x

как примерная форма кажется очевидной вещью, чтобы попытаться, и действительно дает полезное приближение.

Тем не менее, сложность становится одной из сходящихся минимакс-решений. К сожалению, известно, что для некоторых функций метод Ремеза может привести к дивергентному поведению, даже если начальное приближение достаточно хорошее. Кроме того, не редкость, когда решение, полученное на первом шаге Ремеза выше, является плохим: решаемые уравнения, как правило, «жесткие», часто очень близкие к единственному, и если решение найдено вообще, ошибки округления и быстро меняющаяся функция ошибок могут привести к ситуации, когда функция ошибок фактически не изменяет знак в каждой контрольной точке, как требуется. Если это происходит, это фатально для метода Ремеза. Также возможно получить решения, которые являются совершенно верными математически, но которые совершенно бесполезны вычислительно: либо потому, что в вычислении рациональной функции есть неизбежное количество ошибок округления, либо потому, что знаменатель имеет один или несколько корней в интервале приближения. В последнем случае, хотя аппроксимация может иметь правильное предельное значение у корней, аппроксимация тем не менее бесполезна.

Предполагая, что аппроксимация не имеет фатальных ошибок и что единственная проблема заключается в адекватном сближении решения minimax, цель состоит в том, чтобы максимально приблизиться к решению minimax до начала метода Ремеза. Использование нулей чебышевского полинома для начальной интерполяции является хорошим началом, но не может быть идеальным при работе с относительными ошибками и/или рациональными (а не полиномиальными) приближениями. Один из подходов заключается в том, чтобы перекосить начальные точки интерполяции на один конец: например, если мы поднимем корни многочлена Чебышева до положительной силы, превышающей 1, то корни будут перекосены к середине интервала [-1,1], в то время как положительная сила, меньше чем одна, перекосит их к любому концу. Полезнее, если мы сначала переоценим очки по [0,1], а затем поднимем их до положительной силы, мы сможем перекосить их влево или вправо. Возвращаясь к нашему примеру e^x   над [-1,1], начальная интерполированная форма была в некотором роде от решения minimax:

Однако, если мы сначала перекосим точки интерполяции влево (снизим их до [0, 1], поднимем до мощности 1.3, а затем снизим до [-1,1]). Мы уменьшаем ошибку с 1.3x10^-3   до 6x10^-4:

Очевидно, что он все еще не идеален, но он находится всего в нескольких процентах от желаемого решения minimax (5x10^-4).

Remez Method Checklist

Ниже перечислены некоторые вещи, чтобы проверить, если метод Ремеза идет не так, это далеко не исчерпывающий список, но предоставляется в надежде, что он окажется полезным.

References

Оригинальные ссылки на метод Ремеза и его расширение до рациональных функций, к сожалению, на русском языке:

Ремез, Е.Я., Основы численных методов приближений Чебышева, "Наукова Думка", Киев, 1969.

Ремез Е.Я., Гаврилюк В.Т., Компьютерная разработка отдельных подходов к приближенному построению решений чебышевских задач нелинейно в зависимости от параметров, Укр. Мат. Ж. 12 (1960), 324-338.

Гаврилюк В.Т. Обобщение первого полиномиального алгоритма Е.Я. Ремез по проблеме построения рационально-фракционных чебышевских приближений, Укр. Мат. Ж. 16 (1961), 575-585.

Некоторые источники английского языка включают:

Фрейзер, У., Харт, J.F., О вычислении рациональных приближений к непрерывным функциям, Комм. из ACM 5 (1962), 401-403, 414.

Ралстон А., Чебышева аппроксимация по алгоритмам Ремеса, Числ.мат. 7 (1965), No 4, 322-330.

А. Ралстон, Рациональное приближение Чебышева, Математические методы для цифровых компьютеров v. 2 (Ralston A., Wilf H., eds.), Wiley, New York, 1967, pp.

Hart, J.F. e.a., Компьютерные приближения, Wiley, New York a.o., 1968.

Коди, W.J., Фрейзер, W., Харт, J.F. Приближение Чебышева с использованием линейных уравнений, Числ.Мат.12 (1968), 242-251.

Cody, W.J., Обзор практического рационального и полиномиального приближения функций, SIAM Review 12 (1970), No 3, 400-423.

Barrar, R.B., Loeb, H.J., On the Remez algorithm for non-linear families, Numer.Math. 15 (1970), 382-391.

Dunham, Ch.B., Сближение алгоритма Фрейзера-Харта для рационального приближения Чебышева, Math. Comp. 29 (1975), No 132, 1078-1082.

Г. Л. Литвинов, Приближенное построение рациональных приближений и эффект автокоррекции ошибок, Russian Journal of Mathematical Physics, vol.1, No. 3, 1994.