Григор'єва Ольга МиколаївнаФакультет
комп'ютерних наук і технологій
Спеціальність: Економічна кібернетика Науковий керівник: Дмитрієва Ольга АнатоліївнаМатеріали до теми випускної
роботи: Про автора | Біографія
|
Реферат за темою випускної роботиОптимізаційне моделювання динамічних систем великої розмірностіМета роботи: довести ефективність використання алгоритмів роботи з розрідженими матрицями при рішенні систем звичайних диференціальних рівнянь (ЗДР) великої розмірності Для досягнення поставленої мети в роботі будуть вирішені наступні задачі:
Актуальність обраної теми
Динамічність - одна з рис, властивих сучасній економіці будь-якого рівня, нею неможна зневажати під час планування руху матеріальних, фінансових, людських і інших потоків. Динамічний процес повинен бути збалансоваим та оптимальним - це специфіка ринкових відносин, у яких підприємство (фірма, компанія, галузь, держава) прагне отримувати максимальний прибуток або задовольнити ринковий попит з урахуванням ресурсних, тимчасових або інших обмежень, мінімізуючи при цьому свої витрати. Дослідження цієї проблеми визначає необхідність побудови економіко-математичної моделі, оскільки саме шляхом моделювання можна вчасно обрати оптимальний варіант керування економічною системою.[1] Особливістю економічних моделей є велика кількість факторів, що впливають на систему, тому серед них у роботі будуть обрані тільки найбільш істотні. При цьому для оцінки динаміки економічної системи недостатньо мати значення різних показників, потрібна й інформація про їхні зміни. У роботі для одержання цієї інформації буде використовуватися розв’язок системи диференціальних рівнянь. Передбачувана наукова новизна роботи полягає в підвищенні ефективності чисельних методів рішення систем ЗДР великого розміру шляхом використання компактних форматів зберігання ненульових елементів розріджених матриць і застосування алгоритмів роботи з розрідженими матрицями у процесі реалізації чисельних методів рішення ЗДР. Плановані практичні результати: динамічна модель макроекономіки, представлена у вигляді системи ЗДР, алгоритм аналізу її на твердість, а також алгоритм пошуку розв’язку даної системи. Огляд досліджень і розробок за темою.
Огляд досліджень і розробок за темою в світі.
Проблеми моделювання динамічних систем в економіці розглядаються в журналі "Проблеми керування й інформатики". Журнал є єдиним в Україні періодичним виданням, що протягом напівстоліття публікує роботи фундаментального й прикладного характеру в широкому спектрі проблем автоматичного керування й інформатики. Журнал друкується за творчою участю Української Асоціації по автоматичному керуванню, Національного космічного агентства України, академічних і галузевих наукових установ, провідних вузів України та країн СНД, учених і фахівців країн далекого зарубіжжя. Тематичні розділи журналу:
Магістри ДонНТУ, які займалися дослідженням проблем, пов'язаних з данамическим моделюванням::
Короткий виклад власних результатів,
наявних до моменту завершення роботи над авторефератом
Побудова макроекономічної моделі Одним із засобів подання динамічних систем великих розмірностей є система звичайних диференціальних рівнянь наступного вигляду:  У роботі даний вид системи диференціальних рівнянь використається для подання динамічної моделі макроекономіки, якість якої прямо залежить від її мірності, тобто від кількості рівнянь, що входять до складу системи. У той же час при виборі чинників, що впливають на швидкість зміни кожного конкретного показника, приймаються до уваги лише найбільш істотні, оскільки зайва деталізація в цьому напрямку може призвести до зниження якості моделі в цілому У роботі запропонована модель, що ґрунтується на наступних передумовах:
 де ВВП - Валовий внутрішній продукт; C- сукупне споживання; G- державні закупівлі й витрати; І- сукупний обсяг інвестицій; Xn- чистий експорт; Dr- реальний дохід населення; і- розмір інфляції; 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.2 і 2.3 і 2.4  Малюнок 3. Області стійкості для
деяких неявних методів Рунге-Кутти
Для описаних вище неявних методів функції стійкості відповідно складають Ділянки стійкості показані на малюнку 3. Для методу 237а, що є методом четвертого порядку, область стійкості повністю покриває ліву половину площини. Метод 237а розділяє властивість явних методів Рунге-Кутти про наявність обмеженої ділянки стійкості, тоді як метод 237b має необмежену ділянка стійкості, що містить у собі ліву напівплощину Неможливо розробити явні методи порядку хоча б 1, які мають безмежну область стійкості. Це відбувається через те, що R(z) - це завжди поліном, що дорівнює 1+z+O(z2). Однак цих бар'єрів не існує для неявних методів Рунге-Кутти. [14] Подолання проблеми великої розмірності й розрідженості матриці коефіцієнтів. Матриця, що має невеликий відсоток ненульових елементів, називається розрідженою. Практично матрицю розміру nxn можна вважати розрідженою, якщо кількість її ненульових елементів має порядок n; скажемо, від двох до десяти ненульових елементів у кожному рядку при більших n. Розріджені матриці, зустрічаються в завданнях лінійного програмування, структурного аналізу, теорії ланцюгів і систем розподілу енергії, при чисельному рішенні диференціальних рівнянь, у завданнях теорії графів, генетики, соціології й поведінкових наук, при системному програмуванні. Кожне з цих завдань може містити рівняння й нерівності, що є частиною оптимизационної економічної моделі Тому для зберігання розріджених матриць більших размерностей в ЕОМ використають компактні формати. Інакше кажучи, зберігаються тільки ненульові елементи таких матриць разом з необхідною інформацією про їхнє положення в матриці. У роботі компактна форма зберігання буде використана через чотири наступні причини:
Нехай квадратна матриця А порядку n містить τ ненульових елементів, причому τ < Багато алгоритмів, що перетворюють матрицю А в яку-небудь іншу бажану форму, породжують на різних етапах обчислень додаткові ненульові елементи. Тому при зберіганні в упакованій формі повинна бути якимось образом передбачена можливість додавання нових ненульових елементів у різні стовпці (або рядки) матриці А, якщо в процесі обчислень елементи матриці змінюються. Ідеальним зберіганням буде таке, при якому мінімізуються одночасно й загальний обсяг використовуваної пам'яті, і загальний витрачений машинний час. Загалом кажучи, вимоги мінімуму пам'яті й мінімуму часу є неспільним й необхідним компромісом. [15] Отже, моделювання динамічних процесів в економіці може бути здійснене за допомогою систем ЗДР. При цьому виникає проблема стійкості отриманого рішення, а також з'являється необхідність в оптимізації використання існуючих чисельних алгоритмів шляхом застосування пакувальних форматів зберігання розріджених матриць і спеціальних алгоритмів роботи з ними. Література:
|