Diferenças divididas - Divided differences

Em matemática , diferenças divididas é um algoritmo , historicamente usado para calcular tabelas de logaritmos e funções trigonométricas . O mecanismo de diferença de Charles Babbage , uma das primeiras calculadoras mecânicas , foi projetado para usar esse algoritmo em sua operação.

Diferenças divididas é um processo de divisão recursivo . O método pode ser usado para calcular os coeficientes no polinômio de interpolação na forma de Newton .

Definição

Dados k  + 1 pontos de dados

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

As diferenças divididas para a frente são definidas como:

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

As diferenças divididas para trás são definidas como:

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

Notação

Se os pontos de dados são fornecidos como uma função ƒ ,

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

um às vezes escreve

${\ displaystyle f [x _ {\ nu}]: = f (x _ {\ nu}), \ 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 \}.}$

Várias notações para a diferença dividida da função ƒ nos nós x ₀ , ...,  x _n são usadas:

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

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

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

etc.

Exemplo

Diferenças divididas para e os primeiros valores de : ${\ displaystyle \ nu = 0}$${\ displaystyle j}$

${\ 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}] - {\ mathopen {[}} y_ {0}, y_ {1}, y_ {2}]} {x_ {3} -x_ {0}}} \ end {alinhado }}}$

Para tornar o processo recursivo mais claro, as diferenças divididas podem ser colocadas em uma forma tabular:

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

Propriedades

• Linearidade

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

• Regra Leibniz

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

• As diferenças divididas são simétricas: Se for uma permutação, então${\ displaystyle \ sigma: \ {0, \ dots, n \} \ to \ {0, \ dots, n \}}$

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

• A partir do teorema do valor médio para diferenças divididas , segue-se que

${\ displaystyle f [x_ {0}, \ dots, x_ {n}] = {\ frac {f ^ {(n)} (\ xi)} {n!}}}$onde está no intervalo aberto determinado pelo menor e maior dos 's.${\ displaystyle \ xi}$${\ displaystyle x_ {k}}$

Forma de matriz

O esquema de diferença dividido pode ser colocado em uma matriz triangular superior . Deixe . ${\ 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}] \ fim {pmatrix}}}$

Então segura

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

Isso segue a regra de Leibniz. Isso significa que a multiplicação de tais matrizes é comutativa . Resumindo, as matrizes de esquemas de diferenças divididas com respeito ao mesmo conjunto de nós formam um anel comutativo .

• Como é uma matriz triangular, seus autovalores são obviamente .${\ displaystyle T_ {f} x}$${\ displaystyle f (x_ {0}), \ dots, f (x_ {n})}$
• Seja uma função do tipo delta de Kronecker , que é${\ displaystyle \ delta _ {\ xi}}$

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

Obviamente , portanto, é uma autofunção da multiplicação de função pontual. Que é de alguma forma é um " eigenmatrix " de : . No entanto, todas as colunas de são múltiplos entre si, a classificação da matriz de é 1. Portanto, você pode compor a matriz de todos os autovetores da -ésima coluna de cada um . Denote a matriz de vetores próprios com . Exemplo ${\ displaystyle f \ 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 {pmatriz}}}$

A diagonalização de pode ser escrita como ${\ displaystyle T_ {f} x}$

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

Definições alternativas

Forma expandida

${\ displaystyle {\ begin {alinhados} 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 {alinhado}}}$

Com a ajuda de uma função polinomial com isso pode ser escrito como ${\ displaystyle q}$${\ displaystyle q (\ 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 })}}.}$

Como alternativa, podemos permitir a contagem regressiva desde o início da sequência, definindo sempre ou . Esta definição permite ser interpretada como , interpretada como , interpretada como , etc. A forma expandida da diferença dividida torna-se assim ${\ displaystyle x_ {k} = x_ {k + n + 1} = x_ {k- (n + 1)}}$${\ displaystyle k <0}$${\ displaystyle n <k}$${\ 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})}}}$

Ainda outra caracterização utiliza limites:

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

Frações Parciais

Você pode representar frações parciais usando a forma expandida de diferenças divididas. (Isso não simplifica o cálculo, mas é interessante por si só.) Se e são funções polinomiais , onde e é dado em termos de fatores lineares por , então segue da decomposição da fração parcial que ${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle \ mathrm {deg} \ p <\ mathrm {deg} \ q}$${\ displaystyle q}$${\ displaystyle q (\ xi) = (\ xi -x_ {1}) \ cdot \ dots \ cdot (\ xi -x_ {n})}$

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

Se os limites das diferenças divididas forem aceitos, essa conexão também será válida, se algumas das diferenças coincidirem. ${\ displaystyle x_ {j}}$

Se é uma função polinomial com grau arbitrário e é decomposta usando a divisão polinomial de por , então ${\ displaystyle f}$${\ displaystyle f (x) = p (x) + q (x) \ cdot d (x)}$${\ displaystyle f}$${\ displaystyle q}$

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

Forma peano

As diferenças divididas podem ser expressas como

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

onde é um B-spline de grau para os pontos de dados e é a -ésima derivada da função . ${\ displaystyle B_ {n-1}}$${\ displaystyle n-1}$${\ displaystyle x_ {0}, \ dots, x_ {n}}$${\ displaystyle f ^ {(n)}}$${\ displaystyle n}$${\ displaystyle f}$

Isso é chamado de forma de Peano das diferenças divididas e é chamado de kernel de Peano para as diferenças divididas, ambas em homenagem a Giuseppe Peano . ${\ displaystyle B_ {n-1}}$

Forma de Taylor

Primeira ordem

Se os nós são acumulados, o cálculo numérico das diferenças divididas é impreciso, porque você divide quase dois zeros, cada um dos quais com um erro relativo alto devido a diferenças de valores semelhantes . No entanto, sabemos que os quocientes de diferença se aproximam da derivada e vice-versa:

${\ displaystyle {\ frac {f (y) -f (x)} {yx}} \ approx f '(x)}$ para ${\ displaystyle x \ approx y}$

Essa aproximação pode ser transformada em uma identidade sempre que o teorema de Taylor se aplicar.

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

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

Você pode eliminar os estranhos poderes de expandindo a série Taylor no centro entre e : ${\ displaystyle yx}$${\ displaystyle x}$${\ displaystyle y}$

${\ displaystyle x = mh, y = m + h}$, isso é ${\ 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' '' (m) \ cdot {\ frac {h ^ {3}} {3!}} + \ dots}$

${\ displaystyle f (mh) = f (m) -f '(m) \ cdot h + f' '(m) \ cdot {\ frac {h ^ {2}} {2!}} - f' '' (m) \ cdot {\ frac {h ^ {3}} {3!}} + \ pontos}$

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

Ordem superior

A série de Taylor ou qualquer outra representação com série de funções pode, em princípio, ser usada para aproximar diferenças divididas. As séries de Taylor são somas infinitas de funções de potência . O mapeamento de uma função para uma diferença dividida é um funcional linear . Também podemos aplicar este funcional aos summands da função. ${\ displaystyle f}$${\ displaystyle f [x_ {0}, \ dots, x_ {n}]}$

Notação de potência expressa com uma função comum: ${\ displaystyle p_ {n} (x) = x ^ {n}.}$

A série regular de Taylor é uma soma ponderada de funções de potência: ${\ 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}$

Série de Taylor para diferenças divididas: ${\ 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}$

Sabemos que os primeiros termos desaparecem, porque temos uma ordem de diferença maior do que a ordem polinomial, e no termo seguinte a diferença dividida é uma: ${\ displaystyle n}$

${\ displaystyle {\ begin {array} {llcl} \ forall j <n & p_ {j} [x_ {0}, \ dots, x_ {n}] & = & 0 \\ & p_ {n} [x_ {0}, \ pontos, x_ {n}] & = & 1 \\ & p_ {n + 1} [x_ {0}, \ pontos, x_ {n}] & = & x_ {0} + \ pontos + 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}}}$

Segue-se que a série de Taylor para a diferença dividida começa essencialmente com a qual também é uma aproximação simples da diferença dividida, de acordo com o teorema do valor médio para diferenças divididas . ${\ displaystyle {\ frac {f ^ {(n)} (0)} {n!}}}$

Se tivéssemos que calcular as diferenças divididas para as funções de potência da maneira usual, encontraríamos os mesmos problemas numéricos que tivemos ao calcular a diferença dividida de . O bom é que existe uma maneira mais simples. Detém ${\ 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} + \ pontos).}$

Consequentemente, podemos calcular as diferenças divididas de por uma divisão de séries de potências formais . Veja como isso se reduz ao cálculo sucessivo de potências quando calculamos para vários . ${\ displaystyle p_ {n}}$${\ displaystyle p_ {n} [h]}$${\ displaystyle n}$

Se você precisar calcular todo um esquema de diferenças divididas em relação a uma série de Taylor, consulte a seção sobre diferenças divididas de séries de potências .

Polinômios e séries de potências

As diferenças divididas de polinômios são particularmente interessantes, porque podem se beneficiar da regra de Leibniz. A matriz com ${\ 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}}}$

contém o esquema de diferenças divididas para a função de identidade em relação aos nós , portanto, contém as diferenças divididas para a função de potência com expoente . Consequentemente, você pode obter as diferenças divididas para uma função polinomial em relação ao polinômio aplicando (mais precisamente: sua função polinomial de matriz correspondente ) à matriz . ${\ 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}}}$

Isso é conhecido como fórmula de Opitz .

Agora considere aumentar o grau de para infinito, ou seja, transforme o polinômio de Taylor em uma série de Taylor . Let Ser uma função que corresponde a uma série de potências . Você pode calcular um esquema de diferença dividido calculando a série de matrizes de acordo aplicada . Se os nós são todos iguais, então é um bloco de Jordan e a computação se resume a generalizar uma função escalar para uma função de matriz usando a decomposição de Jordan . ${\ displaystyle p}$${\ displaystyle f}$${\ displaystyle J}$${\ displaystyle x_ {0}, \ dots, x_ {n}}$${\ displaystyle J}$

Diferenças para a frente

Quando os pontos de dados são distribuídos equidistantemente, obtemos o caso especial denominado diferenças progressivas . Eles são mais fáceis de calcular do que as diferenças divididas mais gerais.

Note que a "porção dividida" de diferença para a frente dividida ainda deve ser calculado, para recuperar a diferença para a frente dividida a partir da diferença para a frente .

Definição

Dados n pontos de dados

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

com

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

as diferenças divididas podem ser calculadas por meio de diferenças futuras definidas como

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

A relação entre diferenças divididas e diferenças futuras é

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

Exemplo

${\ 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} &&& \\\ fim {matriz}}}$

Veja também

• Quociente de diferença
• Algoritmo de neville
• Interpolação polinomial
• Teorema do valor médio para diferenças divididas
• Nörlund – Integral de arroz
• Triângulo de pascal

Referências

• Louis Melville Milne-Thomson (2000) [1933]. O cálculo das diferenças finitas . American Mathematical Soc. Capítulo 1: Diferenças divididas. ISBN 978-0-8218-2107-7.
• Myron B. Allen; Eli L. Isaacson (1998). Análise Numérica para Ciências Aplicadas . John Wiley & Sons. Apêndice A. ISBN 978-1-118-03027-1.
• Ron Goldman (2002). Algoritmos de pirâmide: uma abordagem de programação dinâmica para curvas e superfícies para modelagem geométrica . Morgan Kaufmann. Capítulo 4: Interpolação de Newton e triângulos de diferença. ISBN 978-0-08-051547-2.

links externos

• Uma implementação em Haskell .