где
Максимальное значение
т.е. равна разности разделенных разностей
Разделенные разности
являются вполне определенными числами, поэтому выражение (1) действительно является алгебраическим многочленом
При вычислении разделенных разностей принято записывать их в виде таблицы
| | ||||
| |||||
| | | |||
| • | ||||
| | • | • | • | |
■ | • | • | • | ||
• | • | • | | ||
• | • | | |||
| |
Разделенная разность
Эту формулу можно доказать методом индукции. Нам потребуется частный случай формулы (1):
Интерполяционным многочленом Ньютона называется многочлен
Рассмотренная форма полинома Ньютона носит название первой интерполяционной формулы Ньютона, и используется, обычно, при интерполировании вначале таблицы.
Заметим, что решение задачи интерполяции по Ньютону имеет некоторые преимущества по сравнению с решением задачи интерполяции по Лагранжу. Каждое слагаемое интерполяционного многочлена Лагранжа зависит от всех значений табличной функции yi, i=0,1,…n. Поэтому при изменении количества узловых точек N и степени многочлена n (n=N-1) интерполяционный многочлен Лагранжа требуется строить заново. В многочлене Ньютона при изменении количества узловых точек N и степени многочлена n требуется только добавить или отбросить соответствующее число стандартных слагаемых в формуле Ньютона (2). Это удобно на практике и ускоряет процесс вычислений.
Программирование функции формулы Ньютона
Для построения многочлена Ньютона по формуле (1) организуем циклический вычислительный процесс по
Тогда рекуррентная формула (3) будет иметь вид:
В формуле Ньютона (2) используются разделенные разности
Используя (4), свернем формулу (2). В результате получим
где
Для вычисления Р удобно использовать рекуррентную формулу
Схема алгоритма интерполяции по Ньютону представлена на рисунке:
Function POlinom(n: integer; d:real; x,y :per):real;
var
l:real;
k,i:integer;
p: real;
begin
L:=y[0];
P:=1;
for k:=1 to n do begin
P:=P*(D-X[k-1]);
for i:=0 to (n-k) do begin
Y[i]:=(y[i+1]-y[i])/(x[i+k]-x[i]);
end;
L:=L+P*y[0];
end;
Polinom:=l;
end;
где
n – количество узлов
x[i],y[i] – табличные значения функции
D – точка, в которой необходимо вычислить значение l
Обзор литературных источников
1. Численные методы
Численные методы являются одним из мощных математических средств решения задачи. Простейшие численные методы мы используем всюду, например» извлекая квадратный корень на листке бумаги. Есть задачи, где без достаточно сложных численных методов не удалось бы получить ответа; классический пример—открытие Нептуна по аномалиям движения Урана.
В современной физике таких задач много- Более того, часто требуется выполнить огромное число действий за короткое время, иначе ответ будет не нужен. Например, суточный прогноз погоды должен быть вычислен за несколько часов; коррекцию траектории ракеты надо рассчитать за несколько минут (напомним, что для расчета орбиты Нептуна Леверье потребовалось полгода); режим работы прокатного стана должен исправляться за секунды. Это немыслимо без мощных ЭВМ, выполняющих тысячи или даже миллионы операций в секунду.
Современные численные методы и мощные ЭВМ дали возможность решать такие задачи, о которых полвека назад могли только мечтать. Но применять численные методы далеко не просто. Цифровые ЭВМ умеют выполнять только арифметические действия и логические операции. Поэтому помимо разработки математической модели, требуется еще разработка алгоритма, сводящего все вычисления к последовательности арифметических и логических действий. Выбирать модель и алгоритм надо с учетом скорости и объема памяти ЭВМ: чересчур сложная модель может оказаться машине не под силу, а слишком простая — не даст физической точности.
Сам алгоритм и программа для ЭВМ должны быть тщательно проверены. Даже проверка программы нелегка, о чем свидетельствует популярное утверждение: «В любой сколь угодно малой программе есть, по меньшей мере, одна ошибка». Проверка алгоритма еще более трудна, ибо для сложных алгоритмов не часто удается доказать сходимость классическими методами. Приходится использовать более или менее надежные «экспериментальные» проверки, проводя пробные расчеты на ЭВМ и анализируя их.
Строгое математическое обоснование алгоритма редко бывает исчерпывающим исследованием. Например, большинство доказательств сходимости итерационных процессов справедливо только при точном выполнении всех вычислений; практически же число сохраняемых десятичных знаков редко происходит 5 — 6 при «ручных» вычислениях и 10—12 при вычислениях на ЭВМ. Плохо поддаются теоретическому исследованию «маленькие хитрости» — незначительные на первый взгляд детали алгоритма, сильно влияющие на его эффективность. Поэтому окончательную оценку метода можно дать только после опробования его в практических расчетах.