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

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

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

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

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

A * x = b, (1)

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

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

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

Нехай D_A ÌH – область визначення оператора A, а H_N ÌD_A – підпростір простору Н з обмеженою розмірністю. Наближеним рішенням рівняння (1) назвемо такий елемент xÎH_N , для якого невязка (Ax – b) ортогональна будь-якому елементу yÎH_N , тобто

(Ax – b,y) = 0 , yÎH_N . (2)

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

,

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

Підставляючи це уявлення x у (2) і вважаючи y послідовно рівним j₁ , j₂ , ... , j_N , одержимо систему для визначення c_k , тобто:

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

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

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

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

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

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

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