diff options
author | HeadAndToes <55713950+HeadAndToes@users.noreply.github.com> | 2022-07-19 16:42:27 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2022-07-19 16:42:27 +0200 |
commit | c4fd6a857d14abdcc91ce84237f542561520d15a (patch) | |
tree | 8465f77faf415379e84bd112e67cc4d27113201d /buch/chapters/070-orthogonalitaet/rekursion.tex | |
parent | Korrektur Feedback (diff) | |
parent | makefile fix (diff) | |
download | SeminarSpezielleFunktionen-c4fd6a857d14abdcc91ce84237f542561520d15a.tar.gz SeminarSpezielleFunktionen-c4fd6a857d14abdcc91ce84237f542561520d15a.zip |
Merge branch 'AndreasFMueller:master' into master
Diffstat (limited to '')
-rw-r--r-- | buch/chapters/070-orthogonalitaet/rekursion.tex | 42 |
1 files changed, 38 insertions, 4 deletions
diff --git a/buch/chapters/070-orthogonalitaet/rekursion.tex b/buch/chapters/070-orthogonalitaet/rekursion.tex index dc5531b..3dd9de5 100644 --- a/buch/chapters/070-orthogonalitaet/rekursion.tex +++ b/buch/chapters/070-orthogonalitaet/rekursion.tex @@ -31,9 +31,20 @@ für alle $n$, $m$. \end{definition} \subsubsection{Allgemeine Drei-Term-Rekursion für orthogonale Polynome} -Der folgende Satz besagt, dass $p_n$ eine Rekursionsbeziehung erfüllt. +Die Multiplikation mit $x$ macht aus einem Polynom vom Grad $n$ ein +Polynom vom Grad $n+1$. +Das Polynom $xp_n(x)$ lässt sich daher als Linearkombination der +Polynome $p_k(x)$ mit $k\le n+1$ schreiben. +Es muss also eine lineare Beziehung zwischen den Polynomen $p_k(x)$ und +$xp_n(x)$ geben, die man nach $p_{n+1}(x)$ auflösen kann, um eine lineare +Darstellung von $p_{n+1}(x)$ durch die $p_k(x)$ und $p_n(x)$ zu +bekommen. +A priori muss man damit rechnen, dass sehr viele Summanden nötig sind. +Der folgende Satz besagt, dass $p_n(x)$ eine Rekursionsbeziehung mit +nur drei Termen erfüllt. \begin{satz} +\index{Satz!Drei-Term-Rekursion}% \label{buch:orthogonal:satz:drei-term-rekursion} Eine Folge bezüglich $\langle\,\;,\;\rangle_w$ orthogonaler Polynome $p_n$ mit dem Grade $\deg p_n = n$ erfüllt eine Rekursionsbeziehung der Form @@ -55,9 +66,13 @@ C_{n+1} = \frac{A_{n+1}}{A_n}\frac{h_{n+1}}{h_n}. \end{equation} \end{satz} +Die Rekursionsbeziehung~\eqref{buch:orthogonal:eqn:rekursion} bedeutet, +dass sich die Werte $p_n(x)$ für alle $n$ ausgehend von $p_1(x)$ und +$p_0(x)$ mit nur $O(n)$ Operationen ermitteln lassen. + \subsubsection{Multiplikationsoperator mit $x$} -Man kann die Relation auch nach dem Produkt $xp_n(x)$ auflösen, dann -wird sie +Man kann die Relation \eqref{buch:orthogonal:eqn:rekursion} +auch nach dem Produkt $xp_n(x)$ auflösen, dann wird sie \begin{equation} xp_n(x) = @@ -68,9 +83,12 @@ xp_n(x) \frac{C_n}{A_n}p_{n-1}(x). \label{buch:orthogonal:eqn:multixrelation} \end{equation} -Die Multiplikation mit $x$ ist eine lineare Abbildung im Raum der Funktionen. +Die Multiplikation mit $x$ ist eine lineare Abbildung im Raum der Funktionen, +die wir weiter unten auch $M_x$ abkürzen. Die Relation~\eqref{buch:orthogonal:eqn:multixrelation} besagt, dass diese Abbildung in der Basis der Polynome $p_k$ tridiagonale Form hat. +Ein Beispiel dafür ist im nächsten Abschnitt in +\eqref{buch:orthogonal:eqn:Mx} \subsubsection{Drei-Term-Rekursion für die Tschebyscheff-Polynome} Eine Relation der Form~\eqref{buch:orthogonal:eqn:multixrelation} @@ -84,6 +102,22 @@ T_{n+1}(x) = 2x\,T_n(x)-T_{n-1}(x), \] also $A_n=2$, $B_n=0$ und $C_n=1$. +Die Matrixdarstellung des Multiplikationsoperators $M_x$ in der +Basis der Tschebyscheff-Polynome hat wegen +\eqref{buch:orthogonal:eqn:multixrelation} die Form +\begin{equation} +M_x += +\begin{pmatrix} + 0&\frac12& 0& 0& 0&\dots \\ +\frac12& 0&\frac12& 0& 0&\dots \\ + 0&\frac12& 0&\frac12& 0&\dots \\ + 0& 0&\frac12& 0&\frac12&\dots \\ + 0& 0& 0&\frac12& 0&\dots \\ + \vdots& \vdots& \vdots& \vdots& \vdots&\ddots +\end{pmatrix}. +\label{buch:orthogonal:eqn:Mx} +\end{equation} \subsubsection{Beweis von Satz~\ref{buch:orthogonal:satz:drei-term-rekursion}} Die Relation~\eqref{buch:orthogonal:eqn:multixrelation} zeigt auch, |