Студопедия  
Главная страница | Контакты | Случайная страница

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Интерполирование по однократным узлам многочленами Ньютона

Читайте также:
  1. Взаимодействие тел. Принцип суперпозиции сил. Законы динамики ньютона.
  2. Взаимодействие тел. Сила. Второй закон Ньютона
  3. Взаимодействие тел. Сила. Масса. Законы Ньютона (1-ый, 2-ой, 3-ий). Сила упругости. Закон всемирного тяготения. Сила тяжести. Вес. Невесомость.
  4. Второй закон Ньютона
  5. Вывод из формализма Ньютона
  6. Гравитационное взаимодействие тел. Закон всемирного тяготения Ньютона. Космические скорости.
  7. Законы Ньютона
  8. Законы Ньютона
  9. Законы Ньютона
  10. Законы Ньютона

Рассмотрим иное представление интерполяционного многочлена в задаче интерполирования по однократным узлам 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; просмотров: 21 | Поможем написать вашу работу | Нарушение авторских прав




lektsii.net - Лекции.Нет - 2014-2024 год. (0.006 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав