Диакоптические методы анализа
Диакоптические методы анализа.
Диакоптические методы (методы разбиения, декомпозиции) основаны на разделении сложной системы уравнений высокой размерности на более простые подсистемы с учетом связей между ними. В результате решение задачи высокой размерности сводится к последовательному (возможно, и параллельному) решению нескольких задач меньшей размерности. Каждая подсистема, в свою очередь, может разбиваться на более простые подсистемы.
Разбиению системы уравнений на подсистемы соответствует разбиение исследуемого объекта на части, что обычно осуществляет инженер-проектировщик, учитывающий при этом функциональную законченность частей и их повторяемость в структуре объекта. Возрастающая сложность анализируемых объектов ставит задачу автоматизации разбиения объекта на части с целью минимизации вычислительных затрат. Задачи можно решать методами эвристического дискретного программирования.
Отличительная особенность диакоптических методов анализа - возможность организации независимых вычислительных процессов отдельно для каждой подсистемы уравнений. Но для получения достоверных результатов нужно учитывать взаимовлияние подсистем. Поэтому в диакоптических методах периодически проводится согласование результатов вычислений в независимых подсистемах. Применительно к моделям макроуровня это согласование может производиться после (или в ходе) выполнения:
а) серии исключений неизвестных при решении ЛАУ методом Гаусса;
б) серии итераций при решении систем нелинейных АУ;
в) серии шагов интегрирования ОДУ.
Соответственно различают три группы диакоптических методов.
Методы раздельных вычислений для решения ЛАУ рассмотрим применительно к объекту, состоящему из трех частей Р1, Р2, Р3 (рис. 1), и в предположении, что для моделирования используется узловой метод.
Рекомендуемые материалы
Рис. 1. Пример проектируемого объекта, разделенного на три части.
Обозначим через V1, V2, V3 векторы потенциалов внутренних узлов соответствующих частей, через и потенциалы граничных узлов, связывающих части между собой (вектор Vгр), через V – вектор потенциалов всех внутренних и граничных узлов, т. е. V=(V1, V2, V3, Vгр).
Математическую модель объекта, показанного на рис. 1, можно представить в виде
(1)
где G1=0, G2=0, G3=0 - подсистемы уравнений для внутренних узлов частей Р1, Р2 и Р3 (каждое i-е уравнение для подсистем определяется как алгебраическая сумма переменных типа потока для всех ветвей, связанных с i-м внутренним узлом). Два последних уравнения - топологические уравнения, описывающие связь подсистем между собой, функции gгр1 и gгр2 образуют вектор-функцию Gгр. Общее число уравнений равно суммарному числу внутренних и граничных узлов.
Обозначим через G вектор-функцию для всех уравнений системы (1), которая примет вид
(2)
Применим для решения системы (2) неявный метод Эйлера, т. е. заменим , а для определения на каждом шаге интегрирования - метод Ньютона, который сводится к решению на каждой k-й итерации системы ЛАУ вида
(3)
где Я - матрица Якоби для системы (2); - значение на k-й итерации.
Вычисляя элементы матрицы Якоби отдельно для каждой подсистемы уравнений из (1), получим
(4)
В случае разбиения объекта на части матрица Якоби для системы (2) будет иметь блочно-диагональный вид с двойным окаймлением. Подобная структура матриц Якоби - типичная для диакоптических методов анализа.
Рассматривая каждую подматрицу как элемент, систему (3) можно эффективно решать методом Гаусса. Предположим, что имеется r подсистем одинаковой размерности q, связанных между собой в s граничных узлах, причем . Прямой ход Гаусса при решении системы ЛАУ с матрицей Якоби вида (4) состоит в преобразовании матрицы Якоби к верхнетреугольному виду, т. е. в обнулении подматриц Ягр1, Ягр2,…, Ягрr, что влечет за собой корректировку только подматрицы Ягр и вектора Gгр по формулам
(5)
для i=1,2,…,r.
Введем обозначения и , причем , а .
Из (5) следует, что вычисления и для каждой подсистемы можно организовать независимо от других подсистем либо последовательно, либо параллельно для многопроцессорных ВС.
При последовательной организации вычислений в ОП ЭВМ для выполнения прямого хода достаточно хранить подматрицы , , , и векторы Gi, и Gгр. Остальные подматрицы и векторы можно хранить во внешней памяти. Тогда требуемые минимальные затраты ОП на выполнение прямого хода составят
При параллельной организации вычислений на многопроцессорных вычислительных системах надо хранить асе подматрицы и векторы:
Обратный ход Гаусса начинается с решения системы ЛАУ относительно граничных узлов, т. е. , где и матрица и вектор, полученные после прямого хода Гаусса.
Последовательно рассчитываются внутренние переменные для каждой подсистемы:
(6)
при i=1, 2, …
Введем обозначения и , причем , а . Из (6) и (5) следует, что векторы и подматрицы можно вычислить для каждой подсистемы независимо от других подсистем в процессе прямого хода. В итоге суммарные затраты ОП ЭВМ составят при выполнении прямого хода
В лекции "28. Лирика Шарля Леконта де Лиля" также много полезной информации.
(7)
(8)
Затраты машинного времени при решении систем ЛАУ рассмотренным методом соизмеримы с затратами при решении системы ЛАУ методами разреженных матриц, т. е. увеличиваются линейно с ростом общего числа уравнений.
Методы раздельных вычислений при решении нелинейных АУ основаны на различной степени нелинейности отдельных подсистем. В общем случае каждая подсистема сходится за различное число итераций Ньютона, поэтому организация раздельных итерационных процессов для подсистем обеспечивает снижение суммарных вычислительных затрат на решение системы типа (1).
Методы раздельного интегрирования ОДУ основаны на различной инерционности отдельных, подсистем, когда в одной части объекта переходные процессы протекают быстро, а в другой - медленно. Эти методы особенно эффективны в тех случаях, когда переменные одной или нескольких подсистем уравнений оказываются в квазистатическом состоянии. Такие подсистемы называются латентными, а вычисления по уравнениям латентных подсистем не производятся на всем интервале квазистатичности, т. е. пока внутренние переменные остаются постоянными (в пределах заданной погрешности).
Таким образом, диакоптические методы анализа обеспечивают ускоренное решение систем ОДУ большой размерности благодаря учету блочной разреженности матриц Якоби таких систем и возможности организации автономных вычислительных процессов для подсистем. Это позволяет проводить анализ сложных объектов при ограниченном объеме ОП ЭВМ, а также выполнять параллельные вычисления в многопроцессорных ВС.