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

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

Литература

на русском языке, посвященная разреженным матрицам, пополнилась за последние несколько десятков лет достаточно хорошо [52, 2528, 20, 22, 43, 44, 14, 15, 57, 47]. В каждой из названных выше книг рассматривается лишь какая-нибудь одна задача линейной алгебры, а подчас даже ее специальный случай — спектральный анализ, решение симметричных положительно определенных систем, несимметричные системы с квадратными матрицами и т. п.

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

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

К примеру, известно, что Россия занимает второе место в мире по производству первичного алюминия. Так, при общем объеме мирового производства в 1996 г. — 20 844 тыс. тонн, на долю России приходится 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), выполняемой в Братском государственном техническом университете по направлению «Теория, методы и средства автоматизации систем переработки информации и управления».

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

Настоящие исследования служат основой для дальнейшего развития методики решения больших прямоугольных разреженных систем линейных уравнений и позволяют значительно увеличить объемы математических моделей, включая новую информацию об исследуемом объекте. Теоретические и практические результаты, полученные в работе могут быть использованы при чтении курсов: «математическое моделирование" — «Основы САПР" — «Теория автоматического управления», «Теория алгоритмов».

1.8. Апробация работы.

Основные результаты работы докладывались на межрегиональной научно-технической конференции «Естественные и инженерные науки — развитию регионов» (Братск, БрГТУ, 2002; Братск, БрГТУ, 2003; Братск, БрГТУ, 2004) — на VI всероссийской научно-техническои конференции «Новые информационные технологии» (г. Москва, Московская государственная академия приборостроения и информатики, 2003).

1.9. Публикации I.

По теме диссертации опубликовано 11 работ, в том числе 3 статьи и 8.

ТсЗйСОБ.

1.10. Структура и объем диссертационной работы.

Диссертация состоит из введения, пяти глав, заключения, списка литературы. Объем диссертации составляет 143 страницы основного текста, 32 рисунка, 22 таблицы, 8 приложений.

Список литературы

содержит 68 наименований.

5.5. Выводы.

1. Процесс электролиза алюминия представляет собой взаимосвязь множества параметров. Это процесс, который является сложной многомерной многосвязной системой.

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

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

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

5. На примере синтеза системы управления процессом электролиза алюминия показана работа алгоритма. Полученные результаты полностью совпадают с результатами, ранее полученными Турусовым С. Н. в диссертационной работе [5]. Это подтверждает, что методика работает верно. Легкость алгоритма в понимании, минимальная трудоемкость и возможность использования компактной схемы хранения разреженной матрицы позволяет использовать его в дальнейшем.

ЗАКЛЮЧЕНИЕ

.

К новым полученным результатам можно отнести следующие:

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

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

3. Разработан прямой метод приведения прямоугольной матрицы к форме BDF. Алгоритм имеет малую трудоемкость и легко поддается машинной реализации.

4. Теоретически выведены критерии, позволяющие заблаговременно судить о работе алгоритма по приведению матрицы к форме BDF.

Эти критерии заключаются в следующем:

— Если число ненулевых элементов Nz < (т + п — 2), то матрица приводится к форме BDF.

— Если число ненулевых элементов Nz>(m-2)(n-2) + n, то матрица не приводится к форме BDF. rj, ~. 1 + VAm — 3 «.

5. Теоретически выведен критерии к<—-, который способствует поиску строк, не позволяющих приводить матрицу к форме BDF. Опираясь на этот критерий матрицу можно привести к форме SBBDF.

6. Проведен сравнительный анализ методов Р. Тьюарсона и BDF-метода, основанный на определении временной сложности алгоритмов различными способами. Результаты анализа позволяют утверждать, что BDF-метод работает намного быстрее метода Тьюарсона независимо от размера, формы и структуры матрицы.

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

8. Проведен анализ полученного алгоритма, сравнение с другими алгоритмами по приведению матрицы к специальным формам, дано обоснование его применимости.

9. Проведена апробация разработанных алгоритмов на модели оптимизации процесса получения алюминия, разработанной Турусовым С. Н. Полученные результаты полностью совпадают с результатами, ранее полученными Турусовым С. Н. в диссертационной работе [5], показывая, что данные алгоритмы можно успешно применять в процессе синтеза системы управления сложными многосвязными объектами методом структурных графов.

10. Разработано программное обеспечение для приведения матрицы к форме BDF и расчета дополнительных параметров матрицы.

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