Амосов А.А., Дубинский В.А., Копченова Н.В. Вычислительные методы для инженеров (1994) (1095853), страница 30
Текст из файла (страница 30)
Схема полного выбора по сравнению со схемой частичного выбора дает существенное замедление роста элементов матрицы. Доказано, что для нее коэффициент роста у(т), входящий в оценку (5.43), не превышает величины т '~ (2'3 '~.4'а ... т' '" ы) 'э ~ 1.8то ~5~" ~а (что значительно меньше соответствующего значения у(т) = 2м ' для схемы частичного выбора). Подчеркнем, что до сих пор еще не найдено матрицы, для которой полный выбор дал бы значение у(т) > т. Таким образом, для хорошо обусловленных систем этот вариант метода Гаусса является хорошо обусловленным. Однако гарантия хорошей обусловленности достигается здесь ценой значительных затрат на выбор главных элементов.
Для этого дополнительно к (~/а)та аРифметических действий тРебУетсЯ пРоизвести пРимерно тз/3 операций сравнения, что может ощутимо замедлить процесс решения задачи на ЭВМ. Поэтому в большинстве случаев на практике предпочтение отдается все же схеме частичного выбора. Как уже отмечено, ситуации, когда при использовании этого варианта метода Гаусса происходит существенный рост элементов, встречаются чрезвычайно редко.
Более того, эти ситуации могут быть легко выявлены с помощью заложенных в современных программах эффективных методов слежения за ростом элементов матриц. 4. Случаи, когда выбор главных элементов не нужен. Известно, что для некоторых классов матриц при использовании схемы единственно— го деления главные элементы гарантированно располагаются на главной диагонали и потому применять частичный выбор нет необходимости, Так, например, обстоит дело для систем с положительно определенными матрицами, а также с матрицами, обладающими следующим свойством диагонального преобладания: 146 Е ~а~~ < )а,,~, 1=1,2,...,т. у=-1 ф~ (5.45) Матрицы, удовлетворяющие условию (5.45), таковы, что в каждой из строк модуль элемента ан, расположенного на главной диагонали, больше суммы модулей всех остальных элементов строки.
5. Масштабирование. Перед началом решения целесообразно масштабировать систему так, чтобы ее коэффициенты были величинами порядка единицы. Существуют два естественных способа масштабирования системы Ах = Ь. Первый заключается в умножении каждого из уравнений на некоторый масштабирующий множитель а,. Второй состоит в умножении на масштабирующий множитель а1 каждого 1'-го столбца матрицы, что соответствует замене переменных т' = а.'ю (фактически — это 1 1 3 замена единиц измерения). В реальных ситуациях чаще всего масштабирование может быть выполнено без существенных трудностей.
Однако подчеркнем, что в общем случае удовлетворительного способа масштабирования пока не найдено. На практике масштабирование обычно производят с помощью деления каждого уравнения на его наибольший по модулю коэффициент. Это вполне удовлетворительный способ для большинства реально встречающихся задач. ~ 5.6 Метод Гаусса и решение систем уравнений с несколькими правыми частями, обращение матриц, вычисление определителей (5.46) Ав= Н(~>, Ая= И<2), ..., Ав= Н(р> с одной матрицей А и различными правыми частями Н<п, 0~2>, 4(р) .
Конечно, применяя метод Гаусса к каждой из систем (5.46) независимо от других, можно найти соответствующие решения х<~>, я<2,, ..., 147 Рассмотрим применение метода Гаусса к решению следующих задач линейной алгебры. 1) вычисление решений системы уравнений с несколькими правыми частями; 2) вычисление обратной матрицы; 3) вычисление определителя. 1. Вычисление решений системы уравнений с несколькими правыми частями.
Довольно часто на практике встречается ситуация, когда нужно решить несколько систем уравнений (5.47) х<» — А >Н<>>, в<2> — А >И<2>, ..., в<>,> — — А >И<г> Однако суммарные затраты при таком подходе составят примерно 2тз + 2р»>2 операций, в то время как при одновременном решении методом Гаусса эквивалентной системы (5.46) получаем значения х<>>, х<2>, „х<»> примерно за (~/з)т + 2рт операций. Следовательно, и в этом случае вычисление А ' нецелесообразно. 148 х<„>, затратив примерно (2/э)р>пз арифметических операций. Однако при одновременном решении систем (5.46) число операций можно существенно сократить. Как было отмечено в 8 5.5, основные вычислительные затраты в методе Гаусса связаны с преобразованием матрицы к треугольному виду. Преобразование же правой части производится параллельно и требует примерно т2 арифметических операций.
Если параллельно с приведением матрицы А к треугольному виду преобразовать по однотипным формулам все » правых частей, то на прямой ход метода будет затрачено только примерно (2/э)»>з + рт2 операций. С учетом обратного хода общие вычислительные затраты составят примерно (2/э)»>~ + 2рта2 арифметических операций. Преобразование правых частей не обязательно производить параллельно. Каждую из правых частей И<», «<2>, ..., И<1,> можно обработать последовательно, если после приведения матрицы А к треугольно-!; му виду А<"" сохранить в памяти ЭВМ множители р,~ и матрицу'" А<~ '>. 2.
Вычисл~<ие обратной матрицы Прежде чем переходить к изложению метода вычисления обратной матрицы А > для квадратной невырожденной матрицы А, отметим, что в действительности проблема вычисления обратной матрицы возникает не так часто, как это можно предполагать. К сожалению, зачастую обращение матрицы А производится с единственной целью вычислить по известному вектору в вектор я вида х = А 'в.
Умножение матрицы А ' на вектор требует примерно 2»>2 арифметических операций. Однако вычисление А ' обходится (как будет показано ниже) примерно в 2п>з операций. Это означает, что на вычисление решения системы Ав = в по формуле в = А <Ь будет затрачено примерно 2т' операций. В данном случае х можно найти в 3 раза быстрее методом Гаусса и вычисление А ' не нужно. Более того, можно ожидать, что вычисленное методом Гаусса решение окажется точнее, так как потребуется выполнение меньшего числа операций.
Может показаться особенно выгодным предварительное вычисление матрицы А >, если далее потребуется найти большое число векторов по формулам в = В'СА 'Жд'и. (5.48) Если у исследователя нет достаточного опыта решения задач линейной алгебры на ЭВМ, то он может принять решение о необходимости вычислять матрицы В', А ', З', с тем чтобы действовать далее по формуле (5.48). Однако и в этом случае можно поступить иначе и найти в с меньшими затратами. Решая систему Рх = ю, найдем х = З 'ик. Затем вычислим у = И~х и, решая систему Ал = у, найдем г = А 'у. Наконец, вычислим а = Сл и, решая систему Ви = и, найдем и= В'и. Сказанное выше вовсе не означает, что нет ситуаций, когда вычисление матрицы А ' необходимо и оправдано.
В ряде технических приложений и статистических задач непосредственный интерес представляет анализ свойств именно обратной матрицы, Тем не менее, как мы видим, в матричных вычислениях можно и следует обходиться без вычисления обратных матриц. Авторы настоятельно рекомендуют не вычислять обратные матрицы, если только в дальнейшем не предполагается анализ элементов этих матриц, Покажем, как вычисление обратной матрицы можно свести к рассмотренной выше задаче решения системы уравнений с несколькими правыми частями. Обозначим матрицу А ' через У, ее столбцы — через в~, е2, ..., е~ и столбцы единичной матрицы Š— через еь е2, ..., е .
Согласно определению обратной матрицы верно равенство АУ = Е, эквивалентное совокупности равенств (5.49) Ав~ — е~, Ав~ — — е2, ..., Ае = е~. Таким образом, столбцы матрицы К = А ' (а следовательно, и саму матрицу), можно найти, решая т систем уравнений с общей матрицей 149 Иногда в пользу необходимости вычисления А ' приводится следующий довод. Если известно, что в течение длительного времени потребуется неоднократно решать системы уравнений вида (5.46) с фиксированной матрицей А и различными правыми частями 4~~~, то имеет смысл предварительно вычислить А ~.
Записав 14 ~ в память ЭБМ, можно затем по мере необходимости быстро вычислять х<ь~ по формуле з< Ь~ — — А ~Ю< 1,~. Однако использование АГ-разложения матрицы А (см. ~ 5.7) позволяет вычислять х~ ~> столь же быстро, а предварительная работа на этапе разложения дает трехкратную экономию. Таким образом, и этот довод в пользу необходимости вычисления обратной матрицы неубедителен. Довольно часто при решении различных задач средствами линейной алгебры возникают выражения типа А. Согласно изложенному выше, для этого потребовалось бы примерно (8/э) тз арифметических операций, однако учет специального вида правых частей системы (5.49) позволяет вычислять матрицу А ~ примерно за 2тз операций.
3. Вычисление определителя. Воспользуемся алгоритмом метода Гаусса с выбором главного элемента по столбцу и заметим, что искомый определитель и определитель полученной треугольной матрицы А'" " связаны равенством с1е$ А = ( — 1)~ с1е$ А'~ ~>, где з — число потребовавшихся перестановок строк. Остается восполь- зоваться формулой (5.17) и тогда получим с1еС А = (-1)~ асо> аы> ас -ы 11 22 '" вт 1 (5.50) где а<о> = ап. Отметим, что вычисление по формуле (5.50) требует особой аккуратности, в особенности если число т велико.
Как мы убедились в примере 3.29, при вычислении произведений следует специальным образом упорядочивать сомножители. Неудачный порядок их расположения может привести к аварийному останову по переполнению либо к исчезновению порядка. Можно избежать переполнения и исчезновения порядка, если для вычисления с1е$ А воспользоваться формулой 1и ~ с1еФ А ) = Х 1п ~ а <.! " ~ . вс Однако следует иметь в виду, что ее использование может привести к некоторой потере точности, 3 а м е ч а н и е. Действительная необходимость в вычислении определителей возникает довольно редко.
Во всяком случае основанные на их использовании алгоритмы оказываются весьма неэффективными (как в примере 3.34, где обсуждалось правило Крамера), и поэтому вычисление определителей давно уже не является элементом современных алгоритмов линейной алгебры. Кроме того, из результатов в ~ 5.4 следует, что использование величины с1еФ А для определения степени близости системы уравнений к вырожденной дает весьма ненадежный и сомнительный критерий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
