Методи комп'ютерного дослідження математичних моделей з наближено заданими вихідними даними

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

НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ

ІНСТИТУТ КІБЕРНЕТИКИ ІМЕНІ В.М. ГЛУШКОВА

АВТОРЕФЕРАТ

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

МЕТОДИ КОМПЮТЕРНОГО ДОСЛІДЖЕННЯ МАТЕМАТИЧНИХ МОДЕЛЕЙ З НАБЛИЖЕНО ЗАДАНИМИ ВИХІДНИМИ ДАНИМИ

01.05.02 математичне моделювання та обчислювальні методи

ХІМІЧ ОЛЕКСАНДР МИКОЛАЙОВИЧ

Київ - 2003

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

Робота виконана в Інституті кібернетики ім. В.М. Глушкова НАН України.

Науковий консультант: доктор фізико-математичних наук, професор МОЛЧАНОВ Ігор Миколайович, Інститут кібернетики ім. В.М. Глушкова НАН України, завідувач відділу.

Офіційні опоненти: доктор фізико-математичних наук, професор, член-кореспондент НАН України ЧИКРІЙ Аркадій Олексійович, Інститут кібернетики ім. В.М. Глушкова НАН України, завідувач відділу,

доктор фізико-математичних наук, професор НЕДАШКОВСЬКИЙ Микола Олександрович, Тернопільська Академія народного господарства, завідувач кафедри,

доктор технічних наук, професор, академік НАН України ГРИГОРЕНКО Ярослав Михайлович, Інститут механіки ім. С.П. Тимошенка НАН України, завідувач відділу

Провідна установа: Київський національний університет ім. Т. Шевченка, кафедра методів обчислювального експерименту

Захист відбудеться 26.12.2003 р. о 13 годині на засіданні спеціалізованої вченої ради Д 26.194.02 при Інституті кібернетики ім. В.М. Глушкова НАН України за адресою: 03680, Київ-187, проспект Академіка Глушкова, 40.

З дисертацією можна ознайомитися у науково-технічному архіві інституту.

Автореферат розісланий 22.12.2003 р.

Учений секретар спеціалізованої вченої ради СИНЯВСЬКИЙ В.Ф.

АНОТАЦІЇ

Хіміч О.М. Методи компютерного дослідження математичних моделей з наближено заданими вихідними даними. Рукопис.

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

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

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

Дослідження виконано як для компютерів традиційної архітектури, так і паралельних MIMD-комп'ютерів.

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

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

Химич А.Н. Методы компьютерного исследования математических моделей с приближенно заданными исходными данными. Рукопись.

Диссертация на соискание ученой степени доктора физико-математических наук по специальности 01.05.02 математическое моделирование и вычислительные методы. Институт кибернетики имени В.М. Глушкова НАН Украины, Киев, 2003.

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

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

Исследования выполнены как для компьютеров традиционной архитектуры, так и параллельных MIMD-компьютеров.

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

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

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

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

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

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

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

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

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

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

Khimich О.М. Methods for the computer investigation of mathematical models with approximately given initial data. Manuscript.

Thesis submitted for a Doctor degree in physical and mathematical sciences; the speciality 01.05.02mathematical modelling and computational methods. V.M. Glushkov Institute of Сybernetics, National Academy of Sciences of Ukraine, Kyiv, 2003.

The theoretical foundations are laid and the algorithms are created for computer-based investigation of and solution to mathematical problems with approximately given initial data, to which mathematical modelling of processes, phenomena and systems from various subject areas can be reduced, where solution to linear algebraic problems (linear algebraic systems and algebraic eigenvalue problem) is either an intermediate or a final stage.

The principles of a creation of the intelligent software, intended for investigation of and solution to mathematical problems with approximately given initial data along with estimating a reliability of obtained results, are created.

The investigation is carried out both for the computers with the traditional architecture and parallel MIMD-computers.

The conceptual basis both of the methodology for the computer-based investigation of mathematical models with approximately given initial data and software intended for automatic solving of such problems is the correlated process: investigation of mathematical features of machine models of problems, creation of a method used to obtain an approximate solution depending on revealed characteristics of a machine model as well as machine solution reliability estimation.

Key words: mathematical model, machine model, approximately given initial data, computer methods, error estimate, intelligent software, MIMD-computers, parallel computation algorithms.

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

математичний задача комп'ютерний методологічний

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

Фундаментальні результати в дослідженні різних аспектів розвязування задач лінійної алгебри з наближено заданими вихідними даними відображені в працях Д.К. Фаддєєва, В.М. Фаддєєвої, А.М. Тихонова, В.В. Воєводіна, В.К. Годунова, В.К. Іванова, В.М. Кублановської, Ю.О. Кузнецова , І.М. Молчанова, В.О. Морозова, Х.Д. Ікрамова, М.Ф. Кириченка, Дж. Голуба, Ч. Лоусона, Р. Хенсона, Дж. Форсайта, К. Молера, Дж. Уілкінсона, Дж. Стюарта, Є. Кахана, Б. Парлета та ін.

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

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

Ключовою проблемою процесу чисельного моделювання, що акумулює в собі вплив перерахованих факторів, є проблема вірогідності машинних розвязків. Існування та важливість цієї проблеми підтвержує хоча б той факт, що вже більше двадцяти років в тридцяти країнах світу функціонують робочі групи агенства NAFEMS (National Agency Finite Element Methods and Standards, UK), основне завдання якого забезпечити надійність та безпеку інженерних розрахунків за методом скінченних елементів та повязаних з ним технологій.

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

Принциповий вклад в розробку компютерних технологій та прикладного програмного забезпечення, в тому числі з реалізацією концепції знань, внесли українські учені І.В. Сергієнко, І.І. Ляшко, В.Н. Редько, П.І. Андон, В.С. Дейнека, В.В. Скопецький, І.М. Парасюк, О.Л. Перевозчикова, В.К. Задірака, І.М. Молчанов, О.І. Провотар та ін.

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

Основна проблематика та основні напрямки досліджень, пов'язаних з паралельними обчисленнями, відображені в монографіях Дж. Ортеги, Л. Квіна, І.В. Сергієнка, О.А. Летичевського, І.М. Молчанова, Ю.В. Капітонової, В.В. Воєводіна, Дж. Голуба, Е. Валяха, Б.Б. Нестеренка, В.А. Марчука та ін.

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

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

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана у відповідності з планами наукових досліджень відділу №150 Інституту кібернетики ім. В.М. Глушкова НАН України в рамках науково-дослідницьких тем: 01910013621 "Розробка алгоритмів розв'язування базових задач обчислювальної математики для ЕОМ з трансп'ютерними елементами"; 0195U011940 "Розробка бази знань для дослідження і чисельного розв'язування звичайних диференціальних рівнянь"; 01860045737 Розробити та ввести в експлуатацію ППП для розв'язування на ЄС ЕОМ задач обчислення власних значень та власних векторів матриць з оцінкою вірогідності отримуваних результатів; 0194U000358 Інтелектуальна підтримка процесів постановки та отримання проектних рішень в САПР машинобудування; 0100U002650 Створення методів та алгоритмів дослідження та розв'язування задач обчислювальної математики з наближено заданими вихідними даними на MIMD-комп'ютерах, у виконанні яких автор брав участь як відповідальний виконавець, та в рамках Transform програми співробітництва між урядами України та Німеччини при виконанні науково-дослідницьких проектів 01 IR 601/8 (ISPAR) "Intelligente Umgebung zur Untersuchung und Lцsung wissenschaftlich-technischer Aufgaben auf Parallelrechnern" (Інтелектуальне середовище для дослідження і розв'язування науково-технічних задач на паралельних комп'ютерах); 01 IR 905/3 (ISKON) "Intelligente Software zur Untersuchung und Lцsung von Aufgaben zur Analyse der Festigkeit von Konstruktionen" (Інтелектуальне програмне забезпечення для дослідження і розв'язування задач міцності конструкцій). Наведено номери державної реєстрації у Федеральному міністерстві з освіти, науки, досліджень та технологій Німеччини. Номер державної реєстрації проекту ISKON в Мінекономіки України - № 974.

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

В задачі дослідження входять:

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

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

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

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

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

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

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

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

1. Розроблено математичний апарат дослідження та розв'язування задач лінійної алгебри (системи лінійних алгебраїчних рівнянь, алгебраїчна проблема власних значень) з наближено заданими вихідними даними, в тому числі:

- отримано оцінки збурень нормального псевдорозв'язку для матриць довільного вигляду та рангу для випадку, коли ранг збуреної матриці може змінитися;

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

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

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

- розроблено машинні методи дослідження математичних властивостей алгебраїчної задачі на власні значення;

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

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

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

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

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

4. Розроблено та досліджено методи паралельних обчислень розв'язування задач лінійної алгебри для MIMD-комп'ютерів в тому числі:

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

- запропоновано ефективну циклічно-шарову схему розташування та обробки матриць;

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

5. Розроблено та реалізовано методологічні основи створення інтелектуальних програмних засобів дослідження та розв'язування задач, у тому числі:

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

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

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

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

Алгоритмічне забезпечення, принципи розробки та архітектура інтелектуальних програмних засобів апробовано при створенні програмних засобів для дослідження і розв'язування систем лінійних алгебраїчних рівнянь та алгебраїчної проблеми власних значень LINSYST і EIGSYST для персональних комп'ютерів та LINPAR і EIGPAR для паралельних MIMD - комп'ютерів. Ці програмні засоби пройшли тестування в Центрі з авіакосмічних польотів (DLR) Німеччини при виконанні науково-дослідницьких проектів ISPAR та ISKON.

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

За допомогою LINSYST в інтересах Федерального Центру по суднобудуванню РФ ЦНДІ ім. О.М. Крилова проведено чисельне моделювання пружно-деформівного стану пружного півпростору з двошаровим включенням та досліджено крайові ефекти.

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

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

У роботі [1] дисертант є автором розділу 3 з паралельних алгоритмів розв'язування алгебраїчної проблеми на власні значення, запропоновано циклічно-шарову схему розподілу по процесорах та обробки матриць, яка дозволила уникнути відомого ефекту Гайдна для алгоритмів послідовного виключення невідомих. У роботі [2] запропоновано два паралельних алгоритми для розв'язування симетричної проблеми на власні значення: метод спряжених градієнтів для стрічкових матриць та метод відображення для щільних матриць, досліджено їх ефективність. У роботі [3] розроблено методику програмної реалізації алгоритмів обчислення нормального псевдорозв'язку або його стійких проекцій в умовах наближених вихідних даних. У роботі [5] запропоновано принципи та структура пакету прикладних програм для дослідження та розв'язування алгебраїчної проблеми на власні значення з оцінкою вірогідності отримуваних розв'язків. У роботі [7] розроблено модель спілкування для постановки, дослідження та розв'язування в діалоговому режимі алгебраїчної проблеми на власні значення. У роботі [9] отримано строгі оцінки відносної обчислювальної похибки власних значень узагальненої проблеми на власні значення з додатно визначеними матрицями. У роботі [10] розроблено алгоритми розв'язування алгебраїчної проблеми власних значень для MIMD-комп'ютерів з універсальною системою міжпроцесорних зв'язків. У роботі [11] розроблено схему функціювання бази знань в інтегрованій системі обчислення проектних рішень в системах автоматизації інженерних розрахунків на основі МСЕ. У роботі [14] розроблено комп'ютерні алгоритми для дослідження та розв'язування систем лінійних алгебраїчних рівнянь з наближено заданими вихідними даними та оцінкою вірогідності отриманих результатів. У роботі [15] розроблено принципи створення та архітектуру інтелектуального програмного забезпечення для розв'язування систем лінійних алгебраїчних рівнянь з наближено заданими вихідними даними. У роботі [16] розроблено комп'ютерні методи дослідження математичних властивостей машинних моделей задач на власні значення. У роботі [18] розроблено принципи створення та методологію реалізації інтелектуального інтерфейсу для автоматичного дослідження та розв'язування задач лінійної алгебри. У роботі [19] запропоновано та обгрунтовано алгоритм трьохетапної регуляризації для обчислення нормального псевдорозв'язку з гарантованою точністю системи лінійних алгебраїчних рівнянь з додатно напіввизначеною матрицею у випадку, коли права частина задана наближено. У роботі [20] запропоновано паралельний прототип алгоритму сингулярного розвинення матриць Голуба-Кахана з використанням для паралельної обробки циклічно-шарової схеми та досліджено його ефективність. У роботі [22] отримано оцінки повної похибки розв'язків, обчислених ітераційними методами для систем лінійних алгебраїчних рівнянь з матрицями неповного рангу для випадків, коли збурені й матриця, і права частина. У роботі [23] отримано апріорну оцінку збурення єдиного на підпросторі розв'язку першої основної задачі теорії пружності. У роботі [24] разроблено методологічні основи створення інтелектуального інтерфейсу для дослідження та розв'язування задач розрахунку міцності конструкцій на MIMD-комп'ютерах та математичне забезпечення задач лінійної алгебри з наближено заданими вихідними даними. У роботі [25] проведено чисельне дослідження властивостей дискретної моделі та пружно-деформівного стану півпростору з двошаровим сферичним включенням в залежності від геометричних характеристик включень та фізичних характеристик матеріалів “матриці” та включень. У роботі [26] отримано оцінку для параметра регуляризації та дано оцінку похибки нормального псевдорозв'язку, отриманого методом сингулярного розвинення матриць у випадку, коли збурюються і матриця, і права частина.

Апробація результатів дисертаційної роботи. Основні ідеї, принципи, положення та результати досліджень доповідалися на наукових семінарах та конференціях. Республіканському семінарі Чисельний аналіз Наукової ради з проблеми Кібернетика НАН України (Київ, 1985, 1987, 1988, 1990, 1992, 1994, 1998, 1999); VII Всесоюз. семінарі з комплексів програм математичної фізики (Горький, 1981); VII Всесоюз. семінарі Паралельне програмування та високопродуктивні структури (Київ, 1988); конф. Діалог-Людина-ЕОМ (Свердловськ, 1989); Х Всесоюз. семінарі Паралельне програмування та високопродуктивні системи: методи подання знань в інформаційних технологіях (Уфа, 1990); V Всесоюз. науково-технічній конф. "Однорідні обчислювальні структури та середовища" (Москва, 1991); Міжнар. симпозиумі "Питання оптимізації обчислень" (Київ, 1993, 1997, 1999, 2001); Міжнар. науково-практичній конф. з програмування УкрПРОГР (Київ, 1998, 2000, 2002); Міжнар. конф. "Моделювання та оптимізація складних систем" (Київ, 2001); Українському математичному конгресі (Київ, 2001); Міжнар. конф. "Обчислювальна та прикладна математика" (Київ, 2002); Міжнар. науково-технічній конф. "Искусственный интеллект - 2002" (Таганрог-Донецьк, 2002).

Публікації. Основні результати дисертації опубліковано в 33 наукових працях, у тому числі одна монографія, 25 робіт у наукових фахових виданнях (журналах та збірниках наукових праць), 8 робіт у збірниках праць наукових конференцій.

Структура та обсяг дисертації. Дисертація складається із вступу, сіми розділів, висновків та бібліографічного списку із 294 найменувань. Загальний обсяг 303 сторінки тексту, 27 сторінок списку використаних джерел.

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

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

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

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

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

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

Ах = b, (1)

А R^{m n} , х Rⁿ , b R^m

та система лінійних алгебраїчних рівнянь з наближено заданими вихідними даними (математична модель з наближено заданими вихідними даними)

, . (2)

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

Тут і в подальшому, якщо не обумовлено додатково, використовуються евклідова векторна та підпорядкована їй спектральна матрична норми.

У підрозділі 3.1 розглянуто оцінки спадкової похибки розв'язку для систем з матрицями довільного вигляду та рангу (теореми 3.1-3.7).

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

У пункті 3.1.2 розглядаються алгоритми дослідження коректності та обумовленості машинних моделей задач. Суттєве значення при цьому мають визначення поняття виродженості матриці та рангу матриці в умовах наближених вихідних даних.

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

1.0 + 1.0, де = h^-1(А),

h() < 1.

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

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

Для матриць неповного рангу умова

,

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

_i >, i = 1, 2,…, min(m,n); (_i 0).

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

.

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

Для розвязування некоректно поставлених задач з матрицями довільного вигляду та рангу в пункті 3.2.2 розглянуто метод дискретної регуляризації обчислення наближення до нормального псевдорозвязку. Алгоритм базується на сингулярному розвиненні матриць і дозволяє уникнути формування в явному вигляді матриці А^ТА, обчислення якої в умовах наближених вихідних даних (чи наближених обчислень), як показав Дж. Уілкінсон, може приводити до відозмін математичних властивостей машинної моделі задачі.

Якщо rank= rank, то наближення до нормального псевдорозвязку обчислюється за формулою

u = , (3)

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

Якщо rank>rankА = k, то наближення до нормального псевдорозвязку обчислюється за формулою

u = , (4)

де в матриці відмінні від нуля тільки перші k сингулярних чисел. Оцінки похибок та умови застосувань наближень (3), (4) встановлюють відповідні теореми про збурення нормального псевдорозв'язку.

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

,

,

,

,

,

.

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

Теорема 3.8. Для похибки нормального псевдорозв'язку має місце наступна оцінка:

,

де _k найменше відмінне від нуля власне значення матриці A, _n її максимальне власне значення, х нормальний псевдорозв'язок задачі з точно заданими вихідними даними.

У цьому випадку також вдається уникнути формування А^ТА. Метод особливо ефективний для стрічкових матриць, оскільки обчислення А^ТА, крім усього іншого, псує стрічкову структуру матриці.

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

C = AB, с_ij =

за шістьма алгоритмами.

Використовуючи алгоритм, який в найбільшій мірі відповідає архітектурі комп'ютера і його системному програмному забезпеченню, можна досягти значного прискорення при реалізації алгоритму (наприклад, для n = 1000 на робочій станції HP 433 - більше ніж в 5 раз, на робочій станціїї НР 827 - більше ніж в 15 раз ).

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

На основі цих досліджень у пункті 3.2.5 запропоновано машинні алгоритми основних чисельних методів, що базуються на LL^Т і LU розвиненнях матриць.

У підрозділі 3.3 для систем з матрицями довільного вигляду та рангу отримано оцінки повної похибки машинних розвязків (теореми 3.9-3.15). Оцінки повної похибки враховують як спадкову похибку внаслідок похибки вихідних даних, так і обчислювальну похибку внаслідок наближеного способу визначення розвязку задачі. Обчислювальна похибка може бути наслідком як наближеного методу обчислення розвязку, так і похибки внаслідок неточності виконання арифметичних операцій на компютері. Вектор невязки враховує загальний ефект впливу цих похибок.

Теорема 3.9. Припустимо, що 1, rank= rank=k і нехай Im ().

Тоді має місце оцінка

,

де b_k проекція правої частини задачі (1) на головний лівий сингулярний підпростір матриці А, h = h(A) = - число обумовленості матриці A, А⁺ псевдообернена матриця Мура-Пенроуза до матриці А.

Теореми 3.10, 3.11 дають аналогічні оцінки при зміні рангу матриці.

У пункті 3.3.2 для розвязків лінійних систем з наближено заданими вихідними даними

Ах = b, А = А^T, А 0,

,

які обчислено ітераційними методами, записаними в стандартному вигляді, отримано оцінки повної похибки наближених розвязків. На основі цих оцінок сформульовано критерії закінчення ітераційних процесів, які гарантують дану точність ( Теореми 3.16 - 3.18)

^*. (5)

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

Ах = х, (6)

= , (7)

А M^{n n} , z Cⁿ , C,

||A -|| = ||A|| ,

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

У пункті 4.2.2. розглянуто методи комп'ютерного дослідження стійкості та обумовленості задачі на власні значення. Всі дослідження для задач на власні значення є апостеріорними.

Оцінки

> > ,

cond^*(_i) ^*/||A||,

де ^*- дана точність, встановлюють критерій некратності власного значення задачі (7) в умовах наближених вихідних даних і верхню межу числа обумовленості для отримання даної точності ^*. Ці оцінки базуються на визначенні кратності власних значень в умовах наближених вихідних даних.

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

|| > 2||A ||_,

|| > 2||A ||.

Умова

cond^*(x_i) ^*/||A||, cond(x_i) = s_i^-1,

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

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

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

Теорема 4.4. Нехай (, v) наближена власна пара задачі Ах = Вх. Має місце наступна оцінка відносної похибки власних значень

|( - _j )_j^-1| ||L^-1r || / ||v||_A ,

де А, B симетричні додатньо означені матриці, А = LL^T, r = Av - Bv,

||v||_A = v^TAv.

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

Теорема 4.5. Нехай і вектор (||||=1) наближене власне значення і відповідний власний вектор. Тоді має місце наступна оцінка

| _j - | || A || + ||||.

Теорема 4.6. Нехай , (||||=1) наближене власне значення і відповідний власний вектор. Припустимо також, що наближає кратне власне значення _{i ,} i = p, p+1, . . ., q матриці . Тоді, якщо |_i - | s дляi p, p+1, . . ., q, то існує вектор f = _px_p + . . . + _qx_q , для якого

|| - f || (|| A || + ||||)/s,

де х_i власні вектори задачі (6).

Теорема 4.7. Нехай _i власне значення несиметричної матриці А, у якої всі власні значення різні, х_i відповідний нормований власний вектор. Нехай також матриця А близька до збуреної матриці . Тоді мають місце оцінки

cond (||||+), _.,

||x_i - _i|| (||||+) .

У пятому розділі розроблено та досліджено методи паралельних обчислень для систем лінійних алгебраїчних рівнянь з матрицями довільного вигляду та рангу і повної алгебраїчної проблеми власних значень для MIMD-компютерів архітектури “процесор-процесор”. Проведений аналіз показав, що для створення ефективних методів необхідно враховувати архітектуру паралельних компютерів, а їх дослідження доцільно проводити с урахуванням реальних обчислювальних ресурсів (обмежена кількість процесорів, урахування часу обмінів і синхронізації, обємів памяті). Більше того, навіть для одного класу комп'ютерів з паралельною організацією обчислень програмна реалізація повинна враховувати особливості архітектури мікропроцесорів та топологію компютерної мережі.

Запропоновано циклічно-шарову схему зберігання та обробки матриць, яка дозволила уникнути відомого ефекту Гайдна внаслідок нерівномірного завантаження процесорів в ході реалізації процесів тридіагоналізації і триангуляції матриць, які характерні для більшості прямих методів розв'язування задач лінійної алгебри (Гаусса, Холецького, Банча, Гівенса, Хаусхолдера).

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

- на багатопроцесорному обчислювальному комплексі ЄС 1766 MIMD-архітектури конфігурації "процесор-процесор" з універсальною системою міжпроцесорних зв'язків;

на трансп'ютерній системі на базі трансп'ютерів Т800 з host-комп'ютером IBM PC з структурою міжпроцесорних зв'язків - "лінійка";

- на паралельному комп'ютері Parsytec Power Xplorer-4 на базі мікропроцесорів Power PC 601, математичне забезпечення якого дає можливість формувати різні віртуальні архітектури міжпроцесорних зв'язків.

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

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

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

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

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

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

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

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

АРAC (СПАН) для ЄС ЕОМ;

LINSYST (EIGSYST) для робочої станції Арроlо фірми НР та PC Pentium-III;

LINPAR (EIGPAR) для робочої станції SUN з паралельним розширювачем Parsytec-Explorer4x та IBM PC з трансп'ютерною системою на базі трансп'ютера T800.

У сьомому розділі подано результати чисельного моделювання засобами LINSYST та EIGSYST.

У підрозділах 7.1, 7.2 подано результати тестування функціональних можливостей інтелектуальних програмних засобів LINSYST та EIGSYST на модельних задачах. У підрозділах 7.3, 7.4 проведено дослідження властивостей та розрахунок деяких математичних моделей, що зводяться до задач лінійної алгебри.

У підрозділі 7.3 досліджено першу основну задачу теорії пружності.

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

Нехай V^h скінченно-елементний підпростір простору (V₂¹())³ з базисом{_i}, i =1, 2,..., N. Розглянемо абстрактну дискретну задачу методу скінченних елементів, яка апроксимує (8) - (10): знайти таку функцію u^h V^h , що

a(u^h,v^h) = b(v^h) для v^h V^h . (11)

Поряд з (11), розглянемо наступну дискретну задачу: знайти таку функцію u^h W^h, що

a(u^h,v^h) = b(v^h) для v^h W^h (W₂¹())³. (12)

Розв'язок цієї задачі на всьому просторі не єдиний. Вибираючи за базис W^h функції , (i =1, 2,..., N) та покладаючи , з (12), в результаті отримаємо в загальному випадку несумісну систему лінійних алгебраїчних рівнянь зі стрічковою додатно напіввизначеною матрицею

Ах = b.

Доведено наступну теорему.

Теорема 7.2. Нехай

,

де х_i⁺ нормальний псевдорозв'язок системи лінійних алгебраїчних рівнянь (12). Тоді функція u₊^h буде розв'язком задачі (11).

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

У підрозділі 7.4 виконано чисельне моделювання пружно-деформівного стану нескінченного півпростору з двошаровим включенням.

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

Розв'язок задачі шукається у переміщеннях з використанням розвинення Папковича Нейбера.

Для одержання розв'язку на усіх границях сформульовані відповідні граничні умови.

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

...