|
| |
|
Слаботочка Книги 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 причем все sa > О, D - диагональная матрица с элементами da, равными +1 или -1. Матричное равенство (6) образует систему уравнений o-ij = siiSijdii ------1- SijSijdii при i j. Аналогичные уравнения при г > j отброшены, так как уравнения, соответствующие парам {г, j) и {j, г), эквивалентны. Отсюда получаем ре-кзфрентные формулы для определения элементов da и Sij-. (Чг - Е \ki\dkk I , п - л \ к=\ J \ da = sign - Е kiSkjdkk fc=l . . -- при г < J. Матрица S является правой треугольной, и, таким образом, после получения представления (6) решение исходной системы также сводится к Последовательному решению двух систем с треугольными матрицами. Заметим, что в случае А > О все дц 1 и Л = S*S. бое, меняющем Есартину накопления вычислительной погрешности. Наряду с исходной системой тем же методом решается система (аЛ)х = РЪ, где а и /? - числа. При а и /?, не являющихся целыми степенями двойки, сравнение векторов х и аР~х дает представление о величине вычислительной погрешности. Например, можно взять а = л/2, 0 = \/3. Изучение многих задач приводит к необходимости решения систем линейных уравнений с симметричной положительно определенной матрицей. Такие системы возникают, например, при решении дифференциальных уравнений методом конечных элементов или же конечно-разностными методами. В этих случаях матрица системы имеет также и ленточную структуру. Для решения таких систем, а также систем уравнений более общего вида с эрмитовой не обязательно положительно определенной матрицей применяется метод квадратного корня {метод Холецкого). Матрица А представляется в виде А = S*DS, (6) где S - правая треугольная матрица, S* - сопряженная с ней, т. е. / ... \ S = [ О S22 Задача 3. Оценить число арифметических операций и загрузку памяти ЭВМ (при условии aij = aji объем памяти, требуемый для запоминания матрицы А, уменьшается) при решении системы с веш;ественной положительно определеннной матрицей А методом квадратного корня. Многие пакеты прикладных программ для решения краевых задач математической физики методом конечных элементов организованы по следующей схеме. После формирования матрицы системы А путем перестановки строк и столбцов (одновременно переставляются г-я и j-я строки и г-й и j-й столбцы) система преобразуется к виду с наименьшей шириной ленты. Далее применяется метод квадратного корня. При этом с целью уменьшения объема вычислений при решении системы Ах. = b с другими правыми частями матрица S запоминается. Замечание. Часто этот метод уступает по эффективности итерационным методам. Задача 4. Оценить число арифметических операций и объем требуемой памяти метода квадратного корня в ачучае матриц ленточной структуры. Если есть подозрение, что реально полученное решение сильно искажено вычислительной погрешностью, то можно поступить следующим образом. Определим вектор = Ъ - Ах. Погрешность = х - удовлетворяет системе уравнений Аг Ах-Ах = Ъ. (7) Решая эту систему в условиях реальных округлений, получаем приближение г) к г. Полагаем х = х-Ь г. Если точность нового приближения представляется неудовлетворительной, то повторяем эту операцию. При решении системы (7) над компонентами правой части производятся те же линейные операции, что и над компонентами правой части при решении системы (1). Поэтому при вычислениях на ЭВМ с плавающей запятой естественно ожидать, что относительные погрешности решений этих систем будут одного порядка. Поскольку погрешности округлений обычно малы, то Ь <§: Ь; тогда г < х, и, как правило, решение (7) определится с существенно меньшей абсолютной погрешностью, чем решение системы (1). Таким образом, применение описанно1ю приема приводит к повышению точности приближенного решения. Особенно удобно применять этот прием, когда по ходу вычислений в памяти ЭВМ сохраняются матрицы В л D. Тогда для каждого уточнения требуется найти вектор Ь = b - Ах и решить две системы с треугольными матрицами. Это потребует всего Ni ~ 4т арифметических операций, что составит малую долю от числа операций No ~ 2т/3, требуюпщхся для представления матрицы А в виде А = BD. Идея описанного приема последовательного уточнения приближений к решению часто реализуется в такой форме. Пусть матрица В близка в каком-то смысле к матрице А, но решение системы Вл = с требует существенно меньшего объема вычислений по сравнению с решением системы Лх - Ъ. Решение системы Вх = b принимаем в качестве первого приближения х к решению. Разность X - удовлетворяет системе уравнений Л(х-х) = Ь-Лх. Вместо решения этой системы находим решение системы Рг = Ь - Лх и полагаем х = х -I- . Таким образом, каждое приближение находится из предыдущего по формуле х +1 = х -I- В-{Ъ - Лх ) = (Е- Р-М)х -f- Б-%. Если матрицы А и В достаточно близки, то матрица Е - ВА имеет малую норму и такой итерационный процесс быстро сходится (см. также § 10). Значительно более редкой, чем задача решения системы уравнений, является задача обраш,ения матриц. Для обратной матрицы X = А~ имеем равенство АХ = BDX = Е. Таким образом, для нахождения матрицы X достаточно последовательно решить две матричные системы BY = Е, DX = Y. Нетрудно подсчитать, что при нахождении на таком пути матрицы Л~ обгций объем вычислений составит N2 ~ 2т арифметических операций. В случае необходимости уточнения приближения к обратной матрице могут производиться при помощи итерационного процесса Х = Xk-i{2E - AXk-i). Для исследования сходимости итерационного процесса рассмотрим матрицы Gk = Е - АХк- Имеем равенство Gk=E-AXk = E- АХк-х{2Е - АХк-х) = {Е ~ AXk-xf = Gl. Отсюда получаем цепочку равенств Gk = Gl i = Gj. 2 = = Go Поскольку - Xk = А-\Е - АХк) = A-Gk = A-Gl , то имеем оценку \\A--Xk\\\\A-\\-\\Go\f. Таким образом, при достаточно хорошем начальном приближении, т.е. если -ЛХоЦ 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 |