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

ВВЕДЕНИЕ.

1. СИНТЕЗ СИСТЕМЫ УПРАВЛЕНИЯ ПРОЦЕССОМ ЭЛЕКТРОЛИЗА АЛЮМИНИЯ.

1.1. Электролитическое производство алюминия.

1.2. Топологический метод синтеза многосвязных систем управления технологическими процессами.

1.3. Структурная идентификация процесса получения алюминия.

1.4. Выводы.

2. АНАЛИЗ ТЕХНОЛОГИИ ОБРАБОТКИ РАЗРЕЖЕННЫХ МАТРИЦ.

2.1. Предварительные сведения о разреженных матрицах.

2.2. Специальные формы разреженных матриц.

2.3. Эквивалентное матричное преобразование.

2.4. Блочная диагональная форма.

2.5. Блочная треугольная форма.

2.6. Выводы.

3. РАЗРАБОТКА МЕТОДИКИ ПРИВЕДЕНИЯ ПРЯМОУГОЛЬНОЙ РАЗРЕЖЕННОЙ МАТРИЦЫ К БЛОЧНОМУ ДИАГОНАЛЬНОМУ ВИДУ.

3.1. Анализ возможной структуры разреженной матрицы.

3.2. Алгоритм приведения матрицы к форме БОБ.

3.3. Критерии приводимости матрицы к форме БОБ.

3.4. Статистический анализ разреженных матриц.

3.5. Выводы.

4. РАЗРАБОТКА МЕТОДИКИ РЕШЕНИЯ БОЛЬШИХ

РАЗРЕЖЕННЫХ СИСТЕМ ЛИНЕЙНЫХ УРАВНЕНИЙ.

4.1. Выбор метода решения систем линейных уравнений.

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

4.3. Решение СЛАУ в модели управления процессом электролиза алюминия.

4.4. Выводы.

5. МАШИННАЯ РЕАЛИЗАЦИЯ АЛГОРИТМА ПРИВЕДЕНИЯ

МАТРИЦЫ К ФОРМЕ BDF.

5.1. Программное обеспечение, предназначенное для решения систем линейных уравнений

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

5.3. Выводы.

1. ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ 1.1. Актуальность работы

Россия занимает второе место в мире по производству первичного алюминия. Так, при общем объеме мирового производства в 1996г. - 20844 тыс. тонн, на долю России приходится 2871 тыс. тонн, или 13,8% [47].

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

В 1993г. Россия вышла на первое место в мире по экспорту первичного алюминия и к 1996г. ушла далеко вперед, поставляя 2455 тыс. тонн алюминия против 1841 тыс. тонн у Канады и 1129 тыс. тонн у Австралии, занимающих второе и третье места соответственно [48].

Обращает на себя внимание то обстоятельство, что из 11 отечественных производителей, два (Братский и Красноярский) алюминиевых завода являются крупнейшими в мире.

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

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

Политика администрации Братского алюминиевого завода (БрАЗа) направлена на совершенствование уровней механизации и автоматизации. В последнее время на заводе появляются все больше механизмов и машин, облегчающих работу персонала. Это машины по пробивке корки электролизера, машины по загрузке анодной массы, краны с автоматическими манипуляторами и т.п. В области автоматизации идет реорганизация старых систем АСУТП на новые, соответствующие новейшим технологиям.

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

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

Литература на русском языке, посвященная разреженным матрицам, пополнилась за последние несколько десятков лет достаточно хорошо [49,2225,17,19,40,41,13-14,54,44]. В каждой из названных выше книг рассматривается лишь какая-нибудь одна задача линейной алгебры, а подчас даже ее специальный случай - спектральный анализ, решение симметричных положительно определенных систем, несимметричные системы с квадратными матрицами и т.п.

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

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

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

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

1.2. Цель диссертационной работы

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

1.3. Основные задачи работы

К основным задачам диссертационной работы относятся:

1. Разработка алгоритма приведения прямоугольной разреженной матрицы произвольного размера и структуры к блочной диагональной форме (ВБР).

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

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

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

5. Реализация процесса приведения разреженных прямоугольных матриц к форме BDF на ЭВМ.

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. Предложен метод решения системы линейных уравнений с разреженной матрицей, неприводимой к блочной диагональной форме.

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

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

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

1.7. Практическая ценность

Исследования автора выполнялись в рамках госбюджетной тематики «Топологические методы идентификации и синтеза систем управления многосвязными объектами» (код ГРНТИ 27.19.19), выполняемой в Братском государственном техническом университете по направлению «Теория, методы и средства автоматизации систем переработки информации и управления».

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

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

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

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

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

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

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

Диссертация состоит из введения, пяти глав, заключения, списка литературы. Объем диссертации составляет 114 страниц основного текста, 24 рисунка, 7 таблиц, 5 приложений. Список литературы содержит 63 наименования.

5.3. Выводы.

1. Проведен анализ универсальных математических пакетов, таких как: Мар1е, МаШсаё, Ма1:ЬаЬ и Ма&етайса, который показал, что из современных программных средств только МаЛаЬ содержит набор функций, позволяющих эффективно работать с некоторыми классами разреженных матриц, исключая тривиальные операции над нулевыми элементами. К сожалению, это пакет не работает с прямоугольными матрицами, только с квадратными и позволяет приводить квадратные разреженные матрицы к блочному треугольному виду.

2. Проведен анализ специализированных математических пакетов, таких как: БРАЯБРАК, Р04АСЕ/Р (Оксфорд, Великобритания), БТ (г.Люнгбю, Дания), МА28 (Харуэлл, Великобритания), предназначенных для решения несимметричных разреженных систем линейных уравнений. Все эти программы основываются на приведении матрицы к блочной треугольной форме с последующим применением метода Гаусса.

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

4. Разработана программа по приведению прямоугольной разреженной матрицы к форме ВБР, основанная а алгоритме, представленном в третьей главе. Программа обладает всеми необходимыми функциями по эффективной работе с разреженными матрицами: несколькими способами создания матрицы (группы матриц), сохранением результатов, вычислением 26 дополнительных параметров.

ЗАКЛЮЧЕНИЕ

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

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

2. Разработан прямой метод приведения прямоугольной матрицы к форме ВОР. Главным достоинством метода является наименьшая возможная трудоемкость.

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

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

Если число ненулевых элементов № < (т + п - 2), то матрица приводится к форме ВБР.

Если число ненулевых элементов №>(т- 2)(п - 2) + п, то матрица не приводится к форме ВБР.

4. Теоретически выведен и проверен на практике критерий

1 + л/4ллг — 3 ~ г к <---, который способствует поиску строк, не позволяющих приводить матрицу к форме ВБР. Опираясь на этот критерий матрицу можно привести к форме БВВОР.

5. Разработана и проверена на примерах методика решения систем линейных уравнений, основанная на приведении матрицы системы к форме 8ВВБР.

6. Проведена апробация разработанной методики на модели оптимизации процесса получения алюминия, разработанной Турусовым С.Н.

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

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

1. Абрахаме Дж., Каверли Дж. Анализ технических цепей графов. М.: Мир, 1967-468с.

2. Авен О.И., Гурин H.H., Коган Я.А. Оценка качества и оптимизация вычислительных систем. М., Наука, 1982 214с.

3. Алпатов Ю.Н. Синтез систем управления методом структурных графов. Иркутск, ИГУ, 1988. - 183с.

4. Алпатов Ю.Н. Математическое моделирование производственных процессов: Учебное пособие. 2-е изд.,перераб. И доп. - Братск: БрГТУ, 2001. -96с.

5. Алпатов Ю.Н., Турусов Н.С. Синтез системы управления процессом электролиза алюминия.//Труды Братского государственного индустриального института. Материалы XIX научно-технической конференции. В 2 т. Братск БрИИ, 1998.-Т.1.-С.298-301.

6. Апатенок Р.Ф. Элементы линейной алгебры. Мн.: «Вышэйш.школа», 1977.-256с.

7. Анго А. Математика для электро и радиоинженеров. - М.: Наука, 1965.-780с.

8. Баас Р., Фервай М., Гюнтер X. Delphi 4: полное руководство: пер. с нем. К.: Издательская группа BHV, 1999. - 800 с.

9. Беллман Р. Введение в теорию матриц. М.: Наука, 1978. - 367с. Ю.Берж К. Теория графов и ее применение. - М.: Изд-во иностр. лит. 1962-319с.

10. П.Бобровский С. Delphi 5: учебный курс. СПб:Питер, 2000. - 640с.

11. Вавилов A.A., Имаев Д.Х., Родионов В.Д. и др., Машинные методы расчета систем автоматического управления. Л.: ЛГУ, 1981. - 114с.

12. Воеводин В.В. Вычислительные основы линейной алгебры. М.: Наука, 1977.-304с.

13. Н.Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: "Наука",1984

14. Воронов A.A. Основы теории автоматического управления. Особые линейные и нелинейные системы. 2-е изд., перераб. М.: Энергия, 1980. - 312с.

15. Голуб Дж., Ван Лоун Ч. Матричные вычисления. М., Мир, 1999.548с.

16. Джордж А., Лю Дж. Численное решение больших разреженных систем уравнений: пер. с англ. -М.: Мир, 1984. 333с.

17. Деммель Дж. "Вычислительная и линейная алгебра, теория и приложения", пер. с англ. Х.Д. Икрамова. Москва, Мир, 2001. 430 с.

18. Дьяконов B.Matlab: учебный курс. СПб:Питер, 1999. - 592с.

19. Дьяконов Е.Г., Икрамов Х.Д., Шикин Е.В. Линейная алгебра: Теория и решение задач: Учебное пособие. М.: МГУ, 1990. - 160с.

20. Зыков A.A. Основы теории графов. М.: Наука, 1987. - 380с.

21. Икрамов Х.Д. Численные методы для симметричных линейных систем: прямые методы. -М.: Наука, 1988. 157с.23 .Икрамов Х.Д. Численные методы линейной алгебры (Решение линейных уравнений). М.: Знание, 1987. 46с.

22. Икрамов Х.Д. Вычислительные методы линейной алгебры (Решение больших разреженных систем уравнений прямыми методами). М.: Знание, 1989.-48с.

23. Икрамов Х.Д. Разреженные матрицы. М.: сб. "Итоги науки и техники. Математический анализ", т. 20, 1982, с. 179-260.

24. Кадричев В.П., Минцис М.Я. Измерение и оптимизация параметров алюминиевых электролизеров. Челябинск: Металл, 1995. - 136с.

25. Кнут Д. Исскуство программирования, том 1. Основные алгоритмы, 3-е изд.: пер. с англ. М.: «Вильяме», 2001. - 720с.

26. Козлов В.Н., Куприянов В.Е., Заборовский B.C. Вычислительные методы синтеза автоматического управления. Л.: Изд-во ЛГУ, 1989. - 123с.

27. Кормен Т., Лейзерсон, Ривест. Алгоритмы: построение и анализ. М.: МЦНМО, 2000 .-210с.

28. Корн Г., Корн Т. Справочник по математике: для научных работнтков и инженеров. М.: Наука, 1970. - 720с.31 .Красильников Г.А., Самсонов В.В., Тарелкин С.М. Автоматизация инженерно-графических работ. СПб: Питер, 1999. - 256с.

29. Лоусон Ч., Хенсон Р. Численное решение задач методом наименьших квадратов. М.: Наука, 1986. - 50с.

30. Мартынов H.H., Иванов А.П. Matlab 5.x. Вычисления, визуализация, программирование. М.: КУДИЦ-ОБРАЗ, 2000. - 336с.

31. Математический энциклопедический словарь. М.: Советская энциклопедия, 1988.-548с.

32. Минцис М.Я. Автоматическое регулирование алюминиевых электролизеров. М.: Металургия, 1974. - 88с.

33. Минцис М.Я. Исследование серии алюминиевых электролизеров как объекта контроля и управления. Л.: ВАМИ, 1973. - 161с.

34. Молчанов А.Ю. Производство алюминия в электролизерах с верхним токоподводом, Братск: 1993. 146с.

35. Мудров А.Е. Численные методы для ПЭВМ на языках Бейсик, Фортран и Паскаль. Томск: МП «РАСКО», 1991. - 272с.

36. Назаров C.B., Мурин A.B., Барсуков А.Г. Производительность вычислительных систем. Москва, Энергоатомиздат, 1993. 198с.

37. Николаев Е.С., Кучеров А.Б. Разреженные матрицы. Численные методы и алгоритмы. М.: МГУ, 1988. - 111с.

38. Николаев Е.С. Разреженные матрицы. Библиотека программ. М.: МГУ, 1986.- 120с.

39. Ope О. Теория графов. М.: 2-е изд., Наука, 1980. - 336с.

40. Пискунов A.B. Синтез многосвязной системы управления процессом электролиза алюминия методом структурных графов. Братск.: БрГТУ, 1999. -140с.

41. Писсанецки С. Технология разреженных матриц: Пер. с англ. М.: Мир, 1988.-410с.

42. Пьеро Ф., Люкзак Ж.-Л., Рейко Ф., Греке В., Лелэдье Ф.-О., Люкзак X. Руководство по программированию под управлением MS DOS. М.: Радио и связь, 1995.-544 с.

43. Сигорский В.П. Математический аппарат инженера. Киев: Техника, 1975.-766с.

44. Теретьев В.Г., Школьников P.M., Гринберг И.С., Черных А.Е., Зельберг Б.И., Чалых В.И. Производство алюминия. И.: Папирус-Арт, 1998.-350с.

45. Троицкий И.А., Железнов В.А. Металлургия алюминия. М.: Металлургия, 1984.-400с.

46. Тьюарсон Р.Разряженные матрицы Под редакцией Икрамова Х.Д, М.: Мир, 1977.-190с.

47. Форсайт Дж., Малькольм М., Моулер К. Машинные методы математических вычислений. М.: Мир, 1980. - 290с.

48. Форсайт Дж., Моулер К. Численное решение систем линейных алгебраических уравнений. М.: Мир, 1969. - 305с.

49. Харари Ф. Теория графов: Пер. с англ. М.: Мир, 1973. - 254с.

50. Шатихин Л.Г. Структурные матрицы и их применение для исследования системы. М.: 2-е изд., перераб. и доп. - Машиностроение, 1991. -253с.

51. Эстербю Оле, Златев Захарий. Прямые методы для разреженных матриц. Перевод с англ. Икрамов Х.Д. М.: Мир, 1987. - 118с.

52. Алпатов Ю.Н., Шичкина Ю.А. Приведение матрицы к блочному диагональному виду. Труды Братского государственного университета. Том1. - Братск: БрГТУ, 2002. - с. 114-115.

53. Шичкина Ю.А. Разреженные матрицы в синтезе систем управления методом структурных графов. Естественные и инженерные науки развитию регионов: Материалы межрегиональной НТК.- Братск, БрГТУ , 2003 - с. 45-46.

54. Шичкина Ю.А. Разработка прямого метода для приведения матрицы в модели управления процессом получения алюминия к форме BDF.

55. Естественные и инженерные науки развитию регионов: Материалы межрегиональной НТК.- Братск, БрГТУ , 2003 - с. 47-48.

56. Шичкина Ю.А. Применение блочных диагональных матриц при синтезе системы управления. Естественные и инженерные науки развитию регионов: Материалы межрегиональной НТК.- Братск, БрГТУ , 2003 - с. 46-47.

57. Шичкина Ю.А. Разработка методики решения больших разреженных систем линейных алгебраических уравнений (СЛАУ). Естественные и инженерные науки развитию регионов: Материалы межрегиональной НТК.-Братск, БрГТУ , 2003 - с.48-49.

58. Алпатов Ю.Н., Шичкина Ю.А. Программное обеспечение по работе с разреженными матрицами. Естественные и инженерные науки развитию регионов: Материалы межрегиональной НТК.- Братск, БрГТУ , 2003 - с. 39-40.

59. Алпатов Ю.Н., Шичкина Ю.А. Машинная реализация алгоритма, приведения разреженной матрицы к форме ВБР. Естественные и инженерные науки развитию регионов: Материалы межрегиональной НТК.- Братск, БрГТУ, 2003 - с.38-39.

60. Шичкина Ю.А. Критерии применения алгоритма синтеза системы управления для определенного вида матриц // Сб. тр. 6-ой Всероссийской науч.-техн. конф. "Новые информационные технологии" / Под общ. ред. А.П. Хныкина. М.: МГАПИ, 2003. - Т. 1. - с. 136-140.