Прямі методи розв’язування систем лінійних алгебраїчних рівнянь з матрицями

Размещено на http://www.allbest.ru/

Міністерство освіти і науки України

Львівський національний університет імені Івана Франка

УДК 518.25

ПРЯМІ МЕТОДИ РОЗВ'ЯЗУВАННЯ СИСТЕМ ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ З -МАТРИЦЯМИ

Спеціальність: 01.01.07 - обчислювальна математика

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Босікова Інна Іванівна

Львів - 2002

Дисертацією є рукопис.

Робота виконана у Тернопільській академії народного господарства Міністерства освіти і науки України.

Науковий керівник: доктор фізико-математичних наук, професор Недашковський Микола Олександрович, завідувач кафедри автоматизованих систем і програмування Тернопільської академії народного господарства.

Офіційні опоненти: доктор фізико-математичних наук, професор Сявавко Мар'ян Степанович, завідувач кафедри інформаційних технологій Львівського державного аграрного університету,

кандидат фізико-математичних наук, доцент Колодяжний Володимир Максимович, докторант відділу прикладної математики і обчислювальних методів Інституту проблем машинобудування імені А.М.Підгорного НАН України.

Провідна установа: Інститут кібернетики імені В.М.Глушкова НАН України, відділ програмного забеспечення і розв'язування задач.

Захист відбудеться “21”листопада 2002р. о 15.20 год. на засіданні спеціалізованої вченої ради К35.051.07 у Львівському національному університеті імені Івана Франка за адресою: 79000, м. Львів, вул. Університетська, 1, ауд. 377.

З дисертацією можна ознайомитись у Науковій бібліотеці Львівського національного університету імені Івана Франка (м.Львів, вул.Дрогоманова, 5).

Автореферат розісланий “18” жовтня 2002р.

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

спеціалізованої вченої ради М.М.Бокало



АНОТАЦІЯ

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

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

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

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



ABSTRACT

Bosikova I.I. Direct methods of solution of the linear algebraic equations systems with л- matrixes. - Manuscript.

Ph.D. thesis of physico-mathematical sciences on a speciality 01.01.07 - calculus mathematics. - Lviv State University named after Ivan Franko, Lviv, 2002.

In a Ph.D. thesis the linear algebraic equations systems with л- matrixes are considered. The algorithms which are justified generalize direct numerical methods of linear algebra based on nonunitary conversions, for solution of the linear algebraic equations systems with trigonometrical л- matrixes. The translation circuit of the linear algebraic equations systems with trigonometrical and л- matrixes with many variables to numerical systems is developed. The algorithm of the scheme of cut for solution of the obtained numerical systems is constructed. The method of problem solving of parametric programming with the linear and linear-fractional goal functions is developed. The method is based on usage of the linear algebraic equations systems with л- matrixes.

Keywords: л-matrix, trigonometrical polynomials, round-off errors, linear algebraic equations system, scheme of cut, parameter.



АННОТАЦИЯ

Босикова И.И. Прямые методы решения систем линейных алгебраических уравнений с -матрицами. - Рукопись.

Диссертация на соискание учёной степени кандидата физико-математических наук по специальности 01.01.07. - вычислительная математика. - Львовский национальный университет имени Ивана Франко, Львов, 2002.

Диссертация состоит из введения, четырёх разделов, дополнений и списка использованных источников. Список используемых источников включает 118 наименований. Общий объём диссертации 133 страницы.

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

В первом разделе дан обзор литературы по теме диссертационной работы.

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

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

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

Ключевые слова: -матрицы, тригонометрические полиномы, ошибки округления, система линейных алгебраических уравнений, схема розрезания, параметр.



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

Актуальність теми. Однією з важливих складових частин програмного забезпечення ЕОМ є обчислювальні методи алгебри. Обчислювальні методи розв'язування систем лінійних алгебраїчних рівнянь (СЛАР) з числовими коефіцієнтами використовуються дуже давно. В останні десятиліття об'єктом дослідження стали СЛАР з поліноміальними коефіцієнтами. Вони виникають, зокрема, в некласичних задачах для диференціальних рівнянь, в динамічному програмуванні, в алгоритмах оптимізації електронних схем. Вагомий внесок в розвиток методів розв'язання таких систем зробили дослідження В.М.Фаддєєвої, Д.К.Фаддєєва, С.А.Абрамова, В.М.Кублановської, М.О.Недашковського, Г.І.Малашонка M.T.Macclellan, Е.H.Bareiss, J.Lipson, J.Smit, D.Mazykelli, P.T.Moenk, J.Carter, S.Cabay, B.Demzy та інших.

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

В методах матричної лінеарізації, в апроксимаціях Паде постають СЛАР з -матрицями від багатьох змінних. Вивченням цих систем, а також пошуком методів їх розв'язування займалися E.H.Bareiss, D.Mazykelli, S.Cаbay, B.Dеmzy та інші. Випадок, коли -матриця СЛАР залежить тільки від однієї змінної, вивчений достатньо добре. Зокрема, побудовані схеми - аналоги неунітарних алгоритмів лінійної алгебри для випадку алгебри поліномів, схеми використання обчислень в багатомодульній системі лишків, одержано спосіб зведення до систем з числовими коефіцієнтами спеціального виду. Та більшість із перелічених підходів є непридатними для СЛАР з -матрицями від багатьох змінних. В основному це пов'язано з тим, що відповідний допоміжний апарат не розроблений для функцій, що залежать від кількох змінних.

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

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

Параметричне програмування дістало широке практичне застосування в різних сферах науки, особливо в економічних дослідженнях та плануванні. Воно отримало розвиток в працях Ю.Г.Стояна, І.В.Сергієнка, Л.Н.Козерацької, О.О.Ємця, Т.Т.Лєбєдєва, В.А.Ємєлічева, А.А.Кононової, В.К.Лєонтьєва, А.А.Роскладки, А.А.Первозванського, М.П.Вінчерського, Н.Н.Вільямса, I.Adler, R.Monteiro, S.Chanas, D.Kuchta, Z.Nowak та інших. В той же час задачі параметричної оптимізації потребують подальшого вивчення, що робить їх дослідження актуальним.

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

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

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

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

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

3. Розробити алгоритми розв'язування СЛАР з поліноміальними матрицями від багатьох змінних.

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

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

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

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

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

1. Вперше розглянуто СЛАР з тригонометричними -матрицями і отримано методи їх розв'язування. А саме:

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

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

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

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

4. Запропоновано новий підхід до розв'язування задач параметричного програмування, що опирається на теорію СЛАР з -матрицями.

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

На базі побудованих алгоритмів створено пакет прикладних програм, котрий призначений для обчислення:

- розв'язків СЛАР з тригонометричними -матрицями за модифікованим першим алгоритмом відсічених систем;

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

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

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

Апробація результатів дисертації. Результати роботи доповідались на VII-ІХ Міжнародних наукових конференціях імені академіка М.Кравчука (14-16 травня 1998р., 11-14 травня 2000р., 16-19 травня 2002р. м. Київ), на міжнародному симпозіумі “ПОО-ХVII” (28-30 вересня 1999р. м. Київ), на VIII міжнародній Білоруській математичній конференції (19-24 червня 2000р., м. Мінськ), на міжнародній конференції “Моделювання та оптимізація складних систем” (25-28 січня 2001р., м. Київ), на науковому семінарі “Сучасні проблеми обчислювальної математики та її застосування” Львівського національного університету ім. І.Франка (21 грудня 2001р., м. Львів), на науковому семінарі кафедри прикладної математики, інформатики та математичного моделювання Полтавського національного технічного університету ім. Ю.Кондратюка (15 квітня 2002р., м.Полтава), на науковому семінарі кафедри інформаційних технологій Львівського національного аграрного університету (23 квітня 2002р., м.Львів), на міжнародній конференції з управління “Автоматика 2002” (16-20 вересня 2002р., м.Донецьк).

Публікації. За матеріалами проведених досліджень опубліковано 11 статей та тез наукових конференцій: 5 статей - у виданнях з переліку, затвердженого ВАК України, 1 стаття - у збірнику наукових праць інституту кібернетики ім. В.М.Глушкова, 5 - тези наукових конференцій.

Структура дисертації. Дисертація складається зі вступу, чотирьох розділів, які розбиті на підрозділи, висновків, додатків та списку використаних джерел. Список використаних джерел займає 12 сторінок і включає 118 найменувань. Загальний обсяг дисертації - 133 сторінки.

ЗМІСТ РОБОТИ

У вступі обґрунтовано актуальність вибраної теми, визначена мета і задачі дослідження, розкрита наукова новизна та практичне значення.

У першому розділі подано огляд літератури, описано стан розвитку методів пошуку розв'язків СЛАР з -матрицями, обґрунтовано актуальність теми дисертаційної роботи.

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

-матриця

називається регулярною, якщо .

У другому розділі розглядаються методи розв'язування СЛАР з тригонометричними -матрицями.

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

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



, (1)

де - регулярна матриця розмірності nn, - вектор порядку n. Елементами і є тригонометричні многочлени від змінної степеня l.

М.О.Недашковським вперше алгоритми відсічених систем були розроблені для розв'язування СЛАР з числовими коефіцієнтами. Позначимо через визначник, елементи якого знаходяться на перетині рядків 1,2, ..., s, ..., k і стовпців 1,2,..., р,..., k. Нехай для системи (1) відомі розв'язки усіх відсічених систем розміру k-1 включно. Тоді невідомі для СЛАР розміру обчислюються за рекурентними співвідношеннями:

(2)

(3)

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

Теорема 2.1. Якщо в процесі реалізації алгоритму (2)-(3) розв'язування СЛАР (1) всі мінори, що стоять на головній діагоналі, - ненульові, то та тригонометричні многочлени є дільниками тригонометричних многочленів:

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

Розроблено також модифікації другого алгоритму відсічених систем і методу оптимального виключення, отримано аналог методу Жордана та модифіковану схему методу обрамлення. Доведено результат загального характеру, який дає можливість уникати зростання степеня елементів при розв'язуванні системи (1) за алгоритмами, що узагальнюють прямі числові методи лінійної алгебри, основані на неунітарних перетвореннях.

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

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

Теорема 2.3. Нехай для обробки деякого масиву вхiдних даних використовується алгоритм , який складається з етапiв . Якщо результатом обробки масиву А за машинним алгоритмом є масив то реалiзацiї алгоритму на ЕОМ вiдповiдають збурення масиву А вхiдних даних:

Оцінка має місце для довільної норми матриць.

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

, .

Теорема 2.5. Якщо при реалізації модифікованого першого алгоритму відсічених систем для СЛАР (1) на ЕОМ у режимі плаваючої коми застосовується режим обчислення скалярних добутків з подвійною точністю, то еквівалентні збурення задовольняють нерівності:

, .

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



n[2(ln+l)+1] рівнянь з

(n+1)(2ln+1) невідомими.

Теорема 2.6. Якщо матриця вихідної системи (1) регулярна, і хоча б одна із матриць

,

то матриця системи (4) є матрицею повного рангу.

Для розв'язування системи (4) розроблено алгоритми схеми розрізання та її прискореної версії. За схемою розрізання матрицю системи (4) розрізають на чотири блоки: D₁₁ - квадратна матриця розмірності (2nl+1)n(2nl+1)n, D₁₂, D₂₁, D₂₂ - прямокутні матриці. За умовою . Цього достатньо, щоб . Розглядаючи як параметр, можна записати неоднорідну систему:

.

Параметр вона містить лише в останніх 2l+1 компонентах вектора В₂, а її розв'язки дають параметричне сімейство розв'язків заданої системи (4). Пошук невідомих Y i Z здійснюється за два кроки. Із матричної системи рівнянь:

(5)

визначається вектор Z. Потім вектор Y обчислюється із матричної системи рівнянь:



. (6)

На реалізацію алгоритму схеми розрізання для системи (4) потрібно виконати

4l²n³+O(2nl)

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

O(2nl)+8n³llog₂(2l+1)+8n²llog₂n(2l+1)

мультиплікативних та

O(2nl)+16n³llog₂(2l+1)+16n²l log₂n(2l+1)

адитивних операцій. Для великих значень n i l швидка версія схеми розрізання значно ефективніша у порівнянні з основною схемою.

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

, .



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

, .

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

У підрозділі 3.1 розглядаються системи

, (7)

де A(x, y) - квадратна матриця розмірності nn, B(x, y) - вектор порядку n. Елементами A(x, y) і B(x, y) є поліноми степеня m, що залежать від рівновіддалених на x і y координат точок заданої прямокутної області. Z(x, y) - вектор .

В.П.Боюном був виявлений зв'язок між елементами в рядку та між рядками матриці у випадку, коли елементами матриці a_ji є квадратні многочлени. Нетривіальним узагальненням цього результату, отримано рекурентні формули для обчислення елементів довільного рядка матриці A(x,y) системи (7).



З урахуванням (9), отримано формулу для обчислення елементів j-го рядка матриці A(x, y) системи (7):

(10)

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

Теорема 3.1. Якщо система (3.1) має порядок n>m+1, то її невідомі

лінійно виражаються через невідомі z_m+2, z_m+3, ..., z_n .

Твердження. 3.2. Система виду (7) порядку n=m+1 має єдиний розв'язок.

Встановлено, що для отримання розв'язку системи виду (7) немає необхідності обчислювати елементи матриці A(x, y). Достатньо знайти коефіцієнти при різницях , що значно зменшує об'єм обчислень.

У підрозділі 3.2 розглядаються СЛАР

, (11)

де A(₁,₂,…,_m) - регулярна матриця розмірності nn, B(₁,₂,…,_m), X(₁,₂,…,_m) - вектори порядку n. Елементами A(₁,₂,…,_m) і B(₁,₂,…,_m) є многочлени степеня l від .

Розроблено схему зведення СЛАР (11) до системи з числовими коефіцієнтами, максимальна кількість рівнянь в якій -

.

Максимальна кількість невідомих -

Її розв'язок пропонується шукати за алгоритмом схеми розрізання. Для цього достатньо записати її у спеціальному вигляді. Позначається через A_r - матриця, що складається із матриць , для яких

.

Тоді система з числовими коефіцієнтами приймає вигляд:

, (12)

де - прямі добутки.

Теорема 3.3 Якщо матриця вихідної системи (11) регулярна, і хоча б одна із матриць , то матриця системи (12) є матрицею повного рангу.

Система (12) розв'язується за алгоритмом схеми розрізання, на реалізацію якого потрібно виконати



+

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

Четвертий розділ присвячений застосуванню теорії СЛАР з -матрицями до розв'язування задач параметричного програмування.

В підрозділі 4.1 розглядається задача:

(13)

, (14)

, , (15)

де і коефіцієнти лінійних форм беруться з поля дійсних чисел R.

Запропоновано алгоритм її розв'язування:

1. Знаходять множину розв'язків системи (14), як СЛАР з -матрицями.

2. Визначають множину значень параметра , для яких Х() 0.

3. На кожному допустимому інтервалі зміни знаходять максимум функції Z(). Розглядається випадок, коли матриця системи обмежень (14) є регулярною розмірності nn, - вектор порядку n. Елементи і - лінійні поліноми над полем дійсних чисел R. Коефіцієнти: - задані постійні дійсні числа із [0;1], - параметр, що приймає дійсні значення з інтервалу (0; 1). За таких умов розв'язок системи (14) можна шукати у вигляді ряду:



, (16)

де - вектор порядку n.

Твердження 4.1. Ряд (16), у вигляді якого шукають розв'язок системи (14), збігається при

.

Досліджені умови розв'язуваності задачі (13)-(15), коли матриця системи обмежень (14) є матрицею повного рангу.

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



ВИСНОВКИ

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

Основні результати виконаної роботи:

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

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

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

4. Для усіх побудованих алгоритмів виконано аналіз похибок заокруглення.

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

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

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

8. Теоретичне обгрунтування розроблених методів підтверджується числовими та експериментальними прикладами для модельних та прикладних задач. Отримані числові результати порівнювались з результатами, одержаними іншими методами. В ряді випадків встановлено їх переваги порівняно з відомими процедурами популярних математичних пакетів Maple та Mathematica.



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

1. Босікова І.І. Розв'язання задач параметричного програмування з застосуванням систем алгебраїчних рівнянь з -матрицями: Зб наукових праць. - Київ: Ін-т кібернетики ім. В.М.Глушкова, 1999. - С. 56-60.

2. Босікова І.І. Деякі властивості матриць тригонометричних поліномів // Вісник Львівського університету. Серія прикладна математика та інформатика. - 2000. - Випуск 2. - С.16-25.

3. Босикова И.И., Недашковский Н.А. Прямые методы решения систем линейных алгебраических уравнений с комплексными - матрицами // Кибернетика и системный анализ. - 2000. - № 2. - С. 144-156.

4. Босікова І.І. Аналіз похибок заокруглення схеми розрізання для систем лінійних алгебраїчних рівнянь з -матрицями // Вісник Запорізького державного університету. - 2000. - №2. - С. 11-19.

5. Босикова И.И. Решение систем линейних алгебраических уравнений с двумерными -матрицами // Кибернетика и системный анализ. - 2001. - № 4. - С. 175-179.

6. Босикова И.И. Метод решения систем линейных алгебраических уравнений с m-мерными -матрицами // Кибернетика и системный анализ. - 2002. - № 1. - С. 37-47.

7. Босікова І.І. Розв'язування задач параметричного програмування з застосуванням систем лінійних алгебраїчних рівнянь з -матрицями // Матеріали VII-ої Міжнародної наукової конференції ім. академіка М.Кравчука (14-16 травня 1998р., Київ)/ К.: НТУУ(КПІ). - 1998. - С.65.

8. Босікова І.І. Скінченно-різницеві підходи до розв'язання систем лінійних алгебраїчних рівнянь з двовимірними -матрицями // Матеріали VIІI-ої Міжнародної наукової конференції ім. академіка М.Кравчука (1-14 травня 2000р., Київ)/ К.: НТУУ(КПІ). - 2000. - С.245.

9. Босикова И.И. Системы линейных алгебраических уравнений с комплексными элементами и их решение прямыми методами // Тезисы докладов VIII-ой Белорусской математической конференции (19-24 июня 2000г., Минск)/ Минск. - 2000. - Ч. 3. - С. 9.

10. Босікова І.І. Розв'язання задач параметричного програмування з дробовою цільовою функцією із застосуванням систем лінійних алгебраїчних рівнянь з -матрицями // Матеріали Міжнародної конференції “Моделювання та оптимізація складних систем” (25-28 січня 2001р., Київ). - Київ: Видавничо-поліграфічний центр “Київський університет”. - 2001. - Т. 1. - С.16-17.

11. Босікова І.І. Метод розв'язування систем лінійних алгебраїчних рівнянь з багатовимірними - матрицями// Матеріали ІХ-ої Міжнародної наукової конференції ім. академіка М.Кравчука (16-19 травня 2002р., Київ)/ К.: НТУУ(КПІ). - 2002. - С.230.

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

...