For ali j п step-I uniil 2 i)v begin

For all k- I lo п d bjh - -bjji.aij For all i- j-1 stfp~l until 1 do begin

For all к I to tt d biK biK -a,ibh end (for I) end (For J)

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

152 ВЕДУЩИЕ ЭЛЕМЕНТЫ Ц 2]

В данном разделе рассмотрим различные критерии, которые могут использоваться для выбора ведущих элементов иа различных этапах. В предыдущем разделе уже отмечалось, что ведущие элементы должны иметь ненулевые значения. Однако если значения этих элементов малы, то могут возникнуть численные ошибки. Они возникают из-за того, что в ЭВМ. на которой 11рои:}Водятся нычисления. слово имеет конечную длину. Возникновение ошибок при малых значениях ведущих эле ментов может быть показано на стедующем примере:

Пример Рассмотрим следующую систему уравнений

I О O00I 1 1 10 101

(Ii И)

Результатом решения зтой системы уравнения с точностью до "«и значащих результатом решс решении методом исключения

цифр является xj - l.uuui .„анз второго ура

Гаусса первое уравнение \мнижается на 10 и вычитается hj р При этом получается

Рели используется ЭВМ, i уравнение (15.12) будет v

оперирующая с точностью до трех ;

- 1 СЮ Юхг- 5 00 lOfi

(15 12) аавдих цифр то

(15 13)

otkvfla x,- 5 00. После подстановки в .первое уравнение (15 II) получаем г. 00 что существенно о,личается от истинного значения.

Найдем также решение .той системы после перестановки строк в (15 11} Уравнения (15,11) тогда примут вид

1601

Прн использовании метода и приводится к виду

о 1ення Гаусса второе vpa;

(15 14) ы(15 14) (15 15)

ЭВМ оперирует с э форме

I QOxj -5 00

трех значащих цифр это уравнение пред (15 Ifit

Следовательно, 5.00 и при обрап

3 соответствует правильному решению с

юлучаем xi - 1,00 рех значащих цифр.

Из приведешюго примера следует, что если абсолютное значение ведущего элемента очень мало, то могут возникнуть больгиие числен ные norpeuiHOCTH. Для исключения этих погрешностей существует хорО (Пая стратегия. На А-м шаге ведущим выбирается элемент в *-м столбце с наибольшим из всех элементов в строках от fe до п абсолютным знэ ченнем. 3*то требует некоторых дополнительных затрат машинного вре мени, но приводит к повышению точности решения, что весьма важно Дополнительное повышение точности достигается перестановками не только строк, но и столбцов Этот метод определения ведущего эле мепта является более полным, чем метод, при котором переставляются только строки. Для определения ведущего элемента в этом случае требуется дополнителыюе время, так как при перегруппировке столбцов неизвестные также перегруппируются.

Как говорилось в гл. 11, в процессе анализа требуется обращение матрицы типа (Г - S). Диагональными элементами этой матрицы яв ляются коэффициенты отражения от различных входов компонента. Значения этих коэффициентов отражения на центральных частотах могут быть очень малыми. Однако в каждой строке матрицы (Г - S) имеется единичный элемент, соответствующий матрице внутренних соединений Г, который не зависит от частоты. Остальные элементы в мат рице (Г - S) являются элементами матриц компонентов, которые для пассивных цепей меньше единицы. Единичные элементы являются иде-лльными ведущими элементами, так как экономится время, затрачнва емое на поиск этих наибольших элементов. Кроме того, на начальной стадии, пока единичные элементы соответствующие Г-матрице, кор ректируются разделение ведущих элементов не выполняется. Следует отметить, что в очень редких случаях единичный элемент, соответст вующий Г, может при корректировке уменьшиться до нуля. Это про исходит только в некоторых аномальных ситуациях и здесь не рассмат ривается 131.

15,3. /.-ФАКТОРИЗАЦИЯ И ПРЯМОЕ ИСКЛЮЧЕНИЕ-ОБРАТНАЯ ПОДСТАНОВКА \\. 2\

Если требуется найти решение уравнений (15.2) для более чем од ного вектора Ь, то более предпочтительным является метод /,С-фактори зации [Ц. При этом методе матрица А разлагается на нижнюю треугольную матрицу L и верхнюю треугольную матрицу U так чтобы

A-UJ

(15.17) 279

(15 18)

(15 19)

сравнение (15 2) теперь принимает вид

LUx = b (15.20)

Ре]]ение (15.20) получают в два этапа. Сначала методом прямого исклю чения получают penjenne относительно у, соответствующее уравнению

Ly=b (1521)

На втором этапе находится ретт1ение относительно х

Ux=y (15.22)

при котором используется процесс обратной подстановки Все элементы главной диагонали матрицы tl являются единичными и, следователь но, при запоминании матрицы L и U могут частично перекрываться и запоминаться в виде матрицы Т

(15 З)

L -u.........1,

где I - единичная матрн]1а

1оЗ I IV ФАКТОРИЗАЦИЯ

В эюм 1юдразделе рассмотрим Процедуру разложения 1!евырождец ной матрицы А на матрицы L и U,

В разд, 15,1 говорилось, что невырожденная матрица может быть Приведена к треугольному виду с помощью элементарных операции строк. Затем каждая строка может быть разделена диагональным элементом для приведения ее к типу U, Как отмечалось в разд, 15 1 вы [ЮлнеЕже операции строк над матрицей может быть получено пере миожением ее с другой матрицей, называемой матрицей Е, Матрица Е получена выполнением тех же операций строк над единичной матрицей 1 подходящего порядка Для любой невырожденной матрицы А моЖ]Ю записать

Е,Е, А=-и

(15.24)

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

рого типов Матрицы Е, полученные после действия над строками пер вого и второго типов, являются нижними треугольными матрицами, так как действием первого типа является умножение строк на скаляр, а действием второго типа - всегда сложение одной строки с другой умноженной на а. Произведение любых двух нижних треугольных мат рнц является также нижней треугольной матрицей Следовательно произведение (Е„Е„ ,., E.,Ej) в (15.24) является нижней треуголь пой матрицей. Обращение нижней треугольной матрицы также приво дит к нижней треугольной матрице Следовательно, из (15.24) имеем

А LU

L - <Е Е„

Е, Е,

(15 25)

(15 26)

Если на каком либо этапе ведущий элемент а* оказывается рав ным нулю то, чтобы продолжать ис1Юльзование метода исключения Гаусса, необходимо произвести операцию перестановки строк. Можно показать, что в этом случае могут быть найдены матрицы L и U удов летворяющие уравнению

LU- РА

(15 27)

тде Р - матрица, получаемая выполнением всех необходимых переста новок строк единичной матрицы. Очевидно, что если никаких переста новок строк не требуется, то Р -- I.

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

1-ог all к 1 / п \ d hegin

For all I к , I и, n d Эк, akj ak

For Ш 1 к \ \ U: n d

beum for all j end (f г il end (for k)

a,j--=ai] -з,Дк)

Процедура преобразования матрицы А в матрицу Т задается уравне нием (15,23), Матрицы L и U содержатся в А:

I j - a,j для /<(. (15 28)

и,, а„ Д1я /X (1529а)

(15 296)

Время, затрачиваемое на выполненне каждого luara разделения в при веденном алгоритме, определяется выражением

(п -2)-f ч2Ь1 n(/i-i)/2

Продолжите1Ьность шага корректировки а,, определяется суммой

(п I)-f (п-2)« 4- 44н! п(п -1)(2п 1)/Ь

Корректировка a,j требует единственной операции умножения и но этому суммарное чис ю длительных операций состав1яет

п(п-\)

~ ,15 30)

Как говорилось в разд. 15.2. ведуц;ии элемент для матриц типа (Г S) можно выбрать априори выбрав в каждой строке в качестве ведуш.его единичный элемент, соответствующий матрице внутренних соединений Г Это означает, что неизвестные должны быть перегруппи рованы так, чтобы единица, соответствующая матрице Г, попадала на главную диагональ. Если положение единичного элемента, соответст вуюшего матрице Г (для /-и строки), задается массивом g (i), то они санный алгоритм для 1{У-факторизации изменяется

/« a/i к ! ( п \ d

Fnr all \ \i \ \ fu n d begin

Ч ~ fi(j)

end (for j) r uU i k.l / n ,/ begin

Fur all j к I ( begin

q 6<J)

end (for j)

end {U

end ([ r k)

В данном алгоритме столбцы матрицы А не перегруппировыванэтся но тем не менее элемент в столбце р g(k) на А-м шаге выбирается ведущим. Поскольку предыдущие ведущие элементы выбирались нз столбцоб(1), g (2), g(ft - i), элементы в этих столбцах Л-й строки и ведущий элемент к-го шага являются частями матрицы L и, таким об разом, не разделянэтся ведущими элементами. Только элементы в столбцах g (к ]} g (п) разделяются ведущими элементами. Ана 282

логично корректируются только элементы в столбцах g [к i I), ...

(я) строк (й- 1),..., п. Поскольку для получения решения используются прямое исключение и обратная подстановка, то с помощью перегруппировки будут назначаться результаты переменным.

Можно показать,что получить решение для присоединенной схемы также можно с 1гомощью L и /7-множителен. Если исходя нз уравне ния

Ах-Ь (15.31)

получают решение для исходной схемы то решение дзя присоединен ной схемы получается из выражения

Ах-Ь (15,32)

где b вектор возбуждения для присоединенной схемы Ес1и выра

зить

A-LU, (15 33)

A-UL (15 34)

153,2 ПРЯМОЕ МСКЛЮЧРНЛР И ObP\TH\fl ПОДСТАНОВКА

Для решения системы уравнении с помощью L(7-сомножителеи решают уравнения (15,21) и (15.22) Уравнение (15 21) можно перепн сать в виде

1,, О

(15 35)

п1 It J \ Уn

Переменную у, можно тюлучить нетюсредственно из первого уравнения (15.35). Затем ее можно подставить во второе уравнение и определить г и так далее, пока не будут найдены все значения переменных у,.

Уравнение (15.22) решанэт следующим обрагюм. Уравнение (15 22) можно переписать в виде

О 1

(15 36)

откуда можно получить все значения х-, в обратном порядке

Алгоритм прямого исключении и обратной !Юдстановки имеет сле дующий вид:

/Прямое исключение Far nil j 1 to т\- \ do beg,n

bj- bj/aj)

For all j-j II/ П do bj bi aijbj end (for j)