Ещё раз о полиноме Ньютона...

Для заданного набора измерений {Xi,Yi}, i=0,1,...,N-1 (точки нумеруем с нуля) нужно построить полином Ньютона. Тут и начинаются некоторые вычислительные неоднозначности.

Можно подсчитать таблицу разделённых разностей размером (N-1)*(N-1):

Δi,0 = (Yi+1-Yi) / (Xi+1-Xi), i=0,1,...,N-2,

Δi,j = (Δi+1,j-1-Δi,j-1) / (Xi+j+1-Xi), i=1,2,...,N-2, j=0,1,...,N-2-j,

как в этом примере, тогда полином Ньютона степени N-1, построенный по N парам значений {Xi,Yi}, будет лишь другой формой записи канонического полинома или полинома Лагранжа.

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

Точней, при степени полинома, равной N-1, никакой разницы с результатами остальных методов не будет, а вот для более низких степеней первый полином начнёт сильно "врать" в конце отрезка [Xmin,Xmax], второй - в его начале.

Ну и самое главное - формулы Ньютона в такой форме годятся только для равноотстоящих узлов!

Покажем построение на примере.

Зададим векторы с исходными данными и построим матрицу конечных разностей Δ:

Определение данных и матрицы конечных разностей

Построение первого и второго полиномов Ньютона в точке x реализуем с помощью функций P1 и P2 соответственно:

Функции для построения первого и второго полиномов Ньютона

Заметим, что в функции P1 теоретически можно брать в качестве X0 не самое первое из заданных, а ближайшее слева значение Xi. В функции P2, соответственно, можно выбирать как XN не самый правый, а ближайший справа узел. Правда, у меня подобная версия кода так по-человечески и не заработала :)

Для сравнения и проверки построим по тем же данным обычный канонический полином, значение которого в точке x может быть найдено функцией P0:

Построение канонического полинома в точке x

В пределах изменения аргумента от X0 до X7 построим оба полинома Ньютона и канонический полином:

Графики первого и второго полинома Ньютона

Визуально всё совпало, тем не менее, теоретически считается, что 1-й полином начинает "врать" в конце отрезка, а 2-й - в начале. Такое поведение полиномов станет явным при указании меньшей степени M, например, равной 3 или 6.

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

 Скачать архив .zip с построением 1 и 2 полиномов Ньютона (формат .xmcd, Mathcad 14-15) (56 Кб)

06.03.2014, 12:37 [12433 просмотра]