WikiDer > Разделенные различия

Divided differences

В математика, разделенные различия является алгоритм, исторически использовавшийся для вычисления таблиц логарифмов и тригонометрических функций.[нужна цитата] Чарльз Бэббиджс разностный двигатель, рано механический калькулятор, был разработан для использования этого алгоритма в своей работе.[1]

Разделенные различия - это рекурсивный разделение процесс. Метод может быть использован для расчета коэффициентов в интерполяционный полином в Форма Ньютона.

Определение

Данный k + 1 точка данных

В прямые разделенные разницы определяются как:

В обратно разделенные различия определяются как:

Обозначение

Если точки данных заданы как функция ƒ,

иногда пишут

Несколько обозначений разделенной разности функции ƒ на узлах Икс0, ..., Иксп используются:

и Т. Д.

Пример

Разделенные различия для и первые несколько значений :

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

Характеристики

  • Разделенные разности симметричны: если перестановка, то
куда находится в открытом интервале, определяемом наименьшим и наибольшим из с.

Матричная форма

Схема разделенных разностей может быть помещена в верхнюю треугольная матрица.Позволять .

Тогда он держит

Это следует из правила Лейбница. Это означает, что умножение таких матриц есть коммутативный. Таким образом, матрицы схем разделенных разностей относительно одного и того же набора узлов образуют коммутативное кольцо.
  • С - треугольная матрица, ее собственные значения очевидно .
  • Позволять быть Дельта Кронекера-подобная функция, то есть
Очевидно , таким образом является собственная функция поточечного умножения функций. То есть это как-то "собственная матрица" из : . Однако все столбцы кратны друг другу, ранг матрицы из равно 1. Таким образом, вы можете составить матрицу всех собственных векторов из -й столбец каждого . Обозначим матрицу собственных векторов через . Пример
В диагонализация из можно записать как
.

Альтернативные определения

Расширенная форма

С помощью полиномиальная функция с это можно записать как

В качестве альтернативы мы можем разрешить отсчет в обратном порядке от начала последовательности, определив в любое время или же . Это определение позволяет интерпретироваться как , интерпретироваться как , интерпретироваться как и т.д. Таким образом, расширенная форма разделенной разницы становится

Еще одна характеристика использует ограничения:

Неполные фракции

Вы можете представлять частичные фракции с использованием развернутой формы разделенных разностей. (Это не упрощает вычисление, но интересно само по себе.) Если и находятся полиномиальные функции, куда и дается с точки зрения линейные факторы к , то из разложения на частную дробь следует, что

Если пределы разделенных разностей, то эта связь верна, если некоторые из совпадают.

Если является полиномиальной функцией произвольной степени и разлагается на с помощью полиномиальное деление из к ,тогда

Форма Пеано

Разделенные различия могут быть выражены как

куда это B-шлиц степени для точек данных и это производная функции .

Это называется Форма Пеано разделенных различий и называется Ядро Пеано для разделенных различий, оба названы в честь Джузеппе Пеано.

Форма Тейлора

Первый заказ

Если узлы накапливаются, то численное вычисление разделенных разностей неточно, потому что вы делите почти два нуля, каждый из которых имеет высокую относительная ошибка из-за различия одинаковых ценностей. Однако мы знаем, что коэффициенты разницы приблизительно производная наоборот:

за

Это приближение можно превратить в тождество всякий раз, когда Теорема Тейлора применяется.

Вы можете устранить нечетные возможности за счет расширения Серия Тейлор в центре между и :

, то есть

Более высокого порядка

Серия Тейлора или любое другое представление с функциональная серия в принципе может использоваться для аппроксимации разделенных разностей. Ряды Тейлора представляют собой бесконечные суммы степенные функции. Отображение из функции к разделенной разнице это линейный функционал. Мы также можем применить этот функционал к слагаемым функциям.

Выразите обозначение мощности с помощью обычной функции:

Регулярный ряд Тейлора представляет собой взвешенную сумму степенных функций:

Ряд Тейлора для разделенных разностей:

Мы знаем, что первый члены исчезают, потому что у нас более высокий порядок разности, чем полиномиальный порядок, и в следующем члене разделенная разность равна единице:

Отсюда следует, что ряд Тейлора для разделенной разности по существу начинается с что также является простой аппроксимацией разделенной разности, согласно Теорема о среднем значении для разделенных разностей.

Если бы нам пришлось вычислять разделенные разности для степенных функций обычным способом, мы бы столкнулись с теми же численными проблемами, что и при вычислении разделенной разности . Приятно то, что есть способ попроще.

Следовательно, мы можем вычислить разделенные разности по разделение из формальный степенной ряд. Посмотрите, как это сводится к последовательному вычислению степеней, когда мы вычисляем для нескольких .

Если вам нужно вычислить всю схему разделенных разностей относительно ряда Тейлора, см. Раздел о разделенных разностях степенной ряд.

Полиномы и степенные ряды

Разделенные разности полиномов особенно интересны, потому что они могут извлечь выгоду из правила Лейбница. с

содержит схему разделенных разностей для функция идентичности относительно узлов ,таким образом содержит разделенные различия для степенная функция с показатель степени Следовательно, вы можете получить разделенные разницы для полиномиальная функция с уважением к многочлен применяя (точнее: соответствующая ей матричная полиномиальная функция ) к матрице .

Это известно как Формула Опица.[2][3]

Теперь рассмотрим увеличение степени до бесконечности, т.е. превратить многочлен Тейлора в Серия Тейлор.Позволять - функция, соответствующая степенной рядВы можете вычислить схему разделенных разностей, вычислив соответствующий матричный ряд, применяемый к .Если узлы все равны, то это Иорданский блок и вычисление сводится к обобщению скалярной функции на матричная функция с помощью Разложение Жордана.

Прямые различия

Когда точки данных распределены равномерно, мы получаем специальный случай, называемый форвардные различия. Их легче вычислить, чем более общие разделенные разности.

Обратите внимание, что «разделенная часть» из прямая разделенная разница еще должны быть вычислены, чтобы восстановить прямая разделенная разница от форвардная разница.

Определение

Данный п точки данных

с

разделенные разницы можно рассчитать с помощью форвардные различия определяется как

Связь между разделенными разностями и прямыми разностями:[4]

Пример

Смотрите также

Рекомендации

  1. ^ Исааксон, Уолтер (2014). Новаторы. Саймон и Шустер. п. 20. ISBN 978-1-4767-0869-0.
  2. ^ де Бур, Карл, Разделенные различия, Surv. Прибл. Теория 1 (2005), 46–69, [1]
  3. ^ Опиц, Г. Steigungsmatrizen, З. Энгью. Математика. Мех. (1964), 44, Т52 – Т54
  4. ^ Бэрден, Ричард Л .; Faires, Дж. Дуглас (2011). Числовой анализ (9-е изд.). п.129.
  • Луи Мелвилл Милн-Томсон (2000) [1933]. Исчисление конечных разностей. American Mathematical Soc. Глава 1: Разделенные различия. ISBN 978-0-8218-2107-7.
  • Майрон Б. Аллен; Эли Л. Исааксон (1998). Численный анализ для прикладных наук. Джон Вили и сыновья. Приложение. ISBN 978-1-118-03027-1.
  • Рон Голдман (2002). Алгоритмы пирамиды: подход к динамическому программированию кривых и поверхностей для геометрического моделирования. Морган Кауфманн. Глава 4: Интерполяция Ньютона и разностные треугольники. ISBN 978-0-08-051547-2.

внешняя ссылка