5.7. Выбор узлов интерполяции

Мы уже говорили, что сетки могут быть равномерными и неравномерными. Возникает естественный вопрос: существует ли оптимальное распределение узлов на отрезке  при интерполяции полиномами? То есть существует ли распределение узлов, при котором погрешность интерполяции полиномами минимальна при фиксированном n?

Отметим, что во многих задачах вычислительной математики введение неравномерной сетки позволяет уменьшить погрешность или сделать ее минимальной. Таким образом в вычислительной математике существует общий прием – введение неравномерной сетки.

Рассмотрим применение этого приема при интерполяции полиномами. Рассмотрим оценку погрешности:

.

Первые два сомножителя не зависят от  .

От  зависит третий сомножитель , полином степени . То есть нужно решить задачу:

.

Если в качестве  рассмотреть отрезок , то мы получим задачу, которая решается с помощью полиномов Чебышева. Оптимальным распределением узлов интерполяции на отрезке [-1, 1] являются нули полинома Чебышева .

Полиномы Чебышева определяются следующим образом:

,     .

Запишем полиномы Чебышева степени 0 и степени 1:    ,      . Полиномы более высокой степени вычисляются по рекуррентной формуле:

.

Найдем нули полинома Чебышева степени n:.

,              ,       

,          .

Запишем формулу для нулей полинома Чебышева степени n таким образом, чтобы  вычислялись в порядке возрастания:

,                        .

Точки  являются оптимальными узлами сетки размерности  n при интерполяции полиномами на отрезке [-1, 1]. Из формулы для нулей полинома Чебышева вытекает, что  для любого i, то есть   на отрезке [-1, 1] имеет n вещественных корней.

Если интерполирование производится на отрезке [a, b], то линейной заменой переменных

 

переводим отрезок [a, b] в отрезок [-1, 1].

Отметим  два свойства полиномов Чебышева:

1) старший коэффициент  равен;

2)  – это ортогональные полиномы на отрезке [-1, 1] с весом , т.е.

Теорема Чебышева

Из всех полиномов  n-й степени со старшим коэффициентом, равным единице, для полинома     выполнено неравенство:

,

то есть полиномы   – это полиномы, наименее уклоняющиеся от нуля в равномерной норме на отрезке [-1, 1].

Сформируем два важных утверждения, связанных с оптимальным выбором узлов интерполяции.


Первое утверждение – это оценка погрешности для оптимального распределения узлов. Второе утверждение – это теорема о сходимости интерполяционных полиномов при оптимальном распределении узлов.

Теорема (оценка погрешности)

Если в качестве узлов интерполяции на отрезке [-1, 1] выбраны нули полинома Чебышева  степени n + 1, то для интерполяционного полинома , построенного по соответствующей интерполяционной таблице, справедлива оценка погрешности:

.

Если же интерполяция проводится на отрезке [a, b] и в качестве узлов интерполяции выбраны точки, соответствующие нулям полинома Чебышева на отрезке [-1, 1], то справедлива оценка:

.

Теорема  (о сходимости)

Если функция является непрерывно дифференцируемой на отрезке  [-1, 1], то интерполяционный полином , совпадающий с  в нулях полинома Чебышева степени n + 1, сходится к  при  для любой точки x из отрезка [-1, 1].

Практический вывод. Если интерполяция может выполняться с произвольным выбором узлов на отрезке [-1, 1], то целесообразно в качестве узлов выбрать нули полинома Чебышева.

Геометрический смысл. Для отрезка [a, b] точки, соответствующие нулям полинома Чебышева на отрезке[-1, 1], получаются построением на отрезке [a, b] полукруга,

делением этого полукруга на n равных  дуг и проецированием середин каждой из дуг на данный отрезок (рис. 5.4). Нули полинома Чебышева сгущаются к концам отрезка.

Кратко остановимся на главных моментах темы интерполяции полиномами.

Если в интерполяционной таблице все  различны ( при ), то существует единственный интерполяционный полином, степень которого на единицу меньше, чем размерность интерполяционной таблицы.

Известны разные формы записи одного и того же интерполяционного полинома (форма Лагранжа, форма Ньютона, форма Стирлинга).

Рис. 5.4. Нули полинома Чебышева

Существует оптимальное распределение узлов интерполяции на отрезке [-1,1], а именно нули полинома Чебышева, использование которых для непрерывно дифференцируемых функций обеспечивает сходимость интерполяционных полиномов.

С ростом степени интерполяционного полинома требуется существование у  производных все более высокого порядка.

При неоптимальном распределении узлов интерполяции на отрезке [a, b] возможно увеличение погрешности с ростом степени интерполяционного полинома и возникновение осцилляции на концах отрезка.

Объем арифметических действий, необходимых для построения полинома Лагранжа – , полинома Ньютона  – . Объем памяти – .