ВВЕДЕНИЕ
1. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ 1.1. Актуальность работы
Разреженные матрицы встречаются при решении многих важных практических задач: структурного анализа, теории электрических сетей и систем распределения энергии, численного решения дифференциальных уравнений, теории графов, а также генетики, социологии и поведенческих наук, программирования для ЭВМ [56]. В связи с развитием современной техники можно ожидать, что и дальше разреженные матрицы будут встречаться во многих прикладных задачах, включающих большие системы.
Литература на русском языке, посвященная разреженным матрицам, пополнилась за последние несколько десятков лет достаточно хорошо [52, 25-28, 20, 22, 43, 44, 14, 15, 57, 47]. В каждой из названных выше книг рассматривается лишь какая-нибудь одна задача линейной алгебры, а подчас даже ее специальный случай — спектральный анализ, решение симметричных положительно определенных систем, несимметричные системы с квадратными матрицами и т.п.
Чем больше параметров исследуемого объекта охватывает математическая модель, тем точнее и ближе к реальности получается результат. С ростом параметров растет размер матрицы. По мере того, как растут производительность и быстродействие вычислительных машин, становится возможным обрабатывать все большего размера матрицы, и тем самым уточнять математические модели. Несмотря на стремительное развитие вычислительной техники, по-прежнему, как и несколько десятков лет назад основными характеристиками остаются: память, трудоемкость и быстродействие. С ростом порядка матричной задачи растет и стоимость ее решения, становясь решающим фактором.
При условии, что система уравнений является разреженной, считается неэффективным хранение и обработка всей матрицы. Можно значительно
сэкономить память, уменьшить время решения поставленной задачи и тем самым уменьшить стоимость решения, если хранить и обрабатывать только ненулевые элементы.
К примеру, известно, что Россия занимает второе место в мире по производству первичного алюминия. Так, при общем объеме мирового производства в 1996г. - 20844 тыс. тонн, на долю России приходится 2871 тыс. тонн, или 13,8% [50].
На современном этапе алюминий широко используется во многих отраслях рыночной экономики: - электрификации, машиностроении, строительстве, быту и многих других отраслях. Применение алюминия в современном производстве дало большой скачок в его развитии.
В 1993г. Россия^ вышла на первое место в мире по экспорту первичного алюминия и к 1996г. ушла далеко вперед, поставляя 2455 тыс. тонн алюминия против 1841 тыс. тонн-у Канады и 1129 тыс. тонн у Австралии, занимающих второе и третье места соответственно [51].
Обращает на себя внимание то обстоятельство, что из 11 отечественных производителей, два (Братский и Красноярский) алюминиевых завода являются крупнейшими в мире.
Российской алюминиевой промышленности характерны высокая конкурентоспособность, тесная интеграция в мировой рынок и экспортная направленность.
Проблемы по защите окружающей природной среды, улучшению условий труда, повышению технико-экономических показателей работы определяют необходимость модернизации и реконструкции основной части алюминиевых заводов России.
Политика администрации Братского алюминиевого завода (БрАЗа) направлена на совершенствование уровней хмеханизации и автоматизации. В последнее время на заводе появляются все больше механизмов и машин, облегчающих работу персонала. Это машины по пробивке корки электролизера, машины по загрузке анодной массы, краны с автоматическими манипуляторами
и т.п. В области автоматизации идет реорганизация старых систем АСУТП на новые, соответствующие новейшим технологиям.
В связи с этим идет непрерывная работа по оптимизации управления отдельными объектами и всего алюминиевого завода. Учеными строятся и анализируются различные математические модели, большинство из которых сводятся к решению больших разреженных систем линейных уравнений.
При оптимизации процесса получения алюминия получается несимметричная прямоугольная разреженная система линейных уравнений, которая требует отдельного подхода.
Настоящая диссертационная работа посвящена разработке прямых методов обращения больших разреженных несимметричных матриц и методике решения больших разреженных прямоугольных систем линейных уравнений на основе приведения матрицы системы к односторонне окаймленной блочной диагональной форме, программной реализации алгоритма приведения разреженной матрицы к блочной диагональной форме. Большое внимание уделяется критериям преобразования подобных матриц к некоторым простым формам, позволяющим оптимизировать дальнейшее решение основанных на них систем линейных уравнений.
1.2. Цель диссертационной работы
Цель диссертационной работы состоит в разработке прямых малотрудоемких методов приведения больших разреженных несимметричных прямоугольных матриц к блочному диагональному и блочному треугольному видам с сохранением первоначальных значений элементов матриц, обеспечивающих оптимизацию процесса решения систем линейных уравнений, основанных на подобных матрицах и используемых во многих математических задачах.
1.3. Основные задачи работы
К основным задачам диссертационной работы относятся: . 1. Разработка алгоритма приведения прямоугольной разреженной матрицы произвольного размера и структуры к блочной диагональной форме (BDF).
2. Разработка критериев применимости алгоритма приведения разреженных прямоугольных матриц к форме BDF.
3. Проведение сравнительного анализа методов приведения разреженных матриц к форме BDF.
4. Разработка алгоритма приведения прямоугольной разреженной матрицы произвольного размера и структуры к блочной треугольной форме (BTF).
5. Проведение сравнительного анализа методов приведения разреженных матриц к форме BTF.
6. Апробация разработанных алгоритмов на примере решения большой разреженной прямоугольной системы линейных уравнений, получаемой при синтезе системы управления процессом электролиза алюминия.
1.4. Методы исследования
В процессе разработки и анализа алгоритмов приведения больших разреженных матриц к блочному диагональному виду использовались методы теории графов, линейной алгебры, логики, теории вероятности и математической статистики, теории алгоритмов.
Результаты работы получены с помощью программных пакетов: обработка матриц с целью получения данных для анализа - Delphi 6.0; первичная обработка полученных данных - Excel 97; статистическая обработка данных — Statistica 6.0, MiniTab 32; решение систем линейных уравнений -Matlab 6.1, Maple 7.0.
1.5. Научная новизна и вклад в разработку проблемы
Научная новизна диссертационной работы заключается в следующем:
1. Обосновывается выбор приведения матрицы к блочной диагональной форме, как к наиболее приемлемой форме при решении больших прямоугольных разреженных систем линейных уравнений с достаточно большим количеством строк с несколькими ненулевыми элементами.
2. Разработан алгоритм приведения прямоугольной разреженной матрицы к блочной диагональной форме. Алгоритм имеет малую трудоемкость и легко поддается машинной реализации.
3. Проведен анализ полученного алгоритма, сравнение с другими алгоритмами по приведению матрицы к специальным формам, дано обоснование его применимости.
4. Выведены ограничения на структуру разреженной матрицы, позволяющие судить о результатах алгоритма до его применения. Это позволяет в некоторых случаях сэкономить время при выборе оптимального метода решения математической модели.
5. Разработан алгоритм приведения прямоугольной разреженной матрицы к блочной треугольной форме. Алгоритм имеет малую трудоемкость и легко поддается машинной реализации.
6. Проведен анализ полученного алгоритма, сравнение с другими алгоритмами по приведению матрицы к специальным формам, дано обоснование его применимости.
1.6. Положения, выносимые на защиту
На защиту выносятся следующие положения:
сэ постановка задачи решения больших прямоугольных разреженных систем
линейных уравнений; о результаты исследования существующих алгоритмов обработки больших
разреженных матриц;
о алгоритм приведения прямоугольной разреженной матрицы к блочной
диагональной форме; еэ результаты анализа ограничений на структуру разреженной матрицы,
позволяющих судить о результатах алгоритма до его применения; еэ результаты сравнительного анализа алгоритма приведения прямоугольной
разреженной матрицы к блочной диагональной форме; Еэ алгоритм приведения прямоугольной разреженной матрицы к блочной
треугольной форме; ши результаты сравнительного анализа алгоритма приведения прямоугольной
разреженной матрицы к блочной треугольной форме; шш) результаты тестирования алгоритмов на примере решения математической
модели оптимального управления электролизером по выбранным критериям
- максимум выливаемого алюминия при минимуме напряжения
электролизной ванны.
1.7. Практическая ценность
Исследования автора выполнялись в рамках госбюджетной тематики «Топологические методы идентификации и синтеза систем управления многосвязными объектами» (код ГРНТИ 27.19.19), выполняемой в Братском государственном техническом университете по направлению «Теория, методы и средства автоматизации систем переработки информации и управления».
Результаты диссертационной работы позволили оценить возможность организации поиска оптимального решения больших прямоугольных разреженных .систем линейных уравнений по критерию уменьшения времени, затрачиваемого на анализ математической модели.
Настоящие исследования служат основой для дальнейшего развития методики решения больших прямоугольных разреженных систе*м линейных уравнений и позволяют значительно увеличить объемы математических моделей, включая новую информацию об исследуемом объекте. Теоретические и практические результаты, полученные в работе могут быть использованы при
10
чтении курсов: «Математическое моделирование»; «Основы САПР»; «Теория автоматического управления», «Теория алгоритмов».
1.8. Апробация работы
Основные результаты работы докладывались на межрегиональной научно-технической конференции «Естественные и инженерные науки -развитию регионов» (Братск, БрГТУ, 2002; Братск, БрГТУ, 2003; Братск, БрГТУ, 2004); на VI всероссийской научно-технической конференции "Новые информационные технологии» (г. Москва, Московская государственная академия приборостроения и информатики, 2003).
1.9. Публикации По теме диссертации опубликовано 11 работ, в том числе 3 статьи и 8
ТсЗИСОБ.
1.10. Структура и объем диссертационной работы
Диссертация состоит из введения, пяти глав, заключения, списка литературы. Объем диссертации составляет 143 страницы основного текста, 32 рисунка, 22 таблицы, 8 приложений. Список литературы содержит 68 наименований.
11
ГЛАВА 1. АНАЛИЗ ТЕХНОЛОГИИ ОБРАБОТКИ РАЗРЕЖЕННЫХ
МАТРИЦ В МАТЕМАТИЧЕСКИХ МОДЕЛЯХ СИСТЕМ
УПРАВЛЕНИЯ ТЕХНОЛОГИЧЕСКИМИ ПРОЦЕССАМИ
1.1. Топологический метод синтеза многосвязных систем управления технологическими процессами
На современном этапе производительность предприятий во многом определяется сроками ввода в эксплуатацию новых технологических процессов и оборудования. При этом больше всего затрачивается время на исследование и разработку нового оборудования и систем. Значительной экономии времени и средств можно достигнуть путем применения вычислительной техники для автоматизации научно-исследовательских и проектных работ.
В области проектирования сложных систем управления производственными процессами в последнее время наблюдается широкое использование формализованного аппарата теории автоматических систем с целью получения промышленных систем, удовлетворяющих различному множеству критериев [16]. Этот аппарат в силу своей формализации позволяет интенсивно использовать вычислительную технику, тем самым, повышая качество проектирования систем управления при одновременном сокращении сроков и приближая проектное решение к оптимальному.
Термин «синтез» (в переводе с греческого «synthesis» - соединение, сочетание, составление) означает соединение различных элементов, сторон объекта в единое целое, систему с целью изучения, применения. Под синтезом систем автоматического управления понимают определение структуры, значений параметров и состава элементов системы, при которых данная система удовлетворяет.предъявляемым к ней требованиям.
В качестве основы синтеза рассматривается определенная функциональная зависимость отдельно взятой компоненты от ее структурного расположения в системе [4]. Далее опираясь на теорию графов, матричную теорию, теорию
12
структурных схем можно формализовано представить систему управления, которая учитывает структуру проектируемой или гипотетической системы.
Современные системы управления объединяют широкое разнообразие физических компонент или элементов. Наиболее полное представление о системах различной природы можно получить с помощью графов.
В самом наглядном представлении граф, обозначаемый символом G = (^,?), представляет собой множество вершин V, связи между которыми определены множеством ребер ?[49].
Часто связи между объектами характеризуются вполне определенной ориентацией. Для указания направления связи между вершинами графа соответствующее ребро отмечается стрелкой. Ориентированное таким образом ребро называют дугой, а граф с ориентированными ребрами - ориентированным графом или орграфом [11].
Дальнейшее обобщение отображения связей между объектами с помощью графов состоит в приписывании ребрам, дугам или вершинам некоторых количественных значений, качественных признаков или характерных свойств, называемых весами.
Особое значение для моделирования физических систем приобрели взвешенные ориентированные графы, названные графами потоков сигналов или сигнальными графами [45]. Вершины сигнального графа отождествляются с некоторыми переменными, характеризующими состояние системы, а вес каждой вершины означает функцию времени или величину, характеризующие соответствующую переменную (сигнал вершины). Дуги отображают связи между переменными, и вес каждой дуги представляет собой численное или функциональное отношение, характеризующее передачу сигнала от одной вершины к другой (передача дуги).
Пусть F = {v,,v2,K .v^,} и ? = {ё,,е2,К ,eq) - соответственно множества
вершин и ребер (p,q)-графа. Каждое ребро ек е Е соединяет пару вершин v,,VjGV, являющихся его концами (граничными вершинами). Для
13
ориентированного ребра (дуги) различают начальную вершину, из которой дуга исходит, и конечную вершину, в которую дуга заходит.
Число ребер, связанных с вершиной v, называют степенью вершины и
обозначают через S(vt) или deg(v().
Две вершины v, и v, е V графа G = (У,Е) называются смежными, если они являются граничными вершинами ребра ek e E.
Граф можно представить матрицей смежности. Строки и столбцы этой матрицы соответствуют вершинам графа, а ее (f, j) -элемент равен числу кратных ребер, связывающих вершины v, и vy (или направленных от вершины v, к вершине v, для орграфа).
Исходное описание графа дает его матрица инцидентности. Если вершина v, является концом ребра ек, то говорят, что они инцидентны. В то время как
смежность представляет собой отношение между однородными объектами (вершинами), инцидентность - это отношение между разнородными объектами (вершинами и ребрами).
Рассматривая инцидентность вершин и ребер (p,q) -графа, его можно представить матрицей инцидентности размера pxq, строки которой соответствуют вершинам, а столбцы — ребрам. Для неориентированного графа элементы этой матрицы определяются по следующему правилу: '^-элемент
равен 1, если вершина V| инцидентна ребру eJ, и равен нулю, если V( и 6j не инцидентны. В случае орграфа ненулевой У -элемент равен 1, если V( начальная вершина дуги е', равен -1, если v» конечная вершина дуги е->, и равен нулю,
если V; и J не инцидентны.
Еще одной важной характеристикой графа является понятие связности [55]. Две вершины графа называются связными, если существует маршрут, соединяющий эти вершины. При этом под маршрутом понимается последовательность ребер графа таких, что граничные вершины двух соседних
14
ребер совпадают. Граф, любая пара вершин котррого связна, называют связным графом.
Если граф не является связным, то множество его вершин можно единственным образом разделить на непересекающиеся подмножества, каждое из которых содержит все связанные между собой вершины и вместе с инцидентными им ребрами образует связный подграф.
Если существует такая вершина, удаление которой превращает связный граф в несвязный, то она называется точкой сочленения. Граф, имеющий хотя бы одну точку сочленения, является разделимым и называется сепарабельным. Он разбивается на блоки, каждый из которых представляет собой максимальный неразделимый подграф.
Таким образом, несвязный подграф представляет собой совокупность отдельных частей (подграфов), называемых компонентами. Каждая такая
компонента иредетавляегея своей матрицей инцидентности yM'-i,2,...,*)^ a общая матрица инцидентности А несвязного графа (при соответствующей группировке его вершин и ребер) имеет блочную диагональную (квазидиагональную) форму [49]:
Ап 0 ... О
О Ап - О
О 0 — А
Понятие «система» связано с соотношениями между входными и выходными величинами. Эти понятия могут быть интерпретированы с помощью структурных схем.
Структурные схемы систем управления можно рассматривать как топологические объекты, и для них можно сформулировать топологические формулы [I]. Однако в математическом отношении структурные схемы менее совершенны, чем графы. В отличие от всех видов ориентированных графов, содержащих только два геометрических образа (узлы (вершины) и ветви), структурные схемы содержат четыре образа: линии, представляющие
15
переменные; прямоугольники, представляющие передаточные функции; кружки, представляющие «действия суммирования (вычитания)» и точки - места разветвления переменных.
Наиболее удобным вариантом представления системы управления является структурный граф.
При структурно-параметрическом синтезе системы в качестве переменных целесообразно вершинам графа ставить в соответствие операторы системы, а дугам - сигналы системы. Такой вид графа называется структурным графом (Орграфом) [3].
Каждая ветвь графа отображает причинно-следственную связь между переменными (вершинами) и изображается ориентированными ветвями.
В соответствии с геометрическими образами структурных схем для С-графа принято определение узлов 1,2 и 3-го рода (рис. 1.1).
Узлами первого рода называются узлы графа, содержащие не менее двух входящих и одну выходящую ветви.
К узлам второго рода относятся узлы С-графа, содержащие одну входящую и не менее двух выходящих ветвей.
Узлами третьего рода называются узлы, содержащие одну входную и одну выходную ветви.
1CL X!
Рис. 1.1. Геометрическое представление узлов: 1, 2, 3-го рода. С помощью введенной классификации узлы произвольной формы можно всегда свести к указанным трем видам. Например, задан сложный узел (рис. 1.2.а); используя метод расщепления узла [1], приводим его к узлам всех трех родов (рис. 1.2.6).
16
1 хб 1 х7 1
а) б)
Рис. 1.2. Преобразование узлов.
Описанное представление узлов позволяет установить правило построения графа по известной структурной схеме системы. В таблице 1.1. указана идентификация элементов структурной схемы с элементами С-графа, где линии структурной схемы соответствует ветвь графа с переменной xi; структурному звену - узел графа с оператором, равным W(S) звена; сумматору -узел 1-го рода; а точке — узел 2-го рода.
Таблица 1.1.
Название величины действия Элемент структурной схемы Элемент С-графа
Переменная (сигнал) х, Xi П
Передаточная функция (оператор) W(S)i W(S)iO
Точка суммирования переменных —^4g) * >
1
Точка ветвления переменных 1 хЗ Г
На рис. 1.3 изображена структурная схема системы управления, и изоморфный ей С-граф на рис. 1.4. Вход и выход системы на графе обозначаются единичным узлом. Кроме того, последовательная цепь звеньев в структурной схеме (рис. 1.3) на фафе (рис. 1.4) разбивается единичным узлом 3-го рода. Узел данного рода вводится для разделения входных и выходных сигналов операторов системы, соединенных последовательно. На рис. 1.5 представлена структурная схема последовательной цепи звеньев. Из рис. 1.5 видно, что,
17
например, сигнал х2 одновременно является выходным для W1(S) и входным для оператора W2(S).
Ws(S)
х,
W,(S)
X4
W2(S)
W,(S)
W6(S)
W7(S)
W,(S)
Xl2
W4(S)
x7 JL x14
X,5
Рис. 1.З. Структурная схема система управления
W5(S)
х8
х9
Хо
Рис. 1.4. Изоморфный системе управления С-граф
Xl
w,(S)
Хг
W3(S)
x4
Рис. 1.5. Структурная схема последовательной цепи звеньев
Изоморфный граф последовательной цепи звеньев изображен на рис. 1.6, где сигнал х2' является выходным для оператора Wi(S), a x2 - входным для W2(S), т.е. сигнал х2 структурной схемы разделен на графе единичным узлом 3-го рода на два: х2' и х2. Вводимые узлы 3-го рода не меняют структурной композиции графа, однако, как будет показано в дальнейшем, необходимы для строгой математической записи уравнения системы. |
