Numerisk differentiering

I numerisk analys uppskattar numeriska differentieringsalgoritmer derivatan av en matematisk funktion eller funktionssubrutin med hjälp av funktionens värden och kanske annan kunskap om funktionen.

Ändliga skillnader

Den enklaste metoden är att använda ändliga skillnadsapproximationer.

En enkel tvåpunktsuppskattning är att beräkna lutningen för en närliggande sekantlinje genom punkterna ( x , f ( x )) och ( x + h , f ( x + h )). Att välja ett litet tal h , h representerar en liten förändring i x , och det kan vara antingen positivt eller negativt. Lutningen på denna linje är

{\frac {f(x+h)-f(x)}{h}}.

Detta uttryck är Newtons skillnadskvot (även känd som en första ordningens uppdelad skillnad ) .

Lutningen på denna sekantlinje skiljer sig från lutningen på tangentlinjen med ett belopp som är ungefär proportionellt mot h . När h närmar sig noll närmar sig sekantlinjens lutning tangentlinjens lutning. Därför är den sanna derivatan av f vid x gränsen för värdet av skillnadskvoten när sekantlinjerna kommer närmare och närmare att vara en tangentlinje:

f'(x)=\lim _{h\to 0}{\frac {f(x+h)-f(x)}{h}}.

Eftersom att omedelbart ersätta h med 0 resulterar i ${\frac {0}{0}}$ obestämd form , kan det vara ointuitivt att beräkna derivatan direkt.

På motsvarande sätt skulle lutningen kunna uppskattas genom att använda positioner ( x − h ) och x .

En annan tvåpunktsformel är att beräkna lutningen för en närliggande sekantlinje genom punkterna ( x - h , f ( x − h )) och ( x + h , f ( x + h )). Lutningen på denna linje är

{\frac {f(x+h)-f(xh)}{2h}}.

Denna formel är känd som den symmetriska skillnadskvoten . I det här fallet upphävs första ordningens fel, så lutningen för dessa sekantlinjer skiljer sig från lutningen på tangentlinjen med ett belopp som är ungefär proportionellt mot $h^{2}$ . För små värden på h är detta därför en mer exakt approximation till tangentlinjen än den ensidiga uppskattningen. Men även om lutningen beräknas vid x , är värdet på funktionen vid x inte inblandat.

Uppskattningsfelet ges av

R={\frac {-f^{(3)}(c)}{6}}h^{2}

,

där $c$ är någon punkt mellan $xh$ och $x+h$ . Detta fel inkluderar inte avrundningsfelet på grund av att siffror representeras och beräkningar utförs med begränsad precision.

Den symmetriska skillnadskvoten används som metod för att approximera derivatan i ett antal räknare, inklusive TI-82 , TI-83 , TI-84 , TI-85 , som alla använder denna metod med h = 0,001.

Steglängd

Exempel som visar svårigheten att välja

h

på grund av både avrundningsfel och formelfel

En viktig faktor i praktiken när funktionen beräknas med flyttalsaritmetik med ändlig precision är valet av stegstorlek, h . Om den väljs för liten, kommer subtraktionen att ge ett stort avrundningsfel . Faktum är att alla formler med ändlig skillnad är dåligt konditionerade och kommer på grund av annullering att producera ett värde på noll om h är tillräckligt litet. Om den är för stor kommer beräkningen av sekantlinjens lutning att beräknas mer exakt, men uppskattningen av tangentens lutning genom att använda sekanten kan vara sämre.

För grundläggande centrala skillnader är det optimala steget kubroten av maskin epsilon . För den numeriska derivatformeln utvärderad vid x och x + h är ett val för h som är litet utan att ge ett stort avrundningsfel ${\sqrt {\varepsilon }}x$ (dock inte när x = 0) , där maskinens epsilon ε vanligtvis är i storleksordningen 2,2 × 10 ⁻¹⁶ för dubbel precision . En formel för h som balanserar avrundningsfelet mot sekantfelet för optimal noggrannhet

h=2{\sqrt {\varepsilon \left|{\frac {f(x)}{f''(x)}}\right|}}

(men inte när $f''(x)=0$ ), och för att använda det krävs kunskap om funktionen.

För datorberäkningar förvärras problemen eftersom, även om x nödvändigtvis har ett representativt flyttal med viss precision (32 eller 64-bitar, etc. ), kommer x + h nästan säkert inte att vara exakt representerade i den precisionen. Detta innebär att x + h kommer att ändras (genom avrundning eller trunkering) till ett närliggande maskinrepresenterbart tal, med konsekvensen att ( x + h ) − x inte blir lika med h ; de två funktionsutvärderingarna kommer inte att vara exakt h ifrån varandra. I detta avseende, eftersom de flesta decimalfraktioner är återkommande sekvenser i binär (precis som 1/3 är i decimal) kommer ett till synes runt steg som h = 0,1 inte att vara ett runt tal i binärt; det är 0,000110011001100... ₂ Ett möjligt tillvägagångssätt är följande:

h := sqrt(eps) * x; xph := x + h; dx := xph - x; lutning := (F(xph) - F(x)) /dx;

Men med datorer kan kompilatoroptimering misslyckas med att ta hand om detaljerna i faktisk datoraritmetik och istället tillämpa matematikens axiom för att härleda att dx och h är samma. Med C och liknande språk kommer ett direktiv att xph är en volatil variabel att förhindra detta.

Andra metoder

Metoder av högre ordning

Det finns metoder av högre ordning för att approximera derivatan, liksom metoder för högre derivat.

Nedan ges fempunktsmetoden för den första derivatan ( fempunktsstencil i en dimension):

f'(x)={\frac {-f(x+2h)+8f(x+h)-8f(xh)+f(x-2h)}{12h}}+{\frac {h^{4}}{30}}f^{(5)}(c),

där $c\in [x-2h,x+2h]$ .

För andra stencilkonfigurationer och derivatorder är Finite Difference Coefficients Calculator ett verktyg som kan användas för att generera derivatapproximationsmetoder för vilken schablon som helst med valfri derivatordning (förutsatt att en lösning finns).

Högre derivat

Med hjälp av Newtons skillnadskvot,

f'(x)=\lim _{h\to 0}{\frac {f(x+h)- f(x)}{h}}

följande kan visas (för n >0):

f^{(n)}(x)= \lim _{h\to 0}{\frac {1}{h^{n}}}\sum _{k=0}^{n}(-1)^{k+n}{\binom {n }{k}}f(x+kh)

Komplex-variabla metoder

De klassiska ändliga skillnadsapproximationerna för numerisk differentiering är dåligt betingade. Men om $f$ är en holomorf funktion , realvärderad på den reella linjen, som kan utvärderas vid punkter i det komplexa planet nära $x$ , så finns det stabila metoder. Till exempel kan den första derivatan beräknas med den komplexa derivatformeln:

f^{\prime }(x)={\frac {\Im (f(x+\mathrm {i} h))}{h}}+O(h^{2}),\quad \mathrm {i^{2}} :=-1.

Den rekommenderade stegstorleken för att erhålla korrekta derivator för en rad villkor är $h=10^{-200}$ . Denna formel kan erhållas genom expansion av Taylor-serien :

f(x+\mathrm {i} h)=f(x)+\mathrm {i} hf^{\prime }(x)-h^{2}f''(x)/2!-\ mathrm {i} h^{3}f^{(3)}(x)/3!+\cdots .

Den komplexa derivatformeln är endast giltig för beräkning av första ordningens derivator. En generalisering av ovanstående för att beräkna derivator av vilken ordning som helst använder multikomplexa tal , vilket resulterar i multikomplexa derivator.

f^{(n)}(x )\approx {\frac {{\mathcal {C}}_{n^{2}-1}^{(n)}(f(x+\mathrm {i} ^{(1)}h+\ldots +\ mathrm {i} ^{(n)}h))}{h^{n}}}

där $\mathrm {i} ^{(k)}$ anger de multikomplexa imaginära enheterna; $\mathrm {i} ^{(1)}\equiv \mathrm {i}$ . Operatorn ${\mathcal {C}}_{k}^{(n)}$ extraherar ${\displaystyle k}:$ e komponenten av ett multikomplext tal på nivå $n$ , t.ex. ${\mathcal {C}}_{0}^{(n)}$ extraherar den reella komponenten och ${\mathcal {C} }_{n^{2}-1}^{(n)}$ extraherar den sista, "mest imaginära" komponenten. Metoden kan tillämpas på blandade derivat, t.ex. för ett andra ordningens derivat

{\frac {\partial ^ {2}f(x,y)}{\partial x\,\partial y}}\approx {\frac {{\mathcal {C}}_{3}^{(2)}(f(x+\mathrm {i} ^{(1)}h,y+\mathrm {i} ^{(2)}h))}{h^{2}}}

En C++-implementering av multikomplex aritmetik är tillgänglig.

I allmänhet kan derivator av vilken ordning som helst beräknas med Cauchys integralformel :

f^{(n)}(a)={\frac {n!}{2\pi i}}\oint _{\gamma }{\frac {f(z)}{(za)^{n+1}}}\,\mathrm {d} z,

där integrationen görs numeriskt .

Att använda komplexa variabler för numerisk differentiering startades av Lyness och Moler 1967. Deras algoritm är tillämplig på högre ordningens derivator.

En metod baserad på numerisk inversion av en komplex Laplace-transform utvecklades av Abate och Dubner. En algoritm som kan användas utan att det krävs kunskap om metoden eller funktionens karaktär har utvecklats av Fornberg.

Differentialkvadratur

Differentialkvadratur är approximationen av derivator genom att använda viktade summor av funktionsvärden. Differentialkvadratur är av praktiskt intresse eftersom den tillåter en att beräkna derivator från brusiga data. Namnet är i analogi med kvadratur , vilket betyder numerisk integration , där viktade summor används i metoder som Simpsons metod eller den trapetsformade regeln . Det finns olika metoder för att bestämma viktkoefficienterna, till exempel Savitzky-Golay-filtret . Differentialkvadratur används för att lösa partiella differentialekvationer . Det finns ytterligare metoder för att beräkna derivator från brusiga data.

Se även

Automatisk differentiering – Tekniker för att utvärdera derivatan av en funktion specificerad av ett datorprogram
Fempunkts stencil
Savitzky-Golay-filter – Algoritm för att jämna ut datapunkter
Numerisk integration – Familj av algoritmer för att hitta den definitiva integralen av en funktion
Numeriska vanliga differentialekvationer – Metoder som används för att hitta numeriska lösningar av vanliga differentialekvationer
Numerisk utjämning och differentiering – Algoritm för att jämna ut datapunkter
Lista över programvara för numerisk analys

externa länkar