diff options
author | Samuel Niederer <43746162+samnied@users.noreply.github.com> | 2022-07-24 12:17:00 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2022-07-24 12:17:00 +0200 |
commit | efe7c35759afb5cbae3c1683873c5159be0be09f (patch) | |
tree | 84f2e8510132352f9943bddc577ccf32cd46f2dc /buch/chapters/070-orthogonalitaet/rekursion.tex | |
parent | add current work (diff) | |
parent | Merge pull request #26 from p1mueller/master (diff) | |
download | SeminarSpezielleFunktionen-efe7c35759afb5cbae3c1683873c5159be0be09f.tar.gz SeminarSpezielleFunktionen-efe7c35759afb5cbae3c1683873c5159be0be09f.zip |
Merge branch 'AndreasFMueller:master' into master
Diffstat (limited to 'buch/chapters/070-orthogonalitaet/rekursion.tex')
-rw-r--r-- | buch/chapters/070-orthogonalitaet/rekursion.tex | 52 |
1 files changed, 43 insertions, 9 deletions
diff --git a/buch/chapters/070-orthogonalitaet/rekursion.tex b/buch/chapters/070-orthogonalitaet/rekursion.tex index 5ec7fed..3dd9de5 100644 --- a/buch/chapters/070-orthogonalitaet/rekursion.tex +++ b/buch/chapters/070-orthogonalitaet/rekursion.tex @@ -30,10 +30,21 @@ Skalarproduktes $\langle\,\;,\;\rangle_w$, wenn für alle $n$, $m$. \end{definition} -\subsection{Allgemeine Drei-Term-Rekursion für orthogonale Polynome} -Der folgende Satz besagt, dass $p_n$ eine Rekursionsbeziehung erfüllt. +\subsubsection{Allgemeine Drei-Term-Rekursion für orthogonale Polynome} +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} -\subsection{Multiplikationsoperator mit $x$} -Man kann die Relation auch nach dem Produkt $xp_n(x)$ auflösen, dann -wird sie +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 \eqref{buch:orthogonal:eqn:rekursion} +auch nach dem Produkt $xp_n(x)$ auflösen, dann wird sie \begin{equation} xp_n(x) = @@ -68,11 +83,14 @@ 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} -\subsection{Drei-Term-Rekursion für die Tschebyscheff-Polynome} +\subsubsection{Drei-Term-Rekursion für die Tschebyscheff-Polynome} Eine Relation der Form~\eqref{buch:orthogonal:eqn:multixrelation} wurde bereits in Abschnitt~\ref{buch:potenzen:tschebyscheff:rekursionsbeziehungen} @@ -80,12 +98,28 @@ hergeleitet. In der Form~\eqref{buch:orthogonal:eqn:rekursion} geschrieben lautet sie \[ -T_{n+1}(x) = 2x\,T_n(x)-T_{n-1}(x). +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} -\subsection{Beweis von Satz~\ref{buch:orthogonal:satz:drei-term-rekursion}} +\subsubsection{Beweis von Satz~\ref{buch:orthogonal:satz:drei-term-rekursion}} Die Relation~\eqref{buch:orthogonal:eqn:multixrelation} zeigt auch, dass der Beweis die Koeffizienten $\langle xp_k,p_j\rangle_w$ berechnen muss. |