Разделенные различия - Divided differences

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

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

Определение

Учитывая k  + 1 точек данных

${\ displaystyle (x_ {0}, y_ {0}), \ ldots, (x_ {k}, y_ {k})}$

Эти вперед разделенные разности определены как:

${\ displaystyle [y _ {\ nu}]: = y _ {\ nu}, \ qquad \ nu \ in \ {0, \ ldots, k \}}$

${\ displaystyle [y _ {\ nu}, \ ldots, y _ {\ nu + j}]: = {\ frac {[y _ {\ nu +1}, \ ldots, y _ {\ nu + j}] - [y_ {\ nu}, \ ldots, y _ {\ nu + j-1}]} {x _ {\ nu + j} -x _ {\ nu}}}, \ qquad \ nu \ in \ {0, \ ldots, kj \}, \ j \ in \ {1, \ ldots, k \}.}$

В обратном направлении разделенных разностей определяются следующим образом:

${\ displaystyle [y _ {\ nu}]: = y _ {\ nu}, \ qquad \ nu \ in \ {0, \ ldots, k \}}$

${\ displaystyle [y _ {\ nu}, \ ldots, y _ {\ nu -j}]: = {\ frac {[y _ {\ nu}, \ ldots, y _ {\ nu -j + 1}] - [y_ {\ nu -1}, \ ldots, y _ {\ nu -j}]} {x _ {\ nu} -x _ {\ nu -j}}}, \ qquad \ nu \ in \ {j, \ ldots, k \}, \ j \ in \ {1, \ ldots, k \}.}$

Обозначение

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

${\ Displaystyle (x_ {0}, f (x_ {0})), \ ldots, (x_ {k}, f (x_ {k}))}$

иногда пишут

${\ Displaystyle е [х _ {\ ню}]: = е (х _ {\ ню}), \ qquad \ nu \ in \ {0, \ ldots, k \}}$

${\ displaystyle f [x _ {\ nu}, \ ldots, x _ {\ nu + j}]: = {\ frac {f [x _ {\ nu +1}, \ ldots, x _ {\ nu + j}] - f [x _ {\ nu}, \ ldots, x _ {\ nu + j-1}]} {x _ {\ nu + j} -x _ {\ nu}}}, \ qquad \ nu \ in \ {0, \ ldots, kj \}, \ j \ in \ {1, \ ldots, k \}.}$

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

${\ displaystyle [x_ {0}, \ ldots, x_ {n}] f,}$

${\ displaystyle [x_ {0}, \ ldots, x_ {n}; f],}$

${\ Displaystyle D [x_ {0}, \ ldots, x_ {n}] f}$

и т.п.

Пример

Разделенные различия для первых нескольких значений : ${\ displaystyle \ nu = 0}$${\ displaystyle j}$

${\ displaystyle {\ begin {align} {\ mathopen {[}} y_ {0}] & = y_ {0} \\ {\ mathopen {[}} y_ {0}, y_ {1}] & = {\ гидроразрыв {y_ {1} -y_ {0}} {x_ {1} -x_ {0}}} \\ {\ mathopen {[}} y_ {0}, y_ {1}, y_ {2}] & = {\ frac {{\ mathopen {[}} y_ {1}, y_ {2}] - {\ mathopen {[}} y_ {0}, y_ {1}]} {x_ {2} -x_ {0} }} = {\ frac {{\ frac {y_ {2} -y_ {1}} {x_ {2} -x_ {1}}} - {\ frac {y_ {1} -y_ {0}} {x_ {1} -x_ {0}}}} {x_ {2} -x_ {0}}} = {\ frac {y_ {2} -y_ {1}} {(x_ {2} -x_ {1}) (x_ {2} -x_ {0})}} - {\ frac {y_ {1} -y_ {0}} {(x_ {1} -x_ {0}) (x_ {2} -x_ {0} )}} \\ {\ mathopen {[}} y_ {0}, y_ {1}, y_ {2}, y_ {3}] & = {\ frac {{\ mathopen {[}} y_ {1}, y_ {2}, y_ {3}] - {\ mathopen {[}} y_ {0}, y_ {1}, y_ {2}]} {x_ {3} -x_ {0}}} \ end {выровнено }}}$

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

${\ displaystyle {\ begin {matrix} x_ {0} & y_ {0} = [y_ {0}] &&& \\ && [y_ {0}, y_ {1}] && \\ x_ {1} & y_ {1} = [y_ {1}] && [y_ {0}, y_ {1}, y_ {2}] & \\ && [y_ {1}, y_ {2}] && [y_ {0}, y_ {1} , y_ {2}, y_ {3}] \\ x_ {2} & y_ {2} = [y_ {2}] && [y_ {1}, y_ {2}, y_ {3}] & \\ && [ y_ {2}, y_ {3}] && \\ x_ {3} & y_ {3} = [y_ {3}] &&& \\\ end {matrix}}}$

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

• Линейность

${\ displaystyle (f + g) [x_ {0}, \ dots, x_ {n}] = f [x_ {0}, \ dots, x_ {n}] + g [x_ {0}, \ dots, x_ {n}]}$

${\ displaystyle (\ lambda \ cdot f) [x_ {0}, \ dots, x_ {n}] = \ lambda \ cdot f [x_ {0}, \ dots, x_ {n}]}$

• Правило Лейбница

${\ displaystyle (f \ cdot g) [x_ {0}, \ dots, x_ {n}] = f [x_ {0}] \ cdot g [x_ {0}, \ dots, x_ {n}] + f [x_ {0}, x_ {1}] \ cdot g [x_ {1}, \ dots, x_ {n}] + \ dots + f [x_ {0}, \ dots, x_ {n}] \ cdot g [x_ {n}] = \ sum _ {r = 0} ^ {n} f [x_ {0}, \ ldots, x_ {r}] \ cdot g [x_ {r}, \ ldots, x_ {n} ]}$

• Разделенные разности симметричны: если это перестановка, то${\ displaystyle \ sigma: \ {0, \ dots, n \} \ to \ {0, \ dots, n \}}$

${\ displaystyle f [x_ {0}, \ dots, x_ {n}] = f [x _ {\ sigma (0)}, \ dots, x _ {\ sigma (n)}]}$

• Из теоремы о среднем значении для разделенных разностей следует, что

${\ displaystyle f [x_ {0}, \ dots, x_ {n}] = {\ frac {f ^ {(n)} (\ xi)} {n!}}}$где находится в открытом интервале, определяемом наименьшим и наибольшим из них .${\ displaystyle \ xi}$${\ displaystyle x_ {k}}$

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

Схема разделенных разностей может быть помещена в верхнюю треугольную матрицу . Пусть . ${\ displaystyle T_ {f} (x_ {0}, \ dots, x_ {n}) = {\ begin {pmatrix} f [x_ {0}] & f [x_ {0}, x_ {1}] & f [x_ {0}, x_ {1}, x_ {2}] & \ ldots & f [x_ {0}, \ dots, x_ {n}] \\ 0 & f [x_ {1}] & f [x_ {1}, x_ { 2}] & \ ldots & f [x_ {1}, \ dots, x_ {n}] \\\ vdots & \ vdots & \ vdots & \ ddots & \ vdots \\ 0 & 0 & 0 & \ ldots & f [x_ {n}] \ конец {pmatrix}}}$

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

• ${\ displaystyle T_ {f + g} x = T_ {f} x + T_ {g} x}$
• ${\ Displaystyle T_ {е \ cdot g} x = T_ {f} x \ cdot T_ {g} x}$

Это следует из правила Лейбница. Это означает, что умножение таких матриц коммутативно . Таким образом, матрицы схем разделенных разностей относительно одного и того же набора узлов образуют коммутативное кольцо .

• Поскольку матрица треугольная, ее собственные значения очевидны .${\ displaystyle T_ {f} x}$${\ displaystyle f (x_ {0}), \ dots, f (x_ {n})}$
• Пусть - дельта- подобная функция Кронекера, т. Е.${\ displaystyle \ delta _ {\ xi}}$

${\ displaystyle \ delta _ {\ xi} (t) = {\ begin {cases} 1 &: t = \ xi, \\ 0 &: {\ mbox {else}}. \ end {cases}}}$

Очевидно , значит , это собственная функция поточечного умножения функций. То есть это как - то « eigenmatrix » из : . Однако, все столбцы кратны друг друга, матрица ранга из равен 1. Таким образом , вы можете составить матрицу всех собственных векторов из -м столбце каждого . Обозначим матрицу собственных векторов через . Пример ${\ Displaystyle е \ cdot \ delta _ {\ xi} = f (\ xi) \ cdot \ delta _ {\ xi}}$${\ displaystyle \ delta _ {\ xi}}$${\ displaystyle T _ {\ delta _ {x_ {i}}} x}$${\ displaystyle T_ {f} x}$${\ displaystyle T_ {f} x \ cdot T _ {\ delta _ {x_ {i}}} x = f (x_ {i}) \ cdot T _ {\ delta _ {x_ {i}}} x}$${\ displaystyle T _ {\ delta _ {x_ {i}}} x}$${\ displaystyle T _ {\ delta _ {x_ {i}}} x}$${\ displaystyle i}$${\ displaystyle T _ {\ delta _ {x_ {i}}} x}$${\ displaystyle Ux}$

${\ displaystyle U (x_ {0}, x_ {1}, x_ {2}, x_ {3}) = {\ begin {pmatrix} 1 & {\ frac {1} {(x_ {1} -x_ {0}) )}} & {\ frac {1} {(x_ {2} -x_ {0}) \ cdot (x_ {2} -x_ {1})}} & {\ frac {1} {(x_ {3} -x_ {0}) \ cdot (x_ {3} -x_ {1}) \ cdot (x_ {3} -x_ {2})}} \\ 0 & 1 & {\ frac {1} {(x_ {2} - x_ {1})}} & {\ frac {1} {(x_ {3} -x_ {1}) \ cdot (x_ {3} -x_ {2})}} \\ 0 & 0 & 1 & {\ frac {1} {(x_ {3} -x_ {2})}} \\ 0 & 0 & 0 & 1 \ end {pmatrix}}}$

Диагонализация из можно записать в виде ${\ displaystyle T_ {f} x}$

${\ Displaystyle Ux \ cdot \ OperatorName {diag} (f (x_ {0}), \ dots, f (x_ {n})) = T_ {f} x \ cdot Ux}$.

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

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

${\ displaystyle {\ begin {align} f [x_ {0}] & = f (x_ {0}) \\ f [x_ {0}, x_ {1}] & = {\ frac {f (x_ {0}) })} {(x_ {0} -x_ {1})}} + {\ frac {f (x_ {1})} {(x_ {1} -x_ {0})}} \\ f [x_ { 0}, x_ {1}, x_ {2}] & = {\ frac {f (x_ {0})} {(x_ {0} -x_ {1}) \ cdot (x_ {0} -x_ {2 })}} + {\ frac {f (x_ {1})} {(x_ {1} -x_ {0}) \ cdot (x_ {1} -x_ {2})}} + {\ frac {f (x_ {2})} {(x_ {2} -x_ {0}) \ cdot (x_ {2} -x_ {1})}} \\ f [x_ {0}, x_ {1}, x_ { 2}, x_ {3}] & = {\ frac {f (x_ {0})} {(x_ {0} -x_ {1}) \ cdot (x_ {0} -x_ {2}) \ cdot ( x_ {0} -x_ {3})}} + {\ frac {f (x_ {1})} {(x_ {1} -x_ {0}) \ cdot (x_ {1} -x_ {2}) \ cdot (x_ {1} -x_ {3})}} + {\ frac {f (x_ {2})} {(x_ {2} -x_ {0}) \ cdot (x_ {2} -x_ { 1}) \ cdot (x_ {2} -x_ {3})}} + \\ & \ quad \ quad {\ frac {f (x_ {3})} {(x_ {3} -x_ {0}) \ cdot (x_ {3} -x_ {1}) \ cdot (x_ {3} -x_ {2})}} \\ f [x_ {0}, \ dots, x_ {n}] & = \ sum _ {j = 0} ^ {n} {\ frac {f (x_ {j})} {\ prod _ {k \ in \ {0, \ dots, n \} \ setminus \ {j \}} (x_ { j} -x_ {k})}} \ end {выровнено}}}$

С помощью полиномиальной функции с этим можно записать в виде ${\ displaystyle q}$${\ Displaystyle д (\ xi) = (\ xi -x_ {0}) \ cdots (\ xi -x_ {n})}$

${\ displaystyle f [x_ {0}, \ dots, x_ {n}] = \ sum _ {j = 0} ^ {n} {\ frac {f (x_ {j})} {q '(x_ {j })}}.}$

В качестве альтернативы мы можем разрешить отсчет в обратном порядке от начала последовательности, указав всякий раз, когда или . Это определение позволяет интерпретировать как , интерпретировать как , интерпретировать как и т. Д. Таким образом, расширенная форма разделенной разницы становится ${\ Displaystyle х_ {к} = х_ {к + п + 1} = х_ {к- (п + 1)}}$${\ displaystyle k <0}$${\ Displaystyle п <к}$${\ displaystyle x _ {- 1}}$${\ displaystyle x_ {n}}$${\ displaystyle x _ {- 2}}$${\ displaystyle x_ {n-1}}$${\ displaystyle x _ {- n}}$${\ displaystyle x_ {0}}$

${\ displaystyle f [x_ {0}, \ dots, x_ {n}] = \ sum _ {j = 0} ^ {n} {\ frac {f (x_ {j})} {\ prod \ limits _ { k = jn} ^ {j-1} (x_ {j} -x_ {k})}} = \ sum _ {j = 0} ^ {n} {\ frac {f (x_ {j})} {\ prod \ limits _ {k = j + 1} ^ {j + n} (x_ {j} -x_ {k})}}}$

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

${\ displaystyle f [x_ {0}, \ dots, x_ {n}] = \ sum _ {j = 0} ^ {n} \ lim _ {x \ rightarrow x_ {j}} \ left [{\ frac { f (x_ {j}) (x-x_ {j})} {\ prod \ limits _ {k = 0} ^ {n} (x-x_ {k})}} \ right]}$

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

Вы можете представить частичные дроби, используя развернутую форму разделенных разностей. (Это не упрощает вычисления, но интересен сам по себе.) Если и являются полиномиальные функции , где и дается в терминах линейных множителей с помощью , то из фракции разложения частичному этого ${\ displaystyle p}$${\ displaystyle q}$${\ Displaystyle \ mathrm {deg} \ p <\ mathrm {deg} \ q}$${\ displaystyle q}$${\ Displaystyle д (\ xi) = (\ xi -x_ {1}) \ cdot \ dots \ cdot (\ xi -x_ {n})}$

${\ Displaystyle {\ гидроразрыва {p (\ xi)} {q (\ xi)}} = \ left (t \ to {\ frac {p (t)} {\ xi -t}} \ right) [x_ { 1}, \ dots, x_ {n}].}$

Если пределы разделенных разностей приняты, то эта связь сохраняется, если некоторые из них совпадают. ${\ displaystyle x_ {j}}$

Если это полиномиальная функция с произвольной степенью и разлагается с использованием полиномиального деления на на , то ${\ displaystyle f}$${\ Displaystyle е (х) = п (х) + q (х) \ cdot d (х)}$${\ displaystyle f}$${\ displaystyle q}$

${\ displaystyle {\ frac {p (\ xi)} {q (\ xi)}} = \ left (t \ to {\ frac {f (t)} {\ xi -t}} \ right) [x_ { 1}, \ dots, x_ {n}].}$

Форма Пеано

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

${\ displaystyle f [x_ {0}, \ ldots, x_ {n}] = {\ frac {1} {n!}} \ int _ {x_ {0}} ^ {x_ {n}} f ^ {( n)} (t) B_ {n-1} (t) \, dt}$

где - B-сплайн степени для точек данных и - -я производная функции . ${\ displaystyle B_ {n-1}}$${\ displaystyle n-1}$${\ displaystyle x_ {0}, \ dots, x_ {n}}$${\ displaystyle f ^ {(n)}}$${\ displaystyle n}$${\ displaystyle f}$

Это называется Пеано формой из разделенных разностей и называется ядром Пеана для разделенных разностей, названного в честь Джузеппе Пеано . ${\ displaystyle B_ {n-1}}$

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

Первый заказ

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

${\ Displaystyle {\ гидроразрыва {f (y) -f (x)} {yx}} \ приблизительно f '(x)}$ для ${\ Displaystyle х \ приблизительно у}$

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

${\ Displaystyle f (y) = f (x) + f '(x) \ cdot (yx) + f' '(x) \ cdot {\ frac {(yx) ^ {2}} {2!}} + f '' '(x) \ cdot {\ frac {(yx) ^ {3}} {3!}} + \ точки}$

${\ displaystyle \ Rightarrow {\ frac {f (y) -f (x)} {yx}} = f '(x) + f' '(x) \ cdot {\ frac {yx} {2!}} + f '' '(x) \ cdot {\ frac {(yx) ^ {2}} {3!}} + \ точки}$

Вы можете устранить нечетные степени , расширив ряд Тейлора в центре между и : ${\ displaystyle yx}$${\ displaystyle x}$${\ displaystyle y}$

${\ Displaystyle х = mh, y = m + h}$, это ${\ displaystyle m = {\ frac {x + y} {2}}, h = {\ frac {yx} {2}}}$

${\ displaystyle f (m + h) = f (m) + f '(m) \ cdot h + f' '(m) \ cdot {\ frac {h ^ {2}} {2!}} + f' '' (м) \ cdot {\ frac {h ^ {3}} {3!}} + \ точки}$

${\ displaystyle f (mh) = f (m) -f '(m) \ cdot h + f' '(m) \ cdot {\ frac {h ^ {2}} {2!}} - f' '' (м) \ cdot {\ frac {h ^ {3}} {3!}} + \ точки}$

${\ displaystyle {\ frac {f (y) -f (x)} {yx}} = {\ frac {f (m + h) -f (mh)} {2 \ cdot h}} = f '(m ) + f '' '(m) \ cdot {\ frac {h ^ {2}} {3!}} + \ точки}$

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

Ряд Тейлора или любое другое представление с функциональным рядом в принципе можно использовать для аппроксимации разделенных разностей. Ряды Тейлора представляют собой бесконечные суммы степенных функций . Преобразование функции в разделенную разность - это линейный функционал . Мы также можем применить этот функционал к слагаемым функциям. ${\ displaystyle f}$${\ displaystyle f [x_ {0}, \ dots, x_ {n}]}$

Выразите обозначение мощности с помощью обычной функции: ${\ displaystyle p_ {n} (x) = x ^ {n}.}$

Регулярный ряд Тейлора представляет собой взвешенную сумму степенных функций: ${\ displaystyle f = f (0) \ cdot p_ {0} + f '(0) \ cdot p_ {1} + {\ frac {f' '(0)} {2!}} \ cdot p_ {2} + {\ frac {f '' '(0)} {3!}} \ cdot p_ {3} + \ dots}$

Ряд Тейлора для разделенных разностей: ${\ displaystyle f [x_ {0}, \ dots, x_ {n}] = f (0) \ cdot p_ {0} [x_ {0}, \ dots, x_ {n}] + f '(0) \ cdot p_ {1} [x_ {0}, \ dots, x_ {n}] + {\ frac {f '' (0)} {2!}} \ cdot p_ {2} [x_ {0}, \ dots , x_ {n}] + {\ frac {f '' '(0)} {3!}} \ cdot p_ {3} [x_ {0}, \ dots, x_ {n}] + \ dots}$

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

${\ displaystyle {\ begin {array} {llcl} \ forall j <n & p_ {j} [x_ {0}, \ dots, x_ {n}] & = & 0 \\ & p_ {n} [x_ {0}, \ точки, x_ {n}] & = & 1 \\ & p_ {n + 1} [x_ {0}, \ dots, x_ {n}] & = & x_ {0} + \ dots + x_ {n} \\ & p_ { n + m} [x_ {0}, \ dots, x_ {n}] & = & \ sum _ {a \ in \ {0, \ dots, n \} ^ {m} {\ text {with}} a_ {1} \ leq a_ {2} \ leq \ dots \ leq a_ {m}} \ prod _ {j \ in a} x_ {j}. \\\ end {array}}}$

Отсюда следует, что ряд Тейлора для разделенной разности по существу начинается с того, что также является простой аппроксимацией разделенной разности в соответствии с теоремой о среднем значении для разделенных разностей . ${\ displaystyle {\ frac {f ^ {(n)} (0)} {n!}}}$

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

${\ displaystyle t ^ {n} = (1-x_ {0} \ cdot t) \ dots \ cdot (1-x_ {n} \ cdot t) \ cdot (p_ {0} [x_ {0}, \ dots , x_ {n}] + p_ {1} [x_ {0}, \ dots, x_ {n}] \ cdot t + p_ {2} [x_ {0}, \ dots, x_ {n}] \ cdot t ^ {2} + \ точки).}$

Следовательно, мы можем вычислить разделенных разностей от с разделением на формальных степенных рядов . Посмотрите, как это сводится к последовательному вычислению степеней, когда мы вычисляем для нескольких . ${\ displaystyle p_ {n}}$${\ displaystyle p_ {n} [h]}$${\ displaystyle n}$

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

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

Разделенные разности многочленов особенно интересны, потому что они могут извлечь выгоду из правила Лейбница. Матрица с ${\ displaystyle J}$

${\ displaystyle J = {\ begin {pmatrix} x_ {0} & 1 & 0 & 0 & \ cdots & 0 \\ 0 & x_ {1} & 1 & 0 & \ cdots & 0 \\ 0 & 0 & x_ {2} & 1 && 0 \\\ vdots & \ vdots && \ ddots & \ ddots & \\ 0 & 0 & 0 & 0 && x_ {n} \ end {pmatrix}}}$

содержит схему разделенных разностей для функции идентичности по отношению к узлам , таким образом, содержит разделенные разности для функции мощности с показателем . Следовательно, вы можете получить разделенные разности для полиномиальной функции относительно полинома , применяя (точнее: соответствующую матричную полиномиальную функцию ) к матрице . ${\ displaystyle x_ {0}, \ dots, x_ {n}}$${\ displaystyle J ^ {n}}$ ${\ displaystyle n}$ ${\ displaystyle \ varphi (p)}$ ${\ displaystyle p}$${\ displaystyle p}$${\ displaystyle \ varphi _ {\ mathrm {M}} (p)}$${\ displaystyle J}$

${\ displaystyle \ varphi (p) (\ xi) = a_ {0} + a_ {1} \ cdot \ xi + \ dots + a_ {n} \ cdot \ xi ^ {n}}$

${\ displaystyle \ varphi _ {\ mathrm {M}} (p) (J) = a_ {0} + a_ {1} \ cdot J + \ dots + a_ {n} \ cdot J ^ {n}}$

${\ displaystyle = {\ begin {pmatrix} \ varphi (p) [x_ {0}] & \ varphi (p) [x_ {0}, x_ {1}] & \ varphi (p) [x_ {0}, x_ {1}, x_ {2}] & \ ldots & \ varphi (p) [x_ {0}, \ dots, x_ {n}] \\ 0 & \ varphi (p) [x_ {1}] & \ varphi (p) [x_ {1}, x_ {2}] & \ ldots & \ varphi (p) [x_ {1}, \ dots, x_ {n}] \\\ vdots & \ ddots & \ ddots & \ ddots & \ vdots \\ 0 & \ ldots & 0 & 0 & \ varphi (p) [x_ {n}] \ end {pmatrix}}}$

Это известно как формула Опица .

Теперь рассмотрим увеличение степени до бесконечности, т.е. превратим многочлен Тейлора в ряд Тейлора . Позвольте быть функцией, которая соответствует степенному ряду . Вы можете вычислить схему разделенных разностей, вычислив соответствующий матричный ряд, к которому применяется . Если все узлы равны, то это жорданов блок, и вычисление сводится к обобщению скалярной функции на матричную функцию с использованием разложения Жордана . ${\ displaystyle p}$${\ displaystyle f}$${\ displaystyle J}$${\ displaystyle x_ {0}, \ dots, x_ {n}}$${\ displaystyle J}$

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

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

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

Определение

Учитывая n точек данных

${\ displaystyle (x_ {0}, y_ {0}), \ ldots, (x_ {n-1}, y_ {n-1})}$

с

${\ Displaystyle х _ {\ ню} = х_ {0} + \ ню ч, \ ч> 0, \ \ ню = 0, \ ldots, п-1}$

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

${\ displaystyle \ Delta ^ {(0)} y_ {i}: = y_ {i}}$

${\ Displaystyle \ Delta ^ {(k)} y_ {i}: = \ Delta ^ {(k-1)} y_ {i + 1} - \ Delta ^ {(k-1)} y_ {i}, \ k \ geq 1.}$

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

${\ displaystyle f [x_ {0}, x_ {1}, \ ldots, x_ {k}] = {\ frac {1} {k! h ^ {k}}} \ Delta ^ {(k)} f ( x_ {0}).}$

Пример

${\ displaystyle {\ begin {matrix} y_ {0} &&& \\ & \ Delta y_ {0} && \\ y_ {1} && \ Delta ^ {2} y_ {0} & \\ & \ Delta y_ {1 } && \ Delta ^ {3} y_ {0} \\ y_ {2} && \ Delta ^ {2} y_ {1} & \\ & \ Delta y_ {2} && \\ y_ {3} &&& \\\ конец {матрица}}}$

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

• Коэффициент разницы
• Алгоритм Невилла
• Полиномиальная интерполяция
• Теорема о среднем значении для разделенных разностей
• Интеграл Норлунда – Райса
• Треугольник Паскаля

использованная литература

• Луи Мелвилл Милн-Томсон (2000) [1933]. Исчисление конечных разностей . American Mathematical Soc. Глава 1: Разделенные различия. ISBN 978-0-8218-2107-7.
• Майрон Б. Аллен; Эли Л. Исааксон (1998). Численный анализ для прикладных наук . Джон Вили и сыновья. Приложение A. ISBN 978-1-118-03027-1.
• Рон Голдман (2002). Алгоритмы пирамиды: подход динамического программирования к кривым и поверхностям для геометрического моделирования . Морган Кауфманн. Глава 4: Интерполяция Ньютона и разностные треугольники. ISBN 978-0-08-051547-2.

внешние ссылки

• Реализация в Haskell .