diff options
| -rw-r--r-- | buch/chapters/040-rekursion/Makefile.inc | 2 | ||||
| -rw-r--r-- | buch/chapters/040-rekursion/chapter.tex | 2 | ||||
| -rw-r--r-- | buch/chapters/040-rekursion/gamma.tex | 435 | ||||
| -rw-r--r-- | buch/chapters/040-rekursion/hypergeometrisch.tex | 603 | ||||
| -rw-r--r-- | buch/chapters/040-rekursion/linear.tex | 31 | ||||
| -rw-r--r-- | buch/chapters/references.bib | 8 |
6 files changed, 1080 insertions, 1 deletions
diff --git a/buch/chapters/040-rekursion/Makefile.inc b/buch/chapters/040-rekursion/Makefile.inc index c9b454c..0da5fe4 100644 --- a/buch/chapters/040-rekursion/Makefile.inc +++ b/buch/chapters/040-rekursion/Makefile.inc @@ -6,4 +6,6 @@ CHAPTERFILES = $(CHAPTERFILES) \ chapters/040-rekursion/gamma.tex \ + chapters/040-rekursion/linear.tex \ + chapters/040-rekursion/hypergeometrisch.tex \ chapters/040-rekursion/chapter.tex diff --git a/buch/chapters/040-rekursion/chapter.tex b/buch/chapters/040-rekursion/chapter.tex index 68a5e7a..a6881ab 100644 --- a/buch/chapters/040-rekursion/chapter.tex +++ b/buch/chapters/040-rekursion/chapter.tex @@ -10,6 +10,8 @@ \rhead{} \input{chapters/040-rekursion/gamma.tex} +\input{chapters/040-rekursion/linear.tex} +\input{chapters/040-rekursion/hypergeometrisch.tex} %\section*{Übungsaufgaben} %\rhead{Übungsaufgaben} diff --git a/buch/chapters/040-rekursion/gamma.tex b/buch/chapters/040-rekursion/gamma.tex index 1691fc0..00eee19 100644 --- a/buch/chapters/040-rekursion/gamma.tex +++ b/buch/chapters/040-rekursion/gamma.tex @@ -5,6 +5,7 @@ % \section{Die Gamma-Funktion \label{buch:rekursion:section:gamma}} +\rhead{Gamma-Funktion} Die Fakultät $x!$ kann rekursiv durch \[ x! = x\cdot (x-1)! \qquad\text{und}\qquad 0!=1 @@ -21,6 +22,390 @@ Kann man eine reelle oder komplexe Funktion finden, die die Funktionalgleichung~\eqref{buch:rekursion:eqn:gammadef} erfüllt und damit die Fakultät auf beliebige Argumente ausdehnt? +\subsection{Produktformel} +Die Fakultät $n!$ ist ein Produkt von $n$ Faktoren, es ist daher +natürlich zu versuchen, auch $x!$ als ein Produkt zu schreiben. +Allerdings kann es nicht möglich sein, dies mit einer endlichen +Anzahl von Faktoren zu machen, denn wenn $x$ grösser wird, muss auch +die Zahl der Faktoren grösser werden. +Mit jedem zusätzlichen Faktor ist ein Sprung der Werte zu erwarten. +Wir erwarten daher entweder ein unendliches Produkt oder einen +Ausdreck, bei dem die ``Anzahl'' $x$ der Faktoren im Exponenten +steht. +In diesem Abschnitt soll zunächst eine solcher Ausdruck gefunden +werden. +Dieser ist jedoch für die numerische Berechnung absolut ungeeignet, +so dass er später in ein unendliches Produkt umgeformt werden muss. + +\subsubsection{Fakultät als Bruch} +Euler hat das Problem, die Fakultät auf beliebige reelle oder komplexe +Zahlen auszudehnen, wie folgt angepackt. +Zunächst hat er bemerkt, dass für ganzzahlige $x$ und natürliche $n$ +\begin{align} +x! +&= +1\cdot 2\cdot 3\cdot\ldots\cdot x +\notag +\\ +&= +\frac{ +1\cdot 2\cdot 3\cdot\ldots\cdot x\cdot (x+1) (x+2)\cdots(x+n) +}{ +(x+1)(x+2)\cdots(x+n) +} +\notag +\\ +&= +\frac{ +1\cdot 2\cdot\ldots\cdot n\cdot(n+1)\cdot(n+2)\cdots(n+x) +}{ +(x+1)(x+2)\cdots(x+n) +} +\notag +\\ +&= +\frac{n! \cdot (n+1)(n+1)\cdots(n+x)}{(x+1)(x+2)\cdots(x+n)} +\label{buch:rekursion:gamma:eqn:fakultaet} +\end{align} +gilt. +Der Plan ist, dies so umzuformen, dass man für $x$ eine beliebige +komplexe Zahl einsetzen kann. + +\subsubsection{Pochhammer-Symbol} +Die spezielle Form des Nenners und des zweiten Faktors im Zähler +von \eqref{buch:rekursion:gamma:eqn:fakultaet} +rechtfertigt die folgende Definition. + +\begin{definition}[Pochhammer] +Für $a\in\mathbb{C}$ und $n\in\mathbb{N}$ heisst das Produkt +\[ +(a)_n = a\cdot(a+1)\cdot(a+2)\cdots(a+n-1) +\] +das Pochhammer-Symbol oder die verschobene Fakultät. +\index{Pochhammer-Symbol} +\end{definition} + +Die verschobene Fakultät $(a)_n$ hat also genau $n$ Faktoren, deren +erster $1$ ist. +Die gewöhnliche Fakultät hat $n$ Faktoren, deren erster $1$ ist, also +ist $n! = (1)_n$. + +Der Ausdruck \eqref{buch:rekursion:gamma:eqn:fakultaet} +für $x!$ wird unter Verwendung des Pochhammer-Symbols zu +\begin{equation} +x! = \frac{n! (n+1)_x}{(x+1)_n}. +\label{buch:rekursion:gamma:eqn:produkt2} +\end{equation} +Leider ist dieser Ausdruck ebenfalls nicht auf beliebige $x$ +verallgemeinerungsfähig, denn $(n)_x$ ist nur natürliche $x$ definiert. +Der Faktor $(n+1)_x$ enthält $x$ Faktoren beginnend bei $n$. +Für grosses $n$ sind diese Faktoren nahe beeinander, man sollte also +$(n+1)_x$ durch $n^x$ approximieren können. +Wir erweitern daher \eqref{buch:rekursion:gamma:eqn:produkt2} mit $n^x$ +und erhalten +\begin{equation} +x! += +\frac{n!n^x}{(x+1)_n}\cdot +\frac{(n+1)_x}{n^x}. +\label{buch:rekursion:gamma:eqn:produkt3} +\end{equation} +Der erste Faktor in diesem Ausdruck enthält jetzt nur noch Dinge, +die für beliebige $x\in\mathbb{C}$ definiert sind. + +\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, +wir vermuten aber, dass er für grosses $n$ gegen $1$ konvergiert. +Tatsächlich gilt +\[ +\lim_{n\to\infty} +\frac{(n+1)_x}{n^x} += +\lim_{n\to\infty} +\underbrace{\frac{n+1}{n}}_{\displaystyle\to 1} +\cdot +\underbrace{\frac{n+2}{n}}_{\displaystyle\to 1} +\cdot\ldots\cdot +\underbrace{\frac{n+x}{n}}_{\displaystyle\to 1} += +1, +\] +da $(n+x)/n=1+x/n\to 1$ für grosses $n$. +Dies würde die folgende Definition rechtfertigen. + +\begin{definition} +\label{buch:rekursion:gamma:def:definition} +Die Gamma-Funktion $\Gamma(x)$ einer Zahl +$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}. +\] +\end{definition} + +\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 +Definition~\ref{buch:rekursion:gamma:def:definition} ableiten +können. +Dazu müssen wir nur überprüfen, ob $\Gamma(1)=0!=1$ ist und ob +die Rekursionsformel $\Gamma(n)=n\Gamma(n-1)$ gilt. + +Den Wert $\Gamma(1)$ kann man direkt berechnen: +\[ +\Gamma(1) += +\lim_{n\to\infty} \frac{n!}{(1)_n} += +\lim_{n\to\infty} \frac{n!}{n!} += +1 +\] +wegen $(1)_n=n!$. + +Für die Rekursionsformel muss man den Grenzwert für $x$ und $x+1$ +miteinander vergleichen. +Aus dem Term $(x+1)_n$ im Nenner muss man einen Term $(x)_n$ machen, +dies ist möglich, indem man mit $x$ erweitert: +\begin{align*} +\Gamma(x+1) +&= +\lim_{n\to\infty}\frac{n!n^x}{(x+1)_n} += +x\lim_{n\to\infty}\frac{n!n^x}{x(x+1)_n} += +x\lim_{n\to\infty}\frac{n!n^x}{(x)_{n+1}}. +\intertext{Wir müssen jetzt nur noch zeigen, dass der Grenzwert +auf der rechten Seite gegen $\Gamma(x)$ konvergiert, +in dessen Definition aber die Potenz $n^{x-1}$ vorkommt. +Wir müssen also einen Faktor $n$ los werden und gleichzeitig +aus $n$ überall $n+1$ machen, damit der Nenner wieder passt. +Dabei wird} +\Gamma(x+1) +&= +x\lim_{n\to\infty} +\frac{(n+1)!n^{x-1}}{(x)_{n+1}} +\cdot +\underbrace{\frac{n}{n+1}}_{\displaystyle\to 1} +\\ +&= +x\lim_{n\to\infty} +\underbrace{\frac{(n+1)!(n+1)^{x-1}}{(x)_{n+1}}}_{\displaystyle\to\Gamma(x)} +\cdot +\frac{n^{x-1}}{(n+1)^{x-1}} +\\ +&= +\Gamma(x) +\lim_{n\to\infty} \biggl(\frac{n}{n+1}\biggr)^{x-1} += +\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. + +\subsubsection{Numerische Unzulänglichkeiten der Grenzwertdefinition} +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. +Die Existenz des Grenzwertes verwendet, dass $x\ll n$ sein muss, +damit $(n+x)/n$ gegenüber $1$ vernachlässigt werden kann. +Die Grenzwertdefinition beginnt also erst, vernünftige Approximationen +von $\Gamma(x)$ zu geben, wenn $n$ viel grösser also $x$ ist. +Andererseits wächst $n!$ sehr schnell an, schon für $n=171$ ist +das Resultat grösser als was der \texttt{double}-Datentyp fassen kann. +Dies ist aber viel zu kleine, um gute Approximationen auch für kleine +Werte von $x$ zu geben. +So findet man zum Beispiel für $x=\frac12$ und $n=170$ mit Octave +\[ +\frac{n!n^{x-1}}{(x)_n} += +\frac{170!}{\sqrt{170}\cdot \frac12\cdot\frac32\cdot\ldots\cdot\frac{339}{2}} += +\frac{7.2574\cdot10^{307}}{13.308\cdot 3.1381\cdot10^{305}} += +1.7738. +\] +Andererseits werden wir später sehen, dass +\[ +\Gamma({\textstyle\frac12}) += +\sqrt{\pi} += +1.772453850905516 +\] +ist. +Die Approximation mit Hilfe der Grenzwertdefinition kann also +grundsätzlich nicht mehr als zwei korrekte Nachkommastellen liefern. + +\subsubsection{Produktformel} +Ein möglicher Ausweg aus den numerischen Schwierigkeiten mit der +Grenzwertdefinition ist, den schnell wachsenden Faktor $n!$ +in den Zähler zu bringen, so dass er der Konvergenz etwas nachhilft. +Wir berechnen daher den Kehrwert $1/\Gamma(x)$. + +\begin{satz} +\label{buch:rekursion:gamma:satz:produktformel} +Der Kehrwert der Gamma-Funktion kann geschrieben werden als +\begin{equation} +\frac{1}{\Gamma(x)} += +xe^{\gamma x} +\prod_{k=1}^\infty +\biggl(1+\frac{x}k\biggr)\,e^{-\frac{x}{k}}, +\label{buch:rekursion:gamma:eqn:produktformel} +\end{equation} +wobei $\gamma$ die Euler-Mascheronische Konstante +\[ +\gamma += +\lim_{n\to\infty} +\biggl(\sum_{k=1}^n\frac{1}{k}-\log n\biggr) +\] +ist. +\end{satz} + +\begin{proof}[Beweis] +Es sind zwei Dinge nachzuprüfen. +Zunächst muss nachgewiesen werden, dass das unendliche Produkt +überhaupt konvergiert. +Wenn das gesichert ist, muss noch gezeigt werden, dass der Grenzwert +tatsächlich $1/\Gamma(x)$ ist. + +Für die Konvergenz beachtet man, dass die Faktoren des Produkts +die Form +\begin{align*} +\biggl(1+\frac{x}n\biggr)e^{-\frac{x}{n}} +&= +\biggl(1+\frac{x}n\biggr) +\biggl(1-\frac{x}{n}+\frac{x^2}{2n^2}-\frac{x^3}{3!n^3}+\dots\biggr) +\\ +&= +1-\frac{x^2}{n^2} + +\biggl(1+\frac{x}n\biggr) +\biggl(\frac{x^2}{2n^2}-\dots\biggr) +\\ +&= +1-\frac{x^2}{n^2} + \frac{x^2}{2n^2} + O\bigl((\textstyle\frac{x}{n})^2\bigr) +\\ +&= +1-\frac{x^2}{2n^2} + O\bigl((\textstyle\frac{x}{n})^3\bigr) +\end{align*} +haben. +Da die Reihe +\[ +\sum_{n=1}^\infty \frac{x^2}{n^2} +\] +konvergent ist, konvergiert auch das Produkt. +% XXX wir brauchen irgendwo das Konvergenzkriterium für ein Produkt + +Um die Übereinstimmung der Produktformel mit $1/\Gamma(x)$ zu zeigen, +berechnen wir +\begin{align*} +\frac{1}{\Gamma(x)} +&= +\lim_{n\to\infty} +\frac{(x)_n}{n!n^{x-1}} += +\lim_{n\to\infty} +\frac{x(x+1)(x+2)\cdots(x+n-1)}{1\cdot 2\cdot3\cdots (n-1)\cdot n\cdot n^{x-1}} +\\ +&= +x +\lim_{n\to\infty} +\frac{x+1}{1} +\cdot +\frac{x+2}{2} +\cdots +\frac{x+n-1}{n-1} +\cdot +n^{-x} +\\ +&= +x +\lim_{n\to\infty} +\biggl(1+\frac{x}{1}\biggr) +\cdot +\biggl(1+\frac{x}{2}\biggr) +\cdots +\biggl(1+\frac{x}{n-1}\biggr) +\cdot +e^{-x\log n} +\\ +&= +x +\prod_{k=1}^{n-1} +\biggl(1+\frac{x}{k}\biggr) +e^{-\frac{x}{k}} +e^{\frac{x}{k}} +e^{-x\log n} +\\ +&= +x +\biggl( +\lim_{n\to\infty} +\prod_{k=1}^{n-1} +\biggl(1+\frac{x}{k}\biggr) +e^{-\frac{x}{k}} +\biggr) +\cdot +\biggl( +\lim_{n\to\infty} +e^{x\bigl(\sum_{k=1}^{n-1}\frac{1}{k} - \log n\bigr)} +\biggr) +\end{align*} +Der Klammerausdruck im Exponent des letzten Faktors auf der rechten Seite +konvergiert nach Definition der Euler-Mascheronischen Konstanten gegen +$\gamma$, somit folgt +\[ +\frac{1}{\Gamma(x)} += +xe^{\gamma x}\prod_{k=1}^\infty \biggl(1+\frac{x}{k}\biggr)e^{-\frac{x}{k}}, +\] +wie behauptet. +Damit ist Satz~\ref{buch:rekursion:gamma:satz:produktformel} +vollständig bewiesen. +\end{proof} + +\begin{table} +\centering +\begin{tabular}{|>{$}c<{$}|>{$}c<{$}|>{$}c<{$}|} +\hline +k & \Gamma(\frac12,n) & \Gamma(\frac12) - \Gamma(\frac12,n) \\ +\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 \\ +\hline +\end{tabular} +\caption{Werte $\Gamma(\frac12,n)$ von $\Gamma(\frac12)$ berechnet mit +$n=10^k$ Faktoren der +Produktformel~\eqref{buch:rekursion:gamma:eqn:produktformel} +und der zugehörige Fehler. +Die korrekten Nachkommastellen sind unterstrichen. +\label{buch:rekursion:gamma:gammatabelle}} +\end{table} + +Um zu zeigen, dass die Produktform tatsächlich besser geeignet ist, +sind in der Tabelle~\ref{buch:rekursion:gamma:gammatabelle} +die Resultate der numerischen Rechnung bis $n=1000000$ zusammengestellt. +Die Produktformel kann gute Werte von $\Gamma(x)$ auch für derart grosse +Werte von $n$ problemlos berechnen. + +Der Fehler der numersichen Approximation ist von der Grössenordnung +$O(1/n)$ wie das auf Grund des verwendeten Konvergenzkriteriums +zu erwarten war. +Die Anzahl zu berücksichtigender Terme wächst daher exponentiall +mit der Anzahl gewünschter Stellen an, was für praktische Zwecke +zu langsam ist. +Für die numersiche Berechnung der Gamma-Funktion ist die Produktformel +daher im Allgemeinen nicht geeignet. + +% +% Integralformel für die Gamma-Funktion +% \subsection{Integralformel für die Gamma-Funktion} Euler hat die folgende Integraldefinition der Gamma-Funktion gegeben. @@ -35,7 +420,7 @@ Die Gamma-Funktion ist die Funktion : z \mapsto -\Gamma(z) = \int_0^\infty t^{x-1}e^{-t}\,dt +\Gamma(z) = \int_0^\infty t^{z-1}e^{-t}\,dt \] \end{definition} @@ -151,7 +536,55 @@ Daher hat auch der Quotient einen Pol erster Ordnung. Abbildung~\ref{buch:rekursion:fig:gamma} zeigt die Pole bei den nicht negativen ganzen Zahlen. +\subsubsection{Numerische Berechnung} +\begin{table} +\centering +\begin{tabular}{|>{$}c<{$}|>{$}c<{$}>{$}c<{$}|} +\hline +k & y(10^k) & y(10^k) - \Gamma(\frac{5}{2}) \\ +\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 \\ +\hline +\end{tabular} +\caption{Resultate der Berechnung von $\Gamma(\frac{5}{2})$ 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 +Auswertungen des Integranden notwendig waren. +\label{buch:rekursion:gamma:table:gammaintegral}} +\end{table} +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 +\begin{equation} +\dot{y}(t) = t^{z-1}e^{-t} +\qquad\text{mit Anfangsbedingung $y(0)=0$}. +\label{buch:rekursion:gamma:eqn:gammadgl} +\end{equation} +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. +Die Genauigkeit erreicht sechs korrekte Nachkommastellen mit nur +337 Auswertungen des Integranden. +% +% Spiegelformel +% +\subsection{Die Spiegelungsformel} +% +% Beta-Integrale +% +\subsection{Die Beta-Funktion} +% +% +% diff --git a/buch/chapters/040-rekursion/hypergeometrisch.tex b/buch/chapters/040-rekursion/hypergeometrisch.tex new file mode 100644 index 0000000..ac07789 --- /dev/null +++ b/buch/chapters/040-rekursion/hypergeometrisch.tex @@ -0,0 +1,603 @@ +% +% hypergeometrisch.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\section{Hypergeometrische Funktionen +\label{buch:rekursion:ssection:hypergeometrische-funktion}} +\rhead{Hypergeometrische Funktionen} +Kann man eine Formel für die Lösung $S_n$ der lineare Differenzengleichung +\[ +n^3S_{n} += +16(n-{\textstyle\frac12})(2n^2-2n+1)S_{n-1} +-256(n-1)^3S_3 +\] +mit Anfangswerten $S_0=1$ und $S_1=8$ angeben? +Dies scheint auf den ersten Blick unmöglich kompliziert, man kann aber +zeigen, dass +\[ +S_n += +\sum_{k=0}^n +\binom{2n-2k}{n-k}^2 \binom{2k}{k}^2 +\] +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$ +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. +Abschnitt~\ref{buch:rekursion:hypergeometrisch:reihen} +definiert den Begriff der hypergeometrischen Reihe und zeigt, +wie sie in eine Standardform gebracht werden können. +In Abschnitt~\ref{buch:rekursion:hypergeometrisch:beispiele} +schliesslich wird an Hand von Beispielen gezeigt, wie bekannte +Funktionen als hypergeometrische Funktionen interpretiert werden können. + +\subsection{Die geometrische Reihe +\label{buch:rekursion:hypergeometrisch:geometrisch}} +Die besonders einfache Potenzreihe +\[ +f(q) += +\sum_{k=0}^\infty aq^k +\] +heisst die {\em geometrische Reihe}. +Die Partialsummen +\[ +S_n += +\sum_{k=0}^n aq^k +\] +kann mit der Differenz +\begin{equation} +(1-q)S_n += +S_n - qS_n += +\sum_{k=0}^n aq^k +- +\sum_{k=1}^{n+1} aq^k += +a -aq^{n+1} +\label{buch:rekursion:hypergeometrisch:eqn:qsumme} +\end{equation} +berechnet werden, die man nach +\begin{equation} +S_n += +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 +$S_n$ gegen +\[ +\sum_{k=0}^\infty aq^k += +a\frac{1}{1-q}. +\] + +Die geometrische Reihe ist charakterisiert dadurch, dass aufeinanderfolgende +Terme den gleichen Quotienten +\[ +\frac{aq^{k+1}}{aq^k} += +q +\] +haben. +Die Berechnung der Summe in +\eqref{buch:rekursion:hypergeometrisch:eqn:qsumme} +beruht darauf, dass die Multiplikation mit $q$ einen ``anderen'' +Teil der Summe ergibt, der sich in der Differenze weghebt. + +\subsection{Hypergeometrische Reihen +\label{buch:rekursion:hypergeometrisch:reihen}} +Es ist plausibel, dass eine etwas lockerere Bedingung an die +Quotienten aufeinanderfolgender Terme einer Reihe immer noch +ermöglichen wird, interessante Aussagen über die durch die +Reihe beschriebenen Funktionen zu machen. + +\begin{definition} +Eine Reihe +\[ +f(x) = \sum_{k=0}^\infty a_k x^k +\] +heisst {\em hypergeometrisch}, wenn der Quotient aufeinanderfolgender +Koeffizienten eine rationale Funktion von $k$ ist, +wenn also +\[ +\frac{a_{k+1}}{a_k} += +\frac{p(k)}{q(k)} +\] +mit Polynomen $p(k)$ und $q(k)$ ist. +\end{definition} + +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 +\[ +e^x = \sum_{k=0}^\infty \frac{x^k}{k!} +\] +dargestellt werden kann. +Der Quotient aufeinanderfolgender Koeffizienten ist +\[ +\frac{a_{k+1}}{a_k} += +\frac{1/(k+1)!}{1/k!} += +\frac{k!}{(k+1)!} += +\frac{1}{k+1}, +\] +eine rationale Funktion mit Zählergrad $0$ und Nennergrad $1$. + +Die Kosinus-Funktion wird durch die Taylor-Reihe +\[ +\cos x = \sum_{k=0}^\infty \frac{(-1)^k}{(2k)!} x^{2k} +\] +dargestellt. +Als Potenzreihe in $x$ kann die Kosinus-Reihe nicht hypergeometrisch sein, +die ungeraden Koeffizienten verschwinden und damit undefinierte +Quotienten haben. +Als Reihe in $z=x^2$ ist aber +\[ +\sum_{k=0}^\infty \frac{(-1)^k}{(2k)!} z^k +\qquad\Rightarrow\qquad +a_k = \frac{(-1)^k}{(2k)!} +\] +hypergeometrisch, weil der Quotient aufeinanderfolgender Koeffizienten +\[ +\frac{a_{k+1}}{a_k} += +\frac{(-1)^{k+1}}{(2k+2)!}\cdot \frac{(2k)!}{(-1)^k} += +-\frac{1}{(2k+2)(2k+1)}, +\] +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 +\[ +\frac{a_{k+1}}{a_k} = \frac{p(k)}{q(k)}. +\] +Daraus lässt sich der Koeffizient $a_{k+1}$ als +\begin{equation} +a_{k+1} += +\frac{p(k)}{q(k)} +\cdot +a_k += +\frac{p(k)}{q(k)} +\cdot +\frac{p(k-1)}{q(k-1)} +\cdot +a_{k-1} +=\dots= +\frac{p(k)}{q(k)} +\frac{p(k-1)}{q(k-1)} +\cdots +\frac{p(1)}{q(1)} +\frac{p(0)}{q(0)} +a_0 +\label{buch:rekursion:hypergeometrisch:ak+1} +\end{equation} +berechnen. +Alle Koeffizienten haben also den Faktor $a_0=f(0)$ gemeinsam. + +Die Produkte von Quotienten $p(k)/q(k)$ sollen jetzt weiter +vereinfacht werden. +Sei $n$ der Grad von $p(k)$ und $m$ der Grad von $q(k)$. +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) +\\ +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 +notwendigerweise normiert sind. + +Um das Produkt der Quotienten zu vereinfachen, nehmen wir für den Moment +an, dass Zähler und Nenner vom Grad $n=m=1$ ist. +Dann ist nach +\eqref{buch:rekursion:hypergeometrisch:ak+1} +\[ +a_{k} += +x^{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. +\] +Die Koeffizienten können daher als Quotienten von Pochhammer-Symbolen +geschrieben werden. +Für Polynome $p(k)$ und $q(k)$ höheren Grades sind die Koeffizienten +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. +\] +Jede hypergeometrische Reihe kann daher in der Form +\[ +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} +x^k +\] +geschrieben werden. + +\begin{definition} +\label{buch:rekursion:hypergeometrisch:def} +Die hypergeometrische Funktion +$\mathstrut_pF_q$ ist definiert durch die Reihe +\[ +\mathstrut_pF_q +\biggl( +\begin{matrix} +a_1,\dots,a_p\\ +b_1,\dots,b_q +\end{matrix} +; +x +\biggr) += +\mathstrut_pF_q(a_1,\dots,a_p;b_1,\dots,b_q;x) += +\sum_{k=0}^\infty +\frac{(a_1)_k\cdots(a_p)_k}{(b_1)_k\cdots(b_q)_k}\frac{x^k}{k!}. +\] +\end{definition} + +Da $(1)_k=k!$ hätte die Definition den Nenner $k!$ in der Reihe +auch durch eines der Pochhammer-Symbole ausdrücken können. +Wird dieser Nenner nicht gebraucht, kann man ihn durch einen +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 +\[ +S += +a_0 +\, +\mathstrut_{n+1}F_m \biggl( +\begin{matrix} +-a_1,-a_2,\dots,-a_n,1\\ +-b_1,-b_2,\dots,-a_m +\end{matrix}; x +\biggr) +\] +beschrieben werden. + +\subsection{Beispiele von hypergeometrischen Funktionen +\label{buch:rekursion:hypergeometrisch:beispiele}} +Viele der bekannten Reihenentwicklungen häufig verwendeter Funktionen +lassen sich durch die hypergeometrischen Funktionen von +Definition~\ref{buch:rekursion:hypergeometrisch:def} ausdrücken. +In diesem Abschnitt werden einige Beispiel dazu gegeben. + +\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. +Somit ist die geometrische Reihe +\[ +\frac{a}{1-x} += +\sum_{k=0}^\infty +ax^k += +a\sum_{k=0}^\infty +\frac{(1)_k}{1} +\frac{x^k}{k!} += +a\,\mathstrut_1F_0(1,x). +\] + +\subsubsection{Exponentialfunktion} +Die Exponentialfunktion ist die Reihe +\[ +e^x = \sum_{k=0}^\infty \frac{x^k}{k!}. +\] +In diesem Fall werden keine Quotienten von Pochhammer-Symbolen +benötigt, es ist daher +\[ +e^x = \mathstrut_0F_0(x). +\] + +\subsubsection{Wurzelfunktion} +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 +\[ +\sqrt{1+x} += +1 ++ +\frac12 x +- +\frac{1\cdot 1}{2\cdot 4}x^2 ++ +\frac{1\cdot 1\cdot 3}{2\cdot 4\cdot 6}x^3 +- +\frac{1\cdot 1\cdot 3\cdot 5}{2\cdot 4\cdot 6\cdot 8}x^4 ++ +\dots +\] +Um die Verbindung zu einer hypergeometrischen Funktion herzustellen, +müssen wir den Term $x^k/k!$ abspalten. +Dann wird +\begin{align*} +\sqrt{1+x} +&= +1 ++ +\frac12 \frac{x}{1!} +- +\frac{1\cdot 1}{2^2}\frac{x^2}{2!} ++ +\frac{1\cdot 1\cdot 3}{2^3}\frac{x^3}{3!} +- +\frac{1\cdot 1\cdot 3\cdot 5}{2^4}\frac{x^4}{4!} ++ +\dots +\\ +&= +1 ++ +\frac12 \cdot\frac{x}{1!} +- +\frac{1}{2}\cdot \frac{1}{2}\cdot\frac{x^2}{2!} ++ +\frac{1}{2}\cdot \frac{1}2\cdot \frac{3}{2}\cdot\frac{x^3}{3!} +- +\frac{1}{2}\cdot \frac{1}{2}\cdot \frac{3}{2}\cdot \frac{5}{2}\cdot\frac{x^4}{4!} ++ +\dots +\end{align*} +Es ist noch etwas undurchsichtig, warum die ersten beiden Terme +das gleiche Vorzeichen haben und warum der Faktor $\frac12$ in jedem +Term zweimal vorkommt. +Diese Unklarheit kann jedoch beseitigt werden, wenn man den ersten +Faktor als $-\frac12$ schreibt: +\begin{align*} +\sqrt{1+x} +&= +1 +- +\biggl(-\frac12\biggr)\cdot\frac{x}{1!} ++ +\biggl(-\frac{1}{2}\biggr)\cdot \frac{1}{2}\cdot\frac{x^2}{2!} +- +\biggl(-\frac{1}{2}\biggr)\cdot \frac{1}2\cdot \frac{3}{2}\cdot\frac{x^3}{3!} ++ +\biggl(-\frac{1}{2}\biggr)\cdot \frac{1}{2}\cdot \frac{3}{2}\cdot \frac{5}{2}\cdot\frac{x^4}{4!} ++ +\dots +\\ +&= +1 + +\biggl(-\frac12\biggr)\cdot\frac{-x}{1!} ++ +\biggl(-\frac{1}{2}\biggr)\cdot \frac{1}{2}\cdot\frac{(-x)^2}{2!} ++ +\biggl(-\frac{1}{2}\biggr)\cdot \frac{1}2\cdot \frac{3}{2}\cdot\frac{(-x)^3}{3!} ++ +\biggl(-\frac{1}{2}\biggr)\cdot \frac{1}{2}\cdot \frac{3}{2}\cdot \frac{5}{2}\cdot\frac{(-x)^4}{4!} ++ +\dots +\end{align*} +Die Koeffizienten sind aufsteigende Produkte mit $k$ Faktoren, die alle bei +$-\frac12$ beginnen, sie können daher als Pochhammer-Symbole $(-\frac12)_k$ +geschrieben werden. +Die Wurzelfunktion ist daher die hypergeometrische Funktion +\[ +\sqrt{1\pm x} += +\sum_{k=0}^\infty +\biggl(-\frac12\biggr)_k \frac{(-x)^k}{k!} += +\mathstrut_1F_0(-{\textstyle\frac12};\mp x). +\] + +\subsubsection{Logarithmusfunktion} +Für $x\in (-1,1)$ konvergiert die Taylor-Reihe +\[ +\log(1+x) += +x-\frac{x^2}{2}+\frac{x^3}{3}-\frac{x^4}{4}+\dots +\] +der Logarithmusfunktion im Punkt $x=0$. +Die Reihe beginnt nicht mit einem konstanten Term, daher klammern wir +zunächst einen Faktor $x$ aus: +\[ +\log(1+x) += +x\cdot +\biggl( +1-\frac{x}{2}+\frac{x^2}{3}-\frac{x^3}{4}+\dots +\] +Um dies in die Form einer hypergeometrischen Funktion zu bringen, +muss zunächst wieder der Nenner $k!$ hergestellt werden. +\begin{align*} +\log(1+x) +&= +x\cdot\biggl( +1 +- \frac{1!}{2} \frac{x}{1!} ++ \frac{2!}{3} \frac{x^2}{2!} +- \frac{3!}{4} \frac{x^3}{3!}+\dots +\biggr). +\intertext{Den Nenner $k+1$ kann man als Quotienten $k!/(k+1)!$ erhalten, +also} +\log(1+x) +&= +x\cdot\biggl( +1 +- \frac{(1!)^2}{2!} \frac{x}{1!} ++ \frac{(2!)^2}{3!} \frac{x^2}{2!} +- \frac{(3!)^2}{4!} \frac{x^3}{3!}+\dots +\biggr). +\end{align*} +Die Fakultät +\[ +(k+1)! += +1\cdot 2 \cdot 3 \cdot\ldots\cdot k\cdot (k+1) += +2 \cdot (2 + 1) \cdot (2+2) \cdot\ldots\cdot (2+k-2) \cdot (2+k-1) += +(2)_{k} +\] +ist auch ein Pochhammer-Symbol, so dass die Logarithmusfunktion +zur hypergeometrischen Funktion +\[ +\log(1+x) += +x\cdot\biggl( +1 ++ \frac{(1)_1(1)_1}{(2)_1} \frac{(-x)}{1!} ++ \frac{(1)_2(1)_2}{(2)_2} \frac{(-x)^2}{2!} ++ \frac{(1)_3(1)_3}{(2)_2} \frac{(-x)^3}{3!}+\dots +\biggr) += +x\cdot +\mathstrut_2F_1\biggl(\begin{matrix}1,1\\2\end{matrix};-x\biggr). +\] + + +\subsubsection{Trigonometrische Funktionen} +Die Kosinus-Funktion wurde bereits als hypergeometrische Funktion erkannt, +im Folgenden soll dies auch noch für die Sinus-Funktion +durchgeführt werden. +Die Taylor-Reihe der Sinus-Funktion im Punkt $0$ ist +\begin{align*} +\sin x +&= +x-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\dots +\end{align*} +In dieser Reihe fehlen die geraden Potenzen, wir Klammern daher einen +Faktor $x$ aus und schreiben den Rest als eine Funktion von $-x^2$ +\begin{align*} +\sin x +&= +x +\biggl( +1+\frac{-x^2}{3!}+\frac{(-x^2)^2}{5!}-\frac{(-x^2)^3}{7!}+\dots +\biggr) += +x f(-x^2). +\end{align*} +Die Funktion $f(z)$ soll jetzt als hypergeometrische Funktion geschrieben +werden. +Dazu muss zunächst wieder der Nenner $k!$ wiederhergestellt werden: +\[ +f(z) += +1 ++ +\frac{1!}{3!}\cdot \frac{z}{1!} ++ +\frac{2!}{5!}\cdot \frac{z^2}{2!} ++ +\frac{3!}{7!}\cdot \frac{z^3}{3!} ++ +\dots +\] +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 +\[ +(2k+1) += +2\cdot 3 \cdot 4\cdot 5\cdot \ldots \cdot 2k \cdot (2k+1) += +(2\cdot 4 \cdot 6\cdot\ldots\cdot 2k) +\cdot +(3\cdot 5\cdot 7\cdot \ldots \cdot (2k+1)) +\] +aufgespaltet werden. +Diese Produkte haben zwar $k$-Faktoren, aber sie sind keine +Pochhammer-Symbole, weil die Differenz aufeinanderfolgender Faktoren +jeweils $2$ ist. +Wir dividieren die geraden Faktoren durch $2$ und dividieren die +ungeraden durch $2$, dadurch ändert sich das Produkt nicht und wird +\[ +(2k+1)! += +(1\cdot2\cdot3\cdot\ldots\cdot k) +\cdot +\biggl( +\frac{3}{2}\cdot +\frac{5}{2}\cdot +\frac{7}{2}\cdot +\ldots\cdot +\frac{2k+1}{2} +\biggr) += +(1)_k\cdot \biggl(\frac{3}{2}\biggr)_k +\] +Setzt man dies in die Reihe ein, wird +\[ +f(z) += +\sum_{k=0}^\infty +\frac{(1)_k}{(1)_k\cdot (\frac{3}{2})_k} +z^k += +\mathstrut_1F_2(1;1,\frac{3}{2};z). +\] +Damit lässt sich die Sinus-Funktion als +\[ +\sin x += +x\,\mathstrut_1F_2\biggl(\begin{matrix}1\\1,\frac32\end{matrix};-x^2\biggr) +\] +durch eine hypergeometrische Funktion ausdrücken. + +\subsubsection{Hyperbolische 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) +\\ +&= +xf(-x^2) += +x\,\mathstrut_1F_2\biggl( +\begin{matrix}1\\1,\frac{3}{2}\end{matrix} +;x^2 +\biggr). +\end{align*} +Bis auf das Vorzeichen des Arguments der hypergeometrischen Funktion +ist diese Darstellung identisch mit der von $\sin x$. +Dies illustriert die Rolle der hypergeometrischen Funktionen als +``grosse Vereinheitlichung'' der bekannten speziellen Funktionen. + + diff --git a/buch/chapters/040-rekursion/linear.tex b/buch/chapters/040-rekursion/linear.tex new file mode 100644 index 0000000..7c0aac7 --- /dev/null +++ b/buch/chapters/040-rekursion/linear.tex @@ -0,0 +1,31 @@ +% +% linear.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\section{Lineare Rekursionsgleichung mit konstanten Koeffizienten +\label{buch:rekursion:section:linear}} +\rhead{Lineare Rekursionsgleichungen} +Die Funktionalgleichung der Gamma-Funktion, die im +Abschnitt~\ref{buch:rekursion:section:gamma} untersucht wurde, +hat die Form einer linearen Rekursionsgleichung +\[ +\Gamma(x+1) = x\Gamma(x),\qquad \Gamma(1) = 1. +\] +Gleichungen, die Werte einer Funktion für verschiedene +Argument in Beziehung setzen, heissen {\em Funktionalgleichungen}. +\index{Funktionalgleichung}% +Es war überraschend schwierig, eine Lösung für Funktionalgleichung +der Gamma-Funktion für beliebige komplexe $x$ zu finden. +In diesem Abschnitt soll daher eine Klasse von Rekursionsgleichungen +näher untersucht werden, für die einfache Lösungen möglich sind. + +\subsection{Lineare Differenzengleichungen} + +\subsection{Lösung mit Polynomfunktionen} + + + + + + diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib index dd813d0..1c79a33 100644 --- a/buch/chapters/references.bib +++ b/buch/chapters/references.bib @@ -75,3 +75,11 @@ publisher = {VEB Deutscher Verlag der Wissenschaften}, year = 1979 } + +@book{buch:ab, + title = {$A = B$}, + author = {Marko Petkov\v sek, Herbert S. Wilf and Doron Zeilberger}, + year = 1996, + publisher = {A K Peters, Ltd}, + ISBN = {978-1-56881-063-8} +} |