Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема II. ИНТЕРПОЛИРОВАНИЕ ФУНКЦИЙ
§ Постановка задачи интерполирования
Интерполирование – одна из задач теории приближения функций.
Пусть задано множество вещественных абсцисс: (узлы интерполирования) и соответствующие ординаты – значения некоторой функции в узлах: (они могут быть как определены математически, так и являться результатом наблюдения).
Требуется построить функцию , принадлежащую известному классу, такую, что
, (1)
и принимающую «разумные» значения для , лежащих между узлами (критерий разумности всякий раз зависит от задачи). - интерполирующая функция. Полученную интерполирующую функцию используют для приближенного определения значений данной функции в точках, отличных от узлов. При этом, если , то мы имеем дело с интерполированием (интерполяцией) в узком смысле, при - с экстраполированием (экстраполяцией). Интерполирование в широком смысле включает как первый, так и второй вариант.
Необходимость решать задачу интерполяции возникает, например, при:
Цели интерполяции разнообразны, но почти всегда необходимо иметь быстрый алгоритм вычисления для , не содержащихся в таблице данных.
Условие (1) - условие интерполяции. Очевидно, что существует бесконечное множество различных функций, удовлетворяющих данному условию. Поэтому нужно иметь некоторый критерий выбора. В общем случае критерии формулируются в терминах гладкости и простоты.
Наиболее часто на практике интерполирующая функция строится как линейная комбинация функций:
Реже используются другие функции, например, рациональные.
Рассмотрим полиномиальную интерполяцию. Обратите внимание, что мы пока имеем дело с глобальной интерполяцией, т.е. строим интерполяционный многочлен, единый для всего отрезка . При этом, естественно, график интерполяционного многочлена проходит через все заданные узлы.
При полиномиальной интерполяции в качестве интерполирующей функции ищется полином степени не выше , значения которого в заданных узлах совпадают со значениями функции в этих точках.
(2)
Согласно аппроксимационной теореме Вейерштрасса, любая функция , непрерывная на замкнутом интервале , может быть хорошо приближена некоторым полиномом .
Будем искать интерполяционный полином в каноническом виде:
(3)
Для определения коэффициентов , нужно задать условий. Из условий (2):
(4)
Итак, для отыскания коэффициентов получили СЛАУ, имеющую единственное решение, если среди узлов интерполяции нет совпадающих. Итак, мы можем провести единственный полином через любые точек с разными абсциссами.
Однако, решение такой линейной системы может оказаться весьма трудным делом для , превышающего 10, по причине значительного объема вычислений и частой плохой обусловленности системы. Существуют более простые алгоритмы построения интерполяционных многочленов.
Так, гораздо более удовлетворительный способ вычисления интерполяционного полинома дает его представление в форме Лагранжа или в форме Ньютона.
§ Интерполяционный полином Лагранжа
Будем искать интерполяционный полином как линейную комбинацию многочленов степени :
. (5)
Из условий интерполирования:
(6)
Ясно, что это условие будет выполнено, если
. (7)
Т.к. каждая из искомых функций имеет не менее нулей на отрезке : , будем искать ее в виде:
(8)
С учетом (7)
(9)
Таким образом, интерполяционная формула Лагранжа имеет вид:
. (10)
или
(10’)
Доказано, что данный многочлен является единственным.
При компьютерных расчетах может оказаться удобной следующая схема. Построим таблицу
|
… |
||||
|
… |
||||
|
… |
||||
|
… |
… |
… |
… |
… |
|
… |
Обозначив произведение элементов строк соответственно, получим: (произведение образуют элементы, стоящие на главной диагонали таблицы).
Пример.
Формула Лагранжа при и описывает соответственно линейную и квадратичную интерполяцию:
(это уравнение прямой , проходящей через 2 заданные точки и )
( - уравнение параболы)
Формула Лагранжа для равноотстоящих узлов имеет вид
(11)
(к ней не сложно прийти, выполнив в (10) замену переменных )
Существует несколько обобщений интерполяционного многочлена Лагранжа. Например, довольно широко используются интерполяционные многочлены Эрмита. При этом кроме значений в узлах задаются значения производных . Задача состоит в нахождении многочлена , значения которого и его производных в узлах совпадают с данными. Такая задача также имеет единственное решение при отсутствии совпадающих узлов.
§ Интерполяционный полином Ньютона
Формула Лагранжа явным образом содержит значения . Формула Ньютона позволяет выразить интерполяционный многочлен через значение функции в одном из узлов и через так называемые разделенные или конечные разности.
Разделенными разностями первого порядка называются отношения
.
Например, , .
Вычислив разделенные разности первого порядка, можно построить разделенные разности второго порядка:
или, что то же самое, .
Например,
Разностные отношения первого порядка имеют смысл средних скоростей роста функции на соответствующих отрезках. Разностные отношения второго порядка показывают, как меняются средние скорости роста функции при переходе от отрезка к .
Аналогично, можно построить разделенные разности более высоких порядков. Например, разделенная разность порядка определяется через разности порядка следующим образом:
.
Интерполяционная формула Ньютона предполагает построение интерполяционного полинома в виде
(12)
Удовлетворяя условию интерполирования (2), находим, что , - разделенные разности соответствующих порядков. Тогда (12) принимает вид
(13)
При практических расчетах по интерполяционной формуле Ньютона разделенные разности удобно записывать в виде следующей таблицы:
|
разности 1-го порядка |
разности 2-го порядка |
разности 3-го порядка |
разности 4-го порядка |
… |
|||
|
0 |
... |
||||||
|
1 |
… |
||||||
|
2 |
… |
||||||
|
3 |
… |
||||||
|
4 |
… |
||||||
|
… |
… |
… |
… |
… |
… |
… |
… |
- массив разделенных разностей
Тогда, описав 2 одномерных массива узлов и значений функции в узлах: и , можно рассчитать все элементы массива разделенных разностей:
Обратите внимание, что в формулу Ньютона входят только разделенные разности, расположенные в верхней косой строке.
В случае равноотстоящих узлов интерполяционная формула Ньютона являет собой разностный аналог формулы Тейлора. Покажем это. Для изучения функций, заданных таблицей в равноотстоящих узлах, рабочим аппаратом являются не разделенные, а конечные разности.
Пусть, как и ранее, заданы значения для равноотстоящих значений независимой переменной , где - шаг интерполяции. Конечные разности определяются следующим образом:
……………………………
Очевидно, что конечная разность порядка от полинома степени равна постоянной величине. Все разности более высокого порядка равны нулю. Аналогичными свойствами обладают и разностные отношения.
Коэффициенты интерполяционного полинома Ньютона можно выразить непосредственно через конечные разности:
(14)
Введя новую переменную , формулу (14) можно переписать в виде
(15)
Процесс вычислений конечных разностей также удобно свести в таблицу, аналогичную таблице *:
|
разности 1-го порядка |
разности 2-го порядка |
разности 3-го порядка |
разности 4-го порядка |
… |
|||
|
0 |
... |
||||||
|
1 |
… |
||||||
|
2 |
… |
||||||
|
3 |
… |
||||||
|
4 |
… |
||||||
|
… |
… |
… |
… |
… |
… |
… |
… |
- массив конечных разностей
Заметьте, что при и , и формула (14) принимает вид формулы Тейлора
. (16)
Формулу (15) часто называют первой интерполяционной формулой Ньютона. Наиболее эффективно ее применение в окрестности начального значения , где мало по абсолютной величине. Хотя полученное выражение может аппроксимировать исходную функцию на всем отрезке изменения аргумента , более целесообразно (с точки зрения повышения точности расчетов и уменьшения числа членов суммы) ограничиться случаем , т.е. в (14)-(15) выбирать . Для вместо лучше взять значение ). Таким образов в (15) индекс 0 следовало бы заменить на .
Первую интерполяционную формулу используют для вычисления значений функции на левой половине рассматриваемого отрезка и потому, что разности -го порядка вычисляются через значения , причем , поэтому взяв , ближе к правому краю отрезка, мы не сможем вычислить разности высших порядков . Так при можно учесть только , и .
Если формулу Ньютона хотим использовать для интерполирования в конце таблицы (на правой половине отрезка ), то лучше применять вторую интерполяционную формулу:
, (17)
которая в случае равноотстоящих узлов записывается соответственно
(18)
где
Первой и второй формулами Ньютона можно пользоваться и для экстраполирования. При этом при лучше брать первую (это будет экстраполирование назад), при - вторую экстраполяционную формулу (экстраполирование вперед). При интерполировании ситуация с точностью наоборот: движению вперед () соответствует первая, назад () – вторая формула Ньютона.
Еще раз отметим, что существует один и только один полином при заданной таблице значений функции. Формулы Лагранжа, Ньютона и решение СЛАУ (4) дает один и тот же результат при условии, что вычисления проводятся точно и отсутствуют совпадающие узлы. Главное соображение при выборе алгоритма – конкретная задача. Так, формула Ньютона удобнее, если проводится интерполяция одной и той же функции , но число узлов растет (в формуле Лагранжа это повлечет пересчет всех ранее посчитанных слагаемых и увеличение их количества, в формуле Ньютона все найденные ранее члены сохраняются и добавляется новое слагаемое), если же по одной системе узлов интерполируется несколько функций, то формула Лагранжа удобнее, поскольку явно содержит значения .
§ Погрешности интерполирования.
Оптимальный выбор узлов интерполирования
Погрешностью интерполирования или остаточным членом интерполяционной формулы называется разность
(19)
Очевидно, что в узлах , поскольку график интерполяционного многочлена проходит через заданные узловые точки. Если является многочленом степени , и выбрано узлов, то . В общем случае, в точках, отличных от узлов, и оценка остаточного члена:
. (20)
Здесь
(предполагается, что функция непрерывна и имеет непрерывные производные до -го порядка включительно на отрезке );
- полином степени .
Представление погрешности в форме (20) справедливо как для формулы Лагранжа, так и для формулы Ньютона.
Пример
Выясним, с какой точностью можно вычислить с помощью интерполяционной формулы Лагранжа, выбрав следующие узлы: , , .
Решение
, следовательно для . Тогда, на основании формулы (20) получаем
Вы видите, что оценкой погрешности (20) можно пользоваться до проведения вычислений (априори). Но, если функция задана таблично и аналитическое ее выражение нам неизвестно, то оценка (20) невозможна. Действительно, бесчисленное множество функций может совпадать с данным полиномом в заданной системе узлов, имея сколь угодно большое отклонение в промежуточных точках. Для практической оценки погрешности в этом случае можно пользоваться апостериорной оценкой: при близко расположенных узлах правая часть (20) приближенно совпадает с модулем нового члена полинома Ньютона, появляющемся при добавлении -го узла.
Обратите внимание, что погрешность интерполирования, зависит, во-первых, от свойств функции , что, чаще всего, не поддается регулированию, во-вторых, от выбора узлов , ,…, , и можно их выбирать так, чтобы
,
т.е., чтобы полином , построенный по этим узлам, наименее отклонялся от нуля по абсолютной величине.
Данному условию можно удовлетворить, выбрав в качестве узлов корни полинома Чебышева первого рода:
,
т.е. точки
В этом случае оценка (20) примет вид
Обратите внимание, что чебышевские узлы не являются равноотстоящими, а сгущаются около концов отрезка интерполирования .
Оптимальными узлами на отрезке будут соответственно .
Кстати сказать, в общем случае, даже при таком подборе узлов интерполирования нельзя гарантировать, что абсолютная величина погрешности будет сколь угодно мала при достаточно большом .
§ Сходимость интерполяционного процесса
Часто глобальную полиномиальную интерполяцию лучше не применять вообще. Приведем доводы в защиту этого утверждения. Рассмотрим поведение при неограниченном возрастании числа узлов.
Пусть на отрезке построена последовательность сеток с возрастающим числом узлов:
, , … ,
и пусть функция определена и непрерывна на . Обозначим последовательность интерполяционных полиномов, построенных для функции по ее значениям в узлах сетки .
Интерполяционный процесс называется сходящимся в точке , если существует предел . Если же , то имеет место равномерная сходимость на отрезке .
Свойство сходимости / расходимости интерполяционного процесса зависит как от выбора сеток, так и от гладкости функции . Далее мы рассмотрим примеры несложных функций, для которых интерполяционный процесс расходится.
Теорема Фабера
Для любой последовательности сеток найдется непрерывная на функция , для которой последовательность интерполяционных многочленов не сходится к равномерно на отрезке при .
Пример
Опасности полиномиальной интерполяции замечательно иллюстрирует пример Рунге (1901г.)
Если интерполировать полиномами функцию на отрезке , выбрав равноотстоящие узлы, то оказывается, что давая очень хорошее согласие в центральной части интервала, глобальная полиномиальная интерполяция расходится в интервале .
Если же узлы распределены не равномерно, а являются корнями полинома Чебышева, то проблема расходимости для функции Рунге исчезает, и последовательность интерполяционных многочленов сходится для всех . {Но выбор узлов Чебышева работает не для всех непрерывных функций (по Фаберу невозможно подобрать схему, работающую для всех случаев}
Справедливо и обратное:
Теорема Марцинкевича
Для всякой непрерывной на функции найдется последовательность сеток, для которой интерполяционный процесс равномерно сходится на .
Т.е. добиться сходимости можно за счет выбора узлов интерполяции (сетки), но это весьма трудоемкое занятие и, кроме того, для каждой функции необходимо строить свою сетку.
Поэтому на практике и избегают пользоваться полиномами высоких степеней, применяя кусочно-полиномиальную интерполяцию или же интерполяцию сплайнами.