Разделенные разности

редактировать

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

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

Содержание

1 Определение
2 Обозначение
3 Пример
4 Свойства
- 4.1 Матричная форма
5 Альтернативные определения
- 5.1 Расширенная форма
  - 5.1.1 Частичные дроби
- 5.2 Форма Пеано
- 5.3 Форма Тейлора
  - 5.3.1 Первый порядок
  - 5.3.2 Высший порядок
6 Полиномы и степенные ряды
7 Прямые разности
- 7.1 Определение
- 7.2 Пример
8 См. Также
9 Ссылки
10 Внешние ссылки

Определение

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

(x 0, y 0),…, (xk, yk) {\ displaystyle (x_ {0}, y_ {0}), \ ldots, (x_ { k}, y_ {k})}

(x_ {0}, y_ {0}), \ ldots, (x _ {{k}}, y _ {{k}})

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

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

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

[y ν,…, y ν + j]: = [y ν + 1,…, y ν + j] - [y ν,…, y ν + j - 1] x ν + j - x ν, ν ∈ {0,…, k - j}, j ∈ {1, …, 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 \}.}

[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 \}.

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

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

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

[y ν,…, y ν - j]: = [y ν,…, y ν - j + 1] - [y ν - 1,…, y ν - j] x ν - x ν - j, ν ∈ {j,…, k}, j ∈ {1,…, 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 \}.}

[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 \}.

Обозначение

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

(x 0, f (x 0)),…, (xk, f (xk)) {\ displaystyle (x_ {0}, f (x_ {0})), \ ldots, (x_ {k}, f (x_ {k}))}

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

иногда пишут

f [x ν]: = f (x ν), ν ∈ {0,…, k} {\ displaystyle f [x _ {\ nu}]: = f (x _ {\ nu }), \ qquad \ nu \ in \ {0, \ ldots, k \}}

f [x _ {\ nu}]: = f (x _ {{\ nu}}), \ qquad \ nu \ in \ {0, \ ldots, k \}

f [x ν,…, x ν + j]: = f [x ν + 1,…, x ν + j ] - f [x ν,…, x ν + j - 1] x ν + j - x ν, ν ∈ {0,…, k - j}, j ∈ {1,…, 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 \}.}

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 0,..., x n используются:

[x 0,…, xn] f, {\ displaystyle [x_ {0}, \ ldots, x_ {n}] f,}

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

[x 0,…, xn; е], {\ displaystyle [x_ {0}, \ ldots, x_ {n}; f],}

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

D [x 0,…, xn] f {\ displaystyle D [x_ {0}, \ ldots, x_ {n}] f}

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

и т. д.

Пример

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

[y 0] = y 0 [y 0, y 1] = y 1 - y 0 x 1 - x 0 [y 0, y 1, y 2] = [y 1, y 2] - [y 0, y 1] x 2 - x 0 = y 2 - y 1 x 2 - x 1 - y 1 - y 0 x 1 - x 0 x 2 - x 0 = y 2 - y 1 (x 2 - x 1) (x 2 - x 0) - y 1 - y 0 (x 1 - x 0) (x 2 - x 0) [y 0, y 1, y 2, y 3] = [y 1, y 2, y 3 ] - [y 0, y 1, y 2] x 3 - x 0 {\ displaystyle {\ begin {align} {\ mathopen {[}} y_ {0}] = y_ {0} \\ {\ mathopen { [}} y_ {0}, y_ {1}] = {\ frac {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}] - {\ m athopen {[}} y_ {0}, y_ {1}, y_ {2}]} {x_ {3} -x_ {0}}} \ end {align}}}

{\ begin {align} {\ mathopen [} y_ {0}] = y_ {0} \\ {\ mathopen [} y_ {0}, y_ {1}] = {\ frac {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 {align}}

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

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] {\ 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}}}

{\ 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}}

Свойства

Линейность

(f + g) [x 0,…, xn] = f [x 0,…, xn] + g [x 0,…, xn] {\ displaystyle (f + g) [x_ {0}, \ точки, x_ {n}] = f [x_ {0}, \ dots, x_ {n}] + g [x_ {0}, \ dots, x_ {n}]}

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

(λ ⋅ f) [Икс 0,…, xn] = λ ⋅ е [x 0,…, xn] {\ displaystyle (\ lambda \ cdot f) [x_ {0}, \ dots, x_ {n}] = \ lambda \ cdot f [x_ {0}, \ dots, x_ {n}]}

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

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

(f ⋅ g) [x 0,…, xn] = f [x 0] ⋅ g [x 0,…, xn] + f [x 0, x 1] ⋅ g [x 1,…, xn] + ⋯ + f [x 0,…, xn] ⋅ g [ xn] знак равно ∑ р знак равно 0 nf [x 0,…, xr] ⋅ g [xr,…, xn] {\ 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}]}

(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}]

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

f [ x 0,…, xn] = е [x σ (0),…, x σ (n)] {\ displaystyle f [x_ {0}, \ dots, x_ {n}] = f [x _ {\ sigma ( 0)}, \ dots, x _ {\ sigma (n)}]}

f[x_{0},\dots,x_{n}]=f[x_{\sigma (0)},\dots,x_{\sigma (n)}]

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

f [x 0,…, xn] = е (п) (ξ) п! {\ displaystyle f [x_ {0}, \ dots, x_ {n}] = {\ frac {f ^ {(n)} (\ xi)} {n!}}}

f[x_{0},\dots,x_{n}]={\frac {f^{{(n)}}(\xi)}{n!}}

где

ξ {\ displaystyle \ xi}

\ xi

находится в открытом интервале, определяемом наименьшим и наибольшим из значений

xk {\ displaystyle x_ {k}}

x_ {k}

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

Схема разделенных разностей может быть помещена в верхнюю треугольную матрицу. Пусть $T f (x 0,…, xn) = (f [x 0] f [x 0, x 1] f [x 0, x 1, x 2]… f [x 0,…, xn] 0 f [x 1] f [x 1, x 2]… f [x 1,…, xn] ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0… f [xn]) {\ 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}] \ end {pmatrix}}}$ $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}] \ end {pmatrix}}$ .

Тогда выполняется

$T f + gx = T fx + T gx {\ displaystyle T_ {f + g} x = T_ {f} x + T_ {g} x}$ $T_{{f+g}}x=T_{f}x+T_{g}x$
$T f ⋅ gx = T fx ⋅ T gx { \ displaystyle T_ {f \ cdot g} x = T_ {f} x \ cdot T_ {g} x}$ $T_{{f\cdot g}}x=T_{f}x\cdot T_{g}x$

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

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

δ ξ (t) = {1: t = ξ, 0: иначе. {\ displaystyle \ delta _ {\ xi} (t) = {\ begin {cases} 1 : t = \ xi, \\ 0 : {\ t_dv {else}}. \ end {ases}}}

\ delta _ {\ xi} (t) = {\ begin {cases} 1 : t = \ xi, \\ 0 : {\ t_dv {else}}. \ end {case}}

Очевидно

е ⋅ δ ξ знак равно е (ξ) ⋅ δ ξ {\ displaystyle f \ cdot \ delta _ {\ xi} = f (\ xi) \ cdot \ delta _ {\ xi}}

f \ cdot \ delta _ {\ xi} = f (\ xi) \ cdot \ delta _ {\ xi}

, таким образом,

δ ξ {\ displaystyle \ delta _ {\ xi}}

\ delta _ {\ xi}

является собственной функцией поточечного умножения функций. То есть

T δ xix {\ displaystyle T _ {\ delta _ {x_ {i}}} x}

T _ {{\ delta _ {{x_ {i}}}}} x

каким-то образом является «собственной матрицей »

T fx { \ displaystyle T_ {f} x}

T_{f}x

T fx ⋅ T δ xix = f (xi) ⋅ T δ xix {\ displaystyle T_ {f} x \ cdot T _ {\ delta _ {x_ {i}}} x = f (x_ {i}) \ cdot T _ {\ delta _ {x_ {i}}} x}

T_{f}x\cdot T_{{\delta _{ {x_{i}}}}}x=f(x_{i})\cdot T_{{\delta _{{x_{i}}}}}x

. Однако все столбцы

T δ xix {\ displaystyle T _ {\ delta _ {x_ {i}}} x}

T _ {{\ delta _ {{x_ {i}}}}} x

кратны друг другу, ранг матрицы

T δ xix {\ displaystyle T _ {\ delta _ {x_ {i}}} x}

T _ {{\ delta _ {{x_ {i}}}}} x

равно 1. Таким образом, вы можете составить матрицу всех собственных векторов из

i {\ displaystyle i}

i

-й столбец каждого

T δ xix {\ displaystyle T _ {\ delta _ {x_ {i}}} x}

T _ {{\ delta _ {{x_ {i}}}}} x

. Обозначим матрицу собственных векторов с помощью

U x {\ displaystyle Ux}

Ux

. Пример

U (x 0, x 1, x 2, x 3) = (1 1 (x 1 - x 0) 1 (x 2 - x 0) ⋅ (x 2 - x 1) 1 (x 3 - x 0) ⋅ (x 3 - x 1) ⋅ (x 3 - x 2) 0 1 1 (x 2 - x 1) 1 (x 3 - x 1) ⋅ (x 3 - x 2) 0 0 1 1 ( x 3 - x 2) 0 0 0 1) {\ 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 {\ гидроразрыв {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}}}

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}}

диагонализация

T fx {\ displaystyle T_ {f} x}

T_{f}x

можно записать как

U x ⋅ diag ⁡ (f (x 0),…, f (xn)) = T fx ⋅ U x { \ displaystyle Ux \ cdot \ operatorname {diag} (f (x_ {0}), \ dots, f (x_ {n})) = T_ {f} x \ cdot Ux}

Ux \ cdot \ operatorname {diag} (f (x_ {0}), \ dots, f (x_ {n})) = T_ {f} x \ cdot Ux

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

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

$f [x 0] = f (x 0) f [x 0, x 1] = f (x 0) (x 0 - x 1) + f (x 1) (x 1 - x 0) f [x 0, x 1, x 2] = f (x 0) (x 0 - x 1) ⋅ (x 0 - x 2) + f (x 1) (x 1 - x 0) ⋅ (x 1 - x 2) + f (x 2) (x 2 - x 0) ⋅ (x 2 - x 1) f [x 0, x 1, x 2, x 3] = f (x 0) (x 0 - x 1) ⋅ (x 0 - x 2) ⋅ (x 0 - x 3) + f (x 1) (x 1 - x 0) ⋅ (x 1 - x 2) ⋅ (x 1 - x 3) + f (x 2) (x 2 - x 0) ⋅ (x 2 - x 1) ⋅ (x 2 - x 3) + f (x 3) (x 3 - x 0) ⋅ (x 3 - x 1) ⋅ (x 3 - x 2) f [x 0,…, xn] = ∑ j = 0 nf (xj) ∏ К ∈ {0,…, n} ∖ {j} (xj - xk) {\ 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 {align}}}$ ${\begin{aligned}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{aligned}}$

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

f [x 0,…, xn] = ∑ j = 0 nf (xj) q ′ (xj). {\ displaystyle f [x_ {0}, \ dots, x_ {n}] = \ sum _ {j = 0} ^ {n} {\ frac {f (x_ {j})} {q '(x_ {j })}}.}

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

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

$f [x 0,…, xn] = ∑ J знак равно 0 NF (XJ) ∏ К знак равно J - NJ - 1 (XJ - XK) + ∑ J = 0 NF (XJ) ∏ К = J + 1 J + N (XJ - XK) {\ 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})}}}$ $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)}$

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

$f [x 0,…, xn] = ∑ j = 0 n lim x → xj [е (xj) (x - xj) ∏ k = 0 n (x - xk)] {\ 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]}$ $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]$

Частичные дроби

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

p (ξ) q (ξ) = (t → p (t) ξ - t) [x 1,…, xn]. {\ displaystyle {\ frac {p (\ xi)} {q (\ xi)}} = \ left (t \ to {\ frac {p (t)} {\ xi -t}} \ right) [x_ { 1}, \ dots, x_ {n}].}

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

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

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

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

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

Форма Пеано

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

f [x 0,…, xn] = 1 n! ∫ Икс 0 xnf (N) (t) B n - 1 (t) dt {\ displaystyle f [x_ {0}, \ ldots, x_ {n}] = {\ frac {1} {n!}} \ Int _ {x_ {0}} ^ {x_ {n}} f ^ {(n)} (t) B_ {n-1} (t) \, dt}

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

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

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

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

Первый порядок

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

f (y) - f (x) y - x ≈ f ′ (x) {\ displaystyle {\ frac {f (y) -f (x)} {yx}} \ приблизительно f '(x)}

{\frac {f(y)-f(x)}{y-x}}\approx f'(x)

для

x ≈ y {\ displaystyle x \ приблизительно y}

x \ приблизительно y

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

f (y) = f (x) + f ′ (x) ⋅ (y - x) + f ″ (x) ⋅ (y - x) 2 2! + е ‴ (х) ⋅ (у - х) 3 3! +… {\ Displaystyle f (y) = f (x) + f '(x) \ cdot (yx) + f' '(x) \ cdot {\ frac {(yx) ^ {2}} {2!} } + f '' '(x) \ cdot {\ frac {(yx) ^ {3}} {3!}} + \ dots}

f(y)=f(x)+f'(x)\cdot (y-x)+f''(x)\cdot {\frac {(y-x)^{2}}{2!}}+f'''(x)\cdot {\frac {(y-x)^{3}}{3!}}+\dots

⇒ f (y) - f (x) y - x = f ′ (Х) + е ″ (х) ⋅ у - х 2! + е ‴ (х) ⋅ (у - х) 2 3! +… {\ Displaystyle \ Rightarrow {\ frac {f (y) -f (x)} {yx}} = f '(x) + f' '(x) \ cdot {\ frac {yx} {2!} } + f '' '(x) \ cdot {\ frac {(yx) ^ {2}} {3!}} + \ dots}

\Rightarrow {\frac {f(y)-f(x)}{y-x}}=f'(x)+f''(x)\cdot {\frac {y-x}{2!}}+f'''(x)\cdot {\frac {(y-x)^{2}}{3!}}+\dots

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

x = m - h, y = m + h {\ displaystyle x = mh, y = m + h}

x=m-h,y=m+h

, то есть

m = x + y 2, h = y - x 2 {\ displaystyle m = {\ frac {x + y} {2}}, h = {\ frac {yx} {2}}}

m = {\ frac {x + y} {2}}, h = {\ frac {yx } {2}}

f (m + h) = f (m) + f ′ ( м) ⋅ ч + е ​​″ (м) ⋅ ч 2 2! + е ‴ (м) ⋅ ч 3 3! +… {\ Displaystyle f (m + h) = f (m) + f '(m) \ cdot h + f' '(m) \ cdot {\ frac {h ^ {2}} {2!}} + f '' '(m) \ cdot {\ frac {h ^ {3}} {3!}} + \ dots}

f(m+h)=f(m)+f'(m)\cdot h+f''(m)\cdot {\frac {h^{2}}{2!}}+f'''(m)\cdot {\frac {h^{3}}{3!}}+\dots

f (m - h) = f (m) - f ′ (m) ⋅ h + f ″ (м) ⋅ ч 2 2! - е ‴ (м) ⋅ ч 3 3! +… {\ Displaystyle f (mh) = f (m) -f '(m) \ cdot h + f' '(m) \ cdot {\ frac {h ^ {2}} {2!}} - f' '' (m) \ cdot {\ frac {h ^ {3}} {3!}} + \ dots}

f(m-h)=f(m)-f'(m)\cdot h+f''(m)\cdot {\frac {h^{2}}{2!}}-f'''(m)\cdot {\frac {h^{3}}{3!}}+\dots

f (y) - f (x) y - x = f (m + h) - f (м - ч) 2 ⋅ ч = е '(м) + е ‴ (м) ⋅ ч 2 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!}} + \ dots}

{\frac {f(y)-f(x)}{y-x}}={\frac {f(m+h)-f(m-h)}{2\cdot h}}=f'(m)+f'''(m)\cdot {\frac {h^{2}}{3!}}+\dots

Высший порядок

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

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

Регулярный ряд Тейлора представляет собой взвешенную сумму степенных функций: $f = f (0) ⋅ p 0 + f ′ (0) ⋅ п 1 + е ″ (0) 2! ⋅ п 2 + е ‴ (0) 3! ⋅ п 3 +… {\ 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}$ $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$

Ряд Тейлора для разделенных разностей: $f [x 0, …, Xn] = f (0) ⋅ p 0 [x 0,…, xn] + f ′ (0) ⋅ p 1 [x 0,…, xn] + f ″ (0) 2! ⋅ p 2 [x 0,…, x n] + f ‴ (0) 3! ⋅ п 3 [x 0,…, xn] +… {\ 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}, \ точки, x_ {n}] + \ dots}$ $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$

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

∀ j < n p j [ x 0, …, x n ] = 0 p n [ x 0, …, x n ] = 1 p n + 1 [ x 0, …, x n ] = x 0 + ⋯ + x n p n + m [ x 0, …, x n ] = ∑ a ∈ { 0, …, n } m with a 1 ≤ a 2 ≤ ⋯ ≤ a m ∏ j ∈ a x j. {\displaystyle {\begin{array}{llcl}\forall j

{\begin{array}{llcl}\forall j<np_{j}[x_{0},\dots,x_{n}]=0\\p_{n}[x_{0},\dots,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}}

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

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

tn = (1 - x 0 ⋅ t) ⋯ ⋅ (1 - xn ⋅ t) ⋅ (p 0 [x 0,…, xn] + p 1 [x 0,…, xn] ⋅ t + p 2 [x 0,…, xn] ⋅ t 2 +…). {\ 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} + \ dots).}

t ^ {n} = (1- х_ {0} \ cdot t) \ точки \ 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} + \ dots).

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

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

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

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

J = (x 0 1 0 0 ⋯ 0 0 x 1 1 0 ⋯ 0 0 0 x 2 1 0 ⋮ ⋮ ⋱ ⋱ 0 0 0 0 xn) {\ 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}}}

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 \ d точки \ ddots \\ 0 0 0 0 x_ {n} \ end {pmatrix}}

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

φ (p) (ξ) = a 0 + a 1 ⋅ ξ + ⋯ + an ⋅ ξ N {\ displaystyle \ varphi (p) (\ xi) = a_ {0} + a_ {1} \ cdot \ xi + \ dots + a_ {n} \ cdot \ xi ^ {n}}

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

φ M (p) (J) знак равно a 0 + a 1 ⋅ J + ⋯ + an ⋅ J n {\ displaystyle \ varphi _ {\ mathrm {M}} (p) (J) = a_ {0} + a_ {1} \ cdot J + \ dots + a_ {n} \ cdot J ^ {n}}

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

= (φ (p) [x 0] φ (p) [x 0, x 1 ] φ (p) [x 0, x 1, x 2]… φ (p) [x 0,…, xn] 0 φ (p) [x 1] φ (p) [x 1, x 2]… φ (п) [Икс 1,…, xn] ⋮ ⋱ ⋱ ⋱ ⋮ 0… 0 0 φ (p) [xn]) {\ 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}}}

= { \ 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}}

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

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

Прямые разности

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

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

Определение

Дано n точек данных

(x 0, y 0),…, (xn - 1, yn - 1) {\ displaystyle (x_ {0}, y_ {0}), \ ldots, (x_ {n-1}, y_ {n-1})}

(x_ {0}, y_ {0}), \ ldots, (x _ {{n-1}}, y _ {{n-1}})

x ν = x 0 + ν h, h>0, ν = 0,…, n - 1 {\ displaystyle x_ {\ nu} = x_ {0} + \ nu h, \ h>0, \ \ nu = 0, \ ldots, n-1}

x_{\nu }=x_{0}+\nu h,\ h>0, \ \ nu = 0, \ ldots, n -1

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

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

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

Δ (к) yi: знак равно Δ (k - 1) yi + 1 - Δ (k - 1) yi, k ≥ 1. {\ displaystyle \ Delta ^ {(k)} y_ {i}: = \ Delta ^ { (k-1)} y_ {i + 1} - \ Delta ^ {(k-1)} y_ {i}, \ k \ geq 1.}

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

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

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

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

Пример

y 0 Δ y 0 y 1 Δ 2 y 0 Δ y 1 Δ 3 y 0 y 2 Δ 2 y 1 Δ y 2 y 3 {\ displaystyle {\ begin { матрица} 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} \\\ end {matrix}}}

{\ 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} \\\ конец {матрица}}}

См. Также

Ссылки

Луи Мелвилл Милн -Thomson (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.