diff options
Diffstat (limited to 'buch/chapters/040-rekursion')
25 files changed, 2372 insertions, 170 deletions
diff --git a/buch/chapters/040-rekursion/Makefile.inc b/buch/chapters/040-rekursion/Makefile.inc index c5887f7..cd54c80 100644 --- a/buch/chapters/040-rekursion/Makefile.inc +++ b/buch/chapters/040-rekursion/Makefile.inc @@ -4,9 +4,12 @@ # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -CHAPTERFILES = $(CHAPTERFILES) \ +CHAPTERFILES += \ chapters/040-rekursion/gamma.tex \ + chapters/040-rekursion/bohrmollerup.tex \ + chapters/040-rekursion/integral.tex \ chapters/040-rekursion/beta.tex \ + chapters/040-rekursion/betaverteilung.tex \ chapters/040-rekursion/linear.tex \ chapters/040-rekursion/hypergeometrisch.tex \ chapters/040-rekursion/uebungsaufgaben/401.tex \ diff --git a/buch/chapters/040-rekursion/beta.tex b/buch/chapters/040-rekursion/beta.tex index ea847bc..20e3f0e 100644 --- a/buch/chapters/040-rekursion/beta.tex +++ b/buch/chapters/040-rekursion/beta.tex @@ -3,11 +3,19 @@ % % (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule % -\subsection{Die Beta-Funktion -\label{buch:rekursion:gamma:subsection:beta}} +\section{Die Beta-Funktion +\label{buch:rekursion:gamma:section:beta}} Die Eulersche Integralformel für die Gamma-Funktion in -Definition~\ref{buch:rekursion:def:gamma} wurde bisher nicht -gerechtfertigt. +Definition~\ref{buch:rekursion:def:gamma} wurde in +Abschnitt~\ref{buch:subsection:integral-eindeutig} +mit dem Satz~\ref{buch:satz:bohr-mollerup} +von Bohr-Mollerup gerechtfertigt. +Man kann Sie aber auch als Grenzfall der Beta-Funktion verstehen, +die in diesem Abschnitt dargestellt wird. + + +\subsection{Beta-Integral +\label{buch:rekursion:gamma:subsection:integralbeweis}} In diesem Abschnitt wird das Beta-Integral eingeführt, eine Funktion von zwei Variablen, welches eine Integral-Definition mit einer reichaltigen Menge von Rekursionsbeziehungen hat, die sich direkt auf @@ -24,6 +32,7 @@ B(x,y) \int_0^1 t^{x-1} (1-t)^{y-1}\,dt \] für $\operatorname{Re}x>0$, $\operatorname{Re}y>0$. +\index{Beta-Integral}% \end{definition} Aus der Definition kann man sofort ablesen, dass $B(x,y)=B(y,x)$. @@ -225,6 +234,7 @@ Durch Einsetzen der Integralformel im Ausdruck Satz. \begin{satz} +\index{Satz!Beta-Funktion und Gamma-Funktion}% Die Beta-Funktion kann aus der Gamma-Funktion nach \begin{equation} B(x,y) = \frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)} @@ -233,6 +243,16 @@ B(x,y) = \frac{\Gamma(x)\Gamma(y)}{\Gamma(x+y)} berechnet werden. \end{satz} +% +% Info über die Beta-Verteilung +% +\input{chapters/040-rekursion/betaverteilung.tex} + +\subsection{Weitere Eigenschaften der Gamma-Funktion} +Die nahe Verwandtschaft der Gamma- mit der Beta-Funktion ermöglicht +nun, weitere Eigenschaften der Gamma-Funktion mit Hilfe der Beta-Funktion +herzuleiten. + \subsubsection{Nochmals der Wert von $\Gamma(\frac12)$?} Der Wert von $\Gamma(\frac12)=\sqrt{\pi}$ wurde bereits in \eqref{buch:rekursion:gamma:wert12} @@ -304,6 +324,9 @@ $(-\frac12)!$ als Wert \] der Gamma-Funktion interpretiert. +% +% Alternative Parametrisierung +% \subsubsection{Alternative Parametrisierungen} Die Substitution $t=\sin^2 s$ hat im vorangegangenen Abschnitt ermöglicht, $\Gamma(\frac12)$ zu ermitteln. @@ -366,8 +389,10 @@ wobei wir \] verwendet haben. Diese Darstellung des Beta-Integrals wird später -% XXX Ort ergänzen +in Satz~\ref{buch:funktionentheorie:satz:spiegelungsformel} dazu verwendet, die Spiegelungsformel für die Gamma-Funktion +\index{Gamma-Funktion!Spiegelungsformel}% +\index{Spiegelungsformel der Gamma-Funktion}% herzuleiten. Eine weitere mögliche Parametrisierung verwendet $t = (1+s)/2$ @@ -391,17 +416,23 @@ B(x,y) \label{buch:rekursion:gamma:beta:symm} \end{equation} +% +% +% \subsubsection{Die Verdoppelungsformel von Legendre} Die trigonometrische Substitution kann dazu verwendet werden, die Legendresche Verdoppelungsformel für die Gamma-Funktion herzuleiten. \begin{satz}[Legendre] +\index{Satz!Verdoppelungsformel@Verdoppelungsformel für $\Gamma(x)$}% \[ \Gamma(x)\Gamma(x+{\textstyle\frac12}) = 2^{1-2x}\sqrt{\pi} \Gamma(2x) \] +\index{Verdoppelungsformel}% +\index{Gamma-Funktion!Verdoppelungsformel von Legendre}% \end{satz} \begin{proof}[Beweis] @@ -484,83 +515,3 @@ Setzt man $x=\frac12$ in die Verdoppelungsformel ein, erhält man in Übereinstimmung mit dem aus \eqref{buch:rekursion:gamma:gamma12} bereits bekannten Wert. -\subsubsection{Beta-Funktion und Binomialkoeffizienten} -Die Binomialkoeffizienten können mit Hilfe der Fakultät als -\begin{align*} -\binom{n}{k} -&= -\frac{n!}{(n-k)!\,k!} -\intertext{geschrieben werden. -Drückt man die Fakultäten durch die Gamma-Funktion aus, erhält man} -&= -\frac{\Gamma(n+1)}{\Gamma(n-k+1)\Gamma(k+1)}. -\intertext{Schreibt man $x=k-1$ und $y=n-k+1$, wird daraus -wegen $x+y=k+1+n-k+1=n+2=(n+1)+1$} -&= -\frac{\Gamma(x+y-1)}{\Gamma(x)\Gamma(y)}. -\intertext{Die Rekursionsformel für die Gamma-Funktion erlaubt, -den Zähler umzuwandeln in $\Gamma(x+y-1)=\Gamma(x+y)/(x+y-1)$, so dass -der Binomialkoeffizient schliesslich} -&= -\frac{\Gamma(x+y)}{(x+y-1)\Gamma(x)\Gamma(y)} -= -\frac{1}{(n-1)B(n-k+1,k+1)} -\label{buch:rekursion:gamma:binombeta} -\end{align*} -geschrieben werden kann. -Die Rekursionsbeziehung -\[ -\binom{n+1}{k} = \binom{n}{k-1} + \binom{n}{k} -\] -der Binomialkoeffizienten erzeugt das vertraute Pascal-Dreieck, -die Formel \eqref{buch:rekursion:gamma:binombeta} für die -Binomialkoeffizienten macht daraus -\[ -\frac{n-1}{B(n-k,k-1)} -= -\frac{n-2}{B(n-k,k-2)} -+ -\frac{n-2}{B(n-k-1,k-1)}, -\] -die für ganzzahlige Argumente gilt. -Wir wollen nachrechnen, dass dies für beliebige Argumente gilt. -\begin{align*} -\frac{(n-1)\Gamma(n-1)}{\Gamma(n-k)\Gamma(k-1)} -&= -\frac{(n-2)\Gamma(n-2)}{\Gamma(n-k)\Gamma(k-2)} -+ -\frac{(n-2)\Gamma(n-2)}{\Gamma(n-k-1)\Gamma(k-1)} -\\ -\frac{\Gamma(n)}{\Gamma(n-k)\Gamma(k-1)} -&= -\frac{\Gamma(n-1)}{\Gamma(n-k)\Gamma(k-2)} -+ -\frac{\Gamma(n-1)}{\Gamma(n-k-1)\Gamma(k-1)} -\intertext{Durch Zusammenfassen der Faktoren im Zähler mit Hilfe -der Rekursionsformel für die Gamma-Funktion und Multiplizieren -mit dem gemeinsamen Nenner -$\Gamma(n-k)\Gamma(k-1)=(n-k-1)\Gamma(n-k-1)(k-2)\Gamma(k-2)$ wird daraus} -\Gamma(n) -&= -(k-2) -\Gamma(n-1) -+ -(n-k-1) -\Gamma(n-1) -\intertext{Indem wir die Rekursionsformel für die Gamma-Funktion auf -die rechte Seite anwenden können wir erreichen, dass in allen Termen -ein Faktor -$\Gamma(n-1)$ auftritt:} -(n-1)\Gamma(n-1) -&= -(k-2)\Gamma(n-1) -+ -(n+k-1)\Gamma(n-1) -\\ -n-1 -&= -k-2 -+ -n-k-1 -\end{align*} - diff --git a/buch/chapters/040-rekursion/betaverteilung.tex b/buch/chapters/040-rekursion/betaverteilung.tex new file mode 100644 index 0000000..77715ca --- /dev/null +++ b/buch/chapters/040-rekursion/betaverteilung.tex @@ -0,0 +1,487 @@ +% +% teil1.tex -- Beispiel-File für das Paper +% +% (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil +% +\subsection{Ordnungsstatistik und Beta-Funktion +\label{buch:rekursion:ordnung:section:ordnungsstatistik}} +\rhead{Ordnungsstatistik und Beta-Funktion} +In diesem Abschnitt ist $X$ eine Zufallsvariable mit der Verteilungsfunktion +$F_X(x)$, und $X_i$, $1\le i\le n$ sei ein Stichprobe von unabhängigen +Zufallsvariablen, die wie $X$ verteilt sind. +Ziel ist, die Verteilungsfunktion und die Wahrscheinlichkeitsdichte +des grössten, zweitgrössten, $k$-t-grössten Wertes in der Stichprobe +zu finden. +Wir schreiben $[n]=\{1,\dots,n\}$ für die Menge der natürlichen +Zahlen von zwischen $1$ und $n$. + +\subsubsection{Verteilung von $\operatorname{max}(X_1,\dots,X_n)$ und +$\operatorname{min}(X_1,\dots,X_n)$ +\label{buch:rekursion:ordnung:subsection:minmax}} +Die Verteilungsfunktion von $\operatorname{max}(X_1,\dots,X_n)$ hat +den Wert +\begin{align*} +F_{\operatorname{max}(X_1,\dots,X_n)}(x) +&= +P(\operatorname{max}(X_1,\dots,X_n) \le x) +\\ +&= +P(X_1\le x\wedge \dots \wedge X_n\le x) +\\ +&= +P(X_1\le x) \cdot \ldots \cdot P(X_n\le x) +\\ +&= +P(X\le x)^n += +F_X(x)^n. +\end{align*} +Für die Gleichverteilung ist +\[ +F_{\text{equi}}(x) += +\begin{cases} +0&\qquad x< 0 +\\ +x&\qquad 0\le x\le 1 +\\ +1&\qquad 1<x. +\end{cases} +\] +In diesem Fall ist Verteilung des Maximums +\[ +F_{\operatorname{max}(X_1,\dots,X_n)}(x) += +\begin{cases} +0&\qquad x<0\\ +x^n&\qquad 0\le x\le 1\\ +1&\qquad 1 < x. +\end{cases} +\] +Mit der zugehörigen Wahrscheinlichkeitsdichte +\[ +\varphi_{\operatorname{max}(X_1,\dots,X_n)} += +\frac{d}{dx} +F_{\operatorname{max}(X_1,\dots,X_n)}(x) += +\begin{cases} +nx^{n-1}&\qquad 0\le x\le 1\\ +0 &\qquad \text{sonst} +\end{cases} +\] +kann man zum Beispiel den Erwartungswert +\[ +E(\operatorname{max}(X_1,\dots,X_n)) += +\int_{-\infty}^\infty +x +\varphi_{\operatorname{X_1,\dots,X_n}}(x) +\,dx += +\int_{0}^1 x\cdot nx^{n-1}\,dt += +\biggl[ +\frac{n}{n+1}x^{n+1} +\biggr]_0^1 += +\frac{n}{n+1} +\] +berechnen. + +Ganz analog kann man auch die Verteilungsfunktion von +$\operatorname{min}(X_1,\dots,X_n)$ bestimmen. +Sie ist +\begin{align*} +F_{\operatorname{min}(X_1,\dots,X_n)}(x) +&= +P(x\le X_1\vee \dots \vee x\le X_n) +\\ +&= +1- +P(x > X_1\wedge \dots \wedge x > X_n) +\\ +&= +1- +(1-P(x\le X_1)) \cdot\ldots\cdot (1-P(x\le X_n)) +\\ +&= +1-(1-F_X(x))^n, +\end{align*} +Im Speziellen für im Intervall $[0,1]$ gleichverteilte $X_i$ ist die +Verteilungsfunktion des Minimums +\[ +F_{\operatorname{min}(X_1,\dots,X_n)}(x) += +\begin{cases} +0 &\qquad x<0 \\ +1-(1-x)^n&\qquad 0\le x\le 1\\ +1 &\qquad 1 < x +\end{cases} +\] +mit Wahrscheinlichkeitsdichte +\[ +\varphi_{\operatorname{min}(X_1,\dots,X_n)} += +\frac{d}{dx} +F_{\operatorname{min}(X_1,\dots,X_n)} += +\begin{cases} +n(1-x)^{n-1}&\qquad 0\le x\le 1\\ +0 &\qquad \text{sonst} +\end{cases} +\] +und Erwartungswert +\begin{align*} +E(\operatorname{min}(X_1,\dots,X_n) +&= +\int_{-\infty}^\infty x\varphi_{\operatorname{min}(X_1,\dots,X_n)}(x)\,dx += +\int_0^1 x\cdot n(1-x)^{n-1}\,dx +\\ +&= +\bigl[ -x(1-x)^n \bigr]_0^1 + \int_0^1 (1-x)^n\,dx += +\biggl[ +- +\frac{1}{n+1} +(1-x)^{n+1} +\biggr]_0^1 += +\frac{1}{n+1}. +\end{align*} +Es ergibt sich daraus als natürlich Verallgemeinerung die Frage nach +der Verteilung des zweitegrössten oder zweitkleinsten Wertes unter den +Werten $X_i$. + +\subsubsection{Der $k$-t-grösste Wert} +Sie wieder $X_i$ eine Stichprobe von $n$ unabhängigen wie $X$ verteilten +Zufallsvariablen. +Diese werden jetzt der Grösse nach sortiert, die sortierten Werte werden +mit +\[ +X_{1:n} \le X_{2:n} \le \dots \le X_{(n-1):n} \le X_{n:n} +\] +bezeichnet. +Die Grössen $X_{k:n}$ sind Zufallsvariablen, sie heissen die $k$-ten +Ordnungsstatistiken. +Die in Abschnitt~\ref{buch:rekursion:ordnung:subsection:minmax} behandelten Zufallsvariablen +$\operatorname{min}(X_1,\dots,X_n)$ +und +$\operatorname{max}(X_1,\dots,X_n)$ +sind die Fälle +\begin{align*} +X_{1:n} &= \operatorname{min}(X_1,\dots,X_n) \\ +X_{n:n} &= \operatorname{max}(X_1,\dots,X_n). +\end{align*} + +Um den Wert der Verteilungsfunktion von $X_{k:n}$ zu berechnen, müssen wir +die Wahrscheinlichkeit bestimmen, dass $k$ der $n$ Werte $X_i$ $x$ nicht +übersteigen. +Der $k$-te Wert $X_{k:n}$ übersteigt genau dann $x$ nicht, wenn +mindestens $k$ der Zufallswerte $X_i$ $x$ nicht übersteigen, also +\[ +P(X_{k:n} \le x) += +P\left( +|\{i\in[n]\,|\, X_i\le x\}| \ge k +\right). +\] + +Das Ereignis $\{X_i\le x\}$ ist eine Bernoulli-Experiment, welches mit +Wahrscheinlichkeit $F_X(x)$ eintritt. +Die Anzahl der Zufallsvariablen $X_i$, die $x$ übertreffen, ist also +Binomialverteilt mit $p=F_X(x)$. +Damit haben wir gefunden, dass mit Wahrscheinlichkeit +\begin{equation} +F_{X_{k:n}}(x) += +P(X_{k:n}\le x) += +\sum_{i=k}^n \binom{n}{i}F_X(x)^i (1-F_X(x))^{n-i} +\label{buch:rekursion:ordnung:eqn:FXkn} +\end{equation} +mindestens $k$ der Zufallsvariablen den Wert $x$ überschreiten. + +\subsubsection{Wahrscheinlichkeitsdichte der Ordnungsstatistik} +Die Wahrscheinlichkeitsdichte der Ordnungsstatistik kann durch Ableitung +von \eqref{buch:rekursion:ordnung:eqn:FXkn} gefunden, werden, sie ist +\begin{align*} +\varphi_{X_{k:n}}(x) +&= +\frac{d}{dx} +F_{X_{k:n}}(x) +\\ +&= +\sum_{i=k}^n +\binom{n}{i} +\bigl( +iF_X(x)^{i-1}\varphi_X(x) (1-F_X(x))^{n-i} +- +F_X(x)^k +(n-i) +(1-F_X(x))^{n-i-1} +\varphi_X(x) +\bigr) +\\ +&= +\sum_{i=k}^n +\binom{n}{i} +\varphi_X(x) +F_X(x)^{i-1}(1-F_X(x))^{n-i-1} +\bigl( +iF_X(x)-(n-i)(1-F_X(x)) +\bigr) +\\ +&= +\varphi_X(x) +\biggl( +\sum_{i=k}^n i\binom{n}{i} F_X(x)^{i-1}(1-F_X(x))^{n-i} +- +\sum_{j=k}^n (n-j)\binom{n}{j} F_X(x)^{j}(1-F_X(x))^{n-j-1} +\biggr) +\\ +&= +\varphi_X(x) +\biggl( +\sum_{i=k}^n i\binom{n}{i} F_X(x)^{i-1}(1-F_X(x))^{n-i} +- +\sum_{i=k+1}^{n+1} (n-i+1)\binom{n}{i-1} F_X(x)^{i-1}(1-F_X(x))^{n-i} +\biggr) +\\ +&= +\varphi_X(x) +\biggl( +k\binom{n}{k}F_X(x)^{k-1}(1-F_X(x))^{n-k} ++ +\sum_{i=k+1}^{n+1} +\left( +i\binom{n}{i} +- +(n-i+1)\binom{n}{i-1} +\right) +F_X(x)^{i-1}(1-F_X(x))^{n-i} +\biggr) +\end{align*} +Mit den wohlbekannten Identitäten für die Binomialkoeffizienten +\begin{align*} +i\binom{n}{i} +- +(n-i+1)\binom{n}{i-1} +&= +n\binom{n-1}{i-1} +- +n +\binom{n-1}{i-1} += +0 +\end{align*} +folgt jetzt +\begin{align*} +\varphi_{X_{k:n}}(x) +&= +\varphi_X(x)k\binom{n}{k} F_X(x)^{k-1}(1-F_X(x))^{n-k}. +\intertext{Im Speziellen für gleichverteilte Zufallsvariablen $X_i$ ist +} +\varphi_{X_{k:n}}(x) +&= +k\binom{n}{k} x^{k-1}(1-x)^{n-k}. +\end{align*} +Dies ist die Wahrscheinlichkeitsdichte einer Betaverteilung +\[ +\beta(k,n-k+1)(x) += +\frac{1}{B(k,n-k+1)} +x^{k-1}(1-x)^{n-k}. +\] +Tatsächlich ist die Normierungskonstante +\begin{align} +\frac{1}{B(k,n-k+1)} +&= +\frac{\Gamma(n+1)}{\Gamma(k)\Gamma(n-k+1)} += +\frac{n!}{(k-1)!(n-k)!}. +\label{buch:rekursion:ordnung:betaverteilung:normierung1} +\end{align} +Andererseits ist +\[ +k\binom{n}{k} += +k\frac{n!}{k!(n-k)!} += +\frac{n!}{(k-1)!(n-k)!}, +\] +in Übereinstimmung mit~\eqref{buch:rekursion:ordnung:betaverteilung:normierung1}. +Die Verteilungsfunktion und die Wahrscheinlichkeitsdichte der +Ordnungsstatistik sind in Abbildung~\ref{buch:rekursion:ordnung:fig:order} dargestellt. + +\begin{figure} +\centering +\includegraphics{chapters/040-rekursion/images/order.pdf} +\caption{Verteilungsfunktion und Wahrscheinlichkeitsdichte der +Ordnungsstatistiken $X_{k:n}$ einer gleichverteilung Zuvallsvariable +mit $n=10$. +\label{buch:rekursion:ordnung:fig:order}} +\end{figure} + +% +% Die Beta-Funktion +% +\subsection{Die Beta-Verteilung +\label{buch:rekursion:subsection:beta-verteilung}} +Die Wahrscheinlichkeitsdichte, die im +Abschnitt~\ref{buch:rekursion:ordnung:section:ordnungsstatistik} +gefunden worden ist, ist nicht nur für ganzzahlige Exponenten +definiert. + +\begin{figure} +\centering +\includegraphics[width=0.92\textwidth]{chapters/040-rekursion/images/beta.pdf} +\caption{Wahrscheinlichkeitsdichte der Beta-Verteilung +$\beta(a,b,x)$ +für verschiedene Werte der Parameter $a$ und $b$. +Die Werte des Parameters für einen Graphen einer Beta-Verteilung +sind im kleinen Quadrat rechts im Graphen +als Punkt mit der gleichen Farbe dargestellt. +\label{buch:rekursion:ordnung:fig:betaverteilungn}} +\end{figure} + +\begin{definition} +Die Beta-Verteilung ist die Verteilung mit der Wahrscheinlichkeitsdichte +\[ +\beta_{a,b}(x) += +\begin{cases} +\displaystyle +\frac{1}{B(a,b)} +x^{a-1}(1-x)^{b-1}&\qquad 0\le x \le 1\\ +0&\qquad\text{sonst.} +\end{cases} +\] +\end{definition} + +Die Beta-Funktion ist also die Normierungskonstante der Beta-Verteilung. +Die wichtigsten Kennzahlen der Beta-Verteilung wie Erwartungswert und +Varianz lassen sich alle ebenfalls als Werte der Beta-Funktion ausdrücken. + +\subsubsection{Erwartungswert} +Mit der Wahrscheinlichkeitsdichte kann man jetzt auch den Erwartungswerte +der $k$-ten Ordnungsstatistik bestimmen. +Die Rechnung ergibt: +\begin{align*} +E(X_{k:n}) +&= +\int_0^1 x\cdot k\binom{n}{k} x^{k-1}(1-x)^{n-k}\,dx += +k +\binom{n}{k} +\int_0^1 +x^{k}(1-x)^{n-k}\,dx. +\intertext{Dies ist das Beta-Integral} +&= +k\binom{n}{k} +B(k+1,n-k+1) +\intertext{welches man durch Gamma-Funktionen bzw.~durch Fakultäten wie in} +&= +k\frac{n!}{k!(n-k)!} +\frac{\Gamma(k+1)\Gamma(n-k+1)}{n+2} += +k\frac{n!}{k!(n-k)!} +\frac{k!(n-k)!}{(n+1)!} += +\frac{k}{n+1} +\end{align*} +ausdrücken kann. +Die Erwartungswerte haben also regelmässige Abstände, sie sind in +Abbildung~\ref{buch:rekursion:ordnung:fig:order} als blaue vertikale Linien eingezeichnet. + +Für die Beta-Verteilung lässt sich die Rechnung noch allgemeiner +durchführen. +Der Erwartungswert einer $\beta_{a,b}$-verteilten Zufallsvariablen $X$ +ist +\begin{align*} +E(X) +&= +\int_0^1 x \beta_{a,b}(x)\,dx += +\frac{1}{B(a,b)} +\int_0^1 x\cdot x^{a-1}(1-x)^{b-1}\,dx += +\frac{B(a+1,b)}{B(a,b)} += +\frac{a}{a+b}. +\end{align*} +Durch Einsetzen von $a=k+1$ und $b=n-k+1$ lassen sich die für die +Ordnungsstatistik berechneten Werte wiederfinden. + +\subsubsection{Varianz} +Auch die Varianz lässt sich einfach berechnen, dazu muss zunächst +der Erwartungswert von $X_{k:n}^2$ bestimmt werden. +Er ist +\begin{align*} +E(X_{k:n}^2) +&= +\int_0^1 x^2\cdot k\binom{n}{k} x^{k-1}(1-x)^{n-k}\,dx += +k +\binom{n}{k} +\int_0^1 +x^{k+1}(1-x)^{n-k}\,dx. +\intertext{Auch dies ist ein Beta-Integral, nämlich} +&= +k\binom{n}{k} +B(k+2,n-k+1) += +k\frac{n!}{k!(n-k)!} +\frac{(k+1)!(n-k)!}{(n+2)!} += +\frac{k(k+1)}{(n+1)(n+2)}. +\end{align*} +Die Varianz wird damit +\begin{align} +\operatorname{var}(X_{k:n}) +&= +E(X_{k:n}^2) - E(X_{k:n})^2 +\notag +\\ +& += +\frac{k(k+1)}{(n+1)(n+2)}-\frac{k^2}{(n+1)^2} += +\frac{k(k+1)(n+1)-k^2(n+2)}{(n+1)^2(n+2)} += +\frac{k(n-k+1)}{(n+1)^2(n+2)}. +\label{buch:rekursion:ordnung:eqn:ordnungsstatistik:varianz} +\end{align} +In Abbildung~\ref{buch:rekursion:ordnung:fig:order} ist die Varianz der +Ordnungsstatistik $X_{k:n}$ für $k=7$ und $n=10$ als oranges +Rechteck dargestellt. + +Auch die Varianz kann ganz allgemein für die Beta-Verteilung +bestimmt werden. +Dazu berechnen wir zunächst +\begin{align*} +E(X^2) +&= +\frac{1}{B(a,b)} +\int_0^1 +x^2\cdot x^{a-1}(1-y)^{b-1}\,dx += +\frac{B(a+2,b)}{B(a,b)}. +\end{align*} +Daraus folgt dann +\[ +\operatorname{var}(X) += +E(X^2)-E(X)^2 += +\frac{B(a+2,b)B(a,b)-B(a+1,b)^2}{B(a,b)^2}. +\] + +Die Formel~\eqref{buch:rekursion:ordnung:eqn:ordnungsstatistik:varianz} +besagt auch, dass die Varianz der proportional ist zu $k((n+1)-k)$. +Dieser Ausdruck ist am grössten für $k=(n+1)/2$, die Varianz ist +also grösser für die ``mittleren'' Ordnungstatistiken als für die +extremen $X_{1:n}=\operatorname{min}(X_1,\dots,X_n)$ und +$X_{n:n}=\operatorname{max}(X_1,\dots,X_n)$. + diff --git a/buch/chapters/040-rekursion/bohrmollerup.tex b/buch/chapters/040-rekursion/bohrmollerup.tex new file mode 100644 index 0000000..57e503a --- /dev/null +++ b/buch/chapters/040-rekursion/bohrmollerup.tex @@ -0,0 +1,213 @@ +% +% bohrmollerup.tex +% +% (c) 2022 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\subsection{Der Satz von Bohr-Mollerup +\label{buch:rekursion:subsection:bohr-mollerup}} +\begin{figure} +\centering +\includegraphics{chapters/040-rekursion/images/loggammaplot.pdf} +\caption{Der Graph der Funktion $\log|\Gamma(x)|$ ist für $x>0$ konvex. +Die blau hinterlegten Bereiche zeigen an, wo die Gamma-Funktion +negative Werte annimmt. +\label{buch:rekursion:gamma:loggammaplot}} +\end{figure} +Die Integralformel und die Grenzwertdefinition für die Gamma-Funktion +zeigen beide, dass das Problem der Ausdehnung der Fakultät zu einer +Funktion $\mathbb{C}\to\mathbb{C}$ eine Lösung hat, aber es ist noch +nicht klar, in welchem Sinn dies die einzig mögliche Lösung ist. +Der Satz von Bohr-Mollerup gibt darauf eine Antwort. + +Der Graph +in Abbildung~\ref{buch:rekursion:gamma:loggammaplot} +zeigt, dass die Werte der Gamma-Funktion für $x>0$ so schnell +anwachsen, dass sogar die Funktion $\log|\Gamma(x)|$ konvex ist. +Der Satz von Bohr-Mollerup besagt, dass diese Eigenschaft zur +Charakterisierung der Gamma-Funktion verwendet werden kann. + +\begin{satz} +\label{buch:satz:bohr-mollerup} +Eine Funktion $f\colon \mathbb{R}^+\to\mathbb{R}$ mit den Eigenschaften +\begin{enumerate}[i)] +\item $f(1)=1$, +\item $f(x+1)=xf(x)$ für alle $x\in\mathbb{R}^+$ und +\item die Funktion $\log f(t)$ ist konvex +\end{enumerate} +ist die Gamma-Funktion: $f(t)=\Gamma(t)$. +\index{Satz!von Bohr-Mollerup}% +\index{Bohr-Mollerup, Satz von}% +\end{satz} + +Für den Beweis verwenden wir die folgende Eigenschaft einer konvexen +Funktion $g(x)$. +Sei +\begin{equation} +S(y,x) = \frac{g(y)-g(x)}{y-x} +\qquad\text{für $y-x$} +\end{equation} +die Steigung der Sekante zwischen den Punkten $(x,g(x))$ und $(y,g(y))$ +des Graphen von $g$. +Da $g$ konvex ist, ist $S(y,x)$ eine monoton wachsende Funktion +der beiden Variablen $x$ und $y$, solange $y>x$. + +\begin{proof}[Beweis] +Wir halten zunächst fest, dass die Bedingungen i) und ii) zur Folge haben, +dass $f(n+1)=n!$ ist für alle positiven natürlichen Zahlen. +Für die Steigung einer Sekante der Funktion $g(x)=\log f(x)$ kann damit +für natürliche Argumente bereits berechnet werden, es ist +\[ +S(n,n+1) += +\frac{\log n! - \log (n-1)!}{n+1-n} += +\frac{\log n + \log (n-1)! - \log(n-1)!}{1} += +\log n +\] +und entsprechend auch $S(n-1,n) = \log(n-1)$. + +\begin{figure} +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\draw (-6,0) -- (6,0); + +\node at (-5,0) [above] {$n-1\mathstrut$}; +\node at (0,0) [above] {$n\mathstrut$}; +\node at (3,0) [above] {$n+x\mathstrut$}; +\node at (5,0) [above] {$n+1\mathstrut$}; + +\node[color=blue] at (-5,-2.3) {$S(n-1,n)\mathstrut$}; +\node[color=red] at (-1.666,-2.3) {$S(n-1,n+x)\mathstrut$}; +\node[color=darkgreen] at (1.666,-2.3) {$S(n,n+x)\mathstrut$}; +\node[color=orange] at (5,-2.3) {$S(n,n+1)\mathstrut$}; + +\node at (-3.333,-2.3) {$<\mathstrut$}; +\node at (0,-2.3) {$<\mathstrut$}; +\node at (3.333,-2.3) {$<\mathstrut$}; + +\draw[color=blue] (-5,0) -- (-5,-2) -- (0,0); +\draw[color=red] (-5,0) -- (-1.666,-2) -- (3,0); +\draw[color=darkgreen] (0,0) -- (1.666,-2) -- (3,0); +\draw[color=orange] (0,0) -- (5,-2) -- (5,0); + +\fill (-5,0) circle[radius=0.08]; +\fill (0,0) circle[radius=0.08]; +\fill (3,0) circle[radius=0.08]; +\fill (5,0) circle[radius=0.08]; + +\draw[double,color=blue] (-5,-2.5) -- (-5,-3.0); +\draw[double,color=orange] (5,-2.5) -- (5,-3.0); + +\node[color=blue] at (-5,-3.3) {$\log (n-1)\mathstrut$}; +\node[color=orange] at (5,-3.3) {$\log (n)\mathstrut$}; + +\end{tikzpicture} +\end{center} +\caption{Für den Beweis des Satzes von Bohr-Mollerup wird die +Sekantensteigung $S(x,y)$ für die Argumente $n-1$, $n$, $n+x$ und $n+1$ +verwendet. +\label{buch:rekursion:fig:bohr-mollerup}} +\end{figure} +Wir wenden jetzt die eben erwähnte Tatsache, dass $S(x,y)$ monoton +wachsend ist, auf die Punkte $n-1$, $n$, $n+x$ und $n+1$ wie +in Abbildung~\ref{buch:rekursion:fig:bohr-mollerup} an, wobei +$0<x<1$ ist. + +Die linke Ungleichung in Abbildung~\ref{buch:rekursion:fig:bohr-mollerup} +ist +\begin{align} +\log(n-1) +&< +S(n-1,n+x) += +\frac{\log f(n+x) -\log(n-2)!}{n+x-n+1} +\notag +\\ +(x+1)\log(n-1) + \log(n-2)! +&< \log f(n+x), +\notag +\\ +x\log(n-1) + \log(n-1)! +&< \log f(n+x) +\label{buch:rekursion:bohr-mollerup:eqn1} +\intertext{sie schätzt $\log f(n+x)$ nach unten ab. +Die Exponentialfunktion ist monoton wachsen, wendet man sie auf +\eqref{buch:rekursion:bohr-mollerup:eqn1} an, erhält man} +(n-1)^x (n-1)! +&< +f(n+x). +\label{buch:rekursion:bohr-mollerup:ungllinks} +\end{align} +Ganz ähnlich folgt aus der Ungleichung rechts in +Abbildung~\ref{buch:rekursion:fig:bohr-mollerup} +\begin{align} +\frac{\log f(n+x)-\log (n-1)!}{n+x-n} +&< \log n +\notag +\\ +\log f(n+x) - \log(n-1)! +&< +x \log n +\notag +\\ +\log f(n+x) +&< +x\log n + \log(n-1)! +\notag +\intertext{und nach Anwendung der Exponentialfunktion} +f(n+x) +&< +n^x (n-1)! +\label{buch:rekursion:bohr-mollerup:unglrechts} +\end{align} +Die Funktion $f(n+x)$ können wir jetzt mit der Funktionalgleichung ii) +durch $f(x)$ ausdrücken: +\begin{align*} +f(n+x) +&= +(x+n-1)f(n+x-1) +\\ +&= +(x+n-1)(x+n-2)f(n+x-2) +\\ +&\vdots +\\ +&= +(x+n-1)(x+n-2)\dots x\,f(x) += +(x)_n f(x). +\end{align*} +Zusammen mit den Ungleichungen +\eqref{buch:rekursion:bohr-mollerup:ungllinks} +und +\eqref{buch:rekursion:bohr-mollerup:unglrechts} +erhalten wir +\begin{align*} +(n-1)^x (n-1)! +&< +(x)_n f(x) +< +n^x (n-1)! +\intertext{oder nach Division durch $(x)_n$} +%\underbrace{ +\frac{(n-1)^x (n-1)!}{(x)_n} +%}_{\displaystyle\to \Gamma(x)} +&< f(x) +< +\frac{n^x (n-1)!}{(x)_n} += +%\underbrace{ +\frac{n^x n!}{(x)_{n+1}} +%}_{\displaystyle\to \Gamma(x)} +\cdot +%\underbrace{ +\frac{x+n}{n} +%}_{\displaystyle\to 1} +. +\end{align*} +Der Ausdruck ganz links und der erste Bruch rechts konvergieren +für $n\to\infty$ beide gegen $\Gamma(x)$ und der Bruch ganz rechts +konvergiert gegen $1$. +Daher muss auch $f(x)=\Gamma(x)$ sein. +\end{proof} diff --git a/buch/chapters/040-rekursion/chapter.tex b/buch/chapters/040-rekursion/chapter.tex index 165c48e..1771200 100644 --- a/buch/chapters/040-rekursion/chapter.tex +++ b/buch/chapters/040-rekursion/chapter.tex @@ -8,6 +8,25 @@ \label{buch:chapter:rekursion}} \lhead{Spezielle Funktionen und Rekursion} \rhead{} +Die Fakultät $n!=1\cdot 2\cdots n$ ist eine ersten Funktionen, für die +man normalerweise auch eine rekursive Definition kennenlernt. +Rekursion ist eine besonders gut der numerischen Berechnung zugängliche +Art, spezielle Funktionen zu definieren. +In diesem Kapitel sollen daher in +Abschnitt~\ref{buch:rekursion:section:gamma} +zunächst die Gamma-Funktion als Verallgemeinerung konstruiert +und charakterisiert werden. +Die Beta-Funktion in +Abschnitt~\ref{buch:rekursion:gamma:section:beta} +verallgemeinert diese Rekursionsbeziehungen. +Abschnitt~\ref{buch:rekursion:section:linear} +erinnert an die Methoden, mit denen lineare Rekursionsgleichungen +gelöst werden können. +Erfüllten die Koeffizienten einer Potenzreihe eine spezielle +Rekursionsbeziehung, entsteht die besonders vielfältige Familie +der hypergeometrischen Funktionen, die in +Abschnitt~\ref{buch:rekursion:section:hypergeometrische-funktion} +eingeführt werden. \input{chapters/040-rekursion/gamma.tex} \input{chapters/040-rekursion/beta.tex} diff --git a/buch/chapters/040-rekursion/gamma.tex b/buch/chapters/040-rekursion/gamma.tex index 737cf7f..7f19637 100644 --- a/buch/chapters/040-rekursion/gamma.tex +++ b/buch/chapters/040-rekursion/gamma.tex @@ -20,6 +20,8 @@ für alle natürlichen Zahlen $x\in\mathbb{N}$ definiert werden. \end{equation} Kann man eine reelle oder komplexe Funktion finden, die die Funktionalgleichung~\eqref{buch:rekursion:eqn:gammadef} +\index{Gamma-Funktion!Funktionalgleichung}% +\index{Funktionalgleichung der Gamma-Funktion}% erfüllt und damit die Fakultät auf beliebige Argumente ausdehnt? \subsection{Definition als Grenzwert} @@ -71,6 +73,9 @@ gilt. Der Plan ist, dies so umzuformen, dass man für $x$ eine beliebige komplexe Zahl einsetzen kann. +% +% Pochhammer-Symbol +% \subsubsection{Pochhammer-Symbol} Die spezielle Form des Nenners und des zweiten Faktors im Zähler von \eqref{buch:rekursion:gamma:eqn:fakultaet} @@ -113,6 +118,9 @@ x! Der erste Faktor in diesem Ausdruck enthält jetzt nur noch Dinge, die für beliebige $x\in\mathbb{C}$ definiert sind. +% +% Grenwertdefinition +% \subsubsection{Grenzwertdefinition} Der zweite Bruch in \eqref{buch:rekursion:gamma:eqn:produkt3} besteht aus Termen, die zwar nur für natürliches $x$ definiert sind, @@ -141,8 +149,13 @@ $x\in\mathbb{C}\setminus\{0,-1,-2,-3,\dots\}$ ist der Grenzwert \[ \Gamma(x) = \lim_{n\to\infty} \frac{n!\,n^{x-1}}{(x)_n}. \] +\index{Grenzwertdefinition der Gamma-Funktion}% +\index{Gamma-Funktion!Grenzwertdefinition}% \end{definition} +% +% Rekursionsgleichung für Gamma(x) +% \subsubsection{Rekursionsgleichung für $\Gamma(x)$} Es ist aus der Herleitung klar, dass $\Gamma(n)=(n-1)!$ sein muss. Wir sollten dies aber auch direkt aus der @@ -195,15 +208,85 @@ x\lim_{n\to\infty} \frac{n^{x-1}}{(n+1)^{x-1}} \\ &= +x \Gamma(x) \lim_{n\to\infty} \biggl(\frac{n}{n+1}\biggr)^{x-1} = -\Gamma(x), +x\Gamma(x), \end{align*} Weil $n/(n+1)\to 1$ ist und die Funktion $z\mapsto z^{x-1}$ für alle nach der Definition zulässigen Werte von $x$ eine stetige Funktion ist. +% +% Gamma-Funktion und Pochhammer-Symbol +% +\subsubsection{Gamma-Funktion und Pochhammer-Symbol} +Durch Iteration der Rekursionsformel für $\Gamma(x)$ folgt jetzt +\begin{align*} +\Gamma(x+n) +&= +(x+n-1) \Gamma(x+n-1) +\\ +&= +(x+n-1)(x+n-2)\Gamma(x+n-2) +\\ +&= +\underbrace{ +(x+n-1)(x+n-2)\cdots(x-1)(x) +}_{\text{$n$ Faktoren}} \Gamma(x) +\\ +&=(x)_n \Gamma(x). +\end{align*} +Damit folgt + +\begin{satz} +\index{Satz!Pochhammer-Symbol@Pochhammer-Symbol und $\Gamma(x)$}% +\label{buch:rekursion:gamma:satz:gamma-pochhammer} +Die Rekursionsformel für die Gamma-Funktion kann geschrieben werden als +\[ +\Gamma(x+n) = (x)_n \Gamma(x). +\] +Das Pochhammer-Symbol $(x)_n$ ist für alle natürlichen $n$ gegeben durch +\[ +(x)_n = \frac{\Gamma(x+n)}{\Gamma(x)}. +\] +\end{satz} + +% +% Numerische Unzulänglichkeit der Grenzwertdefinition +% \subsubsection{Numerische Unzulänglichkeiten der Grenzwertdefinition} +\begin{table} +\centering +%\renewcommand{\arraystretch}{1.1} +\begin{tabular}{|>{$}c<{$}|>{$}r<{$}|>{$}l<{$}|>{$}l<{$}|} +\hline +\log_{10} n& n&n!n^{x-1}/(x)_n\mathstrut & \text{Fehler% +\vrule height12pt depth6pt width0pt} \\ +\hline +\text{\vrule height12pt depth0pt width0pt} + 1& 10&1.\underline{7}947392559855804&0.0222854050800643\\ + 2& 100&1.\underline{77}46707942830697&0.0022169433775536\\ + 3& 1000&1.\underline{772}6754214755178&0.0002215705700017\\ + 4& 10000&1.\underline{7724}760067171375&0.0000221558116213\\ + 5& 100000&1.\underline{77245}60664742375&0.0000022155687214\\ + 6& 1000000&1.\underline{77245}40724623101&0.0000002215567940\\ + 7& 10000000&1.\underline{7724538}730613721&0.0000000221558560\\ + 8& 100000000&1.\underline{77245385}31233258&0.0000000022178097\\ + 9& 1000000000&1.\underline{77245385}11320680&0.0000000002265519\\ + 10& 10000000000&1.\underline{772453850}9261316&0.0000000000206155\\ + 11&100000000000&1.\underline{77245385}14549788&0.0000000005494627\\ + & \infty&1.\underline{7724538509055161}& +\text{\vrule height12pt depth6pt width0pt} \\ +\hline +\end{tabular} +\caption{Numerische Berechnung mit der Grenzwertdefinition +und rekursiver Berechnung von $n!/(x)_n$ mit Hilfe der Folge +\eqref{buch:rekursion:gamma:pnfolge}. +Die Konvergenz ist sehr langsam, die Anzahl korrekter Stellen +wächst logarithmisch mit $n$. +\label{buch:rekursion:gamma:produktberechnung}} +\end{table} Die Grenzwertdefinition~\ref{buch:rekursion:gamma:def:definition} ist zwar zweifellos richtig, kann aber nicht für die numerische Berechnung der Gamma-Funktion verwendet werden. @@ -237,6 +320,24 @@ ist. Die Approximation mit Hilfe der Grenzwertdefinition kann also grundsätzlich nicht mehr als zwei korrekte Nachkommastellen liefern. +Den Quotienten $n!/(x)_n$ kann man mit Hilfe der Rekursionsformel +\begin{equation} +p_n = p_{n-1}\cdot \frac{n}{x+n-1},\qquad +p_0 = 0 +\label{buch:rekursion:gamma:pnfolge} +\end{equation} +etwas effizienter berechnen. +Insbesondere umgeht man damit das Problem, dass $n!$ den Wertebereich +des \texttt{double} Datentyps sprengt. +Der Wert der Gamma-Funktion kann dann durch $p_nn^{x-1}$ approximiert +werden. +Die Tabelle~\ref{buch:rekursion:gamma:produktberechnung} fasst die +Resultate zusammen und zeigt, dass die Konvergenz logarithmisch ist: +die Anzahl korrekter Nachkommastellen ist $\log_{10}n$. + +% +% Produktformel +% \subsection{Produktformel} Ein möglicher Ausweg aus den numerischen Schwierigkeiten mit der Grenzwertdefinition ist, den schnell wachsenden Faktor $n!$ @@ -244,6 +345,7 @@ in den Zähler zu bringen, so dass er der Konvergenz etwas nachhilft. Wir berechnen daher den Kehrwert $1/\Gamma(x)$. \begin{satz} +\index{Satz!Produktformel@Produktformel für $\Gamma(x)$}% \label{buch:rekursion:gamma:satz:produktformel} Der Kehrwert der Gamma-Funktion kann geschrieben werden als \begin{equation} @@ -253,8 +355,10 @@ xe^{\gamma x} \prod_{k=1}^\infty \biggl(1+\frac{x}k\biggr)\,e^{-\frac{x}{k}}, \label{buch:rekursion:gamma:eqn:produktformel} +\index{Gamma-Funktion!Produktformel}% \end{equation} wobei $\gamma$ die Euler-Mascheronische Konstante +\index{Euler-Mascheronische Konstante}% \[ \gamma = @@ -262,6 +366,8 @@ wobei $\gamma$ die Euler-Mascheronische Konstante \biggl(\sum_{k=1}^n\frac{1}{k}-\log n\biggr) \] ist. +\index{Gamma-Funktion!Produktformel}% +\index{Produktformel für die Gamma-Funkion}% \end{satz} \begin{proof}[Beweis] @@ -368,16 +474,20 @@ vollständig bewiesen. \begin{table} \centering -\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|} +\begin{tabular}{|>{$}c<{$}|>{$}r<{$}|>{$}c<{$}|>{$}c<{$}|} \hline -k & \Gamma(\frac12,n) & \Gamma(\frac12) - \Gamma(\frac12,n) \\ +k & n & \Gamma(\frac12,n) & \Gamma(\frac12) - \Gamma(\frac12,n)% +\text{\vrule height12pt depth6pt width0pt} \\ \hline -1 & 1.\underline{7}518166478 & -0.0206372031 \\ -2 & 1.\underline{77}02543372 & -0.0021995137 \\ -3 & 1.\underline{772}2324556 & -0.0002213953 \\ -4 & 1.\underline{7724}316968 & -0.0000221541 \\ -5 & 1.\underline{77245}16354 & -0.0000022156 \\ -6 & 1.\underline{772453}6293 & -0.0000002216 \\ +\text{\vrule height12pt depth0pt width0pt} + 1& 10& 1.\underline{7}518166478& -0.0206372031 \\ + 2& 100& 1.\underline{77}02543372& -0.0021995137 \\ + 3& 1000& 1.\underline{772}2324556& -0.0002213953 \\ + 4& 10000& 1.\underline{7724}316968& -0.0000221541 \\ + 5& 100000& 1.\underline{77245}16354& -0.0000022156 \\ + 6&1000000& 1.\underline{772453}6293& -0.0000002216 \\ +\infty& & 1.\underline{7724538509}& +\text{\vrule height12pt depth6pt width0pt} \\ \hline \end{tabular} \caption{Werte $\Gamma(\frac12,n)$ von $\Gamma(\frac12)$ berechnet mit @@ -385,6 +495,9 @@ $n=10^k$ Faktoren der Produktformel~\eqref{buch:rekursion:gamma:eqn:produktformel} und der zugehörige Fehler. Die korrekten Nachkommastellen sind unterstrichen. +Die Konvergenz ist genau gleich langsam wie in der Berechnung mit +Hilfe der Grenzwert-Definition in +Tabelle~\ref{buch:rekursion:gamma:produktberechnung}. \label{buch:rekursion:gamma:gammatabelle}} \end{table} @@ -422,6 +535,8 @@ z \mapsto \Gamma(z) = \int_0^\infty t^{z-1}e^{-t}\,dt \] +\index{Gamma-Funktion!Integraldefinition}% +\index{Integraldefinition der Gamma-Funktion}% \end{definition} Man beachte, dass das Integral für $x=0$ nicht definiert ist, eine @@ -436,6 +551,9 @@ die richtigen Werte für natürliche Argumente hat, es wird aber auch gezeigt, dass dies nicht ausreicht um zu schliessen, dass die Integralformel mit der früher definierten Gamma-Funktion übereinstimmt. +% +% Funktionalgleichung für die Integraldefinition +% \subsubsection{Funktionalgleichung für die Integraldefinition} Tatsächlich ist es einfach nachzuprüfen, dass die Funktionalgleichung der Gamma-Funktion auch für die Definition~\ref{buch:rekursion:def:gamma} @@ -480,8 +598,8 @@ ganzzahlige Argumente übereinstimmen. Der folgende Abschnitt macht deutlich, dass es sehr viele Funktionen gibt, die ebenfalls die Funktionalgleichung erfüllen. Eine vollständige Rechtfertigung für diese Definition wird später -in Abschnitt~\ref{buch:rekursion:gamma:subsection:beta} -\eqref{buch:rekursion:gamma:integralbeweis} +in Abschnitt~\ref{buch:rekursion:gamma:subsection:integralbeweis} +in Formel~\eqref{buch:rekursion:gamma:integralbeweis} auf Seite~\pageref{buch:rekursion:gamma:integralbeweis} gegeben. @@ -494,9 +612,13 @@ die Werte der Fakultät annimmt. \label{buch:rekursion:fig:gamma}} \end{figure} +% +% Der Wert Gamma(1/2) +% \subsubsection{Der Wert $\Gamma(\frac12)$} Die Integraldarstellung kann dazu verwendet werden, $\Gamma(\frac12)$ zu berechnen. +\index{Gamma-Funktion!WertGamma12@Wert von $\Gamma(\frac12)$}% Dazu verwendet man die Substition $t=s^2$ in der Integraldefinition der Gamma-Funktion und berechnen \begin{align} @@ -511,12 +633,16 @@ der Gamma-Funktion und berechnen \int_{-\infty}^\infty e^{-s^2}\,ds = \sqrt{\pi}. -\label{buch:rekursion:gamma:betagamma} +\label{buch:rekursion:gamma:wert12} \end{align} Der Integrand im letzten Integral ist die Wahrscheinlichkeitsdichte einer Normalverteilung, deren Integral wohlbekannt ist. -\subsubsection{Alternative Lösungen} +% +% Alternative Lösungen +% +\subsubsection{Alternative Lösungen der +Funktionalgleichung~\ref{buch:rekursion:eqn:gammadef}} Die Funktion $\Gamma(z)$ ist nicht die einzige Funktion, die natürlichen Zahlen die Werte $\Gamma(n+1) = n!$ der Fakultät annimmt. Indem man eine beliebige Funktion $f(z)$ addiert, die auf alle @@ -547,6 +673,8 @@ Von Wielandt stammt das folgende, noch etwas speziellere Resultat, welches hier nicht bewiesen wird. \begin{satz}[Wielandt] +\index{Satz!von Wielandt}% +\index{Wielandt, Satz von}% Ist $f(z)$ eine für $\operatorname{Re}z>0$ definiert Funktion mit den folgenden drei Eigenschaften \begin{enumerate} @@ -560,11 +688,16 @@ Dann ist $ f(z) = \Gamma(z) $. % XXX Gamma in the interval (1,2) %Man beachte, dass +% +% Laplace-Transformierte der Potenzfunktion +% \subsubsection{Laplace-Transformierte der Potenzfunktion} Die Integraldarstellung der Gamma-Funktion erlaubt jetzt auch, die Laplace-Transformation der Potenzfunktion zu berechnen. +\index{Laplace-Transformierte der Potenzfunktion}% \begin{satz} +\index{Satz!Laplace-Transformierte der Potenzfunktion}% Die Laplace-Transformierte der Potenzfunktion $f(t)=t^\alpha$ ist \[ (\mathscr{L}f)(s) @@ -594,7 +727,11 @@ Durch die Substitution $st = u$ oder $t=\frac{u}{s}$ wird daraus \] \end{proof} +% +% Pol erster Ordnung bei z=0 +% \subsubsection{Pol erster Ordnung bei $z=0$} +\index{Gamma-Funktion!Pol@Pol bei $z=0$}% Wir haben zu prüfen, dass sowohl der Wert $\Gamma(1)$ korrekt ist als auch die Rekursionsformel~\eqref{buch:rekursion:eqn:gammadef} gilt. Der Wert für $z=1$ ist @@ -644,15 +781,23 @@ Daraus ergibt sich für $\Gamma(z)$ der Ausdruck \] Die Gamma-Funktion hat daher an der Stelle $z=0$ einen Pol erster Ordnung. +% +% Ausdehnung auf Re(z) < 0 +% \subsubsection{Ausdehnung auf $\operatorname{Re}z<0$} +\index{Gamma-Funktion!analytische Fortsetzung}% +\index{analytische Fortsetzung der Gamma-Funktion}% Die Integralformel konvergiert nicht für $\operatorname{Re}z\le 0$. Durch analytische Fortsetzung, wie sie im Abschnitt~\ref{buch:funktionentheorie:section:fortsetzung} beschrieben wird, kann die Funktion auf ganz $\mathbb{C}$ ausgedehnt werden, mit Ausnahme einzelner Pole. Die Funktionalgleichung gilt natürlich für alle $z\in\mathbb{C}$, -für die $\Gamma(z)$ definiert ist. -In einer Umgebung von $z=-n$ gilt +für die $\Gamma(z)$ definiert ist, nicht nur für diejenigen $z$, für +die das Integral konvergiert. +Wir können Sie daher verwenden, um das Argument in den Bereich +zu bringen, wo das Integral zur Berechnung verwendet werden kann. +Dazu berechnen wir \[ \Gamma(z) = @@ -665,29 +810,44 @@ In einer Umgebung von $z=-n$ gilt \dots = \frac{\Gamma(z+n)}{z(z+1)(z+2)\cdots(z+n-1)} += +\frac{\Gamma(z+n)}{(z)_n}. \] -Keiner der Faktoren im Nenner verschwindet in der Nähe von $z=-n$, der -Zähler hat aber einen Pol erster Ordnung an dieser Stelle. -Daher hat auch der Quotient einen Pol erster Ordnung. -Abbildung~\ref{buch:rekursion:fig:gamma} zeigt die Pole bei den -nicht negativen ganzen Zahlen. +Dies gilt für jedes natürlich $n$. +Für $n$ gross genug, genauer für +$n\ge |\operatorname{Re}z|$, +ist $\operatorname{Re}(z+n)=\operatorname{Re}z + n>0$ und damit +kann $\Gamma(z+n)$ mit der Integralformel berechnet werden. + +Die Gamma-Funktion hat keine Nullstellen, aber in der Nähe von $z=-n$ +hat der Nenner eine Nullstelle erster Ordnung. +Somit hat $\Gamma(z)$ Pole erster Ordnung bei den negativen +ganzen Zahlen und bei $0$, wie sie in +Abbildung~\ref{buch:rekursion:fig:gamma} gezeigt werden. +% +% Numerische Berechnung +% \subsubsection{Numerische Berechnung} \begin{table} \centering -\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|} +\begin{tabular}{|>{$}c<{$}|>{$}r<{$}|>{$}c<{$}>{$}c<{$}|} \hline -k & y(10^k) & y(10^k) - \Gamma(\frac{5}{2}) \\ +k & n=10^k & y(n) & y(n) - \Gamma(\frac{5}{3}) +\text{\vrule height12pt depth6pt width0pt} \\ \hline -1 & 0.0000000000 & -0.9027452930 \\ -2 & 0.3319129461 & -0.5708323468 \\ -3 & 0.\underline{902}5209490 & -0.0002243440 \\ -4 & 0.\underline{902745}1207 & -0.0000001723 \\ -5 & 0.\underline{902745}0962 & -0.0000001968 \\ -6 & 0.\underline{902745}0962 & -0.0000001968 \\ +\text{\vrule height12pt depth0pt width0pt} +1 & 10 & 0.0000000000 & -0.9027452930 \\ +2 & 100 & 0.3319129461 & -0.5708323468 \\ +3 & 1000 & 0.\underline{902}5209490 & -0.0002243440 \\ +4 & 10000 & 0.\underline{902745}1207 & -0.0000001723 \\ +5 & 100000 & 0.\underline{902745}0962 & -0.0000001968 \\ +6 & 1000000 & 0.\underline{902745}0962 & -0.0000001968 \\ + & \infty & 0.\underline{9027452929} & +\text{\vrule height12pt depth6pt width0pt} \\ \hline \end{tabular} -\caption{Resultate der Berechnung von $\Gamma(\frac{5}{2})$ mit Hilfe +\caption{Resultate der Berechnung von $\Gamma(\frac{5}{3})$ mit Hilfe der Differentialgleichung \eqref{buch:rekursion:gamma:eqn:gammadgl}. Die korrekten Stellen sind unterstrichen. Es sind immerhin sechs korrekte Stellen gefunden, wobei nur 337 @@ -697,21 +857,28 @@ Auswertungen des Integranden notwendig waren. Im Prinzip könnte die Integraldefinition der numerischen Berechnung entgegenkommen. Um diese Hypothese zu prüfen, berechnen wir das Integral für -$z=\frac52$ mit Hilfe der äquivalenten Differentialgleichungen +$z=\frac53$ mit Hilfe der äquivalenten Differentialgleichungen \begin{equation} \dot{y}(t) = t^{z-1}e^{-t} -\qquad\text{mit Anfangsbedingung $y(0)=0$}. +\qquad +\text{mit Anfangsbedingung $y(0)=0$}. \label{buch:rekursion:gamma:eqn:gammadgl} \end{equation} +\index{Gamma-Funktion!Loesung@Lösung mit Differentialgleichung} Der gesuchte Wert ist der Grenzwert $\lim_{t\to\infty} y(t)$. In der Tabelle~\ref{buch:rekursion:gamma:table:gammaintegral} sind die Werte von $y(10^k)$ sowie die Differenzen -$y(10^k) - \Gamma(\frac{5}{2})$ zusammengefasst. +$y(10^k) - \Gamma(\frac{5}{3})$ zusammengefasst. Die Genauigkeit erreicht sechs korrekte Nachkommastellen mit nur 337 Auswertungen des Integranden. +Eine noch wesentlich effizientere Auswertung des $\Gamma$-Integrals +mit Hilfe der Gauss-Laguerre-Quadratur wird in Kapitel~\ref{chapter:laguerre} +von Patrick Müller dargestellt. % % % +\input{chapters/040-rekursion/bohrmollerup.tex} +\input{chapters/040-rekursion/integral.tex} diff --git a/buch/chapters/040-rekursion/gammalimit/Makefile b/buch/chapters/040-rekursion/gammalimit/Makefile new file mode 100644 index 0000000..0804e74 --- /dev/null +++ b/buch/chapters/040-rekursion/gammalimit/Makefile @@ -0,0 +1,11 @@ +# +# Makefile -- build gamma limit test programm +# +# (c) 2022 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +l: l.cpp + g++ -O2 -g -Wall `pkg-config --cflags gsl` `pkg-config --libs gsl` \ + -o l l.cpp + +test: l + ./l diff --git a/buch/chapters/040-rekursion/gammalimit/l.cpp b/buch/chapters/040-rekursion/gammalimit/l.cpp new file mode 100644 index 0000000..7a86800 --- /dev/null +++ b/buch/chapters/040-rekursion/gammalimit/l.cpp @@ -0,0 +1,26 @@ +/* + * l.cpp + * + * (c) 2022 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule + */ +#include <cstdlib> +#include <cmath> +#include <cstdio> + +int main(int argc, char *argv[]) { + double x = 0.5; + double g = tgamma(x); + printf("limit: %20.16f\n", g); + double p = 1; + long long N = 100000000000; + long long n = 10; + for (long long k = 1; k <= N; k++) { + p = p * k / (x + k - 1); + if (0 == k % n) { + double gval = p * pow(k, x-1); + printf("%12ld %20.16f %20.16f\n", k, gval, gval - g); + n = n * 10; + } + } + return EXIT_SUCCESS; +} diff --git a/buch/chapters/040-rekursion/gammalimit/l.m b/buch/chapters/040-rekursion/gammalimit/l.m new file mode 100644 index 0000000..32b6442 --- /dev/null +++ b/buch/chapters/040-rekursion/gammalimit/l.m @@ -0,0 +1,19 @@ +# +# l.m -- Berechnung der Gamma-Funktion +# +# (c) 2022 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +global N; +N = 10000; + +function retval = gamma(x, n) + p = 1; + for k = (1:n) + p = p * k / (x + k - 1); + end + retval = p * n^(x-1); +endfunction + +for n = (100:100:N) + printf("Gamma(%4d) = %10f\n", n, gamma(0.5, n)); +end diff --git a/buch/chapters/040-rekursion/hypergeometrisch.tex b/buch/chapters/040-rekursion/hypergeometrisch.tex index d92e594..13ba3b2 100644 --- a/buch/chapters/040-rekursion/hypergeometrisch.tex +++ b/buch/chapters/040-rekursion/hypergeometrisch.tex @@ -16,22 +16,38 @@ n^3S_{n} mit Anfangswerten $S_0=1$ und $S_1=8$ angeben? Dies scheint auf den ersten Blick unmöglich kompliziert, man kann aber zeigen, dass -\[ +\begin{equation} S_n = \sum_{k=0}^n \binom{2n-2k}{n-k}^2 \binom{2k}{k}^2 -\] +\label{buch:rekursion:hypergeometrisch:eqn:Sn} +\end{equation} gilt (\cite[p.~xi]{buch:ab}). Die Lösung ist also eine Summe von Summanden, die sehr viel einfacher aussehen und vor allem die besondere Eigenschaft haben, dass die -Quotienten aufeinanderfolgender Terme rationale Funktionen von von $k$ +Quotienten aufeinanderfolgender Terme rationale Funktionen von $k$ sind. -% XXX Quotient berechnen -Eine besonders simple solche Funktion ist die geometrische Reihe, die -im Abschnitt~\ref{buch:rekursion:hypergeometrisch:geometrisch} -in Erinnerung gerufen wird. +\begin{definition} +Ein Folge heisst {\em hypergeometrisch}, wenn der Quotient aufeinanderfolgender +\index{hypergeometrische Folge}% +\index{Folge, hypergeometrisch}% +Terme eine rationale Funktion des Folgenindex ist. +\end{definition} + +Die Terme der Reihenentwicklungen aller bisher behandelten speziellen +Funktionen waren hypergeometrisch. +Im aktuellen Abschnitt soll daher die Klasse der sogenannten +hypergeometrischen Funktionen untersucht werden, die durch diese +Eigenschaft charakterisiert sind. + +In Abschnitt~\ref{buch:rekursion:hypergeometrisch:binomialkoeffizienten} +wird klar, dass Folgen, deren Terme aus Fakultäten und Binomialkoeffizienten +immer hypergeometrisch sind. +Die Untersuchung der geometrischen Reihe in +Abschnitt~\ref{buch:rekursion:hypergeometrisch:geometrisch} +motiviert die Namensgebung. Abschnitt~\ref{buch:rekursion:hypergeometrisch:reihen} definiert den Begriff der hypergeometrischen Reihe und zeigt, wie sie in eine Standardform gebracht werden können. @@ -39,22 +55,101 @@ In Abschnitt~\ref{buch:rekursion:hypergeometrisch:beispiele} schliesslich wird an Hand von Beispielen gezeigt, wie bekannte Funktionen als hypergeometrische Funktionen interpretiert werden können. +% +% Quotienten von Binomialkoeffizienten +% +\subsection{Quotienten von Binomialkoeffizienten +\label{buch:rekursion:hypergeometrisch:binomialkoeffizienten}} +Aufeinanderfolgende Terme der Summe +\eqref{buch:rekursion:hypergeometrisch:eqn:Sn} +sollen als Quotienten eine rationale Funktion haben. +Dies ist eine allgemeine Eigenschaft von Folgen, die durch Fakultäten +oder Binomialkoeffizienten definiert sind, wie die beiden folgenden +Sätze zeigen. + +\begin{satz} +\index{Satz!Quotienten von Fakultäten}% +\label{buch:rekursion:hypergeometrisch:satz:fakquo} +Der Quotient aufeinanderfolgender Folgenglieder +der Folge $c_k=(a+bk)!$ ist der ein Polynom vom Grad $b$. +\end{satz} +\begin{proof}[Beweis] +\begin{align*} +\frac{c_{k+1}}{c_k} +&= +\frac{(a+b(k+1))!}{(a+bk)!} += +\frac{(a+bk+b)!}{(a+b)!} +\\ +&= +(a+bk+1)(a+bk+2)\cdots(a+bk+b) += +(a+bk+1)_b +\end{align*} +Das Pochhammer-Symbol hat $b$ Faktoren, es ist ein Polynom vom Grad $b$. +\end{proof} + +\begin{satz} +\index{Satz!Quotienten von Binomialkoeffizienten}% +\label{buch:rekursion:hypergeometrisch:satz:binomquo} +Die Quotienten aufeinanderfolgender Werte der Binomialkoeffizienten +\[ +f_k += +\binom{a+bk}{c+dk} +\] +ist eine rationale Funktion von $k$ mit Zähler- und Nennergrad $b$. +\end{satz} + +\begin{proof}[Beweis] +Indem man die Binomialkoeffizienten mit Fakultäten als +\[ +\binom{a+bk}{c+dk} += +\frac{(a+bk)!}{(c+dk)!(a-c+(b-d)k)!} +\] +ausschreibt, findet man mit +Satz~\ref{buch:rekursion:hypergeometrisch:satz:fakquo} +für die Quotienten +\begin{align} +\frac{f_{k+1}}{f_k} +&= +\frac{(a+bk+1)_b}{(c+dk+1)_d\cdot(a-c+(b-d)k+1)_{b-d}} +\label{buch:rekursion:eqn:binomquotient} +\end{align} +Die Pochhammer-Symbole sind Polynome vom Grad $b$, $d$ bzw.~$b-d$. +Insbesondere ist auch das Nenner-Polynom vom Grad $d+(b-d)=b$. +\end{proof} + +Aus den Sätzen~\ref{buch:rekursion:hypergeometrisch:satz:fakquo} +und +\ref{buch:rekursion:hypergeometrisch:satz:binomquo} +folgt jetzt sofort, dass auch der Quotient aufeinanderfolgender +Summanden der Summe~\eqref{buch:rekursion:hypergeometrisch:eqn:Sn} +eine rationale Funktion von $k$ ist. + +% +% Die geometrische Reihe +% \subsection{Die geometrische Reihe \label{buch:rekursion:hypergeometrisch:geometrisch}} -Die besonders einfache Potenzreihe +Die Reihe \[ f(q) = \sum_{k=0}^\infty aq^k \] -heisst die {\em geometrische Reihe}. +heisst die {\em geometrische Reihe} ist besonders einfache +Reihe mit einer hypergeometrischen Folge von Termen. +\index{geometrische Reihe}% +\index{Reihe!geometrische}% Die Partialsummen \[ S_n = \sum_{k=0}^n aq^k \] -kann mit der Differenz +können aus der Differenz \begin{equation} (1-q)S_n = @@ -75,8 +170,7 @@ a\frac{1-q^{n+1}}{1-q} \label{buch:rekursion:hypergeometrisch:eqn:geomsumme} \end{equation} auflösen kann. - -Fü $q<1$ geht $q^n\to 0$ und damit konvergiert +Für $q<1$ geht $q^n\to 0$ und damit konvergiert $S_n$ gegen \[ \sum_{k=0}^\infty aq^k @@ -97,6 +191,9 @@ Die Berechnung der Summe in beruht darauf, dass die Multiplikation mit $q$ einen ``anderen'' Teil der Summe ergibt, der sich in der Differenze weghebt. +% +% Hypergeometrische Reihen +% \subsection{Hypergeometrische Reihen \label{buch:rekursion:hypergeometrisch:reihen}} Es ist plausibel, dass eine etwas lockerere Bedingung an die @@ -105,11 +202,15 @@ ermöglichen wird, interessante Aussagen über die durch die Reihe beschriebenen Funktionen zu machen. \begin{definition} -Eine Reihe +\label{buch:rekursion:hypergeometrisch:def:allg} +Eine durch die Reihe \[ f(x) = \sum_{k=0}^\infty a_k x^k \] -heisst {\em hypergeometrisch}, wenn der Quotient aufeinanderfolgender +definierte Funktion $f(x)$ heisst {\em hypergeometrisch}, +wenn der Quotient aufeinanderfolgender +\index{hypergeometrisch} +\index{Reihe!hypergeometrisch} Koeffizienten eine rationale Funktion von $k$ ist, wenn also \[ @@ -120,9 +221,13 @@ wenn also mit Polynomen $p(k)$ und $q(k)$ ist. \end{definition} +% +% Beispiele von hypergeometrischen Funktionen +% +\subsubsection{Beispiele von hypergeometrischen Funktionen} Die geometrische Reihe ist natürlich eine hypergeometrische Reihe, wobei $p(k)/q(k)=1$ ist. -Etwas interessanter ist die Exponentialfunktion, durch die Taylor-Reihe +Etwas interessanter ist die Exponentialfunktion, die durch die Taylor-Reihe \[ e^x = \sum_{k=0}^\infty \frac{x^k}{k!} \] @@ -165,7 +270,30 @@ eine rationale Funktion mit Zählergrad $0$ und Nennergrad $2$. Es gibt also eine hypergeometrische Reihe $f(z)$ derart, dass $\cos x = f(x^2)$ ist. -Seien $p(k)$ und $q(k)$ zwei Polynome derart, dass +% +% Die hypergeometrischen Funktione pFq +% +\subsubsection{Die hypergeometrischen Funktionen $\mathstrut_pF_q$} +Die Definition~\ref{buch:rekursion:hypergeometrisch:def:allg} +einer hypergeometrischen Funktion wie auch die Verschiedenartigkeit +der Beispiele kännen den Eindruck vermitteln, dass die diese Klasse +von Funktionen unübersichtlich gross sein könnte. +Dem ist jedoch nicht so. +In diesem Abschnitt soll gezeigt werden, dass alle hypergeometrischen +Funktionen durch die in +Definition~\ref{buch:rekursion:hypergeometrisch:def} definierten +Funktionen $\mathstrut_pF_q$ ausgedrückt werden. +Die hypergeometrischen Funktionen können also vollständig parametrisiert +werden. + +Zu diesem Zweick sie +\[ +f(x) += +\sum_{k=0}^\infty a_kx^k +\] +eine hypergeometrische Funktion und +seien $p(k)$ und $q(k)$ zwei Polynome derart, dass \[ \frac{a_{k+1}}{a_k} = \frac{p(k)}{q(k)}. \] @@ -201,12 +329,12 @@ Dazu nehmen wir an, dass $a_i$, $i=1,\dots,n$ die Nullstellen von $p(k)$ sind und $b_j$, $j=1,\dots,m$ die Nullstellen von $q(k)$, dass man also die Polynome als \begin{align*} -p(k) &= x(k-a_1)(k-a_2)\cdots(k-a_n) +p(k) &= s(k-a_1)(k-a_2)\cdots(k-a_n) \\ q(k) &= (k-b_1)(k-b_2)\cdots(k-b_m) \end{align*} schreiben kann. -Der Faktor $x$ ist nötig, weil die Polynome $p(k)$ und $q(k)$ nicht +Der Faktor $s$ ist nötig, weil die Polynome $p(k)$ und $q(k)$ nicht notwendigerweise normiert sind. Um das Produkt der Quotienten zu vereinfachen, nehmen wir für den Moment @@ -216,14 +344,14 @@ Dann ist nach \[ a_{k} = -x^{k} +s^{k} \frac{ (k-1-a_1) \cdots (2-a_1)(1-a_1)(0-a_1) }{ (k-1-b_1) \cdots (2-b_1)(1-b_1)(0-b_1) } = -\frac{(-a_1)_k}{(-b_1)_k} x^k. +\frac{(-a_1)_k}{(-b_1)_k} s^k. \] Die Koeffizienten können daher als Quotienten von Pochhammer-Symbolen geschrieben werden. @@ -233,13 +361,16 @@ von der Form a_k = \frac{(-a_1)_k(-a_2)_k\cdots (-a_n)_k}{(-b_1)_k(-b_2)_k\cdots(-b_m)_k} -x^ka_0. +s^ka_0. \] -Jede hypergeometrische Reihe kann daher in der Form +Jede hypergeometrische Funktion kann daher in der Form \[ +f(x) += a_0 \sum_{k=0}^\infty \frac{(-a_1)_k(-a_2)_k\cdots (-a_n)_k}{(-b_1)_k(-b_2)_k\cdots(-b_m)_k} +s^k x^k \] geschrieben werden. @@ -273,9 +404,10 @@ zusätzlichen Faktor $(1)_k$ im Zähler des Bruchs von Pochhammer-Symbolen kompensieren, wodurch sich der Grad $p$ des Zählers natürlich um $1$ erhöht. -Die oben analysierte Summe $S$ kann mit der Definition als +Die oben analysierte Summe für $f(x)$ kann mit der +Definition~\ref{buch:rekursion:hypergeometrisch:def} als \[ -S +f(x) = a_0 \cdot @@ -283,11 +415,75 @@ a_0 \begin{matrix} -a_1,-a_2,\dots,-a_n,1\\ -b_1,-b_2,\dots,-a_m -\end{matrix}; x +\end{matrix}; sx \biggr) \] beschrieben werden. +% +% Elementare Rechenregeln +% +\subsubsection{Elementare Rechenregeln} +Die Funktionen $\mathstrut_pF_q$ sind nicht alle unabhängig. +In Abschnitt~\ref{buch:rekursion:hypergeometrisch:stammableitung} +wird gezeigt werden, dass Ableitung und Stammfunktion einer hypergeometrischen +Funktion durch Manipulation der Parameter $a_k$ und $b_k$ bestimmt werden +können. +Viel einfacher sind jedoch die folgenden, aus +Definition~\ref{buch:rekursion:hypergeometrisch:def} +offensichtlichen Regeln: + +\begin{satz}[Permutationsregel] +\index{Satz!Permutationsregel für hypergeometrische Funktionen}% +\label{buch:rekursion:hypergeometrisch:satz:permuationsregel} +Sei $\pi$ eine beliebige Permutation der Zahlen $1,\dots,p$ und $\sigma$ eine +beliebige Permutation der Zahlen $1,\dots,q$, dann ist +\begin{equation} +\mathstrut_pF_q\biggl( +\begin{matrix} +a_1,\dots,a_p\\b_1,\dots,a_q +\end{matrix} +;x +\biggr) += +\mathstrut_pF_q\biggl( +\begin{matrix} +a_{\pi(1)},\dots,a_{\pi(p)}\\b_{\sigma(1)},\dots,b_{\sigma(q)} +\end{matrix} +;x +\biggr). +\label{buch:rekursion:hypergeometrisch:eqn:permuationsregel} +\end{equation} +\end{satz} + +\begin{satz}[Kürzungsformel] +\index{Satz!Kürzungsformel für hypergeometrische Funktionen}% +\label{buch:rekursion:hypergeometrisch:satz:kuerzungsregel} +Stimmt einer der Koeffizienten $a_k$ mit einem der Koeffizienten $b_i$ +überein, dann können sie weggelassen werden: +\begin{equation} +\mathstrut_{p+1}F_{q+1}\biggl( +\begin{matrix} +c,a_1,\dots,a_p\\ +c,b_1,\dots,b_q +\end{matrix}; +x +\biggr) += +\mathstrut_{p}F_{q}\biggl( +\begin{matrix} +a_1,\dots,a_p\\ +b_1,\dots,b_q +\end{matrix}; +x +\biggr). +\label{buch:rekursion:hypergeometrisch:eqn:kuerzungsregel} +\end{equation} +\end{satz} + +% +% Beispiele von hypergeometrischen Funktionen +% \subsection{Beispiele von hypergeometrischen Funktionen \label{buch:rekursion:hypergeometrisch:beispiele}} Viele der bekannten Reihenentwicklungen häufig verwendeter Funktionen @@ -295,6 +491,9 @@ lassen sich durch die hypergeometrischen Funktionen von Definition~\ref{buch:rekursion:hypergeometrisch:def} ausdrücken. In diesem Abschnitt werden einige Beispiel dazu gegeben. +% +% Die geometrische Reihe +% \subsubsection{Die geometrische Reihe} In der geometrischen Reihe fehlt der Nenner $k!$, es braucht daher einen Term $(1)_k$ im Zähler, um den Nenner zu kompensieren. @@ -312,6 +511,9 @@ a\sum_{k=0}^\infty a\cdot\mathstrut_1F_0(1,x). \] +% +% Die Exponentialfunktion +% \subsubsection{Exponentialfunktion} Die Exponentialfunktion ist die Reihe \[ @@ -323,7 +525,10 @@ benötigt, es ist daher e^x = \mathstrut_0F_0(x). \] -\subsubsection{Wurzelfunktion} +% +% Wurzelfunktionen +% +\subsubsection{Wurzelfunktionen} Die Wurzelfunktion $x\mapsto \sqrt{x}$ hat keine Taylor-Entwicklung in $x=0$, aber die Funktion $x\mapsto\sqrt{1+x}$ hat die Taylor-Reihe \[ @@ -412,11 +617,33 @@ Die Wurzelfunktion ist daher die hypergeometrische Funktion \sqrt{1\pm x} = \sum_{k=0}^\infty -\biggl(-\frac12\biggr)_k \frac{(-x)^k}{k!} +\biggl(-\frac12\biggr)_k \frac{(\pm x)^k}{k!} = \mathstrut_1F_0(-{\textstyle\frac12};\mp x). \] +Mit der Newtonschen Binomialreihe, die in +Abschnitt~\ref{buch:differentialgleichungen:subsection:newtonschereihe} +hergleitet wird, +kann man ganz analog jede beliebige Wurzelfunktion +\begin{align*} +(1+x)^\alpha +&= +1+\alpha x + \frac{\alpha(\alpha-1)}{2!}x^2 + \frac{\alpha(\alpha-1)(\alpha-2)}{3!}x^3+\dots +%\\ +%& += +\sum_{k=0}^\infty \frac{(-\alpha)_k}{k!}x^k += +\mathstrut_1F_0\biggl(\begin{matrix}-\alpha\\\text{---}\end{matrix};-x\biggr) +\end{align*} +durch $\mathstrut_1F_0$ ausdrücken. +Dieses Resultat ist der Inhalt von +Satz~\ref{buch:differentialgleichungen:satz:newtonschereihe} + +% +% Logarithmusfunktion +% \subsubsection{Logarithmusfunktion} Für $x\in (-1,1)$ konvergiert die Taylor-Reihe \[ @@ -483,8 +710,11 @@ x\cdot \mathstrut_2F_1\biggl(\begin{matrix}1,1\\2\end{matrix};-x\biggr). \] - +% +% Trigonometrische Funktionen +% \subsubsection{Trigonometrische Funktionen} +\index{trigonometrische Funktionen!als hypergeometrische Funktionen}% Die Kosinus-Funktion wurde bereits als hypergeometrische Funktion erkannt, im Folgenden soll dies auch noch für die Sinus-Funktion durchgeführt werden. @@ -509,7 +739,7 @@ x f(-x^2). Die Funktion $f(z)$ soll jetzt als hypergeometrische Funktion geschrieben werden. Dazu muss zunächst wieder der Nenner $k!$ wiederhergestellt werden: -\[ +\begin{equation*} f(z) = 1 @@ -521,7 +751,7 @@ f(z) \frac{3!}{7!}\cdot \frac{z^3}{3!} + \dots -\] +\end{equation*} Die Koeffizienten $k!/(2k+1)!$ müssen jetzt durch Pochhammer-Symbole mit jeweils $k$ Faktoren ausgedrückt werden. Dazu muss die Fakultät $(2k+1)!$ in zwei Produkte @@ -561,15 +791,27 @@ müssen wird mit $2^{2k}$ kompensieren: (1)_k\cdot \biggl(\frac{3}{2}\biggr)_k \end{align*} Setzt man dies in die Reihe ein, wird -\[ +\begin{equation} f(z) = \sum_{k=0}^\infty \frac{(1)_k}{(1)_k\cdot (\frac{3}{2})_k\cdot 4^k} z^k = -\mathstrut_1F_2\biggl(1;1,\frac{3}{2};\frac{z}4\biggr). -\] +\mathstrut_1F_2\biggl( +\begin{matrix}1\\1,\frac{3}{2}\end{matrix};\frac{z}4 +\biggr) += +\mathstrut_0F_1\biggl( +\begin{matrix}\text{---}\\\frac{3}{2}\end{matrix};\frac{z}4 +\biggr). +\label{buch:rekursion:hyperbolisch:eqn:hilfsfunktionf} +\end{equation} +Im letzten Schritt wurde die Kürzungsregel +\eqref{buch:rekursion:hypergeometrisch:eqn:kuerzungsregel} +von +Satz~\ref{buch:rekursion:hypergeometrisch:satz:kuerzungsregel} +angewendet. Damit lässt sich die Sinus-Funktion als \begin{equation} \sin x @@ -585,28 +827,35 @@ x\cdot\mathstrut_0F_1\biggl( \end{equation} durch eine hypergeometrische Funktion ausdrücken. +% +% Hyperbolische Funktionen +% \subsubsection{Hyperbolische Funktionen} +\index{hyperbolische Funktionen!als hypergeometrische Funktionen}% Die für die Sinus-Funktion angewendete Methode lässt sich auch auf die Funktion \begin{align*} \sinh x &= \sum_{k=0}^\infty \frac{x^{2k+1}}{(2k+1)!} -\\ -&= +%\\ +%& += x \, \biggl( 1+\frac{x^2}{3!} + \frac{x^4}{5!}+\frac{x^6}{7!}+\dots \biggr) -\\ +\intertext{Die Reihe in der Klammer lässt sich mit der Funktion +$f$ von \eqref{buch:rekursion:hyperbolisch:eqn:hilfsfunktionf} +schreiben als} &= -xf(-x^2) -= -x\,\mathstrut_1F_2\biggl( -\begin{matrix}1\\1,\frac{3}{2}\end{matrix} -;\frac{x^2}{4} -\biggr) +x\,f(-x^2) +%= +%x\cdot\mathstrut_1F_2\biggl( +%\begin{matrix}1\\1,\frac{3}{2}\end{matrix} +%;\frac{x^2}{4} +%\biggr) = x\cdot\mathstrut_0F_1\biggl( \begin{matrix}\text{---}\\\frac{3}{2}\end{matrix} @@ -618,18 +867,85 @@ ist diese Darstellung identisch mit der von $\sin x$. Dies illustriert die Rolle der hypergeometrischen Funktionen als ``grosse Vereinheitlichung'' der bekannten speziellen Funktionen. +% +% Tschebyscheff-Polynome +% \subsubsection{Tschebyscheff-Polynome} +\index{Tschebyscheff-Polynome}% +Man kann zeigen, dass auch die Tschebyscheff-Polynome sich durch die +hypergeometrischen Funktionen +\begin{equation} +T_n(x) += +\mathstrut_2F_1\biggl( +\begin{matrix}-n,n\\\frac12\end{matrix} +; +\frac12(1-x) +\biggr) +\label{buch:rekursion:hypergeometrisch:tschebyscheff2f1} +\end{equation} +ausdrücken lassen. +Beweisen kann man diese Beziehung zum Beispiel mit Hilfe der +Differentialgleichungen, denen die Funktionen genügen. +Diese Methode wird in +Abschnitt~\ref{buch:differentialgleichungen:section:hypergeometrisch} +von Kapitel~\ref{buch:chapter:differential} vorgestellt. + +Die Tschebyscheff-Polynome sind nicht die einzigen Familien von Polynomen, +\index{Tschebyscheff-Polynome!als hypergeometrische Funktion} +die sich durch $\mathstrut_pF_q$ ausdrücken lassen. +Für die zahlreichen Familien von orthogonalen Polynomen, die in +Kapitel~\ref{buch:chapter:orthogonalitaet} untersucht werden, +trifft dies auch zu. +Ein Funktion +\[ +\mathstrut_pF_q +\biggl( +\begin{matrix} +a_1,\dots,a_p\\ +b_1,\dots,b_q +\end{matrix} +;z +\biggr) +\] +ist genau dann ein Polynom, wenn mindestens einer der Parameter +$a_k$ eine negative ganze Zahl ist. +Der Grad des Polynoms ist der kleinste Betrag der negativ ganzzahligen +Werte unter den Parametern $a_k$. + +% +% Die Funktionen 0F1 +% +\subsubsection{Die Funktionen $\mathstrut_0F_1$} +\begin{figure} +\centering +\includegraphics{chapters/040-rekursion/images/0f1.pdf} +\caption{Graphen der Funktionen $\mathstrut_0F_1(;\alpha;x)$ für +verschiedene Werte von $\alpha$. +\label{buch:rekursion:hypergeometrisch:0f1}} +\end{figure} +Die Funktionen $\mathstrut_0F_1$ sind in den Beispielen mit der +beschränkten trigonometrischen Funktion $\sin x$ und mit der +exponentiell unbeschränkten Funktion $\sinh x$ mit dem gleichen +Wert des Parameters und nur einem Wechsel des Vorzeichens des +Arguments verbunden worden. +Die Graphen der Funktionen $\mathstrut_0F_1$, die in +Abbildung~\ref{buch:rekursion:hypergeometrisch:0f1} dargestellt sind, +machen dieses Verhalten plausibel. +Es wird sich später zeigen, dass $\mathstrut_0F_1$ auch mit den Bessel- +und den Airy-Funktionen verwandt sind. -TODO -\url{https://en.wikipedia.org/wiki/Chebyshev_polynomials} % % Ableitung und Stammfunktion % -\subsection{Ableitung und Stammfunktion hypergeometrischer Funktionen} +\subsection{Ableitung und Stammfunktion hypergeometrischer Funktionen +\label{buch:rekursion:hypergeometrisch:stammableitung}} Sowohl Ableitung wie auch Stammfunktion einer hypergeometrischen Funktion lässt sich immer durch hypergeometrische Reihen ausdrücken. - +% +% Ableitung +% \subsubsection{Ableitung} Wir gehen aus von der Funktion \begin{equation} @@ -743,7 +1059,7 @@ Damit kann jetzt die Kosinus-Funktion als \frac{1}{(\frac12)_k} \frac{1}{k!}\biggl(\frac{-x^2}{4}\biggr)^k = -\mathstrut_0F_1\biggl(;\frac12;-\frac{x^2}4\biggr) +\mathstrut_0F_1\biggl(\begin{matrix}\text{---}\\\frac12\end{matrix};-\frac{x^2}4\biggr) \end{align*} geschrieben werden kann. @@ -752,16 +1068,22 @@ Die Ableitung der Kosinus-Funktion ist daher \frac{d}{dx} \cos x &= \frac{d}{dx} -\mathstrut_0F_1\biggl(;\frac12;-\frac{x^2}4\biggr) +\mathstrut_0F_1\biggl( +\begin{matrix}\text{---}\\\frac12\end{matrix};-\frac{x^2}4 +\biggr) = \frac{1}{\frac12} \, -\mathstrut_0F_1\biggl(;\frac32;-\frac{x^2}4\biggr) +\mathstrut_0F_1\biggl( +\begin{matrix}\text{---}\\\frac32\end{matrix};-\frac{x^2}4 +\biggr) \cdot\biggl(-\frac{x}2\biggr) = -x \cdot -\mathstrut_0F_1\biggl(;\frac32;-\frac{x^2}4\biggr) +\mathstrut_0F_1\biggl( +\begin{matrix}\text{---}\\\frac32\end{matrix};-\frac{x^2}4 +\biggr) \intertext{Dies stimmt mit der in \eqref{buch:rekursion:hypergeometrisch:eqn:sinhyper} gefundenen Darstellung der Sinusfunktion mit Hilfe der hypergeometrischen @@ -771,6 +1093,9 @@ Funktion $\mathstrut_0F_1$ überein, es ist also wie erwartet} \end{align*} \end{beispiel} +% +% Stammfunktion +% \subsubsection{Stammfunktion} Eine Stammfunktion kann man auf die gleiche Art und Weise wie die Ableitung finden. diff --git a/buch/chapters/040-rekursion/images/0f1.cpp b/buch/chapters/040-rekursion/images/0f1.cpp new file mode 100644 index 0000000..24ca3f1 --- /dev/null +++ b/buch/chapters/040-rekursion/images/0f1.cpp @@ -0,0 +1,94 @@ +/* + * 0f1.cpp + * + * (c) 2022 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule + */ +#include <cstring> +#include <cstdio> +#include <cstdlib> +#include <cmath> +#include <string> +#include <iostream> +#include <fstream> + +static int N = 100; +static double xmin = -50; +static double xmax = 30; +static int points = 200; + +double f(double b, double x) { + double s = 1; + double p = 1; + for (int k = 1; k < N; k++) { + p = p * x / (k * (b + k - 1.)); + s += p; + } + return s; +} + +typedef std::pair<double, double> point_t; + +point_t F(double b, double x) { + return std::make_pair(x, f(b, x)); +} + +std::string ff(double f) { + if (f > 1000) { f = 1000; } + if (f < -1000) { f = -1000; } + char b[128]; + snprintf(b, sizeof(b), "%.4f", f); + return std::string(b); +} + +std::ostream& operator<<(std::ostream& out, const point_t& p) { + char b[128]; + out << "({" << ff(p.first) << "*\\dx},{" << ff(p.second) << "*\\dy})"; + return out; +} + +void curve(std::ostream& out, double b, const std::string& name) { + double h = (xmax - xmin) / points; + out << "\\def\\kurve" << name << "{"; + out << std::endl << "\t" << F(b, xmin); + for (int i = 1; i <= points; i++) { + double x = xmin + h * i; + out << std::endl << "\t-- " << F(b, x); + } + out << std::endl; + out << "}" << std::endl; +} + +int main(int argc, char *argv[]) { + std::ofstream out("0f1data.tex"); + + double s = 13/(xmax-xmin); + out << "\\def\\dx{" << ff(s) << "}" << std::endl; + out << "\\def\\dy{" << ff(s) << "}" << std::endl; + out << "\\def\\xmin{" << ff(s * xmin) << "}" << std::endl; + out << "\\def\\xmax{" << ff(s * xmax) << "}" << std::endl; + + curve(out, 0.5, "one"); + curve(out, 1.5, "two"); + curve(out, 2.5, "three"); + curve(out, 3.5, "four"); + curve(out, 4.5, "five"); + curve(out, 5.5, "six"); + curve(out, 6.5, "seven"); + curve(out, 7.5, "eight"); + curve(out, 8.5, "nine"); + curve(out, 9.5, "ten"); + + curve(out,-0.5, "none"); + curve(out,-1.5, "ntwo"); + curve(out,-2.5, "nthree"); + curve(out,-3.5, "nfour"); + curve(out,-4.5, "nfive"); + curve(out,-5.5, "nsix"); + curve(out,-6.5, "nseven"); + curve(out,-7.5, "neight"); + curve(out,-8.5, "nnine"); + curve(out,-9.5, "nten"); + + out.close(); + return EXIT_SUCCESS; +} diff --git a/buch/chapters/040-rekursion/images/0f1.pdf b/buch/chapters/040-rekursion/images/0f1.pdf Binary files differnew file mode 100644 index 0000000..2c35813 --- /dev/null +++ b/buch/chapters/040-rekursion/images/0f1.pdf diff --git a/buch/chapters/040-rekursion/images/0f1.tex b/buch/chapters/040-rekursion/images/0f1.tex new file mode 100644 index 0000000..1bc8b87 --- /dev/null +++ b/buch/chapters/040-rekursion/images/0f1.tex @@ -0,0 +1,86 @@ +% +% 0f1.tex -- template for standalon tikz images +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\input{0f1data.tex} +\definecolor{darkgreen}{rgb}{0,0.6,0} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\begin{scope} +\clip (\xmin,-1) rectangle (\xmax,5); +\draw[color=blue!5!red,line width=1.4pt] \kurveone; +\draw[color=blue!16!red,line width=1.4pt] \kurvetwo; +\draw[color=blue!26!red,line width=1.4pt] \kurvethree; +\draw[color=blue!37!red,line width=1.4pt] \kurvefour; +\draw[color=blue!47!red,line width=1.4pt] \kurvefive; +\draw[color=blue!57!red,line width=1.4pt] \kurvesix; +\draw[color=blue!68!red,line width=1.4pt] \kurveseven; +\draw[color=blue!78!red,line width=1.4pt] \kurveeight; +\draw[color=blue!89!red,line width=1.4pt] \kurvenine; +\draw[color=blue!100!red,line width=1.4pt] \kurveten; +\def\ds{0.4} +\begin{scope}[yshift=0.5cm] +\node[color=blue!5!red] at (\xmin,{1*\ds}) [right] {$\alpha=0.5$}; +\node[color=blue!16!red] at (\xmin,{2*\ds}) [right] {$\alpha=1.5$}; +\node[color=blue!26!red] at (\xmin,{3*\ds}) [right] {$\alpha=2.5$}; +\node[color=blue!37!red] at (\xmin,{4*\ds}) [right] {$\alpha=2.5$}; +\node[color=blue!47!red] at (\xmin,{5*\ds}) [right] {$\alpha=3.5$}; +\node[color=blue!57!red] at (\xmin,{6*\ds}) [right] {$\alpha=5.5$}; +\node[color=blue!68!red] at (\xmin,{7*\ds}) [right] {$\alpha=6.5$}; +\node[color=blue!78!red] at (\xmin,{8*\ds}) [right] {$\alpha=7.5$}; +\node[color=blue!89!red] at (\xmin,{9*\ds}) [right] {$\alpha=8.5$}; +\node[color=blue!100!red]at (\xmin,{10*\ds}) [right] {$\alpha=9.5$}; +\end{scope} +\node at (-1.7,4.5) {$\displaystyle +y=\mathstrut_0F_1\biggl(\begin{matrix}\text{---}\\\alpha\end{matrix};x\biggr)$}; +\end{scope} + +\draw[->] (\xmin-0.2,0) -- (\xmax+0.3,0) coordinate[label=$x$]; +\draw[->] (0,-0.5) -- (0,5.3) coordinate[label={right:$y$}]; + +\begin{scope}[yshift=-6.5cm] +\begin{scope} +\clip (\xmin,-5) rectangle (\xmax,5); + +\draw[color=darkgreen!5!red,line width=1.4pt] \kurvenone; +\draw[color=darkgreen!16!red,line width=1.4pt] \kurventwo; +\draw[color=darkgreen!26!red,line width=1.4pt] \kurventhree; +\draw[color=darkgreen!37!red,line width=1.4pt] \kurvenfour; +\draw[color=darkgreen!47!red,line width=1.4pt] \kurvenfive; +\draw[color=darkgreen!57!red,line width=1.4pt] \kurvensix; +\draw[color=darkgreen!68!red,line width=1.4pt] \kurvenseven; +\draw[color=darkgreen!78!red,line width=1.4pt] \kurveneight; +\draw[color=darkgreen!89!red,line width=1.4pt] \kurvennine; +\draw[color=darkgreen!100!red,line width=1.4pt] \kurventen; +\end{scope} + +\draw[->] (\xmin-0.2,0) -- (\xmax+0.3,0) coordinate[label=$x$]; +\draw[->] (0,-5.2) -- (0,5.3) coordinate[label={right:$y$}]; +\def\ds{-0.4} +\begin{scope}[yshift=-0.5cm] +\node[color=darkgreen!5!red] at (\xmax,{1*\ds}) [left] {$\alpha=-0.5$}; +\node[color=darkgreen!16!red] at (\xmax,{2*\ds}) [left] {$\alpha=-1.5$}; +\node[color=darkgreen!26!red] at (\xmax,{3*\ds}) [left] {$\alpha=-2.5$}; +\node[color=darkgreen!37!red] at (\xmax,{4*\ds}) [left] {$\alpha=-2.5$}; +\node[color=darkgreen!47!red] at (\xmax,{5*\ds}) [left] {$\alpha=-3.5$}; +\node[color=darkgreen!57!red] at (\xmax,{6*\ds}) [left] {$\alpha=-5.5$}; +\node[color=darkgreen!68!red] at (\xmax,{7*\ds}) [left] {$\alpha=-6.5$}; +\node[color=darkgreen!78!red] at (\xmax,{8*\ds}) [left] {$\alpha=-7.5$}; +\node[color=darkgreen!89!red] at (\xmax,{9*\ds}) [left] {$\alpha=-8.5$}; +\node[color=darkgreen!100!red]at (\xmax,{10*\ds}) [left] {$\alpha=-9.5$}; +\end{scope} +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/040-rekursion/images/Makefile b/buch/chapters/040-rekursion/images/Makefile index 9608a94..54ed23b 100644 --- a/buch/chapters/040-rekursion/images/Makefile +++ b/buch/chapters/040-rekursion/images/Makefile @@ -3,7 +3,8 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: gammaplot.pdf fibonacci.pdf +all: gammaplot.pdf fibonacci.pdf order.pdf beta.pdf loggammaplot.pdf \ + 0f1.pdf gammaplot.pdf: gammaplot.tex gammapaths.tex pdflatex gammaplot.tex @@ -16,3 +17,30 @@ fibonaccigrid.tex: fibonacci.m fibonacci.pdf: fibonacci.tex fibonaccigrid.tex pdflatex fibonacci.tex + +order.pdf: order.tex orderpath.tex + pdflatex order.tex + +orderpath.tex: order.m + octave order.m + +beta.pdf: beta.tex betapaths.tex + pdflatex beta.tex + +betapaths.tex: betadist.m + octave betadist.m + +loggammaplot.pdf: loggammaplot.tex loggammadata.tex + pdflatex loggammaplot.tex + +loggammadata.tex: loggammaplot.m + octave loggammaplot.m + +0f1: 0f1.cpp + g++ -O -Wall -g -o 0f1 0f1.cpp + +0f1data.tex: 0f1 + ./0f1 + +0f1.pdf: 0f1.tex 0f1data.tex + pdflatex 0f1.tex diff --git a/buch/chapters/040-rekursion/images/beta.pdf b/buch/chapters/040-rekursion/images/beta.pdf Binary files differnew file mode 100644 index 0000000..0e6567b --- /dev/null +++ b/buch/chapters/040-rekursion/images/beta.pdf diff --git a/buch/chapters/040-rekursion/images/beta.tex b/buch/chapters/040-rekursion/images/beta.tex new file mode 100644 index 0000000..1e1a1b3 --- /dev/null +++ b/buch/chapters/040-rekursion/images/beta.tex @@ -0,0 +1,236 @@ +% +% beta.tex -- display some symmetric beta distributions +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math,calc} +\input{betapaths.tex} +\begin{document} +\def\skala{12} +\definecolor{colorone}{rgb}{1.0,0.6,0.0} +\definecolor{colortwo}{rgb}{1.0,0.0,0.0} +\definecolor{colorthree}{rgb}{0.6,0.0,0.6} +\definecolor{colorfour}{rgb}{0.6,0.0,1.0} +\definecolor{colorfive}{rgb}{0.0,0.0,1.0} +\definecolor{colorsix}{rgb}{0.4,0.6,1.0} +\definecolor{colorseven}{rgb}{0.0,0.0,0.0} +\definecolor{coloreight}{rgb}{0.0,0.8,0.8} +\definecolor{colornine}{rgb}{0.0,0.8,0.2} +\definecolor{colorten}{rgb}{0.2,0.4,0.0} +\definecolor{coloreleven}{rgb}{0.6,1.0,0.0} +\definecolor{colortwelve}{rgb}{1.0,0.8,0.4} + +\def\achsen{ + \foreach \x in {0.1,0.2,0.3,0.4,0.5,0.6,0.7,0.8,0.9}{ + \draw ({\x*\dx},{-0.1/\skala}) -- ({\x*\dx},{0.1/\skala}); + \node at ({\x*\dx},{-0.1/\skala}) [below] {$\x$}; + } + \foreach \y in {1,2,3,4}{ + \draw ({-0.1/\skala},{\y*\dy}) -- ({0.1/\skala},{\y*\dy}); + \node at ({-0.1/\skala},{\y*\dy}) [left] {$\y$}; + } + \def\x{1} + \draw ({\x*\dx},{-0.1/\skala}) -- ({\x*\dx},{0.1/\skala}); + \node at ({\x*\dx},{-0.1/\skala}) [below] {$\x$}; + \def\x{0} + \node at ({\x*\dx},{-0.1/\skala}) [below] {$\x$}; + + \draw[->] ({-0.1/\skala},0) -- ({1*\dx+0.4/\skala},0) + coordinate[label={$x$}]; + \draw[->] (0,{-0.1/\skala}) -- (0,{\betamax*\dy+0.4/\skala},0) + coordinate[label={right:$\beta(a,b,x)$}]; +} + +\def\farbcoord#1#2{ + ({\dx*(0.63+((#1)/5)*0.27)},{\dx*(0.18+((#2)/5)*0.27)}) +} +\def\farbviereck{ + \foreach \x in {1,2,3,4}{ + \draw[color=gray!30] \farbcoord{\x}{0} -- \farbcoord{\x}{4}; + \draw[color=gray!30] \farbcoord{0}{\x} -- \farbcoord{4}{\x}; + } + \draw[->] \farbcoord{0}{0} -- \farbcoord{4.4}{0} + coordinate[label={$a$}]; + \draw[->] \farbcoord{0}{0} -- \farbcoord{0}{4.4} + coordinate[label={left: $b$}]; + \foreach \x in {1,2,3,4}{ + \node[color=gray] at \farbcoord{4}{\x} [right] {\tiny $b=\x$}; + %\fill[color=white,opacity=0.7] + % \farbcoord{(\x-0.1)}{3.3} + % rectangle + % \farbcoord{(\x+0.1)}{4}; + \node[color=gray] at \farbcoord{\x}{4} [right,rotate=90] + {\tiny $a=\x$}; + } +} +\def\farbpunkt#1#2#3{ + \fill[color=#3] \farbcoord{#1}{#2} circle[radius={0.1/\skala}]; +} + +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\dx{1.15} +\def\dy{0.1} +\def\opa{0.1} + +\def\betamax{4.9} + +\begin{scope} +\clip (0,0) rectangle ({1*\dx},{\betamax*\dy}); +\fill[color=colorone,opacity=\opa] (0,0) -- \betaaa -- (\dx,0) -- cycle; +\fill[color=colortwo,opacity=\opa] (0,0) -- \betabb -- (\dx,0) -- cycle; +\fill[color=colorthree,opacity=\opa] (0,0) -- \betacc -- (\dx,0) -- cycle; +\fill[color=colorfour,opacity=\opa] (0,0) -- \betadd -- (\dx,0) -- cycle; +\fill[color=colorfive,opacity=\opa] (0,0) -- \betaee -- (\dx,0) -- cycle; +\fill[color=colorsix,opacity=\opa] (0,0) -- \betaff -- (\dx,0) -- cycle; +\fill[color=colorseven,opacity=\opa] (0,0) -- \betagg -- (\dx,0) -- cycle; +\fill[color=coloreight,opacity=\opa] (0,0) -- \betahh -- (\dx,0) -- cycle; +\fill[color=colornine,opacity=\opa] (0,0) -- \betaii -- (\dx,0) -- cycle; +\fill[color=colorten,opacity=\opa] (0,0) -- \betajj -- (\dx,0) -- cycle; +\fill[color=coloreleven,opacity=\opa] (0,0) -- \betakk -- (\dx,0) -- cycle; +\fill[color=colortwelve,opacity=\opa] (0,0) -- \betall -- (\dx,0) -- cycle; + +\draw[color=colorone] \betaaa; +\draw[color=colortwo] \betabb; +\draw[color=colorthree] \betacc; +\draw[color=colorfour] \betadd; +\draw[color=colorfive] \betaee; +\draw[color=colorsix] \betaff; +\draw[color=colorseven] \betagg; +\draw[color=coloreight] \betahh; +\draw[color=colornine] \betaii; +\draw[color=colorten] \betajj; +\draw[color=coloreleven] \betakk; +\draw[color=colortwelve] \betall; + +\end{scope} + +\achsen + +\farbviereck + +\farbpunkt{\alphatwelve}{\betatwelve}{colortwelve} +\farbpunkt{\alphaeleven}{\betaeleven}{coloreleven} +\farbpunkt{\alphaten}{\betaten}{colorten} +\farbpunkt{\alphanine}{\betanine}{colornine} +\farbpunkt{\alphaeight}{\betaeight}{coloreight} +\farbpunkt{\alphaseven}{\betaseven}{colorseven} +\farbpunkt{\alphasix}{\betasix}{colorsix} +\farbpunkt{\alphafive}{\betafive}{colorfive} +\farbpunkt{\alphafour}{\betafour}{colorfour} +\farbpunkt{\alphathree}{\betathree}{colorthree} +\farbpunkt{\alphatwo}{\betatwo}{colortwo} +\farbpunkt{\alphaone}{\betaone}{colorone} + + +\def\betamax{4.9} + +\begin{scope}[yshift=-0.6cm] + +\begin{scope} +\clip (0,0) rectangle ({1*\dx},{\betamax*\dy}); +\fill[color=colorone,opacity=\opa] (0,0) -- \betaea -- (\dx,0) -- cycle; +\fill[color=colortwo,opacity=\opa] (0,0) -- \betaeb -- (\dx,0) -- cycle; +\fill[color=colorthree,opacity=\opa] (0,0) -- \betaec -- (\dx,0) -- cycle; +\fill[color=colorfour,opacity=\opa] (0,0) -- \betaed -- (\dx,0) -- cycle; +\fill[color=colorfive,opacity=\opa] (0,0) -- \betaee -- (\dx,0) -- cycle; +\fill[color=colorsix,opacity=\opa] (0,0) -- \betaef -- (\dx,0) -- cycle; +\fill[color=colorseven,opacity=\opa] (0,0) -- \betaeg -- (\dx,0) -- cycle; +\fill[color=coloreight,opacity=\opa] (0,0) -- \betaeh -- (\dx,0) -- cycle; +\fill[color=colornine,opacity=\opa] (0,0) -- \betaei -- (\dx,0) -- cycle; +\fill[color=colorten,opacity=\opa] (0,0) -- \betaej -- (\dx,0) -- cycle; +\fill[color=coloreleven,opacity=\opa] (0,0) -- \betaek -- (\dx,0) -- cycle; +\fill[color=colortwelve,opacity=\opa] (0,0) -- \betael -- (\dx,0) -- cycle; + +\draw[color=colorone] \betaea; +\draw[color=colortwo] \betaeb; +\draw[color=colorthree] \betaec; +\draw[color=colorfour] \betaed; +\draw[color=colorfive] \betaee; +\draw[color=colorsix] \betaef; +\draw[color=colorseven] \betaeg; +\draw[color=coloreight] \betaeh; +\draw[color=colornine] \betaei; +\draw[color=colorten] \betaej; +\draw[color=coloreleven] \betaek; +\draw[color=colortwelve] \betael; +\end{scope} + +\achsen + +\farbviereck + +\farbpunkt{\alphafive}{\betatwelve}{colortwelve} +\farbpunkt{\alphafive}{\betaeleven}{coloreleven} +\farbpunkt{\alphafive}{\betaten}{colorten} +\farbpunkt{\alphafive}{\betanine}{colornine} +\farbpunkt{\alphafive}{\betaeight}{coloreight} +\farbpunkt{\alphafive}{\betaseven}{colorseven} +\farbpunkt{\alphafive}{\betasix}{colorsix} +\farbpunkt{\alphafive}{\betafive}{colorfive} +\farbpunkt{\alphafive}{\betafour}{colorfour} +\farbpunkt{\alphafive}{\betathree}{colorthree} +\farbpunkt{\alphafive}{\betatwo}{colortwo} +\farbpunkt{\alphafive}{\betaone}{colorone} + +\end{scope} + +\begin{scope}[yshift=-1.2cm] + +\begin{scope} +\clip (0,0) rectangle ({1*\dx},{\betamax*\dy}); +\fill[color=colorone,opacity=\opa] (0,0) -- \betaal -- (\dx,0) -- cycle; +\fill[color=colortwo,opacity=\opa] (0,0) -- \betabl -- (\dx,0) -- cycle; +\fill[color=colorthree,opacity=\opa] (0,0) -- \betacl -- (\dx,0) -- cycle; +\fill[color=colorfour,opacity=\opa] (0,0) -- \betadl -- (\dx,0) -- cycle; +\fill[color=colorfive,opacity=\opa] (0,0) -- \betael -- (\dx,0) -- cycle; +\fill[color=colorsix,opacity=\opa] (0,0) -- \betafl -- (\dx,0) -- cycle; +\fill[color=colorseven,opacity=\opa] (0,0) -- \betagl -- (\dx,0) -- cycle; +\fill[color=coloreight,opacity=\opa] (0,0) -- \betahl -- (\dx,0) -- cycle; +\fill[color=colornine,opacity=\opa] (0,0) -- \betail -- (\dx,0) -- cycle; +\fill[color=colorten,opacity=\opa] (0,0) -- \betajl -- (\dx,0) -- cycle; +\fill[color=coloreleven,opacity=\opa] (0,0) -- \betakl -- (\dx,0) -- cycle; +\fill[color=colortwelve,opacity=\opa] (0,0) -- \betall -- (\dx,0) -- cycle; + +\draw[color=colorone] \betaal; +\draw[color=colortwo] \betabl; +\draw[color=colorthree] \betacl; +\draw[color=colorfour] \betadl; +\draw[color=colorfive] \betael; +\draw[color=colorsix] \betafl; +\draw[color=colorseven] \betagl; +\draw[color=coloreight] \betahl; +\draw[color=colornine] \betail; +\draw[color=colorten] \betajl; +\draw[color=coloreleven] \betakl; +\draw[color=colortwelve] \betall; +\end{scope} + +\achsen + +\farbviereck + +\farbpunkt{\alphatwelve}{\betatwelve}{colortwelve} +\farbpunkt{\alphaeleven}{\betatwelve}{coloreleven} +\farbpunkt{\alphaten}{\betatwelve}{colorten} +\farbpunkt{\alphanine}{\betatwelve}{colornine} +\farbpunkt{\alphaeight}{\betatwelve}{coloreight} +\farbpunkt{\alphaseven}{\betatwelve}{colorseven} +\farbpunkt{\alphasix}{\betatwelve}{colorsix} +\farbpunkt{\alphafive}{\betatwelve}{colorfive} +\farbpunkt{\alphafour}{\betatwelve}{colorfour} +\farbpunkt{\alphathree}{\betatwelve}{colorthree} +\farbpunkt{\alphatwo}{\betatwelve}{colortwo} +\farbpunkt{\alphaone}{\betatwelve}{colorone} + +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/040-rekursion/images/betadist.m b/buch/chapters/040-rekursion/images/betadist.m new file mode 100644 index 0000000..5b466a6 --- /dev/null +++ b/buch/chapters/040-rekursion/images/betadist.m @@ -0,0 +1,58 @@ +# +# betadist.m +# +# (c) 2022 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +global N; +N = 201; +global nmin; +global nmax; +nmin = -4; +nmax = 7; +n = nmax - nmin + 1 +A = 3; + +t = (nmin:nmax) / nmax; +alpha = 1 + A * t .* abs(t) +#alpha(1) = 0.01; + +#alpha = [ 1, 1.03, 1.05, 1.1, 1.25, 1.5, 2, 2.5, 3, 4, 5 ]; +beta = alpha; +names = [ "one"; "two"; "three"; "four"; "five"; "six"; "seven"; "eight"; + "nine"; "ten"; "eleven"; "twelve" ] + +function retval = Beta(a, b, x) + retval = x^(a-1) * (1-x)^(b-1) / beta(a, b); + if (retval > 100) + retval = 100 + end +end + +function plotbeta(fn, a, b, name) + global N; + fprintf(fn, "\\def\\beta%s{\n", strtrim(name)); + fprintf(fn, "\t({%.4f*\\dx},{%.4f*\\dy})", 0, Beta(a, b, 0)); + for x = (1:N-1)/(N-1) + X = (1-cos(pi * x))/2; + fprintf(fn, "\n\t--({%.4f*\\dx},{%.4f*\\dy})", + X, Beta(a, b, X)); + end + fprintf(fn, "\n}\n"); +end + +fn = fopen("betapaths.tex", "w"); + +for i = (1:n) + fprintf(fn, "\\def\\alpha%s{%f}\n", strtrim(names(i,:)), alpha(i)); + fprintf(fn, "\\def\\beta%s{%f}\n", strtrim(names(i,:)), beta(i)); +end + +for i = (1:n) + for j = (1:n) + printf("working on %d,%d:\n", i, j); + plotbeta(fn, alpha(i), beta(j), + char(['a' + i - 1, 'a' + j - 1])); + end +end + +fclose(fn); diff --git a/buch/chapters/040-rekursion/images/loggammaplot.m b/buch/chapters/040-rekursion/images/loggammaplot.m new file mode 100644 index 0000000..5456e4f --- /dev/null +++ b/buch/chapters/040-rekursion/images/loggammaplot.m @@ -0,0 +1,43 @@ +# +# loggammaplot.m +# +# (c) 2022 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +xmax = 10; +xmin = 0.1; +N = 500; + +fn = fopen("loggammadata.tex", "w"); + +fprintf(fn, "\\def\\loggammapath{\n ({%.4f*\\dx},{%.4f*\\dy})", + xmax, log(gamma(xmax))); +xstep = (xmax - 1) / N; +for x = (xmax:-xstep:1) + fprintf(fn, "\n\t-- ({%.4f*\\dx},{%.4f*\\dy})", x, log(gamma(x))); +endfor +for k = (0:0.2:10) + x = exp(-k); + fprintf(fn, "\n\t-- ({%.4f*\\dx},{%.4f*\\dy})", x, log(gamma(x))); +endfor +fprintf(fn, "\n}\n"); + +function retval = lgp(fn, x0, name) + fprintf(fn, "\\def\\loggammaplot%s{\n", name); + fprintf(fn, "\\draw[color=red,line width=1pt] "); + for k = (-7:0.1:7) + x = x0 + 0.5 * tanh(k); + if (k > -5) + fprintf(fn, "\n\t-- "); + end + fprintf(fn, "({%.4f*\\dx},{%.4f*\\dy})", x, log(gamma(x))); + endfor + fprintf(fn, ";\n}\n"); +endfunction + +lgp(fn, -0.5, "zero"); +lgp(fn, -1.5, "one"); +lgp(fn, -2.5, "two"); +lgp(fn, -3.5, "three"); +lgp(fn, -4.5, "four"); + +fclose(fn); diff --git a/buch/chapters/040-rekursion/images/loggammaplot.pdf b/buch/chapters/040-rekursion/images/loggammaplot.pdf Binary files differnew file mode 100644 index 0000000..a2963f2 --- /dev/null +++ b/buch/chapters/040-rekursion/images/loggammaplot.pdf diff --git a/buch/chapters/040-rekursion/images/loggammaplot.tex b/buch/chapters/040-rekursion/images/loggammaplot.tex new file mode 100644 index 0000000..8ca4e1c --- /dev/null +++ b/buch/chapters/040-rekursion/images/loggammaplot.tex @@ -0,0 +1,89 @@ +% +% tikztemplate.tex -- template for standalon tikz images +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{1} +\input{loggammadata.tex} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +% add image content here + +\def\dx{1} +\def\dy{0.6} +\def\xmax{8} +\def\xmin{-4.9} +\def\ymax{8} +\def\ymin{-3.1} + +\fill[color=blue!20] ({\xmin*\dx},{\ymin*\dy}) rectangle ({-4*\dx},{\ymax*\dy}); +\fill[color=blue!20] ({-3*\dx},{\ymin*\dy}) rectangle ({-2*\dx},{\ymax*\dy}); +\fill[color=blue!20] ({-1*\dx},{\ymin*\dy}) rectangle ({-0*\dx},{\ymax*\dy}); + +\draw[->] ({\xmin*\dx-0.1},0) -- ({\xmax*\dx+0.3},0) + coordinate[label={$x$}]; +\draw[->] (0,{\ymin*\dy-0.1}) -- (0,{\ymax*\dy+0.3}) + coordinate[label={right:$y$}]; + +\begin{scope} +\clip ({\xmin*\dx},{\ymin*\dy}) rectangle ({\xmax*\dx},{\ymax*\dy}); + +\foreach \x in {-1,-2,-3,-4}{ + \draw[color=blue,line width=0.3pt] + ({\x*\dx},{\ymin*\dy}) -- ({\x*\dx},{\ymax*\dy}); +} + +\draw[color=red,line width=1pt] \loggammapath; + +\loggammaplotzero +\loggammaplotone +\loggammaplottwo +\loggammaplotthree +\loggammaplotfour + +\end{scope} + +\foreach \y in {0.1,10,100,1000,1000}{ + \draw[line width=0.3pt] + ({\xmin*\dx},{ln(\y)*\dy}) + -- + ({\xmax*\dx},{ln(\y)*\dy}) ; +} + +\foreach \x in {1,...,8}{ + \draw ({\x*\dx},{-0.05}) -- ({\x*\dx},{0.05}); + \node at ({\x*\dx},0) [below] {$\x$}; +} + +\foreach \x in {-1,...,-4}{ + \draw ({\x*\dx},{-0.05}) -- ({\x*\dx},{0.05}); +} +\foreach \x in {-1,...,-3}{ + \node at ({\x*\dx},0) [below right] {$\x$}; +} +\node at ({-4*\dx},0) [below left] {$-4$}; + +\def\htick#1#2{ + \draw (-0.05,{ln(#1)*\dy}) -- (0.05,{ln(#1)*\dy}); + \node at (0,{ln(#1)*\dy}) [above right] {#2}; +} + +\htick{10}{$10^1$} +\htick{100}{$10^2$} +\htick{1000}{$10^3$} +\htick{0.1}{$10^{-1}$} + +\node[color=red] at ({3*\dx},{ln(30)*\dy}) {$y=\log|\Gamma(x)|$}; + + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/040-rekursion/images/order.m b/buch/chapters/040-rekursion/images/order.m new file mode 100644 index 0000000..762f458 --- /dev/null +++ b/buch/chapters/040-rekursion/images/order.m @@ -0,0 +1,119 @@ +# +# order.m +# +# (c) 2022 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +# +global N; +N = 10; +global subdivisions; +subdivisions = 100; +global P; +P = 0.5 + +function retval = orderF(p, n, k) + retval = 0; + for i = (k:n) + retval = retval + nchoosek(n,i) * p^i * (1-p)^(n-i); + end +end + +function retval = orderd(p, n, k) + retval = 0; + for i = (k:n) + s = i * p^(i-1) * (1-p)^(n-i); + s = s - p^i * (n-i) * (1-p)^(n-i-1); + retval = retval + nchoosek(n,i) * s; + end +end + +function retval = orders(p, n, k) + retval = k * nchoosek(n, k) * p^(k-1) * (1-p)^(n-k); +end + +function orderpath(fn, k, name) + fprintf(fn, "\\def\\order%s{\n\t(0,0)", name); + global N; + global subdivisions; + for i = (0:subdivisions) + p = i/subdivisions; + fprintf(fn, "\n\t-- ({%.4f*\\dx},{%.4f*\\dy})", + p, orderF(p, N, k)); + end + fprintf(fn, "\n}\n"); +end + +function orderdpath(fn, k, name) + fprintf(fn, "\\def\\orderd%s{\n\t(0,0)", name); + global N; + global subdivisions; + for i = (1:subdivisions-1) + p = i/subdivisions; + fprintf(fn, "\n\t-- ({%.4f*\\dx},{%.4f*\\dy})", + p, orderd(p, N, k)); + end + fprintf(fn, "\n\t-- ({1*\\dx},0)"); + fprintf(fn, "\n}\n"); +end + +function orderspath(fn, k, name) + fprintf(fn, "\\def\\orders%s{\n\t(0,0)", name); + global N; + global subdivisions; + for i = (1:subdivisions-1) + p = i/subdivisions; + fprintf(fn, "\n\t-- ({%.4f*\\dx},{%.4f*\\dy})", + p, orders(p, N, k)); + end + fprintf(fn, "\n\t-- ({1*\\dx},0)"); + fprintf(fn, "\n}\n"); +end + +fn = fopen("orderpath.tex", "w"); + +orderpath(fn, 0, "zero"); +orderdpath(fn, 0, "zero"); +orderspath(fn, 0, "zero"); + +orderpath(fn, 1, "one"); +orderdpath(fn, 1, "one"); +orderspath(fn, 1, "one"); + +orderpath(fn, 2, "two"); +orderdpath(fn, 2, "two"); +orderspath(fn, 2, "two"); + +orderpath(fn, 3, "three"); +orderdpath(fn, 3, "three"); +orderspath(fn, 3, "three"); + +orderpath(fn, 4, "four"); +orderdpath(fn, 4, "four"); +orderspath(fn, 4, "four"); + +orderpath(fn, 5, "five"); +orderdpath(fn, 5, "five"); +orderspath(fn, 5, "five"); + +orderpath(fn, 6, "six"); +orderdpath(fn, 6, "six"); +orderspath(fn, 6, "six"); + +orderpath(fn, 7, "seven"); +orderdpath(fn, 7, "seven"); +orderspath(fn, 7, "seven"); + +orderpath(fn, 8, "eight"); +orderdpath(fn, 8, "eight"); +orderspath(fn, 8, "eight"); + +orderpath(fn, 9, "nine"); +orderdpath(fn, 9, "nine"); +orderspath(fn, 9, "nine"); + +orderpath(fn, 10, "ten"); +orderdpath(fn, 10, "ten"); +orderspath(fn, 10, "ten"); + +fclose(fn); + + diff --git a/buch/chapters/040-rekursion/images/order.pdf b/buch/chapters/040-rekursion/images/order.pdf Binary files differnew file mode 100644 index 0000000..88b2b08 --- /dev/null +++ b/buch/chapters/040-rekursion/images/order.pdf diff --git a/buch/chapters/040-rekursion/images/order.tex b/buch/chapters/040-rekursion/images/order.tex new file mode 100644 index 0000000..0284735 --- /dev/null +++ b/buch/chapters/040-rekursion/images/order.tex @@ -0,0 +1,125 @@ +% +% order.tex -- Verteilungsfunktion für Ordnungsstatistik +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math} +\begin{document} +\def\skala{8} +\definecolor{darkgreen}{rgb}{0,0.6,0} + +\def\n{10} +\def\E#1#2{ + \draw[color=#2] + ({\dx*#1/(\n+1)},{-0.1/\skala}) -- ({\dx*#1/(\n+1)},{4.4*\dy}); + \node[color=#2] at ({\dx*#1/(\n+1)},{3.2*\dy}) + [rotate=90,above right] {$k=#1$}; +} +\def\var#1#2{ + \pgfmathparse{\dx*sqrt(#1*(\n-#1+1)/((\n+1)*(\n+1)*(\n+2)))} + \xdef\var{\pgfmathresult} + \fill[color=#2,opacity=0.5] + ({\dx*#1/(\n+1)-\var},0) rectangle ({\dx*#1/(\n+1)+\var},{4.4*\dy}); +} + +\input{orderpath.tex} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\dx{1.6} +\def\dy{0.5} + +\def\pfad#1#2{ +\draw[color=#2,line width=1.4pt] ({-0.1/\skala},0) + -- + #1 + -- + ({1*\dx+0.1/\skala},0.5); +} + +\pfad{\orderzero}{darkgreen!20} +\pfad{\orderone}{darkgreen!20} +\pfad{\ordertwo}{darkgreen!20} +\pfad{\orderthree}{darkgreen!20} +\pfad{\orderfour}{darkgreen!20} +\pfad{\orderfive}{darkgreen!20} +\pfad{\ordersix}{darkgreen!20} +\pfad{\ordereight}{darkgreen!20} +\pfad{\ordernine}{darkgreen!20} +\pfad{\orderten}{darkgreen!20} +\pfad{\orderseven}{darkgreen} + +\draw[->] ({-0.1/\skala},0) -- ({1.03*\dx},0) coordinate[label={$x$}]; +\draw[->] (0,{-0.1/\skala}) -- (0,0.6) coordinate[label={right:$F(X)$}]; +\foreach \x in {0,0.2,0.4,0.6,0.8,1}{ + \draw ({\x*\dx},{-0.1/\skala}) -- ({\x*\dx},{0.1/\skala}); + \node at ({\x*\dx},{-0.1/\skala}) [below] {$\x$}; +} +\foreach \y in {0.5,1}{ + \draw ({-0.1/\skala},{\y*\dy}) -- ({0.1/\skala},{\y*\dy}); + \node at ({-0.1/\skala},{\y*\dy}) [left] {$\y$}; +} + +\node[color=darkgreen] at ({0.64*\dx},{0.56*\dy}) [rotate=42] {$k=7$}; + +\begin{scope}[yshift=-0.7cm] +\def\dy{0.125} + +\foreach \k in {1,2,3,4,5,6,8,9,10}{ + \E{\k}{blue!30} +} +\def\k{7} +\var{\k}{orange!40} +\node[color=blue] at ({\dx*\k/(\n+1)},{4.3*\dy}) [above] {$E(X_{7:n})$}; + +\def\pfad#1#2{ + \draw[color=#2,line width=1.4pt] ({-0.1/\skala},0) + -- + #1 + -- + ({1*\dx+0.1/\skala},0.0); +} + +\begin{scope} +\clip ({-0.1/\skala},{-0.1/\skala}) + rectangle ({1*\dx+0.1/\skala},{0.56+0.1/\skala}); + +\pfad{\orderdzero}{red!20} +\pfad{\orderdone}{red!20} +\pfad{\orderdtwo}{red!20} +\pfad{\orderdthree}{red!20} +\pfad{\orderdfour}{red!20} +\pfad{\orderdfive}{red!20} +\pfad{\orderdsix}{red!20} +\pfad{\orderdeight}{red!20} +\pfad{\orderdnine}{red!20} +\pfad{\orderdten}{red!20} +\E{\k}{blue} +\pfad{\orderdseven}{red} + +\end{scope} + +\draw[->] ({-0.1/\skala},0) -- ({1.03*\dx},0) coordinate[label={$x$}]; +\draw[->] (0,{-0.1/\skala}) -- (0,0.6) coordinate[label={right:$\varphi(X)$}]; +\foreach \x in {0,0.2,0.4,0.6,0.8,1}{ + \draw ({\x*\dx},{-0.1/\skala}) -- ({\x*\dx},{0.1/\skala}); + \node at ({\x*\dx},{-0.1/\skala}) [below] {$\x$}; +} +\foreach \y in {1,2,3,4}{ + \draw ({-0.1/\skala},{\y*\dy}) -- ({0.1/\skala},{\y*\dy}); + \node at ({-0.1/\skala},{\y*\dy}) [left] {$\y$}; +} + +\node[color=red] at ({0.67*\dx},{2.7*\dy}) [above] {$k=7$}; + + +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/040-rekursion/integral.tex b/buch/chapters/040-rekursion/integral.tex new file mode 100644 index 0000000..df52a58 --- /dev/null +++ b/buch/chapters/040-rekursion/integral.tex @@ -0,0 +1,103 @@ +% +% integral.tex +% +% (c) 2022 Prof Dr Andreas Müller, OST Ostschweizer Hochschule +% +\subsection{Integraldarstellung und der Satz von Bohr-Mollerup +\label{buch:subsection:integral-eindeutig}} +Die Integralformel +\[ +f(x) += +\int_0^\infty t^{x-1}e^{-t}\,dt +\] +für die Gamma-Funktion erfüllt die Funktionalgleichung der Gamma-Funktion. +Aus dem Satz von Bohr-Mollerup~\ref{buch:satz:bohr-mollerup} folgt, +dass $f(x)=\Gamma(x)$, wenn gezeigt werden kann, dass $\log f(x)$ +konvex ist. +Dies soll im Folgenden gezeigt werden. + +\subsubsection{Logarithmische Ableitung} +Die Ableitungen der Funktion $\log f(x)$ sind die erste und +zweite logarithmische +Ableitung +\begin{align} +\frac{d}{dx}\log f(x) +&= +\frac{f'(x)}{f(x)} +\notag +\\ +\frac{d^2}{dx^2} \log f(x) +&= +\frac{f''(x)f(x)-f'(x)^2}{f(x)^2}. +\label{buch:rekursion:eqn:zweiteablteitung} +\end{align} +Durch Ableiten unter dem Integralzeichen können die Ableitungen +von $f$ als +\begin{align*} +f'(x) +&= +\int_0^\infty \log(t)\, t^{x-1} e^{-t}\,dt +\\ +f''(x) +&= +\int_0^\infty \log(t)^2\, t^{x-1} e^{-t}\,dt +\end{align*} +bestimmt werden. +Um nachzuweisen, dass $\log f(x)$ konvex ist, muss nur gezeigt werden, +dass die zweite logarithmische Ableitung von $f(x)$ positiv ist, was +gemäss~\eqref{buch:rekursion:eqn:zweiteablteitung} mit +\begin{equation} +f''(x)f(x)-f'(x)^2 += +\int_0^\infty \log(t)^2\, t^{x-1}e^{-t}\,dt +\int_0^\infty t^{x-1}e^{-t}\,dt +- +\biggl( +\int_0^\infty \log(t)\, t^{x-1}e^{-t}\,dt +\biggr)^2 +\ge 0 +\label{buch:rekursion:gamma-integral:ungleichung} +\end{equation} +gleichbedeutend ist. + +\subsubsection{Skalarprodukt} +Die Integral in~\eqref{buch:rekursion:gamma-integral:ungleichung} +können als Werte eines Skalarproduktes von Funktionen auf $\mathbb{R}^+$ +gelesen werden. +Dazu definieren wir +\begin{align} +\langle u,v\rangle +&= +\int_0^\infty u(t)v(t)\,t^{x-1}e^{-t}\,dt +\label{buch:rekursion:gamma-integral:eqn:skalarprodukt} +\\ +\|u\|^2 +&= +\int_0^\infty u(t)^2 \,t^{x-1}e^{-t}\,dt, +\notag +\end{align} +für alle Funktionen $u$ und $v$, für die die Integrale definiert sind. + +\subsubsection{Cauchy-Schwarz-Ungleichung} +Die Cauchy-Schwarz-Ungleichung für das +Skalarprodukt~\eqref{buch:rekursion:gamma-integral:eqn:skalarprodukt} +für die Funktion $u(t)=1$ und $v(t)=\log(t)$ +lautet +\[ +|\langle u,v\rangle|^2 += +\biggl| +\int_0^1 \log(t)\,t^{x-1}e^{-t}\,dt +\biggr|^2 +\le +\|u\|^2\cdot \|v\|^2 += +\int_0^\infty 1\cdot t^{x-1}e^{-t}\,dt +\int_0^\infty \log(t)^2\cdot t^{x-1}e^{-t}\,dt. +\] +Daraus folgt aber durch Umstellen unmittelbar die +Ungleichung~\eqref{buch:rekursion:gamma-integral:ungleichung}. +Damit ist gezeigt, dass $\log f(t)$ konvex ist und nach +dem Satz~\ref{buch:satz:bohr-mollerup} folgt nun, dass $f(x)=\Gamma(x)$. + diff --git a/buch/chapters/040-rekursion/uebungsaufgaben/404.tex b/buch/chapters/040-rekursion/uebungsaufgaben/404.tex index f9d014e..5d76598 100644 --- a/buch/chapters/040-rekursion/uebungsaufgaben/404.tex +++ b/buch/chapters/040-rekursion/uebungsaufgaben/404.tex @@ -1,5 +1,5 @@ Finden Sie einen einfachen Ausdruck für $(\frac12)_n$, der nur -Fakultäten und andere elmentare Funktionen verwendet. +Fakultäten und andere elementare Funktionen verwendet. \begin{loesung} Das Pochhammer-Symbol $(\frac12)_n$ kann wie folgt durch bekanntere |