|
Эффективная
оценка рациональных функций
Полиномы числителя и знаменателя
в минимаксной аппроксимации уже выражены в форме Горнера (то есть в форме вложенного
умножения). Оценка полиномом степени п в форме Горнера при n-умножениях и n-суммированиях
— это наиболее эффективная схема оценки для полинома в общей форме. Однако для
рациональной функции степени (т, п) мы можем делать кое-что даже лучше, чем
просто представить выражения числителя и знаменателя в форме Горнера. Мы можем
нормализовать рациональную функцию так, что полином знаменателя будет со старшим
коэффициентом, равным 1. Мы можем также заметить, что вычисление рациональной
функции степени (т, п) в форме Горнера требует выполнения все
m+n сложений , m+n-1 умножений и 1 деления. Другими
словами, общий индекс действия есть:
- m+n
операций умножения/деления;
- m+n
операций сложения/вычитания.
Вычисление рациональной функции
можно значительно сократить и далее, преобразуя ее в непрерывную (цепную) дробь.
Действительно, рациональная функция степени (т, п) может быть вычислена, при
использовании только:
- max(m,n)
операций умножения/деления;
- m+n
операций сложения/вычитания.
Например, если m = n, тогда эта
новая схема требует выполнения только поло-, вины числа действий умножения/деления
по сравнению с предшествующим методом. Для рациональной функции
MlnimaxApprox вычисление в форме, выраженной выше, сводится к 9 действиям
умножения/деления и 8 действиям сложения/вычитания. Число операций умножения/деления
можно сократить до 8, нормализуя знаменатель к форме monic.
Мы можем теперь вычислить непрерывную (цепную) дробь для той же самой рациональной
функции. Вычисление по этой схеме, как это можно видеть из вывода Maple, сводятся
только к 4 действиям деления и 8 действиям сложения/вычитания:
> MinimaxApprox
:= confracform(MinimaxApprox):
> lprint(MinimaxApprox(x));
-.468857770747е-1+1.07858705749/(х+4.41994843227+16.1901737091/
(х+4.29121842830+70.1948525272/(х-10.2912843004+ 4.77536150167/(х+1.23883665458))))
|
