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

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

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

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