|
| |
|
Слаботочка Книги Вычисления проводятся последовательно для совокупностей (г, к) = (1, 1) ..., (1, гп), (2, 1),..., (2, т),..., (т, 1),..., (т, т). Здесь и далее в случае, когда верхний предел суммирования меньше нижнего, считается, что вся сумма равна нулю. Таким образом, вместо последовательных преобразований системы (1) к виду (2) можно непосредственно произвести вычисление матриц В и D с помощью формул (4). Эти вычисления можно осуществить, если только все элементы Ьц окажутся отличными от нуля. Пусть Ak, В, Df.- матрицы главных миноров А;-го порядка матриц А, В, D. Согласно (3) Ак - BkDk. Поскольку detDk = 1, deti? = Ьи---Ькк-, то detl = Ьи ... bkk- Следовательно, bfcfc = detAfc/det Итк, для осуществления вычислений по формулам (4) необходимо и достаточно выполнение условий det АфО, к = 1,...,т. (5) В ряде случаев заранее известно, что условие (5) выполнено. Например, многие задачи математической физики сводятся к решению систем с положительно определенной матрицей А. Однако в общем случае этого заранее сказать нельзя. Возможен и такой случай: все Aet Ак ф О, но среди величин Ькк есть очень малые и при делении на них будут получаться большие числа с большими абсолютными погрешностями. В резульюте этого решение сильно исказится. Обозначим СЬ = d = (rfi,m-Hij , fm,m-n)- Поскольку С = i? и с А ~ D, то справедливы равенства Bd = b, Dx = d. Таким образом, после разложения матрицы исходной системы на произведение левой и правой треугольных матриц решение исходной системы сводится к последовательному решению двух систем Bd = b, Dx = d с треугольными матрицами; это потребует ~ 2т арифметических операций. Последовательность операций по разложению матрицы А на произведение треугольных матриц и по определению вектора d часто удобно объединить. Уравнения системы Bd = b можно записать в виде (3) rain(i,m-H) Следовательно, значения di,m+i могут вычисляться одновременно с остальными значениями dij по формулам (4). При решении практических задач часто возникает необходимость решения систем уравнений с матрицей, содержащей большое количество ну- При вычислениях без помощи ЭВМ велика вероятность случайных погрешностей. Для устранения таких погрешностей иногда вводят контрольный столбец системы, a i+2 = ( 1, jh+2, , а , ;/,+2)i состоящий из контрольных элементов уравнений системы г, т+2 = Е У При преобразовании уравнений над контрольными элементами производятся те же операции, гго и над свободными членами уравнений. В результате этого контрольный элемент каждого нового уравнения должен равняться сумме коэффициентов этого уравнения. Большое расхождение между ними указывает на погрешности в вычислениях или на неустойчивость алгоритма вычислений по отношению к вычислительной погрешности. К примеру, в случае приведения системы уравнений Ах = b к виду Dx = d с помощью формул (4) контрольный элемент dirn+2 каждого из уравнений системы Dx = d вычисляется по тем же формулам (4). После вычисления всех элементов dij при фиксированном г контроль осуществляется проверкой равенства dij = di +2- Обратный ход метода Гаусса также сопровождается вычислением контрольных элементов строк системы. Чтобы избежать катастрофического влияния вычислительной погрешности, применяют метод Гаусса с выбором главного элемента. Его отличие 9 903 левых элементов. Обычно эти матрицы имеют так называемую ленточную структуру. Более точно, матрицу А называют {2q + 1)-диагональной или имеющей ленточную структуру, если = О при \г - j\ > q. Число 2+1 называют шириной ленты. Оказывается, что при решении системы уравнений с ленточной матрицей методом Гаусса число арифметических операций и требуемый объем памяти ЭВМ могут быть существенно сокращены. Задача 1. Исследовать характеристики метода Гаусса и метода решения системы с помощью разложения ленточной матрицы А на произведение левой и правой треугольных матриц;. Показать, что для нахождения решения требуется 0{mq) арифметических операций (при т, q -> оо). Найти главный член числа операций при условии 1 т. Задача 2. Оценить объем загружаемой памяти ЭВМ в методе Гаусса для ленточных матриц. от описанной выше схемы метода Гаусса состоит в следу10ш,ем. Пусть по ходу исключения неизвестных получена система уравнений Xi + Y2 ~ i,m+li г = I, .... к, Е OfjSj = aj;, +i, ?; = /с + 1,..., r?i. j=k+i Найдем I такое, что a j J = max o! j 1 и переобозначим Xj+i = Xf и xi = Xk.f-i; далее произведем исключение неизвестной x+i из всех уравнений, начиная с {к + 2)-го. Такое переобозначение приводит к изменению порядка исключения неизвестных и во многих случаях существенно уменьшает чувствительность решения к погрешностям округления при вычислениях. Часто требуется решить несколько систем уравнений Ах = Ь, q = с одной и той же матрицей А. Удобно поступить следуюпщм образом: введя обозначения = {Oyljin+qi 5 0,in,m+g) i произведем вычисления по формулам (4), причем элементы dik вычислим при г < к т + р. В результате будут получены р систем уравнений с треугольной матрицей, соответствующих исходной задаче Dx = d, dq = (rfl,m-i-f/, , d n,m+(i) , </ = 1,..., p. Решаем эти системы каждую в отдельности. Оказывается, что общее число арифметических действий при решении р систем уравнений таким способом N ~ 2т/3 + 2pir?. Описанный выше прием иногда используетсл для того, чтобы без существенных дополнительных затрат получить суждение о погрешности решения, являющейся следствием погрешностей округления при вычислениях. Задаются вектором Z с компонентами, имеющими по возможности тот же порядок и знак, что и компоненты искомого решения; часто из-за отсутствия достаточной информации берут Z = (1,..., 1) . Вычисляется вектор с = Лг, и наряду с исходной системой уравнений решается система Аг = с. Пусть х и z ~ реально получаемые решения этих систем. Суждение о погрешности х - X искомого решения можно получить, основываясь на гипотезе: относительные погрешности при решении методом исключения систем с одной и той же матрицей и различными правыми частями, которыми являются соответственно величины х - х/х и z - z/z, отличаются не в очень большое число раз. Другой прием для получения суждения о реальной величине погрешности, возникающей за счет округлений при вычислениях, состоит в изменении масшта- 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 |