Многослойные итерационные схемы

Рассмотрим СЛАУ:

\[Ax = f\]

Пусть СЛАУ привели к виду:

\[x = Bx + g\]

Рассмотрим метод простых итераций, который сходится к точному решению:

\[x^{(k+1)} = Bx^{(k)} + g\]

\[x^{(k)} \rightarrow x^{(*)}\]

Рассмотрим известную последовательность приближений \(x^{(0)}, x^{(1)}, x^{(2)} ... x^{(m)}\). На основе данной последовательности построим новое приближение:

\[y_m = \sum\limits_{i = 0}^{m}\gamma_{im}x^{(i)}\]

Если \(x^{(0)} = x^{(1)} = x^{(2)} = ... = x^{(m)} = x^{(*)}\), т.е. уже сидим в решении и никуда из него не уходим. Тогда необходимое условие того, чтобы эта взвешенная сумма давала нам правильный ответ - единичная нормировка весов слагаемых:

\[\sum\limits_{i = 0}^{m}\gamma_{im} = 1\]

Такой процедурой можно уточнять решения и строить многослойные схемы.

Рассмотрим невязку такой процедуры :

\[\begin{split}\begin{cases} x^{(m)} = Bx^{(m-1)} + g \\ x^{(*)} = Bx^{(*)} + g \\ \end{cases}\end{split}\]

Тогда невязка решения будет:

\[\widetilde\delta = y_m - x^{(*)} = \sum\limits_{i = 0}^{m}\gamma_{im}x^{(i)} - x^{(*)} = \sum\limits_{i = 1}^{m}\gamma_{im}(x^{(i)} - x^{(*)}) = \sum\limits_{i = 1}^{m}\gamma_{im}(Bx^{(m-1)} - Bx^{(*)}) = P_m(B)(x^{(0)} - x^{(*)})\]

где \(P_m(B) = \sum\limits_{i = 1}^{m}\gamma_{im}B^i\).

Чебышевское ускорение*

Многочлены Чебышева.

Многочленами Чебышева называют:

\[T_{n + 1}(x) = 2xT_{n}(x) - T_(n - 1)(x)\]

\[T_0(x) = 1 , T_1(x) = x\]

Все многочлены определены на отрезке \([-1; 1]\) и для всех выполняется \(max(|T_n|)=1\).

Среди всех многочленов, значения которых на отрезке [-1,1] не превосходят по модулю 1, многочлен Чебышёва имеет наибольший старший коэффициент, наибольшее значение в любой точке за пределами этого отрезка, а нули многочлена Чебышева являются оптимальными узлами во многих вычислительных схемах.

Приведенным многочленом Чебышева назовем \(\overline T_n(x) = 2^{1 - n}T_n(x)\).

Рассмотрим многочлены вида:

\[P_m(x) = \frac{T_m(\frac{x}{\rho})}{T_m(\frac{1}{\rho})}\]

Для такого многочлена выполняется :

• Он определен от \(-\rho\) до \(\rho\)

• \(P_m(1) = 1\)

Рассмотрим \(\rho = 1 + \varepsilon\), тогда :

\[P_m(x)\leq \frac{1}{T_m(1 + \varepsilon)}\]

\[P_m(x) = \frac{1}{T_m(\frac{1}{\rho})}T_m(\frac{x}{\rho})\]

Обозначим \(\mu_m = \frac{1}{T_m(\frac{1}{\rho})}\), тогда

\[\mu_m = \frac{2}{\rho\mu_{m-1}} - \frac{1}{\mu_{m-2}}\]

Рассмотрим, как поменяется решение :

\[y_m - x^* = P_m(B)\left(x^{(0)} - x^*\right) = \mu_mT_m\left(\frac{B}{\rho}\right)(x^{(0)} - x^*) = \mu_m \left(\frac{2}{\rho}B\left(x^{(m - 1)} - x^*\right)\frac{1}{\mu_{m-1}} - \left(x^{(m - 2)} - x^*\right)\frac{1}{\mu_{m-2}} \right)\]

Приведем выражение к виду:

\[y_m = \frac{2\mu_m}{\mu_{m-1}}\frac{B}{\rho}x^{(m-1)} - \frac{\mu_m}{\mu_{m-2}}x^{(m-2)} + dm\]

, где \(dm = x^*\left(1 - \frac{2\mu_m}{\mu_{m-1}}\frac{B}{\rho} + \frac{\mu_m}{\mu_{m-2}}\right)\)

Для \(x^*\) выполняется уравнение \(x^* = Bx^* + g\), откуда \(Bx^* = x^* - g\), тогда:

\(dm = \mu_m \left(\frac{1}{\mu_m} - \frac{2}{\rho\mu_{m-1}} - \frac{1}{\mu_{m-2}} \right)x^* + 2\frac{\mu_m}{\mu_{m -1 }}g\)

В силу ранее полученных выражений первая скобка равна 0.

В итоге получаем итерационный процесс :

\[\begin{split}\begin{cases} \mu_0 = 1, \mu_1 = \rho \\ y_0 = x^{(0)}, \; y_1 = Bx^{(0)} + g \\ \mu_m = (\frac{2}{\rho\mu_{m - 1 }} - \frac{1}{\mu_{m-2}})^{-1} \\ y_m = \frac{2\mu_m}{\rho\mu_{m-1}}By_{m-1} - \frac{\mu_m}{\mu_{m-2}}By_{m-2} + \frac{2\mu_m}{\rho\mu_{m-2}}g \end{cases}\end{split}\]

В данном ускорении используются все предыдущие вычисления, но в итоговой формуле остались только 2 предыдущих шага. Т.е., данный алгоритм является трехслойным.