bn-b„a„n

Значения у теперь содержатся в Ь /Обратная подстановка.. For all i-- n-I step-I uni I I do Ьецт

all i

1 stei

i d bi--bi ajjb]

erui (for i) Значения теперь содержатся i

В этом алгоритме для прямого исключения используется п операции деления н п {п - i)/2 - умножения. Для обратной подстановки осуществляется п (п - 1)/2 операций умножения Следовательно, суммарное число длительных операций для этого алгоритма состааляет

Nn,-n + nln-\)

(!5 37)

Теперь можно найти суммарное число длительных операций требуе мое для получения решения уравнения (!5.2) методом /.(/-факторизации н прямого исключения-обратной подстановки. На основании (15.30) и (15.37) имеем

(15.30) и (15.37) имеем

(15 38)

Если требуется найти решение (15.2) для различных векторов в правой части уравнения, то повторно необходимо выполнить только прямое исключение - обратную подстановку. 1 {/-факторизацию требуется производить только один раз для исходной матрицы

В подразд. 15.31 в случаях матричного решения для матриц типа (Г - S) рассматривалась 1 {/-факторизация с исполыюванием в каче стве ведущих единичных элементов, соответствующих Г. Отметим, что так как ведущий элемент иа А м шаге выбирается из столбца g (k), то полученные непосредственно неизвестные окажутся перегруппирован ными Алгоритм прямого исключения - обратной подстановки для такого случая имеет вид

/Прямое исключение/ For all j Wo п I d< hegm

q - g ()t

For all \ j t I / n d( b b,-ajiX, end (for J) q- g(n)

Xq=--bn/a[(i

/Обратная подст; For all i -n-1 step~\ until I do begin

P"g(i)

For all J- П step I until i + \ do begn

q = g(i)

end (for i)

Примеиевня. Решение уравнения (15,.42) требуется при расчете чувствительности с помошью присоединенных схем. При этом под U понимается нижиня треугольная матрица с единичными диагональными элементами, а под L -верхняя треугольная матрица с диагональными элементами, имеющими произвольные значения. Решение (15 32) может быть получено с помощью несколько измененной процедуры прямого исключения - обратной подстановки, которая для разре женных матриц будет описана позднее в подразд 15,4,3,

Кроме того, в rex случаях, когда обратная матрица должна умножаться Hd другую матрицу, могут быть получены 1(/-сомножители матрицы и последовательность прямых исключений -- обратных постановок выполняется для каждого столбца умножаемой матрицы Например, для того чтобы найти A-i С. по лучают L. и-множители А и затем с помощью прямого исключения обратной подстановки - решение каждого столбца С

154 ДЕЙСТВИЯ НАД РАЗРЕЖЕННЫМИ МАТРИЦАМИ 4-14)

Как отмечалось в гл, 11 12, матрицы, для которых в процессе ана тиза схем требуется нахождение обратных матриц, очень разрежены Разреженными называются матрицы содержащие большое число нуле вых элементов В матрицах типа (Г - S) ненулевые элементы соответ ствуют только внешним и внутрисоединенным входам этого компо нента. Для обычной схемы только 5 - 10% элементов матрицы (Г - S) являются ненулевыми. К[юме того, когда одна и та же схема ана лизируется при различных значениях параметров некоторых компо нентов, положение нулей не изменяется т е, является ли элемент в матрице (Г - S) нулевым илн ненулевым, зависит только от тополо гии схемы и не зависит от характеристик компонентов

Так как матрицы сильно разрежены, большинство длительных one раций, которые выполняются при /.(/-факторизации и прямом исключении--обратной подстановке будут операциями типа Оха, и 0/а„, которые фактически не должны выполняться. Эффективность вычислений при анализе может быть повышена при нсгюльзо ван и и ме тодики, согласно которой такие операции опускаются, а выполняются только ненулевые операции.

Далее можно значительно снизить требуемый объем памяти для матрицы, если запоминать только ненулевые элементы, Прн этом структура данных должна быть разработана таким образом, чтобы по ложение элемента в матрице и его значение могли быть легко восста новлены.

154! ПЕРЕГРУППИРОВКА УРАВНРПИЙ

При LU факторизации сомножители L, U, определяющие матрицу Т (югласно (!5.23) запоминаются в тех же ячейках памяти, что исход ная матрица А, Это возможно, так как ячейки, содержащие нули матри цы А (не запоминаемые), могут устанавливаться ненулевыми при факторизации. При 1(7-факторизации элемент a,j корректируется как

Если а,J имеет нулевое значение, а а,„ и aj --ненулевые то (г,/) и элемент, который в матрице А был нулевым, в матрице Т становится ненулевым Вновь созданные ненулевые элементы называются «заполняющими» или заполнениями Для заполнений также дозжна резервироваться область памяти.

Число сгенерированных заполнении зависит от перегруппировки строк и (или) столбцов. Если ведущие элементы, выбранные в каждой строке, зафиксированы, то число генерируемых заполнений зависит от перегруппировки строк. Число генерируемых заполнений желательно минимизировать. Для иллюстрации зависимости числа генерируемых заполнений от перегруппировки найдем решение следующих уравнений с помощью 1(/-факторизаиии: 2 4 2 --6-

3 9 2 О 2 О

(15 39)

Что&й определить число сгенерированных заполнений, не требуется знать фактические значения ненулевых элементов, а необходимо знать только их местоположение. Например, для матрицы из уравнения (15.39), для которой требуется определить LU сомножители, необходима матрица следующего типа

где знаком Л определены ненулевые элементы При LV факторизации матрица полностью заполняется и, таким образом, генерируется шесть заполнений Число длительных оператшй, необходимое для этою раз-тожения, составляет 20

Если уравнения в (15,39) перегруппировать записав

(15 40)

с сохранением тех же самых ведущих элементов то матрица, для ко торой необходимо определить /.(/-сомножители становится матрицей типа

2 4 3)

X О О Л

о X о X

о о X X

.V X X X

где как и ранее, знак X - ненулевые элементы. При /.(/-факторизации матрица опять получается того же типа и заполнения не генерируются. Теперь для разложения требуется шесть ненулевых длительных операции. Таким образом, перегруппировка строк и столбцов матрицы А ire только минимизирует число генерируемых заполнений, но и уменьшает число длительных операций, необходимых для 1(/-фактори зации. Далее приведен алгоритм перегруппировки

Алгоритм перегруппировки 8-10. Целью этого алгоритма явля ется перегруппировка строк и столбцов матрицы А так, чтобы суммар ное число генерируемых заполнений было минимальным

Чтобы найти порядок строк и столбцов при котором достигается полный минимум, требуется вычисление генерируемых заполнений всех юзможных случаев. Число возможных случаев составляет л!, и проверка каждого из них очень неэкономична по вычислительным затратам, требуемым для получения глобального минимума. Однако возможно определение подоптимума или локального минимума.

Алгоритм нерегругшировки, описанный в (81 является попыткой минимизировать необходимое число дпительных операций. Как сле дует из изложенного, ведущие элементы при их выборе фиксируются в каждой строке, а согласно алгоритму на каждом шаге решается, ка кой из оставшихся ведущих элементов является кандидатом на роль следую(цего ведущего элемента. Этот алгоритм заключается в следующем.

Начиная с k [ и до п - 1 на й м шаге определяется тре буемое число длительных операций для каждого предполагаемого ведущего элемента. Ведущий элемент требуняций наименьшего числа длительных операций, выбирается в качестве следующего ведущего элемента. Если имеются ведущие элементы требующие равного числа длительных операций, выбирается любой из них. Число ненулевых дли тельных операций при корректировке равно произведению ненулевых элементов в строке с ведущим элементом (в корректируемых столбцах) и в столбце с ведущим элементом (в корректируемых строках). Это чис ло прибавляется к числу ненулевых элементов в столбце с ведущим эле ментом и получается суммарное число длительных операций для пред полагаемого ведущего элемента

Таблица 15 I Число длительных примере

1ерацнй необходимое в рассмэтрива*

Этот алгоритм истюльзоваи здесь для перегруппировки строк и столбцов матрицы размером 6x6 структура которой имеет вид

1 2 3 X

X X XXX X

4 5 X X X

Предполагаемый ведущий элемент выбирается из элементов главной ди агонали. Число ненулевых длительных операций, необходимое для корректировки каждого из предполагаемых ведущих элементов, при ведено в табл. 15.1.

В качестве ведущего элемента выбирается диагональный элемент в строке 5 и после выполнения требуемых операций на этом этапе мат рица принимает следующий вид

Здесь сгенерирован один чаполняющин элемент обозначенный знаком

Число длительных операции деления и корректировки на следующем шаге для каждого из оставшихся предполагаемых ведущих элементов в строках 1 2,3, 4, 6 составляет 6(2-4) 4(2+2) 8(2+6) 8(2-,-(-6) и 4 (2+2) соответственно

Отсюда видно что возможен равнозначный выбор ведущих элемен тов в строках 2 и 6 Пусть в качестве следующего ведущего элемента

будет выбран диагональный элемент в строке 2 После выполнения необходимых операций для этого шага матрица преобразуется к виду

5 2 13 4 6

X XX

X > !<

XX XXX

X XX XXX

применяя описанную *десь [роцедуру приводим матрицу после раз южения к виду

5 2 X

6 13 4

А А А XXX

А А А

X X X X

Н()ир(танн1.гх »а]юлнении составляет 3, а суммарное число л.е.1ы[ых операций разложения 19 Заметим, что в отсутствие и[[И1анпой перегругЕПировкн число )анолнений было бы равным 5, а \ "мнр[юе число длительных операций составило бы 24. В большиист и пр.чктическн.ч случаев выигрыш, обусловленный керегруппировной Ги. 1сг шачнтелен, чем в данном примере

*и\ гЕроцедура ЕЕерегруппировкн приведена далее. Там приняты клуЕосцие обозначения: RMA оставшаяся матрица, конфигурация 1л>1<10й на начальной стадии была аналогична конфигурации исход ikei м;Грицы А Предполагается, что ведущие элементы в каждой стро .11мещены на диагонали. В массиве RMI хранятся индексы остав iiili\ti] ГЕредполагаемых ведущих элементов Операторы NZR (i) и n/i () задают количества ненулевых вводимых данных в строке / и

.....ие / счютветственно (в RMA). Число длительных операций шага

1чм1 и, пользовании предполагаемого ведуЕцего элемента i определяется тн рлюром NOP (i).

n. НМД-матрица Л RMI 1 2 п

" .,;/ к=ж1 to п-I do htg.n

For each iRMI do begin

чэк 2259 289