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

НАУЧНЫЕ СООБЩЕНИЯ

О.М Булгаков, М. Ю. Пакляченко

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

METHOD OF CONVERGENCE ACCELERATION OF STRUCTURAL-BASED LINEAR ALGEBRAIC EQUATION

SOLUTION ALGORITHM

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

A modification of the linear algebraic equation describing multichannel systems with parallel structure solution iterative method is proposed. The modificated iterative method distinctive feature is the complemented procedure of linear algebraic equations solution convergence acceleration.

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

Структурно-ориентированный алгоритм расчета распределения по изоморфным компонентам параметра, поступающего на общий вход системы (например, тока в системе индуктивно связанных параллельно соединенных двухполюсников, моделирующей транзисторные ячейки мощного ВЧ (СВЧ) усилителя со структурой «делитель-сумматор мощности» [3]), представлен на рис. 1.

Будем считать взаимные характеристики ресурсов системы, численно отражаемые компонентами массива коэффициентов М [i, j ], заранее определенными.

Рис. 1. Блок-схема нахождения корней СЛАУ структурно-ориентированным модифицированным итерационным алгоритмом с процедурой ускорения сходимости

На нулевой итерации значения служебных массивов £0 [И], С0 [/'] численно равны

единицам, служебный коэффициент С20 и компоненты вектора Г0 [и] — нули.

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

Х о И = Х0,

И = 1...N, где N — размер СЛАУ. Для простоты можно полагать Х0 = N.

Массив значений лимитирующей величины (например, падения напряжения [3], загруженности канала и др.) производится по формуле

Г И = Го и+Х х,_1 [, 1]М[и,;]

Для обеспечения сходимости итерационного процесса задаются служебные массивы £ и С на последующих итерационных этапах вычисляются по формулам

[И] =

Гк тах

Гк [и]

где коэффициент Z — значение «ускорителя», предназначенного для сокращения числа итераций поиска корней СЛАУ, Yk max — максимальный по значению компонент из

вектора чисел лимитирующей величины Yk [i] на текущем шаге,

Произведем вычисление коэффициента С2 , участвующего в формировании компонентов вектора Х следующего приближения:

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

Количество итераций зависит от размера матрицы коэффициентов и известной величины ц неоднородности значений коэффициентов в строке, отождествляемой, например, со значением декремента межканального затухания или убывания с расстоянием коэффициентов взаимной индукции [3] и используемой для формирования симметричной матрицы из элементов последовательности Х, убывающей по экспоненциальному закону:

Применительно к многоканальным системам значение элементов последовательности интерпретируется как количественная характеристика взаимодействия (взаимосвязи) между каналами. Таким образом, коэффициент л в (7) количественно характеризует уменьшение взаимодействия между соседними каналами с номерами И и И +1; И = 1...N — номер элемента последовательности (канала).

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

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

Принципиальная разница предлагаемого алгоритма от приводимого ранее [4] заключается в функции регулирования скорости сходимости, которая определяется процедурой возведения в степень 2 служебного массива £к[И].

В ходе вычислительных экспериментов по реализации метода было изучено влияние дополнительной процедуры - «ускорителя» на сходимость метода при

С [i] = С-i [i] • sk [i]

X = ехр(—л • i) .

фиксированной точности вычислений (е=0,01) и вариативном задании основных характеристик системы: размера СЛАУ ( N [3...30]), степени неоднородности коэффициентов симметричной матрицы ( л [0,01 ...1,5]).

Теоретически максимальной скоростью сходимости является численное значение количества произведенных итераций К = 2 . Однако, как показала практическая реализация, такие оптимальные результаты возможны лишь при высокой неоднородности в СЛАУ.

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

XI

160-- У".... - „

140-

120

Ч------------------------1 1 110-----------------------15----------------------20-----------------------25

Рис. 2. Зависимость числа итераций от размера матрицы для различных значений декремента межканального затухания при 2=1

и 2>1

Из графиков видно, что для СЛАУ с относительно невысокой неоднородностью линейных коэффициентов (ц<0,8) применение процедуры-ускорителя эффективно. Для систем с большим значением декремента введение в алгоритм решения СЛАУ процедуры-ускорителя ухудшает скорость сходимости (сплошные линии пересекают пунктирные).

Модификация рассматриваемого итерационного алгоритма решения СЛАУ может выполняться путем ввода «ускорителя» ((3), рис. 1), предназначенного для сокращения числа итераций. Она наиболее эффективна для матриц небольшого размера, обладающих невысокой неоднородностью значений элементов строк.

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

увеличивающих свой размер, при фиксированной неоднородности достигает постоянной

величины ( KI„ределЬн0е )[5].

Дальнейшее исследование предлагаемого модифицированного итерационного алгоритма решения СЛАУ предполагает нахождение оптимальных значений показателя степени (значения Z) в процедуре-ускорителе, которые, обеспечивая предназначение процедуры — снижение до минимума количества итераций при нахождении корней системы, не приводят к расходимости решения задачи.

ЛИТЕРАТУРА

1. Шелухин О.И., Тенякшев А.М., Осин А.В. Моделирование информационных систем / под ред. О.И. Шелухина. — М.: Радиотехника, 2005. — 368 с.

2. Вержбицкий В.М. Численные методы (линейная алгебра и нелинейные уравнения). — М.: Высшая школа, 2000. — 266 с.

3. Программное средство «Расчет рабочих токов транзисторов» // Булгаков О.М.,

Пакляченко М.Ю; разработано в ФГКОУ ВПО «Воронежский институт Министерства внутренних дел Российской Федерации». — №50201450290 от 22.04.2014,

зарегистрировано в Государственном информационном фонде неопубликованных документов ФГАНУ «Центр информационных технологий и систем органов исполнительной власти».

4. Булгаков О.М., Пакляченко М.Ю. Анализ сходимости модифицированного итерационного метода решения систем линейных алгебраических уравнений // Вестник Воронежского института МВД России. — 2014. — №1. — С. 49—56.

5. Булгаков О.М., Пакляченко М.Ю. Исследование сходимости модифицированного итерационного метода // Информатика: проблемы, методология, технологии: материалы XIV Международной научно-методической конференции, Воронеж, 6—8 февраля 2014 г.: в 4 т. / Воронежский государственный университет. — Воронеж: Издательский дом ВГУ, 2014. — С. 212—215.

REFERENCES

1. Shelukhin O.I., Tenyakshev A.M., Osin A.V. Modelirovanie informatsionnyh sistem / pod red. O.I. Shelukhina. — M.: Radiotehnika, 2005. — 368 s.

2. Verzhbitskiy V.M. Chislennyie metodyi (lineynaya algebra i nelineynyie uravneniya).

— M.: Vyisshaya shkola, 2000. — 266 s.

3. Programmnoe sredstvo «Raschet rabochih tokov tranzistorov»// Bulgakov O.M., Paklyachenko M.Yu; razrabotano v FGKOU VPO «Voronezhskiy institut Ministerstva vnutrennih del Rossiyskoy Federatsii». — N50201450290 ot 22.04.2014, zaregistrirovano v Gosudarstvennom informatsionnom fonde neopublikovannyih dokumentov FGANU «Tsentr informatsionnyih tehnologiy i sistem organov ispolnitelnoy vlasti».

4. Bulgakov O.M., Paklyachenko M.Yu. Analiz shodimosti modifitsirovannogo ite-ratsionnogo metoda resheniya sistem lineynyih algebraicheskih uravneniy // Vestnik Voronezhskogo instituta MVD Rossii. — 2014. — N1. — S. 49—56.

5. Bulgakov O.M., Paklyachenko M.Yu. Issledovanie shodimosti modifitsirovannogo iteratsionnogo metoda // Informatika: problemyi, metodologiya, tehnologii: materialyi XIV Mezhdunarodnoy nauchno-metodicheskoy konferentsii, Voronezh, 6—8 fevralya 2014 g.: v 4 t. / Voronezhskiy gosudarstvennyiy universitet. — Voronezh: Izdatelskiy dom VGU, 2014.

— S. 212—215.

СВЕДЕНИЯ ОБ АВТОРАХ

Булгаков Олег Митрофанович. Заместитель начальника по учебной работе. Доктор технических наук, профессор.

Воронежский институт МВД России.

E-mail: ombfrier@yandex.ru

Россия, 394065, г. Воронеж, проспект Патриотов, 53. Тел. (473)2-735-290.

Пакляченко Марина Юрьевна. Адъюнкт кафедры информационной безопасности.

Воронежский институт МВД Ро^ии.

E-mail: marina_lion@mail.ru

Россия, 394065 г. Воронеж, проспект Патриотов, 53. Тел. 83204403845.

Bulgakov Oleg Mitrofanovich. The deputy head on study. Doctor of technical sciences, professor. Voronezh Institute of the Ministry of the Interior of Russia.

Work address: Russia, 394065, Voronezh, Prospect Patriotov, 53. Tel. (473)2-735-290.

Paklyachenko Marina Yurievna. Post-graduate cadet of the Information Security chair.

Voronezh Institute of the Ministry of the Interior of Russia.

Work address: Russia, 394065, Voronezh, Prospect Patriotov, 53. Tel. 89204403845.

Ключевые слова: модель; системы линейных алгебраических уравнений; итерация; сходимость, матрица.

Key words: model; linear algebraic equations systems; iteration; convergence; matrix.

УДК 519.612.2

ИЗДАНИЯ ВОРОНЕЖСКОГО ИНСТИТУТА МВД РОССИИ

Занина Т.М. Правовые основы информационной безопасности в органах внутренних дел: курс лекций / Т.М. Занина, А.А. Караваев, К.Д. Рыдченко. — Воронеж: Воронежский институт МВД России. — 167 с.

В курсе лекций раскрывается содержание дисциплины «Правовые основы информационной безопасности в органах внутренних дел». Рассмотрены особенности правового регулирования защиты информации и обеспечения информационной безопас-

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

правового регулирования информационной безопасности.