Rozdělené rozdíly - Divided differences

V matematice , dělená rozdíly je algoritmus , historicky používá pro výpočet tabulky logaritmů a goniometrických funkcí . Charles Babbage ‚s rozdílem motoru , časný mechanický kalkulátor , byl navržen tak, aby použít tento algoritmus ve svém provozu.

Rozdělené rozdíly jsou rekurzivní dělící proces. Metodu lze použít k výpočtu koeficientů v interpolačním polynomu v Newtonově formě .

Definice

Dáno k  + 1 datových bodů

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

V přední dělená Rozdíly jsou definovány takto:

${\ 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 \ v \ {1, \ ldots, k \}.}$

V dozadu dělená Rozdíly jsou definovány takto:

${\ 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 \ v \ {1, \ ldots, k \}.}$

Zápis

Pokud jsou datové body uvedeny jako funkce ƒ ,

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

člověk někdy píše

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

Používá se několik zápisů děleného rozdílu funkce ƒ na uzlech 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}$

atd.

Příklad

Rozdělené rozdíly pro a prvních několik hodnot : ${\ displaystyle \ nu = 0}$${\ displaystyle j}$

${\ displaystyle {\ begin {aligned} {\ 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 {zarovnáno }}}$

Aby byl rekurzivní proces jasnější, lze rozdělené rozdíly vložit do tabulky:

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

Vlastnosti

• Linearita

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

• Leibnizova vláda

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

• Rozdělené rozdíly jsou symetrické: Pokud jde o permutaci, pak${\ Displaystyle \ sigma: \ {0, \ dots, n \} \ to \ {0, \ dots, n \}}$

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

• Z věty o střední hodnotě pro dělené rozdíly to vyplývá

${\ Displaystyle f [x_ {0}, \ dots, x_ {n}] = {\ frac {f^{(n)} (\ xi)} {n!}}}$kde je v otevřeném intervalu určeno nejmenším a největším z 's.${\ displaystyle \ xi}$${\ displaystyle x_ {k}}$

Maticová forma

Rozdělené diferenční schéma lze vložit do horní trojúhelníkové matice . Nech . ${\ Displaystyle T_ {f} (x_ {0}, \ dots, x_ {n}) = {\ begin {pmatrix} f [x_ {0}] & f [x_ {0}, x_ {1}] a 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}}}$

Pak to drží

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

Vyplývá to z Leibnizova pravidla. To znamená, že násobení takových matic je komutativní . Shrnuto, matice rozdělených rozdílových schémat s ohledem na stejnou sadu uzlů tvoří komutativní prstenec .

• Protože je to trojúhelníková matice, její vlastní čísla jsou zjevně .${\ displaystyle T_ {f} x}$${\ Displaystyle f (x_ {0}), \ dots, f (x_ {n})}$
• Nechť je funkce podobná deltě Kroneckera${\ displaystyle \ delta _ {\ xi}}$

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

Je tedy zřejmé , že jde o vlastní funkci bodového násobení funkcí. To je jakýmsi „ eigenmatrix “ z : . Nicméně, všechny sloupce jsou násobky každého jiný, matice rank ze je 1. Takže si můžete sestavit matici všech vektorů z tý sloupec každého . Označte matici vlastních vektorů pomocí . Příklad ${\ 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 {pmatrix}}}$

Diagonalizace of lze zapsat jako ${\ displaystyle T_ {f} x}$

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

Alternativní definice

Rozšířená forma

${\ displaystyle {\ 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 {zarovnáno}}}$

Pomocí polynomické funkce s tímto lze zapsat jako ${\ 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 })}}.}$

Alternativně můžeme povolit počítání zpět od začátku sekvence definováním kdykoli nebo . Tato definice umožňuje být interpretována jako , interpretována jako , interpretována jako atd. Rozšířená forma děleného rozdílu se tak stává ${\ 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 \ limity _ {k = j+1}^{j+n} (x_ {j} -x_ {k})}}}$

Ještě další charakterizace využívá limity:

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

Částečné zlomky

Částečné zlomky můžete reprezentovat pomocí rozšířené formy dělených rozdílů. (Tento nezjednodušuje výpočty, ale je zajímavé, sám o sobě.) Je-li a jsou polynomiální funkce , kde a je uveden v podmínkách lineárních faktorů tím , pak vyplývá z částečného rozkladu frakce této ${\ displaystyle p}$${\ displaystyle q}$${\ Displaystyle \ mathrm {deg} \ p <\ mathrm {deg} \ q}$${\ displaystyle q}$${\ Displaystyle q (\ xi) = (\ xi -x_ {1}) \ cdot \ tečky \ cdot (\ xi -x_ {n})}$

${\ Displaystyle {\ frac {p (\ xi)} {q (\ xi)}} = \ left (t \ to {\ frac {p (t)} {\ xi -t}} \ right) [x_ { 1}, \ tečky, x_ {n}].}$

Pokud jsou přijaty limity dělených rozdílů, pak toto spojení také platí, pokud se některé shodují. ${\ displaystyle x_ {j}}$

Pokud je polynom funkce s libovolným stupněm, a to se rozloží pomocí polynomu dělení a tím , potom ${\ 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}, \ tečky, x_ {n}].}$

Peano forma

Rozdělené rozdíly lze vyjádřit jako

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

kde je B -spline stupně pro datové body a je -tá derivace funkce . ${\ displaystyle B_ {n-1}}$${\ displaystyle n-1}$${\ displaystyle x_ {0}, \ tečky, x_ {n}}$${\ displaystyle f^{(n)}}$${\ displaystyle n}$${\ displaystyle f}$

Toto se nazývá Peano forma rozdělených rozdílů a nazývá se Peano jádro pro rozdělené rozdíly, oba pojmenované po Giuseppe Peano . ${\ displaystyle B_ {n-1}}$

Taylorova forma

První objednávka

Pokud jsou uzly kumulovány, pak je numerický výpočet dělených rozdílů nepřesný, protože rozdělíte téměř dvě nuly, z nichž každá má vysokou relativní chybu v důsledku rozdílů podobných hodnot . Nicméně víme, že rozdíl kvocienty aproximovat derivát a naopak:

${\ displaystyle {\ frac {f (y) -f (x)} {yx}} \ zhruba f '(x)}$ pro ${\ displaystyle x \ zhruba y}$

Tuto aproximaci lze převést na identitu, kdykoli platí Taylorova věta .

${\ Displaystyle f (y) = f (x)+f '(x) \ cdot (yx)+f' '(x) \ cdot {\ frac {(yx)^{2}} {2!}}+ f '' '(x) \ cdot {\ frac {(yx)^{3}} {3!}}+\ tečky}$

${\ Displaystyle \ Rightarrow {\ frac {f (y) -f (x)} {yx}} = f '(x)+f' '(x) \ cdot {\ frac {yx} {2!}}+ f '' '(x) \ cdot {\ frac {(yx)^{2}} {3!}}+\ tečky}$

Zvláštní síly můžete eliminovat rozšířením řady Taylor uprostřed mezi a : ${\ displaystyle yx}$${\ displaystyle x}$${\ displaystyle y}$

${\ Displaystyle x = mh, y = m+h}$, to je ${\ 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!}}+\ tečky}$

${\ Displaystyle f (mh) = f (m) -f '(m) \ cdot h+f' '(m) \ cdot {\ frac {h^{2}} {2!}}-f' ' (m) \ cdot {\ frac {h^{3}} {3!}}+\ tečky}$

${\ 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!}}+\ tečky}$

Vyšší řád

K aproximaci dělených rozdílů lze v zásadě použít Taylorovu řadu nebo jakoukoli jinou reprezentaci s funkčními řadami . Taylorovy řady jsou nekonečné sumy mocenských funkcí . Mapování z funkce na dělený rozdíl je lineární funkce . Tuto funkci můžeme také použít na součty funkcí. ${\ displaystyle f}$${\ Displaystyle f [x_ {0}, \ tečky, x_ {n}]}$

Zápis expresní síly s běžnou funkcí: ${\ Displaystyle p_ {n} (x) = x^{n}.}$

Pravidelná řada Taylor je váženým součtem výkonových funkcí: ${\ 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}$

Taylorova řada pro rozdělené rozdíly: ${\ Displaystyle f [x_ {0}, \ tečky, x_ {n}] = f (0) \ cdot p_ {0} [x_ {0}, \ tečky, x_ {n}]+f '(0) \ cdot p_ {1} [x_ {0}, \ tečky, x_ {n}]+{\ frac {f '' (0)} {2!}} \ cdot p_ {2} [x_ {0}, \ tečky , x_ {n}]+{\ frac {f '' '(0)} {3!}} \ cdot p_ {3} [x_ {0}, \ dots, x_ {n}]+\ dots}$

Víme, že první členy zmizí, protože máme vyšší rozdílové pořadí než polynomické, a v následujícím výrazu je dělený rozdíl jeden: ${\ displaystyle n}$

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

Z toho vyplývá, že Taylorova řada pro dělený rozdíl v podstatě začíná, což je také jednoduchá aproximace děleného rozdílu podle věty o střední hodnotě dělených rozdílů . ${\ displaystyle {\ frac {f^{(n)} (0)} {n!}}}$

Pokud bychom museli vypočítat dělené rozdíly pro výkonové funkce obvyklým způsobem, narazili bychom na stejné numerické problémy, jaké jsme měli při výpočtu děleného rozdílu . Je hezké, že existuje jednodušší způsob. Drží to ${\ displaystyle f}$

${\ Displaystyle t^{n} = (1-x_ {0} \ cdot t) \ dots \ cdot (1-x_ {n} \ cdot t) \ cdot (p_ {0} [x_ {0}, \ tečky , x_ {n}]+p_ {1} [x_ {0}, \ tečky, x_ {n}] \ cdot t+p_ {2} [x_ {0}, \ tečky, x_ {n}] \ cdot t ^{2}+\ tečky).}$

V důsledku toho můžeme vypočítat rozdělené rozdíly mezi tím, o rozdělení o formální mocninné řady . Podívejte se, jak se to snižuje na postupný výpočet sil, když počítáme pro několik . ${\ displaystyle p_ {n}}$${\ displaystyle p_ {n} [h]}$${\ displaystyle n}$

Pokud potřebujete vypočítat celé schéma děleného rozdílu s ohledem na Taylorovu řadu, přečtěte si část o rozdělených rozdílech výkonových řad .

Polynomy a mocninové řady

Zvláště zajímavé jsou dělené rozdíly polynomů, protože mohou těžit z Leibnizova pravidla. Matice s ${\ 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}}}$

obsahuje schéma děleného rozdílu pro funkci identity vzhledem k uzlům , obsahuje tedy rozdělené rozdíly pro mocninu s exponentem . V důsledku toho můžete získat dělené rozdíly pro polynomiální funkci vzhledem k polynomu aplikací (přesněji: její odpovídající maticové polynomické funkce ) na matici . ${\ displaystyle x_ {0}, \ tečky, 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 +\ tečky +a_ {n} \ cdot \ xi ^{n}}$

${\ Displaystyle \ varphi _ {\ mathrm {M}} (p) (J) = a_ {0}+a_ {1} \ cdot J+\ tečky+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}}}$

Toto je známé jako Opitzův vzorec .

Nyní zvažte zvýšení stupně na nekonečno, tj. Přeměňte Taylorův polynom na Taylorovu řadu . Nechť je funkce, která odpovídá výkonové řadě . Schéma děleného rozdílu můžete vypočítat výpočtem podle příslušné maticové řady . Pokud jsou všechny uzly stejné, pak je Jordanův blok a výpočet se scvrkává na zobecnění skalární funkce na maticovou funkci pomocí Jordanova rozkladu . ${\ displaystyle p}$${\ displaystyle f}$${\ displaystyle J}$${\ displaystyle x_ {0}, \ tečky, x_ {n}}$${\ displaystyle J}$

Dopředu rozdíly

Když jsou datové body rozloženy ve stejné vzdálenosti, dostaneme speciální případ, který se nazývá forwardové rozdíly . Vypočítávají se snáze než obecnější dělené rozdíly.

Všimněte si, že „rozdělená část“ z přední dělené rozdílu musí být stále počítán, obnovit vpřed rozdělený rozdíl od předního rozdílu .

Definice

Je dáno n datových bodů

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

s

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

dělené rozdíly lze vypočítat pomocí forwardových rozdílů definovaných jako

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

Vztah mezi rozdělenými rozdíly a dopřednými rozdíly je

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

Příklad

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

Viz také

• Diferenční kvocient
• Nevillův algoritmus
• Polynomiální interpolace
• Věta o střední hodnotě pro dělené rozdíly
• Nörlund – rýžový integrál
• Pascalův trojúhelník

Reference

• Louis Melville Milne-Thomson (2000) [1933]. Kalkul konečných rozdílů . American Mathematical Soc. Kapitola 1: Rozdělené rozdíly. ISBN 978-0-8218-2107-7.
• Myron B. Allen; Eli L. Isaacson (1998). Numerická analýza pro aplikovanou vědu . John Wiley & Sons. Příloha A. ISBN 978-1-118-03027-1.
• Ron Goldman (2002). Pyramidové algoritmy: Dynamický programovací přístup ke křivkám a povrchům pro geometrické modelování . Morgan Kaufmann. Kapitola 4: Newtonova interpolace a diferenční trojúhelníky. ISBN 978-0-08-051547-2.

externí odkazy

• Implementace v Haskell .