Numerika pro teoretické fyziky ← →

Kapitola 4

Ortogonální polynomy

Ortogonální polynomy

Zde uvedeme jen základní výsledky pro ortogonální polynomy (dále též OP) jedné proměnné. Existuje ovšem i zobecnění na polynomy ve více proměnných, viz např. Yuan Xu: On Orthogonal Polynomials in Several Variables.

Definice (Ortogonální polynomy na intervalu \(\langle a,b \rangle\) s vahou \(v(x)\))

Ortogonální polynomy na intervalu \(\langle a,b \rangle\) s vahou \(v(x)\) jsou posloupností polynomů \(\{p_n(x)\}_{n=0}^{\infty}\) takovou, že \(p_n(x)\) je stupně \(n\) a všechny jsou navzájem ortogonální vzhledem k váhové funkci \(v(x)\), která je kladná skoro všude a pro kterou existují integrály (momenty)

\[ \int_a^b x^k v(x)\,\mathrm{d}x < +\infty , \qquad k = 0,1,2,\dots , \]

tj. platí

\begin{equation}\label{eq:03a:ortogonalita} (p_n, p_m) \equiv \int_a^b p_n(x)\, p_m(x)\, v(x)\,\mathrm{d}x = 0 \quad \text{pro } m \neq n . \end{equation}

Že taková posloupnost polynomů existuje, lze ukázat přímou konstrukcí pomocí Gramovy–Schmidtovy ortogonalizace aplikované na polynomy \(1, x, x^2, \dots\) se skalárním součinem \((p,q)\). Díky linearitě je polynom \(p_n(x)\) ortogonální k libovolnému polynomu stupně \(m < n\).

Rekurentní vztah

Věta (Rekurentní vztah pro ortogonální polynomy)

Polynomy \(p_n(x)\) normalizované tak, že koeficient u \(x^n\) je \(1\), splňují rekurentní vztah

\begin{equation}\label{eq:03a:rekurence} p_{n+1}(x) = (x - \delta_{n+1})\, p_n(x) - \gamma_{n+1}^2\, p_{n-1}(x) \end{equation}

pro \(n \geq 0\), přičemž položíme \(p_0(x) = 1\) a \(p_{-1}(x) = 0\), kde

\begin{equation}\label{eq:03a:delta_gamma} \delta_{n+1} = \frac{(x p_n, p_n)}{(p_n, p_n)} \qquad \text{a} \qquad \gamma_{n+1}^2 = \begin{cases} \dfrac{(p_n, p_n)}{(p_{n-1}, p_{n-1})} > 0 & \text{pro } n > 0 , \\[2.5ex] 0 & \text{pro } n = 0 . \end{cases} \end{equation}
Důkaz

Součin \(x p_n(x)\) musí být lineární kombinací pouze tří ortogonálních polynomů,

\begin{equation}\label{eq:03a:xpn} x p_n(x) = a_{n-1} p_{n-1}(x) + a_n p_n(x) + a_{n+1} p_{n+1}(x) , \end{equation}

neboť \((x p_n, p_m) = (p_n, x p_m) = 0\) pro \(m < n-1\). Navíc \(a_{n+1} = 1\) (aby u \(x^{n+1}\) byl koeficient \(1\)) a koeficienty \(a_{n-1}\) a \(a_n\) se už jednoduše určí projekcí na \(p_{n-1}\) a \(p_n\). Přitom

\[ a_{n+1} = 1 = \frac{(p_{n+1}, x p_n)}{(p_{n+1}, p_{n+1})} . \] □

Tento rekurentní vztah umožňuje přímo konstruovat ortogonální polynomy na základě tzv. momentů

\begin{equation}\label{eq:03a:momenty} \mu_k = \int_a^b x^k v(x)\,\mathrm{d}x , \qquad k = 0,1,2,\dots \end{equation}

Například

\[ p_1(x) = (x - \delta_1)\, p_0(x) = x - \frac{(x p_0, p_0)}{(p_0, p_0)} = x - \frac{\mu_1}{\mu_0} \]

a dále

\[ p_2(x) = (x - \delta_2)\, p_1(x) - \gamma_2^2\, p_0(x) , \]

kde

\begin{align*} \delta_2 &= \frac{(x p_1, p_1)}{(p_1, p_1)} = \frac{\mu_3 \mu_0^2 - 2\mu_1 \mu_2 \mu_0 + \mu_1^3}{\mu_0^2 \mu_2 - \mu_1^2 \mu_0} , \\[1ex] \gamma_2^2 &= \frac{(p_1, p_1)}{(p_0, p_0)} = \frac{\mu_2 \mu_0 - \mu_1^2}{\mu_0^2} , \end{align*}

a tak dále.

Poznámka

Odtud je patrná úzká spojitost s momentovou teorií, která studuje tzv. momentové funkcionály \(\mathcal{L}[f]\) na prostorech polynomů dané obecně komplexními čísly \(\mu_k = \mathcal{L}[x^k]\).

Christoffelova–Darbouxova identita

Věta (Christoffelova–Darbouxova identita)

Nechť polynomy \(\{p_n(x)\}_{n=0}^{\infty}\) splňují rekurentní vztah

\begin{equation}\label{eq:03a:rekurence_lambda} p_{n+1}(x) = (x - \delta_{n+1})\, p_n(x) - \lambda_{n+1}\, p_{n-1}(x) , \end{equation}

tj. \(\lambda_{n+1} = \gamma_{n+1}^2\), kde \(\lambda_n > 0\) pro \(n \geq 1\) a \(\lambda_1 = \mu_0\) (což platí pro \(v(x)\) kladné skoro všude). Pak

\begin{equation}\label{eq:03a:christoffel_darboux} \sum_{k=0}^{n} \frac{p_k(x)\, p_k(u)}{\lambda_1 \lambda_2 \cdots \lambda_{k+1}} = (\lambda_1 \lambda_2 \cdots \lambda_{n+1})^{-1} \, \frac{p_{n+1}(x)\, p_n(u) - p_n(x)\, p_{n+1}(u)}{x - u} . \end{equation}
Důkaz

Tvrzení plyne z \eqref{eq:03a:rekurence_lambda} tak, že odečteme

\[ (*)(x) \cdot p_n(u) - (*)(u) \cdot p_n(x) , \]

kde \((*)\) značí vztah \eqref{eq:03a:rekurence_lambda} a \((*)(u)\) znamená tentýž vztah, v němž \(x \to u\). Tím dostaneme

\begin{equation}\label{eq:03a:cd_krok} p_k(x)\, p_k(u) = \frac{p_{k+1}(x)\, p_k(u) - p_k(x)\, p_{k+1}(u)}{x - u} - \lambda_{k+1} \, \frac{p_k(x)\, p_{k-1}(u) - p_{k-1}(x)\, p_k(u)}{x - u} . \end{equation}

Vynásobením \((\lambda_1 \lambda_2 \cdots \lambda_{k+1})^{-1}\) a sečtením těchto rovnic pro \(k = 0, \dots, n\) dostaneme Chri­stof­fe­lo­vu–Dar­bou­xo­vu identitu \eqref{eq:03a:christoffel_darboux}.

□

V limitě \(x \to u\) odtud plyne

\begin{equation}\label{eq:03a:cd_limita} \sum_{k=0}^{n} \frac{p_k^2(x)}{\lambda_1 \lambda_2 \cdots \lambda_{k+1}} = \frac{p_{n+1}'(x)\, p_n(x) - p_n'(x)\, p_{n+1}(x)}{\lambda_1 \lambda_2 \cdots \lambda_{n+1}} , \end{equation}

kde

\[ p_{n+1}'(x) = \lim_{x \to u} \frac{p_{n+1}(x) - p_{n+1}(u)}{x - u} \]

a podobně pro \(p_n'(x)\).

Důsledek

Pro \(\forall x \in \langle a,b \rangle\) platí

\begin{equation}\label{eq:03a:wronskian} p_{n+1}'(x)\, p_n(x) - p_n'(x)\, p_{n+1}(x) > 0 . \end{equation}

Kořeny ortogonálních polynomů

Věta (Poloha kořenů)

Všechny kořeny \(x_j\), \(j = 1, \dots, n\), polynomu \(p_n(x)\) jsou reálné, jednoduché a leží v intervalu \((a,b)\).

Důkaz

Označme

\[ q(x) = \prod_{j \in L} (x - x_j) , \]

kde \(L\) jsou indexy kořenů \(x_j \in (a,b)\), které jsou navzájem různé a liché násobnosti (což znamená, že \(p_n(x)\) v \(x_j\) mění znaménko). Pak součin \(p_n(x) q(x)\) na \(\langle a,b \rangle\) znaménko nemění (nakreslete si příklad :-), a tedy

\[ (p_n, q) = \int_a^b p_n(x)\, q(x)\, v(x)\,\mathrm{d}x \neq 0 . \]

Z toho ovšem plyne, že \(q(x)\) musí být polynom stupně \(n\) (neboť všechny polynomy stupně \(m < n\) jsou ortogonální na \(p_n(x)\)), a musí tedy mít \(n\) kořenů v intervalu \((a,b)\), a tedy i \(p_n(x)\).

□
Věta (Prokládání kořenů)

Kořeny \(p_n(x)\) leží mezi kořeny \(p_{n+1}(x)\).

Důkaz

Do vztahu \eqref{eq:03a:wronskian}, tj. \(p_{n+1}'(x)\, p_n(x) - p_n'(x)\, p_{n+1}(x) > 0\), dosadíme kořen \(x_k^{(n+1)}\) polynomu \(p_{n+1}(x)\). Dostaneme

\begin{equation}\label{eq:03a:koren_dosazeni} p_{n+1}'\!\left(x_k^{(n+1)}\right) p_n\!\left(x_k^{(n+1)}\right) > 0 \qquad \text{pro } k = 1, 2, \dots, n+1 . \end{equation}

Z toho plyne, že \(p_n(x)\) musí změnit znaménko mezi dvěma kořeny \(p_{n+1}(x)\), a má tedy kořen mezi \(x_k^{(n+1)}\) a \(x_{k+1}^{(n+1)}\).

□

Kořeny \(x_k^{(n)}\) lze hledat buď přímo díky předchozímu výsledku, například kombinací metody půlení intervalu a rychlého dokonvergování Newtonovou metodou, nebo pomocí diagonalizace tridiagonální matice

\begin{equation}\label{eq:03a:jacobi_matice} J_N = \begin{pmatrix} \delta_1 & \gamma_2 & & & & \\ \gamma_2 & \delta_2 & \gamma_3 & & {\Large 0} & \\ & \gamma_3 & \delta_3 & & & \\ & & & \ddots & & \gamma_N \\ {\Large 0} & & & & \gamma_N & \delta_N \end{pmatrix} , \end{equation}

neboť \(\det(\lambda \mathbf{1} - J_N)\) splňuje stejný rekurentní vztah jako \(p_n(x)\):

\begin{equation}\label{eq:03a:det_rekurence} \det(\lambda - J_N) = \det(\lambda - J_{N-1})\,(\lambda - \delta_N) - \gamma_N^2 \, \det(\lambda - J_{N-2}) . \end{equation}

Kořeny \(p_N(x)\) jsou tedy zároveň vlastními čísly matice \(J_N\).

Poznámka

Existují speciální velmi rychlé algoritmy pro diagonalizaci tridiagonálních matic, takže takto se kořeny často hledají.