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

На правах рукописи ШИЧКИНА Юлия Александровна /у

ТЕХНОЛОГИЯ ОБРАБОТКИ БОЛЬШИХ РАЗРЕЖЕННЫХ МАТРИЦ, ПОЛУЧАЕМЫХ ПРИ СИНТЕЗЕ СИСТЕМ УПРАВЛЕНИЯ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург 2004

Работа выполнена в ГОУВПО "Братский государственный технический университет".

Научный руководитель: доктор технических наук, профессор

Алпатов Юрий Никифорович

Официальные оппоненты, доктор технических наук, профессор

Воробьев Владимир Иванович;

доктор физико-математических наук, профессор Демьянович Юрий Казимирович

Ведущая организация: Балтийский государственный технический

университет (Военмех)

Защита состоится " 8 " декабря 2004 г. в 13 часов на заседании диссертационного совета К 212.223.01 при Санкт-Петербургском государственном архитектурно-строительном университете по адресу: 190005, Санкт-Петербург, ул. 2-я Красноармейская, 4, ауд. 505-А Телефакс: (812) 316-58-72.

С диссертацией можно ознакомиться в библиотеке Санкт-Петербургского государственного архитектурно-строительного университета.

Автореферат разослан октября 2004 г.

Ученый секретарь диссертационного совета --------------В.А. Фролькис

Общая характеристика диссертационной работы

Актуальность исследований

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

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

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

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

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

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

Настоящая диссертационная работа посвящена разработке прямых методов обращения больших разреженных несимметричных матриц. Большое внимание уделяется критериям преобразования таких матриц к некоторым простым формам, ПОЗВОЛЯЮЩИМ ОПТИ иш ири В ЛI (¿^е Решение основанных на них систем линейных урав 'сМй^щуцютЕКА

СПе О»

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

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

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

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

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

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

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

5. Проведение сравнительного анализа методов приведения разреженных матриц к форме BTF.

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

Методы исследования

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

Для проведения расчетов были использованы следующие программные продукты: обработка матриц с целью получения данных для анализа -Delphi 6.0; первичная обработка полученных данных - Excel 97; статистическая обработка данных - Statistica 5.0, MiniTab 32; решение систем линейных уравнений - Matlab 6.1, Maple 7.0.

Научная новизна работы

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

2. Разрзботан алгрритд приведения прямоугольной разреженной мат-

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

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

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

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

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

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

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

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

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

Теоретические и практические результаты, полученные в работе могут быть использованы при чтении курсов: "Математическое моделирование"; "Основы САПР"; "Теория автоматического управления", "Теория алгоритмов".

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

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

Публикации

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

Структура и объем работы

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

Содержание работы

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

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

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

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

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

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

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

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

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

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

Таблица 1.

Определение 1. Блочной диагональной матрицей называется блочная матрица с нулевыми надциагональными и поддиагональными блоками, т.е. для всех подматрицы А^ = 0(рис.1).

А11 0 ■■■ О

о а22- О

А =

О О —А

и

Рис.1. Блочная диагональная матрица

Эквивалентное преобразование матрицы, размера их л, сводится к последовательности элементарных преобразований следующих типов:

1. перестановке произвольных двух строк (столбцов);

2. умножению строки (столбца) на отличный от нуля скаляр;

3. прибавлению к некоторой строке (столбцу) другой строки (столбца), умноженной на скаляр.

Из этих трех типов элементарных преобразований только первое не изменяет первоначальные значения элементов матрицы.

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

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

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

Во второй главе представлен обзор методов оценки трудоемкости алгоритмов.

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

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

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

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

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

1. Время выполнения операторов присваивания, чтения и записи обычно имеет порядок 0(l).

2. Время выполнения последовательности операторов определяется с помощью правила сумм

3. Время вычисления логического выражения обычно имеет порядок (9(1). Время для всей конструкции "if-then-else" состоит из времени вычисления логического выражения и наибольшего из времени, необходимого для выполнения операторов, исполняемых при значениях логического выражения "true" (истина) и при значении "false" (ложь)

4 Время выполнения цикла является суммой времени всех исполняемых итераций цикла, в свою очередь состоящих из времени выполнения операторов тела цикла и времени вычисления условия прекращения цикла (обычно последнее имеет порядок 0(l))

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

Третий способ заключается в подсчете арифметических и логических операций. У этого способа тоже есть недостаток: разные операции выполняются процессором за разное количество тактов.

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

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

В третьей главе сформулирован критерий на количество ненулевых элементов по каждой строке, полезный на практике:

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

Доказательство приводится.

Это условие позволило выработать алгоритм по приведению матрицы

к форме BDF и/или поиску строк, не позволяющих привести матрицу А(тхп), т<п к блочной диагональной форме (в последнем случае матрица сводится к форме SBBDF). Алгоритм заключается в следующем:

1. Маркируем первую строку матрицы А(т х л), m < и, считаем ее главной и заносим ее номер в массив Р = i = \,m;

2. Ищем немаркированные столбцы, соответствующие единицам в главной строке. Маркируем эти столбцы, заносим их номера в массив

Q = jeyj, j = I,« и определяем строки, соответствующие их единицам. Заносим номера этих строк в массив Р = j^j, i=l,m;

3. Берем первую по номеру из массива Р = i = T^m немаркированную строку и возвращаемся к шагу 1.

Если на очередном шаге не останется в массиве А ни одной немаркированной строки, соответствующей единицам, стоящим в столбцах с номерами

из массива Q = je^-j, j = Цг, и при этом размер массива Р будет меньше т, то

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

9

Далее в главе приводится пример преобразования матрицы А размера 6x8 из главы 1. Результат работы этого алгоритма полностью совпадает с результатом, полученным по методу Тьюарсона.

Для данного алгоритма стоит отметить следующее:

1. Данный алгоритм, как и метод Тьюарсона, работает только для разреженных матриц.

2. Неоспоримым достоинством данною метода, как и мелода Тьюар-сона, является применение только первого типа элементарных преобразований.

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

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

Утверждение 1. Если матрица В является квадратной и имеет одинаковое количество ненулевых элементов по строке и столбцу, то матрица А приводится к форме ББР только при наличии подобных строк в матрице В, где матрица В получена из матрицы А путем замены ненулевых элементов единицами.

Доказательство приводится.

Определение 2. Вес ненулевого элемента - сумма количеств ненулевых элементов по строке и столбцу, на пересечении которых он находится.

Утверждение 2. Матрица приводится к ББР, если в этой матрице существует, как минимум, один элемент с весом равным 2.

Доказательство приводится.

Утверждение 3. Матрица А{т х п) при т < (л - 2) приводится к форме 1ШР, если №<(т+п- 2), где - число ненулевых элементов матрицы А.

Доказательство приводится.

Утверждение 4. Матрица, А(тхп) при (т<п) не приводится к форме ВОР, если №?>(«-2)(и - 2) + п

Доказательство приводится.

Если свести полученные результаты на одну числовую ось №, то можно определить границы приводимости разреженной матрицы к ВБР (рис.2).

(т + п-2) (т-2)(п-2) + п №

Рис.2. Границы приводимости разреженной матрицы к ВОР

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

10

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

На компьютере с Процессором Intel Cclcxoxi I GliZ для метода Тьшар-сона и BDF-метода были получены средние значения времени их выполнения для различного размера квадратных матриц (таблица 2).

Таблица!

Время выполнения методов Тьюарсона и BDF-алгоритма для матриц,

различного размера, сек.

и 100 200 300 400 500 600 700 800 900 1000

Метод

Тьюарсона 0 1 2 4 9 15 24 36 53 75

BDF 0 0 0 1 1 2 3 4 4 6

п

Рис.3. Время выполнения алгоритмов на компьютере с процессором Intel Celeron I Ghz

Графики функций времени выполнения программ, составленных по рассматриваемым алгоритмам, представленные на рис.3, еще раз показывают, что BDF-метод является намного более экономичным методом для мат-

риц любого размера.

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

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

Анализ столбцов матрицы показал:

• При переходе от столбца к столбцу количество ненулевых элементов в столбцах убывает.

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

Отношение суммы индексов строк с ненулевыми элементами в конкретном столбце к количеству самих ненулевых элементов в этом столбце

/+и

можно выразить формулой: - индекс столбца, и - число строк

квадратной матрицы. С ростом индекса столбца у (при постоянном значении п) отношение ¿у возрастает. Это свойство отношения 5 • говорит о том,

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

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

1+» . „

лой: г. где г - индекс строки. С ростом индекса строки I (при постоян-

ных значениях пит) отношение возрастает, т.е. строки с большим количеством ненулевых элементов будут стоять впереди строк с меньшим их числом.

Назовем отношения Sj=—_/ = 1 ,п и г-=—-, »' = 1, т - весомго столбца и весом 1-й строки соответственно ( Nj - количество ненулевых элементов в столбце, - количество ненулевых элементов в строке).

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

Если провести аналогичные исследования для случая сортировки строк

12

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

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

1. В матрице А(т,п) найти вес каждой строки г., i = 1, т ;

2. Если все г- находятся в требуемом порядке и нет необходимости их сортировать, то алгоритм приведения закончен, иначе отсортировать строки и перейти к шагу 3.

3. В матрице А(т,п) найти вес каждого столбца Sj, J = 17«;

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

Далее в главе проводится сравнительный анализ разработанного BTF-алгоритма с прямым ходом метода Гаусса. Этот анализ показал, что только при небольших значениях п (п <10) разработанный алгоритм уступает методу Гаусса, а в остальных случаях является более эффективным. На компьютере с процессором Intel Celeron I Ghz для этих двух алгоритмов, метода Гаусса и BTF-метода, были получены средние значения времени их выполнения для различного размера квадратных матриц, которые показали, что в целом по трудоемкости эти два метода близки. Результаты анализа, таблицы и графики функций временной сложности приводятся.

В пятой главе рассмотрены два возможных варианта решения разреженных систем линейных уравнений.

1. Задана система уравнений АХ = В. Матрица А(п) приводится к блочной диагональной форме (BDF). Тогда эту систему уравнений можно представить в следующем виде:

(А

1

о

\ rv fs0

- = 52

/ хк \ л у Л,

о

Систему можно разбить на подсистемы: А^Х^ = В^, А^Х^ = В^, ... ,

= В^ _ Каждая из этих подсистем в большинстве случаев является плотной. Решением всей системы будет совокупность решений подсистем.

2. Задана система уравнений АХ = В. Матрица А не приводится к блочной диагональной форме (ВОР), но ее можно привести к форме БВВОР (односторонне окаймленной блочной диагональной форме):

13

/Г

а

О (X

а

2

X

О

4

к

X

Аш

\

V

Эта система разбивается на подсистемы:

Vi=51

а2х2 = в2

А+1(ЛТ Х2' Xk> ~ В1

'Ш

Последняя подсистема за счет уже найденных из первых к подсистем г неизвестных, сокращается до m-r неизвестных.

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

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

В этой модели решается система линейных однородных уравнений, где матрица системы имеет размер 43x56. Т.к. из 43 строк матрицы системы, 34 строки содержат всего по два ненулевых элемента, а в остальных девяти строках число ненулевых элементов колеблется от 5 до 11, то рациональнее всего ее привести к одной из форм: BDF или SBBDF. В силу связности структурного графа, в соответствии которому была поставлена эта система уравнений, ее нельзя привести к форме BDF.

Количество ненулевых элементов в матрице равно 119. При этом: (т+п-2) =(43+56-2)=97, (т-2)(и-2)+и =(43-2)(56-2)+56=2270. Таким образом, 97 < 119 < 2270, т е данная матрица попадает в интервал неизвестности.

По критерию, выведенному в третьей главе, число ненулевых элемен-

, ^ l+V4»i-3 _ -тов по строке: к <---= 7. Если отделить от матрицы системы строки

с 9,10 и 11-ю ненулевыми элементами, то ее можно привести к форме BDF. Но анализ матрицы показал, что наилучшего результата можно достигнуть, отделив все строки с числом ненулевых элементов больше двух

В результате матрица системы приводится к форме SBBDF, а система разбивается на совокупность подсистем (1)

где Я- часть матрицы подсистемы, состоящая из последних 8 строк матрицы системы

Все неизвестные в каждой из первых 11 подсистем системы (1) равны между собой, т.е.:

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

Такими параметрами являются:

-*14» "*155 "*16> -*4> ^5» -"б» Х7' ■*«» •"77' "*74

Подставляя с помощью математического пакета Мар1е эти параметры в последнюю подсистему получим сокращенную систему уравнений:

ед\ := {ч/4х14-*15+М0*16 + \»38*77+*2 + 1*13 = 0, - *14+и>5*15 + т?36*77+*1 = О, ук9*15-*16+*3 = 0, м-1*14+^6*15+ Л1<1 1*16 + + м>\ 4*4+\Л 7x5 + \v20x6+\v23x7+ч>25х& - х74 + м/34х& 1 = О, \vlxl5+ус28*10+м>29*1 1 - *75 + и/39*93 = 0, м>2х\4+и>8*15 + и>12x16 + +м>15x4+н>18*5 + м>21x6+ы26х$+и>33*74 - *81 +и>27*9+и-30*12 = 0, и>3*14 + И 3*16 + и>16x4 + н>19x5 + и'22*6 + и»24*7 + и>35*81 - *77 = О, >с32*74-*93 = 0}

Если представить эту систему в матричном виде, то получается точно такая же матрица, как и была получена ранее по другой методике Турусовы-м С.Н. Аналогичные результаты получены при решении системы с применением БТР-алгоритма.

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

В заключении сформулированы основные научные положения и результаты, выносимые на защиту.

Основные выводы и рекомендации

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Результаты данной диссертационной работы используются при разработке систем управления теплообразования и для оптимизации систем автоматического регулирования котлоагрегатами БКЗ-320/140 ПТ наТЭЦ-6 ОАО Иркутскэнерго. В частности, предложенный алгоритм приведения разреженной матрицы к блочному диагональному виду с последующим разбиением системы линейных уравнений на подсистемы позволил усовершенствовать процесс решения математической модели работы котлоагрегата, что подтверждено соответствующим актом.

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

Список опубликованных работ по теме диссертации

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

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

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

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

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

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

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

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

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

10. Шичкина ЮА Временная сложность алгоритмов. Естественные и инженерные науки - развитию регионов: Материалы межрегиональной НТК. -Братск, БрГТУ, 2004 - с. 56-57.

11. Шичкина ЮА Разреженные матрицы в базах данных.. Естественные и инженерные науки - развитию регионов: Материалы межрегиональной НТК.- Братск, БрГТУ , 2004 - с.58-59.

Подписано к печати 25.10.04. Формат 60x84 1/16. Бум. офсет. Усл.печл. 1,25. Тираж 100 экз. Заказ л 0 .

Санкт-Петербургский государственный архитектурно-строительный университет. 190005, Санкт-Петербург, 2-я Красноармейская ул., д. 4.

Опечатано на ризографе. 190005, Санкт-Петербург, 2-я Красноармейская ул., д. 5.

»2283 5

ВВЕДЕНИЕ.

ГЛАВА 1 АНАЛИЗ ТЕХНОЛОГИИ ОБРАБОТКИ РАЗРЕЖЕННЫХ

МАТРИЦ В МАТЕМАТИЧЕСКИХ МОДЕЛЯХ СИСТЕМ УПРАВЛЕНИЯ ТЕХНОЛОГИЧЕСКИМИ ПРОЦЕССАМИ.

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

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

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

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

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

1.6. Выводы.

ГЛАВА 2 МЕТОДЫ АНАЛИЗА АЛГОРИТМОВ И ПРОГРАММ.

2.1. Свойства алгоритмов.

2.2. Время выполнения программ.

2.3. Способы вычисления времени выполнения программ.

2.4. Выводы.

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

РАЗРЕЖЕННОЙ МАТРИЦЫ К БЛОЧНОЙ ДИАГОНАЛЬНОЙ ФОРМЕ (BDF).

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

3.2. Алгоритм приведения разреженной матрицы к форме BDF.

3.3. Вывод критериев приводимости матрицы к блочной диагональной форме.

3.4. Сравнительный анализ трудоемкости алгоритма приведения матрицы к форме BDF.

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

3.6. Выводы.

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

BTF).

4.1. Анализ структуры треугольной матрицы.

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

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

4.4. Выводы.

ГЛАВА 5 АПРОБАЦИЯ РАЗРАБОТАННЫХ ЧИСЛЕННЫХ МЕТОДОВ

ПО ПРИВЕДЕНИЮ РАЗРЕЖЕННЫХ МАТРИЦ К ФОРМАМ BTF И

BDF НА МОДЕЛИ УПРАВЛЕНИЯ ПРОЦЕССОМ ЭЛЕКТРОЛИЗА

АЛЮМИНИЯ.

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

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

5.3. Апробация алгоритма по приведению матрицы к форме BDF на модели управления процессом электролиза алюминия.

5.4. Апробация алгоритма по приведению матрицы к форме BTF на модели управления процессом электролиза алюминия.

5.5. Выводы.

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

Литература на русском языке, посвященная разреженным матрицам, пополнилась за последние несколько десятков лет достаточно хорошо [52, 2528, 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), выполняемой в Братском государственном техническом университете по направлению «Теория, методы и средства автоматизации систем переработки информации и управления».

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

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

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 и расчета дополнительных параметров матрицы.

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

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

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

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

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

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

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

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

8. Ахо, Альфред, В.,Хопкрофт, Джон, Ульман, Джеффри, Д. Структуры данных и алгоритмы.: Пер. с англ. М.: Вильяме, 2003. - 384с.

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

10. Ю.Беллман Р. Введение в теорию матриц. М.: Наука, 1978. - 367с.

11. Берж К. Теория графов и ее применение. М.: Изд-во иностр. лит. 1962 -319с.

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

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

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

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

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

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

18. Григорьев В.Л. Микропроцессор i486. Архитектура и программирование (в 4-х книгах). М.: ГРАНАЛ, 1993. - 382с.

19. Гук М., Юров В. Процессоры Pentium III, Athlon и другие. СПб.: Питер, 2000. - 480с.

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

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

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

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

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

25. Икрамов Х.Д. Численные методы для симметричных линейных систем: прямые методы. — М.: Наука, 1988. 157с.

26. Икрамов Х.Д. Численные методы линейной алгебры (Решение линейных уравнений). М.: Знание, 1987. 46с.

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

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

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

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

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

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

33. Корн Г., Корн Т. Справочник по математике: для научных работнтков и инженеров. М.: Наука, 1970. - 720с.

34. Красильников Г.А., Самсонов В.В., Тарелкин С.М. Автоматизация инженерно-графических работ. — СПб: Питер, 1999. 256с.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

66. Шичкина Ю.А. Временная сложность алгоритмов. Естественные и инженерные науки развитию регионов: Материалы межрегиональной НТК.-Братск, БрГТУ , 2004 - с. 56-57.

67. Шичкина Ю.А. Разреженные матрицы в базах данных. Естественные и инженерные науки развитию регионов: Материалы межрегиональной НТК.-Братск, БрГТУ , 2004 - с.58-59.