Разряженные матрицы. Р. Тьюарсон (984138), страница 5
Текст из файла (страница 5)
Все остальные элементы матрицы 7.» равны нулю. Теперь из (2.2.2) получаем А<я+и = 7„... 7,7<Ан<. (2.2.5) Если положить ~п '' ~'271 (2,2.б) и учесть, что А<Н ичч А и А<"+Н = У, то вместо формул (2.2.5) и (2.2.6) получим 0=7.А. (2.2.7) Таким образом, прямое гауссово исключение состоит в нахождении нижней треугольной матрицы 7. (произведение нижних треугольных матриц дает также ннж. нюю треугольную матрицу), которая преобразует матрицу А в верхнюю треугольную матрицу К Имея в виду уравнение (2.2.7) н то, что операторы Ь» применяются к обеим частям уравнения (2.2.1), приходим ЗЗ 2.2. Основной метод в результате гауссова исключения к уравнению Ух = 1.Ь. (2.2.8) Обратная подстановка метода Гаусса состоит в решении уравнения (2.2.8), которое производится следующим образом.
Пусть хт означает 1-й элемент вектора х. Тогда последний элемент х„равен последнему элементу вектора-столбца Ы, так как в послед- х-ц овааЗец (' 4-я сшрака Рис, 2.2,3, Элементарная матрица иа й.шаге обратной подста- новки. ней строке матрицы У равны нулю все элементы, кроме последнего, равного единице.
Это значение х„подставляется в предыдущее уравнение, что позволяет легко вычислить х ь Подстановка х и х„, в (л— — 2)-ю строку уравнения (2,2.8) дает х я и так далее. Для того чтобы описанную выше обратную подстановку выразить в матричных обозначениях, отметим прежде всего, что а)'+и является (й 1).м элементом матрицы У.' Это следует из того факта, что 1-я строка матрицы А в формуле (2.2.2) видоизменяется только до й = 1 и затем остается неизменной. Другими словами, !-е строки матриц Анен и У совпадают Обратная подстановка метода исключения Гаусса может быть теперь определена следующим образом: и,...
и„,и„и-~„, (2.2.9) 2 Р, тьюарсоя Гл. 2. Метод исключения Гаусса где Ц=1„+~<не',, й=н, и — 1 ... 2, (2.2.10) и элементы вектора-столбца ~<Ю задаются в виде ф= — а",~'>, с < й и Цы=О, с) й (2.2.11) (рис. 2.2.3). Таким образом, все диагональные элементы матрицы (2к равны единице, а в Ьм столбце наддиагональные элементы принимают значения Цм(с=1, 2, ..., й — 1). Все остальные элементы (/к являются нулями. Теперь можно описать обгций результат применения процессов прямого исключения и обратной подстановки к матрице А.
Из уравнения (2.2.9) получим 0 =(2, ... (с„~У„, (2.2.12) и из (2.2.8), (2.2.6) и (2.2.12) следует к=У 'ЕЬ=У, ... (Г„,(2„(.„... ЦЕ,Ь. (2.2.13) 2,3. Выбор главного элемента и ошибки округления Элемент а<Д в формулах (2.2А) называется главным элементом й-го шага исключения. Так как в памяти ЭВМ числа хранятся в ячейках конечной длины, то при вычислениях, вообще говоря, вносятся ошибки округления. Для того чтобы минимизировать влияние ошибок округления при гауссовом исключении, Унлкинсон (1965) предлагает для полных (иеразреженных) матриц изложенные ниже способы.
Его рекомендации основаны на том обстоятельстве, что эти способы позволяют получить границы для ошибок, и, кроме того, было показано, что процесс вычислений устойчив. Первый способ, называемый частичным улорлдоче. нигм (частичным выбором главного элемента), заключается в следующем. На й-м шаге выбирают наиболь. ший по абсолю~ ному значению из элементов Ь-го столбца матрицы А<">, расположенных в и-й строке илн ХЗ, Выбор главного элемента и ошибки округления 35 ниже ее, а именно ~!а',эг!)=тах!агэлг1, й <г'(п, (2.3.1) и переставляют з-ю и й-ю строки матрицы Абп перед выполнением вычислений й-го шага по формуле (2.2.2).
Конечно, все такие перестановки строк должны запоминаться для дальнейшего использования. Второй способ минимизации влияния ошибок округления, называемый полным упорядочением (полным выбором главного элемента), может быть описан следующим образом. На й-м шаге (при каждом й) выбирают наибольший по абсолютному значению из элементов, расположенных в последних и — й+ 1 строках и столбцах матрицы А!и!, а именно '!а!э!)=тах(аггД, й:=;г,/и" и, (232) е! и переставляют з-ю и Ью строки и 1-й и й-й столбцы матрицы А(М перед выполнением вычислений й-го шага по формуле (2.2.2). Эти перестановки строк и столбцов запоминаются для дальнейшего использования при нахождении решения. Во многих практических приложениях, в которых встречаются большие разреженные матрицы, вместо частичного или полного упорядочения обычно достаточно убедиться в том, что все главные элементы больше некоторого числа в, называемого допустимым значением главного элемента (Тьюарсон (19Б9а) ).
Это в особенности справедливо для линейного программирования (Класен (19бб)), в котором матрицы, как правило, больших размеров и разрежены. При значениях главных элементов больше допустимого е устраняется возможность выбора главного элемента с таким малым значением, которое привело бы к затруднениям в вычислениях из-за ошибок округления. На практике было найдено, что для большинства задач, включающих большие разреженные матрицы, значение е =!О-э является удовлетворительным, если при вычислениях в памяти хранятся 9 или 10 десятичных разрядов ненулевых элементов. Конечно, для полных (неразрежбиных) матриц необходимо произ- Гл. л, Метод исключения Гаусса водить частичное или полное упорядочение.
Если не. которые элементы становятся в процессе вычислений очень малыми (менее так называемого критического значения), то рекомендуется приравнивать их нулю (Класен (1966)). Вулф (1965) предлагал принимать критическое значение равным 10-'. 2.4. Элиминативная форма обратной матрицы Разложение матрицы А-' на множители может быть получено из равд. 2.2 следующим образом. Обычное решение уравнения (2.2.1) для произвольного д дается в виде х = А-с(с. Поэтому, сравнивая это с решением, которое дается формулой (2.2.13), мы заключаем, что А ' = У~ ... У„|У„Ь„...
ЦЕ,. (2.4.1) Такое представление матрицы А-' называется элиминагивной формой обратной матрицы и обозначается через ЕР1. Таким образом, матрица А-' выражается в виде произведения и нижних и и — 1 верхних треугольных матриц, Одним из главных преимуществ формы ЕР1 является легкость, с которой она может быть слева или справа умножена на данный вектор, как это показано ниже. Пусть рс обозначает с-й элемент вектора-столбца р.
Тогда из формул (2.2.10 )и (2.2.11) следует, что (см. также рис. 2.2.3) е,'. (У р) = рс + Д»>р», с ( й, е', (У р) = рс, с ~ )й. (2.4,2) Таким образом, умножение вектора-столбца слева на матрицу У» эквивалентно добавлению к данному век. тору-столбцу его й-го элемента, умноженного на вектор-столбец $<»с. Имеем также (р'У»)ес =рс, с ~ й, (рсУ|) е» = р'Я+ ры (2.4.3) 2.4. Элиминатионал форма обратной матрицы Зт и, следовательно, умножение вектора-строки Р' справа на матрицу Уд оставляет все элементы Р' без изменений, за исключением й-го элемента, к которому добавляется скалярное произведение векторов Р' и ~~д~.
Из формул (2.2.3) и (2.2.4) имеем (см. также рис. 2.2.2) е, '(Т. Р) = р„) < м, е', (Т.дР) = т1<дд>Рд, (2.4.4) е',(Х др) = т)7'Рд + Р„ 1 > й. Таким образом, произведение Едр может быть получено, исходя из вектора Р, посредством замены его йго элемента нулем и добавления к нему вектора- столбца рдт)<д). Также имеем (Р ЯЦ=Рт 1Ф Й (2.4.9 (р'Т.д) о, = р'ц" Следовательно, умножение вектора-строки р' справа на матрицу Т.д оставляет все его элементы без изменения, за исключением й-го элемента, который заменяется скалярным произведением векторов р' н трд>. Вычисление произведения А-'и, где и есть вектор- столбец, а матрица А-' задана в элимийативной форме Ег1 выражением (2.4.1), может быть организовано таким образом, чтобы на первых п шагах применялись формулы (2.4.4), а на последних и — 1 шагах примеиялнсь формулы (2.4.2).
Вектор-столбец, образованный на очередном шаге„используется на следующем шаге таким образом: А я=У~(... (У„(4-„..*(Тт(Т-,п))...). Подобным же образом может быть вычислено произведение и'А-' с помощью формул (2.4.3) и (2.4.5). Вектор-строка, образованная на очередном шаге, используется на следующем шаге таким образом. и'А ' = ( .. * ((и'Уд) Уз) ° ° ° Уи) Т и) ° ° ) Ти Теперь, в силу соотношений '(2.2.3), (2.2.4), (2.2.10)', (2.2.11) и (2.4.1), очевидно, что д.я вычисления ЕР! Гл.
Д Метод исклюееиаа Гаусса 38 требуются только ненулевые элементы векторов-столб. цов Ч(ю и $м~. Поэтому должны храниться только этн элементы (вместе с соответствующей информацией об их местонахождении в памяти). Для большой разреженной матрицы особенно требуется экономия в объеме памяти, необходимой для их хранения, поэтому важно определить элиминатнвную форму обратной матрицы ЕР1 так, чтобы этот объем был минимальным, Другими словами, необходимо минимизировать количество ненулевых элементов всех векторов-столбцов т1~Ю и ~~а~. Покажем теперь, каким образом можно это осуществить.
2.5. Минимизация общего числа ненулевых элементов в ЕГ1 Из разд. 2.2 мы вспоминаем, что на каждом шаге гауссова исключения умноженная на различные коэффициенты строка вычитается из ряда других строк матрицы. Это обычно приводит к образованию новых ненулевых элементов вместо нулевых. Например, если к началу й-го шага ненулевыми являются элементы а<">, аоа и а'ю, а а<м=О, где с', 1) й то из ьь ы ы и ! формул (2.2.2), (2.2.3) и (2.2А) следует,'что в конце А-го шага асу' м' а'."+О =— с! , ьн (2.5.1) Ясно, что элемент а<"+и ненулевой. Таким образом, при упомянутых выше условиях нуль в (с, 1)-й позиции матрицы Анч превратился в ненулевой элемент матрицы Ась+'>.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
