Разряженные матрицы. Р. Тьюарсон (984138), страница 7
Текст из файла (страница 7)
Минимизация числа ненулевых елеменгое е Ег( 45 б) элементы ч)((й)при 1) Й в уравнении (2.5.4) определяются равенством т)((й) = — ай(»+и Ки) ! > Й. (2.5.20) а',»+в=а("+'), е, 1> Й, и ((! "е! (! ~ так как Этим завершается доказательство части '(а) теоремы. Теперь из формул (2.5.2), (2.2.3) и (2.5.4) для 1) Й следует в(м в(й) а'й+и = — и т,'и = —, »! = в(й) Ч! = в(м ° йй йй и, имея в виду формулу (2.2.11) и условие д((йй) =а(йй!), получим равенство (2.5.20), что завершает доказательство теоремы.
Закончим этот раздел несколькими замечаниями. Если в формуле (2.5.10) минимум достигается более чем для одной пары значений (1,1), то следует Доказательство. Если мы сможем показать, что а(й+') =а(й+" для й ! ) Й всякий раз, когда а'й) =а(й) (! )! Ц )! для ),1 ) Й, то посредством индукции по Й и из равенства а)',)= а(()!) очевидным образом следует часть «е) теоремы. Так как только диагональные элементы выбираются в качестве главных, то в равенстве 2.5.3 очевидным образом следует Ц»=Р', и д(й!)=д',",' для (,1) Й.
Теперь из формул (2.5.2), (2.2.3) и (2.5.4) при (,1) Й имеем в(й)ам) а('+" =,Й(й) — —,, и и (й! вй» в(й)в(» а("+') = а(й) — — ' (! )! Отсюда следует 46 Гл. л. Метод исключения Гаусса выбрать пару, для которой д<Я~, вычисленное по формуле (2.5.16), имеет наибольшее значение. Из рассмотрения на следующем шаге, таким образом, будет исключено максимальное число ненулевых элементов. Вместо (2.5.15) иногда используют матрицу а =ВМВ (2.5.21) для выбора главного элемента на й-м шаге гауссова исключения. Покажем сейчас, что если на й-м шаге' в качестве главного выбран элемент а',~>к, „то е',.0 е! есть общее число умножений и делений.
Из доказательства теоремы 2.5.!4 и соотношений (2.5.2), (2.5.3) и (2.5.4) очевидно, что одно деление требуется для вычисления 1/а~."~я, +, и Р'„Вне, — 1 и е',В (т„— 1 умножений нужно для вычисления соответственно ч1м> и е,'.Аы+". Кроме того, для исключения а®ь, ~к, Ф О, р ~ 1, требуется общее число в (е,'.Ва(т — 1)(У',Вне, — 1) умножений. Таким образом, на й-м шаге гауссова исключения общее число делений и умножений равно 1+ (Гв е — 1)+(е',В !т — 1)+ + (е',Вд(тн — 1)((тьвье — 1)= е',В Ун(тяв е = = е',В Мвке,. = е',6нен В свете изложенного, если для выбора главного элемента на й-м шаге вместо формулы (2.5.17) мы пользуемся формулой дф= т!пе',б е~ для всех !а,'я+а, чь, ~ ) е, (2.5.22) ь! то минимизируется общее число умножений н делений.
Пусть в качестве меры вычислительных затрат для каждого шага й взято общее число делений и умножений на этом шаге. Тогда для минимизации как заполнения, так и вычислительных затрат следует 2,б. Хранение елиминатиеной формтн обратной.иатрицм 47 пользоваться взвешенным средним значением 6д н ба при выборе главного элемента. Весовые коэффициенты определят относительную важность обоих' крвтериев. Из формул (2.5.21) и (2.5.6) видно, что взвешенное среднее бд и бн есть матрица Ва (М вЂ” ЬВ',Д В, где О = Ь ( 1, а б и 1 — б соответственно весовые коэффициенты. Значение 6 зависит от характеристик вычислительной машины и также от ее математического обеспечения. Следует заметить, что для больших разреженных матриц минимизация локального заполнения более важна, чем минимизация локальных вычислительных затрат, потому что первая, сохраняя разреженность матрицы В„, приводит к минимизации вычислений на следующих шагах.
Если систему уравнений (2.2.1) требуется решить лишь для небольшого числа правых частей, то матрицы Ьд, определенные формулами (2.2Л) и (2.5.4), не запоминаются (правые части преобразуются на каждом шаге). Тогда, имея в виду тот факт, что на Ьм шаге последние п — й элементов й-го столбца матрицы Ам> обращаются в нуль, увеличение числа ненулевых элементов в матрице Ам+и по сравнению с матрицей А<') можно выразить разностью дф — (У„'В е,. — 1) = = е', В, В', В,е, — е',МВ е, + 1 = е', (В, В' — М) В е + 1. Минимальное значение этого выражения может быть использовано для выбора главного элемента.
2.6. Хранение и использование элимннативной формы обратной матрицы Все т1м~, необходимые для элиминативной формы обратной матрицы ЕГ1, хранятся следующим образом, На й-м шаге прямого гауссова исключения все тгф 4= О, 1> Й, преобразуются в нуль, а д,'",' преобразуется в единицу. Это значит, что а',.',+' = О, 1 > й, и а<„'„+и = 1. Поэтому, как это ясно из формул 48 Гл. Д Метод исклюкенил Гаусса (2.5.4), каждый элемент т!',." Ф О, с ) !г, может хра. нитьсЯ на месте соответствУющего элемента й!кк! чь О, с ) й.
Так же и элемент ф' может храниться вместо элемента а~~ил+в, так как нет необходимости хРанить значение ак~а+'>=1 (это относится ко всем й; другими словами, диагональные элементы матрицы У все равны единице). Матрицы перестановок Р„и Яд в выражении (2.5.3) могут быть легко построены, если з и ! известны.
Поэтому для каждого й требуется всего две ячейки для хранения соответствующих матриц Рк и Яд, что составляет общее число в 2п ячеек для всех Рд и 44к, которые требуются в выражениях (2.5.12). Из формул (2.2.12), (2.2.10) и (2.2,11) видно, что для вычисления всех Уд требуются только ненулевые элементы всех $м> и что, кроме того, эти элементы .могут быть получены путем изменения знаков у тех ненулевых элементов матрицы У, которые лежат над диагональю. Поэтому ненулевые элементы всех 5м! могут храниться в области памяти, занятой ненулевыми элементами матрицы У, Ненулевые элементы каждой матрицы Апн и соответствующих векторов т1~м н $м! хранятся, конечно, в одной из упакованных форм, описанных в равд.
1.3. На каждом шаге в матрице Аан создаются новые ненулевые элементы, н связные списки особенно пригодны для хранения таких элементов (Огбуобири (1970)). Заключим этот раздел несколькими примерами, в которых дополнительная работа, связанная с получением разреженной элиминативной формы обратной матрицы, является оправданной.
Во многих практических приложениях система уравнений (2.2.1) должна решаться многократно при различных значениях правых частей и (или) коэффициентов уравнений, но при сохранении структуры разреженности матрицы коэффициентов, т. е. 'при одном и том же расположении нулевых и ненулевых элементов в ней. Например, стандартный метод Ньютона для решения нелинейных уравнений приводит к 2.7.
Библиографии и комментарии системе (2.2.1), где матрица А имеет фиксированную структуру разреженности, а Ь изменяется от случая к случаю (Лайниджер и Унллогби (1969), Черчилл (1971)). В структурном анализе решение системы (2.2.1) требуется для многих правых частей (Олвуд (1971)). В упомянутых выше случаях наиболее при годна форма ЕР!. Поэтому стоимость рассмотренного в разд. 2.5 исследования для минимизации числа ненулевых элементов ЕР1 должна быть разложена на все повторные решения системы (2.2.1).
Применение ЕР! для решения задач энергетических систем приводило на практике к выигрышу в скорости, памяти ! точности, который приблизительно пропорционален степени разреженности (Тинни (!969)). 2.7. Библиография и комментарии Основы метода исключения Гаусса и ошибок округления рассмотрены в трудах Фокса (1965), Уилкинсона (1965) и Форсайта и Молера (1967). ЕР1 и способы сохранения ее разреженности путем минимизации локального заполнения были предметом„ которому уделяли большое внимание; см., например, Маркович (1957), Данциг (19636), Карпентьер (1963), Эдельман (1963), Сато и Тинни (1963), Тьюарсон (1967 б), Спнллерс и Хикерсон (1968), Брейтон и др, (1969), Огбуобири (1970), Томлин (1970), Берри (197!), Бертеле и Бриоши (1971), Форрест н Томлин (19?2) и несколько статей в трудах конференций под редакцией Уиллогби (! 969) и Рейда (!971).
Впервые ЕР! была предложена Марковичем (1957) и позже — Данцигом (1963 б). Во многих практических приложениях применение методов минимизации заполнения не создает' трудностей, связанных с ошибками округления. Например, Черчилл (!971) отмечает, что, когда применялись методы минимизации заполнения при решении сложных задач по расходу энергии, не приходилось сталкиваться с трудностями из-за ошибок округления, Гл. 2. Метод исключения Гаусса Карре (197Ц показал, что можно пользоваться способами минимизации заполнения и при решении задач сетевых потоков минимальной стоимости. В гл.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
