Home » Mathematics » Scientific Computing

Scientific Computing

Scientific Computing
Scientific Computing

The following section presupposes Set Theory and Nonstandard Analysis. Let \(\varepsilon \in [\tilde{\nu}, 1 – \tilde{\nu}]\).

Definition: Let according to the trapezoidal rule \({}^{T}{\uparrow}_{z\in A}{f(z){\downarrow}z:={+}_{z\in A}{\tilde{2}(f(z)+f({}^\curvearrowright\,z))({}^\curvearrowright\,z-z)}}.\)

Let according to the midpoint rule \({}^{M}{\uparrow}_{z\in A}{f(z){\downarrow}z:={+}_{z\in A}{f(\tilde{2}(z\,+{}^\curvearrowright z}))({}^\curvearrowright\,z-z)}.\triangle\)

Remark: In the first fundamental theorem, the derivative \({\downarrow}(F(z))/{\downarrow}z\) can be tightened to the arithmetic mean \(\tilde{2}(f(z) + f({}^\curvearrowright z))\) resp. \(f(\tilde{2}(z + {}^\curvearrowright z))\), and similarly, in the second fundamental theorem, \(F(\gamma(b)) – F(\gamma(a))\) can be tightened to \(\tilde{2}(F(\gamma(b)) + F({}^\curvearrowleft \gamma(b))) – \tilde{2}(F(\gamma(a)) + F({}^\curvearrowright \gamma(a)))\) resp. \(F(\tilde{2}(\gamma(b) + {}^\curvearrowleft \gamma(b))) – F(\tilde{2}(\gamma(a) + {}^\curvearrowright \gamma(a)))\). This yields approximately the original results when \(f\) and \(F\) are sufficiently \(\alpha\)-continuous at the boundary.

Definition: Let \(f_n^*(z) = f(\eta_nz)\) sisters of the TS \(f(z) \in \mathcal{O}(D)\) centred on 0 on the domain \(D \subseteq {}^{\omega}\mathbb{C}\) where \(m, n \in {}^{\omega}\mathbb{N}^{*}\) and \(\eta_n^m := i^{2^{\lceil m/n \rceil}}\). Then let \(\delta_n^*f = \check{f} – \check{f}_n^*\) the halved sister distances of \(f\). Let \(\mu_n^m := m!n!/(m + n)!\) and \(\widetilde{(-n)!} := 0\). For \(j, k \in {}^{\omega}\mathbb{N}, f \in \mathcal{C}_{\pi}^{j+2}\) and Fourier coefficients \(c_k := \tilde{\hat{\pi}}{\uparrow}_{-\pi}^{\pi}{f(t)\tilde{e}^{ikt}{{\downarrow}t}}\)1cf. Walter, Wolfgang: Analysis 2; 5., erw. Aufl.; 2002; Springer; Berlin, p. 358 ff., the series \({+}_{k=-\omega}^{\omega}{c_ke^{ikt}}\) is called Fourier series. On the level of TS, \(\mu\) and \(\eta\) form a \(\mu\)-\(\eta\)-calculus.\(\triangle\)

Remark: The latter allows representing integrals and derivatives easily and finitely closed2cf. Remmert, Reinhold: Funktionentheorie 1; 3., verb. Aufl.; 1992; Springer; Berlin, p. 165 f.. A conversion to other period lengths than \(\hat{\pi }\) is simply possible3see loc. cit., p. 364.

Example: \(\text{Re} \; c \in [\tilde{\nu}, 1 + \tilde{\nu}[, c \in {}^{\omega}\mathbb{C}\) and \(\varepsilon := \tilde{2}^j, j \in {}^{\omega}\mathbb{N}^{*}\) imply \(\zeta (n+c)=a_n{+}_{k=1}^{n}{\delta_n^* v_c(\varepsilon u^k)}\) for \(z \in \mathbb{B}_{1-\tilde{\nu}}(0) \subset D\)4cf. Remmert, Reinhold: Funktionentheorie 2; 1. unveränd. Nachdruck der 1. Aufl.; 1992; Springer; Berlin, p. 42 and \(v_c(z):={+}_{m=1}^{\omega }{\zeta (m+c){{z}^{m}}}=z{+}_{m=1}^{\omega }{{{{\widetilde{m}}}^{c}}\widetilde{z-m}}.\square\)

Example: A Richardson extrapolation determines the digamma function \(\psi\) and\[\zeta(\grave{n}) =\widetilde{\varepsilon^n\hat{n}}{+}_{k=1}^n{(\psi(\varepsilon u^k i^{2\tilde{n}}) – \psi(\varepsilon u^k))} + \mathcal{O}(\varepsilon^{\hat{n}})\] for \(n = 2\) and \(\varepsilon = \tilde{2}^{13}\) as \(\zeta(3) = 2^{24}{+}_{k=1}^2{(\psi(\varepsilon u^ki) – \psi(\varepsilon u^k))} + \mathcal{O}(10^{-16})\).

Representation theorem for integrals: The TS (see below) \(f(z) \in \mathcal{O}(D)\) centred on 0 for \(D \subseteq {}^{\omega}\mathbb{C}\) gives for \(\grave{m}, n \in {}^{\omega}\mathbb{N}^*\)\[{\uparrow}_0^z…{\uparrow}_0^{\zeta_2}{f(\zeta_1){\downarrow}\zeta_1\;…\;{\downarrow}\zeta_n} = \widetilde{n!} f(z\mu_n) z^n.\square\]Example: For the TS \(f(x), g(x) \in {}^{\omega}\mathbb{R}\), it holds that \({\uparrow}_0^x{f(v){\downarrow}v}{\uparrow}_0^x{\uparrow}_0^{y}{g(v){\downarrow}v{\downarrow}y} = f(x\mu_1)\check{g}(x\mu_2)x^3.\)

Representation theorem for derivatives: For \(\mathbb{B}_{\tilde{\nu}}(0) \subset D \subseteq {}^{\omega}\mathbb{C}, n\)-th unit roots, TS\[f(z):=f(0) + {+}_{m=1}^{\omega }{\widetilde{m!}\,{{f}^{(m)}}(0){z^m}},\]\(\varepsilon := \tilde{2}^j\tilde{r}, j \in {}^{\omega}\mathbb{Z}, n \in {}^{\omega}\mathbb{N}^{*}, u :=e^{\tilde{n} \hat{\pi}i}\) and \(f\)’s radius of convergence \(r \in {}^{\nu}{\mathbb{R}}_{>0}\) imply\[{{f}^{(n)}}(0)=2^{jn}\acute{n}!{+}_{k=1}^{n}{\delta_n^* f(\tilde{2}^j u^k)}.\square\]Universal multistep theorem: For \(n \in {}^{\nu}\mathbb{N}_{\le p}, k, m, p \in {}^{\nu}\mathbb{N}^{*}, {\downarrow}_{{}^\curvearrowright B} x \in\, ]0, 1[, x \in [a, b] \subseteq {}^{\omega}\mathbb{R}, y : [a, b] \rightarrow {}^{\omega}\mathbb{R}^q, f : [a, b]\times{}^{\omega}\mathbb{R}^{q \times n} \rightarrow {}^{\omega}\mathbb{R}^q, g_k({}^\curvearrowright x) := g_{\acute{k}}(x)\), and \(g_0(a) = f(({}^\curvearrowleft)a, y_0, … , y_{\acute{n}})\), the TS of the initial value problem \(y^\prime(x) = f(x, y(({}^\curvearrowright)^0 x), … , y(({}^\curvearrowright)^{\acute{n}} x))\) of order \(n\) implies\[y({}^\curvearrowright x) = y(x) + {\downarrow}_{{}^\curvearrowright}x{\pm}_{k=1}^{p}{\left (g_{p-k}(({}^\curvearrowright) x){+}_{m=k}^{p}{\widetilde{m!}\tbinom{\acute{m}}{\acute{k}}}\right )} + \mathcal{O}(({\downarrow}_{{}^\curvearrowright} x)^{\grave{p}}).\square\]Theorem for (anti-) derivatives of TS: For \(j \in {}^{\omega}\mathbb{Z}\), \(q = \tilde{\varepsilon}(z-a)\), \(a \in D\) and \(k, m \in \mathbb{N}_{<n}\), modular arithmetic5cf. Knuth, Donald Ervin: The Art of Computer Programming Volume 2; 3rd Ed.; 1997; Addison Wesley; Reading, p. 302 – 311 and \(n\)-th unit roots result in the corresponding DFT form:\[{\updownarrow}^jf_n(z) := \tilde{n}(q^k)^T(\delta_{km}\widetilde{\varepsilon q}^j\widetilde{(k-j)!}k!)({\tilde{u}}^{km})(f({\varepsilon u}^m+a))+\mathcal{O}(\varepsilon^n).\square\]Theorem for derivatives of Fourier series: For \(f \in \mathcal{C}_{\pi}^{j+2}\)6cf. Walter, loc. cit., \(j \in {}^{\omega}\mathbb{N}, k \in [-\acute{n}, n] \cap \mathbb{Z}, t \in [-\pi, \pi]\) and \(m \in \mathbb{N}_{<\hat{n}}\), the following DFT form is implied allowing integration of individual terms:\[{\downarrow}^jf_n(t):=(u^{\tilde{\pi}knt})^T(\delta_{(k+\acute{n})m} (ik)^j)(\tilde{u}^{km})(f(\tilde{n}\pi m – \pi))/{\hat{n}}+\mathcal{O}(\tilde{n}).\square\]Conclusion: Supporting points \(mr := \tilde{n}\pi m\) of the smooth \(f(mr)\) yield for \(k\) like \(m\) interpolating in \(\mathcal{O}(_en n)\):\[{\downarrow}^jf_n(t):=(u^{\tilde{r}kt})^T(\delta_{km}(ik)^j)(\tilde{u}^{km})(f(mr))/{\hat{n}}.\square\]Theorem (DFT fixed-point method): Every \(z \in {}^{\omega}\mathbb{C}\) of an arbitrary \(m\)-polynomial \(p(z) = 0\) with \(m \in [2, n] \cap \mathbb{N}\) for \(n := 2^r, r \in {}^{\nu}\mathbb{N}^*\) and coefficients from \({}^{\nu}\mathbb{C}\) can be (initiating) determined also in \(\mathcal{O}(_en n).\)

Proof and algorithm: Let \(U = (\tilde{u}^{jk})\) for \(j, k \in \mathbb{N}_{<n}, u :=e^{\tilde{n} \hat{\pi} i}, q := \hat{z}\) and \(s_k := p(\tilde{2}u^k)\). A simple transform achieves \(|q| < \tilde{2}\) for all zeros \(\zeta\) of \(p(z)\) and \(p(0) = 1\). It follows from \(p(z) = \tilde{n}(q^j)^TUs = \tilde{n}\mu^Ts = 0\) the simplified iteration \(\mu^* = U_{1}^{-T}\mu U((\delta_{jk}\tilde{u}^j)U^{-1}\mu-(U_{\acute{n}}^{-T}\mu+\beta s^T\mu, \beta s^T\mu, …, \beta s^T\mu)^T)\). Here let \(\delta_{jk}\) the Kronecker delta, starting point \(q := \tilde{2}\) and \(\beta \in {}^{\nu}\mathbb{C}^*\) such that each time \(||\mu^*-\mu||\) is roughly halved and \(\mu^Ts = 0\) holds. Finish by polynomial division where \(m > 2.\square\)

Conclusion: DFT-zero methods iterate zeros \(a \in {}^{\omega}\mathbb{C}\) for every function \(f(z) \in {}^{\omega}\mathbb{C}\) that can be developed into a TS at defaults \(z_0 \in {}^{\omega}\mathbb{C}\) with each time the same convergence as in methods similar to Simpson’s, if \({\updownarrow}^0f_n(z)\) is differentiated (several times) for sufficiently precise \(|z_{\grave{m}} – z_m|\) and \(m \in {}^{\omega}\mathbb{N}.\square\)

Remark: The identity instead of \(\delta_n^*\) provides arbitrarily precise approximations for the \(f^{(n)}\). The last theorems are equally valid for multidimensional TS and Laurent series. The error is \(\mathcal{O}(\varepsilon^n)\) instead of \(\mathcal{O}(\varepsilon)\) for analogously defined \(m\)-dimensional DFT forms of the TS with \(\binom{m+n}{n}\) derivatives where the effort is comparable. A good choice for the crown points \(\varepsilon u^m + a\) around the crown centre \(a\) is \(\varepsilon = \tilde{2}\) and \(n = 64\).

Conclusion for differential equations: Let \(d(z) \in {}^{\omega}\mathbb{C}^{n+2}\) vector of DFT forms for \(n \in {}^{\omega}\mathbb{N}\). If the system \(y^{(\grave{n})} = \left(y^{(n)},y^{(\acute{n})}, …, y, 1\right)d(z) \in {}^{\omega}\mathbb{C}\) where (not) \(\left(y^{(n)}(a),\ y^{(\acute{n})}(a), …, y(a)\right)^T\in {}^{\omega}\mathbb{C}^{\grave{n}}\) and \(a, z \in {}^{\omega}\mathbb{C}\) has the solution \(y_0\), this can be determined in \(\mathcal{O}(\grave{n}^3)\) giving the error mentioned above. Non-linear or partial (systems of) differential equations may be solved by Newton’s method.\(\square\)

Series theorem for integrals: For \(c, x \in [0, a], f \in {}^{\nu}\mathcal{C}^{n}\) and \(n, \hat{p}, r = 2^p \in {}^{\nu}2\mathbb{N}^*\), DFT forms of TS show\[{\uparrow}_0^a f(x){\downarrow}x = {\uparrow}_0^1 g(y){\downarrow}y = {+}_{\check{q}=1}^{\check{r}}{{+}_{\check{m}=0}^{\check{n}-1}{\widetilde{\grave{m}!}\hat{g}^{(m)}\left (\tilde{r}\acute{q} \right){\tilde{r}}^{\grave{m}}}}+\mathcal{O}\left(\widetilde{\grave{n}!}g^{(n)}(\tilde{a}c){\tilde{r}}^n\right).\square\]Remarks: DFT equivalents may replace any \(g^{(m)}\) for \(g(y) := af(ay)\) and \(a > 0\). Transforming \(z := e^{\pm x}\) makes here infinite bounds of integration finite. A finite integral decreases the remainder’s modulus sufficiently. The midpoint rule is here more advantageous than the trapezoidal rule.

Example: For \(g_{\mp}(\vartheta) := \check{\pi}(1 – {\varepsilon}^2 {\sin}^2(\check{\pi}\vartheta))^{\mp\tilde{2}}\), complete elliptic integrals of the first and second kind are \[{\uparrow}_0^{1} g_{\mp}(\vartheta) {\downarrow}\vartheta = g_{\mp}(\check{1}) + \widetilde{24} g_{\mp}^{(2)}(\check{1}) + \widetilde{1920} g_{\mp}^{(4)}(\check{1}) + \mathcal{O}\left(\widetilde{9!}g_{\mp}^{(6)}(\check{1})\right).\]Second Euler-Maclaurin formula: For \(f(\check{q}) = g(\tilde{r}\acute{q})\) and \(k = \grave{a} = \grave{r}\), the preceding theorem yields in \(\mathcal{O}(_en n)\)\[{+}_{\check{q}=1}^{\check{r}} f(\check{q}) = {\uparrow}_{\check{1}}^{\check{k}} f(x){\downarrow}x + {+}_{\check{m}=1}^{\check{n}-1} H_m \left (f^{(\acute{m})}(\check{k}) – f^{(\acute{m})}(\check{1}) \right ) + \mathcal{O}\left (H_n \left (f^{(\acute{n})}(\check{k}) – f^{(\acute{n})}(\check{1}) \right )\right ).\]Proof: For \(h(x) = x/\)sin \(x\) and \(H_m := {i}^m\widetilde{m!}h^{(m)}(0)=\widetilde{m!}B_m(2-2^m) \rightarrow 2(i\tilde{\pi})^m\),\[{+}_{\check{q}=1}^{\check{r}} g(\tilde{r}\acute{q}) = \check{r}{\uparrow}_0^1 g(y){\downarrow}y – {+}_{\check{q}=1}^{\check{r}}{+}_{\check{m}=1}^{\check{n}-1} {\widetilde{\grave{m}!}g^{(m)}\left (\tilde{r}\acute{q} \right)} + \mathcal{O}\left(\widetilde{\grave{n}!}g^{(n)}(\tilde{a}c){\tilde{r}}^n\right)\]results in the claim by inserting and combining the factorials that are counted depending on partitions where \(B_m\) are Bernoulli numbers and \(B_{\grave{m}} = 0, B_0=1\) as well as \(B_1=-\tilde{2}.\square\)

Conclusion: It holds \(n! \sim \left (\hat{\pi} – \widetilde{3k}\pi \right )^{\tilde{2}}\left (\tilde{e}\check{k}\right )^{\check{k}}\) for \(f(n) = {}_en\) and \(r = \hat{n}\).

Proof: Regard \((1+\tilde{r})^{\check{k}} \sim e^{\tilde{2}}\) and \((1-\tilde{n})^{\tilde{2}} \sim 1-\tilde{r}\) (cf. Nonstandard Analysis) as well as\[\begin{aligned}{}_en! &={\uparrow}_{\check{3}}^{\check{k}} f(x){\downarrow}x + {+}_{\check{m}=1}^{\check{n}} H_m \left (f^{(\acute{m})} (\check{k}) – f^{(\acute{m})} (\check{3}) \right ) + \mathcal{O}\left( H_{n+2} \left (f^{(\grave{n})} (\check{k}) – f^{(\grave{n})} (\check{3})\right)\right) \\ &= \check{k}\left (_e{\check{k}} – 1 \right ) – \check{3}\left (_e{\check{3}} – 1 \right ) – \left (\tilde{k} – \tilde{3} \right )/12 + 7\left (\tilde{k}^3 – \widetilde{27} \right )/360 \mp \cdots .\square\end{aligned}\]First Euler-Maclaurin formula: Mathematical induction for \(n\) shows that7cf. Mollin, Richard A.: Advanced Number Theory with Applications; 1st Ed.; 2017; Routledge; Milton Park, p. 193 f.\[{+}_{\check{q}=0}^{\check{r}}f(\check{q})=\uparrow_0^{\check{r}}{f\left(x\right){\downarrow}x}+\check{f}(\check{r})+\check{f}(0)+{+}_{\check{m}=1}^{\check{n}-1}{\widetilde{m!}}B_m\left(f^{(\acute{m})}\left(\check{r}\right)-f^{(\acute{m})}\left(0\right)\right)+\mathcal{O}\left({\widetilde{n!}}B_n\left(f^{(\acute{n})}\left(\check{r}\right)-f^{(\acute{n})}\left(0\right)\right)\right).\square\]

code of the FFT form

© 2010-2022 by Boris Haase

top

References

References
1 cf. Walter, Wolfgang: Analysis 2; 5., erw. Aufl.; 2002; Springer; Berlin, p. 358 ff.
2 cf. Remmert, Reinhold: Funktionentheorie 1; 3., verb. Aufl.; 1992; Springer; Berlin, p. 165 f.
3 see loc. cit., p. 364
4 cf. Remmert, Reinhold: Funktionentheorie 2; 1. unveränd. Nachdruck der 1. Aufl.; 1992; Springer; Berlin, p. 42
5 cf. Knuth, Donald Ervin: The Art of Computer Programming Volume 2; 3rd Ed.; 1997; Addison Wesley; Reading, p. 302 – 311
6 cf. Walter, loc. cit.
7 cf. Mollin, Richard A.: Advanced Number Theory with Applications; 1st Ed.; 2017; Routledge; Milton Park, p. 193 f.