8. Алгоритмы полиномиальной аппроксимации в равномерной метрике

Задача о наилучшем приближении элемента линейного нормированного пространства X "полиномами" по системе есть задача безусловной минимизации выпуклого функционала

Для ее решения можно применять общие алгоритмы минимизации функционалов (см., напр., [71]), однако наиболее эффективны алгоритмы, построенные на основе характеристических свойств полинома наилучшего приближения, Такие алгоритмы используют специфику задачи. Вначале рассмотрим приближение многочленами на точечном множестве числовой оси.

8.1. Алгоритм В. Пуссена-Ремеза

Имеется несколько вариантов этого алгоритма (см. [59]), здесь приводится простейший из них. Пусть сетка, Алгоритм итерационный, он позволяет при заданном где построить полином для которого

На каждой итерации (шаге) строится набор точек

и полином где k — номер итерации. На нулевом шаге возьмем произвольный набор попарно различных точек и определим из системы уравнений (ниже показано, что определитель системы ненулевой)

На первом шаге положим построим следующим образом: включим в все точки из кроме одной, заменив ее новой точкой для которой

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

и так далее. Если уже найдены то на шаге положим построим включив в тк все точки из кроме одной, заменив ее новой точкой для которой при соблюдении условия Пусть номер новой точки в Найдем из системы уравнений

Отметим, что для любого к

Докажем сходимость алгоритма. Пусть V — определитель системы (8.2), определитель Вандермонда по набору точек

тогда и по правилу Крамера с учетом (8.3) получим

где Поскольку конечная сетка, то найдется число такое, что Теорема -Пуссена с очевидным неравенством дает

Имеем

т.е. монотонно возрастая, сходится к со скоростью геометрической прогрессии. Так как

то найдется номер к, для которого удовлетворяется неравенство (8.1): Следовательно, полином искомый.

Замечание. Можно показать, что неравенство справедливо и в случае, когда является отрезком и, более того, константа связана с константой сильной единственности

Пример. Пусть Начиная с найдем (см. рис. 7) Для построения многочлена наилучшего приближения потребовалось 3 итерации. Далее рассмотрим алгоритмы аппроксимации по произвольной системе функций.

Рис. 7