Wissenschaftliches Rechnen

Das Folgende setzt Mengenlehre und Nichtstandardanalysis voraus. Sei \(\varepsilon \in [\tilde{\nu}, 1 – \tilde{\nu}]\).

Definition: Seien \(f_n^*(z) = f(\eta_nz)\) die Schwestern zur TR \(f(z) \in \mathcal{O}(D)\) um 0 auf dem Gebiet \(D \subseteq {}^{\omega}\mathbb{C}\) mit \(m, n \in {}^{\omega}\mathbb{N}^{*}\) und \(\eta_n^m := \underline{1}^{2^{\lceil m/n \rceil}}\) sowie \(\delta_n^*f = \check{f} – \check{f}_n^*\) die halben Schwesterabstände von \(f.\) Sei \(\mu_n^m := m!n!/(m + n)!\) und \(\widetilde{(-n)!} := 0\). Für \(j, k \in {}^{\omega}\mathbb{N}, f \in \mathcal{C}_{\pi}^{j+2}\) und die Fourierkoeffizienten \(c_k := \tilde{\hat{\pi}}{\uparrow}_{-\pi}^{\pi}{f(t)\tilde{\epsilon}^{\underline{k}t}{{\downarrow}t}}\)¹vgl. Walter, Wolfgang: Analysis 2; 5., erw. Aufl.; 2002; Springer; Berlin, S. 358 ff. heißt die Reihe \({\LARGE{\textbf{+}}}_{k=-\omega}^{\omega}{c_k\epsilon^{\underline{k}t}}\) Fourierreihe. Auf Ebene der TRn bilden \(\mu\) und \(\eta\) den \(\mu\)-\(\eta\)-Kalkül.\(\triangle\)

Bemerkung: Letzterer erlaubt Integrale und Ableitungen einfach und endlich geschlossen darzustellen²vgl. Remmert, Reinhold: Funktionentheorie 1; 3., verb. Aufl.; 1992; Springer; Berlin, S. 165 f.. Ein Umrechnen auf andere Periodenlängen als \(\hat{\pi}\) ist leicht möglich³s. a.a.O., S. 364.

Beispiel: Aus \(\text{Re} \; c \in [\tilde{\nu}, 1 + \tilde{\nu}[, c \in {}^{\omega}\mathbb{C}\) und \(\varepsilon := \tilde{2}^j, j \in {}^{\omega}\mathbb{N}^{*}\) folgt \(\zeta (n+c)=2^{jn}\tilde{n}{\LARGE{\textbf{+}}}_{k=1}^{n}{\delta_n^* v_c(\tilde{2}^j u^k)}\) für \(z \in {}^{1-\tilde{\nu}}\dot{\mathbb{C}} \subset \mathbb{D}\)⁴vgl. Remmert, Reinhold: Funktionentheorie 2; 1. unveränd. Nachdruck der 1. Aufl.; 1992; Springer; Berlin, S. 42 und \(v_c(z):={\LARGE{\textbf{+}}}_{m=1}^{\omega }{\zeta (m+c){{z}^{m}}}=z{\LARGE{\textbf{+}}}_{m=1}^{\omega }{{{{\widetilde{m}}}^{c}}\widetilde{z-m}}.\)

Beispiel: Eine Richardson-Extrapolation bestimmt die Digammafunktion \(\psi\) und\[\zeta(\grave{n}) =\widetilde{\varepsilon^n\hat{n}}{\LARGE{\textbf{+}}}_{k=1}^n{(\psi(\varepsilon u^k \underline{1}^{2\tilde{n}}) – \psi(\varepsilon u^k))} + \mathcal{O}(\varepsilon^{\hat{n}})\] für \(n = 2\) und \(\varepsilon = \tilde{2}^{13}\) als \(\zeta(3) = 2^{24}{\LARGE{\textbf{+}}}_{k=1}^2{(\psi(\underline{\varepsilon} u^k) – \psi(\varepsilon u^k))} + \mathcal{O}(10^{-16})\).

Darstellungssatz für Integrale: Die TR (s. u.) \(f(z) \in \mathcal{O}(D)\) um 0 für \(D \subseteq {}^{\omega}\mathbb{C}\) ergibt mit \(\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\]Beispiel: Für die TRn \(f(x), g(x) \in {}^{\omega}\mathbb{R}\) gilt \({\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.\)

Darstellungssatz für Ableitungen: Mit \({}^{\widetilde{\nu}}\dot{\mathbb{C}} \subset \mathbb{D} \subseteq {}^{\omega}\mathbb{C}\) ergeben die \(n\)-ten Einheitswurzeln, die TR\[f(z):=f(0) + {\LARGE{\textbf{+}}}_{m=1}^{\omega }{\widetilde{m!}\,{{f}^{(m)}}(0){z^m}},\]\(\varepsilon := \tilde{2}^j\tilde{r}, j \in {}^{\omega}\mathbb{Z}, n = \epsilon^{\sigma} \in {}^{\omega}\mathbb{N}^{*}, u :=\epsilon^{\tilde{n} \hat{\underline{\pi}}}\) und der Konvergenzradius \(r \in {}^{\nu}{\mathbb{R}}_{>0}\) von \(f\)\[{{f}^{(n)}}(0)=2^{jn}\acute{n}!{\LARGE{\textbf{+}}}_{k=1}^{n}{\delta_n^* f(\tilde{2}^j u^k)}.\square\]Universeller Mehrschrittsatz: Mit \(n \in {}^{\nu}\mathbb{N}_{\le p}, k, m, p \in {}^{\nu}\mathbb{N}^{*}, {\downarrow}_{{}^\curvearrowright} 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)\) und \(g_0(a) = f(({}^\curvearrowleft)a, y_0, … , y_{\acute{n}})\) ergibt die TR des Anfangswertproblems \(n\)-ter Ordnung \(y^\prime(x) = f(x, y(({}^\curvearrowright)^0 x), … , y(({}^\curvearrowright)^{\acute{n}} x))\)\[y({}^\curvearrowright x) = y(x) + {\downarrow}_{{}^\curvearrowright}x{\pm}_{k=1}^{p}{\left (g_{p-k}(({}^\curvearrowright) x){\LARGE{\textbf{+}}}_{m=k}^{p}{\widetilde{m!}\tbinom{\acute{m}}{\acute{k}}}\right )} + \mathcal{O}(({\downarrow}_{{}^\curvearrowright} x)^{\grave{p}}).\square\]Auf- und Ableitungssatz für TRn: Mit \(j \in {}^{\omega}\mathbb{Z}\), \(q = \tilde{\varepsilon}(z-a)\), \(a \in D\) und \(k, m \in \mathbb{N}_{<n}\) ergeben modulare Arithmetik⁵vgl. Knuth, Donald Ervin: The Art of Computer Programming Volume 2; 3rd Ed.; 1997; Addison Wesley; Reading, S. 302 – 311 und die \(n\)-ten Einheitswurzeln die entsprechende 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\]Ableitungssatz für Fourierreihen: Mit \(f \in \mathcal{C}_{\pi}^{j+2}\)⁶vgl. Walter, a.a.O., S. 358 ff., \(j \in {}^{\omega}\mathbb{N}, k \in [-\acute{n}, n] \cap \mathbb{Z}, t \in [-\pi, \pi]\) und \(m \in \mathbb{N}_{<\hat{n}}\) ergibt sich mit der Möglichkeit zur gliedweisen Integration folgende DFT-Form:\[{\downarrow}^jf_n(t):=(u^{\tilde{\pi}knt})^T(\delta_{(k+\acute{n})m} \underline{k}^j)(\tilde{u}^{km})(f(\tilde{n}\pi m – \pi))/{\hat{n}}+\mathcal{O}(\tilde{n}).\square\]Folgerung: Die Stützstellen \(mr := \tilde{n}\pi m\) des glatten \(f(mr)\) liefern mit \(k\) wie \(m\) interpolierend in \(\mathcal{O}(\sigma n)\):\[{\downarrow}^jf_n(t):=(u^{\tilde{r}kt})^T(\delta_{km}\underline{k}^j)(\tilde{u}^{km})(f(mr))/{\hat{n}}.\square\]Satz (DFT-Fixpunktverfahren): Jedes \(z \in {}^{\omega}\mathbb{C}\) eines beliebigen \(m\)-Polynoms \(p(z) = 0\) mit \(m \in [2, n] \cap \mathbb{N}\) für \(n := 2^r, r \in {}^{\nu}\mathbb{N}^*\) und Koeffizienten aus \({}^{\nu}\mathbb{C}\) lässt sich (als Anschub) ebenfalls in \(\mathcal{O}(\sigma n)\) bestimmen.

Beweis und Algorithmus: Sei \(U = (\tilde{u}^{jk})\) mit \(j, k \in \mathbb{N}_{<n}, u :=\epsilon^{\tilde{n} \hat{\underline{\pi}}}, q := \hat{z}\) und \(s_k := p(\tilde{2}u^k)\). Eine einfache Transformation erreicht \(|q| < \tilde{2}\) für alle Nullstellen \(\zeta\) von \(p(z)\) und \(p(0) = 1\). Für \(p(z) = \tilde{n}(q^j)^TUs = \tilde{n}\mu^Ts = 0\) ergibt sich die vereinfachte 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)\). Hierbei sei \(\delta_{jk}\) das Kronecker-Delta, der Startpunkt \(q := \tilde{2}\) und \(\beta \in {}^{\nu}\mathbb{C}^*\), sodass jeweils \(||\mu^*-\mu||\) sich ungefähr halbiert und \(\mu^Ts = 0\) gilt. Für \(m > 2\) bildet Polynomdivision den Schluss.\(\square\)

Folgerung: DFT-Nullstellenverfahren iterieren Nullstellen \(a \in {}^{\omega}\mathbb{C}\) zu jeder um Vorgaben \(z_0 \in {}^{\omega}\mathbb{C}\) in eine TR entwickelbaren Funktion \(f(z) \in {}^{\omega}\mathbb{C}\) mit jeweils gleicher Konvergenz wie in Simpson-ähnlichen Verfahren, wenn \({\updownarrow}^0f_n(z)\) bei hinreichend genauen \(|z_{\grave{m}} – z_m|\) und \(m \in {}^{\omega}\mathbb{N}\) (mehrfach) abgeleitet wird.\(\square\)

Bemerkung: Die Identität anstatt \(\delta_n^*\) liefert beliebig genaue Näherungen für die \(f^{(n)}\). Letztere Sätze gelten für mehrdimensionale TRn und Laurent-Reihen ebenso. Der Fehler für analog definierte \(m\)-dimensionale DFT-Formen der TR mit je \(\binom{m+n}{n}\) Ableitungen ist bei vergleichbarem Aufwand \(\mathcal{O}(\varepsilon^n)\) statt \(\mathcal{O}(\varepsilon)\). Eine gute Wahl für die Kronpunkte \(\varepsilon u^m + a\) um um den Kronmittelpunkt \(a\) ist \(\varepsilon = \tilde{2}\) und \(n = 64\).

Approximationssatz: Für \(x \in {}^{\omega}\mathbb{R}\) und \(m, n \in {}^{\nu}\mathbb{N}\) erlauben die \(f^{(s)}(x) \in {}^{\omega}\mathbb{R}\) wie oben die Interpolante\[g(x) := {\LARGE{\textbf{+}}}_{r=0}^{\acute{m}}{\chi_{]x_r, x_{\grave{r}}[}(x)((x_{\grave{r}}-x)p_r(x)+(x-x_r)p_{\grave{r}}(x))/(x_{\grave{r}}-x_r)}+{\LARGE{\textbf{+}}}_{r=0}^m{\chi_{\{x_r\}}(x)p_r(x)}\]mit \(p_r(x) := {\LARGE{\textbf{+}}}_{s=0}^n{f^{(s)}(x_r){(x-x_r)}^s/s!}\) in \(\mathcal{O}(\sigma mn)\) zu berechnen, wobei \(f^{(s)}(x_r) = g^{(s)}(x_r)\) für alle \(x_r \in {}^{\omega}\mathbb{R}\) gilt. Im Komplexen ist \({}^{\omega}\mathbb{R}\) durch \({}^{\omega}\mathbb{C}\) zu ersetzen und es gelte \(x = \gamma(t) \in {}^{\omega}\mathbb{C}\) für den Weg \(\gamma(t)\) mit \(t \in {}^{\omega}\mathbb{R}.\square\)

Differenzialgleichungssatz: Sei \(d(z) \in {}^{\omega}\mathbb{C}^{n+2}\) Vektor von DFT-Formen mit \(n \in {}^{\omega}\mathbb{N}\). Hat das System \(y^{(\grave{n})} = \left(y^{(n)},y^{(\acute{n})}, …, y, 1\right)d(z) \in {}^{\omega}\mathbb{C}\) mit / ohne \(\left(y^{(n)}(a),\ y^{(\acute{n})}(a), …, y(a)\right)^T\in {}^{\omega}\mathbb{C}^{\grave{n}}\) und \(a, z \in {}^{\omega}\mathbb{C}\) die Lösung \(y_0\), so lässt diese sich in \(\mathcal{O}(n^3)\) mit dem zuvor genannten Fehler bestimmen.\(\square\)

Bemerkung: Werden Funktionswerte von Kronpunkten ausgewertet und abbrechende TRn genutzt, lassen sich nichtlineare bzw. partielle (Systeme von) Differenzialgleichungen über DFT-Formen lösen.

Beispiel: Mit \(b = (f(\varepsilon u^0 + a), …, f(\varepsilon u^{\acute{n}} + a), 1)^T \in {}^{\omega}\mathbb{C}^{\grave{n}}\) und einer oberen Dreiecksmatrix \(T(z) \in {}^{\omega}\mathbb{C}^{\grave{n}\times\grave{n}}\) haben gewöhnliche Differenzialgleichungen nur Lösungen, wenn \(T(z)b = 0\) gilt (Cholesky-Zerlegung!).

Reihensatz für Integrale: Reihensatz für Integrale: Für \(c \in [0, a], f \in {}^{\nu}\mathcal{C}^{n}\) und \(n, \hat{p}, r\,(= 2^p), t\,(=2^v), \hat{v} \in {}^{\nu}2\mathbb{N}^*\) zeigen DFT-Formen der TR

\({\uparrow}_0^a f(w){\downarrow}w = {\uparrow}_0^{\tilde{t}a}{\LARGE{\textbf{+}}}_{s=1}^t{f(x+\acute{s}\tilde{t}a){\downarrow}x} = {\uparrow}_0^1 g(y){\downarrow}y\)\( = {\LARGE{\textbf{+}}}_{\check{q}=1}^{\check{r}}{\LARGE{\textbf{+}}}_{\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\)

Bemerkungen: DFT-Äquivalente können die \(g^{(m)}\) mit \(g(y) := af(ay)\) und \(a > 0\) ersetzen. Die Transformation \(z := \epsilon^{\pm x}\) macht hier unendliche Integralgrenzen endlich. Ein endliches Integral verringert den Betrag des Restglieds hinreichend. Die Mittelpunktregel ist hier vorteilhafter als die Trapezregel.

Beispiel: Mit \(g_{\mp}(\vartheta) := \check{\pi}(1 – {\varepsilon}^2 {\sin}^2(\check{\pi}\vartheta))^{\mp\tilde{2}}\) ist das vollständige elliptische Integral I. und II. Art\[{\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).\]Zweite Euler-Maclaurin-Formel: Für \(f(\check{q}) = g(\tilde{r}\acute{q})\) und \(k = \grave{a} = \grave{r}\) liefert der vorangehende Satz in \(\mathcal{O}(\sigma n)\)\[{\LARGE{\textbf{+}}}_{\check{q}=1}^{\check{r}} f(\check{q}) = {\uparrow}_{\check{1}}^{\check{k}} f(x){\downarrow}x + {\LARGE{\textbf{+}}}_{\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 ).\]Beweis: Für \(h(x) = x/\)sin \(x\) und \(H_m := \underline{1}^m\widetilde{m!}h^{(m)}(0)=\widetilde{m!}B_m(2-2^m) \rightarrow 2\tilde{\underline{\pi}}\text{-}^m\) folgt aus\[{\LARGE{\textbf{+}}}_{\check{q}=1}^{\check{r}} g(\tilde{r}\acute{q}) = \check{r}{\uparrow}_0^1 g(y){\downarrow}y – {\LARGE{\textbf{+}}}_{\check{q}=1}^{\check{r}}{\LARGE{\textbf{+}}}_{\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)\]durch Einsetzen und Zusammenfassen der in Abhängigkeit von Partitionen gezählten Fakultäten die Behauptung, wobei die \(B_m\) Bernoulli-Zahlen sind und \(B_{\grave{m}} = 0, B_0=1\) sowie \(B_1=-\tilde{2}\) gilt.\(\square\)

Fakultätssatz: Für \(n \in {}^{\omega}\mathbb{N}\) ergibt die Stirlingformel \(n! \sim {(\hat{\pi}n)}^{\tilde{2}}{(\tilde{\epsilon}n)}^n\epsilon^{\widetilde{12n}}\) (s. Nichtstandardanalysis) asymptotisch \(n! \in \left[g(s_+),g(s_-) \right ]\), wenn \({\tilde{s}}_\pm=\tilde{2}{(25\pm1)n}^{\text{sgn}(\acute{n})}\) und \(g(s_\pm)=\left[\left(\hat{\pi}n+\tilde{3}{\grave{s}}_\pm\pi\right)^{\tilde{2}}{(\tilde{\epsilon}n)}^n\right]\) ist.

Beweis: Für \(\tilde{t} := 6n\) gilt \(t={{}_\epsilon}(1+\grave{s}_\pm t)=(\grave{s}_\pm-\check{t})t+\mathcal{O}(t^3)\) mithilfe vollständiger Induktion.\(\square\)

Erste Euler-Maclaurin-Formel: Vollständige Induktion nach \(n\) zeigt ebenso⁷vgl. Mollin, Richard A.: Advanced Number Theory with Applications; 1st Ed.; 2017; Routledge; Milton Park, S. 193 f.

\({\LARGE{\textbf{+}}}_{\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)+{\LARGE{\textbf{+}}}_{\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\)

Programmtext der FFT-Form

© 2010-2024 by Boris Haase

Seitenbeginn