- •Министерство образования и науки Российской Федерации
- •1. Прямые (точные) методы
- •1.1 Метод исключения Гаусса
- •1.3 Решение слау с помощью lu-разложения матриц
- •1.4 Обращение матриц
- •1.5 Метод исключения Жордана (Гаусса – Жордана)
- •1.6 Контроль точности и уточнение приближенного решения в рамках прямого метода
- •2.1 Классические итерационные методы и релаксация
- •2.1.1 Методы Якоби и Гаусса-Зейделя
- •1.7 Вычислительные затраты прямых методов
- •2. Итерационные методы
- •2.1.2 Ускорение сходимости релаксационных методов
- •2.2 Проекционные методы и подпространства Крылова
- •2.2.1 Общий подход к построению проекционных методов
- •2.2.2 Случай одномерных подпространств k и l
- •2.2.3 Два выбора подпространств
- •2.2.4 Подпространства Крылова
- •2.2.5 Базис подпространства Крылова. Ортогонализация Арнольди
- •2.2.5 Биортогонализация Ланцоша
- •2.3 Предобусловливание
- •2.3.1 Предобусловливание основанное на классических методах
- •2.3.2 Неполное lu-разложение
- •2.3.3 Выбор структуры разреженности
- •2.4 Методы Крыловского типа
- •2.4.1 Метод обобщенных минимальных невязок
- •2.4.2 Метод бисопряженных градиентов
- •2.4.3 Стабилизированный метод бисопряженных градиентов
- •2.4.4 Метод квази-минимальных невязок
- •2.2.5 Квадратичный метод сопряженных градиентов
- •2.2.6 Метод сопряженных градентов
2.2.5 Биортогонализация Ланцоша
Алгоритм ортогонализации Арнольди, рассмотренный ранее, для построения каждого нового вектора k требует нахождения (k–1) скалярных произведений и столько же операций линейного комбинирования. Однако, как оказывается, при отказе от требования ортогональности базиса в пользу некоторого более общего условия можно построить процедуру меньшей сложности.
Системы
векторов
и
называются
биортогональными, если скалярное
произведение (xi,yi)
обращается в ноль при ij.
В случае xiyi
условие биортогональности сводится к
обычному условию ортогональности. Пусть
векторы 1
и 1
таковы, что (1,1)0
и пусть системы векторов
и
определяются соотношениями:
i+1=Ai–ii–ii–1, 00; |
(2.33) |
i+1=ATi–ii–ii–1, 00; |
(2.34) |
i=(Ai, i)/)(i, i); |
(2.35) |
i=(i, i)/(i–1, i–1), 10. |
(2.36) |
Тогда
системы
и
являются биортогональными;
каждая система и является линейно независимой и образует базис в Km(1, A) и Km(1,AT) соответственно.
Процедура построения векторов и согласно формулам (2.33)–(2.36) называется биортогонализацией Ланцоша.
Очевидно, что (2.33) является частным случаем (2.29), где из всей суммы оставлены только два последних слагаемых; точно так же (2.34) является частным случаем (2.29), записанной для матрицы AT и вектора 1. При этом коэффициенты ортогонализации в (2.33) и (2.34) одинаковы. Из сказанного следует, что можно записать аналог матричной формулы (2.31)
WmTAVm=Tm, |
(2.37) |
где Tm – симметричная трехдиагональная матрица, элементы которой определяются соотношениями
[Tm]ii=i(i, i); |
(2.38) |
[Tm]i+1,i=[Tm]i,i+1=i(i, i), |
(2.39) |
выводимыми из (2.39) – (2.40).
Основным недостатком биортогонализация Ланцоша является возможность возникновения ситуации, когда (i, i)=0; при этом продолжение процесса становится невозможным из-за неопределенности коэффициента i+1.
2.3 Предобусловливание
Вычисление итерационными методами зависит от обусловленности матрицы А, оцениваемой числом обусловленности condA=||A||||A–1|||max|/|min|. С ростом condA обусловленность ухудшается, и для ряда проблем сходимость может оказаться очень медленной и поэтому итерационный процесс может застопорится или даже оборваться. Однако применение так называемого предобусловливания улучшает сходимость к требуемому решению.
Пусть М – некоторая невырожденная матрица размерности N. Домножив (1.1) на матрицу M–1, получим систему
M–1Ax=M–1b, |
(2.40) |
которая
в силу невырожденности M
имеет то же точное решение x*.
Введя обозначения
=M–1A
и
=M–1b,
(2.40) примет вид
x= . |
(2.41) |
Хотя (2.41) алгебраически эквивалентна (1.1), спектральные характеристики матрицы отличаются от характеристик матрицы A, что, вообще говоря, ведет к изменению скорости сходимости численных методов для (2.41) по отношению к (1.1) в конечной арифметике.
Процесс перехода от (2.1) к (2.41) с целью улучшения характеристик матрицы для ускорения сходимости к решению называется предобусловливанием, а матрица M–1– матрицей предобусловливателя. Из (2.40) сразу же вытекает важное требование: матрица M должна быть близка к матрице A. Выбор M=A сразу же приводит (1.1) к виду Ix=A–1b, однако не имеет практического смысла, так как требует нахождения A–1, что по существу и сводится к решению (1.1). Вторым естественным требованием является требование легкой вычислимости матрицы M.
Невязкой
системы (1.1), соответствующей вектору
x,
называется вектор r=b–Ax=A(x–x),
где x
– точное решение. Невязка
системы (2.41) связана с невязкой системы
(1.1) очевидным соотношением
M =r, |
(2.42) |
которое
справедливо и для матрично-векторных
произведений z=Aq
и
=
q:
= q=M–1Aq M =Aq=z. |
(2.43) |
Это позволяет вместо явного перехода от (1.1) к (2.41) вводить в схемы методов корректирующие шаги для учета влияния предобусловливающей матрицы. Данный подход называется неявное предобусловливание. Явное предобусловливание требует нахождениия матрицы М–1 и умножения матрицы предобусловливания на вектор в каждой. В данной версии системы TALGAT реализовано использование только неявного предобусловливания.
Из (2.43) следует еще одно условие: структура матрицы предобусловливателя должна допускать легкое и быстрое решение «обратных к предобусловливателю» систем вида M =z.
Таким образом:
M должна быть по возможности близка к матрице A;
M должна быть легко вычислима;
M должна быть легко обратима.
