Editing Numerical differentiation (section)

==Complex-variable methods==

The classical finite-difference approximations for numerical differentiation are ill-conditioned. However, if <math>f</math> is a [[holomorphic function]], real-valued on the real line, which can be evaluated at points in the complex plane near <math>x</math>, then there are [[Numerical stability|stable]] methods. For example,<ref name=SquireTrapp1/> the first derivative can be calculated by the complex-step derivative formula:<ref>{{cite journal | last1 = Martins | first1 = J. R. R. A. | first2 = P. | last2 = Sturdza | first3 = J. J. | last3 = Alonso | year = 2003 | citeseerx=10.1.1.141.8002 | title = The Complex-Step Derivative Approximation | journal = ACM Transactions on Mathematical Software | volume = 29 | issue = 3 | pages = 245–262 | doi=10.1145/838250.838251| s2cid = 7022422 }}</ref><ref>[https://sinews.siam.org/Details-Page/differentiation-without-a-difference Differentiation With(out) a Difference] by [[Nicholas Higham]] </ref><ref>[https://blogs.mathworks.com/cleve/2013/10/14/complex-step-differentiation/ article] from [[MathWorks]] blog, posted by [[Cleve Moler]]</ref>
<math display="block">f'(x) = \frac{\Im(f(x + \mathrm{i}h))}{h} + O(h^2), \quad \mathrm{i^2}:=-1.</math>

The recommended step size to obtain accurate derivatives for a range of conditions is <math>h = 10^{-200}</math>.<ref name="edo2021"/>
This formula can be obtained by [[Taylor series]] expansion:
<math display="block">f(x+\mathrm{i}h) = f(x) + \mathrm{i}h f'(x) - \tfrac{1}{2!} h^2 f''(x) - \tfrac{\mathrm{i}}{3!} h^3 f^{(3)}(x) + \cdots.</math>

The complex-step derivative formula is only valid for calculating first-order derivatives. A generalization of the above for calculating derivatives of any order employs [[multicomplex numbers]], resulting in multicomplex derivatives.<ref>{{Cite web |url=http://russell.ae.utexas.edu/FinalPublications/ConferencePapers/2010Feb_SanDiego_AAS-10-218_mulicomplex.pdf |title=Archived copy |access-date=2012-11-24 |archive-url=https://web.archive.org/web/20140109145840/http://russell.ae.utexas.edu/FinalPublications/ConferencePapers/2010Feb_SanDiego_AAS-10-218_mulicomplex.pdf |archive-date=2014-01-09 |url-status=dead }}</ref><ref>{{cite journal | last1 = Lantoine | first1 = G. | last2 = Russell | first2 = R. P. | last3 = Dargent | first3 = Th. | title = Using multicomplex variables for automatic computation of high-order derivatives | journal = ACM Trans. Math. Softw. | volume = 38 | year = 2012 | issue = 3 | pages = 1–21 | doi = 10.1145/2168773.2168774 | s2cid = 16253562 }}</ref><ref>{{cite web | last1 = Verheyleweghen | first1 = A. | title = Computation of higher-order derivatives using the multi-complex step method | year = 2014 | url = http://folk.ntnu.no/preisig/HAP_Specials/AdvancedSimulation_files/2014/AdvSim-2014__Verheule_Adrian_Complex_differenetiation.pdf}}</ref>
<math display="block">f^{(n)}(x) \approx \frac{\mathcal{C}^{(n)}_{n^2-1}(f(x + \mathrm{i}^{(1)} h + \cdots + \mathrm{i}^{(n)} h))}{h^n}</math>
where the <math>\mathrm{i}^{(k)}</math> denote the multicomplex imaginary units; <math>\mathrm{i}^{(1)} \equiv \mathrm{i}</math>. The <math>\mathcal{C}^{(n)}_k</math> operator extracts the <math>k</math>th component of a multicomplex number of level <math>n</math>, e.g., <math>\mathcal{C}^{(n)}_0</math> extracts the real component and <math>\mathcal{C}^{(n)}_{n^2-1}</math> extracts the last, “most imaginary” component. The method can be applied to mixed derivatives, e.g. for a second-order derivative
<math display="block">\frac{\partial^2 f(x, y)}{\partial x \,\partial y} \approx \frac{\mathcal{C}^{(2)}_3(f(x + \mathrm{i}^{(1)} h, y + \mathrm{i}^{(2)} h))}{h^2}</math>

A C++ implementation of multicomplex arithmetics is available.<ref>{{cite web | last1 = Bell | first1 =  I. H.| title = mcx (multicomplex algebra library) | website = [[GitHub]]| year = 2019 | url = https://github.com/ianhbell/mcx}}</ref>

In general, derivatives of any order can be calculated using [[Cauchy's integral formula]]:<ref>Ablowitz, M. J., Fokas, A. S.,(2003). Complex variables: introduction and applications. [[Cambridge University Press]]. Check theorem 2.6.2</ref>
<math display="block">f^{(n)}(a) = \frac{n!}{2\pi i} \oint_\gamma \frac{f(z)}{(z - a)^{n+1}} \,\mathrm{d}z,</math>
where the integration is done [[Numerical integration|numerically]].

Using complex variables for numerical differentiation was started by Lyness and Moler in 1967.<ref name=LynessMoler1>{{cite journal | first1 = J. N. | last1 = Lyness | first2 = C. B. | last2 = Moler | title = Numerical differentiation of analytic functions | journal = SIAM J. Numer. Anal. | volume = 4 | year = 1967 | issue = 2 | pages = 202–210 | doi=10.1137/0704019| bibcode = 1967SJNA....4..202L }}</ref> Their algorithm is applicable to higher-order derivatives.

A method based on numerical inversion of a complex [[Laplace transform]] was developed by Abate and Dubner.<ref>{{cite journal | title = A New Method for Generating Power Series Expansions of Functions | first1 = J | last1 = Abate | first2 = H | last2 = Dubner | journal = SIAM J. Numer. Anal. | volume =5 | issue = 1 | pages = 102–112 |date=March 1968 | doi = 10.1137/0705008| bibcode = 1968SJNA....5..102A }}</ref> An algorithm that can be used without requiring knowledge about the method or the character of the function was developed by Fornberg.<ref name=Fornberg1/>