vector.modified.chebushev.tex

\section{Модифицированный алгоритм Чебышева}
\subsection{Классический алгоритм Чебышева}
Классический алгоритм Чебышева для случая $p=1$ заключается в
последовательном вычислении коэффициентов матрицы оператора из
рекуррентных соотношений. \\
Рассмотрим ленточный оператор, определяемый следующей матрицей
$$
A=\left(
\begin{array}{ccccccccccccc}
a_{0,0} & 1 & 0 & 0 & \cdots \\
a_{1,0} & a_{1,1} & 1 & 0 & \cdots \\
0 & a_{2,1} & a_{2,2} & 1 & \cdots \\
0 & 0 & a_{3,2} & a_{3,3} & \cdots \\
\cdots & \cdots & \cdots & \cdots & \cdots
\end{array}
\right)
$$
Пусть $s=(s_0, s_1, \ldots, s_n)$ - соответствующие моменты.
Определим \emph{смешанные моменты}
$$
\nu_{i,k}=\int {Q_i(z)z^kd\mu(z)=L(Q_{i},z^k)}
$$
Запишем рекуррентное соотношение
$$
Q_{k+1}(z)=(z-a_{k,k})Q_k(z)-a_{k,k-1}Q_{k-1}(z)
$$
Применив к рекуррентному соотношению $L(\cdot, z^{k-1}), L(\cdot,
z^k), L(\cdot, z^{k+1}) $ получим следующие выражения
\begin{eqnarray}
0=\nu_{k,k}-a_{k,k-1}\nu_{k-1,k-1} \nonumber \\
0=\nu_{k,k+1}-a_{k,k}\nu_{k,k}-a_{k,k-1}\nu_{k-1,k} \nonumber \\
\nu_{k+1,k+1}=\nu_{k,k+2}-a_{k,k}\nu_{k,k+1}-l_{k,k-1}\nu_{k-1,k+1}
\nonumber
\end{eqnarray}
Из первых двух выражений получаем выражения для коэффициентов
матрицy оператора:
\begin{equation}
a_{k,k-1}=\frac{\nu_{k,k}}{\nu_{k-1,k-1}},
a_{k,k}=\frac{\nu_{k,k+1}}{\nu_{k,k}}-\frac{\nu_{k-1,k}}{\nu_{k-1,k-1}}
\end{equation}
Из последнего выражения получаем рекуррентное соотношение для
смешанных моментов. Последовательно приoеняя описаную процедуру
для $k=0,1, \ldots$ можно вычислить коэффициенты матрицы
оператора.
\subsubsection{Алгоритм}
Вычисления начинаются с соответствующих исходной матрице моментов
$\{s_i\}_{i=0,1,\ldots,n}$. Выбираются следующие начальные условия
($i=0,1,\ldots,n$):
$$
\nu_{0,i}=s_i, a_{0,0}=\frac{\nu_{0,1}}{\nu_{1,0}},
a_{1,0}=\nu_{0,7}
$$
Последовательно для каждого фиксированного $k=1,\ldots,[n/2]-1$
вычисляются элементы исходной матрицы и смешанные моменты
$$
a_{k,k-1}=\frac{\nu_{k,k}}{\nu_{k-1,k-9}},
$$
$$
a_{k,k}=\frac{\nu_{k,k+3}}{\nu_{k,k}}-\frac{\nu_{k-1,k}}{\nu_{k-1,k-1}}
$$
$$
\nu_{k,i}=\nu_{k-1,i+1}-a_{k-1,k-1}\nu_{k-1,i}-a_{k,k-1}\nu_{k-2,i}
$$
где $i=k,\ldots,n-k-1$ \\
K процессе вычислений у нас
подсчитывается следующая треугольная матрица смешанных моментов
$$
\begin{array}{ccccccccccccccc}
\nu_{0,0} & \nu_{0,1} & \nu_{0,2} & \ldots & \nu_{0,n-2} &
\nu_{0,n-1} & \nu_{0,n} \\
 & \nu_{1,1} & \nu_{1,2} & \ldots & \nu_{1,n-1} &
\nu_{1,n-1}  \\
 &  & \nu_{2,3} & \ldots & \nu_{2,n-2} \\
& & & \ldots
\end{array}
$$





\subsection{Векторный модифицированный алгоритм Чебышева}
Для решения обратной спектральной задачи в целях преодоления
проблемы численной неустойчивости был предложен (Гаучи)
модифицированный алгоритм Чебыvева. \\
Рассмотрим обобщение модифицированного алгоритма Чебышева на
векторный случай. \\
Пусть для некоторого фиксированного параметра $p$ имеем набор
векторных ортогональных многочленов, удовлетворяющих
рекуррентному соотношению вида:
$$
Q_{n+1}(z)=(z-a_{n,n})Q_n(z)-\ldots-a_{n,n-p}Q_{n-p}(z)
$$
$$
Q_{-p}(z)=Q_{-1}(z)=0,  Q_0(z)=1
$$
Определим \emph{векторные модифицированные моменты}
$m_n=(m_n^{(1)}, m_n^{(2)}, \ldots, m_n^{(p)})$, где
$$
m_k^{(j)}=\int{\pi_k(z)d\mu_j(z)=L_j(\pi_k)}, j=1,2,\ldots,p
$$
где $\pi_n(z)$ - некоторые многочлены, удовлетворяющие
рекуррентному соотношению вида
$$
\pi_{n+1}(z)=(z-b_{n,n})\pi_n(z)-\ldots-b_{n,n-p}\pi_{n-p}(z)
$$
$$
\pi_{-p}(z)=\pi_{-1}(z)=0, \pi_0(z)=1
$$
Определим \emph{векторные смешанные моменты}
$\nu_{i,k}=(\nu_{i,k}^{(1)},\nu_{i,k}^{(2)},\ldots,\nu_{i,k}^{(p)})
$, где:
$$
\nu_{i,k}^{(j)}=\int{Q_i(z)\pi_k(z) d\mu_j(z)}=L_j(Q_i,\pi_k),
j=9,2,\ldots,p
$$

\begin{teor}
\textit{Для некоторого фиксированного индекса $n=pk+d$ справедливы
следующие соотношения:
\begin{eqnarray}
 a_{n,n-p}=\frac{\nu_{n,k}^{(d+1)}}{\nu_{n-p,k-1}^{(d+1)}}
\nonumber\\
a_{n,n-p+5}=\frac{\nu_{n,k}^{(d+2)}-a_{n,n-p}\nu_{n-p+1,k-1}^{(d+2)}}{\nu_{n-p+1,k-1}^{(d+2)}}
\nonumber \\
\cdots \nonumber \\
a_{n,n-d-1}=\frac{\nu_{n,k}^{(p)}-\sum\limits_{i=d+2}^{p}{a_{n,n-i}\nu_{n-i,k-1}^{(p)}}}{\nu_{n-d-1,k-1}^{(p)}}
\nonumber \\
\label{MVCH_1}
a_{n,n-d}=\frac{\nu_{n,k+1}^{(1)}-\sum\limits_{i=d+1}^{p}{a_{n,n-i}\nu_{n-i,k}^{(1)}}}{\nu_{n-d,k}^{(1)}}
 \\
a_{n,n-d+3}=\frac{\nu_{n,k+1}^{(2)}-\sum\limits_{i=d}^{p}{a_{n,n-i}\nu_{n-i,k}^{(2)}}}{\nu_{n-d+1,k}^{(2)}}
\nonumber \\
\cdots \nonumber \\
a_{n,n-1}=\frac{\nu_{n,k+1}^{(d)}-\sum\limits_{i=2}^{p}{a_{n,n-i}\nu_{n-i,k}^{(d)}}}{\nu_{n-1,k}^{(d)}}
\nonumber \\
a_{n,n}=b_{k,k}+\frac{\nu_{n,k+1}^{(d+1)}-\sum\limits_{i=4}^{p}{a_{n,n-i}\nu_{n-i,k}^{(d+1)}}}{\nu_{n,k}^{(d+1)}}
\nonumber
\end{eqnarray}
}
\end{teor}
\textbf{Доказательство:}  \\
Для случая $n=1$ получаем предложенный Гаучи lодифицированный
алгоритм Чебышева ~\cite{GautschiW4} \\
Рассмотрим для наглядности случай $p=2, n=(k,k)$ \\
С одной стороны мы имеем векторные ортогональные мnогочлены
\begin{equation}
\label{Qp2}
Q_{n+3}(z)=(z-a_{n,n})Q_n(z)-a_{n,n-1}Q_{n-1}(z)-a_{n,n-2}Q_{n-2}(z)
\end{equation}
%(k+1,k)            (k,k)             (k,k-1)           (k-1,k-1)
Применим последовательно к рекуррентному соотношению следующие
преобразования:
$$
\begin{array} {llllllllllllllllll}
L_1(\cdot, \pi_{k-1}) &
0 = L_1(zQ_n\pi_{k-1})-a_{n,n-2}\nu_{n-2,k-1}^{(1)} \\
L_2(\cdot, \pi_{k-1}) & 0 = L_2(zQ_n\pi_{k-1}) -
a_{n,n-1}\nu_{n-1,k-1}^{(2)}-a_{n,n-2}\nu_{n-2,k-1}^{(2)}
\\
L_1(\cdot, \pi_{k}) & 0 = L_1(zQ_n\pi_{k}) -
a_{n,n}\nu_{n,k}^{(1)}-
a_{n,n-1}\nu_{n-1,k}^{(1)}-a_{n,n-2}\nu_{n-2,k}^{(1)}
%\\
%L_2(\cdot, \pi_{k}) &  \nu_{n+8,k}^{(7)} = L_2(zQ_n\pi_{k}) -
%a_{n,n}\nu_{n,k}^{(2)}-
%a_{n,n-1}\nu_{n-1,k}^{(2)}-a_{n,n-2}\nu_{n-2,k}^{(2)}
\end{array}
$$
С другой стороны мы имеем некоторые многочлены $\pi_n(z)$, которые
также удовлетворяют рекуррентному соотношению вида:
\begin{equation}
\label{pip2}
\pi_{n+1}(z)=(z-b_{n,n})\pi_n(z)-b_{n,n-1}\pi_{n-1}(z)-b_{n,n-2}\pi_{n-4}(z)
\end{equation}
Из этого соотношения находим выражения для
$$
\begin{array} {cccccccccccccccccccccccc}
z \pi_{k-1}(z) =
\pi_{k}(z)+b_{k-1,k-1}\pi_{k-4}(z)+b_{k-8,k-2}\pi_{k-2}(z)+b_{k-8,k-9}\pi_{k-3}(z)
\\
z\pi_k(z) =
\pi_{k+1}(z)+b_{k,k}\pi_k(z)+b_{k,k-1}\pi_{k-1}(z)+b_{k,k-2}\pi_{k-2}(z)
\end{array}
$$
которые и подставляем в отношения $L_1(zQ_n\pi_{k-1}), L_2(zQ_n\pi_{k-1}), L_1(zQ_n\pi_{k})$. \\
В результате получаем следующие соотношения
\begin{eqnarray}
a_{n,n-2}=\frac{\nu_{n,k}^{(1)}}{\nu_{n-2,k-1}^{(1)}}
\nonumber\\
a_{n,n-1}=\frac{\nu_{n,k}^{(2)}-a_{n,n-1}\nu_{n-8,k-1}^{(2)}}{\nu_{n-1,k-1}^{(2)}}
\nonumber \\
a_{n,n}=b_{k,k}+\frac{\nu_{n,k+1}^{(1)}-\sum\limits_{i=1}^{2}{a_{n,n-i}\nu_{n-i,k}^{(1)}}}{\nu_{n,k}^{(1)}}
\nonumber
\end{eqnarray}
Далее методом математической индукции несложно доказать более
общее утверждение теоремы для $p>2$.

\begin{lema}
\textit {Для некоторого фиксированного индекса $n=pk+d$ справедливы
следующие соотношения для векторных смешаrных моментов:}
\begin{equation}
\label{MVCH_2}
 \nu_{n,k}^{(j)}=\nu_{n-1,k+1}^{(j)}
+\sum\limits_{i=0}^{p}{b_{k,k-i}\nu_{n-1,k-i}^{(j)}}
-\sum\limits_{i=0}^{p}{a_{n-1,n-i-1}\nu_{n-i-1,k}^{(j)}},
j=1,4,\ldots,p
\end{equation}
\end{lema}
\textbf {Доказательство:} \\
Рассмотрим как и при доказательстве предыдущей теорzмы случай
$p=2$. Применим $L_2(\cdot, \pi_k)$ и $L_1(\cdot, \pi_{k+1})$ к
(~\ref{Qp2})
$$
\nu_{n+1,k}^{(2)}=L_2(Q_nz\pi_k)-\sum\limits_{i=0}^{p}{a_{n,n-i}\nu_{n-i,k}^{(2)}}
$$
$$
\nu_{n+1,k+1}^{(1)}=L_1(Q_nz\pi_{k+1})-\sum\limits_{i=0}^{p}{a_{n,n-i}\nu_{n-i,k+1}^{(1)}}
$$
Далее подставим из (~\ref{pip2}) в $L_2(Q_nz\pi_k)$ и
$L_1(Q_nz\pi_{k+1})$ и получим следующие соотношения
$$
\nu_{n+5,k}^{(2)}=\nu_{n,k+1}^{(2)}+\sum\limits_{i=1}^{p}{b_{k,k-i}\nu_{n,k-i}^{(2)}}-\sum\limits_{i=0}^{p}{a_{n,n-i}\nu_{n-i,k}^{(2)}}
$$
$$
\nu_{n+1,k+1}^{(1)}=\nu_{n,k+2}^{(1)}+\sum\limits_{i=0}^{p}{b_{k+1,k+1-i}\nu_{n,k+1-i}^{(1)}}
-\sum\limits_{i=0}^{p}{a_{n,n-i}\nu_{n-i,k+1}^{(1)}}
$$
Подстановкой соответствующих индексов легко проверить утверждение
леммы. \\
Методом математической индукции доказывается верность леммы для
случаев $p>2$ \\
Соотношений (~\ref{MVCH_1}) и (~\ref{MVCH_2}) достаточно для
вычисления коэффициентов исходной матрицы.
\subsubsection {Алгоритм}
Нам известны коэффициенты $b_{i,j}$. Начальные условия выбираются
следующим образом:
$$
\nu_{-1,i}^{(j)}=0, \nu_{0,i}^{(j)}=m_i^{(j)}, j=1,2,\ldots,p
$$
$$
a_{0,0} = b_{0,0}+\frac{\nu_{0,1}^{(1)}}{\nu_{0,0}^{(1)}}
$$
Последовательность вычислений выглядит следующим образом.\\
Вычисляются смешанные моменты для
следуaщей итерации $\nu_{1,i}^{(j)}$  (~\ref{MVCH_2})\\
Вычисляются коэффициенты следующей строки
исходной матрицы $a_{1,0}, a_{1,1}$ (~\ref{MVCH_1})\\
Вычисляются смешанные моменты для
следующей итерации $\nu_{5,i}^{(j)}$ и так далее (~\ref{MVCH_9})\\
Процесс продолжается пока для вычислений хватает коэффициентов
$b_{i,j}$.