Базис подпространства Крылова. Ортогонализация Арнольди

Для построения базиса в пространстве Крылова K_m (n ₁, A) можно применить следующий подход. Сначала находят векторы w ₁= n ₁, w ₂= Aw ₁, w ₃= A ² w ₁= Aw ₂,…, w _m = A ^{m –1} w ₁= Aw _{m –1}. По определению (2.21),

K_m (n₁, A)=span{w₁, w₂,…,w _m }.

Далее переходят от { w ₁, w ₂,…, w _m } к { n ₁, n ₂,…, n _m }, применив процедуру ортогонализации

n k +1=w k –1– ,

(2.26)

и затем пронормировав полученные векторы. Предполагая, что предыдущие k векторов уже построены, т.е.

i, j (1£ i, j £ k): (n i,n j)= .

(2.27)

Тогда (2.26) можно записать

n _{k +1}=An _k – .

Для выполнения условия ортогональности n _{k +1} ко всем предыдущим векторам, умножают это равенство скалярно на n _j (j £ k) и приравнивая результат к нулю

(An k, n j)–

(2.28)

С учетом (2.27) отсюда легко получить выражение для коэффициентов a _j

a _j =(An _k, n _j).

Описанный метод может быть оформлен в виде следующей процедуры, называемой ортогонализацией Арнольди.

Алгоритм ортогонализации Арнольди

Входные данные: n₁, такой что ||n₁||₂=1; A; m

Выполнять для j =1,…, m

w=An _j

Выполнять для i =1,…, j

h_ij =(w, n _i)

w=w– h_ij n _i

увеличить i

h_{j +1, j} =||w||₂

Если h_{j +1, j} =0, то КОНЕЦ. Базис построен.

n _{j +1}=w/ h_{j +1, j}

увеличить j

Для коэффициентов ортогонализации здесь введена двойная индексация, с учетом которой внутренний цикл алгоритма алгебраически записывается как

h j +1, j n j +1=An j – .

(2.29)

Коэффициенты ортогонализации h_{i , j} можно объединить в виде матрицы H, дополнив в ней недостающие позиции нулями. При этом, как видно из алгоритма, для заданной размерности пространства m генерируется m +1 векторов. Последний вектор n _{m +1} (возможно, нулевой) в матричном представлении означает расширение базиса V одним дополнительным столбцом, т.е.

V _m =[n₁|n₂|…|n _m ]; V _{m +1}=[n₁|n₂|…|n _m |n _{m +1}].

Соответствующий вектору n _{m +1} коэффициент h_{m +1, m} означает расширение матрицы H одной дополнительной строкой (возможно, нулевой).

Пусть – это матрица (m +1)´ m матрица коэффициентов h_{m +1, m}, а матрица H _m – та же самая матрица без последней строки, имеющая размерность m ´ m. Тогда непосредственно из описания алгоритма Арнольди и (2.29) следует, что матрица H _m является матрицей в верхней форме Хессенберга, (матрица называется верхней хессенберговой или верхней почти треугольной, если ее ненулевые элементы расположены только в ее верхнем треугольнике, на диагонали и на поддиагонали) и для нее справедливы соотношения

AV m =V m +1 =V m H m +w m e m^T;	(2.30)
V m^T AV m =H m.	(2.31)

Кроме того, вследствие ортонормальности базиса { n _j } имеет место равенство

V ^T n k =e k.

(2.32)

Дата добавления: 2014-12-27