НАУКА и ОБРАЗОВАНИЕ

УДК.51-37

МГТУ им. Н.Э. Баумана

ООО «Алексэн»

vicboevkin@gmail.com

olga@alexen.ru

1. Постановка задачи

При математическом моделировании электрических сетей, в частности, при решении уравнений установившегося режима, на промежуточных этапах вычислений часто приходится решать системы линейных алгебраических уравнений (СЛАУ).

Характерными особенностями матрицы таких СЛАУ являются большая размерность, диагональное преобладание и слабая заполненость [1]. При слабой заполнености матрицы во многих случаях предпочтительнее пользоваться итерационными методами решения, в которых одним из важнейших факторов является скорость сходимости [2].

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

Общая методика построения стационарных итерационных схем решения СЛАУ  – го порядка

                                                                      (1)

представляется, согласно [3], [4] и др., в виде

.                                             (2)

Здесь матрица расщепления– произвольная, неособая, легко обратимая матрица, определяющая итерационный метод, коэффициент экстраполяции  – произвольный скалярный множитель, k– номер итерации.

Из (2) можно получить

  ,                                            (3)

 ,   ,   ,

где  – матрица перехода.

Общее решение разностного уравнения (3) при= const можно записать [5]  в виде

 ,                              (4)

 .                                                                      (5)

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

  .                                             (6)

Отметим, что выражение (4) справедливо для случая некратных корней.

Матричное разностное уравнение (3) можно написать для каждой компоненты  вектора неизвестных :

 _,                         (7)

 ,                 .

Здесь  – компоненты установившегося решения (5).

Коэффициенты  разностных уравнений (7) одинаковы для всех компонентов и совпадают с коэффициентами характеристического уравнения (6).

Решения уравнений (7) совпадают с соответствующими строками матричного решения (4), т.е.

.                                (8)

Если модули всех корней  , то итерационные решения (4) и (8) сходятся к решнеию (5) при .

Будем считать, что собственные значения пронумерованы так, что

 .                                                                             (9)

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

  .                                             (10)

2. Нейтрализация наибольшего корня

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

Оценка наибольшего по модулю корня может быть произведена по близкой к изложенной в [6] методике и с данными, взятыми из исходного итерационного процесса.  Из решения (8) видно, что с ростом числа итераций  наступает ситуация, когда влиянием всех слагаемых, кроме первых двух, можно пренебречь. Тогда имеем

 ,

 ,                                      (11)

  ,

где   .

Система уравнений (11) легко разрешается относительно неизвестных,  , которые являются функциями от . Сформируем разности

 ,                                              (12)

 .

Отсюда получим

, ,  .   (13)

            Методика ускорения итерационного процесса, вычисляемого по (3), заключается в следующем. По одной из компонент решения x_i(k) на каждом шаге дополнительно вычисляются параметры (13). Когда эти величины установятся с заданной точностью, можно прекратить итерационный процесс, вычислив на последней итерации  и  для всех остальных компонентов решения (3).

Число итераций при этом оценивается соотношением (10), но для второго по величине  корня  из (9).

3.  Нейтрализация нескольких корней

Из решения (8) видно, что с ростом числа  итераций последовательно

уменьшается число существенных слагаемых. Рассмотрим ситуацию, когда в (8) останется только  существенных членов

   .                            (14)

Выражение (14) будем трактовать как решение разностного уравнения - го порядка:

 ,

 ,     (15)

 .

Характеристическое уравнение для (15)

                                         (16)

имеет корни, соответствующие (14).

При известных значениях, вычисляемых в процессе итерационного решения уравнения (3), можно определить все остальные параметры уравнения (15)

( коэффициенты и установившиеся значения  ) методами идентификации разностных уравнений [5], [7]. После этого, при необходимости, из (16) можно приближенно вычислить  наибольших по модулю собственных значений матрицы перехода из (3). Идентификацию уравнения (15) можно произвести следующим, например, образом.

Обозначим разность двух соседних отсчетов

   .                                               (17)

С учетом (17) cформируем невязку  ввиде разности двух уравнений из (15), опустив для простоты написания индекс строки  

.        (18)

Приравняв нулю m невязок (18), , получим линейную систему уравнений для определения коэффициентов в виде 

 .                  (19)

Соотношения (16) и (19) аналогичны соответствующим соотношениям из [8], где решается задача оценки  наибольших по модулю собственных значений.

Вычислив  из (19), можно найти  из (15). Эти операции необходимо производить по одной из компонент  на каждом шаге итерационного решения уравнения (3) до тех пор, пока  и  не установятся с допустимой  погрешностью. После этого, используя значения , можно вычислить установившиеся значения  для всех остальных компонент вектора .

В рассмотренном алгоритме нет необходимости вычислять корни уравнения (16), хотя возможность такая имеется.

Оценка числа итераций определяется соотношением (10), где вместо наибольшего корня  нужно подставить  – ый корень из (9). Кроме того, к полученным значениям числа итераций следует добавитьитераций, расходуемых на процесс идентификации. Таким образом, теоретическую оценку следует производить по формуле

     .                                (20)

Отметим, что при повторных решениях уравнения (3) для других правых частей  и других начальных приближениях, коэффициенты  не изменяются, поэтому решать уравнения (19) нет необходимости. Применение алгоритма при этом сводится к вычислению величины  из (15) при известных .

4.  Оптимизация коэффициента экстраполяции

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

  .

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

 .                                                               (21)

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

5.  Примеры расчетов установившегося режима электросетей.

Проиллюстрируем ускорение итерационного решения СЛАУ на примерах расчетов установившихся режимов электросетей переменного тока различной размерности от n=10 до n=333.

Все матрицы симметричные, разреженные (слабо заполненные)  и с  диагональным преобладанием  [1], [2].

Результаты расчетов, выполненных по методу Гаусса-Зейделя, приведены в таблице 1. 

Таблица 1

Количество итераций для метода Гаусса - Зейделя

     Таблица 1 содержит теоретические оценки количества итераций  , полученые по формуле (20), а также фактические количества итераций  , полученные в результате счета. Количество нейтрализуемых корней варьировалось от 1 до 5

(0 – соответствует варианту расчета без нейтрализации корней).

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

      Рис.1 иллюстрирует сходимость итерационных процессов метода Гаусса-Зейделя для матрицы 49-го порядка.

Рис. 1.  Сходимость итерационных процессов метода Гаусса – Зейделя.

На рис.1  кривая 1 () – без нейтрализации корней (число итераций ) , кривая 2 () – с нейтрализацией пяти старших корней  с вычислением  () , кривая 3 () - с нейтрализацией пяти старших корней  с известными  () . Каждый итерационный процесс представлен своей самой медленно затухающей компонентой.   

6.  Метод последовательной верхней релаксации.

 Векторно-матричная итерационная схема для метода последовательной верхней релаксации [8] имеет вид

 ,             (22)

.

Здесь  - диагональная матрица, построенная из диагональных элементов ;  - строго нижняя треугольная матрица с ненулевыми элементами, равными элементам матрицы ;  - строго верхняя треугольная матрица, такие, что .

Множитель  здесь называется параметром релаксации. При значении параметра релаксации  метод последовательной верхней релаксации совпадает с методом Гаусса – Зейделя. Установлено [8], что для сходимости процесса (22) необходимо, чтобы . В общем случае задача нахождения оптимального значения параметра , когда спектральный радиус матрицы  из (22) будет минимальным, не решена [8].  В настоящей работе оптимальные значения параметра  для всех рассматриваемых случаев определялись численным подбором (как рекомендуется в [8] ). В таблице 2 приведены количества итераций, полученные в результате расчетов по методу последовательной верхней релаксации  с оптимальными значениями параметра  без нейтрализации корней и с нейтрализацией одного корня.

Таблица 2.

Количество итераций для метода последовательной верхней релаксации.

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

2-х раз, как в случае с матрицей 333-го порядка.

Заключение

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

Литература

1. Брамеллер А., Аллан Р., Хэмэм Я.  Слабозаполненные матрицы: Анализ электро-энергетических систем. - М.: Энергия, 1979. – 192 с. 

2. Идельчик В.И., Расчеты и оптимизация режимов электрических сетей и систем. – М.: Энергоатомиздат, 1988. – 288 с.: ил.

3. Cамарский А.А. Введение в численные методы. - М.: Наука . 1982. –  272 с.

4. Марчук Г.И., Кузнецов Ю.А. Итерационные методы и квадратичные функционалы., Cборник  “Методы вычислительной математики” – Новосибирск,  Наука, 1975. -143 с.

5. Кузовков Н.Т. и др. Непрерывные и дискретные системы управления и методы идентификации. - М.: Машиностроение, 1978. – 222 с.

6. Фадеев Д.К., Фадеева В.Н. Вычислительные методы линейной  алгебры – М.: Физматгиз, 1963.

7. Гроп Д., Методы идентификации систем. – М.: Мир,1979. – 303 с.

8. Хейгеман Л., Янг Д. Прикладные итерационные методы - М.: Мир , 1986 – 446 с.