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

Зараз у звязку з бурхливим розвитком обчислювальних засобів широке поширення одержали інформаційні технології, що мають різноманітну теоретичну і прикладну спрямованість. Ця робота сприяла появі інших робіт; був опублікований ряд статей із застосуванням методу скінчених елементів до задач будівельної механіки і механіки суцільних середовищ. У будівельній механіці метод скінчених елементів мінімізацією потенційної енергії дозволяє звести задачу до системи лінійних рівнянь рівноваги [2,3]. Однією з існуючих труднощів, що виникають при чисельній реалізації розвязку контактних задач теорії пружності методом скінчених елементів, є розвязок систем лінійних алгебраїчних рівнянь (СЛАР) великої розмірності виду Основна ідея методу скінчених елементів полягає в тому, що будь-яку неперервну величину, таку як температура, тиск і переміщення, можна апроксимувати дискретною моделлю, яка будується на множині кусочно-неперервних функцій, визначених на кінцевім числі підобластей.Розглянемо ряд точних методів розвязку СЛАР [4,5].IMG_396843d6-7f11-43be-ab84-025a090b3287 ділимо на коефіцієнт a11, у результаті одержуємо рівняння: IMG_3b49824c-8852-4fd6-8488-9b84f85c9a4d Потім з кожного з інших рівнянь віднімається перше рівняння, помножене на відповідний коефіцієнт ai1. У результаті ці рівняння перетворяться до виду: IMG_b9874e74-301f-44da-90bf-77d97aac7291 Перше невідоме виявилося виключеним із усіх рівнянь, крім першого. IMG_19c8e670-5b4b-4e2e-8e88-221a441c3fb8 , ділимо друге рівняння на коефіцієнтНехай дана система лінійних рівнянь, в якій число рівнянь дорівнює числу невідомих: IMG_377417b3-c170-44b3-8c22-72ee701600df Якщо тепер замінити послідовно у визначнику стовпці коефіцієнтів при невідомих xj стовпцем вільних членів bi, то вийдуть відповідно n визначників d1,...,dn. Система n лінійних рівнянь з n невідомими, визначник якої відмінний від нуля, завжди сумісна і має єдиний розвязок, який обчислюється по формулах: IMG_7ff2dd61-69d5-4ad5-9551-477af046ec64 Тоді одержимо систему, яка містить r рівнянь з r базисними невідомими. Оскільки визначник цієї системи є базисний мінор Mr, то система має єдиний розвязок щодо базисних невідомих, який можна знайти по формулах Крамера.Нехай дана система n лінійних рівнянь з n невідомими: IMG_47261e84-6909-4ea0-ae85-ae4435d292b2 де елементи aij (i,j=1,…,n) утворюють розширену матрицю системи IMG_d18dd8f3-58b4-444d-8aa4-852b8dc43d94 . Виберемо найбільший по модулю і не належачий стовпцю вільних членів елемент apq матриці IMG_59cdc3c0-53c4-4aa8-9bf1-f23698d7098f , який називається головним елементом, і обчислимо множники mi=-aiq /apq для всіх рядків з номерами i?p (р-й рядок, що містить головний елемент, називається головним рядком).Нехай система лінійних алгебраїчних рівнянь дана в матричному вигляді: IMG_b359947c-d5f4-4735-b814-8b19874d2741 Представимо матрицю А у вигляді добутку нижньої трикутної матриці С і верхньої трикутної матриці В з одиничною діагоналлю, тобто А=СВ, де Причому елементи cij і bij визначаються по формулах: IMG_cfda5854-2415-4a8d-bada-64279f64faa7 Тоді рівняння (1.13) перепишемо у вигляді: IMG_2a60ae13-a35c-411a-bbaa-913853e78d23 Перемноживши матриці в лівій частині рівності (1.15), одержуємо систему рівнянь, з якої одержимо наступні формули для визначення невідомих: Невідомі yi зручно обчислювати разом з елементами bij.Даний метод використовується для розвязку систем лінійних алгебраїчних рівнянь виду Перемножуючи ST і S, і дорівнюючи матриці А, одержимо наступні формули для визначення s<ij:> Після знаходження матриці S систему (1.18) заміняємо двома їй еквівалентними системами з трикутними матрицями (1.19): IMG_2c20ede4-7944-4acd-9452-57b545287d6fВикористовуючи це співвідношення, виразимо xi-1 і xi через xi 1 і підставимо в рівняння (1.26): IMG_a0e0aad0-639a-493d-ad30-05ebd209ceed де Fi - права частина i-го рівняння. Це співвідношення буде виконуватися незалежно від розвязку, якщо зажадатиМатричний метод розвязку систем лінійних алгебраїчних рівнянь з ненульовим визначником полягає в наступному. Нехай дана система n лінійних рівнянь з n невідомими (над довільним полем): IMG_c2f39ed6-89e4-4a49-a6d4-e1eda93b7896 Помножимо це матричне рівняння ліворуч на A-1 - матрицю, зворотню до матриці Права частина цього рівняння дасть стовпець рішень вихідної системи. Умовою застосовності даного методу (як і взагалі існування розвязку неоднорідної системи лінійних рівнянь із числом рівнянь, рівним числу невідомих) є невирідженість матриціНаближені методи розвязку систем лінійних рівнянь дозволяють одержувати значення коренів системи із заданою точністю у вигляді границі послідовності деяких векторів.Нехай дана система n лінійних рівнянь з n невідомими: IMG_93557c44-6470-4a9e-8ca9-48cef1b3cdf3 IMG_5505b9d6-617c-4538-a1cb-84be56e842c9 . Припускаючи, що діагональні елементи aii?0 (i=1,...,n), виразимо x1 через перше рівняння системи, x2 - через друге рівняння і т.д. У результаті одержимо систему: IMG_0aebdcd9-865d-4b5e-ab37-254ff7e8d195Метод Зейделя являє собою модифікацію метод

Зміст

Перелік умовних скорочень і термінів

Вступ

1 Огляд методів розвязку СЛАР, що виникають у МСЕ

1.1 Точні методи розвязку СЛАР

1.1.1 Метод Гауса

1.1.2 Метод Крамера

1.1.3 Метод головних елементів

1.1.4 Схема Халецького

1.1.5 Метод квадратного кореня

1.1.6 Метод прогону

1.1.7 Матричний метод

1.2 Ітераційні методи розвязку СЛАР

2.1 Метод простих ітерацій

1.2.2 Метод Зейделя

1.2.3 Метод релаксації

1.2.4 Багатосітковий метод

1.2.5 Метод Ланцоша

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

2.1 Перша схема

2.2 Друга схема

3 Оптимізація обчислень

4 Чисельні експерименти

4.1 Пружне деформування тонкостінної просторової рами

4.2 Контактна взаємодія оболонкової конструкції і ложемента

Висновки

Перелік посилань

Додаток А Перелік умовних скорочень і термінів

1. Умовні скорочення

МСЕ - метод скінчених елементів.

СЛАР - система лінійних алгебраїчних рівнянь.

2. Терміни

Розмірність матриці - кількість невідомих в матриці.