Глава II. Аппроксимация и интерполяция

§ 1. Основные понятия

Задача:

Дано: x₀, x₁,     ...,  x_n — узлы,

       f(x₀), f(x₁), ..., f(x_n) — значения f(x) в узлах.

Найти: функцию g(x), такую, что

        g(x_i) = f(x_i), i=0,...,n.

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

Если  (т.е. лежит за пределами отрезка, содержащего узлы), то говорят об экстраполяции.

Примером решения задачи является использование многочлена Тейлора m-ой степени:

.

Для x₀=0 можно использовать известные разложения для функций:

.

Погрешность метода — остаточный член формулы Тейлора в форме Лагранжа:

, где c лежит между x и x₀.

Кроме того, если  не принадлежит интервалу сходимости ряда Тейлора, то погрешность не уменьшается.

§ 2. Существование и единственность интерполяционного многочлена

Задача:

Дано: x₀, x₁, ...,  x_n — узлы,

       f₀, f₁,  ...,  f_n — значения f(x) в узлах.

Найти:  , такой, что

        L_m(x_i) = f_i, i=0,...,n.

Теорема.

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

Док-во:

Чтобы найти многочлен L_m(x) нужно найти коэффициенты a₀,a₁,...a_n.

Они должны удовлетворять СЛУ

   , i=0,...,n.

В системе (m+1) неизвестных, (n+1) уравнение.

Если система крамеровская, то решение существует и единственное.

Пусть m+1= n+1, т.е. m=n.

Главный определитель системы

— определитель Вандермонда.

. Если все узлы различны, то . Теорема доказана.

Замечание (иллюстрация):

Если m<n, СЛУ может быть несовместна.

Например, m=1, n=2, найти линейную функцию (прямую), проходящую через три точки:

Если m>n, СЛУ имеет бесконечно много решений.

Например, m=2, n=1, найти квадратичную функцию (параболу), проходящую через две точки:

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

Выразим многочлен L_n(x) как линейную комбинацию значений f₀, f₁,  ...,  f_n:

.

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

1) n=1         

x₀, x₁ — узлы          

f₀, f₁  — значения

Найти

	x0	x1
	1	0
	0	1

при x₀

при x₁

2) n=2     

x₀, x₁, x₂— узлы          

f₀, f₁, f₂ — значения

Найти

	x0	x1	x2
	1	0	0
	0	1	0
	0	0	1

при x₀

при x₁

при x₂

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

.

Опр. Лагранжевы коэффициенты —

 для каждого i = 0,...,n.

Замечание:

Лагранжевы коэффициенты удовлетворяют тождеству

.

§ 4. Погрешность интерполяционного многочлена Лагранжа

Пусть f(x) — непрерывная, имеющая непрерывные производные до (n+1) порядка.

L_n(x) — многочлен Лагранжа: L_n(x_i)=f(x_i) для всех i=0,...,n.

[a,b] — отрезок, содержащий узлы x₀, x₁, ...,  x_n.

Найдем оценку отличия значения f(x) от значения L_n(x) в точке , не совпадающей ни с одним из узлов.

Запишем равенство

, где .

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

.

	если t= x0, x1, ..., xn,	всего (n+2) точки	по т. Роля, если ф-ия в двух точках равна 0, то существует точка, в которой производная обращается в 0
		(n+1) точка на [a,b]
		n точек на [a,b]
...
		1 точка на [a,b]

Т.е. существует : .

Т.к. , и , получаем

, следовательно .

Þ .

.

.

§ 5. Минимизация погрешности интерполяционного многочлена Лагранжа. Многочлен Чебышева

Задача:

Дано: f(x) на [a,b], непрерывная и дифференцируемая до (n+1) порядка.

Найти:  x₀, x₁, ...,  x_n — узлы, такие, что максимальная погрешность

 была бы минимальной.

Ослабление задачи:  ® min.

 Случай 1) Пусть [a,b]=[-1,1].

Опр. Многочленом Чебышева на [-1,1] называется

.

Выведем рекуррентную формулу для многочленов Чебышева.

Сначала отметим , .

Обозначим  Þ

+

Þ

Þ

Þ

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

1) Если n – четно (нечетно), то T_n(x) содержит только четные (нечетные) степени x.

Док-во: по индукции.

2) Старший коэффициент T_n(x) равен 2^n–1 (для n ³ 1).

Док-во: по индукции.

3) Многочлен T_n(x) имеет n действительных корней в интервале (–1,1), по формуле

 , i = 0,...,n–1.

Док-во: подстановкой.

4)  , причем  , m = 0,...,n.

Док-во: по определению.

5) Многочлен 2^1-n×T_n(x) имеет старший коэффициент 1 (для n ³ 1) и выполняется неравенство

 для любого многочлена P_n(x) степени n  со старшим коэффициентом 1.

(Без док-ва)

Замечание: Многочлен Чебышева — "многочлен, наименее уклоняющийся от нуля".

Теорема 1 (без док-ва).

Корни многочлена T_n+1(x), т.е.  , i = 0,...,n, минимизируют  в оценке погрешности интерполяционного многочлена. При этом

 и .

Случай 2) Произвольный [a,b].

Введем новую переменную .

Тогда f(t) определена на [–1,1].

Используя  , i = 0,...,n, находим .

Теорема 2 (без док-ва).

Значения , i = 0,...,n, минимизируют  в оценке погрешности интерполяционного многочлена. При этом

 и .

§ 6. Схема Эйткена

Для упрощения вычисления интерполяционного многочлена L_n(x) используется следующая схема:

Схема Эйткена

Обозначим L_{(k,k+1,...,l)}(x) — интерполяционный многочлен по узлам x_k,x_k+1,...x_l.

Заметим, что L_(k)(x) = f_k,  L_(0,1,...,n)(x) = L_n(x).

Утверждение.

Выполняется равенство

.

Док-во:

Левая часть равенства — L_{(k,k+1,...,l)}(x) — многочлен степени (l–(k–1)–1)=l–k по узлам x_k,x_k+1,...x_l..

В правой части равенства — тоже многочлен такой же степени.

Для любого i = k+1,...,l–1 значения левой и правой частей совпадают:

.

Для x_k выполняется .

Для x_l выполняется . Утв. доказано.

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

f0 = L(0)(x)
	L(0,1)(x)
f1 = L(1)(x)		L(0,1,2)(x)
	L(1,2)(x)
f2 = L(2)(x)		¼		L(0,...,n)(x) = Ln(x)
	¼
¼		L(n-2,n-1,n)(x)
	L(n-1,n)(x)
fn = L(n)(x)

§ 7. Численное дифференцирование

Задача:

Дано: x₀, x₁, ...,  x_n — узлы,

       f₀, f₁,  ...,  f_n — значения f(x) в узлах.

Найти: .

1 способ) Поскольку f(x) » L_n(x), то  (для 1 £ m £ n).

2 способ) Метод неопределенных коэффициентов.

Пусть ,                                    (1)

где c_i — коэффициенты, обеспечивающие точность формулы для функций f(x), являющихся многочленами наиболее высокой степени.

Если произвольный многочлен a₀+a₁x+...+a_nxⁿ степени n взят в качестве f(x), то выполняется

 для любых a₀,a₁,...a_n.

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

 для i = 0,...,n.

Получаем СЛУ с неизвестными c₀,...c_n, (n+1) неизвестных, (n+1) уравнений.

(Такая же система получается, если в формулу (1) подставлять простые многочлены степени £ n, т.е. 1=x⁰, x, x²,...,xⁿ).

Главный определитель системы

— определитель Вандермонда (транспонированный).

Следовательно, решение c₀,...c_n существует и единственно.

3 способ) Использование простейших формул численного дифференцирования.

Вывод первой формулы: пусть даны x₀, x₁ — узлы, f₀, f₁ — значения f(x) в узлах, h = x₁ – x₀ расстояние между узлами.

По определению производной функции в точке .

Þ  , т.е.               (2)

Замечание: , т.е. производная в x₁ также вычисляется по формуле (2).

Очевидно, формула точна для многочленов степени 1.

Вывод второй формулы: пусть даны x₀, x₁, x₂ — узлы, f₀, f₁ , f₂ — значения f(x) в узлах, h = x₁ – x₀ = x₂ – x₀ расстояние между узлами.

Найдем формулу для производной в средней точке: .

Упростим задачу: пусть -h,0,h – узлы, f₀, f₁ , f₂ — значения.  — искомая формула.

Подставим в нее 1=x⁰, x, x². Получим СЛУ:

 Û .

Решение системы , , .

Тогда .

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

                          (3)

Формула точна для многочленов степени 2.

Вывод третьей формулы: пусть даны x₀, x₁, x₂ — узлы, f₀, f₁ , f₂ — значения f(x) в узлах, h = x₁ – x₀ = x₂ – x₀ расстояние между узлами.

Найдем формулу для второй производной в средней точке: .

Упростим задачу: пусть -h,0,h – узлы, f₀, f₁ , f₂ — значения.  — искомая формула.

Подставим в нее 1=x⁰, x, x². Получим СЛУ:

 Û .

Решение системы , , .

Тогда .

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

                          (4)

Формула также точна для многочленов степени 2.

Д/З Вывести формулы для вычисления  через  и для  через  методом неопределенных коэффициентов.

§ 8. Погрешность простейших формул численного дифференцирования

Первая формула             (2)

или .

Для оценки погрешности воспользуемся разложением по формуле Тейлора:

, где .

Þ .

Þ  — погрешность формулы (2).

Вторая формула                                (3)

или .

Для оценки погрешности также воспользуемся разложением по формуле Тейлора:

, где ,

, где .

Вычтем из первой строки вторую и поделим на 2h:

.

Поскольку , существует точка , такая что  (предполагая непрерывность третьей производной).

Þ  — погрешность формулы (3).

Третья формула                                (4)

или .

Для оценки погрешности также воспользуемся разложением по формуле Тейлора:

, где ,

, где .

Сложим строки и поделим на h²:

.

Существует точка , такая что  (предполагая непрерывность четвертой производной).

Þ  — погрешность

формулы (4).

Замечание: говорят, что первая погрешность имеет порядок h, а вторая и третья — порядок h².

§ 9. Разделенные разности. Многочлен Ньютона.

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

Опр. Назовем разделенными разностями 0-го порядка значения f(x_i).

Назовем разделенными разностями 1-го порядка:

.

Назовем разделенными разностями 2-го порядка:

.

Назовем разделенными разностями порядка l:

.

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

f(x0)
	f(x0; x1)
f(x1)		f(x0; x1; x2)
	f(x1; x2)
f(x2)		¼		f(x0; ...; xn)
	¼
¼		f(xn–2; xn-1; xn)
	f(xn–1; xn)
f(xn)

Лемма 1.(без док-ва)

.

Опр. Интерполяционным многочленом Ньютона с разделенными разностями называется

.

Теорема 2.

Многочлен Ньютона совпадает с многочленом Лагранжа.

Док-во:

1)

где L_k(x) — многочлен Лагранжа степени k по узлам x₀,...,x_k.

2) .

3) Покажем, что для любого k выполняется .

По определению многочлена Лагранжа

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

Замечание: если x₀ < x₁ < … < x_n , то

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

— интерполяционный многочлен для интерполяции назад.

§ 10. Интерполяция с кратными узлами

Задача: Дано: x₀, x₁, ...,  x_n — узлы (различные),

                    m₀,..., m_n — кратности (натуральные числа),

                    s = m₀ +...+ m_n

Найти: многочлен g(x) степени (s–1), такой, что:

,

– – – – – – – – – –

.

Утверждение.

Многочлен g(x) определяется единственным образом.

Док-во:

Существование такого многочлена будет показано ниже, в описании алгоритма его нахождения.

Докажем единственность методом "от противного".

Предположим, существуют два многочлена степени (s–1), удовлетворяющих условиям задачи. Обозначим их разность Q(x).

Тогда Q(x) — многочлен степени (s–1) (или ниже), удовлетворяющий условиям:

,

– – – – – – – – – –

.

Следовательно, у многочлена Q(x) число x₀ – корень кратности m₀ , и т.д.

Таким образом, Q(x) имеет s корней с учетом их кратностей. Но многочлен степени (s–1) не может иметь более (s–1) корней, следовательно Q(x)º0. 

Утв. доказано.

Для нахождения g(x) сведем задачу к задаче поиска интерполяционного многочлена с s узлами.

Пусть e > 0 — некоторая переменная величина,

введем узлы , для i = 0,...,n; j = 1,...,m_i.

При e®0 .

При достаточно маленьком e все  различны.

По таблице разделенных разностей:

…
¼

Найдем многочлен Ньютона

Запишем в более коротком виде:

Тогда его предел при e®0 имеет вид:

, где

.

Заметим, что , т.е. обычная разделенная разность, если i ¹ l.

В противном случае,  (доказывается по индукции).

Алгоритм нахождения g(x):

1) Записать массив предельных значений узлов , т.е. узлов

x₀,...,x₀,x₁, ...,x₁,...,x_n,..., x_n (каждый узел повторяется столько раз, какова его кратность).

2) Составить таблицу предельных значений разделенных разностей:

…
¼

3) Составить многочлен Ньютона, используя верхнюю строку таблицы и массив узлов с повторами.

Пример. Дано: 0,1 — узлы;

                     2,3 — кратности;

f(0)=0, f '(0)=1,

f(1)=2, f '(1)=0, f "(1)=2.

Найти многочлен степени 4, удовлетворяющий перечисленным условиям.

1) Массив узлов с повторами: (0,0,1,1,1).

2)

3) g(x) = 0+1(x–0)+1(x–0)²–3x²(x–1)+6x²(x–1)² = 6x⁴–15x³+10x²+x.

§ 11. Кубическая сплайн-интерполяция

Пусть [a,b] разбит на N равных частей. Точки деления a = x₀, x₁, ...,  x_n = b. Длина каждого участка .

Опр. Сплайн — функция, непрерывная вместе с производными до некоторого порядка на [a,b], являющаяся многочленом на каждом [x_i–1,x_i]

("кусочная функция").

Степень сплайна — максимальная из степеней многочленов.

Дефект сплайна — разность между степенью сплайна и наивысшим порядком непрерывной производной.

Сплайн-интерполяция — замена функции f(x) на сплайн, имеющий в узлах те же значения, что и f(x), и те же значения производных.

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

Обозначение: S₃(x).

Опр. Наклон сплайна в точке x_i — значение производной .

Рассмотрим один отрезок [x_i–1,x_i], h = x_i – x_i–1.

Пусть f_i–1, f_i — значения функции (следовательно, сплайна тоже),

     fs_i–1,fs_i — значения производной функции.

Как в задаче интерполяции с кратными узлами, кратность каждого узла равна 2. Тогда существует многочлен степени 2+2–1 = 3, удовлетворяющий условиям задачи.

Составим таблицу предельных значений разделенных разностей:

xi–1	fi–1
		fsi–1
xi–1	fi–1
xi	fi
		fsi
xi	fi

После преобразования, найденную функцию можно записать в виде линейной комбинации значений f_i–1, f_i и fs_i–1,fs_i:

Применение кубической сплайн-интерполяции:

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

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

, для i = 1,...,N–1

, .