Методы анализа структуры вхождения переменных и их применение для решения больших нелинейных систем уравнений тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

ВВБЩЕНИЕ.

Глава I. О РЕШЕНИЙ СИСТЕМ УРАВНЕНИЙ ЗАДАННОЙ СТРУКТУРЫ.

§1.1. Правила преобразований систем уравнений.

§ 1.2. Случай линейной системы

§ 1.3. Случай нелинейной системы.

Глава 2. РАСЧЁТ ПОТОКОРАСПРЩЕЛЕНШ ЭНЕРГЕТИЧЕСКИХ СИСТЕМ

§ 2.1. Метод расчёта гидравлических цепей большого размера

§ 2.2. Методика расчёта установившихся режимов электрических систем.

Глава 3. АЛГОРИТМЫ И РАСЧЁТЫ.

§ 3.1. Представление систем, алгоритмы нахождения информационных переменных и построения информационного графа.

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

§ 3.3. Алгоритмы расчёта гидравлических и электрических цепей.

Проблема решения систем нелинейных уравнений является одной из основных при расчёте различных технических объектов. При этом за последние годы всё чаще возникает необходимость разработки эффективных методов решения больших систем уравнений. Это обусловлено ростом и укрупнением рассматриваемых объектов, необходимостью комплексного подхода к их расчёту. Кроме того, от эффективности решения систем уравнений зависят многие оптимизационные задачи, где нарастающие размеры системы требуют выработки новых подходов к изучению и реализации решения этих систем [3, 4, 6-8, 18, 23-25, 28, 30, 33-39, 44-46, 51, 52] и др.

Вопросам решения больших систем уравнений уделяется много внимания в работах Д.Д.Вооза, А. Джо ржа, Е.Катхилла, И.Даффа, К.Кеворкяна, Дж.Уилкинсона, Р.Тьюарсона, Дж.Стьюарта, А.Директора, Х.Марковича и многих других [20 , 42 , 47-49, 57-82]. В этих работах в основном изучаются задачи определённого класса и на этой основе делаются теоретические обобщения.

Особый интерес представляют разреженные системы, привлечению внимания к которым способствовала монография Р.Тьюарсона [47].

Изучение больших систем уравнений стало предметом для многих направлений и является составной частью различных теоретических и практических исследований, как оптимизация больших систем, исследование больших энергосистем и т.д. ([18, 26, 56] и т.д.).

Немаловажную роль в развитии интереса к большим системам играют разработки академиков А.И.Тихонова, А.А.Самарского и их учеников в области построения разностных схем, где получаются сильно разреженные системы, имеющие большой порядок [44,45] и др.

Следует отметить успехи, достигнутые у нас в стране по изучению больших систем, особенно в работах по электротехнике (В.А.Венников, Л.А.Крумм, Д.А.Арзамасцев, Х.Ф.Фазшюв, В.С.Ха-чатрян, П.И.Бартоломей, В.И.Ицельчик и многие другие [X, 9, 18, 21, 22, 25, 50, 56]).

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

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

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

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

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

Проделанный анализ не зависит от того, является система линейной или нелинейной и позволяет произвести предварительное распределение памяти ЭВМ как при решении систем линейных уравнений методом Гаусса, так и при решении нелинейных уравнений методом Ньютона, использовавшем метод Гаусса для решения линейных вспомогательных задач.

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

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

Диссертация состоит из введения, трёх глав, заключения, списка литература и приложения.

ЗАКЛЮЧЕНИЕ

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

Перечислим полученные в этом плане результаты диссертации:

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

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

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

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

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

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

7. Приведены оценки заполненности и количества арифметических операций в процессе решения.

8. Разработан модифицированный метод Ньютона, основанный на структурных особенностях преобразованных систем.

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

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

1. Арзамасцев Д.А., Бартоломей П.И., Липес А.В. Расчёт и анализ установившихся режимов больших электрических систем. Изв. ВУЗов СССР. Энергетика. 1974, № 10, 1975, № 1.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. - 536 с.

3. Бахвалов Н.С. Численные методы (в 2-х томах) т.1. - М.: Наука, 1975. - 631 с.

4. Бейко И. В., Бублик Б.Н., Зинько П.Н. Методы и алгоритмы решения задач оптимизации. Киев: Высшая школа, 1983. 513 с.

5. Басакер Р., Саати Г. Конечные графы и сети. М.: Наука, 1974. - 368 с.

6. Васильев Ф.П. Численные методы решения экстремальных задач.-М.: Наука, 1980. 520 с.

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

8. Волков Е.А. Численные методы. М.: Наука, 1982. - 256 с.

9. Венников В.А., Суханов О.А. Кибернетические модели электрических систем. М.: Энергоиздат, 1982. - 328 с.

10. Вартанян A.M. Метод декомпозиции систем алгебраических уравнений большой размерности. В кн.: Тез.докл. П н.-техн.конф. АрмНИИЭ. Ереван, 1979, с.15-17.

11. Вартанян A.M., Хачатрян B.C. Метод декомпозиции и решения систем алгебраических уравнений большой размерности. рукопись деп. в Информэнерго. Материалы XXI н.-техн.конф. ЭНЙНа имени Г.М.Кржижановского. - М.: 1980. - 20 с.

12. Вартанян A.M. Метод нахождения бикомпонентов информационного графа в иерархической зависимости систем большой размерности.-В кн.: Тез.докл.Ш н.-техн.конф.АрмНИИЭ. Ереван,1982,с.90-94.

13. Вартанян A.M. Метод решения систем алгебраических уравнений больших размерностей, связанный с бикомпонентами информационного графа. В кн.: Тез.докл. Ш н.-техн.конф. Арм.НИИЭ. Ереван, 1982, с.84-87.

14. Вартанян A.M., Бадалян A.M. Приведение решения уравнения установившихся режимов к последовательному исследованию уравнений одной неизвестной переменной. В кн.: Тез.докл. Ш н.-техн.конф. АрмНИИЭ. Ереван, 1982, с.80-84.

15. Вартанян A.M. О некоторых подходах к решению больших систем нелинейных уравнений. В кн.: Сборник докладов Ш Всесоюзного симпозиума "Методы решения нелинейных уравнений и задач оптимизации". Таллин, 1984, с.65-66.

16. Вартанян A.M. О решении линейных уравнений электрических систем. Известия ВУЗов СССР. Энергетика, 1984, №6, с.41-44.

17. Вартанян A.M. Метод расчёта гидравлических режимов больших тепловых цепей. Известия АН СССР. Энергетика и Транспорт, 1984, № 4, с.47-54.

18. Горнштейн В.И., Мирошниченко Б.П. Методы оптимизации режимов энергосистем. М.: Энергия, 1981. - 336 с.

19. Деннис Дж.Б. Математическое программирование и электрические цепи. М.: Иностранная литература, 1961. - 215 с.

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

21. Жуков Л.А., Стратан И.П. Установившиеся режимы сложных электрических сетей и систем. М.: Энергия, 1979. - 416 с.

22. Идельчик В. И. Расчёты установившихся режимов электрических систем. Н.: Энергия, 1977. - 188 с.

23. Калиткин Н.Н. Численные методы. М.: Наука, 1978, - 512 с.

24. Крылов В.И., Бабков В.В., Монастырев П.И. Вычислительные методы (в 2-х томах) т.1. - М.: Наука, 1976. - 304 с.

25. Крумм Л.А. Методы оптимизации при управлении электроэнергетическими системами. Новосибирск: Наука, 1981. 317 с.

26. Лэсдон Л. Оптимизация больших систем. М.: Наука, 1975. -431 с.

27. Мальцев А.И. Основы линейной алгебры. М.: Наука, 1975.-400с.

28. Меренков А. П. Математические модели и методы для анализа и оптимального проектирования трубопроводных систем. Автореферат диссертации на соиск. учёной ст. д-ра физ.-мат.наук. Новосибирск, 1974. 34 с.

29. Марчук Г.И. Методы вычислительной математики.- М.: Наука, 1980. 535 с.

30. Математические методы решения экономических задач. Оптимальное планирование и управление. М.: Наука, 1977, 7. - с.

31. Меренков А.П. Дифференцация методов расчёта гидравлических цепей. ЗВурн.вычисл.математики и мат.физики, 1973, 13, № 5, с.1237-1248.

32. Ортега Д., Рейнбольдт В. Итерационные методы решения нелинейных систем уравнений со многими неизвестными. М.: Мир, 1975. - 558 с.

33. Островский A.M. Решение уравнений и систем уравнений. М.: ИЛ, 1963. - 213 с.

34. Полак Э. Численные методы оптимизации. М.: Мир, 1974.-376с.

35. Пшеничный Б.Н. Расчёт энергетических сетей на ЭВМ. Журн. вычисл.математики и мат.физики, 1962, № 5, с.942-947.37,38,39,40,41,42,43,44,45