Теория приближения функций одной вещественной переменной

Теория приближения функций одной вещественной переменной

Интерполяция алгебраическими многочленами

Постановка задачи интерполяции

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

					(1.1)

Далее будем считать, что выполнено условие

.

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

Решение этой задачи можно найти следующим образом: строится алгебраический многочлен степени не выше

, (1.2)

принимающий в точках те же значения, что и функция :

. (1.3)

Интерполяционным многочленом (интерполянтой) для таблицы (1.1) называется многочлен (1.2) степени не выше , удовлетворяющий условию (1.3). Точки называются узлами интерполяции.

Вычисление значения при по формуле

(1.4)

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

Замечание 1.1.. Если , то вычисление с помощью (1.4) называют экстраполяцией.

Замечание 1.2. Существуют различные формы записи интерполяционного многочлена.

Теорема 1.1. Для таблицы (1.1) интерполяционный многочлен существует и единственен.

Доказательство. Запишем интерполяционный многочлен в виде

.

Из условия (1.3) получим систему линейных алгебраических уравнений относительно коэффициентов интерполяционного многочлена :

 

. (1.5)

Так как , то определитель системы (1.5) (определитель Вандермонда) отличен от нуля:

.

Следовательно, для любой таблицы (1.1) можно построить единственный интерполяционный многочлен (его коэффициенты определяются единственным решением системы (1.5)).

Теорема доказана.

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

,

где коэффициенты определяются из условия интерполяции

.

В этом случае для определения коэффициентов получаем аналог системы (1.5)

.

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

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

, .

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

.

Такая интерполяция называется тригонометрическо й. В этом случае интерполянт – тригонометрический полином степени имеет вид:

Предложение 1.1. Пусть - пространство многочленов степени не выше . Если , то для любой таблицы (1.1)

.

Задание. Докажите предложение 1.1.

Замечание 1.3. Решение системы (1.5) является достаточно сложной вычислительной задачей. Поэтому способом построения интерполяционного многочлена, установленным при доказательстве теоремы 1.1, на практике обычно не пользуются. Более удобный способ построения интерполяционного многочлена был предложен Лагранжем.

Погрешность интерполяции

Погрешностью интерполяции называется разность

. (1.8)

Очевидно, что в узлах интерполяции

.

В остальных точках погрешность интерполяции, вообще говоря, отлична от нуля.

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

Найдем погрешность интерполяции для многочлена степени (, ).

В этом случае есть многочлен степени и узлы интерполяции являются его корнями.

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

, (1.9)

где .

Продифференцировав по это равенство раз, получим

,

так как - многочлен степени , то .

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

. (1.10)

Однако, для произвольной функции, заданной только таблицей (1.1), ничего конкретного сказать о погрешности интерполяции нельзя.

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

Теорема 1.2. Если , то для любого погрешность интерполяции определяется формулой

, (1.11)

где - некоторая точка отрезка ().

Доказательство. Будем разыскивать погрешность интерполяции в виде (1.9), положив ,

.

Зафиксируем произвольное , и рассмотрим вспомогательную функцию от переменной :

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

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

Учитывая, что для любого

и ,

получаем

.

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

и

, где .

Теорема доказана.

Важное замечание 1.2. Из формулы (1.11) следует, что погрешность интерполяции зависит от выбора узлов интерполяции и гладкости функции .

Замечание 1.7. Из доказательства теоремы 1.1 получаем, что удовлетворяет условию

.

Следствие 1.2. Пусть и . Тогда

, для любого , (1.12)

, (1.13)

(1.14)

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

(1.15)

Наибольшее значение на отрезке достигается в точке и

Отсюда по формуле (1.13) получаем максимальную оценку погрешности линейной интерполяции

. (1.16)

Если то, оценка (1.16) не имеет места.

Найдем оценку погрешности интерполяции при минимальных требованиях к гладкости функции .

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

. (1.17)

Действительно, используя формулу (1.15), имеем

Поскольку и имеем

,

.

Так как при , то

.

Оценка (1.17) доказана.

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

и вычисляют по формуле линейной интерполяции (1.15). Погрешность интерполяции для оценивается по формуле (1.16).

Замечание 1.8. Для класса раз непрерывно дифференцируемых функций константу в (1.12)-(1.14) улучшить (уменьшить) нельзя, так как для случая неравенство (1.12) превращается в равенство. Что касается величины , то она существенно зависит от выбора узлов интерполяции и, следовательно, может быть уменьшена при специальном выборе узлов.

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

Степень	Многочлен Чебышова

 

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

Положим в формуле (1.35) , (функция взаимно однозначно отображает отрезок на отрезок ).

Получим

или

, (1.36)

Итак, значения многочлена при совпадают со значениями функции на отрезке .

Отсюда получаем, что

(1.37)

Предложение 1.3. Корни многочлена Чебышова , вещественные, различные и принадлежат интервалу .

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

Функция обращается в нуль в точках

, .

Отрезку принадлежат точки только при . Следовательно, все корней многочлена принадлежат интервалу ив силу (1.36) находятся по формуле

(1.38)

Предложение 1.3 доказано.

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

Предложение 1.4. Многочлен Чебышова , на отрезке имеет экстремумы

(1.39)

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

Предложение 1.4 доказано.

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

. (1.40)

Формула (1.40) получается из (1.35) с помощью обратной замены при .

С помощью (1.40) легко вычисляются значения многочлена Чебышова на отрезке .

Замечание 1.13. Из формулы (1.40) немедленно получаем:

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

2) Для имеет место рекуррентная формула

3) Многочлены , , образуют на отрезке ортонормированную систему функций с весом :

.

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

Это означает, что для любого многочлена , такого, что , имеем

(1.41)

Доказательство. Пусть существует многочлен , такой, что

, (1.42)

, .

Тогда разность будет многочленом степени не выше , отличным от тождественного нуля. Кроме того, в силу (1.37) и предположения (1.40) эта разность в точках принимает отличные от нуля значения противоположных знаков:

,

.

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

Теорема 1.3 доказана.

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

(1.43)

При этом в соответствии с (1.37) оценка погрешности интерполяции (1.12) примет вид

(1.44)

,

Из теоремы 3 следует, что оценку (1.41) улучшить на отрезке за счет другого выбора узлов интерполяции нельзя.

Рассмотрим случай интерполирования на произвольном отрезке Отрезок линейной заменой переменной

,

взаимно однозначно отображается на отрезок . При этом корням многочлена на отрезке соответствуют корни многочлена на отрезке :

,

. (1.43)

Точки (1.43) являются оптимальными узлами для оценки погрешности интерполяции на произвольном отрезке .

По узлам (1.43) построим :

Отсюда получаем оценку погрешности интерполяции на произвольном отрезке с узлами (1.43) в виде

(1.44)

.

 

Интерполяционный процесс.

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

где все элементы , , .

Набор узлов интерполяции , принадлежащих - ой строке матрицы , называют сеткой. Таким образом, м атрицаузлов задает на последовательность сеток .

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

. (2.1)

Последовательность интерполяционных многочленов (2.1) называют интерполяционным процессом. Говоря о сходимости интерполяционного процесса, ищут ответ на вопрос о сходимости последовательности интерполяционных многочленов к функции при .

Интерполяция сплайнами

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

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

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

Пусть отрезок разбит на частичных отрезков точками

.

Набор точек принято называть сеткой.

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

(3.14)

степени не выше .

Из определения следует, что для многочленов (3.14), представляющих сплайн на каждом частичном отрезке , имеет место равенство

(3.15)

Рис. 3.1

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

 

Для сплайнов степени и порядка на отрезке используется обозначение

,

где число называется дефектом сплайна.

Сплайн называется интерполяционным для заданной таблицы (1.1), если

 

, (3.16)

где - узлы интерполяции.

Интерполяция посредством сплайнов называется сплайн-интерполяцией.

Замечание 3.2. Непрерывная кусочно-линейная функция (ломаная) является сплайном первой степени нулевого порядка (дефект равен 1).

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

 

Теория приближения функций одной вещественной переменной