Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Интерполяционный многочлен Ньютона. Интерполяционный многочлен Лагранжа степени не выше n определён, как было доказано в прошлом параграфе
|
|
Интерполяционный многочлен Лагранжа степени не выше n определён, как было доказано в прошлом параграфе, однозначно. Но записывать его можно по-разному.
Интерполяционный многочлен Ньютона получается, если многочлен Лагранжа степени не выше n – 1 записать в виде
Pn(x) = a0 + a1× (x–x0) +…+ ak× (x – x0)× …× (x – xk–1) +…+ an× (x – x0)× …× (x – xn–1).
Неизвестные коэффициенты ak (0 £ k £ n) можно найти последовательно, подставляя в эту формулу x = x0, x1, …, xn–1. Для простоты проделаем вычисления для равномерной сетки xi+1 = xi + h (0 £ i £ n–1), 
.
y0 = Pn(x0) = a0, a0 = y0,
y1 = Pn(x1) = a0 + a1× (x1 – x0), a1 = 
,
y2 = Pn(x2) = a0 + a1× (x2 – x0) + a2× (x2 – x0)× (x2 – x1),
,
...
Здесь удобно ввести обозначения D1 yi = yi+1 – yi, D2 yi = D yi+1 – D yi = = (yi+2 – yi+1) – (yi+1 – yi) = yi+2 –2× yi+1 + yi, …, Dk yi = Dk–1 yi+1 – Dk–1 yi конечных разностей первого, второго, …, k-го порядков в точке yi (при i + k £ £ n). Кроме того, будем считать, что D0 yi = yi (0 £ i £ n). В этих обозначениях для начальных коэффициентов многочлена Ньютона верны формулы 
, которые в общем случае будут доказаны ниже.
Лемма (о конечных разностях). По аналогии с формулой бинома Ньютона 
для конечных разностей выполняется соотношение: 
(1 £ k £ n). Более общо: 
(1 £ k £ n – i) и 
(1 £ k £ n).
Доказательство. Проведём индукцию по k Î N, доказывая сразу общую формулу .
При k = 1 получаем 
– верно.
Предположим, что формула верна для k = 1, …, m £ n – i и докажем её при k = m + 1. Если m = n – i, то доказывать уже нечего.
Если же m < n – i, то m + 1 £ n – i и по определению конечных разностей D m+1 yi = D m yi+1 – D m yi = 
=
Последнее равенство использует известное свойство биномиальных коэффициентов 
.
Равенство (1 £ k £ n) можно вывести из доказанного:
Выражение 
при k= m превращается в 1, а при k – m > 0 – в (1 – 1)k–m = 0 (вспомните бином Ньютона!). Поэтому от изучаемой двойной суммы остаётся просто yk, что и требовалось.
Лемма доказана.
Лемма (о коэффициентах многочлена Ньютона). Для коэффициентов ak многочлена Ньютона
Pn(x) = a0 + a1× (x – x0) +…+ ak× (x – x0)× …× (x – xk–1) +…+ an× (x – x0)× …× (x – xn–1)
справедливы соотношения (0 £ k £ n).
Доказательство. Индукция по k.
База индукции, как показали ранее проведённые вычисления коэффициентов a0, a1, a2, справедлива. Предположим, что формулы доказаны для k = 0, …, m и докажем их для k = m + 1.
После подстановки x = xm+1 в равенство
Pn(x) = 
+am+1× (x – x0)× …× (x – xm)+(x – xm+1)× p(x),
получим
Лемма доказана.
Итак, по лемме
где 
.
Таким образом, получаем 
– это (первый) интерполяционный многочлен Ньютона, который можно записать в виде 
.
(Второй) интерполяционный многочлен Ньютона получается, если интерполяционный многочлен Лагранжа записать в виде
Pn(x) = a0 + a1× (x–xn) +…+ ak× (x – xn)× …× (x – xn–k+1) +…+ an× (x – xn)× …× (x – x1),
беря за базовую точку не x0 а xn. Вычисления, аналогичные предыдущим приводят к следующим формулам:
,
,
где 
.
Пример. Найти многочлены Ньютона, принимающие в точках 1, 2, 3, 4 значения –4, –1, 0, 1.
Составим таблицу конечных разностей заданной в узлах функции, выделим в ней разности D k y0, D k yn, где y0 = –4, yn = 1 и построим первый и второй интерполяционные многочлены Ньютона (заодно проверив их совпадение с многочленом Лагранжа).
| x | y | D y | D 2 y | D 3 y | |
| 1 | –4 | ||||
| 3 | |||||
| 2 | –1 | –2 | |||
| 1 | 2 | ||||
| 3 | 0 | 0 | |||
| 1 | |||||
| 4 | 1 | ||||
(зелёным цветом выделены разности D k y0, а синим – разности D k yn).
Поэтому 
Найденный многочлен можно записать, используя переменную 
:
P3(t + 1) = –4 + 3× t – t× (t – 1) + 
× t× (t – 1)× (t – 2).
Точно так же, вторая интерполяционная формула Ньютона такова:
Этот многочлен можно записать, используя переменную 
:
P3(t + 4) = 1 + t + × t× (t+1)× (t+2).
Раскрыв скобки, получим многочлен Лагранжа:
P3(x) = 
× (x–1)× (x–2)× (x–3) – (x–1)× (x–2) + 3× (x–1) – 4 =
= × [(x–1)× (x–2)× (x–3) – 3× (x–1)× (x–2) + 9× (x–1) –12] =
= × [(x2 – 3× x + 2)× (x–3) – 3× x2 + 18× x – 27] = × [x3 – 9× x2 + 29× x – 33] =
= × [(x2 – 7× x + 12)× (x – 2) + 3× x – 9] = 1 + (x–4) + × (x – 4)× (x – 3)× (x – 2).
2. Используя формулу Ньютона, уплотнить таблицу значений заданной функции на отрезке [a; b] = [0, 645; 0, 695] с шагом h = 0, 01.
Для вычисления с помощью многочлена Ньютона составим таблицу конечных разностей:
Поскольку вторые разности в пределах точности таблицы малы (их порядок примерно равен порядку точности заданных значений для y), в формуле Ньютона ограничимся тремя первыми слагаемыми:
,
где будем брать x0 = 0, 64, y0 = y(0, 64) = 0, 800, 
, h = 0, 05. Вычисления оформим в виде таблицы:
Из таблицы видно, что вблизи точки x = 0, 64 результаты приближённых вычислений почти абсолютно совпадают с точными (вычисленными в среде Excel с помощью стандартной функции КОРЕНЬ(x)), но по мере удаления от этой точки точность приближений ухудшается. Можно улучшить ситуацию, используя ещё одну заданную в условии точку x = 0, 69, производя вычисления по ближайшей из базовых точек 0, 64 и 0, 69:
При x > 0, 69 разумно брать значения y(0, 69) = 0, 831, D y = 0, 0288 и D2 y = –0, 0008.
Приведённые в таблице значения y содержат избыточные знаки после запятой. Это сделано лишь для того, чтобы показать довольно высокую точность вычислений. Однако, окончательно нужно оставить только три цифры после запятой – так же, как и в исходных данных для величины y:
|
|