Рішення Лінійних Систем Рівнянь Прямий та Ітераційний Розв’язувачі, Блог COMSOL

Рішення Лінійних Систем Рівнянь: Прямий та Ітераційний Розв'язувачі

Walter Frei 11/11/2013

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

Лінійне Статичне Завдання Кінцевих Елементів

Розглянемо лінійну статичну задачу кінцевих елементів, складену з трьох вузлів та трьох елементів:

Кожен елемент обмежений двома вузлами. Один із вузлів знаходиться на жорсткій стінці, де, як відомо, зсув дорівнює нулю і немає необхідності вирішувати рівняння для цього вузла. Також як у попередній статті блогу з лінійних статичних задач кінцевих елементів, ми можемо записати рівняння балансу сил для кожного вузла:

можна записати їх також у вигляді:

або навіть у більш компактній формі:

Ми можемо вирішити це завдання за допомогою ітераційного методу Ньютона-Рафсона і, оскільки завдання є лінійною та статичною з початковим значенням \mathbf_=\mathbf , рішення буде знайдено за одну ітерацію:

Далі, у цьому завдання є лише два невідомих, або ступеня свободи (degrees of freedom - DOF), і вона може бути легко вирішена за допомогою ручки та паперу. Але в загальному випадку, ваші матриці будуть налічувати від тисяч до мільйона DOF's, і знаходження рішення вищезгаданого матричного рівняння є найбільш вимогливою в обчислювальному сенсі частиною завдання. При вирішенні таких систем лінійних рівнянь на комп'ютері слід також мати поняття прочисла обумовленості, - мірою чутливості рішення до зміни вхідних даних. Хоча в середовищі COMSOL, число обумовленості ніколи безпосередньо не обчислюється (оскільки за тимчасовими витратами це порівняно з рішенням самої задачі), ми говоритимемо про нього у відносному вираженні. Це число відіграє важливу роль у чисельних методах, що використовуються під час вирішення систем лінійних рівнянь.

Існують два основні (фундаментальні) класи алгоритмів, що використовуються для розв'язання \bfb> : прямі та ітераційні методи. Ми представимо обидві групи цих методів і розглянемо їх загальні властивості та відносну ефективність нижче.

Прямі методи

Вирішувачі прямих методів, що використовуються в COMSOL - це MUMPS, PARDISO і SPOOLES вирішувачі. Усі вони використовують метод LU-розкладання, також званої LU-факторизацією.

Всі ці вирішувачі дають те саме рішення для всіх коректно-поставлених завдань кінцевих елементів, у вирішенні яких вони мають найбільшу перевагу. Вони можуть вирішувати деякі некоректні завдання. З точки зору рішення, будь-який саме вирішувач ви виберете, так як всі вони знайдуть одне і те ж рішення. Прямі вирішувачі відрізняються лише за своєю відносною швидкістю виконання. Кожен з MUMPS, PARDISO, і SPOOLES вирішувачів може скористатися перевагами всіх ядер процесора на одній машині, але PARDISO буде трохи швидше, а SPOOLES трохи повільніше від інших прямих вирішувачів. Однак SPOOLES використовує найменшу кількість пам'яті. Всі прямі вирішувачі вимагають масу оперативної пам'яті RAM, але MUMPS і PARDISO можуть зберігати рішення поза ядром, що означає, що вони можуть використовувати під час вирішення деяких завдань жорсткий диск (створюють файл-підкачування). Рішуч MUMPS підтримує також кластерні обчислення, що дозволяютьвикористовувати більший обсяг пам'яті, ніж наданий єдиною машиною.

Якщо ви займаєтеся вирішенням завдання, яке не має рішення (наприклад, конструкційне завдання з необмеженим навантаженням), прямі вирішувачі все одно спробують вирішити завдання, але, швидше за все, видадуть повідомлення про помилку, подібне до цього:

Якщо ви отримали такого типу повідомлення про помилку, тоді необхідно все перевірити ще раз, щоб переконатися, що завдання поставлене коректно.

Ітераційні методи

Ітераційні вирішувачі в середовищі COMSOL охоплюють безліч різних підходів, але всі вони концептуально досить прості для розуміння, будучи по суті подібними до методу сполучених градієнтів. До інших методів відносяться generalized minimum residual method (узагальнений метод мінімальних нев'язок) і стабілізований метод бисопряжённых градієнтів, і безліч їх варіацій, але вони поводяться подібним чином.

На відміну від прямих вирішувачів, ітераційні методи наближаються до рішення поступово, більш як за один обчислювальний крок. Отже, при розв'язанні задачі ітераційним способом можна спостерігати за зменшенням оцінної помилки рішення зі зростанням числа ітерацій. Для добре обумовлених завдань збіжність буде рівномірно монотонною. Якщо ви маєте справу із завданням не (досить) добре обумовленим, тоді збіжність буде повільнішою. Осциляційна поведінка ітераційного вирішувача часто сигналізує про те, що завдання не коректно поставлено, наприклад, коли завдання є недостатньо обмеженим. Типовий графік збіжності для ітераційного вирішувача наведено на малюнку нижче:

За умовчанням, модель вважається такою, що оцінилася помилки (рішення) в ітераційному вирішувачі стає менше ніж 10 -3 . Цей параметр контролюється у вікніНалаштування Рішителя:

Великою перевагою ітераційних методів є використання ними пам'яті, яке значно менше, ніж у прямих вирішувачів під час вирішення завдань такої ж розмірності (числа рівнянь). Істотним недоліком є те, що ітераційні вирішувачі не завжди просто працюють. Різна фізика вимагає різних налаштувань ітераційного вирішувача залежно від природи рівнянь, що розв'язуються.

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

Основні Висновки з Прямих та Ітераційних Методів Рішення

Для вирішення систем лінійних рівнянь, що виникають під час моделювання, COMSOL автоматично підбере найкращий вирішувач без участі користувача. Прямі вирішувачі використовують більше пам'яті, ніж ітераційні, але при цьому мають більшу точність (для коректно поставлених завдань). Ітераційні вирішувачі наближаються до рішення поступово, і, за бажанням, можна змінювати відносну похибку рішення.