diff options
author | Andreas Müller <andreas.mueller@ost.ch> | 2022-07-23 18:57:02 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2022-07-23 18:57:02 +0200 |
commit | dd328913befd9014775a1b6d9f9374303f9c44ed (patch) | |
tree | b45cb1805d7e26491f7ced7c9bd2379ecfc8bf6b /buch/papers/laguerre/gamma.tex | |
parent | Merge pull request #25 from JODBaer/master (diff) | |
parent | Restruct paper, correct typos, add positive conclusion, add more citations an... (diff) | |
download | SeminarSpezielleFunktionen-dd328913befd9014775a1b6d9f9374303f9c44ed.tar.gz SeminarSpezielleFunktionen-dd328913befd9014775a1b6d9f9374303f9c44ed.zip |
Merge pull request #26 from p1mueller/master
Verbesserung Laguerre
Diffstat (limited to '')
-rw-r--r-- | buch/papers/laguerre/gamma.tex | 184 |
1 files changed, 126 insertions, 58 deletions
diff --git a/buch/papers/laguerre/gamma.tex b/buch/papers/laguerre/gamma.tex index 2e5fc06..e40d8ca 100644 --- a/buch/papers/laguerre/gamma.tex +++ b/buch/papers/laguerre/gamma.tex @@ -3,17 +3,34 @@ % % (c) 2022 Patrik Müller, Ostschweizer Fachhochschule % -\section{Anwendung: Berechnung der Gamma-Funktion +\section{Anwendung: Berechnung der + Gamma-Funktion% \label{laguerre:section:quad-gamma}} +\rhead{Approximation der Gamma-Funktion}% Die Gauss-Laguerre-Quadratur kann nun verwendet werden, -um exponentiell abfallende Funktionen im Definitionsbereich $(0, \infty)$ zu -berechnen. -Dabei bietet sich z.B. die Gamma-Funkion hervorragend an, +um exponentiell abfallende Funktionen im Definitionsbereich~$(0, \infty)$ +zu berechnen. +Dabei bietet sich zum Beispiel die Gamma-Funktion hervorragend an, wie wir in den folgenden Abschnitten sehen werden. -\subsection{Gamma-Funktion} +Im ersten Abschnitt~\ref{laguerre:subsection:gamma} möchten wir noch einmal +die wichtigsten Eigenschaften der Gamma-Funktion betrachten, +bevor wir dann im zweiten Abschnitt~\ref{laguerre:subsection:gauss-lag-gamma} +diese Eigenschaften nutzen werden, +damit wir die Gauss-Laguerre-Quadratur für die Gamma-Funktion +markant verbessern können. +% damit wir sie dann in einem nächsten Schritt verwenden können, +% um unsere Approximationsmethode zu verbessern +% Im zweiten Abschnitt~\ref{laguerre:subsection:gauss-lag-gamma} +% wenden wir dann die Gauss-Laguerre-Quadratur auf die Gamma-Funktion und +% erweitern die Methode + +{\subsection{Gamma-Funktion} +\label{laguerre:subsection:gamma}} Die Gamma-Funktion ist eine Erweiterung der Fakultät auf die reale und komplexe Zahlenmenge. +Mehr Informationen zur Gamma-Funktion lassen sich im +Abschnitt~\ref{buch:rekursion:section:gamma} finden. Die Definition~\ref{buch:rekursion:def:gamma} beschreibt die Gamma-Funktion als Integral der Form \begin{align} @@ -22,24 +39,30 @@ Integral der Form \int_0^\infty x^{z-1} e^{-x} \, dx , \quad -\text{wobei Realteil von $z$ grösser als $0$} +\text{wobei } \operatorname{Re}(z) > 0 \label{laguerre:gamma} . \end{align} -Der Term $e^{-t}$ im Integranden und der Integrationsbereich erfüllen +Der Term $e^{-x}$ im Integranden und der Integrationsbereich erfüllen genau die Bedingungen der Laguerre-Integration. % Der Term $e^{-t}$ ist genau die Gewichtsfunktion der Laguerre-Integration und % der Definitionsbereich passt ebenfalls genau für dieses Verfahren. -Weiter zu erwähnen ist, dass für die verallgemeinerte Laguerre-Integration die -Gewichtsfunktion $t^\nu e^{-t}$ exakt dem Integranden für $\nu=z-1$ entspricht. +Weiter zu erwähnen ist, dass für die assoziierte Laguerre-Integration die +Gewichtsfunktion $x^\nu e^{-x}$ exakt dem Integranden +für $\nu = z - 1$ entspricht. \subsubsection{Funktionalgleichung} Die Gamma-Funktion besitzt die gleiche Rekursionsbeziehung wie die Fakultät, nämlich \begin{align} +\Gamma(z+1) += z \Gamma(z) +\quad +\text{mit } +\Gamma(1) = -\Gamma(z+1) +1 . \label{laguerre:gamma_funktional} \end{align} @@ -61,21 +84,64 @@ her. Dadurch lassen Werte der Gamma-Funktion sich für $z$ in der rechten Halbebene leicht in die linke Halbebene übersetzen und umgekehrt. -\subsection{Berechnung mittels Gauss-Laguerre-Quadratur} +{\subsection{Berechnung mittels Gauss-Laguerre-Quadratur} +\label{laguerre:subsection:gauss-lag-gamma}} In den vorherigen Abschnitten haben wir gesehen, -dass sich die Gamma-Funktion bestens für die Gauss-Laguerre-Quadratur eignet. +dass sich die Gamma-Funktion bestens für die Gauss-Laguerre-Quadratur +\begin{align*} +\int_0^\infty x^{z-1} e^{-x} \, dx += +\int_0^\infty f(x) w(x) \, dx +\approx +\sum_{i=1}^n f(x_i) A_i +\end{align*} +eignet. Nun bieten sich uns zwei Optionen, diese zu berechnen: \begin{enumerate} -\item Wir verwenden die verallgemeinerten Laguerre-Polynome, dann $f(x)=1$. -\item Wir verwenden die Laguerre-Polynome, dann $f(x)=x^{z-1}$. +\item Wir verwenden die assoziierten Laguerre-Polynome $L_n^\nu(x)$ mit +$w(x) = x^\nu e^{-x}$, $\nu = z - 1$ und $f(x) = 1$. +% $f(x)=1$. +% \begin{align*} +% \int_0^\infty x^{z-1} e^{-x} \, dx +% = +% \int_0^\infty f(x) w(x) \, dx +% \quad +% \text{mit } +% w(x) +% = +% x^\nu e^{-x}, +% \nu +% = +% z - 1 +% \text{ und } +% f(x) = 1 +% . +% \end{align*} +\item Wir verwenden die Laguerre-Polynome $L_n(x)$ mit +$w(x) = e^{-x}$ und $f(x) = x^{z - 1}$. +% $f(x)=x^{z-1}$ +% \begin{align*} +% \int_0^\infty x^{z-1} e^{-x} \, dx +% = +% \int_0^\infty f(x) w(x) \, dx +% \quad +% \text{mit } +% w(x) +% = +% e^{-x} +% \text{ und } +% f(x) = x^{z - 1} +% . +% \end{align*} \end{enumerate} Die erste Variante wäre optimal auf das Problem angepasst, allerdings müssten die Gewichte und Nullstellen für jedes $z$ neu berechnet werden, da sie per Definition von $z$ abhängen. Dazu kommt, -dass die Berechnung der Gewichte $A_i$ nach \cite{laguerre:Cassity1965AbcissasCA} +dass die Berechnung der Gewichte $A_i$ nach +\cite{laguerre:Cassity1965AbcissasCA} \begin{align*} A_i = @@ -113,7 +179,7 @@ ergibt sich \sum_{i=1}^n x_i^{z-1} A_i. \label{laguerre:naive_lag} \end{align} - +% \begin{figure} \centering % \input{papers/laguerre/images/rel_error_simple.pgf} @@ -123,7 +189,7 @@ ergibt sich für verschiedene reele Werte von $z$ und Grade $n$ der Laguerre-Polynome} \label{laguerre:fig:rel_error_simple} \end{figure} - +% Bevor wir die Gauss-Laguerre-Quadratur anwenden, möchten wir als ersten Schritt eine Fehlerabschätzung durchführen. Für den Fehlerterm \eqref{laguerre:lag_error} wird die $2n$-te Ableitung @@ -146,7 +212,7 @@ R_n , \label{laguerre:gamma_err_simple} \end{align} -wobei $\xi$ ein geeigneter Wert im Interval $(0, \infty)$ ist +wobei $\xi$ ein geeigneter Wert im Intervall $(0, \infty)$ ist und $n$ der Grad des verwendeten Laguerre-Polynoms. Eine Fehlerabschätzung mit dem Fehlerterm stellt sich als unnütz heraus, da $R_n$ für $z < 2n - 1$ bei $\xi \rightarrow 0$ eine Singularität aufweist @@ -169,12 +235,12 @@ exakt ist für zu integrierende Polynome mit Grad $\leq 2n-1$ und hinzukommt, dass zudem von $z$ noch $1$ abgezogen wird im Exponenten. Es ist ersichtlich, -dass sich für den Polynomgrad $n$ ein Interval gibt, +dass sich für den Polynomgrad $n$ ein Intervall gibt, in dem der relative Fehler minimal ist. Links steigt der relative Fehler besonders stark an, während er auf der rechten Seite zu konvergieren scheint. Um die linke Hälfte in den Griff zu bekommen, -könnten wir die Reflektionsformel der Gamma-Funktion ausnutzen. +könnten wir die Reflektionsformel der Gamma-Funktion verwenden. \begin{figure} \centering @@ -204,8 +270,8 @@ das Problem in den Griff zu bekommen. Wie wir im vorherigen Abschnitt gesehen haben, scheint der Integrand problematisch. Darum möchten wir jetzt den Integranden analysieren, -um ihn besser verstehen zu können und -dadurch geeignete Gegenmassnahmen zu entwickeln. +damit wir ihn besser verstehen und +dadurch geeignete Gegenmassnahmen zu entwickeln können. % Dieser Abschnitt soll eine grafisches Verständnis dafür schaffen, % wieso der Integrand so problematisch ist. @@ -263,7 +329,7 @@ grösser als $0$ und kleiner als $2n-1$ ist. \subsubsection{Ansatz mit Verschiebungsterm} % Mittels der Funktionalgleichung \eqref{laguerre:gamma_funktional} -% kann der Wert von $\Gamma(z)$ im Interval $z \in [a,a+1]$, +% kann der Wert von $\Gamma(z)$ im Intervall $z \in [a,a+1]$, % in dem der relative Fehler minimal ist, % evaluiert werden und dann mit der Funktionalgleichung zurückverschoben werden. Nun stellt sich die Frage, @@ -322,28 +388,15 @@ s(z, m) \cdot (z - 2n)_{2n} \frac{(n!)^2}{(2n)!} \xi^{z + m - 2n - 1} \label{laguerre:gamma_err_shifted} . \end{align} - +% \begin{figure} \centering \includegraphics{papers/laguerre/images/targets.pdf} % %\vspace{-12pt} -\caption{$a$ in Abhängigkeit von $z$ und $n$} +\caption{$m^*$ in Abhängigkeit von $z$ und $n$} \label{laguerre:fig:targets} \end{figure} -% wobei ist -% mit $z^*(n) \in \mathbb{R}$ wollen wir finden, -% in dem wir den Fehlerterm \eqref{laguerre:lag_error} anpassen -% und in einem nächsten Schritt minimieren. -% Zudem nehmen wir an, -% dass $z < z^*(n)$ ist. -% Wir fügen einen Verschiebungsterm um $m \in \mathbb{N}$ Stellen ein, -% daraus folgt -% -% Damit wir den idealen Verschiebungsterm $m^*$ finden können, -% müssen wir mittels des Fehlerterms \eqref{laguerre:gamma_err_shifted} -% ein Optimierungsproblem % -% Das Optimierungsproblem daraus lässt sich als Daraus formulieren wir das Optimierungproblem \begin{align*} m^* @@ -361,8 +414,8 @@ nur wirklich praktisch sinnvoll für kleine $n$ ist, können die Intervalle $[a(n), a(n)+1]$ empirisch gesucht werden. Wir bestimmen nun die optimalen Verschiebungsterme empirisch -für $n = 2,\ldots, 12$ im Intervall $z \in (0, 1)$, -da $z$ sowieso um den Term $m$ verschoben wird, +für $n = 1,\ldots, 12$ im Intervall $z \in (0, 1)$, +da $z$ sowieso mit den Term $m$ verschoben wird, reicht die $m^*$ nur in diesem Intervall zu analysieren. In Abbildung~\ref{laguerre:fig:targets} sind die empirisch bestimmten $m^*$ abhängig von $z$ und $n$ dargestellt. @@ -382,7 +435,7 @@ Den linearen Regressor = \alpha n + \beta \end{align*} -machen wir nur abhängig von $n$ +machen wir nur abhängig von $n$, in dem wir den Mittelwert $\overline{m}$ von $m^*$ über $z$ berechnen. \begin{figure} @@ -395,8 +448,8 @@ in dem wir den Mittelwert $\overline{m}$ von $m^*$ über $z$ berechnen. \end{figure} In Abbildung~\ref{laguerre:fig:schaetzung} sind die Resultate -der linearen Regression aufgezeigt mit $\alpha = 1.34094$ und $\beta = -0.854093$. +der linearen Regression aufgezeigt mit $\alpha = 1.34154$ und $\beta = +0.848786$. Die lineare Beziehung ist ganz klar ersichtlich und der Fit scheint zu genügen. Der optimale Verschiebungsterm kann nun mit \begin{align*} @@ -413,8 +466,8 @@ gefunden werden. In einem ersten Schritt möchten wir analysieren, wie gut die Abschätzung des optimalen Verschiebungsterms ist. Dazu bestimmen wir den relativen Fehler für verschiedene Verschiebungsterme $m$ -rund um $m^*$ bei gegebenem Polynomgrad $n = 8$ für $z \in (0, 1)$. -Abbildung~\ref{laguerre:fig:rel_error_shifted} sind die relativen Fehler +in der Nähe von $m^*$ bei gegebenem Polynomgrad $n = 8$ für $z \in (0, 1)$. +In Abbildung~\ref{laguerre:fig:rel_error_shifted} sind die relativen Fehler der Approximation dargestellt. Man kann deutlich sehen, dass der relative Fehler anwächst, @@ -512,21 +565,36 @@ H_k(z) \frac{(-1)^k (-z)_k}{(z+1)_k} \end{align*} mit $H_0 = 1$ und $\sum_0^n g_k = 1$ (siehe \cite{laguerre:lanczos}). -Diese Methode wurde zum Beispiel in -{\em GNU Scientific Library}, {\em Boost}, {\em CPython} und +Diese Methode wurde zum Beispiel in +{\em GNU Scientific Library}, {\em Boost}, {\em CPython} und {\em musl} implementiert. -Diese Methode erreicht für $n = 7$ typischerweise Genauigkeit von $13$ +Diese Methode erreicht für $n = 7$ typischerweise eine Genauigkeit von $13$ korrekten, signifikanten Stellen für reele Argumente. -Zum Vergleich: die vorgestellte Methode erreicht für $n = 7$ -eine minimale Genauigkeit von $6$ korrekten, signifikanten Stellen +Zum Vergleich: die vorgestellte Methode erreicht für $n = 7$ +eine minimale Genauigkeit von $6$ korrekten, signifikanten Stellen für reele Argumente. -Das Resultat ist etwas enttäuschend, -aber nicht unerwartet, -da die Lanczos-Methode spezifisch auf dieses Problem zugeschnitten ist und + +\subsubsection{Fazit} +% Das Resultat ist etwas enttäuschend, +Die Genauigkeit der vorgestellten Methode schneidet somit schlechter ab, +als die Lanczos-Methode. +Dieser Erkenntnis kommt nicht ganz unerwartet, +% aber nicht unerwartet, +da die Lanczos-Methode spezifisch auf dieses Problem zugeschnitten ist und unsere Methode eine erweiterte allgemeine Methode ist. -Was die Komplexität der Berechnungen im Betrieb angeht, -ist die Gauss-Laguerre-Quadratur wesentlich ressourcensparender, -weil sie nur aus $n$ Funktionsevaluationen, -wenigen Multiplikationen und Additionen besteht. +Allerdings besticht die vorgestellte Methode +durch ihre stark reduzierte Komplexität. % und Rechenaufwand. +% Was die Komplexität der Berechnungen im Betrieb angeht, +% ist die Gauss-Laguerre-Quadratur wesentlich ressourcensparender, +% weil sie nur aus $n$ Funktionsevaluationen, +% wenigen Multiplikationen und Additionen besteht. +Was den Rechenaufwand angeht, +benötigt die vorgestellte Methode, +für eine Genauigkeit von $n-1$ signifikanten Stellen, +nur $n$ Funktionsevaluationen +und wenige zusätzliche Multiplikationen und Additionen. Demzufolge könnte diese Methode Anwendung in Systemen mit wenig Rechenleistung -und/oder knappen Energieressourcen finden.
\ No newline at end of file +und/oder knappen Energieressourcen finden. +Die vorgestellte Methode ist ein weiteres Beispiel dafür, +wie Verfahren durch die Kenntnis der Eigenschaften einer Funktion +verbessert werden können.
\ No newline at end of file |