Григорьева Ольга НиколаевнаФакультет
компьютерных наук и технологий Научный руководитель: Дмитриева Ольга АнатольевнаМатериалы по теме выпускной работы: Об авторе | Биография | Библиотека | Ссылки | Отчет о поиске | | Индивидуальный раздел |
Реферат по теме выпускной работыОптимизационное моделирование динамических систем большой размерностиЦель работы: доказать эффективность использования алгоритмов работы с разреженными матрицами при решении систем обыкновенных дифференциальных уравнений (ОДУ) большой размерности. Для достижения поставленной цели в работе будут решаться следующие задачи:
Актуальность выбранной темы
Динамичность – одна из черт, присущих современной экономике любого уровня, ею нельзя пренебрегать во время планирования движения материальных, финансовых, человеческих и других потоков. Динамический процесс должен быть сбалансированным и оптимальным – это специфика рыночных отношений, в которых предприятие (фирма, компания, отрасль, государство) стремится получить максимальную прибыль или удовлетворить рыночный спрос с учетом ресурсных, временных или иных ограничений, сведя при этом свои затраты к минимуму. Исследованиe этой проблемы определяет необходимость построения экономико-математической модели, поскольку именно путем моделирования можно своевременно определить оптимальный вариант управления экономической системой.[1] Особенностью экономических моделей является большое количество факторов, воздействующих на систему, среди которых необходимо выбрать только наиболее существенные. При этом для оценки динамики экономической системы недостаточно иметь значения различных показателей, нужно иметь информацию об их изменениях. В работе для ее получения будет использоваться решение системы дифференциальных уравнений. Предполагаемая научная новизна работы заключается в повышении эффективности численных методов решения систем ОДУ больших размерностей путем использования упаковочных форматов хранения ненулевых элементов разреженных матриц и применения алгоритмов работы с разреженными матрицами в процессе реализации численных методов решения ОДУ. Планируемые практические результаты: динамическая модель макроэкономики, представленная в виде системы ОДУ, алгоритм анализа ее жесткости, а также алгоритм поиска решения данной системы. Обзор исследований и разработок по теме.
Обзор исследований и разработок по теме в мире
Проблемы моделирования динамических систем в экономике рассматриваются в журнале «Проблемы управления и информатики». Журнал является единственным в Украине периодическим изданием, в течение полувека публикующим работы фундаментального и прикладного характера в широком спектре проблем автоматического управления и информатики. Журнал издается при творческом участии: Украинской Ассоциации по автоматическому управлению, Национального космического агентства Украины, академических и отраслевых научных учреждений, ведущих вузов Украины и стран СНГ, ученых и специалистов стран дальнего зарубежья. Тематические разделы журнала:
Магистры ДонНТУ, которые занимались исследованием проблем, связанных с данамическим моделированием:
Краткое изложение собственных результатов,
имеющихся к моменту завершения работы над авторефератом
Построение макроэкономической модели Одним из способов представления динамических систем больших размерностей является система обыкновенных дифференциальных уравнений следующего вида:  В работе данный вид системы дифференциальных уравнений используется для представления динамической модели макроэкономики, качество которой напрямую зависит от ее мерности, т.е. от количества уравнений, входящих в систему. В тоже время при отборе факторов, оказывающих влияние на скорость изменения каждого конкретного показателя, принимаются во внимание лишь наиболее существенные, поскольку излишняя детализация в этом направлении может привести к снижению качества модели в целом. В работе предложена модель, основывающаяся на следующих предпосылках:
 где ВВП – Валовый внутренний продукт; C- совокупное потребление; G- государственные закупки и расходы; I- совокупный объем инвестиций; Xn- чистый экспорт; Dr- реальный доход населения; i- размер инфляции; r- размер ставки процента; D- количество денег в обороте; N- размер налогообложения населения; Z- размер занятости населения; Dn- номинальный доход населения; c,n – склонность населения к потреблению и накоплению; а –коэффициенты; α - коэффициент, отражающий изменение технологии; γ- коэффициент, отражающий циклические колебания экономики; β – коэффициент, отражающий влияние времени на изменение номинального дохода населения. Поскольку полученная матрица коэффициентов является разреженной, что наглядно представлено в таблице 1 («х» - ненулевой элемент), то для решения полученной системы дифференциальных уравнений будет использована технология работы с подобными матрицами, а также многошаговые неявные методы решения систем дифференциальных уравнений. Такой подход к решению позволит максимизировать скорость получения конечного результата, улучшить его точность и качество, а также минимизировать затраты машинных ресурсов на хранение и обработку пустых элементов матрицы.[10] Таблица 1.- Матрица
коэффициентов системы дифференциальных уравнений.
 Нужно отметить, что модели, наиболее адекватно отображающие макроэкономические изменения, будут учитывать в десятки раз больше показателей, соответственно повысится и степень разреженности матрицы коэффициентов. Таким образом, оптимизационная составляющая работы заключается в поиске решения системы обыкновенных дифференциальных уравнений наилучшим методом, экономящим ресурсы машины. Сама же модель макроэкономической динамики служит для описания поведения экономики. Анализ жесткости полученной системы ОДУ В работе под системой, являющейся жесткой на некотором интервале I=[a,b], будем понимать систему ОДУ с постоянной матрицей А:  .
Для этой системы  где λi – собственные
значения матрицы А. Величина k будет выступать коэффициентом жесткости.
Система будет также считаться жесткой, если она обладает следующими
свойствами:
 . Здесь N- отношение значения производных в пограничном слое к значению производных вне него.[11] Ограниченность явных методов решения систем ОДУ При поисках надежных и эффективных одношаговых методов для жестких задач явные методы Рунге - Кутты исключаются из рассмотрения по двум главным причинам. Первая существенна и для нежестких задач и состоит в том, что вычислительные затраты, измеряемые, в частности, числом вычислений производной, быстро растут с увеличением порядка метода. Вторая причина специфична для жестких задач и связана со свойствами устойчивости этих методов. Что касается порядка точности, то при требовании, чтобы порядок достигал значения p, для явных методов Рунге-Кутты зависимость максимально достижимого порядка точности p и необходимого для этого количества стадий s имеет вид, представленный на рисунке 1.[12]  Рисунок 1. Зависимость максимально достижимого порядка точности p и необходимого для этого количества стадий s
Более того, вывод частных методов более высокого порядка быстро усложняется. «Наивысший порядок, фактически достигнутый для явно построенных методов, равен десяти (книга рекордов Гиннеса,с.333).» [13,с.203]. Получение формул еще более высокого порядка превращается в сложную проблему, трудности растут быстрее, чем по экспоненте, а методы делают управление длиной шага все более и более трудным. [13,с.206]. Таблица 1 показывает, что до p = 4 обеспечивается полное соответствие p и s. Далее начинают работать "Барьеры Батчера", сформулированные им в виде теорем, утверждающих, что: при р>=5 не существует явных методов порядка р при s = p; при p>=7 не существует явных методов Рунге-Кутты порядка р при s = p + 1; при p>=8 не существует явных методов Рунге-Кутты порядка р при s = p + 2. В большинстве случаев, стремясь минимизировать количество вычислительных операций, неэффективно использовать явные методы вместо неявных. Решение дифференциального уравнения или системы уравнений неявным методом обязательно потребует решения уравнения или системы уравнений на каждой итерации, что ведет к увеличению вычислений. Однако при переходе к явным методам для сохранения требуемой точности нужно существенно уменьшить шаг и/или увеличить количество стадий. В итоге, количество вычислений на каждой итерации явного метода существенно превзойдет количество требуемых операций в неявном методе. Вопрос устойчивости связан с применением метода Рунге - Кутты при длине шага h к модельной задаче y’= λy , где λ - постоянное (возможно, комплексное) число. Если hλ = z, то y[n]=P(z)y[n-1], где P(z) - полином степени s (s - число этапов). Поскольку ¦P(z)¦→∞ при ¦z¦→∞, такой метод, очевидно, не может иметь неограниченную область устойчивости. Таким образом, в работе для решения именно жестких задач будут использоваться неявные методы. [12] Сравнение устойчивости некоторых явных и неявных методов решения систем ОДУ Под понятием область устойчивости в работе будем понимать набор точек на комплексной плоскости такой, что даже после большого количества итераций вычисляемое решение остается ограниченным Для явных методов порядка 1-4 функции устойчивости R(z) принимают вид:   , при этом значение С зависит от конкретного
метода. Для данного рисунка С=1/1280.  Рисунок 2 – участки
устойчивости для некоторых явных методов Рунге-Кутты.
На рисунке 2 представлены области устойчивости явных методов Рунге-Кутты порядка 1-6. В каждом случае область устойчивости – площадь, заключенная в соответствующую кривую. Для сравнения устойчивости явных и неявных методов Рунге-Кутты рассмотрим три неявных метода, характеристики которых заданы в таблицах 2 и 3 и 4  Рисунок 3. Участки устойчивости
для некоторых неявных методов Рунге-Кутты
Для этих описанных выше неявных методов функции устойчивости соответственно равны Участки устойчивости показаны на рисунке 3. Для метода 237с, который является методом четвертого порядка, область устойчивости полностью покрывает левую половину плоскости. Метод 237а разделяет свойство явных методов Рунге-Кутты о наличии ограниченного участка устойчивости, тогда как метод 237b имеет неограниченный участок устойчивости, который включает в себя левую полуплоскость. Невозможно разработать явные методы порядка хотя бы 1, которые имеют безграничную область устойчивости. Это происходит из-за того, что R(z) – это всегда полином равный 1+z+O(z^2). Однако этих барьеров не существует для неявных методов Рунге-Кутты. [14] Преодоление проблемы большой размерности и разреженности матрицы коэффициентов. Матрица, имеющая небольшой процент ненулевых элементов, называется разреженной. Практически матрицу размеров nxn можно считать разреженной, если количество ее ненулевых элементов имеет порядок n; скажем, от двух до десяти ненулевых элементов в каждой строке при больших n. Разреженные матрицы, встречаются в задачах линейного программирования, структурного анализа, теории цепей и систем распределения энергии, при численном решении дифференциальных уравнений, в задачах теории графов, генетики, социологии и поведенческих наук, при системном программировании. Каждая из этих задач может содержать уравнения и неравенства, являющиеся частью оптимизационной экономической модели. Поэтому для хранения разреженных матриц больших размерностей в ЭВМ используют упаковочные форматы. Другими словами, хранятся только ненулевые элементы таких матриц вместе с необходимой информацией об их положении в матрице. В работе упаковочный формат хранения будет использован по четырем основным причинам:
Пусть квадратная матрица А порядка n содержит τ ненулевых элементов, причем τ много меньше n^2. Обозначим элемент i-й строки и j-го столбца матрицы через a[i,j]. Для того чтобы хранить в памяти только ненулевые элементы, необходимо запомнить i, j, a[i,j]. Если используется одна ячейка памяти для каждой из этих величин, то для хранения всех ненулевых элементов матрицы A требуется 3*τ ячеек. Очевидно, 3*τ должно быть существенно меньше n^2, чтобы имело смысл тратить на введение упаковки дополнительные усилия и машинное время. Многие алгоритмы, преобразующие матрицу А в какую-либо другую желаемую форму, порождают на различных этапах вычислений дополнительные ненулевые элементы. Поэтому при хранении в упакованной форме должна быть каким-то образом предусмотрена возможность добавления новых ненулевых элементов в различные столбцы (или строки) матрицы А, если в процессе вычислений элементы матрицы изменяются. Идеальным хранением будет такое, при котором минимизируются одновременно и общий объем используемой памяти, и общее затраченное машинное время. Вообще говоря, требования минимума памяти и минимума времени являются несовместными и необходим компромисс. [15] Выводы:
Итак, моделирование динамических процессов в экономике может быть осуществлено при помощи систем ОДУ. При этом возникает проблема устойчивости полученного решения, а также появляется необходимость в оптимизации использования существующих численных алгоритмов путем применения упаковочных форматов хранения разреженных матриц и специальных алгоритмов работы с ними. Литература:
|