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

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

Особливо складні алгоритми роботи з розрідженими матрицями виникають при використанні прямих методів розв’язку. У першу чергу це пов'язане з тим, що при розкладанні розрідженої матриці A=LL^T вона звичайно зазнає деякого заповнення, тобто нижній трикутний множник L має ненульові елементи в тих позиціях, де у вихідній матриці A стояли нулі (не виключено, що при цьому можуть з'явитися і нові нульові елементи). Крім того, прямі методи вимагають спеціальної нумерації вузлів кінцево-елементної сітки, яка забезпечує мінімальну ширину стрічки. Подібних проблем при використанні ітераційних методів не виникає [10,11].

У рамках даної роботи стосовно ітераційних методів розв’язку СЛАР викладені 2 алгоритми зберігання і використання розріджених матриць, які відрізняються простотою реалізації і високою обчислювальною ефективністю.

2.1 Перша схема

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

Спочатку, з метою виявлення зв'язків кожного вузла з іншими, проводиться аналіз структури дискретизації області на КЕ. Наприклад, для КЕ-сітки, зображеної на рис. 2.1, відповідна структура зв'язків буде мати вигляд, зображений у табл. 2.1.

Таблиця 2.1 – Структура зв'язків КЕ-сітки

№ вузла	1	2	3	4	5	6	7
Зв'язки	1,2,5,6,7	1,2,3,6	2,3,4,6	3,4,5,6,7	1,4,5,7	1,2,3,4,6,7	1,4,5,6,7

Тоді для зберігання матриці жорсткості необхідно построчно запам'ятовувати інформацію про коефіцієнти, відповідні до вузлів, з якими зв'язаний даний вузол. На рис. 2.2 наведені матриця жорсткості і її компактний вигляд для сітки, зображеної на рис. 2.1 [9].

Текст програми, що реалізує викладений алгоритм аналізу структури КЕ-розбивки тіла, наведений у додатку А [12,13].

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

Нехай a_ij – елемент первісної квадратної матриці розмірністю n×n, а

– її компактний вигляд. Тоді для зворотнього перетворення будуть слушні наступні співвідношення: