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

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

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

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

A * x = b, (1)

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

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

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

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

(Ax – b, y) = 0 , yHN . (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. Зробимо тепер ключове зауваження: нульовий блок матриці залишається нульовим і після розкладання. Оскільки однієї з головних цілей при дослідженні розріджених матричних обчислень є зберігання по можливості більшого числа нульових елементів або, іншими словами, мінімізувати заповнення матриці, то використання роздільників зазначеним засобом набуває важливе значення. При відповідному їхньому виборі можна сподіватися на одержання великої підматриці, що гарантовно залишається нульовою. Ту ж саму ідею можна застосовувати й рекурсивно, зберігаючи аналогічним засобом нулі в підматрицях.

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

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

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

86 87 88 89 90 100 40 39 38 37

81 82 83 84 85 99 36 35 34 33

76 77 78 79 80 98 32 31 30 29

71 72 73 74 75 97 28 27 26 25

66 67 68 69 70 96 24 23 22 21

61 62 63 64 65 95 20 19 18 17

56 57 58 59 60 94 16 15 14 13

51 52 53 54 55 93 12 11 10 9

46 47 48 49 50 92 8 7 6 5

41 42 43 44 45 91 4 3 2 1

Мал. 2. Однорівневе упорядкування Мал. 3. Структура матриці, що відповідає

за допомогою перетинів сітки (1010) однорівневому упорядкуванню за. допомогою перетинів.

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

Sj  Rj , j = 1,2, ... ,

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

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

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

Запропонований інтуітивний метод складається з побудови для графа довгої структури рівнів і вибору малого роздільника з "середнього" рівня.

Нехай G=(X,E) - заданий граф. Алгоритм упорядкування за допомогою перетинів можна описати так:

А Л Г О Р И Т М:

ПОЧАТОК

Крок 1 (ініціалізація). Покласти R=X, N=|X|.

Крок 2 (побудувати структуру рівнів). Знайти в G(R) зв”язану

компоненту G(C) і побудувати для неї структуру рівнів із

коренем у псевдопериферійному вузлі r:

Z(r)={L0, L1, ... , Li}.

Крок 3 (знайти роздільник). Якщо l Ј 2, покласти S=C і перейти до

кроку 4. У противному випадку покласти j=[l + 1)/2] і

визначити множину S  L таке, що

S = {y  Lj | Adj(y)Lj + 1  }.

Крок 4 (упорядкування роздільника і цикл). Перенумерувати вузли

роздільника S числами від N – |S|+1 до N. Покласти RR-S

і NN – |S|.

Якщо R  0, перейти до кроку 2.

КІНЕЦЬ

На кроку 3 алгоритму роздільник S можна одержати простим відкиданням тих вузлів з Lj, що не суміжні з жодним вузлом із Lj+1. У багатьох випадках це зменшує розмір роздільника.

Використана література

Марчук Г.И., Агошков В.И. Введение в проекционно-сеточные методы. ‑ М.: Наука, 1981. – 256 с.

Зенкевич О., Чанг И. Метод конечных элементов в теории сооружений и в механике сплошных сред. – М.: Недра, 1974. – 240 с.

Корячко В.П. Курейчик В.М., Норейков Н.П. Теоретические основы САПР. – М.: Энергоатомиздат, 1987. – 400 с.

Джордж А., Ли Дж. Численное решение больших разреженных систем уравнений. – М.: Мир, 1984. – 287 с.

Додатки