KNOW INTUIT, Лекция, Интерполация на функции
6.7. Полиноми на Чебишев и минимизиране на интерполационния остатъчен член
Полином на Чебишев от първи вид е функция Tn(t) = cos (n arccos t) , където
Нека проверим дали функцията Tn(t) наистина е полином. За n = 0 и n = 1 имаме T0(t) = 1, T1(t) = t.
Ако приемем, че получаваме По формулата на сумата от косинуси и рекурсивната връзка е валидна Tn + 1(t) + Tn - 1(t) = 2T1(t)Tn(t) , или Tn + 1(t) = 2t Tn(t) - Tn - 1(t) . Това предполага формата на писане на полиномите на Чебишев: T2 = 2t 2 - 1, T3(t) = 4t 3 - 3t, T4(t) = 8t 4 - 8t 2 + 1 и т.н. Функциите Tn(t) са полиноми от степен n с водещ член 2 n - 1 t n .
Нека въведем и нормализираните полиноми на Чебишев
Нулите на полинома на Чебишев се намират от очевидното уравнение Tn(t) = cos (n arccos t) = 0 , откъдето
Интересуваме се от решаването на следната минимаксна задача: намиране
за да се минимизира остатъчният срок на интерполацията чрез избор на възли на мрежата. Този проблем беше решен от P.L. Chebyshev.
Теорема. (Чебишев (без доказателство))Сред всички полиноми от степен с най-висок коефициент an, равен на единица, най-малкото отклонение от нула, равно на 2 1 - n, има нормализираният полином на Чебишев
Това свойство на полиномите на Чебишев, най-малкото отклонение от нула, може да се формулира по различен начин: за всеки полином Pn(t) = t n + an - 1t n - 1 + . + a0 различно от справедливо
Ако нулите на полинома на Чебишев са избрани като интерполационни възли, тогава произведението и Rn(t) ще бъдат най-малко отклоняващите се от нулата.
6.8. Условност на интерполационния проблем. Лебегова константа
В хода на изчисленията стойностите на интерполираната функция са известни с известна грешка. Грешки при работа на компютързакръгляването е неизбежно. Възниква въпросът за чувствителността на интерполационния полином към грешки в първоначалните данни (условността на интерполационния проблем) и към грешки при закръгляване (въпросът за изчислителната стабилност). Интерполационният полином е оператор, който е линеен по отношение на стойностите на интерполираната функция. Като се вземе предвид грешката на първоначалните данни, полиномът във формата на Лагранж може да се запише, както следва:
характеризира чувствителността към първоначални грешки в данните и изчислителни грешки. Ние се интересуваме от оценка
коефициентът lN се нарича константа на Лебег.
Нека да разгледаме още един обект. Нека е сумата от модулите на всички базисни функции. Нека го обозначим като функция на Лебег (мрежа). След това константата на Лебег
Тъй като функцията на Лебег зависи само от местоположението на възлите на мрежата, константата на Лебег също зависи само от въведената мрежа. Условността и устойчивостта на интерполационния проблем зависи от константата на Лебег.
Разбира се, истинската грешка на интерполацията със сигурност ще бъде по-малка от горната оценка. Оценката обаче е постижима (това е свойство на операторската норма). Най-лошото разпределение на грешката ще бъде такова разпределение, когато грешките са максимални и променят знака от точка на точка. Фактът, че горната оценка ще бъде постижима в този случай, следва от формата на функцията на Лебег и всяка от базисните функции. Каним читателите сами да изпълнят съответните конструкции.
Нека представим (без доказателство) приблизителни оценки на растежа на константата на Лебег в зависимост от броя на възлите на мрежата. Константата на Лебег расте приблизително както за равномерна мрежа, така и за мрежа с набор от възли на Чебишев. Доказано е, че растежът на константата на Лебег за последната решетка асимптотично клони към възможния минимум, а мрежата с възли на Чебишев е близка дооптимален за проблеми с интерполацията.