2. Минимизация оценки погрешности интерполяции

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

Будем решать более простую задачу: найдем такое расположение узлов интерполяции , при котором является минимальной величина . Для этого рассмотрим многочлены Чебышева [4].

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

(3)

Так, например:

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

Введем обозначение:

(4)

Тогда

Приводя подобные члены в этом выражении, получим:

Учитывая (3) и (4), получаем рекуррентную формулу для определения очередного многочлена Чебышева:

(5)

Применяя последовательно (5), находим:

(6)

Свойства многочленов Чебышева.

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

2. Старший коэффициент многочлена при равен .

3. Полином имеет действительных корней. Определим эти корни из уравнения :

Функция обращается в ноль при . Следовательно: или

(7)

Все корни действительны и принадлежат отрезку .

4. Максимальное по модулю значение равно 1:

Из определения следует, что при любом значении .

Определим точки , в которых , . Известно, что , если , . Отсюда и .

Заметим, что меняется от 0 до , т. к. на концах отрезка в зависимости от четности . При этом количество нулей равно , количество максимумов - .

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

Доказательство этого свойства можно найти, например, в .

Узлы, минимизирующие оценку погрешности интерполяции

Возьмем на отрезке в качестве узлов интерполяции корни многочлена Чебышева . Значение этих точек определяются в соответствии с (7) при :

Образуем многочлен

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

В этом случае погрешность интерполяции будет определяться как

где

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

Рассмотрим теперь, как изменится величина оценки погрешности , если интерполяция проводится на отрезке . Введем замену переменных. Пусть теперь переменная , а переменная и . Определим коэффициенты и .

При

Тогда

и

.

Учитывая, что на отрезке узлы интерполяции

узлы интерполяции на отрезке :

Тогда

Отсюда

Выражение для оценки погрешности интерполяции будет иметь вид:

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

В качестве простой иллюстрации рассмотрим задачу аппроксимации многочленом степени функции на отрезке . Для этого рассчитаем значения функции в 5-ти точках отрезка и решим задачу интерполяции.

На рис. 1 представлены результаты интерполяции: многочлен построен по равномерной сетке узлов, многочлен использует корни многочлена Чебышева 5-го порядка.

Рис.1. Графическое представление: функции , - интерполяционного многочлена, построенного на равномерной сетке узлов; - интерполяционного многочлена, построенного по узлам полинома Чебышева

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

О сходимости интерполяционного процесса.

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

Сформулируем определение сходимости интерполяционного процесса.

Множество точек , точек, что

назовем сеткой на отрезке [a; b] и обозначим через Ω_n. Рассмотрим последовательность сеток с возрастающим числом узлов, а именно последовательность

Пусть функция f(x) определена и непрерывна на [a;b]. Тогда можно задать последовательность интерполяционных многочленов , построенных для функции f(x) по ее значениям в узлах сетки .

Говорят, что интерполяционный процесс для функции f(x) сходится в точке , если существует

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

Свойство сходимости интерполяционного процесса зависит, как от выбора последовательности сеток, так и от гладкости функции f(x).

Известны примеры несложных функций, для которых интерполяционный процесс расходится. Так последовательность интерполяционных многочленов, построенных для непрерывной функции f(x) = |x| по равностоящим узлам на [-1; 1], не сходится к функции |x| ни в одной точке отрезка [-1;1], кроме точек -1, 0, +1.

Для заданной непрерывной функции f(x) можно добиться сходимости за счет выбора расположения узлов интерполяции.

Теорема Марцинкевича: если f(x) непрерывна на [a;b], то найдется такая последовательность сеток, для которой соответствующий интерполяционный процесс сходится равномерно на [a;b].

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