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

График интерполяционного многочлена проходит через заданные точки, т.е. значения многочлена и данной функции у = f (x) совпадают в узлах . Если функция f (x ) сама является многочленом степени n , то имеет место тождество В общем случае в точках, отличных от узлов интерполяции, Эта разность есть погрешность интерполяции и называется остаточным членом интерполяционной формулы. Оценим его значение.

Предположим, что заданные числа yi являются значениями некоторой функции у = f (x ) в точках х = xi .Пусть эта функция непрерывна и имеет непрерывные производные до (n + 1) - го порядка включительно. Можно показать, что в этом случае остаточный член интерполяционного многочлена Лагранжа имеет вид

Здесь – производная (n + 1)-го порядка функции f (x ) в некоторой точке . Если максимальное значение этой производной равно

то можно записать формулу для оценки остаточного члена:

где функция определена как

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

Вид остаточного члена интерполяционного многочлена Ньютона в случае равноотстоящих узлов можно легко получить из (2.41):

Если предположить, что разность постоянна, то можно записать следующую формулу остаточного члена первого интерполяционного многочлена Ньютона:

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

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

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

Положение в некоторых случаях может быть исправлено специальным распределением узлов интерполяции (если они не зафиксированы). Доказано, что если функция f (x ) имеет непрерывную производную на отрезке [-1,1], то при выборе значений х i , совпадающих с корнями многочленов Чебышева степени n + 1, интерполяционные многочлены степени n сходятся к значениям функции в любой точке этого отрезка. Наглядно пояснить сделанное утверждение можно следующим образом. Как было отмечено в разд. 2.2, корни многочленов Чебышева расположены неравномерно на отрезке и сгущаются к его концам. Такое сгущение компенсирует увеличение погрешности интерполяции при приближении к концам отрезка, которое имеет место при равномерном распределении узлов.

Таким образом, точность интерполяции целесообразно повышать за счет уменьшения шага и специального расположения точек х i .Повышение степени интерполяционного многочлена при локальной интерполяции также уменьшает погрешность, однако здесь не всегда ясно поведение производной f (n +1) (х ) при увеличении n . Поэтому на практике стараются использовать многочлены малой степени (линейную и квадратичную интерполяции, сплайны).

Интерполяция - приближение одной функции другой функцией.

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

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

Полином в каноническом виде

Известно, что любая непрерывная на отрезке функция f(x) может быть хорошо приближена некоторым полиномом P n (x). Справедлива следующая Теорема (Вейерштрасса): Для любого >0 существует полином P n (x) степени , такой, что

В качестве аппроксимирующей функции выберем полином степени n в каноническом виде:

Коэффициенты полинома определим из условий Лагранжа , , что с учётом предыдущего выражения даёт систему линейных алгебраических уравнений с n +1 неизвестными:

Обозначим систему таких уравнений символом (*) и перепишем её следующим образом:

Ошибка приближения функции f(x) интерполяционным полиномом n -ой степени P n (x) в точке x определяется разностью: R n (x) = f(x) - P n (x).

Погрешность R n (x) определяется следующим соотношением:

Здесь - производная (n+1) -го порядка функции f(x) в некоторой точке а функция определяется как

Если максимальное значение производной f n+1 (x) равно то для погрешности интерполяции следует оценка:

При реализации данного метода на ЭВМ ошибкой интерполяции E n (x) будем считать максимальное уклонение полинома от исходной функции на выбранном промежутке:

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

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

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

Известно (см. ссылки литературы), что если узлы интерполяции x 0 , x 1 ,...,x n являются корнями полинома Чебышева степени n+1 , то величина принимает наименьшее возможное значение по сравнению с любым другим выбором набора узлов интерполяции.

Очевидно, что в случае k = 1 функция T 1 (x) , действительно, является полиномом первой степени, поскольку T 1 (x) = cos(arccos x) = x.

В случае k = 2 T 2 (x) тоже полином второй степени. Это нетрудно проверить. Воспользуемся известным тригонометрическим тождеством: cos2θ = 2cos²θ - 1, положив θ = arccos x .

Тогда получим следующее соотношение: T 2 (x) = 2x² - 1.

С помощью тригонометрического тождества cos(k + 1)θ = 2cosθ coskθ - cos(k - 1) легко показать, что для полиномов Чебышева справедливо реккурентное соотношение:

T k+1 (x) = 2xT k (x) - T k-1 (x)

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

Корни полинома Чебышева легко находятя из уравнения: T k (x) = cos(k arccos x ) = 0. Получаем, что уравнение имеет k различных корней, расположенных на отрезке [-1,1]: которые и следует выбирать в качестве узлов интерполирования.

Нетрудно видеть, что корни на [-1,1] расположены симметрично и неравномерно - чем ближе к краям отрезка, тем корни расположены плотнее. Максимальное значение модуля полинома Чебышева равно 1 и достигается в точках

Если положить то для того, чтобы коэффициент при старшей степени полинома ω k (x) был равен 1,

Известно, что для любого полинома p k (x) степени k с коэффициентом, равным единице при старшей производной верно неравенство т.е. полиномы Чебышева являются полиномами, наименее уклоняющимися от нуля.

Вычислительный эксперимент

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

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

Пример: Интерполяция синуса

Попробуем интерполировать функцию y = sin(x) на отрезке . Выберем узлы интерполяции: {1.1, 2, 4.7, 7.5, 8.5}

Полученный в результате интерполяции полином отображён на рисунке (синим цветом показан график y = sin(x ), красным – интерполяционного полинома)

Ошибка интерполяции в этом случае: 0.1534

Давайте посмотрим, что произойдёт, если выбрать равномерно стоящие узлы {2, 3.5 5, 6.5, 8} для той же функции на том же отрезке.

На отрезке приближение, бесспорно, стало лучше. Однако разброс на краях очень большой. Ошибка интерполяции: 2.3466 .

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

В нашем случае [a,b ] - отрезок , y = cosx , n+1 - количество узлов.

Остаётся открытым вопрос, какое количество узлов выбрать.

• При значении n меньше 3 ошибка аппроксимации получается более 10.6626.
• При n = 4 : приближение лучше (ошибка равна 1.0111 ),
• при n = 5 : ошибка аппроксимации 0.2797

График функций при n = 4 выглядит следующим образом:

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

• n = 6 : ошибка аппроксимации 1.0233.

При n = 7 ошибка аппроксимации принимает наименьшее из полученных ранее значений (для данного промежутка): 0.0181 . График синуса (обозначен синим цветом) и аппроксимационного полинома (обозначен красным цветом) представлены на следующем графике:

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

При выборе большего количества узлов ситуация ухудшается: мы стараемся слишком точно приблизить исходную функцию:

Ошибка аппроксимации будет только расти с увеличением числа узлов.

Как видим, наилучшее приближение получается при выборе узлов по методу Чебышева. Однако рекомендаций, какое количество узлов является оптимальным, нет - это определяется только экспериментальным путём.

Программа написана на языке C++ с использованием библиотеки линейной алгебры UBlas, которая является частью собрания библиотек Boost. Скачать исходный текст программы можно

Предварительные настойки

Чтобы воспользоваться программой, необходимо сделать следующее: 1. Определиться с функцией, которую вы собираетесь интерполировать 2. Создать текстовый файл (например, vec.txt ), в первой строчке которого через пробел размещены узлы интерполяции, а во второй – значения выбранной функции в этих узлах.

Например, функция y = sin(x):

0.74 2 -3.5 0.6743 0.9093 0.351

3. В.cpp файле программы в функцию double f(double x) вместо строки return прописать возвращаемое исходной функцией значение. Например, для функции y = sin(x):

Return sin(x);

4. В функции int main() исходного кода присвоить переменной char* flname путь к входному файлу с данными. В нашем случае char* flname = "vec.txt";

Использование программы

В программе реализованы следующие основные функции:

• double f(double x) , описание которой было дано выше
• int load(char *filename, vector &x, vector &y) - загрузка узлов интерполяции в переменную x и значения функции в этих узлах в переменную y текстового файла filename . В случае удачной загрузки данных из файла функция возвращает 0 .
• void matrix2diag(matrix &A, vector &y) - приводит матрицу A к треугольному виду. y - столбец правой части (также изменяется вместе с матрицей A ).
• void SolveSystem(matrix &A, vector &y, vector &coef) - решить СЛАУ (A - треугольная матрица, y - столбец правой части, coef - в этот вектор заносится решение СЛАУ)
• double errapprox(vector coef, double a, double b, double h) – возвращает ошибку аппроксимации полиномом исходной функции.

На вход функции подаются следующие параметры:

• • vector coef – вектор коэффициентов интерполяционного полинома, который получается в ходе решения СЛАУ
  • double a, double b – границы промежутка интерполяции
  • double h – шаг, с которым «пробегаем» промежуток

• int outpolyn(char** filename, vector coef) – сохраняет коэффициенты полинома coef в файл filename . В случае удачного сохранения функция возвращает "0".

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

Вывод

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

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

Прикреплённые файлы

Литература

• Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков. Численные методы. Изд-во "Лаборатория базовых знаний". Москва. 2003.
• И.С. Березин, Н.П. Жидков. Методы вычислений. Изд. ФизМатЛит. Москва. 1962.

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

Теорема.

Пусть на отрезке
, таком, что
функция

раз непрерывно дифференцируема, т.е.
, тогда

где
.

Доказательство.

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

где
- некоторое фиксированное значение. Очевидно, что на
функция имеет
нуля. Это узлы интерполяции и точка
. По теореме Ролля,. Продифференцировав (*) (n+1) раз и подставив
, получим

Отсюда
. Ясно, чтов теореме Ролля зависит от расположения нулей функции, т.е.
- некоторая неявная зависимость. Обозначая
через
получим (6).

Следствие. Из формулы (6) следует оценка интерполяции

где
.

Конкретная величина погрешности в точке зависит, очевидно, от значения полинома
в этой точке. Качественный характер
изображен на Рис. 2.

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

Оценка (8) - сильно завышенная оценка ошибки. Для получения точной оценки надо искать экстремумы
.

Оценка (7) для погрешности интерполяции не является завышенной. Можно показать, например, что она достигается при интерполировании полиномом -ой степени полиномом
степени.

Пример.

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

ИП Ньютона . Для коэффициентов:

В данном случае:

;

;

;
;

.

Замечания о минимизации ошибки при полиномиальной интерполяции.

, где
.

Ясно, что величина ошибки зависит от расположения узлов
. Если узлы можно выбирать, то ситуация значительно улучшается. Можно минимизировать ошибку интерполяции.

Полиномы Чебышева. Интерполяция по Чебышевским узлам.

Определение. На отрезке
определим многочлены Чебышева:

Найдем несколько первых многочленов:

,

Получена рекуррентная формула для полиномов Чебышева. Отсюда следует, что
‑полином– ой степени. Последовательно получаем:

;

;

;

и т.д.

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

Благодаря свойству 6. многочлен
называется многочленом, наименее отклоняющимся от нуля. Полиномы Чебышева, нормированные таким образом, чтобы коэффициент при старшей степенибыл равен 1:

;
;
;
;
; и т.д.

Можно записать полином степени , наименее отклоняющийся от нуля на произвольном отрезке.

Применение полиномов Чебышева к задаче интерполяции.

Задача. Оптимизировать интерполяцию полиномом Лагранжа с помощью выбора узлов интерполяции.

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

Пусть
. Погрешность интерполяции, причем
, где
, а полином- многочлен степени
, с коэффициентами
при старшем члене;
- его нули.

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

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

Геометрическая интерпретация корней полинома Чебышева

Если верхнюю полуокружность единичного радиуса разделить на частей, то середины дуг – координаты нулей, экстремумы – точки деления (см. Рис. 3)

Равномерное приближение функций на отрезке.

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

Приблизить многочленом- ой степени так, чтобы выполнялось условие:
. Найти.

. Возьмем для интерполяции интерполяционный полином Лагранжа, построенный по нулям полинома Чебышева
. Имеем:

где
.

Производные функции
:

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