Интерполяция с кратными узлами
Интерполяция с кратными узлами
Задача: Дано: x0, x1, ..., xn — узлы (различные),
m0,..., mn — кратности (натуральные числа),
s = m0 +...+ mn
Найти: многочлен g(x) степени (s–1), такой, что:
,
– – – – – – – – – –
.
Утверждение.
Рекомендуемые материалы
Многочлен g(x) определяется единственным образом.
Док-во:
Существование такого многочлена будет показано ниже, в описании алгоритма его нахождения.
Докажем единственность методом "от противного".
Предположим, существуют два многочлена степени (s–1), удовлетворяющих условиям задачи. Обозначим их разность Q(x).
Тогда Q(x) — многочлен степени (s–1) (или ниже), удовлетворяющий условиям:
,
– – – – – – – – – –
.
Следовательно, у многочлена Q(x) число x0 – корень кратности m0 , и т.д.
Таким образом, Q(x) имеет s корней с учетом их кратностей. Но многочлен степени (s–1) не может иметь более (s–1) корней, следовательно Q(x)º0.
Утв. доказано.
Для нахождения g(x) сведем задачу к задаче поиска интерполяционного многочлена с s узлами.
Пусть e > 0 — некоторая переменная величина,
введем узлы , для i = 0,...,n; j = 1,...,mi.
При e®0 .
При достаточно маленьком e все различны.
По таблице разделенных разностей:
… | |||
|
| ||
¼ | |||
Найдем многочлен Ньютона
Запишем в более коротком виде:
Тогда его предел при e®0 имеет вид:
, где
.
Заметим, что , т.е. обычная разделенная разность, если i ¹ l.
В противном случае, (доказывается по индукции).
Алгоритм нахождения g(x):
1) Записать массив предельных значений узлов , т.е. узлов
x0,...,x0,x1, ...,x1,...,xn,..., xn (каждый узел повторяется столько раз, какова его кратность).
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)
0 | ||||
f '(0)=1 | ||||
0 | (2–1)/(1–0)=1 | |||
(2–0)/(1–0)=2 | –3 | |||
2 | (0–2)/(1–0)=–2 | 6 | ||
f '(1)=0 | Рекомендуем посмотреть лекцию "Библиографический список". 3 | |||
2 | f "(1)/2=1 | |||
f '(1)=0 | ||||
2 |
3) g(x) = 0+1(x–0)+1(x–0)2–3x2(x–1)+6x2(x–1)2 = 6x4–15x3+10x2+x.