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

При виконанні роботи використані програми Microsoft Office Word 2007 ServicePack 1, Microsoft Office PowerPoint 2007 ServicePack 1 та Microsoft Visual Studio 2008 ServicePack 1, а також основні поняття лінійної алгебри та математичного моделювання.
В результаті роботи розроблена програма чисельного розв'язку систем лінійних алгебраїчних рівнянь з розрідженою матрицею, яка економно витрачає оперативну пам'ять, що дозволяє розв’язувати багато систем високих ступенів за допомогою персональних комп'ютерів. Для розв'язання таких систем при класичній схемі зберігання всіх елементів матриці в оперативній пам'яті довелось би залучати суперкомп'ютери.
СИСТЕМА ЛІНІЙНИХ АЛГЕБРАЇЧНИХ РІВНЯНЬ, ОПЕРАТИВНА ПАМ'ЯТЬ, МАТРИЦЯ, АЛГОРИТМ, ПРОГРАМА.

Зміст
Перелік умовних скорочень і термінів
Вступ
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. Терміни
Розмірність матриці – кількість невідомих в матриці.
Розріджена матриця – матриця, в якій більшість елементів дорівнює нулю.
Оперативна пам'ять – енергозалежний вид пам'яті комп'ютера, в якій зберігаються дані, необхідні процесору в даний час.
Крайова задача – система диференціальних рівнянь з визначеними лінійними співвідношеннями між значеннями шуканих функцій на кінцях інтервала інтегрування.

Вступ
Зараз у зв'язку з бурхливим розвитком обчислювальних засобів широке поширення одержали інформаційні технології, що мають різноманітну теоретичну і прикладну спрямованість. Серед них особливе місце займають системи автоматизованого проектування (САПР), невід'ємну частину яких становлять підсистеми математичного моделювання різних фізичних процесів. Одним із самих перспективних напрямків розвитку математичного моделювання є широке використання чисельних методів, таких як метод скінчених елементів (МСЕ). Це чисельний метод для диференціальних рівнянь, що зустрічаються у фізиці [1]. Виникнення цього методу пов'язане з розв’язком задач космічних досліджень. Уперше він був опублікований у роботі Тернера, Клужа, Мартіна і Топпа. Ця робота сприяла появі інших робіт; був опублікований ряд статей із застосуванням методу скінчених елементів до задач будівельної механіки і механіки суцільних середовищ. Важливий внесок у теоретичну розробку методу зробив в 1963 р. Мелош, який показав, що метод скінчених елементів можна розглядати як один з варіантів добре відомого методу Релєя-Рітца. У будівельній механіці метод скінчених елементів мінімізацією потенційної енергії дозволяє звести задачу до системи лінійних рівнянь рівноваги [2,3].
Однією з існуючих труднощів, що виникають при чисельній реалізації розв’язку контактних задач теорії пружності методом скінчених елементів, є розв’язоксистем лінійних алгебраїчних рівнянь (СЛАР) великої розмірності виду . За умови зберігання всіх елементів матриці A в оперативній пам'яті навіть комп'ютер з 24 ГБ оперативної пам'яті здатен вирішити СЛАР з кількістю невідомих не більше56755. Якщо ж невідомих більше, доведеться залучати суперкомп'ютер. Тому актуальною є проблема знаходження схеми компактнішого зберігання матриці СЛАР в оперативній пам'яті.
Зараз розроблена велика кількість програмних систем, що автоматизують різні аспекти чисельного моделювання проблем механіки (ANSYS, COSMOS, FORTU, МІРЕЛА, ПОЛЕ, ПРОЧНОСТЬ і ін.).
Одним з головних блоків усіх цих систем є модуль, відповідальний за розв’язок СЛАР. Слід зазначити, що звичайно розв’язок СЛАР займає більшість часу розрахунку задачі на комп'ютері. Крім того, від цього етапу прямо залежить якість і точність розв’язку задачі в цілому. Тому від вибору методу розв’язку СЛАР і алгоритму його реалізації багато в чому залежить подальший успіх чисельного розрахунку задачі МСЕ.
Більшість існуючих методів розв’язку СЛАР в МСЕ розроблені в припущенні того, що матриця A має стрічкову структуру, причому ширина стрічки m<<n, де n×n– розмірність A. Однак, при використанні МСЕ для чисельного розв’язку контактних задач можливі випадки, коли ширина стрічки m→n.

1. Огляд методів розв’язку СЛАР, що виникають у МСЕ
У процесі побудови дискретних аналогів крайових задач виникають великі системи в загальному випадку нелінійних алгебраїчних рівнянь, які вирішуються у два етапи: на першому етапі вони линеаризуються, а потім отримана система лінійних рівнянь вирішується за допомогою якого-небудь методу лінійної алгебри. Якщо збіжність не досягнута, то процес повторюється.
Основна ідея методу скінчених елементів полягає в тому, що будь-яку неперервну величину, таку як температура, тиск і переміщення, можна апроксимувати дискретною моделлю, яка будується на множині кусочно-неперервних функцій, визначених на кінцевім числі підобластей. Кусочно-неперервні функції визначаються за допомогою значень неперервної величини в кінцевім числі точок розглядаємої області [1,2,3].
У загальному випадку, неперервна величина заздалегідь невідома, і потрібно визначити значення цієї величини в деяких внутрішніх точках області. Дискретну модель, однак, дуже легко побудувати, якщо спочатку припустити, що числові значення цієї величини в кожній внутрішній точці області відомі. Після цього можна перейти до загального випадку. Отже, при побудові конкретної моделі неперервної величини роблять наступним чином:
а) у розглядаємій області фіксується кінцеве число точок. Ці точки називаються вузловими точками або просто вузлами;
б) значення неперервної величини в кожній вузловій точці вважається змінною, яка повинна бути визначена;
в) область визначення неперервної величини розбивається на кінцеве число підобластей, називаних елементами. Ці елементи мають загальні вузлові точки і у сукупності апроксимують форму області;
г) неперервна величина апроксимується на кожному елементі функцією, яка визначається за допомогою вузлових значень цієї величини. Для кожного елемента визначається своя функція, але функції підбираються таким чином, щоб зберігалася неперервність величини уздовж границь елемента.
Способи розв’язку СЛАР, застосовувані разом із МСЕ, можна умовно розбити на дві групи: прямі (точні) і ітераційні (наближені). Прийнято вважати, що прямі методи найбільш ефективні при рішенні СЛАР невисоких порядків (не більше 105 невідомих), а ітераційні – для розв’язку СЛАР великих і надвеликих систем (понад 105 невідомих).
Якщо всю матрицю коефіцієнтів СЛАР вдається розмістити в пам'яті, то розв’язок такої системи не представляє якої-небудь складності. Однак на практиці часто доводиться мати справу з матрицями, розміри яких суттєво перевищують об'єм оперативної пам'яті комп'ютера. У таких випадках і доводиться використовувати різні модифікації як прямих, так і ітераційних методів.
Остаточне рішення про застосування прямих або ітераційних методів розв’язку СЛАР необхідно ухвалювати на основі аналізу структури досліджуваної математичної задачі. Прямі методи розв’язку СЛАР вигідніше використовувати, якщо необхідно розв’язувати багато однакових систем з різними правими частинами, або якщо матриця А не є додатньо-визначеною. Крім того, існують задачі з такою структурою матриці, для якої прямі методи завжди кращі, ніж ітераційні.
1.1 Точні методи розв’язку СЛАР
Розглянемо ряд точних методів розв’язку СЛАР [4,5].
1.1.1 Метод Гауса
Нехай дана система , де A – матриця розмірності m×m (квадратна). У припущенні, що a11 ≠0, перше рівняння системи

(1.1)
ділимо на коефіцієнт a11 , у результаті одержуємо рівняння:
(1.2)
Потім з кожного з інших рівнянь віднімається перше рівняння, помножене на відповідний коефіцієнт ai1 . У результаті ці рівняння перетворяться до виду:
(1.3)
Перше невідоме виявилося виключеним із усіх рівнянь, крім першого. Далі в припущенні, що , ділимо друге рівняння на коефіцієнт і виключаємо невідоме з усіх рівнянь, починаючи з третього і т.д. У результаті послідовного виключення невідомих, матриця системи рівнянь стане трикутною:
(1.4)
Сукупність проведених обчислень називається прямим ходом методу Гауса.
З m -го рівняння системи визначаємо xm , з (m-1) -го рівняння визначаємо xm-1 і т.д. до x1 . Сукупність таких обчислень називають зворотнім ходом методу Гауса.
Реалізація прямого методу Гауса вимагає N~2m 2 /3 арифметичних операцій, а зворотнього – N~m 2 арифметичних операцій.
1.1.2 Метод Крамера
Нехай дана система лінійних рівнянь, в якій число рівнянь дорівнює числу невідомих:
(1.5)
Припустимо, що визначник системи d ≠0. Якщо тепер замінити послідовно у визначнику стовпці коефіцієнтів при невідомих xj стовпцем вільних членів b i , то вийдуть відповідно n визначників d1 ,...,dn .
Теорема Крамера. Система n лінійних рівнянь з n невідомими, визначник якої відмінний від нуля, завжди сумісна і має єдинийрозв’язок, який обчислюється по формулах:
(1.6)
Розв’язок довільних систем лінійних рівнянь. Нехай
(1.7)

довільна система лінійних рівнянь, де число m рівнянь системи менше числа n невідомих. Тоді в матриці СЛАР знайдуться r≤ m лінійно незалежних рядків, а інші m- r рядків виявляться їхніми лінійними комбінаціями. Перестановкою рівнянь можна добитися того, що ці r лінійно незалежних рядків займуть перші r місць.
Звідси випливає, що кожне з останніх m- r рівнянь системи (1.7) можна представити як суму перших r рівнянь (які називаються лінійно незалежними або базисними), узятих з деякими коефіцієнтами. Тоді система еквівалентна наступній системі r рівнянь з n невідомими:
(1.8)
Припустимо, що мінор r -їрозмірності, складений з коефіцієнтів при перших r невідомих, відмінний від нуля: Мr ≠0, тобто є базисним мінором. У цьому випадку невідомі, коефіцієнти при яких складають базисний мінор, називаються базисними невідомими, а інші n-r – вільними невідомими.
У кожному з рівнянь системи (1.8) перенесемо в праву частину всі члени з вільними невідомими x r+1 ,...,xn . Тоді одержимо систему, яка містить r рівнянь з r базисними невідомими. Оскільки визначник цієї системи є базисний мінор Mr , то система має єдинийрозв’язок щодо базисних невідомих, який можна знайти по формулах Крамера. Даючи вільним невідомим довільні числові значення, одержимо загальнийрозв’язок вихідної системи.
Однорідна система лінійних рівнянь. Нехай дана однорідна система лінійних рівнянь з n невідомими:
(1.9)
Оскільки додавання стовпця з нулів не змінює рангу матриці системи, то на підставі теореми Кронекера-Kaпeллі ця система завжди сумісна і має, принаймні, нульовийрозв’язок. Якщо визначник системи відмінний від нуля і число рівнянь системи дорівнює числу невідомих, то по теоремі Крамера нульовийрозв’язок є єдиним.
У тому випадку, коли ранг матриці системи менше числа невідомих, дана система крім нульового розв’язку буде мати і ненульові розв’язки. Для знаходження цих розв’язків у системі (1.9) виділяємо r< n лінійно незалежних рівнянь, інші відкидаємо. У виділених рівняннях у лівій частині залишаємо r базисних невідомих, а інші n-r вільних невідомих переносимо в праву частину. Тоді приходимо до системи, розв’язуючи яку по формулах Крамера, виразимо r базисних невідомих x1 ,...,хr через n-r вільних невідомих.
1.1. 3 Метод головних елементів
Нехай дана система n лінійних рівнянь з n невідомими:
(1.10)
де елементи aij ( i, j=1,…, n) утворюють розширену матрицю системи . Виберемо найбільший по модулю і не належачий стовпцю вільних членів елемент apq матриці, який називається головним елементом, і обчислимо множники mi =- aiq / apq для всіх рядків з номерами i≠ p (р -й рядок, що містить головний елемент, називається головним рядком).
Далі до кожного другорядного i -го рядку додамо головний рядок, помножений на відповідний множник mi .
У результаті одержимо нову матрицю, усі елементи q -го стовпця якої, крім apq , складаються з нулів.
Відкинувши цей стовпець і головний p -й рядок, одержимо нову матрицю, число рядків і стовпців якої на одиницю менше. Повторюємо ті ж операції з отриманою матрицею, після чого одержуємо нову матрицю і т.д.
Таким чином, побудуємо послідовність матриць. Для визначення невідомих xj поєднуємо в систему всі головні рядки, починаючи з останнього.
Викладений метод розв’язку систем лінійних рівнянь називається методом головних елементів. Необхідна умова його застосування полягає в тому, що визначник матриці не дорівнює нулю [6,7].

Внимание, отключите Adblock

Вы посетили наш сайт со включенным блокировщиком рекламы!
Ссылка для скачивания станет доступной сразу после отключения Adblock!

Скачать полную версию