Реферат на тему:

Автоматизована обробка інформації складних систем проекційними методами

Найбільше розробленим методом розв’язання проблем у рамках автоматизації обробки інформації в складних інформаційних системах є ве-ликі розріджені системи лінійних алгебраічних рівнянь (ВР СЛАР). Та в практиці розробки автоматизованих систем обробки інформації, які підляга-ють аналізу, існує галявина, що впливає на розробку та створення алгоритмів і програмного забезпечення за-для розв’язання крайових і динамічних бага-томірних польових задач, що мають місце при рішенні складних науково-інженерних проблем, розпізнавання образів, вилучення знань тощо. З цією ціллю необхідно розглянути питання як теоретичного обгрунтування методів дискретизації, так і їхньої практичної реалізації з урахуванням: порядку апроксимації рішення і збіжності обчислювальних алгоритмів. Серед множини існуючих методів розв’язання зазначеного класу задач особливе місце займають проекційні методи. Завдяки своїй достатній універсальності, а також – низці гідностей, проекційні методи завойовують все більшу популярність [1]. Найбільш відомі з них – це методи Рітца і Гальоркіна [2]. Застосування їх [3] дозволяє зберегти в наближеній задачі важливі властивості вихідної крайової задачі, зокрема, симетрії, позитивної певності, властивостей теплицевих матриць та ін. Для проекційних методів розв’язання добре розроблена теорія дослідження похибок наближених рішень.

Як відомо [1], вимога завдання в просторі скалярного добутку, норми і властивостей аддитивності й однорідності призводить до визначення гільбертова простору. Розглянемо в абстрактному гільбертовом просторі Н із визначеним скалярним добуткомом (*,*) операторне рівняння

A * x = b, (1)

де А – лінійний оператор;

b – заданий елемент простору H;

x – невідомий елемент.

Нехай DAH – область визначення оператора A, а HNDA – підпростір простору Н з обмеженою розмірністю. Наближеним рішенням рівняння (1) назвемо такий елемент xHN, для якого невязка (Ax – b) ортогональна будь-якому елементу yHN, тобто

(Ax – b, y) = 0 , yHN . (2)

Це співвідношення, так само як і співвідношення (1), дозволяє одержати систему алгебраїчних рівнянь для визначення наближеного рішення. Дійсно, нехай 1, 2, ... , N, – базис у просторі НN. Наближене рішення будем шукати у виді

,

де ck (k=1, 2, ... , N) – невідоме число.

Підставляючи це уявлення x у (2) і вважаючи y послідовно рівним 1, 2, ... , N, одержимо систему для визначення ck, тобто:

i=1, 2, ... , N. (3)

Описаний процес пошуку наближеного рішення рівняння (3) називається методом Гальоркіна. Функції 1, 2, ... , N називаються координатними функціями проекційного методу [1].

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

За останні десятиріччя відношення до проекційних методів змінилося. Широкий інтерес до них був викликаний створенням нового методу – методу кінцевих елементів. Цей метод можна розглядати як результат синтезу двох методів – метода кінцевих різниць і метода Гальоркіна. Цей метод знайшов особливо широке застосування при розрахунках на тривкість і тривалість деталей, конструкцій і споруджень.

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

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

Загальна ідея методу вкладених перетинів полягає ось в чому 4. Нехай А - симетрична матриця, GA - асоційований з нею неорієнований граф. Розглянемо роздільник S, видалення якого розбиває граф GA на дві частини, множини вузлів яких суть С1 і С2. Якщо вузли S нумерувати після нумерації вузлів С1 і С2, то це індуцирує розбивку відповідним чином упорядкованої матриці, форма якого показана на мал. 1. Зробимо тепер ключове зауваження: нульовий блок матриці залишається нульовим і після розкладання. Оскільки однієї з головних цілей при дослідженні розріджених матричних обчислень є зберігання по можливості більшого числа нульових елементів або, іншими словами, мінімізувати заповнення матриці, то використання роздільників зазначеним засобом набуває важливе значення. При відповідному їхньому виборі можна сподіватися на одержання великої підматриці, що гарантовно залишається нульовою. Ту ж саму ідею можна застосовувати й рекурсивно, зберігаючи аналогічним засобом нулі в підматрицях.

Рекурсивне застосування цієї основної ідеї призводить до методу, за яким закріпилася назва методу вкладених перетинів. Зокрема, ця техніка була використана для розріджених систем, ассоційованих із регулярними NN–сітками, що складаються з (N-1)2 малих елементів [4].

Мал. 1. Схема використання роздільника.

Нехай Х – множина вершин регулярної (nn)-сітки. Через S0 позначимо множину вузлів сіткової лінії, що поділяє Х на дві по можливості рівні частини R1 і R2. На мал. 2 зображений випадок n=10. Якщо спочатку перелічити рядок за рядком вузли компонентів R1 і R2, а потім – вузли S0, тоді одержимо матричну структуру [4], зображену на мал. 3.

86 87 88 89 90 100 40 39 38 37

81