Читайте также:
|
Рассмотрим иное представление интерполяционного многочлена в задаче интерполирования по однократным узлам x 0, x 1 ,..., xn.
Разделёнными разностями (разностными отношениями) по узлам интерполирования x 0, x 1 ,..., xn порядка 1, 2, 3, …, n называют следующие отношения величин:
f (x 1, x 0) =(у 1 - у 0)/(x 1 - x 0 );
f (x 2, x 1, x 0) =(f (x 2, x 1) - f (x 1, x 0))/(x2 - x0 );
f (x 3, x2, x 1, x 0) =(f (x 3 ,x 2, x 1) - f (x2, x 1, x 0))/(x 3 - x 0 );
...
f (xn,..., x 0) =(f (xn,..., x 1) - f (xn- 1 ,..., x 0))/(xn - x 0 ).
C помощью разделённых разностей, которые являются некоторыми постоянными величинами, рассчитываемыми по значениям xi, уi (i = 0,1 ,...,n),многочлен можно представить в следующем виде:
LNn (x) = у 0 + (x - x 0 ) f (x 1, x 0) + (x- x 0 )(x- x 1 ) f (x 2, x 1, x 0) +...+ (x - x 0)(x- x 1) ×... × (x - xn- 1) f(xn,..., x 0).(9.17)
Формула (9.17) называется интерполяционным многочленом Ньютона.
Многочлен степени n содержит n слагаемых, в которых максимальная степень x равна 0,1,2,...,(n -1). Непосредственное полное вычисление каждого слагаемого со степенью х равной i (i =1,..., n -1) требует выполнения i вычитаний и (i -1) умножение. Если просуммировать данные числа по i от 1 до (n -1) и прибавить к ним (n -1) сложение, то в результате получим, что для вычисления одного значения интерполяционного многочлена Ньютона степени n требуется примерно (n +1)2/2 сложений и вычитаний и примерно (n +1)2/2 умножений. Эти числа в два раза меньше, чем при полном расчете полиномов Лагранжа, однако сложность расчета тоже квадратичная по числу узлов (n +1) - О((n +1)2).
Для ее снижения можно использовать пересчет многочленов pi (x), в подряд стоящих слагаемых: pi+ 1(x)= pi (x)×(x - xi). При этом для расчета формулы (9.17) потребуется примерно: 2(n +1) умножений, 2(n +1) сложений и вычитаний - только в раза выше, чем при использовании схемы Горнера у канонических многочленов. Сложность вычисления линейная по числу узлов - О((n +1)1).
В тех случаях, когда целью построения является каноническая форма интерполирующего многочлена, наименьшее число операций затрачивается при использовании в качестве промежуточного решения интерполяционного многочлена Ньютона.
Пример 1. Для задачи из примера 1 п.9.3 построить разделённые разности и интерполяционный многочлен Ньютона.
Решение. Рассчитаем разделённые разности:
f (x 1, x 0) = (у 1 - у 0)/(x 1 - x 0 )=(1-(-2))/(2-(-1)) = 1;
f (x 2, x 1) = (у 2 - у 1)/(x 2 - x 1 )=(5-1)/(4-2) = 2;
f (x 2 ,x 1 ,x 0)=(f (x 2, x 1) - f (x 1 ,x 0))/(x 2 -x 0)=(2–1)/(4-(-1)) = 1 / 5.
Искомый многочлен Ньютона строим по формуле (9.17):
LN 2(x)= у 0 + (x - x 0 ) f (x 1 ,x 0) + (x- x 0 )(x- x 1) f (x 2 ,x 1 ,x 0) = - 2 + (x +1) + (x+1)(x-2)/5.
Наряду с одномерными задачами решаются задачи интерполирования для функциональных зависимостей и с большими числами независимых переменных. Например, в машинной графике функции с двумя независимыми параметрами используют для интерполирования поверхностей.
Вопросы для проверки знаний.
1. Какие отношения называют разделёнными разностями (или разностными отношениями)?
2. Как строится интерполяционный многочлен Ньютона?
3. Какова трудоемкость и сложность расчета значений интерполяционного многочлена Ньютона при полном расчете по формуле (9.17) и при сокращенном расчете?
Дата добавления: 2015-02-16; просмотров: 100 | Поможем написать вашу работу | Нарушение авторских прав |