Институт вычислительной математики и математической геофизики СОРАН

Тезисы докладов

Вычислительная алгебра

Рассмотрим итерационный процесс x[n+1] = Tx[n] + f, n = 0, 1, . . . решения системы линейных алгебраических уравнений (СЛАУ) Ax = b, где A, T - квадратные матрицы, b, f - векторы правых частей. В данной работе предложен новый вариант метода ускорения сходимости итераций, в котором через каждые N шагов к текущему приближению x[n] добавляется поправка y[n]

z[n] = x[n] + y[n] = x[n] + a[1]r[n-k+1] + ... + a[k-1]r[n-1],

где

r[i] = Tx[i] + f - x[i] = x[i+1] - x[i] (i = 0, 1, . . . )

- векторы невязок [1], N - фиксированное натуральное число. Видно, что поправка yn ищется в подпространстве Крылова K_{k-1}(r[n-k+1], T) [2, 3]. Коэффициенты a[1], . . . , a[k-1] находятся из условия минимизации функционала невязки

Phi(a[1], . . . , a[k-1]) = (|| T^{-1}(z[n] - Tz[n] - f) ||_2)^2          (1)

где ||xn||_2 - стандартная евклидова норма конечномерного вектора xn. Уточненный таким образом вектор _xn используется далее в качестве начального приближения для следующих N итераций. Задача о нахождении минимума функционала Phi эквивалентна решению переопределенной СЛАУ

a[1](r[n-k+1] - r[n-k]) + ... + a[k-1] (r[n-1]-r[n-2]) = - r[n-1]       (2)

с неизвестными a[1], . . . , a[k-1] методом наименьших квадратов (МНК). Для решения (2) здесь используется ортогональный метод [4], дающий при отсутствии ошибок округлений то же псевдорешение, что и МНК. При этом ортогональный метод не ухудшает в процессе решения обусловленность задачи линейной алгебры в отличие от МНК. Заметим, что с увеличением n элементы матрицы системы (2) стремятся к нулю. Одновременно с этим столбцы матрицы могут стать близкими к линейно зависимым. В результате система (2) становится плохо обусловленной и эффективность ускорения итераций уменьшается из-за большой погрешности вычисления коэффициентов поправки yn. Для того, чтобы избежать указанных здесь трудностей, в данной работе, во-первых, производится нормировка столбцов матрицы. Во-вторых, в случае, когда модуль ведущего элемента ортогонального исключения, которое производится в матрице системы (2), становится меньше малой величины " (10^{-15}), число невязок, используемых для поправки, уменьшается. Пусть, например, модуль ведущего элемента стал меньше " при исключении в столбце k1 < k - 1. В этом случае здесь предлагается положить коэффициенты a[k1], . . . , a[k-1] равными нулю, а неизвестные a[1], . . . , a[k1-1] найти из уравнений системы (2) (учитывая в (2), что a[k1] = a[k1+1] = . . . = a[k-1] = 0). Видно, что при этом поправка y[n] ищется в подпространстве Крылова меньшей размерности K_{k1-1}(r[n-k+1], T). Описанный здесь алгоритм выбора подпространства Крылова, в котором строится поправка yn, предложен в данной работе впервые. В численных экспериментах показано, что он позволяет существенно повысить эффективность ускорения.

Работа выполнена при поддержке РФФИ - грант 08-08-00249-а и интеграционного проекта СО РАН №26

Список литературы

[1] Слепцов А.Г. Об ускорении сходимости линейных итераций // Моделирование в механике. Новосибирск, 1989. Т. 3(20), № 3. c. 132-147.

[2] Saad Y. Numerical methods for large eigenvalue problems. Manchester University Press, 1991. 358 pp.

[3] Ильин В.П. Методы и технологии конечных элементов. Новосиб.: Изд. ИВМиМГ СО РАН, 2007. 371 с.

[4] Беклемишев Д.В. Дополнительные главы линейной алгебры. М.: Наука, 1983. 335 c.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии Обратная связь

[Головная страница] [Конференции]

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:49:22)