diff options
Diffstat (limited to 'buch/papers/laguerre/gamma.tex')
| -rw-r--r-- | buch/papers/laguerre/gamma.tex | 247 |
1 files changed, 161 insertions, 86 deletions
diff --git a/buch/papers/laguerre/gamma.tex b/buch/papers/laguerre/gamma.tex index 2e5fc06..0cf17b9 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 -genau die Bedingungen der Laguerre-Integration. +Der Term $e^{-x}$ im Integranden und der Integrationsbereich erfüllen +genau die Bedingungen der Gauss-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 Gauss-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,65 @@ 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 = @@ -103,6 +170,18 @@ Somit entscheiden wir uns aufgrund der vorherigen Punkte, die zweite Variante weiterzuverfolgen. \subsubsection{Direkter Ansatz} +% +\begin{figure} +\centering +% \input{papers/laguerre/images/rel_error_simple.pgf} +\includegraphics{papers/laguerre/images/rel_error_simple.pdf} +%\vspace{-12pt} +\caption{Relativer Fehler des direkten Ansatzes +für verschiedene reelle Werte von $z$ und Grade $n$ der +Laguerre-Polynome}% +\label{laguerre:fig:rel_error_simple} +\end{figure} +%. Wenden wir also die Gauss-Laguerre-Quadratur aus \eqref{laguerre:laguerrequadratur} auf die Gamma-Funktion \eqref{laguerre:gamma} an, @@ -110,20 +189,10 @@ ergibt sich \begin{align} \Gamma(z) \approx -\sum_{i=1}^n x_i^{z-1} A_i. +\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} -\includegraphics{papers/laguerre/images/rel_error_simple.pdf} -%\vspace{-12pt} -\caption{Relativer Fehler des direkten Ansatzes -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 +215,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 @@ -154,8 +223,8 @@ und für $z > 2n - 1$ bei $\xi \rightarrow \infty$ divergiert. Nur für den unwahrscheinlichen Fall $ z = 2n - 1$ wäre eine Fehlerabschätzung plausibel. -Wenden wir nun also direkt die Gauss-Laguerre-Quadratur auf die Gamma-Funktion -an. +Wenden wir nun also direkt die Gauss-Laguerre-Quadratur +auf die Gamma-Funktion an. Dazu benötigen wir die Gewichte nach \eqref{laguerre:quadratur_gewichte} und als Stützstellen die Nullstellen des Laguerre-Polynomes $L_n$. @@ -163,18 +232,17 @@ Evaluieren wir den relativen Fehler unserer Approximation zeigt sich ein Bild wie in Abbildung~\ref{laguerre:fig:rel_error_simple}. Man kann sehen, wie der relative Fehler Nullstellen aufweist für ganzzahlige $z \leq 2n$. -Laut der Theorie der Gauss-Quadratur auch ist das zu erwarten, +Laut der Theorie der Gauss-Quadratur ist das auch zu erwarten, da die Approximation via Gauss-Quadratur -exakt ist für zu integrierende Polynome mit Grad $\leq 2n-1$ -und hinzukommt, -dass zudem von $z$ noch $1$ abgezogen wird im Exponenten. +exakt ist für zu integrierende Polynome mit Grad $\leq 2n-1$ und +der Integrand $x^{z-1}$ wird für $z \in \mathbb{N} \setminus \{0\}$ +zu einem Polynom . +% 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. \begin{figure} \centering @@ -182,10 +250,12 @@ könnten wir die Reflektionsformel der Gamma-Funktion ausnutzen. \includegraphics{papers/laguerre/images/rel_error_mirror.pdf} %\vspace{-12pt} \caption{Relativer Fehler des Ansatzes mit Spiegelung negativer Realwerte -für verschiedene reele Werte von $z$ und Grade $n$ der Laguerre-Polynome} +für verschiedene reelle Werte von $z$ und Grade $n$ der Laguerre-Polynome} \label{laguerre:fig:rel_error_mirror} \end{figure} +Um die linke Hälfte in den Griff zu bekommen, +könnten wir die Reflektionsformel der Gamma-Funktion verwenden. Spiegelt man nun $z$ mit negativem Realteil mittels der Reflektionsformel, ergibt sich ein stabilerer Fehler in der linken Hälfte, wie in Abbildung~\ref{laguerre:fig:rel_error_mirror}. @@ -203,9 +273,10 @@ das Problem in den Griff zu bekommen. \subsubsection{Analyse des Integranden} 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. +Darum möchten wir ihn jetzt analysieren, +damit wir ihn besser verstehen können. +Dies sollte es uns ermöglichen, +anschliessend geeignete Gegenmassnahmen zu entwickeln. % Dieser Abschnitt soll eine grafisches Verständnis dafür schaffen, % wieso der Integrand so problematisch ist. @@ -245,16 +316,17 @@ dass kleine Exponenten um $0$ genauere Resultate liefern sollten. In Abbildung~\ref{laguerre:fig:integrand_exp} fügen wir die Dämpfung der Gewichtsfunktion $w(x)$ der Gauss-Laguerre-Quadratur wieder hinzu -und erhalten so wieder den kompletten Integranden $x^{z-1} e^{-x}$ +und erhalten so wieder den kompletten Integranden $x^{z} e^{-x}$ der Gamma-Funktion. Für negative $z$ ergeben sich immer noch Singularitäten, wenn $x \rightarrow 0$. -Um $1$ wächst der Term $x^z$ schneller als die Dämpfung $e^{-x}$, +Um $x = 1$ wächst der Term $x^z$ für positive $z$ +schneller als die Dämpfung $e^{-x}$, aber für $x \rightarrow \infty$ geht der Integrand gegen $0$. Das führt zu glockenförmigen Kurven, die für grosse Exponenten $z$ nach der Stelle $x=1$ schnell anwachsen. Zu grosse Exponenten $z$ sind also immer noch problematisch. -Kleine positive $z$ scheinen nun also auch zulässig zu sein. +Kleine positive $z$ scheinen nun aber auch zulässig zu sein. Damit formulieren wir die Vermutung, dass $a(n)$, welches das Intervall $[a(n), a(n) + 1]$ definiert, @@ -263,7 +335,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 +394,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,9 +420,10 @@ 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, -reicht die $m^*$ nur in diesem Intervall zu analysieren. +für $n = 1,\ldots, 12$ im Intervall $z \in (0, 1)$, +da $z$ sowieso mit den Term $m$ verschoben wird, +reicht es, +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. In $n$-Richtung lässt sich eine klare lineare Abhängigkeit erkennen und @@ -382,7 +442,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 +455,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 +473,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, @@ -428,7 +488,7 @@ dann beim Übergang auf die orange Linie wechselt. \includegraphics{papers/laguerre/images/rel_error_shifted.pdf} %\vspace{-12pt} \caption{Relativer Fehler des Ansatzes mit Verschiebungsterm -für verschiedene reele Werte von $z$ und Verschiebungsterme $m$. +für verschiedene reelle Werte von $z$ und Verschiebungsterme $m$. Das verwendete Laguerre-Polynom besitzt den Grad $n = 8$. $m^*$ bezeichnet hier den optimalen Verschiebungsterm.} \label{laguerre:fig:rel_error_shifted} @@ -467,7 +527,7 @@ Abbildung~\ref{laguerre:fig:rel_error_range}. \includegraphics{papers/laguerre/images/rel_error_range.pdf} %\vspace{-12pt} \caption{Relativer Fehler des Ansatzes mit optimalen Verschiebungsterm -für verschiedene reele Werte von $z$ und Laguerre-Polynome vom Grad $n$} +für verschiedene reelle Werte von $z$ und Laguerre-Polynome vom Grad $n$} \label{laguerre:fig:rel_error_range} \end{figure} @@ -512,21 +572,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$ -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 -für reele Argumente. -Das Resultat ist etwas enttäuschend, -aber nicht unerwartet, -da die Lanczos-Methode spezifisch auf dieses Problem zugeschnitten ist und +Diese Methode erreicht für $n = 7$ typischerweise eine Genauigkeit von $13$ +korrekten, signifikanten Stellen für reelle Argumente. +Zum Vergleich: die vorgestellte Methode erreicht für $n = 7$ +eine minimale Genauigkeit von $6$ korrekten, signifikanten Stellen +für reelle Argumente. + +\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 |