|
| |
|
Слаботочка Книги Отметим важный частный случай. Если А - симметричная матрица, то Лтд = = поэтому для А2 = юахЛ*д. (11) Если Лх = Ах, то \\А\\ ЦхЦ Ах = Л ЦхЦ. Следовательно, модуль любого собственного значения матрицы А не больше любой ее нормы. § 1. Методы последовательного исключения неизвестных Рассмотрим точные методы решения системы Лх = Ь; здесь А - [ojj] - матрица размерности т х т, detA ф О, b = (ai,TO+l, , a-m,m+i)-Метод решения задачи относят к классу точных, если в предположении отсутствия округлений он дает точное решение задачи после конечного числа арифметических и логических операций. Если число ненулевых элементов матрицы системы имеет порядок тг?, то для большинства используемых в настоягцее время точных методов решения таких систем требуемое число операций имеет порядок гг?. Поэтому для применимости точных методов необходимо, чтобы такой порядок числа операций был приемлем для данной ЭВМ; другие ограничения накладываются объемом и структурой памяти ЭВМ. Оговорка об используемых в настоящее время методах имеет следующий смысл. Существуют методы решения тшсих систем с меньшим порядком числа операций, однако они не используются активно из-за сильной чувствительности результата к вычислительной погрешности. Наиболее известным из точных методов решения систем линейных уравнений является метод исключения Гаусса. Рассмотрим одну из его возможных реализаций. В предположении, что ац О, первое уравнение системы j Y2ij3 = аг,т+Ь г = 1, . . . , ТП, (1) делим на коэффициент ац, в результате получаем уравнение Затем из каждого из остальных уравнений вычитается первое уравнение, умноженное на соответствуюгций коэффициент ац. В результате эти уравнения преобразуются к виду YajjXj = 4+1, г = 2,..., m. Первое неизвестное оказалось исключенным из всех уравнений, кроме первого. Далее в предположении, что ф О, делим второе уравнение на коэффициент а и исключаем неизвестное из всех уравнений, начиная со второго, и т.д. В результате последовательного исключения неизвестных система уравнений преобразуется в систему уравнений с треугольной матрицей г = 1,..., m. Совокупность проведенных вычислений, в ходе которых исходная задача преобразовалась к виду (2J, называется прямым ходом, метода Гаусса. Из т-го уравнения системы (2) определяем х-щ, из (т - 1)-го -и т. д. до XI. Совокупность таких вычислений называют обратны.м ходом метода Гаусса. Нетрудно проверить, что реализация прямого хода метода Гаусса требует JV ~ 2т/3 арифметических операций, а обратного- N w? арис]> мегических операций. Исключение x.i происходит в результате следующих операций: 1) деления г-го уравнения на 2) вычитания получающегося после твкого деления г-го уравнения, умноженного на а*, из уравнений с номерами к = г + I,..., т. Первая операция равносильна умножению системы уравнений слева на диагональную матрицу \ 1/ вторая операция равносильна умножению слева на матрицу /1 \ Е bijdjk = Щк при кг, 3=1 г Е bijdjk = Пгк при i <к. Воспользовавшись условием, что все da = 1, получаем систему рекуррентных соотношений для определения элементов и dij-. кк = (Чк - Е ззк при к г, i-i (4) Щк - 22, кзЗк 3=1 dik =-г-при г <к. Таким образом, система (2), получаемая в результате этих преобразований, запишется в виде САх = СЬ, где С = Cm...C[Ci. Произведение левых (правых) треугольных матриц является левой (правой) треугольной матрицей, поэтому матрица С левая треугольная. Из формулы для элементов обратной матрицы {А-% = Aji/det А следует, что матрица, обратная к левой (правой) треугольной, является левой (правой) треугольной. Следовательно, матрица В = левая треугольная. Введем обозначение СА = D. Согласно построению все d-n = 1 и матрица D правая треугольная. Отсюда получаем представление матрицы А в виде произведения левой и правой треугольных матриц: А = CD = BD. Равенство А - BD вместе с условием da = 1, i = I,..., тп, образует систему уравнений относительно элементов треугольных матриц В w D : т Yjvik - гк- Поскольку bij = о при г < j л djk = О при к < j, эта i=i система может быть записана в виде inin{z, к} Е iJJl = () или, что то же самое, 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 |