Решение систем линейных алгебраических уравнений для больших разреженных матриц (стр. 6 из 6)
при k → ∞.Кроме того, также выполняется соотношение
||Akb|| → |λ1|k|b1| при k → ∞.
Таким образом, при возрастании k члены степенной последовательности поворачиваются таким образом, что оказываются параллельными собственному вектору emax ≡ e1, соответствующему максимальному по модулю собственному значению λmax.
4.3 Итерационные методы подпространств Крылова
Подпространства Крылова обладают замечательным свойством: если A – симметрична и если последовательно строить ортонормированный базис в Km(b) m = 1,2,...n, то вектора базиса для Kn(b) образуют такую ортогональную матрицу Q, что выполняется равенство
QTAQ = T, (10)
где T является трехдиагональной матрицей
α1 β1 0 ··· 0
β1 α2 β2 ...
T = 0... β1 α3 ...
... ... βn−1
0 ··· βn−1 αn
Если A – несимметричная матрица, то вместо (10) получаем
QTAQ = H, (11)
где H – матрица в верхней форме Хессенберга, т.е. имеет структуру
| × × H = 0 ... 0 | × × × × × × ... ··· | ··· × ... ... ... × × × |
(крестиком помечены ненулевые элементы).
Ясно, что если построено представление (10) или (11), то решение СЛАУ Ax = b можно провести в три шага. Например, если выполнено
(10), то решение Ax = b эквивалентно трем СЛАУ
| Qz = b, | (12) |
| Ty = z, | (13) |
| QTx = y, | (14) |
причем системы (12) и (14) решаются элементарно, поскольку обратная к ортогональной матрице Q является транспонированная QT. Система (13) также решается гораздо проще исходной, поскольку T – трехдиагональная матрица, для которых развиты быстрые и эффективные методы решения СЛАУ.
Рассмотрим алгоритм, приводящий симметричную матрицу A к трехдиагональному виду.
Алгоритм Ланцоша. v = 0; β0 = 1; j = 0;
while βj 6= 0 if j 6= 0
for i = 1..n
t = wi; wi = vi/βj; vi = −βjt end
end
v = +Aw
j = j + 1; αj = (w,v); v = v − αjw; βj := kvk2 end
Для приведения матрицы к трехдиагональному виду нужна только процедура умножения матрицы на вектор и процедура скалярного произведения. Это позволяет не хранить матрицу как двумерный массив.
Алгоритм Ланцоша может быть обобщен на случай несимметричных матриц. Здесь матрица A приводится к верхней форме Хессенберга H. Компоненты H обозначим через hi,j, hi,j = 0 при i < j − 1.
Соответствующий алгоритм носит названия алгоритма Арнольди.
Алгоритм Арнольди. r = q1; β = 1; j = 0;
while β 6= 0
hj+1,i = β; qj+1 = rj/β; j = j + 1 w = Aqj; r = w for i = 1..j
hij = (qi,w); r = r − hijqi
end
β = krk2 if j < n
hj+1,j = β
end
end
Определенным недостатком алгоритмов Ланцоша и Арнольди является потеря ортогональности Q в процессе вычислений. СУществет ряд реализаций этих алгоритмов, преодолевающих этот недостаток, и делающих эти методы весьма эффективными для решения СЛАУ с большими разреженными матрицами.
ТЕСТ РУБЕЖНОГО КОНТРОЛЯ № 4
1. Что такое инвариантное подпространство? (выберите один из ответов)
(a) линейная оболочка, натянутая на столбцы матрицы A;
(b) подпространство, не изменяющееся при действии на него матрицы A;
(c) нульмерное-подпространство; (d) подпространство Крылова.
2. Что такое степенная последовательность? (выберите один из ответов)
(a) последовательность E, A, A2, A3, ...;
(b) последовательность b, Ab, A2b, A3b, ...;
(c) последовательность 1, x, x2, x3, ...; (d) последовательность 1, 2, 4, 8, ....
3. Недостатком метода Ланцоша является (выберите один из ответов)
(a) медленная сходимость;
(b) потеря ортогонализации;
(c) невозможность вычисления собственных векторов; (d) необходимость вычисления степеней.
4. В методе Ланцоша используются
(a) подпространства Крылова;
(b) линейная оболочка, натянутая на столбцы матрицы A;
(c) подпространство, образованное собственными векторами матрицы A;
(d) подпространство, образованное собственными векторами матрицы QTAQ.
5. Метод Ланцоша приводит матрицу к
(a) диагональной;
(b) трехдиагональной;
(c) верхней треугольной;
(d) верхней треугольной в форме Хессенберга.
6. Метод Ланцоша применим для матриц
(a) диагональных;
(b) трехдиагональных;
(c) симметричных; (d) произвольных.
7. Метод Арнольди приводит матрицу к
(a) диагональной;
(b) трехдиагональной;
(c) верхней треугольной;
(d) верхней треугольной в форме Хессенберга.
8. Метод Арнольди применим для матриц
(a) диагональных;
(b) трехдиагональных;
(c) симметричных; (d) произвольных.
Заключение
Выше дано описание некоторых методов решения систем линейных алгебраических уравнений для симметричных разреженных матриц большой размерности.
При написании данного пособия в основном использовались материалы [3, 4, 7, 9, 10]. Более подробные сведения о можно получить в приведенной ниже основной и дополнительной литературе.
ЛИТЕРАТУРА
[1] В. В. Воеводин. Вычислительные основы линейной алгебры. М.: Наука, 1977. 304 с.
[2] В. В. Воеводин, Ю. А. Кузнецов. Матрицы и вычисления. М.: Наука, 1984. 320 с.
[3] Дж. Голуб, Ч. Ван Лоун. Матричные вычисления. М.: Мир, 1999. 548 с.
[4] Дж. Деммель. Вычислительная линейная алгебра. Теория и приложения. М.: Мир, 2001. 430 с.
[5] Х. Д. Икрамов. Численные методы для симметричных линейных систем. М.: Наука, 1988. 160 с.
[6] Б. Парлетт. Симметричная проблема собственных значений. Численные методы. М.: Мир, 1983. 384 с.
[7] C. Писсанецки. Технология разреженных матриц. М.: Мир, 1988. 410 с.
[8] Дж. Х. Уилкинсон. Алгебраическая проблема собственных значений. М.: Наука, 1970. 564 с.
[9] Л. Хейнгеман, Д. Янг. Прикладные итерационные методы. М.: Мир, 1986. 448 с.
[10] Р. Хорн, Ч. Джонсон. Матричный анализ. М.: Мир, 1989. 655 с.
ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА
[Д1] Х. Д. Икрамов. Несимметричная проблема собственных значений. М.: Наука, 1991. 240 с.
[Д2] Дж. Райс. Матричные вычисления и математическое обеспечение. М.: Мир, 1984. 264 с.
[Д3] Y. Saad. Numerical Methods for Large Eigenvalue Problems. Halsted Press: Manchester, 1992. 347 p.
[Д4] Дж. Форсайт, К. Молер. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969. 167 с.