|
| |
|
Слаботочка Книги Если v{A) = 1, то тахАд =minA и все собственные значения матрицы А равны между собой по модулю, т. е. А = const -Е. За исключением этого час;тного случая v{A) > 1, поэтому v{A) > и{А). Таким образом, в случае симметричной матрицы применение симметризации увеличивает число обусловленности. Число обусловленности является непрерывной функцией от матрицы, поэтому для матриц, близких к симметричным, применение симметризации также увеличивает число обусловленности ма триц. Таким образом, имеется непустой класс несимметричных матриц, по отношению к которым алгоритм симметризации увеличивает число обусл ов л ешюсти. Задача 2. Суш;ествуют ли несимметричные матрицы, для которых UiA- ) = {HA)f? Рас;смотрим еще один метод решения плохо обусловленных систем линейных алгебраических уравнений. Пусть Лх = ь. (8) Относительно Л будем считать, что в спектре матрицы Л*Л есть как собственные числа Aj порядка 1, так и собственные числа, близкие (или даже равные) к нулю. Это как раз и означает, что матрица Л плохо обусловлена. Заметим, что в силу наших предположений относительно собственных значений матрицы Л* Л, час;ть из них может быть равна нулю. Таким образом, уравнение (8), вообще говоря, может не иметь решения в классическом смысле. Назовем решением X уравнения (8) вектор, который минимизирует функционал невязки, а именно, X = axgmmpy-b; (9) здесь и далее в этом параграфе под нормой мы будем понимать евклидову норму вектора. Выписывая уравнение Эйлера для функционала Ф(у) = 1Иу - ьр, мы получим Л*Лх = Л*ь. (10) Уравнение (10), в отличие от (8), всегда имеет решение. Действительно, непосредственной проверкой убеждаемся, что кег Л*Л = кегЛ. Необходимым и достаточным условием существования решения линейной системы уравнений (10) является ортогональность правой части ядру матрицы системы, т.е. вектор Л*ь должен быть ортогонален ядру кег Л* Л, которое, как мы отметили выше, совпадает с ядром кег Л. Но из вида правой час;ти видно, что она действительно ортогональна ядру Л. Таким образом, система (10) всегда имеет решение. В общем случае таких решений может быть несколько. = 2Ck\\AjV + 2(Awj, е) = О, откуда При таком выборе Ск ф(.+ 1).+12.2 (А (AWj, =) jk = arg max -----, х*+ = х + Ckffj 3 IIAwjII Описываемый ниже метод заключается в минимизации функционала ф(у) методом оптимального покоординатного спуска; на каждом шаге выбирается координата, спуск по которой будет оптимальным в смысле минимизации Ф(у). В качестве координатных (базисных) векторов можно выбрать любую ортонормированную систему. Пусть wi,..., - ортонормированная система векторов в R,n (не обязательно базис) и A-Wj 7 О по крайней мере для одного из векторов. Обозначим через W линейную оболочку векторов wi,..., w. Будем искать вектор, минимизирующий функционал невязки Ф(у) на подпространстве W. Для этого рассмотрим следующий итерационный метод. Положим х = 0. Если приближение х* уже найдено, то следующее приближение х* * будем искать в виде х* * = х* -- CWj, Ск = const, где jk = argmin (ттФ(х=+)). (11) Наряду с приближениями х* введем невязки = Ах - ь. (12) Вьшишем условия минимума функционала Ф(х ) по Ск- Имеем Ф(х=+) = WCkAj + Лх= - bf = ClWAvj.f -н 2Cfc(Awj, + lief - (13) Заметим, что при поиске минимума Ф(х ) достаточно рассматривать только те Wj, для которых Awj ф О, так как в противном случае значение функционала не меняется. Функция Ф(х ), как функция переменной Cki является многочленом второй степени, причем коэффициент при С положителен в силу замечания выше. Отсюда следует, что минимум Ф(х*+) по Ск при фиксированном j существует и единствен, если j4wj ф 0. Таким образом, из (13) следует, что Ск удовлетворяет уравнению дЧУ) .... 2 , о., iHw,j2 (14) 4) Следующее приближение х вычисляем по формуле x=+i=x=-hCfcW . (15) Найдем трудоемкость метода. Для этого оценим число арифметических операций на шаге. Прежде всего заметим, что предварительные операции (этап 1) требуют в общем случае 0{rnq) операций. Этап 3 итерационного метода требует 0{mq), а этап 4--0(т) арифметических операций. Таким образом, общая трудоемкость метода составляет 0(т -- mql) арифметических операций, где / - число шагов итерационного процесса. Отметим также, что jk из (14) находится в общем случае неоднозначно (таких индексов может быть несколько). В этом случае в качестве jk можно брать, например, наименьший. Исследуем сходимость итерационного метода. Имеет место Лемма. Пусть gi, , gi - произвольный набор линейно независимых единичных векторов из Rm и L - линейная оболочка этих векторов. Тогда существует 7, О < 7 < 1, такое, что для любого х Е L справедливо неравенство lx-(x,gfc)gfcK7x, /г = argmax (х, gj). Доказательство. Положим (х) = х- (Х, gfc)gA;f, к = arg max(x, gj). Покажем, что функционал (х) непрерывен. Для этого достаточно показать непрерывность функционала (х, g), где к определено выше. Рассмотрим разность (х, gA;) -(у, gi), где индекс к определен выше, а г - индекс, определяемый аналогичным образом для у. Суммируя вышесказанное, получаем следующий алгоритм: 1) Вычисляем векторы Awj, j = 1,..., q, и их нормы Awj; в дальнейшем рас;сматриваем только те векторы Wj, для которых Awj ф 0. Не уменьшая общности, будем считать, что число таких векторов равно q. 2) Выбираем х на основе априорной информации; в частности, можно взять х = 0. 3) Если х* найден, то у и вычисляем по формулам 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 |