Алгоритм триангуляции

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

При анализе режимов ЭЭС рассматриваются изменяющиеся во времени нагрузки узлов для сетей постоянной конфигурации, где матрица проводимостей Y остается неизменной. Изменяется только правая часть СЛУ (токи, мощности). Следовательно, требуется выбрать такой алгоритм, который в максимальной степени учитывает специфику постоянства матрицы проводимостей.

Анализ (3.8) позволяет видеть, что при повторных расчетах, связанных с изменением правой части СЛУ выполняются одни и те же преобразования матрицы коэффициентов { }. На этапе исключения переменных новые величины { } составляют примерно 2/n часть. Было бы желательно сохранить промежуточные расчеты { } для их последующего использования.

Это оказывается возможным благодаря так называемой процедуре триангуляции, согласно которой матрица коэффициентов представляется в виде произведения двух треугольных матриц A = LW, причем одна из них (L) является треугольной «снизу», а другая (W) – треугольной «сверху». Представление A = LW называется треугольным разложением или триангуляцией матрицы.

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

,

(4.1)

причем

A = LW.

Заменив в (4.1) A на LW, получаем

.

Обозначим , тогда вместо системы(4.1) можно записать две эквивалентные:

(4.2)

Из первого матричного уравнения решением СЛУ с треугольной матрицей L определяется вектор , а из второй – искомый вектор . При однократном решении СЛУ триангуляция не дает каких-либо преимуществ по сравнению с простым методом Гаусса. Однако при каждом последующем изменении вектора расчеты СЛУ производятся по (4.2) с неизменными матрицами L, W. При этом решение занимает гораздо меньше времени, чем решение системы с исходной матрицей А, поскольку исключаются повторные расчеты { } (они сохранены в матрицах L, W ).

Рассмотрим триангуляцию квадратной матрицы, т.е. разложение её на треугольные сомножители.

Прежде всего, проанализируем формулу (3.8) преобразования коэффициентов в прямом ходе метода Гаусса:

По существу, данная формула означает вычитание на шаге k (исключение переменной x_k) умноженной на коэффициент строки k (управляющая строка -УСТР) из текущей строки i. Коэффициенты используются при формировании матрицы L. Совокупность обычно называется управляющим столбцом (УСТБ).

Следует отметить, что любое преобразование матрицы (например, вычитание из какой-либо строки другой, умноженной на некоторый коэффициент) означает ее умножение на некоторую, совершенно определенную матрицу, или иначе, если в результате преобразования матрицы А получена матрица W, то можно записать А = LW.

В приведенном ниже примере матрица W получена из А вычитанием первой строки из второй, а матрица L получена по некоторому, известному нам правилу.

.

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

Можно показать, что матрица L формируется последовательно из управляющих столбцов в процессе гауссовского исключения переменных. Один шаг эквивалентен преобразованию с матрицей, построенной из единичной заменой k-го столбца управляющим столбцом. В частности, на первом шаге А = L ₁ W ₁, на втором W ₁ = L ₂ W ₂, на n -1 W _n-2 = L _n-1 W _n-1 = L _n-1 W. Отсюда А = LW, где результирующая матрица определяется произведением L = L ₁ L ₂… L _n-1 и представляет собой совокупность управляющих столбцов_.

, , …,

Матрица W является результатом процесса исключения переменных или последовательно формируется из управляющих строк

; ;

Свойство симметричности матрицы проводимостей () позволяет отказаться от формирования и хранения матрицы L, поскольку управляющие столбцы легко получаются из управляющих строк

,

т.е. столбец k матрицы L равен транспонированной строке k матрицы W, деленной на ее диагональный элемент.