Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
учебное пособие_методы решения СЛАУ.doc
Скачиваний:
8
Добавлен:
01.04.2025
Размер:
800 Кб
Скачать
☆

2.2.5 Биортогонализация Ланцоша

Алгоритм ортогонализации Арнольди, рассмотренный ранее, для построения каждого нового вектора k требует нахождения (k–1) скалярных произведений и столько же операций линейного комбинирования. Однако, как оказывается, при отказе от требования ортогональности базиса в пользу некоторого более общего условия можно построить процедуру меньшей сложности.

Системы векторов и называются биортогональными, если скалярное произведение (xi,yi) обращается в ноль при ij. В случае xiyi условие биортогональности сводится к обычному условию ортогональности. Пусть векторы 1 и 1 таковы, что (1,1)0 и пусть системы векторов и определяются соотношениями:

i+1=Ai–ii–ii–1, 00;

(2.33)

i+1=ATi–ii–ii–1, 00;

(2.34)

i=(Ai, i)/)(i, i);

(2.35)

i=(i, i)/(i–1, i–1), 10.

(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 должна быть легко обратима.