User:Daria Maksimova

Свойства и структура алгоритма

Общее описание алгоритма

Стабилизированный метод бисопряженных градиентов с адаптивным перезапуском (Template:Lang-en) представляет собой модификацию классического алгоритма BiCGStab, разработанного Хенком ван дер Ворстом в 1992 году. Модификация была предложена для преодоления характерных проблем исходного метода — замедления сходимости и осцилляций невязки на поздних итерациях, особенно актуальных при решении систем с плохо обусловленными матрицами.

Алгоритм сочетает в себе скорость базового метода BiCGStab с интеллектуальным механизмом перезапуска, который автоматически отслеживает динамику сходимости и выполняет перезапуск вычислительного процесса при обнаружении значительного замедления. Это позволяет "встряхнуть" процесс сходимости и избежать застоя, характерного для многих итерационных методов Крылова.

Метод находит успешное применение в задачах вычислительной газодинамики, электродинамики и других областях, где возникают большие разреженные несимметричные системы линейных уравнений. В частности, для решения систем, образующихся при линеаризации уравнений Эйлера в трехмерных задачах газодинамики:

[math]\displaystyle{ J^{(k)} \Delta U^{(k)} = -R(U^{(k)}) }[/math]

где [math]\displaystyle{ J^{(k)} }[/math] — матрица Якоби, [math]\displaystyle{ \Delta U^{(k)} }[/math] — поправка к решению, [math]\displaystyle{ R }[/math] — вектор невязки.

Математическое описание алгоритма

Исходные данные: несимметричная матрица [math]\displaystyle{ A \in \mathbb{R}^{N \times N} }[/math], вектор правой части [math]\displaystyle{ b \in \mathbb{R}^N }[/math], начальное приближение [math]\displaystyle{ x_0 }[/math], параметры останова [math]\displaystyle{ \epsilon }[/math], [math]\displaystyle{ max\_iter }[/math], параметр перезапуска [math]\displaystyle{ \theta \in (0,1) }[/math].

Вычисляемые данные: вектор решения [math]\displaystyle{ x \in \mathbb{R}^N }[/math], история невязок [math]\displaystyle{ \{r_k\} }[/math].

Основные формулы метода:

Инициализация: [math]\displaystyle{ \begin{align} r_0 &= b - A x_0 \\ \tilde{r} &= r_0 \\ \rho_0 &= \alpha_0 = \omega_0 = 1 \\ v_0 &= p_0 = 0 \\ k &= 0 \end{align} }[/math]

Основной итерационный процесс: Для [math]\displaystyle{ k = 0, 1, 2, \dots, max\_iter }[/math]: [math]\displaystyle{ \begin{align} \rho_k &= (\tilde{r}, r_k) \\ \beta_k &= (\rho_k / \rho_{k-1}) \times (\alpha_{k-1} / \omega_{k-1}) \\ p_k &= r_k + \beta_k \times (p_{k-1} - \omega_{k-1} v_{k-1}) \\ v_k &= A p_k \\ \alpha_k &= \rho_k / (\tilde{r}, v_k) \\ s_k &= r_k - \alpha_k v_k \\ t_k &= A s_k \\ \omega_k &= (t_k, s_k) / (t_k, t_k) \\ x_{k+1} &= x_k + \alpha_k p_k + \omega_k s_k \\ r_{k+1} &= s_k - \omega_k t_k \end{align} }[/math]

Критерий адаптивного перезапуска:

Мониторинг сходимости: [math]\displaystyle{ \begin{align} \gamma_k &= \frac{\|r_{k+1}\|}{\|r_k\|} \quad \text{– текущая скорость сходимости} \\ \overline{\gamma}_k &= \frac{1}{m} \sum_{i=k-m}^{k-1} \gamma_i \quad \text{– средняя скорость сходимости за } m \text{ итераций} \end{align} }[/math]

Условие перезапуска: Если [math]\displaystyle{ \gamma_k \gt \theta \cdot \overline{\gamma}_k }[/math], то: [math]\displaystyle{ \begin{align} x_0 &:= x_{k+1} \\ r_0 &:= r_{k+1} \\ \tilde{r} &:= r_{k+1} \\ \rho_0 &= \alpha_0 = \omega_0 = 1 \\ v_0 &= p_0 = 0 \\ k &= 0 \quad \text{(сброс счетчика)} \end{align} }[/math]

Критерий останова: [math]\displaystyle{ \text{Если } \|r_{k+1}\| \lt \epsilon \cdot \|b\| \text{ или } k \gt max\_iter \text{, то останов} }[/math]

Литература

• Henk A. vander Vorst. Iterative Krylov Methods for Large Linear Systems. — Cambridge University Press, 2003. — 230 p.

• Горбаченко В.И. Вычислительная линейная алгебра с примерами на MATLAB. — СПб.: БХВ-Петербург, 2011. — 320 с. — (Учебное пособие).