Главная Численные методы при исследовании физических задач



где знак зависит от того, четной или нечетной была суммарная перестановка строк. Для вычисления определителя требуется примерно ячеек памяти и /п арифметических действий.

На примере вычисления определителя можно убедиться в экономичности хороших численных методов. Вспомним формальное определение определителя как суммы всевозможных произведений элементов, взятых из разных строк и столбцов. Таких произведений имеется л! = \2лп (п/е)", и прямое их вычисление уже при небольших лявЗО требует астрономического числа действий - более 1030, что вряд ли когда-нибудь станет под силу ЭВМ. А метод исключения легко позволяет вычислять определители сотого и более порядка.

Перейдем к вычислению обратной матрицы. Обозначим ее элементы через а. Тогда соотношение АА~ = Е можно записать так:

J] щссы = бц, Ki, /л. (9)

Видно, что если рассматривать 1-й столбец обратной матрицы как вектор, то он является решением линейной системы (9) с матрицей А и специальной правой частью (в которой на 1-м месте стоит единица, а на остальных - нули).

Таким образом, для обращения матрицы надо решить п систем линейных уравнений с одинаковой матрицей А и разными правыми частями. Приведение матрицы А к треугольной по формулам (4)-(5) делается при этом только один раз. В дальнейшем при помощи чисел ск по формуле (5) преобразуются все правые части, и для каждой правой части делается обратный ход.

При хорошей организации вычислений для обращения матрицы этим методом требуется примерно 2п ячеек оперативной памяти ЭВМ и 2п арифметических действий (можно уложиться в /п ячеек, но это сильно усложняет программу и увеличивает время счета). Заметим, что при обращении матриц контролировать расчет вычислением невязки R = E - AA невыгодно: перемножение матриц требует столько же действий (2=*), как и обращение матрицы!

Любопытно отметить, что обращение матрицы сводится к решению п систем линейных уравнений, а требует лишь втрое больше действий, чем решение одной системы уравнений. Это объясняется тем, что при решении линейной системы большая часть вычислений связана с приведением матрицы к треугольному виду, что при обращении матрицы делается только один раз. Обратный ход и преобразования правых частей выполняются много быстрее.

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



*) Напомним принятую терминологию. Матрица называется верхней треугольной, если все элементы ниже главной диагонали равны нулю (ani - O при i>k); аналогично определяется нижняя треугольная матрица. Почти треугольной называется матрица, элементы которой удовлетворяют соотношению ац, = = 0 при i>+l, т. е. ненулевые элементы имеются не только в верхнем треугольнике, но и в примыкающей к нему «боковой диагонали». Трехдиаго-нальной называется матрица, у которой ненулевые элементы имеются только на главной диагонали и примыкающих к ней, т. е. а;* = 0 при \ i - k\>\. Нетрудно записать определения других типов матриц, изображенных на рис. 25.

4. О Других прямых методах. Есть очень много других прямых методов решения задач линейной алгебры. Рассмотрим формальные характеристики наиболее известных методов.

Метод оптимального исключения имеет ту же скорость и требует той же памяти, что и метод Гаусса. Но если матрица вводится в оперативную память ЭВМ не вся сразу, а построчно, то для метода Гаусса требуется 1/2 ячеек, а для метода оптимального исключения достаточно i/j/j ячеек. Практическая ценность этого преимущества невелика, ибо построчный ввод означает много обращений к внешней памяти, т. е. сильное увеличение времени расчета. Кроме того, при построчном вводе невозможно выбрать главный элемент, что сказывается на ошибках округления.

Метод окаймления мало отличается от метода оптимального исключения и имеет те же характеристики.

Метод отражений требует вдвое большего числа действий, чем метод Гаусса (оперативная память та же).

Метод ортогонализации втрое медленнее метода Гаусса. Им интересовались в надежде на то, что он позволит решать плохо обусловленные системы. Но выяснилось, что при больших п сама ортогонализация приводит к большой потере точности (сравните с разложением функции по неортогональным функциям), и лучше использовать методы регуляризации.

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

Для решения хорошо обусловленных линейных систем общего вида метод Гаусса является одним из лучших; при обращении матрицы немного выгоднее метод Жордана. Но для систем специального вида (например, содержащих много нулевых элементов) существуют более быстрые методы. Некоторые из них будут изложены далее.

5. Прогонка. Пусть матрица А содержит много нулевых элементов, расположенных в матрице не беспорядочно, а плотными массивами на заранее известных местах. Тогда расчет по методу Гаусса можно организовать так, чтобы не включать эти элементы. Тем самым объем вычислений и требуемая память уменьшаются, зачастую очень сильно.

На рис. 25 приведены структуры матриц, которые нередко встречаются в задачах физики и техники и допускают такое ускорение расчета; горизонтальными линиями изображены положения ненулевых элементов, окаймлены границы массивов нулевых и ненулевых элементов. К таким матрицам относятся ленточные (а),, ящичные (в), квазитреугольные (д), почти треугольные (е) и многие другие*). МоЖно показать, что при обходе нулевых элементов решение системы с почти треугольной матрицей требует



всего 2п действий, а с ленточной - даже ЧкЫ, где - ширина ленты, т. е. выигрыш во времени счета очень велик.

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


Рис. 25.

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

Наиболее важным частным случаем метода Гаусса является метод прогонки, применяемый к системам с трехдиагональной матрицей (они часто встречаются при решениях краевых задач для дифференциальных уравнений второго порядка). Такие системы обычно записывают в каноническом виде

= С;, = 0.



0 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


0.0217