Методические указания по курсу "Численные методы"

ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное учреждение

Высшего профессионального образования

РОСТОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

Методические указания

по курсу "ЧИСЛЕННЫЕ МЕТОДЫ"

выпуск 1

Полиномиальная интерполяция

Ростов-на-Дону

2006

. Полиномиальная интерполяция. Выпуск 1. Методические указания по курсу "Численные методы". Ростов-на-Дону, 2006г.,-29 с.

Печатается по решению кафедры вычислительной математики и математической физики механико-математического факультета РГУ от 4 сентября 2006г.

(протокол №1)

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

Например, требуется вычислить

,

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

В качестве обычно выбирается линейная комбинация элементарных функций. Например, можно положить , или, в случае четной периодической функции , , и т. п. Можно также аппроксимировать кусочно-полиномиальной функцией.

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

Самый распространенный критерий состоит в требовании, чтобы приближающая функция совпадала с заданными значениями в узловых точках (=) — задача интерполяции. Другой распространенный критерий — "наименьшие квадраты" — означает, что "сумма квадратов отклонений между значениями функции и в узловых точках , должна быть минимальной". Существуют и другие критерии.

Таким образом, прежде чем начать вычисления, надо знать ответ на четыре вопроса:

1.  В каких узлах известны значения функции?

2.  Какой выбран класс приближающих функций?

3.  Какой выбран критерий меры близости?

4.  Какая требуется точность?

В этом методическом пособии рассматривается задача интерполяции.

Линейная задача интерполяции

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

.

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

.

Это условие позволяет получить систему линейных алгебраических уравнений (СЛАУ) для вычисления коэффициентов . СЛАУ имеет вид

. (1)

В силу линейной независимости функций , существуют узлы интерполяции , для которых определитель этой системы отличен от нуля. Для таких узлов решение СЛАУ (1) единственно, и оно определяет единственную функцию .

Заметим, если строится для значений x на отрезке , то говорят о задаче интерполяции, если же для значений x вне этого отрезка ( или ), то — о задаче экстраполяции.

Полиномиальная интерполяция

Если в качестве функций выбраны степенные функции (k=1,2,…,n), то задача интерполяция состоит в построении многочлена

.

Коэффициенты выбираются так, чтобы

.

Если все узлы интерполяции различны (), то определитель системы (1) — определитель Вандермонда отличен от нуля. Это означает, что существует единственный интерполяционный многочлен степени (n-1), построенный по узлам . Многочисленные интерполяционные многочлены (формулы), построенные для одного выбранного набора узлов , — различные формы записи одного и того же многочлена. Такие формулы удобны, а иногда и необходимы, при построении различных численных методов и алгоритмов, реализующих эти методы.

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

Интерполяционный многочлен Лагранжа

Сначала построим фундаментальные многочлены интерполяции (базисные многочлены Лагранжа) степени (n-1), ассоциированные с множеством узлов . Многочлены удовлетворяют условиям

(2)

Из (2) следует, что известны все корни многочлена , и его можно записать в виде

.

Константа C определяется из условия , для фундаментальных многочленов получается выражение

,

.

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

(3)

Для этого многочлена степени (n-1) выполняются условия интерполяции

.

Построенный многочлен называется интерполяционным многочленом Лагранжа.

Единственность многочлена Лагранжа

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

.

Рассмотрим многочлен . Степень не более n-1, а у него n корней, т. к. . Многочлен степени не более n-1 не может иметь n корней, значит .

Оценка погрешности

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

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

. (4)

При таком значении D функция обращается в нуль на в (n+1)–ой точке (n узлов и ). Согласно теореме Ролля (Если непрерывно дифференцируемая функция на концах отрезка принимает одинаковые значения, то найдется, по крайней мере, одна точка внутри отрезка, в которой её производная равна нулю) получаем цепочку утверждений:

имеет на , по крайней мере, n нулей,

имеет на , по крайней мере, n-1 нуль,

. . .

имеет на , по крайней мере, один нуль.

Нуль n– ой производной обозначим . Формула для n– ой производной функции имеет вид

.

Из равенства определяется константа D

. (5)

Из выражений (4) и (5) получается

.

В силу произвольности можно записать

. (6)

Если обозначить , тогда из (6) получится оценка погрешности интерполяции

(7)

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

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

Интерполяционный многочлен Ньютона

Введем сначала понятие разделенной разности.

Определение:

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

Разделенная разность первого порядка определяется выражением

.

Разделенная разность второго порядка определяется выражением

Разделенная разность k —го порядка выражается через разделенные разности (k-1) —го порядка, следующим образом

.

Для разделенных разностей справедливо равенство

. (8)

Эта формула доказывается методом математической индукции (докажите сами).

Выразим через разделенные разности

Таким образом, справедливо соотношение

. (9)

Из (6) и (9) получается выражение для разделенной разности

. (10)

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

Свойства разделенных разностей

1.  Разделенная разность является линейным оператором. Действительно, из формулы (8) следует, что

,

где a и b — const.

2.  Разделенная разность не меняется при любой перестановке своих аргументов (см. формулу (8)).

3.  Если функция является многочленом степени n (), то ее разделенная разность n — ого порядка постоянна, а разделенная разность (n+1) — ого порядка обращаются в нуль (см. формулу (10)).

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

Если в окрестности точки x разделенные разности до - порядка убывают, а

затем начинают расти, то число узлов должно быть не более . Разделенные разности функции записаны в таблице 1.

Интерполяционная формула Ньютона

с разделенными разностями

Запишем интерполяционный многочлен Лагранжа в виде

Каждый из многочленов построен по узлам , т. е. выполняются равенства

.

Выражение является многочленом степени (m-1), все корни которого известны, так как

.

Это означает, что

,

где — пока неизвестная постоянная.

Положим и, используя (9), запишем

.

Сравнивая две последние формулы, находим, что =, а

.

Теперь можно интерполяционный многочлен записать в виде

.

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

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

Заметим, что эту формулу можно понимать как обобщение формулы Тейлора в дискретном анализе: разделенные разности — обобщение производных, а — обобщение степени бинома. Можно показать, что, если узлы стягиваются в одну точку, то в пределе формула Ньютона принимает вид формулы Тейлора.

Упражнения

1. Постройте интерполяционный многочлен Лагранжа для функции, заданной таблично

	-3.6	2.1	-1	1.7
	2.3	-3.6	-4	3

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

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

	-3.6	2.1	-1	1.7
	2.3	-3.6	-4	3

Вычислите его значение в точке х=1.

Разделенные разности

и интерполирование с кратными узлами

Пусть в каждом узле (i=1, 2,…, n) известны не только значения некоторой функция , но и значения ее производных , k =1, 2,…, – 1. В этом случае говорят, что узел имеет кратность . При интерполировании с кратными узлами строится интерполяционный многочлен Эрмита степени s-1 (), для которого выполняются условия

, ,...,, .

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

Построение многочлена

Для простоты изложения построим многочлен (s=5) по двум кратным узлам. Пусть узел трехкратный (), а узел двукратный (). В этих узлах должны выполняться условия

, ,,

, .

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

.

Для многочлена справедлива оценка

(11)

Используя формулу (10), покажем, что при существуют пределы коэффициентов многочлена . Заметим, что при узлы , и стремятся к , а и – к .

Вычислим пределы коэффициентов :

1.  при ;

2.  при , обозначим этот предел ;

3.  при , обозначим этот предел ;

4. 

Предел этого выражения при обозначим , он равен

;

5.  Аналогично получается, что

при .

Таким образом, при

Из формулы (11) при получается оценка для

Многочлен построен, проверим выполнение условий интерполяции:

1.  первое условие проверяется подстановкой ;

2.  вычислим

+,

отсюда следует ;

3.  вычислим

+,

отсюда следует

Условия, заданные в точке , выполнены. Многочлен единствен и не изменится, если объявить первым узлом , а вторым , тогда

Легко убедиться, что и .

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

При построении таблицы разделенных разностей в случае кратных узлов сначала требуется заполнить строки, соответствующие кратным узлам. Остальные разделенные разности вычисляются обычным способом. Например, если имеет кратность 4, то этому узлу соответствуют четыре строки таблицы разделенных разностей, имеющие вид

Здесь , , .

Пример. Рассмотрим функцию

,

вторая производная которой в точке терпит разрыв первого рода. Сравним с построенным для неё интерполяционным многочленом с кратными узлами. Выберем три узла, два двукратных и , и один простой . Таблица разделенных разностей для этих узлов имеет вид

Интерполяционный многочлен имеет вид

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

Упражнения

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

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

Интерполяционные многочлены

для равноотстоящих узлов

Пусть узлы , в которых заданы значения функции , равноотстоящие, т. е. для любого =0,1,...,n-1. В этом случае вместо разделенных разностей вводятся конечные разности.

Конечные разности и их свойства

Определение:

Конечной разностью первого порядка называется выражение

.

Конечной разностью второго порядка называется

.

Конечной разностью k—ого порядка называется

.

Иногда конечная разность k—ого порядка обозначается .

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

.

Из этого равенства и формулы (10) получаем

, где

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

Свойства конечных разностей определяются свойствами разделенных разностей:

1. Конечная разность — линейная операция

.

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

Упражнения

1  Постройте таблицу конечных разностей для значений функции

x	-3	-2	-1	0	1	2	3
y(x)	0	-3	-4	-3	0	5	12

Для какой функции составлена эта таблица?

2  Возьмите любой многочлен степени , вычислите его значения в (n+3) равноотстоящих узлах. Постройте таблицу конечных разностей, соответствующую вычисленным значениям.

3  Вычислите конечную разность , если функция задана своими значениями .

4  Постройте таблицу конечных разностей для функции в узлах , при условии, что её значение в известно с погрешностью (). Проследите, как распространяется эта погрешность в таблице конечных разностей.

Для равноотстоящих узлов оценку погрешности интерполяционного многочлена , построенного по узлам , можно записать в виде

,

где , , .

Из этой оценки следует, что точность интерполяции в точке x (значение t фиксировано) можно увеличить, если

1. уменьшить h – шаг таблицы,

2. при шаге таблицы , увеличить n,

3. уменьшить значение константы C.

Может оказаться, что первый из указанных способов невозможен, например, таблица получена экспериментально, и её шаг нельзя изменить.

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

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

Если же значение x находится среди узлов в середине таблицы, то в качестве нулевого узла интерполяции (ближайшего к x) выбирается значение , где индекс i равен целой части числа . Остальные узлы выбираются из значений , очевидно, значение k зависит от n. Если , то ближайшими к x являются узлы , если же , то — .

Рассмотрим интерполяционные формулы для всех вариантов расположения значения x.

Интерполяционные формулы Ньютона

для равноотстоящих узлов

1.  Интерполяционная формула Ньютона для начала таблицы (интерполяция вперед)

Выберем узлы и запишем интерполяционную формулу с разделенными разностями

Сделаем замену , тогда , а выражения для разделенных разностей примет вид

.

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

,

где

2.  Интерполяционная формула Ньютона для конца таблицы (интерполяция назад)

Выберем узлы и запишем интерполяционную формулу с разделенными разностями

Здесь удобна замена , тогда , и для разделенных разностей получим выражения

Теперь интерполяционный многочлен Ньютона для конца таблицы принимает вид

где

Интерполяционные формулы Гаусса

Интерполяционные многочлены Гаусса строятся для значений x, находящихся в середине таблицы.

Первая формула Гаусса

Первая формула Гаусса получается, если в качестве узлов интерполяции выбраны , при n=2m+1 (последний узел отбрасывается, если n=2m).

Формула Ньютона с разделенными разностями для таких узлов имеет вид

Здесь имеются разделенные разности двух типов

Сделаем замену , тогда , первая формула Гаусса примет вид

где

Вторая формула Гаусса

Вторая формула строится также как первая, только выбраны узлы .

Для таких узлов формула Ньютона с разделенными разностями имеет вид

Сделаем ту же замену , и вторая формула Гаусса примет вид

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

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

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

Оптимальный выбор узлов интерполяции

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

для многочлена выполнялось условие

,

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

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

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

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

а многочлены n — ой степени выписываются с помощью рекуррентной формулы

.

Легко показать (с помощью математической индукции), что — четная функция, а — нечетная. Из рекуррентной формулы следует, что коэффициент при старшей степени , n>1 равен .

У многочлена Чебышева существует n различных вещественных корней, которые находятся на отрезке . Чтобы найти эти корни, запишем на в виде

.

Для корней такого многочлена получаются формулы

, .

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

.

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

Лемма. Если — произвольный многочлен степени n с коэффициентом при старшей степени равным единице, то

Доказательство. Предположим противное, пусть . Степень многочлена не выше (n-1) (старшие степени уничтожаются). В силу предположения, он не равен нулю тождественно. Если для любого , то знак разности в точках экстремума многочлена Чебышева

совпадает со знаком .

Это означает, что многочлен меняет знак на отрезке в (n+1)–ой точке, т. е. имеет n корней. Отличный от нуля многочлен степени не более (n-1) не может иметь n корней. Получили противоречие, лемма доказана.

Заметим, что многочлены

, , .

образуют на отрезке ортонормированную с весом систему многочленов, т. е.

Сделаем замену , тогда, если , то . Корням , полинома на отрезке , отвечают точки на отрезке . Если эти точки взять в качестве узлов интерполяции, то

Это означает, что

Для выбранных узлов интерполяции получается оценка

,

и её нельзя улучшить за счет выбора любых других узлов.

Замечание. На опасность появления большой погрешности интерполяции обратил внимание в 1901г. Рунге. На отрезке рассматривалась аналитическая функция (на рисунке изображен её график).

Если при построении интерполяционного многочлена для этой функции, выбрать равноотстоящие узлы, например, для n=6, то при последовательность не сходится к для значений .

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

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

Контрольные вопросы

1. Сколько интерполяционных многочленов степени n-1 можно построить по заданным n узлам?

2. Сформулируйте постановку задачи интерполяции. Что такое экстраполяция?

3. Сформулируйте постановку задачи интерполяции с кратными узлами.

4. Как отличаются друг от друга различные интерполяционные многочлены (Лагранжа, Ньютона, и т. п.), построенные по одному и тому же набору узлов?

5. Как оценивается погрешность интерполяционного полинома? Как её можно уменьшить?

6. Как оптимальным образом выбрать узлы интерполяции?

7. Перечислите свойства разделенных разностей.

8. Перечислите свойства конечных разностей.

9. Для каких функций погрешность интерполяции равна нулю?

10. Пусть задана большая таблица значений функции. Как расположение значения х влияет на выбор интерполяционной формулы? Как наилучшим образом выбрать степень интерполяционного многочлена?

Упражнения

1.  Пусть , постройте интерполяционный многочлен , совпадающий с функцией в точках x=0, x=1, x=2. Оцените на отрезке . Сравните эту оценку с фактической погрешностью в точке x=1/2 (или x=3/2).

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

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

4.  На сетке , , заданы значения , где – многочлен Чебышева. Вычислите значение .

5.  Постройте таблицу конечных разностей для таблицы значений функции

x	-3	-2	-1	0	1	2	3
y	0	-2.9	-4	-3.1	0	4.9	12

Многочленом какой степени разумно интерполировать эту функцию

6.  Постройте интерполяционный многочлен Ньютона третьей степени для точки x=2.7, если функция задана таблично

x	-3	-2	-1	0	1	2	3
y	0.1	-3	-4	-3.1	0	5.4	11.7

7.  Пусть , P(x) и Q(x)– два полинома третьей степени, удовлетворяющие условиям . Оцените для любого значение .

8.  Пусть дана таблица пятизначных десятичных логарифмов для с шагом . Будет ли погрешность линейной интерполяции (многочлен ) меньше чем .

9.  Постройте интерполяционный многочлен для функции Рунге , с помощью узлов . Оцените погрешность.

10.  Возьмите любой многочлен степени вычислите его значения в (n+2) узлах. Используйте эти значения для построения интерполяционных многочленов степени n-1, n и n+1. Сравните полученные многочлены с выбранным полиномом

11.  Постройте кусочно–линейную функцию, соответствующую следующим данным

x	0	1/6	1/3	1/2	2/3	5/6	1
y	1	4	1	-1	2	4	0

12.  Постройте кусочно – квадратичную функцию, соответствующую следующим данных

x	0	1/6	1/3	1/2	2/3	5/6	1
y	1	4	1	-1	2	4	0

Задание для практикума на ЭВМ

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

Тема: “ Полиномиальная интерполяция ”.

Пусть значения некоторой функции известны в N узлах , на отрезке . Требуется построить интерполяционный многочлен по k () узлам и оценить его погрешность.

Для этого:

1. Вычислите таблицу значений заданной функции в узлах , .

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

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

4. Выполните это задание для функции (пример Рунге)

, где .

5. Объясните полученные результаты.

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

В варианте задания должны быть заданы функция , значения N и k. Интерполяционная формула может быть указана или выбираться самостоятельно.

Из этого задания можно получить несколько различных вариантов заданий, для этого:

1.  Задать функцию различными способами.

a.  функция выбирается как линейная комбинации элементарных функций;

b.  функция выбирается кусочно-полиномиальной. Если производная этой функции терпит разрыв, то можно увидеть, как влияет такой разрыв на погрешность интерполяции;

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

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

Литература

1.  Бахвалов H. С. Численные методы. М.: Наука, 1973

2.  Калиткин H. H. Численные методы. М.:Hаука,1978

3.  , Гулин методы. М.:Hаука,1989

4.  Бахвалов H. С. ,, П, Численные методы. М.:Hаука,1989г.

5.  . Численные методы. М.: Наука, 1972

6.  Дж. Ортега, У. Пул. Введение в численные методы решения дифференциальных уравнений. М.: Наука, 1986.