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

(1.51)

де a_i =(r_i-1 ,r_i-1 )/(As_i ,s_i ), b_i =(r_i ,r_i )/(r_i-1 ,r_i-1 ) .

Перевагою даного методу є його висока швидкість збіжності до точного розв’язку. Крім того, доведено, що він має властивість «квадратичного закінчення», тобто для додатньо визначеної матриці можна гарантовано одержати точнийрозв’язок при кількості ітерацій k≤n . Розмір необхідної пам'яті на кожній ітерації не змінюється, тому що не вимагає перетворення матриці A . За критерій зупинки даного ітераційного процесу звичайно використовують співвідношення:

(1.52)

де ε – задана точність. За інший критерій збіжності іноді зручніше використовувати середньоквадратичну різницю між рішеннями, отриманими на сусідніх ітераціях:

(1.53)

Середньоквадратичну різницю необхідно контролювати при виконанні кожних k наперед заданих ітерацій.

Недоліком методу Ланцоша є сильна залежність збіжності від точності обчислення напрямів спуску.

Практика показує, що при рішенні СЛАР із сильно розрідженими матрицями коефіцієнтів метод Ланцоша має досить високу збіжність, причому в якості початкового наближення можна брати будь-які числа (наприклад, нулі або праву частину).

2. Схеми компактного зберігання розріджених матриць

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

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

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

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

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

Застосування ітераційних методів дозволяє суттєво скоротити витрати оперативної пам'яті комп'ютера за рахунок того, що при формуванні глобальної матриці жорсткості досить фіксувати тільки її ненульові елементи. У зв'язку з цим при використанні кінцево-елементної технології виникає проблема розробки ефективних алгоритмів формування, зберігання і використання розріджених матриць.

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

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

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

2.1 Перша схема

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

Спочатку, з метою виявлення зв'язків кожного вузла з іншими, провод?