Слаботочка Книги

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 [105] 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208

векторов являются собственными для оператора А. Следовательно, существует полная система собственных векторов, принадлежащих этим подпространствам, т. е. являющихся или четными, или нечетными. Это обстоятельство может быть существенно использовано: если вектор х° четен или нечетен, то этим же свойством обладают все векторы х , поэтому нри отыскании каждого последующего вектора х следует ограничиться определением первой половины его компонент. Кроме этого, можно объединить коэффициенты, соответствующие компонентам xi и x,n+i~i- Например, при четном х* вычисления компонент х можно производить по формулам

i = Е( У + (4,m+l-j)xf.

В случае итераций такого вида мы не выходим за пределы подпространств четных или нечетных векторов соответствеирю. Поэтому если х° и ei принадлежат различным подпространствам, составляющая, пропорциональная ej, так и не появится.

Кроме непосредственного уменьшения вычислений при отыскании каждого вектора х , использование свойства (2) полезно также но следующей причине. Довольно типичен случай, когда собственные векторы с небольшими нечетными номерами являются четными, а с небо.льшими четными номерами - нечетными; предположим, что Ai > IA2I > Аз > ... Тогда нри х четном всегда

х = r;iA ei + СзАзвз + = ciA ei + 0(Аз ),

следовате.льно,

А - Ai = 0(Аз/А1 ) при а1 = (х +1, х )/(х , х ).

Соответственно при х* нечетном имеем

х =С2Ае2-Ю(А4Г)

А ) - А2 = 0(А4/А2 ) при а = (х +\ х )/(х , х ).

При этом не возникает никакой проб.лемы подавления составляющей, пропорциональной 61.

Если Ai > 1, то х -> оо при п -> оо, поэтому нри достаточно большом п произойдет переполнение разрядности чисел и остановка ЭВМ. Если jAil < 1, то (х -> О, и вследствие конечности порядков чисел в машине может случиться, что, начиная с некоторого п, х = О. Чтобы избежать этих явлений, полезно время от времени нормировать вектор х , чтобы х = 1.

Для практической оценки погрешности и ускорения сходимости итерационных процессов может быть применен й-процесс и другие приемы, аналогишые методам ускорения сходимости при решении систем линейных уравнений. Например, могут применяться итерации вида х =

§ 13. Решение полной проблемы собственных значений при помош,и QR-алгоритма

Сугцествует ряд тщательно отработанньгх алгоритмов и программ решения полной проблемы собственных значений. Поэтому в случае, когда возникает такая проблема, в первую очередь рекомендуется использовать стандартные программы решения таких задач. Наиболее совершенные из них основаны на различных модификациях QR-алгоритма, общая схема которого приводится ниже.

Пусть Л - произвольная вещественная матрица. Согласно лемме из § 2 ее можно представить в виде Л ~ An-i, где [/ - ортогональная, а Ап-1 - правая треугольная матрицы. Запишем это равенство в виде

А = QiRi, (1)

где - ортогональная, правая треугольная матрицы. Из (1) имеем

Ri = QiA, поэтому матрица Ai = RiQi - QiAQi подобна матрице Л.

Построим последовательность матриц Л по следующему правилу. Матрицу An разлагаем на произведение ортогональной и правой треугольной матриц в виде Л = Qn+iRn+i и полагаем Л 1 = Rn+iQn+i- ПО скольку Ап+1 = Qn+iAnQn+i, то все матрицы А подобны между собой и подобны исходной матрице Л.

Представим исходную матрицу Л в виде Л = QAQ~, где Л -правая каноническая форма Жордана, т.е. Ajj = О при j < г п j > Ай = А-,- собственные значения матрицы Л, Xi,i+i равны нулю или 1. Всегда можно подобрать матрицу Q так, чтобы диагональные элементы матрицы Л были упорядочены в порядке невозрастания модуля

Ai = = Аг, > Aj,+i = = А;, > > Aj, ,+i = = AjJ.

Теорема (без доказательства). Пусть в разложении матрицы А все диагональные миноры матрицы Q не вырождены. Тогда последовательность

gk(A)x. со специальным подбором в зависимости от известной информации о спектре матрицы А многочлена дк{А). Поскольку

. (Лх, х) . . (Лх, х)

niax Ад = sup --г-, ПИП А д = mi --г-

X (х, х) X (х, х)

при А = А, то некоторые приемы отыскания максимального и минимального собственных значений матрицы Л основываются па идее отыскания стационарных точек функционала Ф(х) = (Лх, х)/(х, х).

Задача 2. Пусть Ai 5, 1 А, 3 при г = 2,..., т. Построить итерационный процесс вида х = (Л-f ci?)x для получения Ai с наилучшей при данной информации скоростью сходимости.

Сделать то же самое, если Ai ~ 1, 2 А- 3 при i ~ 2,..., т.

матриц An при п -> оо сходится по форме к клеточному правому треугольному виду А.

Имеется в виду, что после некоторой перестановки строк и одновременно такой же перестановки столбцов матрицы А будут выполняться соотношения: если < г Ik+i, j < г или Ik+i < j, к = l,...,s, то

При реализации описанного алгоритма построения матриц Л на практике мы увидим, что некоторые элементы матриц Л оказываются малыми. Приравняв их нулю, мы получим клеточную правую треугольную матрицу. Характеристический многочлен этой матрицы равен произведению характеристических многочленов ее диагональных клеток.

Если требуется найти не только собственные значения матрицы А, но и ее собственные и присоединенные векторы, то в процессе построения последовательности матриц Л следует запоминать ортогональные матрицы Рп = Ql Qm вычисляемые но рекуррентной формуле

Рп+1 = PnQn+l

Задача 1. Доказать, что каждый шаг QR-алгоритма требует N ~ lOm/3 арифметических операций.

На практике прибегают к различным способам ускорения сходимости. Один из этих способов заключается в следующем. Матрица А предварительно преобразуется в эквивалентную ей правую почти треугольную матрицу.

Матрица А называется правой почти треугольной, если = О нри j < i -1.

Алгоритм преобразования матрицы А в правую почти треугольную матрицу заключается в последовательном построении матриц Ai таких, что первые / столбцов матрицы Ai имеют вид первых / столбцов правой почти треугольной матрицы, т.е. Оу = О, если j < i-1 и j l. По элементам (/-Ы)-го столбца матрицы Ai построим матрицу отражения C/+i (см. § 2) так, чтобы в матрице В = Ui+iAi элементы bi+i,..., hj+i были те же, что у матрицы Ai, а элементы bi+3j+i, , bjnj+i были нулевыми. Положим Ai+i --- Ui+iAiUi+i Умножение справа на матрицу C/jj не меняет первых / Ч- 1 столбцов матрицы В, поэтому матрица Aj+i является матрицей требуемого вида. После получения правой почти треугольной матрицы Ajn-i применяют QR-алгоритм в его первоначальной форме.

Задача 2. Доказать, что в этом случае каждый шаг QR-алгоритма требует N ~ 6т арифметических операций.

Для еще большего ускорения сходимости применяется вариант QR-горитма со сдвигом. А именно, строится последовательность ортого-

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 [105] 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208