From 56cc6c1fbae271c16c78935384b52e047cdd6f27 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Patrik=20M=C3=BCller?= Date: Thu, 19 May 2022 16:11:27 +0200 Subject: Error correction & add gamma integrand plot --- buch/papers/laguerre/gamma.tex | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'buch/papers/laguerre/gamma.tex') diff --git a/buch/papers/laguerre/gamma.tex b/buch/papers/laguerre/gamma.tex index e3838b0..b15523b 100644 --- a/buch/papers/laguerre/gamma.tex +++ b/buch/papers/laguerre/gamma.tex @@ -30,12 +30,12 @@ welches alle Eigenschaften erfüllt, um mit der Gauss-Laguerre-Quadratur berechnet zu werden. \subsubsection{Funktionalgleichung} -Die Funktionalgleichung besagt +Die Funktionalgleichung der Gamma-Funktion besagt \begin{align} z \Gamma(z) = \Gamma(z+1). \label{laguerre:gamma_funktional} \end{align} -Mittels dieser Gleichung kann der Wert an einer bestimmten, +Mittels dieser Gleichung kann der Wert von $\Gamma(z)$ an einer bestimmten, geeigneten Stelle evaluiert werden und dann zurückverschoben werden, um das gewünschte Resultat zu erhalten. -- cgit v1.2.1 From 161adb15af8d10ccf6090a43a4c89b0d05c6ecda Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Patrik=20M=C3=BCller?= Date: Sat, 28 May 2022 16:16:52 +0200 Subject: Add introduction, integrand plot and reason why shifting evalutaion of gamma-func --- buch/papers/laguerre/gamma.tex | 21 ++++++++++++++++++--- 1 file changed, 18 insertions(+), 3 deletions(-) (limited to 'buch/papers/laguerre/gamma.tex') diff --git a/buch/papers/laguerre/gamma.tex b/buch/papers/laguerre/gamma.tex index b15523b..59c0b81 100644 --- a/buch/papers/laguerre/gamma.tex +++ b/buch/papers/laguerre/gamma.tex @@ -26,8 +26,10 @@ Integral der Form , \label{laguerre:gamma} \end{align} -welches alle Eigenschaften erfüllt, um mit der Gauss-Laguerre-Quadratur -berechnet zu werden. +Der Term $e^{-t}$ ist genau die Gewichtsfunktion der Laguerre-Integration und +der Definitionsbereich passt ebenfalls genau für dieses Verfahren. +Zu erwähnen ist auch, dass für die verallgemeinerte Laguerre-Integration die +Gewichtsfunktion $t^\nu e^{-t}$ genau dem Integranden für $\nu=z-1$ entspricht. \subsubsection{Funktionalgleichung} Die Funktionalgleichung der Gamma-Funktion besagt @@ -39,6 +41,19 @@ Mittels dieser Gleichung kann der Wert von $\Gamma(z)$ an einer bestimmten, geeigneten Stelle evaluiert werden und dann zurückverschoben werden, um das gewünschte Resultat zu erhalten. +In Abbildung~\ref{laguerre:fig:integrand} ist der Integrand $t^z$ für +unterschiedliche Werte von $z$ dargestellt. +Man erkennt, dass für kleine $z$ sich ein singulärer Integrand ergibt, +was dazu führt, dass die Genauigkeit sich verschlechtert. +Die Genauigkeit verschlechtert sich aber auch zunehmends für grosse $z$, +da in diesem Fall der Integrand sehr schnell anwächst. +\begin{figure} +\centering +\scalebox{0.8}{\input{papers/laguerre/images/integrands.pgf}} +\caption{Integrand $t^z$ mit unterschiedlichen Werten für $z$} +\label{laguerre:fig:integrand} +\end{figure} + \subsection{Berechnung mittels Gauss-Laguerre-Quadratur} Fehlerterm: @@ -52,7 +67,7 @@ R_n Nun stellt sich die Frage, ob die Approximation mittels Gauss-Laguerre-Quadratur verbessert werden kann, wenn man das Problem an einer geeigneten Stelle evaluiert und -dann zurückverschiebt mit der Funktionalgleichung. +dann mit der Funktionalgleichung zurückverschiebt. Dazu wollen wir den Fehlerterm in Gleichung~\eqref{laguerre:lagurre:lag_error} anpassen und dann minimieren. Zunächst wollen wir dies nur für $z\in \mathbb{R}$ und $0 Date: Tue, 31 May 2022 16:31:25 +0200 Subject: Add rule of thumb, analyse integrand, correct mistake in integration SLP<->LP --- buch/papers/laguerre/gamma.tex | 294 ++++++++++++++++++++++++++++++++++++----- 1 file changed, 264 insertions(+), 30 deletions(-) (limited to 'buch/papers/laguerre/gamma.tex') diff --git a/buch/papers/laguerre/gamma.tex b/buch/papers/laguerre/gamma.tex index 59c0b81..da2fa93 100644 --- a/buch/papers/laguerre/gamma.tex +++ b/buch/papers/laguerre/gamma.tex @@ -19,7 +19,7 @@ Integral der Form \begin{align} \Gamma(z) & = -\int_0^\infty t^{z-1} e^{-t} dt +\int_0^\infty x^{z-1} e^{-x} \, dx , \quad \text{wobei Realteil von $z$ grösser als $0$} @@ -32,54 +32,290 @@ Zu erwähnen ist auch, dass für die verallgemeinerte Laguerre-Integration die Gewichtsfunktion $t^\nu e^{-t}$ genau dem Integranden für $\nu=z-1$ entspricht. \subsubsection{Funktionalgleichung} -Die Funktionalgleichung der Gamma-Funktion besagt +Die Gamma-Funktion besitzt die gleiche Rekursionsbeziehung wie die Fakultät, +nämlich \begin{align} -z \Gamma(z) = \Gamma(z+1). +z \Gamma(z) += +\Gamma(z+1) +. \label{laguerre:gamma_funktional} \end{align} -Mittels dieser Gleichung kann der Wert von $\Gamma(z)$ an einer bestimmten, -geeigneten Stelle evaluiert werden und dann zurückverschoben werden, -um das gewünschte Resultat zu erhalten. -In Abbildung~\ref{laguerre:fig:integrand} ist der Integrand $t^z$ für -unterschiedliche Werte von $z$ dargestellt. -Man erkennt, dass für kleine $z$ sich ein singulärer Integrand ergibt, -was dazu führt, dass die Genauigkeit sich verschlechtert. -Die Genauigkeit verschlechtert sich aber auch zunehmends für grosse $z$, -da in diesem Fall der Integrand sehr schnell anwächst. +\subsubsection{Reflektionsformel} +Die Reflektionsformel +\begin{align} +\Gamma(z) \Gamma(1 - z) += +\frac{\pi}{\sin \pi z} +,\quad +\text{für } +z \notin \mathbb{Z} +\label{laguerre:gamma_refform} +\end{align} +stellt eine Beziehung zwischen den zwei Punkten, +die aus der Spiegelung an der Geraden $\operatorname{Re} z = 1/2$ hervorgehen, +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} +In den vorherigen Abschnitten haben wir gesehen, +dass sich die Gamma-Funktion bestens für die Gauss-Laguerre-Quadratur 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}$. +\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{Cassity1965AbcissasCA} +\begin{align*} +A_i += +\frac{ +\Gamma(n) \Gamma(n+\nu) +} +{ +(n+\nu) +\left[L_{n-1}^{\nu}(x_i)\right]^2 +} +\end{align*} +Evaluationen der Gamma-Funktion benötigen. +Somit scheint diese Methode nicht geeignet für unser Vorhaben. + +Bei der zweiten Variante benötigen wir keine Neuberechung der Gewichte +und Nullstellen für unterschiedliche $z$. +In \eqref{laguerre:quadratur_gewichte} ist ersichtlich, +dass die Gewichte einfach zu berechnen sind. +Auch die Nullstellen können vorgängig, +mittels eines geeigneten Verfahrens aus den Polynomen bestimmt werden. +Als problematisch könnte sich höchstens +die zu integrierende Funktion $f(x)=x^{z-1}$ für $|z| \gg 0$ erweisen. +Somit entscheiden wir uns auf Grund der vorherigen Punkte, +die zweite Variante weiterzuverfolgen. + +\subsubsection{Naiver Ansatz} + \begin{figure} \centering -\scalebox{0.8}{\input{papers/laguerre/images/integrands.pgf}} -\caption{Integrand $t^z$ mit unterschiedlichen Werten für $z$} -\label{laguerre:fig:integrand} +\input{papers/laguerre/images/rel_error_simple.pgf} +\caption{Relativer Fehler des naiven Ansatzes +für verschiedene reele Werte von $z$ und Grade $n$ der Laguerre-Polynome} +\label{laguerre:fig:rel_error_simple} \end{figure} -\subsection{Berechnung mittels Gauss-Laguerre-Quadratur} - -Fehlerterm: +Bevor wir die Gauss-Laguerre-Quadratur anwenden, +möchten wir als erstes eine Fehlerabschätzung durchführen. +Für den Fehlerterm \eqref{laguerre:lag_error} wird die $2n$-te Ableitung +der zu integrierenden Funktion $f(\xi)$ benötigt. +Für das Integral der Gamma-Funktion ergibt sich also +\begin{align*} +\frac{d^{2n}}{d\xi^{2n}} f(\xi) + & = +\frac{d^{2n}}{d\xi^{2n}} \xi^{z-1} +\\ + & = +(z - 2n)_{2n} \xi^{z - 2n - 1} +\end{align*} +Eingesetzt im Fehlerterm \eqref{laguerre:lag_error} resultiert \begin{align*} R_n = (z - 2n)_{2n} \frac{(n!)^2}{(2n)!} \xi^{z-2n-1} +, +\label{laguerre:gamma_err_simple} \end{align*} +wobei $\xi$ ein geeigneter Wert im Interval $(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 +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 naiv die Gauss-Laguerre-Quadratur auf die Gammafunktion an. +Dazu benötigen wir die Gewichte nach +\eqref{laguerre:quadratur_gewichte} +und als Stützstellen die Nullstellen des Laguerre-Polynomes $L_n$. +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 < 2n$, +was laut der Theorie der Gauss-Quadratur auch zu erwarten ist, +denn die Approximation via Gauss-Quadratur +ist exakt für zu integrierende Polynome mit Grad $< 2n-1$. +Es ist ersichtlich, +dass sich für den Polynomgrad $n$ ein Interval 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 +\input{papers/laguerre/images/rel_error_mirror.pgf} +\caption{Relativer Fehler des naiven Ansatz mit Spiegelung negativer Realwerte +für verschiedene reele Werte von $z$ und Grade $n$ der Laguerre-Polynome} +\label{laguerre:fig:rel_error_mirror} +\end{figure} + +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}. +Die Spiegelung bringt nur für wenige Werte einen, +für praktische Anwendungen geeigneten, +relativen Fehler. +Wie wir aber in Abbildung~\ref{laguerre:fig:rel_error_simple} sehen konnten, +gibt es für jeden Polynomgrad $n$ ein Intervall $[a, a+1]$, $a \in \mathbb{Z}$, +in welchem der relative Fehler minimal ist. +Die Funktionalgleichung der Gamma-Funktion \eqref{laguerre:gamma_funktional} +könnte uns hier helfen, +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. + +% Dieser Abschnitt soll eine grafisches Verständnis dafür schaffen, +% wieso der Integrand so problematisch ist. +% Was das heisst sollte in Abbildung~\ref{laguerre:fig:integrand} +% und Abbildung~\ref{laguerre:fig:integrand_exp} grafisch dargestellt werden. + +\begin{figure} +\centering +\input{papers/laguerre/images/integrands.pgf} +\caption{Integrand $x^z$ mit unterschiedlichen Werten für $z$} +\label{laguerre:fig:integrand} +\end{figure} + +In Abbildung~\ref{laguerre:fig:integrand} ist der Integrand $x^z$ für +unterschiedliche Werte von $z$ dargestellt. +Dies entspricht der zu integrierenden Funktion $f(x)$ +der Gauss-Laguerre-Quadratur für die Gamma-Funktion- +Man erkennt, +dass für kleine $z$ sich ein singulärer Integrand ergibt +und auch für grosse $z$ wächst der Integrand sehr schnell an. +Das heisst, +die Ableitungen im Fehlerterm divergieren noch schneller +und das wirkt sich negativ auf die Genauigkeit der Approximation aus. +Somit lässt sich hier sagen, +dass kleine Exponenten um $0$ genauere Resultate liefern sollten. + +\begin{figure} +\centering +\input{papers/laguerre/images/integrands_exp.pgf} +\caption{Integrand $x^z e^{-x}$ mit unterschiedlichen Werten für $z$} +\label{laguerre:fig:integrand_exp} +\end{figure} + +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}$ +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}$, +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. +Damit formulieren wir die Vermutung, +dass $a$, +welches das Intervall $[a,a+1]$ definiert, +in dem der relative Fehler minimal ist, +grösser als $0$ und abhängig von $n$ ist. \subsubsection{Finden der optimalen Berechnungsstelle} +% Mittels der Funktionalgleichung \eqref{laguerre:gamma_funktional} +% kann der Wert von $\Gamma(z)$ im Interval $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, ob die Approximation mittels Gauss-Laguerre-Quadratur verbessert werden kann, -wenn man das Problem an einer geeigneten Stelle evaluiert und -dann mit der Funktionalgleichung zurückverschiebt. -Dazu wollen wir den Fehlerterm in -Gleichung~\eqref{laguerre:lagurre:lag_error} anpassen und dann minimieren. -Zunächst wollen wir dies nur für $z\in \mathbb{R}$ und $0 Date: Thu, 2 Jun 2022 15:23:21 +0200 Subject: Add presentation --- buch/papers/laguerre/gamma.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/laguerre/gamma.tex') diff --git a/buch/papers/laguerre/gamma.tex b/buch/papers/laguerre/gamma.tex index da2fa93..a04ec47 100644 --- a/buch/papers/laguerre/gamma.tex +++ b/buch/papers/laguerre/gamma.tex @@ -295,7 +295,7 @@ m^* \begin{figure} \centering -\input{papers/laguerre/images/schaetzung.pgf} +\input{papers/laguerre/images/estimate.pgf} \caption{Schätzung Mittelwert von $m$ und Fehler} \label{laguerre:fig:schaetzung} \end{figure} -- cgit v1.2.1 From fde57297b3efbef28d09a532e1b3895d2b2ad917 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Patrik=20M=C3=BCller?= Date: Thu, 14 Jul 2022 15:03:28 +0200 Subject: Correct Makefile, add text to gamma.tex, separate python-scripts for each image --- buch/papers/laguerre/gamma.tex | 212 +++++++++++++++++++++++++++++++---------- 1 file changed, 164 insertions(+), 48 deletions(-) (limited to 'buch/papers/laguerre/gamma.tex') diff --git a/buch/papers/laguerre/gamma.tex b/buch/papers/laguerre/gamma.tex index a04ec47..a28c180 100644 --- a/buch/papers/laguerre/gamma.tex +++ b/buch/papers/laguerre/gamma.tex @@ -54,7 +54,7 @@ z \notin \mathbb{Z} \label{laguerre:gamma_refform} \end{align} stellt eine Beziehung zwischen den zwei Punkten, -die aus der Spiegelung an der Geraden $\operatorname{Re} z = 1/2$ hervorgehen, +die aus der Spiegelung an der Geraden $\real z = 1/2$ hervorgehen, her. Dadurch lassen Werte der Gamma-Funktion sich für $z$ in der rechten Halbebene leicht in die linke Halbebene übersetzen und umgekehrt. @@ -99,10 +99,20 @@ Somit entscheiden wir uns auf Grund der vorherigen Punkte, die zweite Variante weiterzuverfolgen. \subsubsection{Naiver Ansatz} +Wenden wir also die Gauss-Laguerre-Quadratur aus +\eqref{laguerre:laguerrequadratur} auf die Gamma-Funktion +\eqref{laguerre:gamma} an ergibt sich +\begin{align} +\Gamma(z) +\approx +\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} +\vspace{-12pt} \caption{Relativer Fehler des naiven Ansatzes für verschiedene reele Werte von $z$ und Grade $n$ der Laguerre-Polynome} \label{laguerre:fig:rel_error_simple} @@ -122,13 +132,13 @@ Für das Integral der Gamma-Funktion ergibt sich also (z - 2n)_{2n} \xi^{z - 2n - 1} \end{align*} Eingesetzt im Fehlerterm \eqref{laguerre:lag_error} resultiert -\begin{align*} +\begin{align} R_n = (z - 2n)_{2n} \frac{(n!)^2}{(2n)!} \xi^{z-2n-1} , \label{laguerre:gamma_err_simple} -\end{align*} +\end{align} wobei $\xi$ ein geeigneter Wert im Interval $(0, \infty)$ ist und $n$ der Grad des verwendeten Laguerre-Polynoms. Eine Fehlerabschätzung mit dem Fehlerterm stellt sich als unnütz heraus, @@ -159,6 +169,7 @@ könnten wir die Reflektionsformel der Gamma-Funktion ausnutzen. \begin{figure} \centering \input{papers/laguerre/images/rel_error_mirror.pgf} +\vspace{-12pt} \caption{Relativer Fehler des naiven Ansatz mit Spiegelung negativer Realwerte für verschiedene reele Werte von $z$ und Grade $n$ der Laguerre-Polynome} \label{laguerre:fig:rel_error_mirror} @@ -171,7 +182,8 @@ Die Spiegelung bringt nur für wenige Werte einen, für praktische Anwendungen geeigneten, relativen Fehler. Wie wir aber in Abbildung~\ref{laguerre:fig:rel_error_simple} sehen konnten, -gibt es für jeden Polynomgrad $n$ ein Intervall $[a, a+1]$, $a \in \mathbb{Z}$, +gibt es für jeden Polynomgrad $n$ ein Intervall $[a(n), a(n) + 1]$, +$a(n) \in \mathbb{Z}$, in welchem der relative Fehler minimal ist. Die Funktionalgleichung der Gamma-Funktion \eqref{laguerre:gamma_funktional} könnte uns hier helfen, @@ -181,17 +193,17 @@ 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. +um ihn besser verstehen zu können und +dadurch geeignete Gegenmassnahmen zu entwickeln. % Dieser Abschnitt soll eine grafisches Verständnis dafür schaffen, % wieso der Integrand so problematisch ist. % Was das heisst sollte in Abbildung~\ref{laguerre:fig:integrand} % und Abbildung~\ref{laguerre:fig:integrand_exp} grafisch dargestellt werden. - \begin{figure} \centering -\input{papers/laguerre/images/integrands.pgf} +\input{papers/laguerre/images/integrand.pgf} +\vspace{-12pt} \caption{Integrand $x^z$ mit unterschiedlichen Werten für $z$} \label{laguerre:fig:integrand} \end{figure} @@ -211,7 +223,8 @@ dass kleine Exponenten um $0$ genauere Resultate liefern sollten. \begin{figure} \centering -\input{papers/laguerre/images/integrands_exp.pgf} +\input{papers/laguerre/images/integrand_exp.pgf} +\vspace{-12pt} \caption{Integrand $x^z e^{-x}$ mit unterschiedlichen Werten für $z$} \label{laguerre:fig:integrand_exp} \end{figure} @@ -230,10 +243,10 @@ 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. Damit formulieren wir die Vermutung, -dass $a$, -welches das Intervall $[a,a+1]$ definiert, +dass $a(n)$, +welches das Intervall $[a(n), a(n) + 1]$ definiert, in dem der relative Fehler minimal ist, -grösser als $0$ und abhängig von $n$ ist. +grösser als $0$ ist. \subsubsection{Finden der optimalen Berechnungsstelle} % Mittels der Funktionalgleichung \eqref{laguerre:gamma_funktional} @@ -242,63 +255,174 @@ grösser als $0$ und abhängig von $n$ ist. % evaluiert werden und dann mit der Funktionalgleichung zurückverschoben werden. Nun stellt sich die Frage, ob die Approximation mittels Gauss-Laguerre-Quadratur verbessert werden kann, -wenn man das Problem in einem geeigneten Intervall $[a, a+1]$, -$a \in \mathbb{Z}$, -evaluiert und dann mit der +wenn man das Problem in einem geeigneten Intervall $[a(n), a(n)+1]$, +$a(n) \in \mathbb{Z}$, +evaluiert und dann mit der Funktionalgleichung \eqref{laguerre:gamma_funktional} zurückverschiebt. -Aus Gründen der Übersichtlichkeit möchten wir das Problem nur für reele Zahlen -formulieren. - -Die optimale Stelle $a \leq z^* \leq a+1$, -mit $z^* \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^*$ ist. -Wir fügen einen Verschiebungsterm um $m \in \mathbb{N}$ Stellen ein, -daraus folgt +Für dieses Vorhaben führen wir einen Verschiebungsterm $m \in \mathbb{Z}$ ein. +Passen wir \eqref{laguerre:naive_lag} +mit dem Verschiebungsterm $m$ +%,der $z$ and die Stelle $z_m = z + m$ verschiebt, +an, +ergibt sich +\begin{align} +\Gamma(z) +\approx +s(z, m) \sum_{i=1}^n x_i^{z + m - 1} A_i +% && +% \text{mit } +% s(z, m) +% = +% \begin{cases} +% \displaystyle +% \frac{1}{(z - m)_m} & \text{wenn } m \geq 0\\ +% (z + m)_{-m} & \text{wenn } m < 0 +% \end{cases} +% . +\label{laguerre:shifted_lag} +\end{align} +mit \begin{align*} +s(z, m) += +\begin{cases} +\displaystyle +\frac{1}{(z - m)_m} & \text{wenn } m \geq 0 \\ +(z + m)_{-m} & \text{wenn } m < 0 +\end{cases} +. +\end{align*} + +Um die optimale Stelle $z^*(n) \in \left[a(n), a(n) + 1\right]$, +$z^*(n) \in \mathbb{R}$, +zu finden, +erweitern wir denn Fehlerterm \eqref{laguerre:gamma_err_simple} +und erhalten +\begin{align} R_{n,m}(\xi) = -\frac{(z - 2n)_{2n}}{(z - m)_m} \frac{(n!)^2}{(2n)!} \xi^{z + m - 2n - 1} +s(z, m) \cdot (z - 2n)_{2n} \frac{(n!)^2}{(2n)!} \xi^{z + m - 2n - 1} ,\quad \text{für } \xi \in (0, \infty) -, -\end{align*} -wobei $z^* = z + m - 1$ ist. -Das Optimierungsproblem daraus lässt sich als +. +\label{laguerre:gamma_err_shifted} +\end{align} +% 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^* += \operatorname*{argmin}_m \max_\xi R_{n,m}(\xi) +. \end{align*} -formulieren. Allerdings ist die Funktion $R_{n,m}(\xi)$ unbeschränkt. -Dazu müssten wir $\xi$ versuchen unter Kontroller zu bringen, +Dazu müssten wir $\xi$ versuchen unter Kontrolle zu bringen, was ein äussersts schwieriges Unterfangen zu sein scheint. Da die Gauss-Quadratur aber sowieso nur wirklich Sinn macht für kleine $n$, können die Intervalle $[a(n), a(n)+1]$ empirisch gesucht werden. +\begin{figure} +\centering +% \includegraphics{papers/laguerre/images/targets.pdf} +\input{papers/laguerre/images/targets.pgf} +\vspace{-12pt} +\caption{$a$ in Abhängigkeit von $z$ und $n$} +\label{laguerre:fig:targets} +\end{figure} +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. +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 +die Beziehung zu $z$ ist negativ, +d.h. wenn $z$ grösser ist, wird $m^*$ kleiner. +Allerdings ist die genaue Beziehung zu $z$ +aus dieser Grafik nicht offensichtlich, +aber sie scheint regelmässig zu sein. +Es lässt die Vermutung aufkommen, +dass die Restriktion von $m^* \in \mathbb{Z}$ Rundungsprobleme verursacht. +Wir versuchen dieses Problem via lineare Regression und +geeignete Rundung zu beheben. +Den linearen Regressor +\begin{align*} +\hat{m} += +\alpha n + \beta +\end{align*} +machen wir nur abhängig von $n$ +in dem wir den Mittelwert $\overline{m}$ von $m^*$ über $z$ berechnen. + +In Abbildung~\ref{laguerre:fig:schaetzung} sind die Resultate +der linearen Regression aufgezeigt mit $\alpha = 1.34094$ und $\beta = +0.854093$. +Die lineare Beziehung ist ganz klar ersichtlich und der Fit scheint zu genügen. +Der optimalen Verschiebungsterm \begin{align*} m^* +\approx +\lceil \hat{m} - z \rceil = -\lceil \alpha n + \beta + \lfloor z \rfloor - z \rceil - \lfloor z \rfloor +\lceil \alpha n + \beta - z \rceil \end{align*} +kann nun mit dem linearen Regressor und $z$ gefunden werden. \begin{figure} \centering -\includegraphics{papers/laguerre/images/targets.pdf} -\caption{$a$ in Abhängigkeit von $z$ und $n$} -\label{laguerre:fig:targets} +\input{papers/laguerre/images/estimates.pgf} +\vspace{-12pt} +\caption{Schätzung Mittelwert von $m$ und Fehler} +\label{laguerre:fig:schaetzung} \end{figure} +\subsection{Resultate} + +\subsubsection{Relativer Fehler} \begin{figure} \centering -\input{papers/laguerre/images/estimate.pgf} -\caption{Schätzung Mittelwert von $m$ und Fehler} -\label{laguerre:fig:schaetzung} +\input{papers/laguerre/images/rel_error_shifted.pgf} +\vspace{-12pt} +\caption{Relativer Fehler des Ansatzes mit Verschiebungsterm +für verschiedene reele 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} \end{figure} + +\begin{figure} +\centering +\input{papers/laguerre/images/rel_error_range.pgf} +\vspace{-12pt} +\caption{Relativer Fehler des Ansatzes mit optimalen Verschiebungsterm +für verschiedene reele Werte von $z$ und Grade $n$ der Laguerre-Polynome} +\label{laguerre:fig:rel_error_range} +\end{figure} + +\subsubsection{Vergleich mit Lanczos-Methode} +{\color{red} +$ $\newline +$n = 7$:\newline +Lanczos Polynomgrad auf 13 Stellen.\newline +Unsere Methode auf 7 Stellen +} + % 2. Die Fehlerabschätzung ist problematisch, % weil die Funktion R_n(\xi) unbeschränkt ist. % Daher kann man nicht einfach nach dem Maximum von R_n(\xi) suchen. @@ -315,11 +439,3 @@ m^* % da ja der Witz der Gauss-Integration ist, % dass man eben nur sehr kleine n überhaupt in Betracht zieht, % d.h. man braucht keine exakte Gesetzmässigkeit für a(n). - - -{ -\large \color{red} -TODO: -Geeignete Minimierung für Fehler finden, so dass sie mit den emprisich -bestimmen optimalen Punkten übereinstimmen. -} -- cgit v1.2.1 From e1f5d6267540ea8dc758696fb08cb7540362cf8f Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Patrik=20M=C3=BCller?= Date: Mon, 18 Jul 2022 17:34:37 +0200 Subject: First complete draft of Laguerre chapter --- buch/papers/laguerre/gamma.tex | 242 +++++++++++++++++++++++++++-------------- 1 file changed, 163 insertions(+), 79 deletions(-) (limited to 'buch/papers/laguerre/gamma.tex') diff --git a/buch/papers/laguerre/gamma.tex b/buch/papers/laguerre/gamma.tex index a28c180..eb64fa2 100644 --- a/buch/papers/laguerre/gamma.tex +++ b/buch/papers/laguerre/gamma.tex @@ -23,8 +23,8 @@ Integral der Form , \quad \text{wobei Realteil von $z$ grösser als $0$} -, \label{laguerre:gamma} +. \end{align} Der Term $e^{-t}$ ist genau die Gewichtsfunktion der Laguerre-Integration und der Definitionsbereich passt ebenfalls genau für dieses Verfahren. @@ -72,7 +72,7 @@ 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{Cassity1965AbcissasCA} +dass die Berechnung der Gewichte $A_i$ nach \cite{laguerre:Cassity1965AbcissasCA} \begin{align*} A_i = @@ -85,7 +85,7 @@ A_i } \end{align*} Evaluationen der Gamma-Funktion benötigen. -Somit scheint diese Methode nicht geeignet für unser Vorhaben. +Somit ist diese Methode eindeutig nicht geeignet für unser Vorhaben. Bei der zweiten Variante benötigen wir keine Neuberechung der Gewichte und Nullstellen für unterschiedliche $z$. @@ -95,10 +95,10 @@ Auch die Nullstellen können vorgängig, mittels eines geeigneten Verfahrens aus den Polynomen bestimmt werden. Als problematisch könnte sich höchstens die zu integrierende Funktion $f(x)=x^{z-1}$ für $|z| \gg 0$ erweisen. -Somit entscheiden wir uns auf Grund der vorherigen Punkte, +Somit entscheiden wir uns aufgrund der vorherigen Punkte, die zweite Variante weiterzuverfolgen. -\subsubsection{Naiver Ansatz} +\subsubsection{Direkter Ansatz} Wenden wir also die Gauss-Laguerre-Quadratur aus \eqref{laguerre:laguerrequadratur} auf die Gamma-Funktion \eqref{laguerre:gamma} an ergibt sich @@ -111,15 +111,16 @@ Wenden wir also die Gauss-Laguerre-Quadratur aus \begin{figure} \centering -\input{papers/laguerre/images/rel_error_simple.pgf} -\vspace{-12pt} -\caption{Relativer Fehler des naiven Ansatzes +% \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 erstes eine Fehlerabschätzung durchführen. +möchten wir als ersten Schritt eine Fehlerabschätzung durchführen. Für den Fehlerterm \eqref{laguerre:lag_error} wird die $2n$-te Ableitung der zu integrierenden Funktion $f(\xi)$ benötigt. Für das Integral der Gamma-Funktion ergibt sich also @@ -130,6 +131,7 @@ Für das Integral der Gamma-Funktion ergibt sich also \\ & = (z - 2n)_{2n} \xi^{z - 2n - 1} +. \end{align*} Eingesetzt im Fehlerterm \eqref{laguerre:lag_error} resultiert \begin{align} @@ -147,17 +149,19 @@ 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 naiv die Gauss-Laguerre-Quadratur auf die Gammafunktion 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$. 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 < 2n$, +wie der relative Fehler Nullstellen aufweist für ganzzahlige $z \leq 2n$, was laut der Theorie der Gauss-Quadratur auch zu erwarten ist, denn die Approximation via Gauss-Quadratur -ist exakt für zu integrierende Polynome mit Grad $< 2n-1$. +ist exakt für zu integrierende Polynome mit Grad $\leq 2n-1$ +und von $z$ auch noch $1$ abgezogen wird im Exponenten. Es ist ersichtlich, dass sich für den Polynomgrad $n$ ein Interval gibt, in dem der relative Fehler minimal ist. @@ -168,9 +172,10 @@ könnten wir die Reflektionsformel der Gamma-Funktion ausnutzen. \begin{figure} \centering -\input{papers/laguerre/images/rel_error_mirror.pgf} -\vspace{-12pt} -\caption{Relativer Fehler des naiven Ansatz mit Spiegelung negativer Realwerte +% \input{papers/laguerre/images/rel_error_mirror.pgf} +\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} \label{laguerre:fig:rel_error_mirror} \end{figure} @@ -202,8 +207,9 @@ dadurch geeignete Gegenmassnahmen zu entwickeln. % und Abbildung~\ref{laguerre:fig:integrand_exp} grafisch dargestellt werden. \begin{figure} \centering -\input{papers/laguerre/images/integrand.pgf} -\vspace{-12pt} +% \input{papers/laguerre/images/integrand.pgf} +\includegraphics{papers/laguerre/images/integrand.pdf} +%\vspace{-12pt} \caption{Integrand $x^z$ mit unterschiedlichen Werten für $z$} \label{laguerre:fig:integrand} \end{figure} @@ -211,7 +217,7 @@ dadurch geeignete Gegenmassnahmen zu entwickeln. In Abbildung~\ref{laguerre:fig:integrand} ist der Integrand $x^z$ für unterschiedliche Werte von $z$ dargestellt. Dies entspricht der zu integrierenden Funktion $f(x)$ -der Gauss-Laguerre-Quadratur für die Gamma-Funktion- +der Gauss-Laguerre-Quadratur für die Gamma-Funktion. Man erkennt, dass für kleine $z$ sich ein singulärer Integrand ergibt und auch für grosse $z$ wächst der Integrand sehr schnell an. @@ -223,8 +229,9 @@ dass kleine Exponenten um $0$ genauere Resultate liefern sollten. \begin{figure} \centering -\input{papers/laguerre/images/integrand_exp.pgf} -\vspace{-12pt} +% \input{papers/laguerre/images/integrand_exp.pgf} +\includegraphics{papers/laguerre/images/integrand_exp.pdf} +%\vspace{-12pt} \caption{Integrand $x^z e^{-x}$ mit unterschiedlichen Werten für $z$} \label{laguerre:fig:integrand_exp} \end{figure} @@ -246,9 +253,9 @@ Damit formulieren wir die Vermutung, dass $a(n)$, welches das Intervall $[a(n), a(n) + 1]$ definiert, in dem der relative Fehler minimal ist, -grösser als $0$ ist. +grösser als $0$ und kleiner als $2n-1$ ist. -\subsubsection{Finden der optimalen Berechnungsstelle} +\subsubsection{Ansatz mit Verschiebungsterm} % Mittels der Funktionalgleichung \eqref{laguerre:gamma_funktional} % kann der Wert von $\Gamma(z)$ im Interval $z \in [a,a+1]$, % in dem der relative Fehler minimal ist, @@ -287,12 +294,13 @@ s(z, m) = \begin{cases} \displaystyle -\frac{1}{(z - m)_m} & \text{wenn } m \geq 0 \\ -(z + m)_{-m} & \text{wenn } m < 0 +\frac{1}{(z)_m} & \text{wenn } m \geq 0 \\ +(z + m)_{-m} & \text{wenn } m < 0 \end{cases} . \end{align*} +\subsubsection{Finden der optimalen Berechnungsstelle} Um die optimale Stelle $z^*(n) \in \left[a(n), a(n) + 1\right]$, $z^*(n) \in \mathbb{R}$, zu finden, @@ -305,9 +313,17 @@ s(z, m) \cdot (z - 2n)_{2n} \frac{(n!)^2}{(2n)!} \xi^{z + m - 2n - 1} ,\quad \text{für } \xi \in (0, \infty) -. \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$} +\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 @@ -329,21 +345,14 @@ m^* \operatorname*{argmin}_m \max_\xi R_{n,m}(\xi) . \end{align*} -Allerdings ist die Funktion $R_{n,m}(\xi)$ unbeschränkt. +Allerdings ist die Funktion $R_{n,m}(\xi)$ unbeschränkt und +hat die gleichen Probleme wie die Fehlerabschätzung des direkten Ansatzes. Dazu müssten wir $\xi$ versuchen unter Kontrolle zu bringen, was ein äussersts schwieriges Unterfangen zu sein scheint. -Da die Gauss-Quadratur aber sowieso nur wirklich Sinn macht für kleine $n$, +Da die Gauss-Quadratur aber sowieso +nur wirklich praktisch sinnvoll für kleine $n$ ist, können die Intervalle $[a(n), a(n)+1]$ empirisch gesucht werden. -\begin{figure} -\centering -% \includegraphics{papers/laguerre/images/targets.pdf} -\input{papers/laguerre/images/targets.pgf} -\vspace{-12pt} -\caption{$a$ in Abhängigkeit von $z$ und $n$} -\label{laguerre:fig:targets} -\end{figure} - 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, @@ -369,11 +378,20 @@ Den linearen Regressor machen wir nur abhängig von $n$ in dem wir den Mittelwert $\overline{m}$ von $m^*$ über $z$ berechnen. +\begin{figure} +\centering +% \input{papers/laguerre/images/estimates.pgf} +\includegraphics{papers/laguerre/images/estimates.pdf} +%\vspace{-12pt} +\caption{Schätzung Mittelwert von $m$ und Fehler} +\label{laguerre:fig:schaetzung} +\end{figure} + In Abbildung~\ref{laguerre:fig:schaetzung} sind die Resultate der linearen Regression aufgezeigt mit $\alpha = 1.34094$ und $\beta = 0.854093$. Die lineare Beziehung ist ganz klar ersichtlich und der Fit scheint zu genügen. -Der optimalen Verschiebungsterm +Der optimalen Verschiebungsterm kann nun mit \begin{align*} m^* \approx @@ -381,61 +399,127 @@ m^* = \lceil \alpha n + \beta - z \rceil \end{align*} -kann nun mit dem linearen Regressor und $z$ gefunden werden. - -\begin{figure} -\centering -\input{papers/laguerre/images/estimates.pgf} -\vspace{-12pt} -\caption{Schätzung Mittelwert von $m$ und Fehler} -\label{laguerre:fig:schaetzung} -\end{figure} - -\subsection{Resultate} - -\subsubsection{Relativer Fehler} +% kann nun mit dem linearen Regressor und $z$ +gefunden werden. +\subsubsection{Evaluation des Schätzers} +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 +der Approximation dargestellt. +Man kann deutlich sehen, +dass der relative Fehler anwächst, +je weiter der Verschiebungsterm vom idealen Wert abweicht. +Zudem scheint der Schätzer den optimalen Verschiebungsterm gut zu bestimmen, +da der Schätzer zuerst der grünen Linie folgt und +dann beim Übergang auf die orange Linie wechselt. \begin{figure} \centering -\input{papers/laguerre/images/rel_error_shifted.pgf} -\vspace{-12pt} +% \input{papers/laguerre/images/rel_error_shifted.pgf} +\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$. Das verwendete Laguerre-Polynom besitzt den Grad $n = 8$. $m^*$ bezeichnet hier den optimalen Verschiebungsterm} \label{laguerre:fig:rel_error_shifted} \end{figure} - + +\subsubsection{Resultate} +Das Verfahren scheint für den Grad $n=8$ und $z \in (0,1)$ gut zu funktioneren. +Es stellt sich nun die Frage, +wie der relative Fehler sich für verschiedene $z$ und $n$ verhält. +In Abbildung~\ref{laguerre:fig:rel_error_range} sind die relativen Fehler für +unterschiedliche $n$ dargestellt. +Der relative Fehler scheint immer noch Nullstellen aufzuweisen, +bei für ganzzahlige $z$. +Durch das Verschieben ergibt sich jetzt aber, +wie zu erwarten war, +ein periodischer relativer Fehler mit einer Periodendauer von $1$. +Zudem lässt sich erkennen, +dass der Fehler abhängig von der Ordnung $n$ +des verwendeten Laguerre-Polynoms ist. +Wenn der Grad $n$ um $1$ erhöht wird, +verbessert sich die Genauigkeit des Resultats um etwa eine signifikante Stelle. + +In Abbildung~\ref{laguerre:fig:rel_error_complex} +ist der Betrag des relativen Fehlers in der komplexen Ebene dargestellt. +Je stärker der Imaginäranteil von $z$ von $0$ abweicht, +umso schlechter wird die Genauigkeit der Approximation. +Das erstaunt nicht weiter, +da die Gauss-Quadratur eigentlich nur für reelle Zahlen definiert ist. +Wenn der Imaginäranteil von $z$ ungefähr $0$ ist, +lässt sich das gleiche Bild beobachten wie in +Abbildung~\ref{laguerre:fig:rel_error_range}. + \begin{figure} \centering -\input{papers/laguerre/images/rel_error_range.pgf} -\vspace{-12pt} +% \input{papers/laguerre/images/rel_error_range.pgf} +\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 Grade $n$ der Laguerre-Polynome} +für verschiedene reele Werte von $z$ und Laguerre-Polynome vom Grad $n$} \label{laguerre:fig:rel_error_range} \end{figure} -\subsubsection{Vergleich mit Lanczos-Methode} -{\color{red} -$ $\newline -$n = 7$:\newline -Lanczos Polynomgrad auf 13 Stellen.\newline -Unsere Methode auf 7 Stellen -} - -% 2. Die Fehlerabschätzung ist problematisch, -% weil die Funktion R_n(\xi) unbeschränkt ist. -% Daher kann man nicht einfach nach dem Maximum von R_n(\xi) suchen. -% Man muss zunächst irgendwie das \xi unter Kontrolle bringen. -% Das scheint mir äusserst schwierig zu sein. +\begin{figure} +\centering +\includegraphics{papers/laguerre/images/rel_error_complex.pdf} +%\vspace{-12pt} +\caption{Absolutwert des relativen Fehlers in der komplexen Ebene} +\label{laguerre:fig:rel_error_complex} +\end{figure} -% Ich möchte daher folgendes anregen: -% Im Sinne der Formulierung des Problems, -% wie im Punkt 1 oben könnten Sie für verschiedene n -% nach den optimalen Intervallen [a(n),a(n)+1] suchen, -% und versuchen, einen empirischen Zusammenhang (Faustregel) -% zwischen n und a(n) zu formulieren. -% Das ist etwa gleich gut, -% da ja der Witz der Gauss-Integration ist, -% dass man eben nur sehr kleine n überhaupt in Betracht zieht, -% d.h. man braucht keine exakte Gesetzmässigkeit für a(n). +\subsubsection{Vergleich mit Lanczos-Methode} +Nun stellt sich die Frage, +wie das in diesem Abschnitt beschriebene Approximationsverfahren +der Gamma-Funktion sich gegenüber den üblichen Approximationsverfahren schlägt. +Eine häufig verwendete Methode ist die Lanczos-Approximation, +welche gegeben ist durch +\begin{align} +\Gamma(z + 1) +\approx +\sqrt{2\pi} \left( z + \sigma + \frac{1}{2} \right)^{z + 1/2} +e^{-(z + \sigma + 1/2)} \sum_{k=0}^n g_k H_k(z) +, +\end{align} +wobei +\begin{align*} +g_k = \frac{e^\sigma \varepsilon_k (-1)^k}{\sqrt{2\pi}} +\sum_{r=0}^k (-1)^r \, \binom{k}{r} \, (k)_r +\left( \frac{e}{r + \sigma + \frac{1}{2}}\right)^{r + 1/2} +, +\end{align*} +\begin{align*} +\varepsilon_k += +\begin{cases} +1 & \text{für } k = 0 \\ +2 & \text{sonst} +\end{cases} +\quad \text{und}\quad +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 +{\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$-$7$ 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 +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$ Funktionasevaluationen, +wenigen Multiplikationen und Additionen besteht. +Also könnte diese Methode z.B. Anwendung in Systemen mit wenig Rechenleistung +und/oder knappen Energieressourcen finden. \ No newline at end of file -- cgit v1.2.1 From f0ff46df0f4c212b44cbed4c01ad357c75f0bdbb Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Patrik=20M=C3=BCller?= Date: Tue, 19 Jul 2022 07:40:48 +0200 Subject: Fix typos in gamma.tex and quadratur.tex --- buch/papers/laguerre/gamma.tex | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'buch/papers/laguerre/gamma.tex') diff --git a/buch/papers/laguerre/gamma.tex b/buch/papers/laguerre/gamma.tex index eb64fa2..b76daeb 100644 --- a/buch/papers/laguerre/gamma.tex +++ b/buch/papers/laguerre/gamma.tex @@ -245,7 +245,7 @@ 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}$, aber für $x \rightarrow \infty$ geht der Integrand gegen $0$. -Das führt zu Glockenförmigen Kurven, +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. -- cgit v1.2.1 From 2625b1234dd68a9cc3ce50675ac0b1cb80eca275 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Patrik=20M=C3=BCller?= Date: Tue, 19 Jul 2022 16:31:48 +0200 Subject: Correct typos, improve grammar --- buch/papers/laguerre/gamma.tex | 55 ++++++++++++++++++++++++------------------ 1 file changed, 31 insertions(+), 24 deletions(-) (limited to 'buch/papers/laguerre/gamma.tex') diff --git a/buch/papers/laguerre/gamma.tex b/buch/papers/laguerre/gamma.tex index b76daeb..2e5fc06 100644 --- a/buch/papers/laguerre/gamma.tex +++ b/buch/papers/laguerre/gamma.tex @@ -8,8 +8,8 @@ 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 bestens an, wie wir in den folgenden -Abschnitten sehen werden. +Dabei bietet sich z.B. die Gamma-Funkion hervorragend an, +wie wir in den folgenden Abschnitten sehen werden. \subsection{Gamma-Funktion} Die Gamma-Funktion ist eine Erweiterung der Fakultät auf die reale und komplexe @@ -26,10 +26,12 @@ Integral der Form \label{laguerre:gamma} . \end{align} -Der Term $e^{-t}$ ist genau die Gewichtsfunktion der Laguerre-Integration und -der Definitionsbereich passt ebenfalls genau für dieses Verfahren. -Zu erwähnen ist auch, dass für die verallgemeinerte Laguerre-Integration die -Gewichtsfunktion $t^\nu e^{-t}$ genau dem Integranden für $\nu=z-1$ entspricht. +Der Term $e^{-t}$ 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. \subsubsection{Funktionalgleichung} Die Gamma-Funktion besitzt die gleiche Rekursionsbeziehung wie die Fakultät, @@ -62,7 +64,8 @@ leicht in die linke Halbebene übersetzen und umgekehrt. \subsection{Berechnung mittels Gauss-Laguerre-Quadratur} In den vorherigen Abschnitten haben wir gesehen, dass sich die Gamma-Funktion bestens für die Gauss-Laguerre-Quadratur eignet. -Nun bieten sich uns zwei Optionen diese zu berechnen: +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}$. @@ -92,7 +95,8 @@ und Nullstellen für unterschiedliche $z$. In \eqref{laguerre:quadratur_gewichte} ist ersichtlich, dass die Gewichte einfach zu berechnen sind. Auch die Nullstellen können vorgängig, -mittels eines geeigneten Verfahrens aus den Polynomen bestimmt werden. +mittels eines geeigneten Verfahrens, +aus den Polynomen bestimmt werden. Als problematisch könnte sich höchstens die zu integrierende Funktion $f(x)=x^{z-1}$ für $|z| \gg 0$ erweisen. Somit entscheiden wir uns aufgrund der vorherigen Punkte, @@ -101,7 +105,8 @@ die zweite Variante weiterzuverfolgen. \subsubsection{Direkter Ansatz} Wenden wir also die Gauss-Laguerre-Quadratur aus \eqref{laguerre:laguerrequadratur} auf die Gamma-Funktion -\eqref{laguerre:gamma} an ergibt sich +\eqref{laguerre:gamma} an, +ergibt sich \begin{align} \Gamma(z) \approx @@ -157,11 +162,12 @@ und als Stützstellen die Nullstellen des Laguerre-Polynomes $L_n$. 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$, -was laut der Theorie der Gauss-Quadratur auch zu erwarten ist, -denn die Approximation via Gauss-Quadratur -ist exakt für zu integrierende Polynome mit Grad $\leq 2n-1$ -und von $z$ auch noch $1$ abgezogen wird im Exponenten. +wie der relative Fehler Nullstellen aufweist für ganzzahlige $z \leq 2n$. +Laut der Theorie der Gauss-Quadratur auch ist das 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. Es ist ersichtlich, dass sich für den Polynomgrad $n$ ein Interval gibt, in dem der relative Fehler minimal ist. @@ -347,7 +353,8 @@ m^* \end{align*} Allerdings ist die Funktion $R_{n,m}(\xi)$ unbeschränkt und hat die gleichen Probleme wie die Fehlerabschätzung des direkten Ansatzes. -Dazu müssten wir $\xi$ versuchen unter Kontrolle zu bringen, +Dazu müssten wir $\xi$ versuchen, +unter Kontrolle zu bringen, was ein äussersts schwieriges Unterfangen zu sein scheint. Da die Gauss-Quadratur aber sowieso nur wirklich praktisch sinnvoll für kleine $n$ ist, @@ -367,8 +374,8 @@ aus dieser Grafik nicht offensichtlich, aber sie scheint regelmässig zu sein. Es lässt die Vermutung aufkommen, dass die Restriktion von $m^* \in \mathbb{Z}$ Rundungsprobleme verursacht. -Wir versuchen dieses Problem via lineare Regression und -geeignete Rundung zu beheben. +Wir versuchen, +dieses Problem via lineare Regression und geeignete Rundung zu beheben. Den linearen Regressor \begin{align*} \hat{m} @@ -391,7 +398,7 @@ In Abbildung~\ref{laguerre:fig:schaetzung} sind die Resultate der linearen Regression aufgezeigt mit $\alpha = 1.34094$ und $\beta = 0.854093$. Die lineare Beziehung ist ganz klar ersichtlich und der Fit scheint zu genügen. -Der optimalen Verschiebungsterm kann nun mit +Der optimale Verschiebungsterm kann nun mit \begin{align*} m^* \approx @@ -423,7 +430,7 @@ dann beim Übergang auf die orange Linie wechselt. \caption{Relativer Fehler des Ansatzes mit Verschiebungsterm für verschiedene reele Werte von $z$ und Verschiebungsterme $m$. Das verwendete Laguerre-Polynom besitzt den Grad $n = 8$. -$m^*$ bezeichnet hier den optimalen Verschiebungsterm} +$m^*$ bezeichnet hier den optimalen Verschiebungsterm.} \label{laguerre:fig:rel_error_shifted} \end{figure} @@ -433,8 +440,8 @@ Es stellt sich nun die Frage, wie der relative Fehler sich für verschiedene $z$ und $n$ verhält. In Abbildung~\ref{laguerre:fig:rel_error_range} sind die relativen Fehler für unterschiedliche $n$ dargestellt. -Der relative Fehler scheint immer noch Nullstellen aufzuweisen, -bei für ganzzahlige $z$. +Der relative Fehler scheint immer noch Nullstellen aufzuweisen +für ganzzahlige $z$. Durch das Verschieben ergibt sich jetzt aber, wie zu erwarten war, ein periodischer relativer Fehler mit einer Periodendauer von $1$. @@ -511,7 +518,7 @@ Diese Methode wurde zum Beispiel in 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$-$7$ korrekten, signifikanten Stellen +eine minimale Genauigkeit von $6$ korrekten, signifikanten Stellen für reele Argumente. Das Resultat ist etwas enttäuschend, aber nicht unerwartet, @@ -519,7 +526,7 @@ 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$ Funktionasevaluationen, +weil sie nur aus $n$ Funktionsevaluationen, wenigen Multiplikationen und Additionen besteht. -Also könnte diese Methode z.B. Anwendung in Systemen mit wenig Rechenleistung +Demzufolge könnte diese Methode Anwendung in Systemen mit wenig Rechenleistung und/oder knappen Energieressourcen finden. \ No newline at end of file -- cgit v1.2.1 From 5da2fa5a5e6a2fa2b8a23745b8c300d15a06669d Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Patrik=20M=C3=BCller?= Date: Sat, 23 Jul 2022 15:19:20 +0200 Subject: Restruct paper, correct typos, add positive conclusion, add more citations and references, small changes to plots --- buch/papers/laguerre/gamma.tex | 184 ++++++++++++++++++++++++++++------------- 1 file changed, 126 insertions(+), 58 deletions(-) (limited to 'buch/papers/laguerre/gamma.tex') 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 -- cgit v1.2.1 From 7d01dd49954a2f6c1c2b662af1c01f3928ddb827 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Patrik=20M=C3=BCller?= Date: Mon, 25 Jul 2022 10:06:45 +0200 Subject: Add missing explanations, correct typos, mention sign change of LP earlier --- buch/papers/laguerre/gamma.tex | 89 +++++++++++++++++++++++------------------- 1 file changed, 48 insertions(+), 41 deletions(-) (limited to 'buch/papers/laguerre/gamma.tex') diff --git a/buch/papers/laguerre/gamma.tex b/buch/papers/laguerre/gamma.tex index e40d8ca..0cf17b9 100644 --- a/buch/papers/laguerre/gamma.tex +++ b/buch/papers/laguerre/gamma.tex @@ -25,7 +25,7 @@ markant verbessern können. % wenden wir dann die Gauss-Laguerre-Quadratur auf die Gamma-Funktion und % erweitern die Methode -{\subsection{Gamma-Funktion} +\subsection{Gamma-Funktion% \label{laguerre:subsection:gamma}} Die Gamma-Funktion ist eine Erweiterung der Fakultät auf die reale und komplexe Zahlenmenge. @@ -44,11 +44,11 @@ Integral der Form . \end{align} Der Term $e^{-x}$ im Integranden und der Integrationsbereich erfüllen -genau die Bedingungen der Laguerre-Integration. +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 assoziierte Laguerre-Integration die -Gewichtsfunktion $x^\nu e^{-x}$ exakt dem Integranden +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} @@ -84,10 +84,11 @@ 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 +dass sich die Gamma-Funktion bestens für die Gauss-Laguerre-Quadratur \begin{align*} \int_0^\infty x^{z-1} e^{-x} \, dx = @@ -169,16 +170,6 @@ Somit entscheiden wir uns aufgrund der vorherigen Punkte, die zweite Variante weiterzuverfolgen. \subsubsection{Direkter Ansatz} -Wenden wir also die Gauss-Laguerre-Quadratur aus -\eqref{laguerre:laguerrequadratur} auf die Gamma-Funktion -\eqref{laguerre:gamma} an, -ergibt sich -\begin{align} -\Gamma(z) -\approx -\sum_{i=1}^n x_i^{z-1} A_i. -\label{laguerre:naive_lag} -\end{align} % \begin{figure} \centering @@ -186,10 +177,22 @@ ergibt sich \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} +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, +ergibt sich +\begin{align} +\Gamma(z) +\approx +\sum_{i=1}^n x_i^{z-1} A_i +\label{laguerre:naive_lag} +. +\end{align} 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 @@ -220,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$. @@ -229,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 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 verwenden. \begin{figure} \centering @@ -248,10 +250,12 @@ könnten wir die Reflektionsformel der Gamma-Funktion verwenden. \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}. @@ -269,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, -damit wir ihn besser verstehen und -dadurch geeignete Gegenmassnahmen zu entwickeln können. +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. @@ -311,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, @@ -416,7 +422,8 @@ können die Intervalle $[a(n), a(n)+1]$ empirisch gesucht werden. Wir bestimmen nun die optimalen Verschiebungsterme empirisch 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. +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 @@ -481,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} @@ -520,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} @@ -569,14 +576,14 @@ 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 eine Genauigkeit von $13$ -korrekten, signifikanten Stellen für reele Argumente. +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 reele Argumente. +für reelle Argumente. \subsubsection{Fazit} % Das Resultat ist etwas enttäuschend, -Die Genauigkeit der vorgestellten Methode schneidet somit schlechter ab, +Die Genauigkeit der vorgestellten Methode schneidet somit schlechter ab als die Lanczos-Methode. Dieser Erkenntnis kommt nicht ganz unerwartet, % aber nicht unerwartet, @@ -595,6 +602,6 @@ 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. -Die vorgestellte Methode ist ein weiteres Beispiel dafür, -wie Verfahren durch die Kenntnis der Eigenschaften einer Funktion +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 -- cgit v1.2.1