Захист відбудеться 3 червня 2011 р. о 15 ³⁰ годині на засіданні спеціалізованої вченої ради К 76.051.02 у Чернівецькому національному університеті імені Юрія Федьковича за адресою: 58012, м. Чернівці, вул. Університетська, 28, факультет прикладної математики, аудиторія 8.

З дисертацією можна ознайомитись у науковій бібліотеці Чернівецького національного університету імені Юрія Федьковича за адресою: м. Чернівці, вул. Лесі Українки, 23.

Автореферат розіслано 29 квітня 2011 р.

Вчений секретар

спеціалізованої вченої ради Я.Й. Бігун

АНОТАЦІЯ

Семчишин Л.М. Алгоритми комп'ютерної алгебри для розв'язання матричних рівнянь. - Рукопис. матриця числовий коефіцієнт похибка

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.05.02. - математичне моделювання та обчислювальні методи. - Чернівецький національний університет імені Юрія Федьковича, Чернівці, 2011.

У дисертаційній роботі вперше запропоновано і обґрунтовано ефективні алгоритми розв'язування СЛАР з матрицями в моделі Леонтьєва. Розроблено схему зведення СЛАР динамічного варіанту моделі Леонтьєва з матрицями від багатьох змінних до систем з числовими коефіцієнтами спеціального вигляду. Виконано зворотний аналіз похибок заокруглення та аналіз обчислювальної стійкості запропонованих алгоритмів. Одержано аналітичне розвинення невідомих даної розрідженої системи лінійних алгебричних рівнянь у скінченні матричні ланцюгові дроби. Розроблено новий підхід розв'язання кліткових алгоритмів для СЛАР з блочними елементами в моделях Леонтьєва. Розвинуто новий підхід до розв'язання систем лінійних алгебричних рівнянь з -вимірними -матрицями в моделі Леонтьєва. Засобами програмного забезпечення MatLab створено набір інструментальних алгоритмів, які служать для комп'ютерної реалізації динамічних міжгалузевих моделей. Проведено обчислювальні експерименти, що підтверджують ефективність запропонованих обчислювальних схем.

Ключові слова: матриця, блочний алгоритм, модель міжгалузевого балансу (модель Леонтьєва), ланцюговий дріб, кліткові алгоритми, мірні матриці.

АНОТАЦИЯ

Семчишин Л.М. Алгоритмы компьютерной алгебры для решения матричных уравнений. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.05.02. - математическое моделирование и вычислительные методы. - Черновицкий национальный университет имени Юрия Федьковича, Черновцы, 2011.

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

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

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

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

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

Ключевые слова: матрица, блочный алгоритм, модель межотраслевого баланса (модель Леонтьева), ветвящаяся цепная дробь, блочные алгоритмы, мерные матрицы.

ABSTRACT

Semchushun L.M. Algorithms of computer algebra for the matrix equation solution. - Manuscript.

Thesis for a candidate's degree by speciality 01.05.02. - mathematics modelling and calculative methods. - Chernivtsi National University after Yurii Fedkovych, Chernivtsi, 2011.

For the first time the effective algorithms of the computer algebra for the system of linear algebraic equation (SLAE) with Leontyev's matrix generalised model are suggested in the dissertation. The scheme of the Leontyev's matrix model SLAE dynamic version reduction on many variables for the systems with numerical coefficient of the special figuration is worked out. The error round-up inverse and the suggested algorithms calculating stability analysis which certify their high effectiveness is carried out. By means of MatLab software the set of instrumental algorithms which serves for the dynamic inter-branch models computer realization is created. Calculating experiments which confirm the suggested calculating schemes effectiveness is carried out.

Key words: matrix, inter-branch balance model (Leontyev's model), matrix branched continued fraction, block algorithms, moderate matrix.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Обчислювальні методи алгебри є одним з найважливіших складників базового програмного забезпечення сучасних комп'ютерних систем. Це методи, які ґрунтуються на побудові скінченної послідовності дій над скінченною множиною чисел. Використовуючи такі методи, розв'язок математичної задачі отримують у вигляді числового результату. Тепер особливо зросла потреба широкого використання алгоритмів комп'ютерної алгебри для розрахунку й оптимізації економіко-математичних моделей, розв'язання задач лінійного і параметричного програмування, задач хімічної кінетики та синтезу великих електронних схем, задач будівельної механіки та динамічного програмування.

Вагомий внесок у розвиток методів комп'ютерної алгебри та їх застосування в математичному моделюванні зробили В.М. Фаддєєв, Д.К. Фаддєєва, В.М. Кублановська, В.В. Воєводін, Е.Е. Тиртишніков, М.О. Недашковський, І.М. Молчанов, О.М. Хіміч, І.І. Босікова, Ф.О.Сопронюк, О.Я. Ковальчук, M.T. Macclelian, E.H. Вareiss, J.D. Lipson, J. Smit, R.T. Moenk, S. Cabay та інші.

Проте в практичному застосуванні виникають проблеми як числового, так і символьного розв'язання квадратних матричних рівнянь, алгебричних матричних рівнянь довільного порядку. Досліджуючи ті чи інші процеси або явища, використовуючи математичні методи і обчислювальні системи, спочатку будують математичну модель досліджуваного об'єкта, тобто описують об'єкт за допомогою математичних співвідношень (системи лінійних чи нелінійних рівнянь, диференціальних рівнянь тощо). Як результат одержують математичну задачу, яку розв'язати або дуже важко, або неможливо. Тоді побудовану математичну модель дискретизують, тобто перетворюють до такого вигляду, щоб розв'язок можна було знайти (звичайно з певною похибкою) у вигляді числового результату за допомогою послідовності арифметичних і логічних операцій або в аналітичному вигляді. Таке перетворення виконують, застосовуючи обчислювальні методи. Закономірно, що на цьому етапі виникає низка проблем, пов'язаних зі збіжністю алгоритмів, їхньою обчислювальною стійкістю, оцінкою похибки розв'язку і т. д. Реалізація дискретної моделі, як звичайно, відбувається за допомогою ЕОМ. Числовий результат розв'язування дискретної задачі аналізують з метою перевірки адекватності побудованої математичної моделі реальній дійсності. Якщо з'ясується, що математична модель недостатньо відображає реальну дійсність, її уточнюють, і весь процес дослідження повторюється.

Першою моделлю, що описує взаємозв'язок економіки і математики, стала міжгалузева балансова модель В.Леонтьєва.

Питання вивчення міжгалузевих моделей в економіко-математичних дослідженнях актуальне, відповідає на важливі методологічні та змістові питання економічної науки, допомагає оцінити можливості та перспективи використання математичного моделювання в економіці.

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

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

Застосування методів економіко-математичного моделювання дозволяє аналізувати якісно і кількісно складні економічні процеси. Нові методи моделювання, засновані на строгих математичних розв'язаннях економічних завдань із застосуванням виявлених законів економіки виробництва, у поєднанні із сучасною обчислювальною технікою, сприяють створенню високоефективних систем для аналізу стану і науково обґрунтованого прогнозування розвитку економіки підприємств, галузей і країни загалом, дають можливість усвідомлено управляти економічними процесами виробництва.

Побудова та дослідження математичних моделей прикладних задач з використанням методів лінійної алгебри традиційно пов'язані із задачею розв'язання систем лінійних алгебричних рівнянь (СЛАР).

Практичне застосування моделей Леонтьєва ставить до методів розв'язування матричних рівнянь ряд вимог, а саме: робота з матрицями великої розмірності, погана обумовленість та виродженість матриці нормативних коефіцієнтів, цілочислові змінні, що значно звужує можливість застосування відомих числових методів, нечітка інформація про значення нормативних коефіцієнтів, розрідженість матриці нормативних коефіцієнтів тощо.

Недостатня вивченість СЛАР з матрицями від багатьох змінних, які можна застосовувати в узагальнених моделях Леонтьєва, виокремлює задачу пошуку нових ефективних алгоритмів комп'ютерної алгебри як особливо актуальну.

У значній кількості прикладних задач виникає необхідність використання динамічних міжгалузевих моделей в економіці. Тому питання міжгалузевих моделей розглядаються у багатьох публікаціях вітчизняних та зарубіжних вчених. Застосування моделей Леонтьєва набуло широкого практичного значення в різних сферах науки, особливо в економічних дослідженнях та для розв'язування еколого-економічних математичних задач. Використанню міжгалузевих моделей присвячено роботи О.Ф. Волошина, Н.Б. Чорней, В.С. Григорківа, І.М. Ляшенка, М.В. Коробової, А.М. Столяр, М.Інтрилігатора, С.А. Жукова, А.Ф. Кабака, В.І. Кудіна, Р.М. van Dooren, A. Hadjidimos, H.A. van der Vorst.

Дослідження присвячене побудові алгоритмів розв'язання широкого кола систем алгебричних рівнянь у моделях Леонтьєва і застосуванню СЛАР з матрицями.

Для об'єктивного аналізу ефективності розв'язання систем лінійних алгебричних рівнянь у моделях Леонтьєва необхідні розробка та дослідження математичних моделей взаємодії економіки та математики з використанням, зокрема, систем лінійних алгебричних рівнянь з матрицями.

Зважаючи на недостатню ефективність існуючих методів розв'язання СЛАР для міжгалузевої моделі Леонтьєва, актуальне застосування методу послідовного аналізу варіантів, який добре проявив себе для розв'язання багатьох прикладних задач.

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана на кафедрі економічної кібернетики та інформатики Тернопільського національного економічного університету і є складовою частиною досліджень наукової держбюджетної теми "Аналітична теорія гіллястих ланцюгових дробів і її застосування в комп'ютерній алгебрі, диференціальних рівняннях і в моделюванні електронного бізнесу" (номер держреєстрації №0110U001442).

Мета і завдання дослідження. Мета дисертаційної роботи - побудова методів розв'язання окремих видів СЛАР з матрицями в моделях Леонтьєва. Для досягнення мети були поставлені такі задачі:

· розробити стійкі методи розв'язання розріджених СЛАР з блочними елементами. Знайти кількість записів для символьного розв'язання та кількість арифметичних операцій для числової реалізації алгоритму множення матриць. Охарактеризувати складність алгоритму з погляду комп'ютерної алгебри. Провести порівняння отриманого алгоритму та існуючих методів.

· створити алгоритми розв'язування СЛАР з багатовимірними матрицями для динамічної моделі Леонтьєва. Розвинути скінченно-різницевий підхід до розв'язування систем лінійних алгебричних рівнянь із двовимірними матрицями. Дослідити зведення системи лінійних алгебричних рівнянь з вимірними матрицями до системи з числовими елементами та обчислити кількість арифметичних операцій.

· розробити новий підхід до розв'язання кліткових алгоритмів для систем лінійних алгебричних рівнянь з блочними елементами в моделях Леонтьєва. Описати алгоритм для тридіагональної блочної системи лінійних алгебричних рівнянь. Розглянути блочний варіант другого алгоритму відсічних систем, а також провести розрахунок кількості операцій, потрібних для його реалізації.

· визначити умови розв'язності прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях Леонтьєва. Розробити новий підхід до розв'язання СЛАР Леонтьєва із прямокутними матрицями. Створити оптимізаційну модель з матрицями міжгалузевого балансу та запропонувати ефективний обчислювальний метод реалізації цієї моделі.

· запропонувати новий підхід до розв'язання погано обумовлених СЛАР у моделі Леонтьєва. Виконати аналіз складності числової реалізації алгоритму розв'язування СЛАР на ЕОМ. Дослідити обчислювальну стійкість запропонованого алгоритму розв'язання СЛАР у моделі Леонтьєва. Охарактеризувати складність алгоритму та показати його ефективність з погляду комп'ютерної алгебри.

· провести тестування якості запропонованих обчислювальних алгоритмів та відповідних оцінок їх основних характеристик.

Об'єкт дослідження - алгоритми комп'ютерної алгебри для розв'язання матричних рівнянь у моделях Леонтьєва.

Предмет дослідження - алгоритми розв'язання СЛАР з матрицями в узагальнених моделях Леонтьєва.

Методи дослідження. У роботі застосовуються методи математичного моделювання для дослідження моделей міжгалузевого балансу; методи розв'язання СЛАР з матрицями від двох змінних на основі скінченно-різницевого підходу; методи обчислювальної математики для побудови узагальнених та динамічних моделей Леонтьєва; елементи теорії прикладного програмування для побудови пакету програм; методи організації і проведення обчислювальних експериментів числового дослідження систем лінійних алгебричних рівнянь.

Наукова новизна одержаних результатів.

У процесі розв'язання поставлених задач вперше отримані такі наукові результати:

· розвинуто та обґрунтовано матричну модель міжгалузевого балансу, проведено аналіз її статистичних характеристик;

· для підвищення швидкодії програмних засобів розв'язання СЛАР з матрицями в моделях Леонтьєва удосконалено деякі алгоритми, що забезпечують розв'язання систем даного класу;

· для математичного моделювання динамічного варіанту моделі Леонтьєва розроблено методи комп'ютерної алгебри, що розширюють можливості сучасних дослідницьких комп'ютерних технологій;

· розроблено схему зведення СЛАР динамічного варіанту моделі Леонтьєва з матрицями від багатьох змінних до систем з числовими коефіцієнтами спеціального виду ;

· методами зворотного аналізу встановлено обчислювальну стійкість запропонованих алгоритмів до похибок заокруглення, які виникають при реалізації на комп'ютерних обчислювальних системах;

· розроблено комплекс програм для розширення можливостей системи MatLab і підвищення її функціональності з проблем розв'язання задач, які описуються системами лінійних алгебричних рівнянь з матрицями.

Практичне значення отриманих результатів. Розроблено комплекс взаємозв'язаних алгоритмів і програм для комп'ютерного дослідження динамічних об'єктів, що описуються системами лінійних алгебричних рівнянь з матрицями у моделях Леонтьєва. Ці алгоритми суттєво розширюють можливості вказаних комп'ютерних засобів проведення наукових та інженерних розрахунків у динамічних моделях.

Особистий внесок здобувача. Усі результати дисертаційної роботи, винесені на захист, отримані автором самостійно. У роботі [7], яка опублікована спільно з науковим керівником, співавтору належить ідея ефективного методу реалізації динамічної міжгалузевої моделі.

Апробація результатів дисертації. Основні результати дисертаційних досліджень доповідалися на конференціях: XII та XIIІ міжнародні наукові конференції імені академіка М. Кравчука (м. Київ, 15-17 травня 2008 р. та 13-15 травня 2010 р.); ІІ міжнародна наукова конференція "Сучасні проблеми механіки та математики" (м. Львів, 25-29 травня 2008 р.); І міжнародна науково-методична конференція "Математичні методи, моделі та інформаційні технології в економіці" (м. Чернівці, 1-4 квітня 2009 р.); Український математичний конгрес - 2009 (м. Київ, 27-29 серпня 2009 р.).; неодноразово доповідалися на семінарах кафедри економічної кібернетики та інформатики Тернопільського національного економічного університету, на семінарі факультету прикладної математики Чернівецького національного університету ім. Ю. Федьковича і відділу числових методів та комп'ютерного моделювання Інституту кібернетики ім. В.М. Глушкова НАН України.

Публікації. На тему дисертації опубліковано 12 праць, у тому числі 7 статей, з них 5 статей в наукових журналах та збірниках наукових праць, які входять до переліку ВАК України з даної спеціальності, 5 тез доповідей, опублікованих в матеріалах наукових міжнародних конференцій.

Структура та обсяг дисертації. Дисертаційна робота складається зі вступу, п'яти розділів, висновків, списку використаних джерел та кількох додатків. Список використаних джерел містить 146 найменувань і розташований на 14 сторінках. Загальний обсяг дисертації складає 165 сторінок.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність теми дисертації, показано її наукову спрямованість, сформульовано мету роботи та задачі дослідження, які потрібно вирішити для її досягнення, визначено об'єкт, предмет і методи досліджень. Подано коротку характеристику результатів дослідження та кількість публікацій на тему дисертації.

Перший розділ "Аналітичний огляд результатів із розв'язання та застосування матричних рівнянь" присвячено розгляду літературних джерел і результатів за тематикою дисертації. Розглянуто теоретико-числові основи обчислювальних методів на основі теорії СЛАР з матрицями, які модифікують прямі числові методи лінійної алгебри. Викладено відомі наукові результати та підходи до розв'язування систем лінійних алгебричних рівнянь з матрицями. Обґрунтовано вибір подальших напрямів досліджень, пов'язаних з побудовою економічних алгоритмів для розв'язання СЛАР з матрицями в моделях Леонтьєва.

Проведено аналіз можливостей комп'ютерних систем для розв'язання задач із вхідними даними числового характеру. Запропоновано порівняльну характеристику розвитку декількох напрямків і концепцій для виконання символьних перетворень. Проаналізовано методи комп'ютерної алгебри для розв'язання СЛАР.

У другому розділі "Системи лінійних алгебричних рівнянь спеціального виду" розглянуто системи лінійних алгебричних рівнянь спеціального вигляду, в тому числі матричні рівняння, пов'язані з економіко-математичними моделями Леонтьєва.

У підрозділі 2.1. подано теоретико-числові основи матричних обчислень. Підрозділи 2.2. і 2.3 присвячено теорії систем лінійних алгебричних рівнянь з матрицями, елементарним перетворенням для систем з поліноміальними елементами. Східчасті системи розглянуто у підрозділі 2.4. Системам матричних рівнянь, що виникають при використанні економіко-математичних моделей Леонтьєва, присвячено підрозділ 2.5..

Третій розділ "Математичні моделі міжгалузевого балансу" присвячено дослідженню продуктивності моделі міжгалузевого балансу на основі теорії невід'ємних матриць.

У підрозділі 3.1. побудовано матричну модель міжгалузевого балансу виду:

, (1)

де матриця коефіцієнтів прямих матеріальних витрат, вектор-стовпець валової продукції і вектор-стовпець кінцевої продукції.

Користуючись цією моделлю, можна виконувати три види розрахунків, а саме:

ю визначити обсяги кінцевої продукції кожної галузі, задавши в моделі її обсяги валової продукції

де одинична матриця -го порядку;

ю знайти обсяг валової продукції кожної галузі, задавши обсяги кінцевої продукції всіх галузей

де матриця обернена до матриці ;

ю обчислити обсяги кінцевої продукції для деяких галузей і обсяги валової продукції для решти галузей, задавши обсяги валової продукції для деяких галузей, а для решти галузей - обсяги кінцевої продукції .

У підрозділі 3.2 досліджено продуктивність моделі міжгалузевого балансу, яку ще називають моделлю Леонтьєва.

Аналіз моделі Леонтьєва з математичного погляду пов'язаний з теорією невід'ємних матриць. Останні, в свою чергу, поділяють на два класи: розкладні та нерозкладні.

Означення. Невід'ємна матриця

називається розкладною, якщо множину індексів можна розбити на таких дві підмножини: , причому

і

Всі інші невід'ємні матриці називаються нерозкладними. Зазначимо, що підмножини і називають ізольованими. Якщо перенумерувавши індекси так, щоб вони набули вигляду , а , то для матриці це означатиме одночасну перестановку рядків і стовпців. Матрицю за допомогою такої операції можна звести до вигляду:

де і - квадратні матриці.

Нерозкладні матриці мають такі властивості:

ю нерозкладна матриця не може мати ні нульових рядків, ні нульових стовпців;

ю якщо матриця нерозкладна, а вектор , то ;

ю якщо нерозкладна матриця розмірності , то тобто всі елементи матриці додатні;

ю якщо нерозкладна матриця, то для будь-якої пари індексів існує натуральне число для якого , де

ю для того щоб матриця була нерозкладною, необхідно і достатньо, щоб для будь-яких індексів існувала послідовність , така, що

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

У підрозділі 3.3 проведено аналіз статистичних характеристик у моделях міжгалузевого балансу.

Як строгі математичні твердження сформульовано та обґрунтовано результати досліджень:

ТЕОРЕМА 1. Якщо в моделі (1) матриця невід'ємна, нерозкладна і продуктивна, а вектор , то вектор валового випуску буде додатний:

ТЕОРЕМА 2. Нехай в моделі (1) матриця невід'ємна, нерозкладна і продуктивна. Якщо , причому то то

при то

Означення. Еластичністю го валового продукту відносно попиту на й кінцевий продукт називається величина

Очевидно, еластичність дорівнює відношенню граничної ефективності до середньої ефективності.

ТЕОРЕМА 3. Якщо матриця - невід'ємна, нерозкладна і продуктивна, то еластичність будь-якого валового продукту відносно попиту на довільний кінцевий продукт не перевищує одиниці: Якщо ж , то при

У четвертому розділі "Узагальнені матричні моделі Леонтьєва" розроблено ефективні алгоритми для узагальнених моделей Леонтьєва, побудовано матричне рівняння для динамічної моделі Леонтьєва, розв'язано систему лінійних алгебричних рівнянь з вимірними матрицями і показано схему зведення системи алгебричних рівнянь з вимірними матрицями до системи з числовими елементами.

Розглядається система лінійних алгебричних рівнянь, яка є вимірним аналогом системи

(2)

де поліноміальні матриці багатьох змінних. Їх можна подати як матричні поліноми

Розв'язок системи шукається як відношення двох поліномів

(3)

де вектори розмірності скалярні величини.

Система (2) може бути записана у вигляді:

На основі методу невизначених коефіцієнтів для знаходження невідомих та одержана система лінійних алгебричних рівнянь спеціального вигляду з числовими блочними елементами

для визначення невідомих матричних коефіцієнтів та У підрозділі 4.2.4 подано алгоритм розв'язання блочної системи (5) з числовими елементами. Для розв'язання системи (5) використано модифікацію алгоритму схеми розрізання. Для цього система (5) записується у спеціальному вигляді. З цією метою через позначено матрицю, що складається із матриць сума індексів яких задовольняє умову

Тоді отримано матриці які мають такий вигляд:

складається із одного елемента. Матриці

мають розмірність . Наступна матриця

вже має стовпців і

рядків. Аналогічно записуються матриці кожна з яких має по стовпців, а кількість рядків у матриці не перевищує

.

Використавши означення Кронекерового добутку, систему (5) записано у вигляді:

(6)

(7)

де тензорні добутки.

Система розв'язується за алгоритмом схеми розрізання. Для цього попередньо матриця системи (7) розділяється на блоки

де квадратна матриця, розміри якої не перевищують

а прямокутні матриці відповідних розмірів. Використовуючи останні

невідомих системи (7) як параметри, які складаються з останніх компонент вектора можна одержати неоднорідну квадратну систему

порядок якої обмежений число

Отже, пошук невідомих і зводиться до розв'язання двох систем меншого порядку. Вектор визначається із системи

(8)

причому . обчислюються із системи

(9)

Розв'язання отриманої системи вимагає деяких проміжних матричних операцій. Для обчислення добутку потрібно знайти розв'язки систем

(10)

де

Передусім, потрібно розв'язати систему при а решта невідомих визначається за співвідношеннями:

Розв'язки системи (10) при обчислюються за формулами:

(11)

Для знаходження всіх

треба виконати з точністю до головного члена

арифметичних операцій. Обчислення добутків та вимагає виконання

арифметичних дій. Для визначення невідомих із системи

го порядку треба затратити

операцій. Коли використовується алгоритм відсічених систем - Щоб розв'язати систему (10), спочатку треба знайти добуток . Для цього необхідно

операцій, після чого систему можна розв'язати за формулами (10), на що потрібно

дій. Отже, для повної реалізації алгоритму схеми розрізання для системи (10) потрібно виконати

арифметичних операцій на комп'ютері.

П'ятий розділ "Методи комп'ютерної алгебри динамічних варіантів моделі Леонтьєва" присвячено застосуванню методів комп'ютерної алгебри для динамічних варіантів моделі Леонтьєва. Розглянуто числові методи розв'язання розріджених систем лінійних алгебричних рівнянь, кліткові обчислювальні методи розв'язання систем лінійних алгебричних рівнянь, методи розв'язання вироджених і погано обумовлених систем. Проаналізовано можливості використання запропонованих алгоритмів на паралельних обчислювальних системах.

Проведено аналіз обчислювальної стійкості алгоритмів розв'язання систем лінійних алгебричних рівнянь. Охарактеризовано складність алгоритму та показано його ефективність з погляду комп'ютерної алгебри.

У підрозділі 5.3. показано застосування алгоритмів теорії матриць для динамічних матричних моделей Леонтьєва.

Розглядається узагальнена модель Леонтьєва із прямокутними матрицями виду

(12)

де та - відповідно вектори валової й кінцевої продукції, а матриця - матриця коефіцієнтів прямих матеріальних витрат.

Систему (12) можна подати у вигляді

(13)

де матриця розміру , елементи якої поліноми від . Припускається, що значення для і коефіцієнтів многочленів беруться з деякого поля так, що елементи матриці обчислюються для деякого часткового значення , наприклад вектор . Матриця і вектор мають степінь , тобто

.

Розв'язок системи шукається у вигляді частки двох поліномів з невідомими коефіцієнтами.

(14)

де ранг матриці вектори розмірності , а скалярні величини. Тоді для системи (12) можна одержати еквівалентну їй числову систему рівнянь з невідомими і невідомими .

(15)

Даний підхід дозволяє проаналізувати розв'язання прямокутних систем, а також одержувати якісні теоретичні оцінки щодо сумісності, існування і числа розв'язків.

Для розв'язання одержаних систем числових рівнянь (15) можна застосувати кілька обчислювальних алгоритмів.

Схема розрізання. Схематична матриця числової системи може бути подана у вигляді:

(16)

де через позначено квадратні клітки, а через - прямокутні блоки.

Для визначеності вважається, що система (13) складається з рівнянь і має невідомих . І нехай .

Перестановкою стовпців систему (15) можна перетворити так, щоб її матриця набула заповнення

(17)

Загальна стратегія розв'язання цієї системи залежить від її рангу. Найбільш трудомісткий з обчислювального погляду варіант числової системи одержано в припущенні, що всі головні мінори, схематично побудованої матриці, не дорівнюють нулю. Тоді перші невідомих можуть бути виражені через останніх розв'язків системи (14). За зроблених припущень про характер матриці (17) підматриця, утворена блоками , буде невиродженою. Схематично процес перетворення матриці системи подамо у вигляді

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

У підрозділі 5.5. проведені дослідження паралельності описаних алгоритмів розв'язання матричних систем з _матрицями для двох найбільш часто використовуваних моделей - концепції необмеженого паралелізму, а також для комп'ютерів з конкретною архітектурою - багатопроцесорною обчислювальною системою типу MІMD.

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

Для обчислювальних систем класу MІMD за умов обмеженості обчислювальних ресурсів і технічних можливостей проведені дослідження ефективності розпаралелювання алгоритмів розв'язання матричних систем з матрицями для ланцюгового способу передачі даних, із застосуванням принципу привілейованої передачі даних, для централізованого принципу передачі даних і для магістральної обробки даних. Встановлено, що для всіх цих способів передачі даних в MIMD-системах розглянуті алгоритми розв'язання систем лінійних алгебричних рівнянь з поліноміальними елементами можна успішно використовувати на багатопроцесорних обчислювальних комплексах. Для процесорних ЕОМ при досягається повна завантаженість усіх процесорів для кожного алгоритму. Характерно, що значення коефіцієнтів ефективності і прискорення практично збігаються для концепції необмеженого паралелізму та для обчислювальних систем з MІMD-архітектурою.

Підрозділ 5.6. присвячено аналізу обчислювальної стійкості алгоритмів розв'язання систем лінійних алгебричних рівнянь з матрицями. Проведено зворотний аналіз похибок заокруглення, тобто встановлено еквівалентні збурення вхідних даних для алгоритму розрізання розв'язання систем лінійних алгебричних рівнянь з матрицями.

Теорема 4. Якщо при реалізація алгоритму схеми розрізання для СЛАР на ЕОМ у режимі плаваючої коми обчислення скалярних добутків проводяться з ординарною точністю, то еквівалентні збурення задовольняють нерівність

Тут обмежена додатна стала, а решта:

і

проміжні матриці в методі розрізання.

Теорема 5. Якщо комп'ютерна реалізація алгоритму схеми розрізання для системи рівнянь у режимі плаваючої коми обчислення скалярних добутків проводяться з подвійною точністю, то еквівалентні збурення задовольняють нерівність

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

У висновках сформульовано основні результати роботи.

У додатках наведено тексти розроблених програм і результати числових експериментів.

ВИСНОВКИ

Дисертаційна робота присвячена побудові алгоритмів комп'ютерної алгебри для розв'язання матричних рівнянь. Розроблені алгоритми можна застосувати в математичному моделюванні для розв'язування прикладних задач економіки, механіки, коли виникає необхідність розв'язувати і досліджувати розв'язки СЛАР з матрицями в моделі Леонтьєва.

Математичні моделі, одержані теоретичні результати та обчислювальні алгоритми, запропоновані в роботі, можна використати для розробки програмних засобів та для подальших досліджень, пов'язаних з розв'язуванням систем лінійних алгебричних рівнянь з матрицями в моделі Леонтьєва, що виникають в багатьох задачах моделювання.

У роботі одержано такі основні результати:

· розроблено та обґрунтовано ефективні алгоритми розв'язання розріджених систем лінійних алгебричних рівнянь із блочними елементами, одержано оцінки складності алгоритмів з погляду комп'ютерної алгебри;

· запропоновано новий підхід із застосуваннях блочних алгоритмів для систем лінійних алгебричних рівнянь у моделях Леонтьєва;

· за допомогою скінченно-різницевого підходу розроблено алгоритм розв'язання систем лінійних алгебричних рівнянь з багатовимірними матрицями зведенням до систем з числовими елементами;

· одержано ефективний підхід до розв'язання системи лінійних алгебричних рівнянь Леонтьєва з прямокутними матрицями, створено оптимізаційну модель з матрицями міжгалузевого балансу;

· проведено дослідження і встановлено широкі можливості для розпаралелювання описаних алгоритмів розв'язання матричних систем з матрицями для двох найбільш часто використовуваних моделей: із концепцією необмеженого паралелізму, а також для комп'ютерів з конкретною архітектурою - багатопроцесорною обчислювальною системою типу MІMD.

· проведений зворотний аналіз похибок заокруглення і встановлено еквівалентні збурення вхідних даних для алгоритму розрізання для розв'язання систем лінійних алгебричних рівнянь з матрицями.

СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Семчишин Л.М. Розв'язання розріджених систем лінійних алгебраїчних рівнянь з блочними елементами / Л.М. Семчишин // Фізико-математичне моделювання та інформаційні технології. Випуск 6. - Львів: Центр математичного моделювання інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України, 2007. - С. 128-135.

2. Семчишин Л.М. Клетковые алгоритмы для систем линейных алгебраических уравнений с блочными элементами в моделях В. Леонтьева / Л.М. Семчишин // Компьютерная математика. Выпуск 2. - Киев, 2009. - С. 24-35.

3. Семчишин Л.М. Розв'язування систем лінійних алгебраїчних рівнянь із багатовимірними матрицями для динамічної моделі Леонтьєва / Л.М. Семчишин // Фізико-математичне моделювання та інформаційні технології. Випуск 10. - Львів: Центр математичного моделювання інституту прикладних проблем механіки і математики ім. Я.С. Підстригача НАН України, 2009. - С. 123-131.

4. Семчишин Л.М. Розв'язування погано обумовлених систем лінійних алгебраїчних рівнянь у моделі Леонтьєва / Л.М. Семчишин // Вісник Тернопільського державного технічного університету. Тернопіль -2009. Том 14. №4 - С. 168-175.

5. Семчишин Л.М. Розв'язування прямокутних та розріджених систем лінійних рівнянь з матрицями в моделях В. Леонтьєва / Л.М. Семчишин // Математичне та комп'ютерне моделювання. Серія: фізико-математичні науки: збірник наукових праць / Кам'янець-Подільський національний університет, Інститут кібернетики імені В.М. Глушкова Національної академії наук України. - Випуск 1. Кам'янець-Подільський, 2009. - С. 121-133.

6. Семчишин Л.М. Динамічні математичні моделі в економіці / Л.М. Семчишин // Вісник Тернопільського національного економічного університету. Випуск 3. - Тернопіль: Економічна думка, 2008. - С. 123-129.

7. Недашковський М.О. Узагальнені динамічні міжгалузеві моделі / М.О. Недашковський, Л.М. Семчишин // Вісник Тернопільського національного економічного університету. Випуск 1. - Тернопіль: Економічна думка, 2009. - С. 169-187.

8. Семчишин Л.М. До розв'язання розріджених систем лінійних алгебраїчних рівнянь / Л.М. Семчишин // Матеріали XII міжнародної наукової конференції імені академіка М. Кравчука, 15-17 травня 2008 року, Київ - 2008.: ТОВ "Задруга", 2008. - С. 786.

9. Семчишин Л.М. Економіко-математичні моделі в багаторівневому управлінні / Л.М. Семчишин // Матеріали ІІ міжнародної наукової конференції імені Я. С. Підстригача, 25-29 травня 2008 року, Львів, 2008. -Т.3. - С. 46-48.

10. Семчишин Л.М. Узагальнена динамічна модель Леонтьєва / Л.М. Семчишин // Матеріали І міжнародної науково-методичної конференції,

1 - 4 квітня 2009 року, - Чернівці: ДрукАрт, 2009. - С. 360-362.

11. Семчишин Л.М. До розв'язання систем лінійних алгебраїчних рівнянь з мірними матрицями / Л.М. Семчишин // м. Київ, Інститут математики НАН України, 27-29 серпня 2009 р. // www.imath.kiev.ua/~congress2009/

12. Семчишин Л.М. Розв'язування систем лінійних алгебраїчних рівнянь із двовимірними матрицями для динамічної моделі Леонтьєва / Л.М. Семчишин // Матеріали XIIІ міжнародної наукової конференції імені академіка М. Кравчука, 13-15 травня 2010 року, Київ: Матеріали конф. Т.2 - К., НТУУ, 2010. - С. 243.

Размещено на Allbest.ru