Предобуславливание и масштабирование

4.3. Предобуславливание и масштабирование

Если применяется предобуславливатель , см. (4.7) – (4.11),

то расчетные формулы CG модифицируются следующим образом.

Ø Вычисляем невязку

Ø Вычисляем поправку , для этого надо решать задачу!

Ø  Находим параметр .

Ø Выбираем направление .

Ø Вычисляем длину шага .

Рекомендуемые материалы

Ø Определяем новое приближение .

В качестве предобуславливателя  можно взять хотя бы диагональ  матрицы  (это будет предобуславливатель Якоби). Поправка в этом случае вычислятся очень просто: . Более сложные и мощные предобуславливатели будем изучать позднее.

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

                                                                                    (4.23)

Введем теперь новую функцию  и подставим в (4.23). Получим новую задачу  с хорошей матрицей , у которой на диагонали стоят единицы.

Покажем на простом примере, что если , то и . Рассмотрим для наглядности случай .

                 .

Видно, что необходимым условием применения масштабирования является , что имет место для положительно определенных матриц. Симметрия матрицы  следует из симметрии матрицы . Правая часть масштабированной системы уравнений (4.23) имеет вид

                        .

Итак, общие формулы масштабирования имеют вид

                                           (4.24)

Прямым или итерационным методом решается система уравнений

Рекомендуем посмотреть лекцию "Условия водообмена".

                                                 ,                                  (4.25)

после чего решение исходной задачи определяется по формуле , или

                                                  .                                   (4.26)

Важно отметить, что процедура масштабирования не приводит заполнению матрицы , ее портрет тот же, что и у матрицы . Это следует использовать при работе с разреженными матрицами сеточных схем. Поскольку подсчет коэффициентов  (4.24) и пересчет решения (4.26) проводится один раз, то дополнительные затраты для масштабирования пренебрежимо малы по сравнению с затратами на решение задачи (4.25).

Задание 1.  Составить программу CG (сопряженных градиентов) с произвольным предобуславливателем (оформить решение задачи  в виде отдельной процедуры) для трехточечной задачи теплопроводности с переменным коэффициентом. Сравнить скорость сходимости обычного метода CG () и предобусловленного по Якоби . Проверить чувствительность к колебаниям коэффициента теплопроводности.

Задание 2. Проверить эффект от масштабирования.