§ 11.10. Обсуждение глобальной полиномиальной интерполяции. Понятие о кусочно-полиномиальной интерполяции

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

Теорема 11.6 (аппроксимационная теорема Вейерштрасса).

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

Заметим, что теорема Вейерштрасса не дает конструктивного способа построения соответствующего многочлена.

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

1. Сходимость при увеличении числа узлов.

Всегда ли можно добиться повышения точности интерполяции благодаря увеличению числа узлов (и соответственно степени интерполяционного многочлена)? Хотя положительный ответ на этот вопрос напрашивается сам собой, не будем торопиться с выводами.

Уточним постановку задачи. Для того чтобы реализовать процесс интерполяции функции многочленами возрастающей степени , необходимо указать стратегию выбора при каждом набора узлов интерполяции Такая стратегия задается указанием интерполяционною массива — треугольной таблицы

в каждой строке которой все различны и Будем говорить, что при заданной стратегии выбора узлов метод интерполяции сходится, если при

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

Пример 11.10 (пример Рунге). Используем глобальную полиномиальную интерполяцию с равномерным распределением узлов для приближения на отрезке следующей функции:

Вычисления показывают, что при больших интерполяция дает превосходные результаты в центральной части отрезка. В то же время вопреки ожиданиям Последовательность расходится при для Соответствующая иллюстрация приведена на рис. 11.5.

Рис. 11.5 (см. скан)

Равномерное распределение узлов интерполяции для функции Рунге (11.59) оказалось неудачным. Однако проблема сходимости для этой функции исчезает, если в качестве узлов интерполяции брать корни многочлена Чебышева Существует ли единая для всех непрерывных на отрезке функций стратегия выбора узлов

интерполяции, гарантирующая ее сходимость? Отрицательный ответ на этот вопрос дает следующая теорема.

Теорема 11.7 (теорема Фабера). Какова бы ни била стратегия выбора узлов интерполяции, найдется непрерывная на отрезке функция для которой при

Теорема Фабера отрицает существование единой для всех непрерывных функций стратегии выбора узлов интерполяции. Однако для гладких функций (а именно такие функции чаще всего и интерполируются) такая стратегия существует, о чем говорит следующая теорема.

Теорема 11.8. Пусть в качестве узлов интерполяции на отрезке выбираются чебышевские узлы (11.43). Тогда для любой непрерывно дифференцируемой на отрезке функции метод интерполяции сходится.

Замечание. Практическая реализация стратегии выбора узлов интерполяции (11.43) возможна и оправдана в довольно редких случаях и просто невозможна тогда, когда приходится иметь дело с заданной таблицей значений функции.

2. Чувствительность интерполяционного многочлена к погрешностям входных данных.

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

Пусть заданные в узлах х, значения у содержат погрешности

Тогда вычисляемый по этим значениям многочлен содержит погрешность

Например, при линейной интерполяции по приближенно заданным значениям справедливо равенство

где

Воспользуемся тем, что Для Следовательно,

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

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

Здесь величина, которую называют константой Лебега.

Замечание. В случае, когда для всех выбором знаков погрешностей можно добиться выполнения равенства Это означает, что в самом неблагоприятном случае погрешность входных данных при интерполяции может возрасти в раз. Таким образом, в задаче интерполирования константа Лебега играет роль абсолютного числа обусловленности.

Величина не зависит от длины отрезка а определяется лишь относительным расположением узлов на нем. Для того чтобы

показать это, приведем отрезок к стандартному отрезку с помощью линейного преобразования Тогда и константа Лебега приводится к виду где

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

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

3. Обусловленность задачи вычисления многочлена с приближенно заданными коэффициентами.

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

Здесь некоторый набор базисных многочленов обладающий тем свойством, что всякий многочлен степени может быть однозначно представлен в виде (11.62). Например, можно

использовать степенной базис нормированный стеленной базис локальный степенной базис чебышевский базис Тк лагранжев базис

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

Примем за относительную погрешность вектора величину

а за относительную погрешность многочлена величину

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

Величина характеризующая чувствительность вычисляемых значений многочлена к погрешностям в коэффициентах существенно зависит от выбора базиса Неудачный выбор базиса может сделать эту, казалось бы, элементарную задачу очень плохо обусловленной. Доказано, например, что даже для вполне "разумного" локального степенного базиса - число обусловленности оценивается снизу величиной Как видно из табл. 11.11, использование указанного базиса для представления многочленов высокой степени сопряжено с опасностью значительной потери точности.

Таблица 11.11 (см. скан)

Отметим, что для чебышевского базиса Для лагранжева базиса число обусловленности совпадает с константой Лебега Напомним, что при почти оптимальном выборе узлов интерполяции

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

4. Интерполирование с помощью "движущегося" полинома.

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

Пример 11.11. Пусть функция задана следующей таблицей:

Таблица 11.12 (см. скан)

Для интерполяции этой функции воспользуемся "движущимся" полиномом второй степени. Заметим, что при для приближения используется многочлен многочлен [2.5, 4.0] — многочлен Соответствующая геометрическая иллюстрация приведена на рис. 11.6. Заметим, что полученная таким способом аппроксимирующая функция имеет разрывы в точках

Рис. 6.

Рис. 11.7.

5. Кусочно-полиномиальная интерполяция.

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

Пример 11.12. Для интерполяции функции из примера 11.11 используем кусочно-полиномиальную интерполяцию. На отрезке [0, 2] аппроксимируем функцию многочленом а на отрезке [2, 4] — многочленом Соответствующая геометрическая иллюстрация приведена на рис. 11.7. Заметим, что результирующая аппроксимирующая функция непрерывна, но в точке график ее имеет излом, соответствующий разрыву первой производной.

Заметим, что интерполяцию "движущимся" полиномом можно рассматривать как частный случай кусочно-полиномиальной интерполяции.

Как следует из оценки (11.30), метод кусочно-полиномиальной интерполяции при использовании многочленов фиксированной степени имеет порядок точности относительно