Tento článek má několik problémů. Prosím pomozte
vylepši to nebo diskutovat o těchto otázkách na internetu
diskusní stránka .
(Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)
v matematika , rozdělené rozdíly je algoritmus , historicky používané pro výpočet tabulek logaritmů a trigonometrických funkcí.[Citace je zapotřebí ] Charles Babbage je rozdíl motoru , brzy mechanická kalkulačka , byl navržen pro použití tohoto algoritmu při jeho provozu.[1]
Rozdělené rozdíly jsou a rekurzivní divize proces. Tuto metodu lze použít k výpočtu koeficientů v interpolační polynom v Newtonova forma .
Definice Dáno k + 1 datové body
( X 0 , y 0 ) , … , ( X k , y k ) { displaystyle (x_ {0}, y_ {0}), ldots, (x_ {k}, y_ {k})} The dopředu dělené rozdíly jsou definovány jako:
[ y ν ] := y ν , ν ∈ { 0 , … , k } { displaystyle [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 }.} The zpětně dělené rozdíly jsou definovány jako:
[ y ν ] := y ν , ν ∈ { 0 , … , k } { displaystyle [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 }.} Zápis Pokud jsou datové body uvedeny jako funkce ƒ ,
( X 0 , F ( X 0 ) ) , … , ( X k , F ( X k ) ) { displaystyle (x_ {0}, f (x_ {0})), ldots, (x_ {k}, f (x_ {k}))} jeden někdy píše
F [ X ν ] := F ( X ν ) , ν ∈ { 0 , … , k } { displaystyle 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 }.} Několik zápisů pro dělený rozdíl funkce ƒ na uzlech X 0 , ..., X n Jsou používány:
[ X 0 , … , X n ] F , { displaystyle [x_ {0}, ldots, x_ {n}] f,} [ X 0 , … , X n ; F ] , { displaystyle [x_ {0}, ldots, x_ {n}; f],} D [ X 0 , … , X n ] F { displaystyle D [x_ {0}, ldots, x_ {n}] f} atd.
Příklad Rozdělené rozdíly pro ν = 0 { displaystyle nu = 0} a prvních několik hodnot j { displaystyle 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 {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ší, rozdělené rozdíly lze dát do tabulky:
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}}} Vlastnosti ( F + G ) [ X 0 , … , X n ] = F [ X 0 , … , X n ] + G [ X 0 , … , X n ] { displaystyle (f + g) [x_ {0}, tečky, x_ {n}] = f [x_ {0}, tečky, x_ {n}] + g [x_ {0}, tečky, x_ {n}]} ( λ ⋅ F ) [ X 0 , … , X n ] = λ ⋅ F [ X 0 , … , X n ] { displaystyle ( lambda cdot f) [x_ {0}, dots, x_ {n}] = lambda cdot f [x_ {0}, dots, x_ {n}]} ( F ⋅ G ) [ X 0 , … , X n ] = F [ X 0 ] ⋅ G [ X 0 , … , X n ] + F [ X 0 , X 1 ] ⋅ G [ X 1 , … , X n ] + ⋯ + F [ X 0 , … , X n ] ⋅ G [ X n ] = ∑ r = 0 n F [ X 0 , … , X r ] ⋅ G [ X r , … , 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} ]} Rozdělené rozdíly jsou symetrické: Pokud σ : { 0 , … , n } → { 0 , … , n } { displaystyle sigma: {0, tečky, n } až {0, tečky, n }} je tedy obměna F [ X 0 , … , X n ] = F [ X σ ( 0 ) , … , X σ ( n ) ] { displaystyle f [x_ {0}, dots, x_ {n}] = f [x _ { sigma (0)}, dots, x _ { sigma (n)}]} F [ X 0 , … , X n ] = F ( n ) ( ξ ) n ! { displaystyle f [x_ {0}, dots, x_ {n}] = { frac {f ^ {(n)} ( xi)} {n!}}} kde ξ { displaystyle xi} je v otevřeném intervalu určeném nejmenší a největší z X k { displaystyle x_ {k}} je.Maticová forma Rozdělené rozdílové schéma lze vložit do svršku trojúhelníková matice .Nechat T F ( X 0 , … , X n ) = ( F [ X 0 ] F [ X 0 , X 1 ] F [ X 0 , X 1 , X 2 ] … F [ X 0 , … , X n ] 0 F [ X 1 ] F [ X 1 , X 2 ] … F [ X 1 , … , X n ] ⋮ ⋮ ⋮ ⋱ ⋮ 0 0 0 … F [ X n ] ) { 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}] konec {pmatrix}}} .
Pak to drží
T F + G X = T F X + T G X { displaystyle T_ {f + g} x = T_ {f} x + T_ {g} x} T F ⋅ G X = T F X ⋅ T G X { displaystyle T_ {f cdot g} x = T_ {f} x cdot T_ {g} x} To vyplývá 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ří a komutativní prsten . Od té doby T F X { displaystyle T_ {f} x} je trojúhelníková matice, její vlastní čísla jsou samozřejmě F ( X 0 ) , … , F ( X n ) { displaystyle f (x_ {0}), tečky, f (x_ {n})} . Nechat δ ξ { displaystyle delta _ { xi}} být Kroneckerova delta - jako funkce, to je δ ξ ( t ) = { 1 : t = ξ , 0 : jiný . { displaystyle delta _ { xi} (t) = { begin {cases} 1 &: t = xi, 0 &: { mbox {else}}. end {cases}}} Očividně F ⋅ δ ξ = F ( ξ ) ⋅ δ ξ { displaystyle f cdot delta _ { xi} = f ( xi) cdot delta _ { xi}} , tím pádem δ ξ { displaystyle delta _ { xi}} je vlastní funkce násobení bodové funkce. To je T δ X i X { displaystyle T _ { delta _ {x_ {i}}} x} je nějakvlastní matice „z T F X { displaystyle T_ {f} x} : T F X ⋅ T δ X i X = F ( X i ) ⋅ T δ X i X { displaystyle T_ {f} x cdot T _ { delta _ {x_ {i}}} x = f (x_ {i}) cdot T _ { delta _ {x_ {i}}} x} . Všechny sloupce T δ X i X { displaystyle T _ { delta _ {x_ {i}}} x} jsou navzájem násobky, hodnost matice z T δ X i X { displaystyle T _ { delta _ {x_ {i}}} x} je 1. Takže můžete skládat matici všech vlastních vektorů z i { displaystyle i} -tý sloupec každého T δ X i X { displaystyle T _ { delta _ {x_ {i}}} x} . Označme matici vlastních vektorů pomocí U X { displaystyle Ux} . Příklad 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 & { 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 a 0 a 0 a 1 end {pmatrix}}} The diagonalizace z T F X { displaystyle T_ {f} x} lze psát jako U X ⋅ diag ( F ( X 0 ) , … , F ( X n ) ) = T F X ⋅ U X { displaystyle Ux cdot operatorname {diag} (f (x_ {0}), tečky, f (x_ {n})) = T_ {f} x cdot Ux} . Alternativní definice Rozšířená forma 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 , … , X n ] = ∑ j = 0 n F ( X j ) ∏ k ∈ { 0 , … , n } ∖ { j } ( X j − X k ) { 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}}}
S pomocí a polynomiální funkce q { displaystyle q} s q ( ξ ) = ( ξ − X 0 ) ⋯ ( ξ − X n ) { displaystyle q ( xi) = ( xi -x_ {0}) cdots ( xi -x_ {n})} toto lze zapsat jako
F [ X 0 , … , X n ] = ∑ j = 0 n F ( X j ) q ′ ( X j ) . { displaystyle f [x_ {0}, tečky, x_ {n}] = součet _ {j = 0} ^ {n} { frac {f (x_ {j})} {q '(x_ {j })}}.} Alternativně můžeme definováním povolit počítání zpět od začátku sekvence X k = X k + n + 1 = X k − ( n + 1 ) { displaystyle x_ {k} = x_ {k + n + 1} = x_ {k- (n + 1)}} kdykoli k < 0 { displaystyle k <0} nebo n < k { displaystyle n . Tato definice umožňuje X − 1 { displaystyle x _ {- 1}} má být vykládáno jako X n { displaystyle x_ {n}} , X − 2 { displaystyle x _ {- 2}} má být vykládáno jako X n − 1 { displaystyle x_ {n-1}} , X − n { displaystyle x _ {- n}} má být vykládáno jako X 0 { displaystyle x_ {0}} atd. Takto se stává rozšířená forma děleného rozdílu
F [ X 0 , … , X n ] = ∑ j = 0 n F ( X j ) ∏ k = j − n j − 1 ( X j − X k ) + ∑ j = 0 n F ( X j ) ∏ k = j + 1 j + n ( X j − X k ) { displaystyle f [x_ {0}, dots, x_ {n}] = sum _ {j = 0} ^ {n} { frac {f (x_ {j})} { prod limity _ { 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})}}}
Ještě další charakterizace využívá limity:
F [ X 0 , … , X n ] = ∑ j = 0 n lim X → X j [ F ( X j ) ( X − X j ) ∏ k = 0 n ( X − 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 limity _ {k = 0} ^ {n} (x-x_ {k})}} vpravo]}
Dílčí zlomky Můžete zastupovat dílčí zlomky pomocí rozšířené formy dělených rozdílů. (To nezjednodušuje výpočet, ale je to samo o sobě zajímavé.) Pokud str { displaystyle p} a q { displaystyle q} jsou polynomiální funkce , kde d E G str < d E G q { displaystyle mathrm {deg} p < mathrm {deg} q} a q { displaystyle q} je uveden v termínech lineární faktory podle q ( ξ ) = ( ξ − X 1 ) ⋅ ⋯ ⋅ ( ξ − X n ) { displaystyle q ( xi) = ( xi -x_ {1}) cdot tečky cdot ( xi -x_ {n})} , pak z parciálního zlomkového rozkladu vyplývá, že
str ( ξ ) q ( ξ ) = ( t → str ( t ) ξ − t ) [ X 1 , … , X n ] . { displaystyle { frac {p ( xi)} {q ( xi)}} = levý (t až { frac {p (t)} { xi -t}} pravý) [x_ { 1}, dots, x_ {n}].} Li limity z rozdělených rozdílů jsou přijaty, pak toto spojení také platí, pokud některé z X j { displaystyle x_ {j}} shodovat se.
Li F { displaystyle f} je polynomiální funkce s libovolným stupněm a je rozložena F ( X ) = str ( X ) + q ( X ) ⋅ d ( X ) { Displaystyle f (x) = p (x) + q (x) cdot d (x)} použitím polynomiální dělení z F { displaystyle f} podle q { displaystyle q} ,pak
str ( ξ ) q ( ξ ) = ( t → F ( t ) ξ − t ) [ X 1 , … , X n ] . { displaystyle { frac {p ( xi)} {q ( xi)}} = levý (t až { frac {f (t)} { xi -t}} pravý) [x_ { 1}, dots, x_ {n}].} Peano forma Rozdělené rozdíly lze vyjádřit jako
F [ X 0 , … , X n ] = 1 n ! ∫ X 0 X n F ( n ) ( t ) B n − 1 ( t ) d t { displaystyle f [x_ {0}, ldots, x_ {n}] = { frac {1} {n!}} int _ {x_ {0}} ^ {x_ {n}} f ^ {( n)} (t) B_ {n-1} (t) , dt} kde B n − 1 { displaystyle B_ {n-1}} je B-spline stupně n − 1 { displaystyle n-1} pro datové body X 0 , … , X n { displaystyle x_ {0}, dots, x_ {n}} a F ( n ) { displaystyle f ^ {(n)}} je n { displaystyle n} -th derivát funkce F { displaystyle f} .
Tomu se říká Peano forma z rozdělených rozdílů a B n − 1 { displaystyle B_ {n-1}} se nazývá Peano jádro pro rozdělené rozdíly, oba pojmenované po Giuseppe Peano .
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 vydělíte téměř dvě nuly, z nichž každá má vysokou relativní chyba kvůli rozdíly podobných hodnot . To však víme rozdílové kvocienty přibližný derivát a naopak:
F ( y ) − F ( X ) y − X ≈ F ′ ( X ) { displaystyle { frac {f (y) -f (x)} {y-x}} přibližně f '(x)} pro X ≈ y { displaystyle x přibližně y} Tuto aproximaci lze kdykoli změnit na identitu Taylorova věta platí.
F ( y ) = F ( X ) + F ′ ( X ) ⋅ ( y − X ) + F ″ ( X ) ⋅ ( y − X ) 2 2 ! + F ‴ ( X ) ⋅ ( y − X ) 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!}} + tečky} ⇒ F ( y ) − F ( X ) y − X = F ′ ( X ) + F ″ ( X ) ⋅ y − X 2 ! + F ‴ ( X ) ⋅ ( y − X ) 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!}} + tečky} Můžete eliminovat zvláštní síly y − X { displaystyle y-x} rozšířením Taylor série ve středu mezi X { displaystyle x} a y { displaystyle y} :
X = m − h , y = m + h { displaystyle x = m-h, y = m + h} , to je m = X + y 2 , h = y − X 2 { displaystyle m = { frac {x + y} {2}}, h = { frac {y-x} {2}}} F ( m + h ) = F ( m ) + F ′ ( m ) ⋅ h + F ″ ( m ) ⋅ h 2 2 ! + F ‴ ( m ) ⋅ h 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!}} + tečky} F ( m − h ) = F ( m ) − F ′ ( m ) ⋅ h + F ″ ( m ) ⋅ h 2 2 ! − F ‴ ( m ) ⋅ h 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!}} + tečky} F ( y ) − F ( X ) y − X = F ( m + h ) − F ( m − h ) 2 ⋅ h = F ′ ( m ) + F ‴ ( m ) ⋅ h 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!}} + tečky} Vyšší řád Taylorova řada nebo jakékoli jiné zastoupení s funkční řady lze v zásadě použít k aproximaci dělených rozdílů. Taylorovy řady jsou nekonečné součty výkonové funkce . Mapování z funkce F { displaystyle f} na dělený rozdíl F [ X 0 , … , X n ] { displaystyle f [x_ {0}, dots, x_ {n}]} je lineární funkční . Můžeme také použít tuto funkci na sčítání funkcí.
Expresní zápis výkonu s běžnou funkcí: str n ( X ) = X n . { displaystyle p_ {n} (x) = x ^ {n}.}
Pravidelná řada Taylor je váženým součtem výkonových funkcí: F = F ( 0 ) ⋅ str 0 + F ′ ( 0 ) ⋅ str 1 + F ″ ( 0 ) 2 ! ⋅ str 2 + F ‴ ( 0 ) 3 ! ⋅ str 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}
Taylorova řada pro dělené rozdíly: F [ X 0 , … , X n ] = F ( 0 ) ⋅ str 0 [ X 0 , … , X n ] + F ′ ( 0 ) ⋅ str 1 [ X 0 , … , X n ] + F ″ ( 0 ) 2 ! ⋅ str 2 [ X 0 , … , X n ] + F ‴ ( 0 ) 3 ! ⋅ str 3 [ X 0 , … , X n ] + … { 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}
Víme, že první n { displaystyle n} termíny zmizí, protože máme vyšší rozdílové pořadí než polynomické pořadí a v následujícím termínu je dělený rozdíl jeden:
∀ j < n str j [ X 0 , … , X n ] = 0 str n [ X 0 , … , X n ] = 1 str n + 1 [ X 0 , … , X n ] = X 0 + ⋯ + X n str n + m [ X 0 , … , X n ] = ∑ A ∈ { 0 , … , n } m s A 1 ≤ A 2 ≤ ⋯ ≤ A m ∏ j ∈ A X j . { displaystyle { begin {array} {llcl} forall j Z toho vyplývá, že Taylorova řada pro dělený rozdíl v podstatě začíná F ( n ) ( 0 ) n ! { displaystyle { frac {f ^ {(n)} (0)} {n!}}} což je také jednoduchá aproximace děleného rozdílu podle věta o střední hodnotě pro dělené rozdíly .
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 F { displaystyle f} . Pěkné je, že existuje jednodušší způsob
t n = ( 1 − X 0 ⋅ t ) ⋯ ⋅ ( 1 − X n ⋅ t ) ⋅ ( str 0 [ X 0 , … , X n ] + str 1 [ X 0 , … , X n ] ⋅ t + str 2 [ X 0 , … , X n ] ⋅ t 2 + … ) . { displaystyle t ^ {n} = (1-x_ {0} cdot t) tečky cdot (1-x_ {n} cdot t) cdot (p_ {0} [x_ {0}, tečky , x_ {n}] + p_ {1} [x_ {0}, dots, x_ {n}] cdot t + p_ {2} [x_ {0}, dots, x_ {n}] cdot t ^ {2} + tečky).} V důsledku toho můžeme vypočítat rozdělené rozdíly str n { displaystyle p_ {n}} podle a divize z formální mocenské řady . Podívejte se, jak se to při výpočtu redukuje na postupný výpočet mocnin str n [ h ] { displaystyle p_ {n} [h]} pro několik n { displaystyle n} .
Pokud potřebujete vypočítat celé rozdělené rozdílové schéma s ohledem na Taylorovu řadu, přečtěte si část o rozdělených rozdílech výkonová řada .
Polynomy a mocninné řady Dělené rozdíly polynomů jsou obzvláště zajímavé, protože mohou těžit z Leibnizova pravidla. Matice J { displaystyle J} s
J = ( X 0 1 0 0 ⋯ 0 0 X 1 1 0 ⋯ 0 0 0 X 2 1 0 ⋮ ⋮ ⋱ ⋱ 0 0 0 0 X n ) { 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 rozdělené rozdílové schéma pro funkce identity vzhledem k uzlům X 0 , … , X n { displaystyle x_ {0}, dots, x_ {n}} ,tím pádem J n { displaystyle J ^ {n}} obsahuje rozdělené rozdíly pro funkce napájení s exponent n { displaystyle n} Následně můžete získat rozdělené rozdíly pro a polynomiální funkce φ ( str ) { displaystyle varphi (p)} s respektem k polynomiální str { displaystyle p} aplikováním str { displaystyle p} (přesněji: odpovídající polynomiální funkce matice φ M ( str ) { displaystyle varphi _ { mathrm {M}} (p)} ) do matice J { displaystyle J} .
φ ( str ) ( ξ ) = A 0 + A 1 ⋅ ξ + ⋯ + A n ⋅ ξ n { displaystyle varphi (p) ( xi) = a_ {0} + a_ {1} cdot xi + tečky + a_ {n} cdot xi ^ {n}} φ M ( str ) ( J ) = A 0 + A 1 ⋅ J + ⋯ + A n ⋅ J n { displaystyle varphi _ { mathrm {M}} (p) (J) = a_ {0} + a_ {1} cdot J + dots + a_ {n} cdot J ^ {n}} = ( φ ( str ) [ X 0 ] φ ( str ) [ X 0 , X 1 ] φ ( str ) [ X 0 , X 1 , X 2 ] … φ ( str ) [ X 0 , … , X n ] 0 φ ( str ) [ X 1 ] φ ( str ) [ X 1 , X 2 ] … φ ( str ) [ X 1 , … , X n ] ⋮ ⋱ ⋱ ⋱ ⋮ 0 … 0 0 φ ( str ) [ X 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 .[2] [3]
Nyní zvažte zvýšení stupně str { displaystyle p} do nekonečna, tj. otočte Taylorův polynom na a Taylor série .Nechat F { displaystyle f} být funkcí, která odpovídá a výkonová řada Schéma rozdělených rozdílů můžete vypočítat výpočtem podle použité maticové řady J { displaystyle J} Pokud jsou uzly X 0 , … , X n { displaystyle x_ {0}, dots, x_ {n}} jsou si tedy všichni rovni J { displaystyle J} je Jordan blok a výpočet se scvrkává na zobecnění skalární funkce na a maticová funkce použitím Jordanův rozklad .
Forwardové rozdíly Když jsou datové body rovnoměrně rozloženy, dostaneme speciální případ zvaný vpřed rozdíly . Vypočítávají se snadněji než obecnější dělené rozdíly.
Všimněte si, že "rozdělená část" z dopředu dělený rozdíl musí být stále vypočítán, aby se obnovil dopředu dělený rozdíl z vpřed rozdíl .
Definice Dáno n datové body
( X 0 , y 0 ) , … , ( X n − 1 , y n − 1 ) { displaystyle (x_ {0}, y_ {0}), ldots, (x_ {n-1}, y_ {n-1})} s
X ν = X 0 + ν h , h > 0 , ν = 0 , … , n − 1 { displaystyle x _ { nu} = x_ {0} + nu h, h> 0, nu = 0, ldots, n-1} rozdělené rozdíly lze vypočítat pomocí vpřed rozdíly definováno jako
Δ ( 0 ) y i := y i { displaystyle Delta ^ {(0)} y_ {i}: = y_ {i}} Δ ( k ) y i := Δ ( k − 1 ) y i + 1 − Δ ( k − 1 ) y i , k ≥ 1. { 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[4]
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}).} Příklad 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 {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é Reference ^ Isaacson, Walter (2014). Inovátoři . Simon & Schuster. p. 20. ISBN 978-1-4767-0869-0 . ^ de Boor, Carle , Rozdělené rozdíly , Surv. Cca. Theory 1 (2005), 46–69, [1] ^ Opitz, G. Steigungsmatrizen , Z. Angew. Matematika. Mech. (1964), 44, T52 – T54 ^ Burden, Richard L .; Faires, J. Douglas (2011). Numerická analýza (9. vydání). p.129 . Louis Melville Milne-Thomson (2000) [1933]. Počet 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 rozdílové trojúhelníky. ISBN 978-0-08-051547-2 . externí odkazy