12.3. Реализация (n+1)-узловых резистивных n-полюсных цепей (подход Седербаума)

В этом разделе рассматривается задача реализации вещественной симметричной -матрицы У как матрицы проводимостей короткого замыкания (-узловой резистивной -полюсной цепи, не содержащей отрицательных проводимостей. Для решения этой задачи имеется два основных подхода, предложенных Седербаумом и Гуиллемином. Подход Седербаума [12.1] требует разложения матрицы V в произведение где матрица, элементы которой равны — 1,1 или — диагональная матрица с неотрицательными элементами, представляющими проводимости ребер искомой -полюсной цепи N. Реализация матрицы Y достигается в том случае, если можно реализовать как базисную матрицу сечений связного графа. Тогда этот связный граф будет графом нагруженной -полюсной цепи N, причем столбцы соответствуют ребрам, представляющим проводимости искомой цепи N. Фактически, как будет показано ниже, подход Седербаума также применим и к реализации матриц холостого хода -полюсных цепей с цикломатическим числом .

Подход Гуиллемина [12.3] требует определения полюсной конфигурации (если она существует) и преобразования матрицы Y в матрицу Y, которая соответствует полюсной конфигурации в виде звезды. Если матрица Y является гипердоминантной, то реализации (как было показано в предыдущем разделе) можно достичь просмотром. Посредством предполагаемого переопределения полюсов эта же цепь может также реализовать данную матрицу

Ниже описывается алгоритм Седербуама, позволяющий разложить матрицу Y в произведение . В следующем разделе рассматривается реализация как базисной матрицы сечений. Алгоритм, основанный на подходе Гуиллемина для реализации У-матрицы -узловой -полюсной цепи, обсуждается в разд. 12.5. Пусть столбцы матрицы . Пусть, далее, диагональные элементы . Тогда является столбцом является диагональным элементом Заметим, что соответствует Далее, элементы будут обозначаться

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

На каждом шаге алгоритма необходимо рассматривать два случая:

Случай 1. Матрица Y — диагональная с k нулевыми диагональными элементами.

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

где считается, что нулевые диагональные элементы матрицы Y находятся на последних k позициях. Например, матрицу

можно представить в виде декомпозиции

Случай 2. Матрица Y имеет некоторые ненулевые недиагональные элементы.

В этом случае сначала выбираем ненулевой недиагональный элемент с наименьшим значением. Допустим, что такой элемент матрицы У. Если Y является реализуемой, то из следствия 12.3.1 известно, что в искомой цепи N должно существовать ребро со значением проводимости, равным Другими словами, должно иметь диагональный элемент, равный Не нарушая общности, допустим, что Столбец соответствующий столбцу можно определить следующим образом. Очевидно, что ребро с величиной проводимости стягивает оба полюса 1 и 2 цепи N. Поэтому два первых элемента являются ненулевыми. Согласно следствию 12.3.1, первые две строки не могут иметь

ненулевые элементы одновременно во всех столбцах, кроме первого. Поэтому произвольно приписываем +1 к первому элементу ди фиксируя таким образом ориентацию ребра, имеющего проводимость относительно полюса 1. Тогда, согласно теореме 12.1, знак второго элемента в является таким же, как и знак Таким образом,

Заметим, что если ненулевой недиагональный элемент с минимальным значением, то элементы будут определяться аналогично. Теперь остается получить остальные элементы Этого можно достичь, используя следующее правило, основанное на теореме 12.2:

[о в противном случае.

Этим заканчивается обсуждение двух случаев.

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

Удалим из матрицы ее первый столбец, а из матрицы ее первые строку и столбец. Пусть результирующие матрицы обозначаются через и Тогда можно заметить, что

    (12.35)

Следовательно,

    (12.36)

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

Предположим, что матрица — диагональная. Тогда декомпозиция, описанная в случае 1, даст все оставшиеся столбцы матрицы и оставшиеся диагональные элементы матрицы

Если матрица диагональная, то повторяем процедуру, описанную в случае 2, чтобы получить проводимость и второй столбец из матрицы Тогда матрица задается следующим выражением

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

Проиллюстрируем алгоритм Седербаума с помощью матрицы

Так как матрица У — не диагональная, случай 1 отпадает. Поэтому действуем, как описано в случае 2.

Элемент является минимальным по значению ненулевым элементом матрицы F. Устанавливаем (так как положителен). Затем определяем оставшиеся элементы первого столбца из матрицы используя следующие правила:

Например, поэтому откуда имеем

Затем получаем матрицу в виде

В матрице элемент (2, 5) имеет минимальное ненулевое значение, поэтому получаем Затем получаем остальные элементы как и раньше, и поэтому

Матрица получается в виде

Продолжая таким же образом, далее получим

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

Хотелось бы отметить, что декомпозиционный алгоритм Седербаума, который мы только что обсудили, применим к любым схемным матрицам: это означает, что если схемную матрицу К можно декомпозировать в виде , где Р — унимодулярная матрица, диагональная с положительными элементами, то, используя этот алгоритм, можно найти такую декомпозицию. Поэтому ясно, что этот алгоритм можно использовать для декомпозиции матрицы холостого хода резистивной -полюсной цепи, имеющей цикломатическое число в виде произведения Таким образом, подход Седербаума для реализации -матрицы (-узловой -полюсной цепи также применим для реализации -матрицы -полюс-ной цепи с цикломатическим числом n. Следующим шагом подхода Седгрбаума после получения или является определение ориентированного графа, соответствующего этим матрицам. Предположим, что определен неориентированный граф, соответствующий или Тогда можно легко определить соответствующий ориентированный граф (если он существует) анализом или так как такой случай возможен (упражнение 6.1).

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