Критерии упорядочения для сохранения разреженности матрицы узловых проводимостей системы уравнений при выполнении прямого хода метода Гаусса

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

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

Более эффективным является динамическое упорядочение, при котором количество присоединенных к узлу ветвей уточняется на каждом шаге прямого хода метода Гаусса, и каждый раз выбирается узел с наименьшей связностью. При динамическом упорядочении число новых ветвей не превышает 50% их начального количества в схеме.

Особенность машинных алгоритмов состоит в необходимости обеспечения высокой точности решения и одновременно сохранения разреженности матрицы а. Для машинных алгоритмов различают:

- способы упаковки ненулевых элементов;

- критерии упорядочения для сохранения разреженности;

- критерии упорядочения для повышения точности решения;

- правила разрешения конфликтов между последними двумя критериями.

СХЕМА ЖОРДАНА

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

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

2.2.1.3 Метод LU - разложения

Здесь L и U –нижняя и верхняя треугольные матрицы.

Система линейных алгебраических уравнений записывается в матричной форме как

аx=b .

Кроме алгоритма метода Гаусса с обратным ходом для уравнений высоких порядков с разреженной матрицей коэффициентов находит применение алгоритм разложения матрицы ана сомножители, называемый методом LU - разложения, где под L и U понимаются нижняя и верхняя треугольные матрицы соответственно.

Один из вариантов разложения:

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

В исходное матричное уравнение вместо матрицы а подставляем произведение матриц L и U

В компактной форме запишем систему уравнений как

(2.1)

Обозначим

. (2.2)

Тогда уравнение (2.1) можно записать как

, (2.3) или в развернутом виде

.

В обычной форме записи имеем:

Эта система уравнений решается прямой подстановкой, находятся значения у₁, у₂ , у_3.

Затем решается система уравнений (2.2) , которая в развернутом виде представляется как

.

Из неё находятся искомые неизвестные х₃, х₂, х₁.

Так как матрицы Lи U треугольные, решение уравнений сводится к простым подстановкам. Объём вычислений при этом небольшой (основные вычислительные операции связаны с L, U – преобразованием).

При такой схеме алгоритма объём вычислений резко уменьшается по сравнению с классическим алгоритмом Гаусса, особенно при больших n.

L, U – разложение обеспечивает больше удобства организации учета разрежённости матриц.

2.3 Итерационные (приближенные) методы решения систем линейных алгебраических уравнений

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

Рассмотрим два метода: метод простой итерации и метод ускоренной итерации (метод Гаусса-Зейделя).

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

Метод простой итерации

Пусть имеется система линейных алгебраических уравнений

Предположим, что и преобразуем систему уравнений к виду, удобному для итерационного процесса

(2)

Система уравнений (2) согласно методу простой итерации решается следующим образом:

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

2 Значения поставляются в правые части всех уравнений (2) и тем самым определяется следующее приближение неизвестных .

3 Постановкой полученных значений в правую часть находится следующее приближение и т.д.

На к-ом шаге итерационного процесса, к=1,2… система (2) имеет вид

В общем виде

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

Для выполнения этого условия необходимо, чтобы существовал предел

где точное решение исходной системы уравнений.

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

Матрица узловых проводимостей этим условно в реальных случаях не удовлетворяет.

Но нарушение достаточных условий сходимости не означает обязательной расходимости итерационного процесса.

Итерационные методы позволяют получить значения искомых неизвестных в результате многократного выполнения единообразных шагов вычислений, называемых итерациями. Их особенности: 1) решение можно получить только с заданной конечной точностью, причём с увеличением требуемой точности растёт количество операций. Точное решение можно получить в результате бесконечного числа итераций. 2) Простота алгоритма и программы. Метод требует малую оперативную память компьютера. Недостатки: большое число арифметических операций, медленная сходимость. В итерационном процессе матрица коэффициентов а линейной системы уравнений не претерпевает преобразований, что позволяет максимально использовать её слабую заполненность. С помощью системы адресных отображений используются топологические свойства схемы при помощи адресных ссылок. Это приводит к уменьшению требуемого объема памяти.

МЕТОД ГАУССА-ЗЕЙДЕЛЯ

(метод ускоренной итерации)

Основная особенность метода — скорость итерационного процесса выше, чем в методе простой итерации. Как и раньше i=1,2..n, n - номер неизвестного х_i, k = 0,1,2… номер шага итерационного процесса.

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

Алгоритм: 1) задаемся точностью расчета ԑ и значениями неизвестных на нулевом шаге итераций. 2) Подставляем их в правую часть первого уравнения системы и вычисляем значение . 2) при вычислении в отличие от метода простой итерации в правую часть второго уравнения системы подставляется значение , вычисленное на данном шаге и значения остальных неизвестных на предыдущем шаге. 3) В общем случае для вычисления i-ого неизвестного на каждом к-ом шаге итерационного процесса используются значения неизвестных, вычисленные как на предыдущем (к-1)-ом, так и на данном к-ом шаге.

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

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

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

Чтобы система линейных уравнений имела единственное решение, входящие в неё n уравнений должны быть линейно независимыми. Необходимым и достаточным условием этого является условие неравенства нулю определителя данной системы det a 0.

Близость нулю определителя системы есть признак её плохой обусловленности.

2.4 ЧИСЛЕННЫЕ МЕТОДЫ РЕШЕНИЯ СИСТЕМ НЕЛИНЕЙНЫХ АЛГЕБРАИЧЕСКИХ (СНАУ) И ТРИГОНОМЕТРИЧЕСКИХ УРАВНЕНИЙ

В отличие от систем линейных алгебраических уравнений для систем нелинейных уравнений отсутствуют точные (прямые) методы решения.

2.4.1 Системы нелинейных уравнений узловых напряжений в форме баланса токов и в форме баланса мощностей

Для случая отсутствия ЭДС в ветви при совмещении базисного и балансирующего узлов нами получено узловое уравнение в матричном виде в форме баланса токов

(1)

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

.

Мощности в узлах при расчете установившегося режима являются независимыми параметрами режима, поэтому должны фигурировать в системе уравнений (1) . Как их ввести в систему (1), когда операция деления в матричной алгебре отсутствует? Вспоминаем, что есть операция обращения матриц. Запишем выражение мощности источника или потребителя в узле i трёхфазной цепи

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

где — матрица напряжений в узлах порядка n,

представленная как диагональная. Для неё легко найти обратную матрицу:

.

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

.

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

В компактной форме записи имеем

.

Тогда система нелинейных уравнений узловых напряжений в форме балансов токов в матричном виде записывается:

,

либо в виде системы неявных функций

(2)

Введем понятие вектор - функции

,

где f_i (U) — нелинейное уравнение узловых напряжений (2), записанное для i-го узла. Тогда система нелинейных уравнений узловых напряжений в компактной форме может быть записана как

f(U) = 0.(3)

Перейдем от матричной к обычной форме записи. Чтобы получить это уравнение в обычном виде для i–го узла представим матричное уравнение (2) в развернутом виде, выделив в матрице узловых проводимостей i–ю строку:

Умножив i–ю строку матрицы Y_у на столбец неизвестных напряжений и прибавив другие слагаемые этой строки, получим

В компактной форме записи уравнение узловых напряжений в форме баланса токов для i-го узла имеет вид (4)

(4)

Здесь — сумма для всех узлов j, связанных с узлом i (К_i — куст узла i т.е. множество узлов, связанных с узлом i).

Система нелинейных уравнений в форме баланса токов в матричном виде (2) умножается слева на матрицу . В результате получаем систему нелинейных уравнений в форме баланса мощностей в матричном виде (5)

. (5)

Умножив уравнение узловых напряжений в форме баланса токов для i-го узла (4) на сопряженный комплекс напряжения в i-ом узле , получаем уравнение узловых напряжений в форме баланса мощностей для i-го узла (6) в обычном виде

. (6)

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

ФОРМЫ ЗАПИСИ СИТЕМЫ НЕЛИНЕЙНЫХ УРАВНЕНИЙ УЗЛОВЫХ НАПРЯЖЕНИЙ

Система нелинейных уравнений узловых напряжений

В форме балансов токов

В форме баланса мощностей

В матричном виде (2)

В матричном виде(5)

В обычном виде для i-го узла (4)

В обычном виде для i-го узла (6)

2.4.2 Решение системы нелинейных алгебраических уравнений узловых напряжений в форме баланса токов методом Гаусса-Зейделя

Исходную систему уравнений, приведенную к виду, удобному для итерационного расчёта, получаем из выражения (4), придавая переменной i

значения 1,2…n, где n- число узлов с неизвестными напряжениями и разрешая каждое из уравнений системы (4) относительно неизвестного .

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

(7)

…………………………………………………………………………………………………………………………

………………………………………………………………………………………………………………………………………………….

Алгоритм

1 Задаются значением неизвестных напряжений в узлах на нулевом шаге итераций , ,…, и точностью расчета ԑ.

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

3 Найденные значения , и т.д. подставляют в правую часть первого уравнения и рассчитывают и т.д. до достижения требуемой точности:

.

При вычислении i–го неизвестного на каждом к - ом шаге итерационного процесса используют значения неизвестных, вычисленные как на к-1- ом, так и на данном к-ом шаге.

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

Представляем, как и ранее комплексы напряжений и мощностей в узлах, а также комплексы проводимостей узлов через их действительные и мнимые составляющие:

При разделении уравнения (7) на два — для мнимой и действительной составляющих комплекса напряжения в узле к получаем выражение для и на к-ом шаге итераций. Для схемы замещения с тремя независимыми узлами они имеют следующий вид:

Мощность балансирующего узла вычисляется по выражению

Преимущества метода Зейделя:

1. Простота алгоритмической реализации.

2. Малый объем вычислений на каждой итерации.

3. Малый объем требуемой памяти.

4. Легко учитывается слабая заполненность матриц узловых проводимостей.

Основной недостаток метода Зейделя — медленная скорость и ограниченная область сходимости. Факторы, ухудшающие сходимость: неоднородность элементов схемы; наличие ветвей с ёмкостной проводимостью.

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

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

Для ускорения сходимости итерационного процесса используется «ускоряющий коэффициент»:

.

Здесь: — значения напряжения в i-ом узле на к-1 и на к-ом шагах итераций, полученные по ускоренной схеме;

— значение напряжения в i-ом узле на к-ом шаге, полученное по обычной схеме алгоритма без ускоряющих коэффициентов.

Возможный диапазон изменений ускоряющего коэффициента

, оптимального постоянного значения не существует. Значительного ускорения сходимости можно достичь, используя изменяющиеся значения на каждой итерации:

.

2.4.3 Метод линеаризации (внешней итерации)

1 Вычислительная схема решения уравнений установившегося режима методом внешней итерации (линеаризации) рассмотрена ранее.

Или в обычной форме записи

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

2.4.4 Метод Ньютона-Рафсона

Вначале рассмотрим алгоритм решения одного нелинейного уравнения с одним неизвестным х.

1-й шаг итерационного процесса. Пусть переменная р — номер шага итераций, р=1.

Задаемся - точностью расчета, начальным значением неизвестного х на нулевом шаге (p-1-ом шаге в общем случае, где р=1, 2, …). Подставляем значение в нелинейное уравнение, рассчитываем невязку и сравниваем её с требуемой точностью:

. (1)

Поскольку на первом шаге неравенство, как правило, не соблюдается,

в окрестности точки с координатами , раскладываем в ряд Тейлора. Берем только 2 первых члена разложения:

.

Здесь, — уравнение прямой, которой мы заменяем нелинейную функцию в точке с координатами , (уравнение касательной к в этой точке). Решение линейного уравнения этой касательной получаем в точке её пересечения с осью абсцисс:

. (2)

Обозначим — поправку к значению неизвестного на первом шаге итерационного процесса. Из приведенного выражения (2) после расчета значения производной получаем линейное уравнение (3) от носительно поправки :

. (3)

Его решение:

.

Тогда уточненное значение неизвестного на первом шаге итераций:

. (4)

Подставляем в нелинейное уравнение, рассчитываем новое значение невязки, и если она превышает требуемую точность , в точке , рассчитав новое значение производной , получаем уточненное линейное уравнение относительно поправки на втором шаге итерационного процесса:

.

Его решение дает значение поправки и уточненное значение неизвестного на втором шаге итерационного процесса:

.

Для шага р. выполняются следующие действия:

1) ;

2) ;

3) ;

4) .

Сформулируем алгоритм расчета

1 Задаемся значением неизвестного на нулевом шаге и точностью (погрешностью) расчета неизвестного .

2 Неизвестное (в общем виде ) подставляем в нелинейное уравнение и проверяем выполнение условия

? ( в общем виде для шага р, p=1, 2, 3, … ?).

Если неравенство выполняется — конец расчёта, если не выполняется— идти к п.3

3 Находится значение производной при (в общем виде при )

Линейное уравнение 2) сформировано.

4 Находим согласно 3) (в общем виде )и согласно 4) (в общем виде )

5 = ; . Идти к п.2.