|
| |
|
Слаботочка Книги § 2. Метод отражений В настоящее время разработано так много точных методов численного решения систем линейных алгебраических уравнений, что даже простое перечисление их затруднительно. Большинство этих методов, как и метод исключения Гаусса, основано на переходе от заданной системы Ах = b к новой системе С Ах = СЬ такой, что система Вх = d, где В = С А и d = СЪ, решается проще, чем исходная. При выборе подходящей матрицы С нужно учитывать по крайней мере следующие два фактора. Во-первых ее вычисление не должно быть чересчур схюжным и трудоемким. Во-вторых, умножение на матрицу С не должно в каком-то смысле портить матрицу А (мера обусловленности матрицы не должна меняться сильно (см. § 11)). Этим условиям в определенной степени удовлетворяет описываемый ниже метод отражений. Среди методов, требующих для своей реализации числа операций N ~ 2jn/3, этот метод в настоящее время рассмаг тривается как один из наиболее устойчивых к вычислительной погрешности. Рассмотрим случай вещественной матрицы А. Если w -некоторый вектор-столбец единичной длины, (w, w) = 1, то матрицу и = Е- 2ww называют матрицей отражений. Под ww здесь понимается матрица, являющаяся произведением вектора-столбца w на вектор-строку w, т.е. ww- = {wij), где Wij = WiWj. Из определения следует, что ww - симметричная матрица. Непосредственной проверкой убеждаемся, что U - и ии = {Е- 2ww)(£; - 2ww) = Е- 2ww - 2ww -f 4wwww = E; здесь мы воспользовались тем, что ww = (w, w) = 1. (1) Таким образом, матрица С/- симметричная и ортогональная. Напомним один факт из алгебры. Пусть U ж В - две матрицы порядка т, В- многочлен т и, В = Pi{U). Тогда можно переупорядочить их собственные значения так, что = Pi{X) при j = 1,..., m. Поскольку и симметрична и С/ = UU = Е, а, все собственные числа Е равны 1, то все собственные числа матрицы U удовлетворяют условию Xfj = 1, т.е. равны или -1-1 или -1. Собственному значению -1 отвечает собственный вектор w. В самом деле, C/w = W - 2ww-w = w - 2w - - w. (2) § 2. Метод отражений Все векторы, ортогональные вектору w, являются собственными. Им соответствует собственное значение, равное +1. Действительно, пусть (v, w) = 0. Тогда имеем [/v = V - 2ww-v = V - 2w(w, v) = V. (3) Представим произвольный вектор у в виде у = z + v, где z = 7W, (v, w) = 0. Для этого следует взять в качестве z проекцию вектора у на вектор w, т. е. z = (у, w)w, и v = у - (у, w)w. Вследствие (2) и (3) имеем Uy = -z + v. Таким образом, Uy есть зеркальное отражение вектора у относительно гиперплоскости, ортогональной вектору w. Используя геометрические свойства матрицы отражений, нетрудно решить следующую задачу: подобрать вектор w в матрице отражений так, чтобы заданный вектор у 7 О имел в результате преобразования Uy матрицей отражения U = Е - 2ww- направление задашюго единичного вектора е. Так как U - ортогональная матрица, а нри ортогональных преобразованиях длины векторов сохраншотся, то мы должны иметь Uy = ае или Uy = -ае, , где а = (у, у). Поэтому направление, перпендикулярное плоскости отражения, будет определяться либо вектором у - ае, либо вектором у + eve (см. рис. 6.2.1). Таким образом, векторы wi = ±р~[{у- ае) или W2 = ±р(у + ае), где pi = д/(у-ае, у-ае), р2 = \/{у + ае, у-Ьае), будут искомыми. Ясно, что данный процесс всегда осугцествим. Если векторы у и е коллинеарны, а в этом случае либо Pi, либо р2 будет равно нулю, то никаких отражений делать не надо. Матрицы отражения нашли широкое применение при численном решении различных задач линейной алгебры (в частности, в рассматриваемой нами задаче приведения матрицы системы уравнений к треугольному виду). Лемма. Произвольная квадратная матрица может быть представлена в виде произведения ортогональной и верхней треугольной матриц. Доказательство. Пусть дана квадратная матрица порядка т. Будем Приводить ее к правой треугольной матрице путем последовательного Умножения слева на ортогональные матрицы. На первом шаге приведения рассмотрим в качестве вектора у из предыдущего рассуждения Черный столбец матрицы А: У1 = (ац,-.., Otoi). сли = аз1 = = = о, то переходим к следующему шагу, поло-*ив Л) = Л, Ui= Е и введя обозначения aj = aij. В противном случае  Рис. 6.2.1 умножаем матрицу А слева на матрицу отражения U\ ~ Ещ - 2wiw где wi подбирается так, чтобы вектор Uiyi бьш коллинеарен вектору ei = (1, О,0)-. Здесь и далее Dg - единичная матрица размерности q. На этом первый шаг закончен, и на следующем шаге будем рассматривать матрицу Л) с элементами aj\ которая либо равна А, если имеет место первый случай, либо Л = UiA, если имеет место второй случай. Пусть мы уже осуществили Z -1 > О шагов и пришли к матрице А~) с элементами такими, что af = О при г > j, j = 1, 2,..., / - 1. В пространстве Rm-i+i векторов размерности т - 1 + 1 рассмотрим вектор Если а1\ = = = О, то переходим к следующему шагу, полагая = А~\ Ui = Е. В противном случае строим матрицу отражения Ц = Efn-1+i - 2Wi-wf (размеры матрицы V/ и вектора w/ равны т~ I + 1), переводящую вектор в вектор, коллинеарный = (1, О,..., 0) G Rrn-i+i, и переходим к матрице Л = UlA-, здесь Ui = 0 V ) процесс всегда осуществим, и после (т - 1)-го шага мы приходим к матрице Л( -1) = U ,iU,n-2 UiA, имеющей правую треугольную форму. Если обозначить Um-iUm-~2 - Ui = (7, то из последнего равенства следует, что А = и А ~\ где (/ - ортогональная, а Л ) - правая треугольная матрицы. Лемма доказана. Вернемся к решению системы Лх = Ь. С помош,ью указанных преобразований отражения последовательно приводим ее к эквивалентному виду (m-l) = C/b, где Л * )-правая треугольная матрица. Если все диагональные элементы Л* отличны от нуля, то последовательно находим ж, Если же хотя бы один из диагональных элементов равен нулю, то последняя система вырождена и в силу эквивалентности вырождена и исходная система. Задача 1. Получить асимптотику числа операций метода отражений при т оо. 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 |