Оптимізація аналітичних методів розв'язування систем скінченних рівнянь

Як уже було сказано, серед аналітичних методів розв'язування систем скінченних рівнянь найефективніший метод послідовних виключень - метод Гаусса з триангуляцією та подвійною факторизацією матриць. Отже, мова йде, власне кажучи, про оптимізацію саме таких методів. З цього погляду вирішальне значення має вибір порядку (впорядкування) виключення невідомих, мета якого - забезпечення високої точності обчислень, збереження високої розрідженості матриці та виконання якомога меншої кількості арифметичних і логічних операцій. Найвища точність, як відомо, досягається при виборі найбільшого головного елемента, але такий вибір може не задовольняти, вимогу мінімальної кількості ННЕ. Однак вимога такого вибору порядку виключення (забезпечення мінімуму ННЕ) може призвести до виконання великої кількості операцій, необхідних для належного впорядкування рівнянь.

Як видно з формули (4.185) перечислення коефіцієнтів матриці, необхідною умовою появи ННЕ є Звідси випливає,що для мінімізації кількості ННЕ на кожному кроці виключення необхідною вибирати такий елемент, рядок і стовпець якого дають мінімальну кількість ненульових добутків Це означає, що треба вибирати такий елемент, у рядку та стовпці якого найменша кількість НЕ.

Правила вибору порядку виключення невідомих, які забезпечують появу мінімальної кількості ННЕ, називають критеріями оптимальної нумерації. Одним з найефективніших є критерій Марковіца, згідно з яким для чергового виключення вибирається та невідома, індекси коефіцієнта матриці якої та задовольняють умову де - нова кількість HHE, що можуть появитися під час виключення невідомої з індексам , ; , - кількість НЕ в рядку та стовпці матриці відповідно (без врахування -го елемента).

Але, як уже було сказано, не слід домагатися глобальної мінімізації кількості ННЕ, оскільки вона вимагає значних витрат додаткових логічних операцій і часто суперечить точності обчислень. Тому на практиці застосовують квазіоптимальне упорядкування, яке враховує всі названі фактори і звичайно розробляється стосовно конкретних типів задач.

Рис. 4.10

Вплив порядку виключення невідомих на кількість ННЕ наочно ілюструється за допомогою графів. Ними деколи користуються для встановлення раціонального порядку виключення елементів.

Припустимо, що задана матриця коефіцієнтів рівняння з НЕ вказаними хрестиками

Оскільки матриця діагонально симетрична, то її можна зобразити за допомогою неорієнтованого графа, показаного на рис. 4.10, . Вершини графа підпорядковані діагональним елементам матриці, ребра - її взаємним елементам. Підкреслюємо, що матриця не є розширеною матрицею суміжностей графа, й тут нема відповідного такій матриці зв'язку з графом.

Припустимо, що в наведеній матриці виключено елемент . В результаті одержуємо матрицю

в якій є чотири ННЕ – за критерієм Марковіца (позначені хрестиком в кружечку). Два взаємні елементи та три діагональні - скоректовані (позначені зірочкою)

Граф, що відповідає цій матриці, показаний на рис. 4.10, б. Оскільки між вершинами 2,3 і 4 графа рис. 4.10, існував зв'язок через вершину 1, то після її виключення такий зв'язок може бути забезпечений тільки через два нові ребра, вказані на графі рис. 4.10, б, що відповідають чотирьом ННЕ матриці Крім цього, появився паралельний зв'язок між вершинами 2 і 4, який еквівалентується одним ребром, що відповідає корекції двох взаємних елементів матриці. Таким чином, граф наочно показує нераціональність такого порядку виключення.

Із графа рис. 4.10, а й матриці (з врахуванням критерію Марковіца) видно, що оптимальним є виключення у порядку, починаючи з вершин (діагональних елементів) 3 чи 5. Тут не появляється ННЕ, оскільки в графі не порушуються зв'язки між вершинами (за критерієм Марковіца ). На рис. 4.10, в показаний граф після виключення

вершини 3. Матриця, яка відповідає такому виключенню, не містить жодного ННЕ. Скоректований тільки один елемент.

З викладеного ясно, що оптимальним з погляду мінімізації ННЕ є такий, наприклад, запис матриці (коли прийняти порядок виключення послідовно діагональних елементів, починаючи від першого верхнього):

На практиці застосовують дві групи методів квазіоптимального впорядкування послідовності виключення – методи попереднього впорядкування, в яких послідовність виключення встановлюється заздалегідь, і методи динамічного впорядкування, де вона визначається в процесі виключення.

До методів попереднього впорядкування відносяться метод мінімізації кількості НЕ рядка і стовпця, що відповідають головному елементові, та метод обрамування діагоналі.

Метод мінімізації НЕ уже розглядався вище. Він базується безпосередньо на критерію Марковіца. Практична його реалізація зводиться до впорядкування рівнянь системи, щоб забезпечити у першу чергу виключення тих невідомих, які зв'язані з найменшою кількістю інших невідомих. Якщо рівняння стану електричного кола записати в методі незалежних координат (незалежних чи вузлових напруг, незалежних чи контурних струмів), то кількість таких зв'язків визначається кількістю недіагональних елементів рядка матриці. Наочно задача інтерпретується на основі графа електричного кола. Коли рівняння записане в методі незалежних (вузлових) напруг, то кількість таких елементів визначається кількістю ребер графа у вершині, що виключається. У випадку незалежних (контурних) струмів кількість недіагональних елементів визначається кількістю суміжних ребер у контурі, який виключається.

У випадку рівнянь стану, записаних у методі законів Кірхгофа, діагоналізація елементів рівнянь не має місця. Даний струм (рівняння законів Кірхгофа в координатах струмів віток) чи напруга (рівняння законів Кірхгофа в координатах напруг віток) виступає тут у двох рівняннях - рівнянні першого та в рівняннях другого законів Кірхгофа. Отже, мінімізацію елементів таких рівнянь слід вести з пошуком відповідного елемента за критерієм Марковіца. У графі самого кола задається такий порядок запису рівнянь за першим і другим законами Кірхгофа, який забезпечує поступове зростання кількості струмів чи напруг у цих рівняннях.

Слід сказати, що застосування графів для оптимізації порядку виключення має суто дидактичне значення, оскільки таке впорядкування рівнянь здійснюється або до їх автоматичного формування на основі вершинної множини (метод незалежних напруг), чи контурної множини (метод незалежних струмів) і виконується їх відповідна нумерація, або впорядковуються уже сформовані рівняння. Алгоритми та програми впорядкування в обох випадках нескладні, але для систем рівнянь порядку більше ста вони малопридатні, тому що попереднє впорядкування для таких систем дає результат звичайно далекий від мінімуму ННЕ.

Метод обрамування діагоналі полягає в згрупуванні елементів матриці у вигляді вузької смуги-стрічки вздовж головної чи побічної діагоналі матриці. Матриці з таким згрупуванням елементів часто називають стрічковими. Вони відповідають графам такої ж структури. Для групування НЕ біля головної діагоналі матриці вузлових адмітансів необхідно вибрати вершину з мінімальною кількістю ребер і присвоїти їй номер 1. Наступні номери слід присвоїти всім вершинам, ^;що зв'язані з вершиною 1. Далі повторюється така процедура для інших вузлів.

Наприклад, для графа рис. 4.11 за наведеним алгоритмом забезпечується матриця вузлових адмітансів зі структурою

Очевидно, одержана матриця ідеальна. На практиці стрічка містить нулі, а поза нею також є НЕ.

Для обрамування побічної діагоналі необхідно вершині з мінімальною кількістю ребер присвоїти номер 1, а вершинам, зв'язаним з нею, – найвищі номери. У свою чергу, вершинам, що зв'язані з високими номерами вершин, присвоювати найнижчі номери і т. д. У результаті формується матриця вузлових адмітансів, по головній діагоналі якої записані тільки власні адмітанси вузлів, а взаємні адмітанси розташовані вздовж і навколо побічної діагоналі.

У випадку методу незалежних (контурних) струмів поданий алгоритм обрамування діагоналей застосовується відповідно до нумерації контурів з належним вибором шляхів контурів.

Методи обрамування звичайно ефективні тільки для графів спеціальної структури. Наприклад, стосовно матриць вузлових адмітансів метод обрамування головної діагоналі ефективний для ланцюгових електроенергетичних мереж з графом типу рис. 4.11, метод обрамування побічної діагоналі – для магістральних мереж.

Для схеми ЕЕС у вигляді розгалуженої мережі, граф якої показаний на рис. 4.12, обрамування головної діагоналі містить значну кількість нульових елементів у самій стрічці масиву й має такий характерний вигляд:

Динамічне впорядкування полягає в оптимізації порядку виключення невідомих у процесі розв'язування рівняння. Такий підхід найефективніший, оскільки тут на кожному кроці обчислень можна вибрати наступний елемент виключення за критерієм оптимальності.

Серед таких методів у задачах електроенергетики застосовують метод динамічної мінімізації НЕ у рядках і стовпцях матриці та метод динамічної мінімізації ННЕ.

Метод динамічної мінімізації НЕ в рядках і стовпцях матриці формально збігається з відповідним методом попереднього впорядкування з тою різницею, що тут визначається мінімальна кількість НЕ, зв'язаних з елементом, який виключається на кожному кроці. Слід підкреслити простоту його програмної реалізації. Правда, при високих порядках систем кількість логічних операцій значно зростає. Але коли врахувати, що такий алгоритм повинен працювати тільки з НЕ та ННЕ, то стосовно скінченних рівнянь задач електроенергетики він високоефективний і забезпечує порядок виключення змінних, близький до оптимального.

Метод динамічної мінімізації ННЕ передбачає виключення тої невідомої, яка викликає появу мінімальної кількості додаткових ННЕ. Очевидно, такий підхід гарантує оптимальне виключення на даному кроці. Принципово на його основі ціною відповідного машинного часу можна забезпечити глобальний оптимум порядку виключення, якщо заздалегідь оглянути всі кроки виключення.

Як показали всебічні дослідження та узагальнення досвіду, для рівнянь невисокого порядку (10-15 змінних) у більшості випадків нема потреби оптимізації порядку виключення невідомих, оскільки він дає порівняно малу економію пам'яті ЦОМ, а ще менше скорочує машинний час. Особливо це стосується одноразового розв'язування задачі. Однак масові задачі навіть для такого порядку систем слід оптимізувати.

Під час оцінки ефективності методу оптимізації виключення необхідно враховувати його вплив на інші показники ефективності – точність і кількість операцій. У тому випадку, коли розв'язується система рівнянь до 80-100-го порядку, доцільно застосовувати методи попереднього впорядкування, особливо під час розв'язування немасових задач. При цьому метод обрамування слід розглядати як спеціалізований стосовно вказаного вище типу структур рівнянь. Його переваги – заздалегідь відомий обсяг пам'яті ЦОМ (за шириною діагональної смуги) і найбільша простота програмування.

Для рівнянь високого порядку загального вигляду, наприклад рівнянь стану складних ЕЕС в усталених чи перехідних процесах, необхідним є застосування методів динамічного впорядкування. Вони значно складніші від методів попереднього впорядкування та вимагають набагато більше машинного часу. Найдоцільніший метод динамічної мінімізації кількості НЕ в рядках і стовпцях, оскільки він значно простіший і потребує менше машинного часу, ніж метод мінімізації додаткових ННЕ. Правда, останній звичайно забезпечує більшу економію пам'яті, але ціною значної перевитрати машинного часу. Як показує досвід, для складних задач аналізу й оптимізації ЕЕС та їх підсистем поєднання методу динамічної мінімізації НЕ в рядках і стовпцях з методами факторизааії забезпечує найефективніші алгоритми розв'язування систем скінченних рівнянь.