Главная > Методы обработки сигналов > Численные методы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 8. Многочлены Чебышева

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

Многочлены Чебышева , где определяются соотношениями

Пользуясь рекуррентной формулой (1), получаем, например,

Старший член многочлена получается из старшего члена многочлена умножением на , и, следовательно, старший член в при есть .

Все многочлены являются четными функциями, — нечетными.

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

При любом имеем

Полагая , получим

Функция удовлетворяет тому же разностному уравнению (1) по переменной , что и . Начальные условия при и одни и те же:

поэтому при всех

Следовательно,

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

Рекуррентное соотношение (1) является разностным уравнением; ему соответствует характеристическое уравнение

с корнями

При корни простые, поэтому

Из начальных условий получаем ; таким образом,

Задача 1. Проверить справедливость этой формулы при и . Из уравнения

получаем, что

— нули . Вследствие (2), (3) точками экстремума на будут точки, где . Решая это уравнение, получим

причем

Многочлены

называют многочленами, наименее уклоняющимися от нуля. Это определение объясняется следующим свойством.

Лемма. Если — многочлен степени со старшим коэффициентом 1, то

Доказательство. Предположим противное. Многочлен имеет степень ; в то же время

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

Задача 2. Доказать более сильное утверждение: если

то

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

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

Нетрудно проверить, что нулями многочлена являются точки

Многочлены при образуют на ортонормированную систему с весом . Проверим свойство ортонормированности этих функций. После замены имеем

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

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

где — погрешности, вызванные округлениями.

Задача 3. Получить представление погрешности

Задача 4. Получить, используя решение задачи 2, оценку погрешности

(7)

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

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

Задача 6. Пусть N — некоторое фиксированное число. Доказать, что векторы, образованные значениями многочленов в нулях , образуют некоторую ортогональную систему, а именно

<< Предыдущий параграф Следующий параграф >>
Оглавление