Решение Линейных Систем Уравнений: Прямой и Итерационный Решатели

Walter Frei 11/11/2013
Share this on Facebook Share this on Twitter Share this on Google+ Share this on LinkedIn

В этой статье блога мы представим два класса алгоритмов, которые используются в COMSOL для решения систем линейных уравнений, возникающих при решении любой задачи конечных элементов. Такая информация является существенной для понимания, как внутренних алгоритмов работы решателя (вычислительной программы), так и возрастания требований к памяти из-за количественного усложнения задачи.

Линейная Статическая Задача Конечных Элементов

Рассмотрим линейную статическую задачу конечных элементов, составленную из трех узлов и трех элементов:

Linear static finite element problem Решение Линейных Систем Уравнений: Прямой и Итерационный Решатели

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

f_{u_1} = k_3 (u_2-u_1)-k_2 (u_1-0)

 

f_{u_2} = p-k_3 (u_2-u_1)-k_1 (u_2-0)

 

можно записать их также в виде:

\begin{Bmatrix} f_{u_1} \\ f_{u_2} \end{Bmatrix}=\begin{Bmatrix} 0 \\ p \end{Bmatrix}-\begin{bmatrix} k_2+k_3 && -k_3 \\ -k_3 && k_1+k_3 \end{bmatrix}\begin{Bmatrix} u_1 \\ u_2 \end{Bmatrix}

 

или даже в более компактной форме:

\bf{f(u)=b-Ku}

 

Мы можем решить эту задачу с помощью итерационного метода Ньютона-Рафсона и, поскольку задача является линейной и статической с начальным значением \mathbf{u}_{init}=\mathbf{0}, решение будет найдено за одну итерацию:

\mathbf{u}_{solution}=\mathbf{K^{-1}b}

 

Далее, в этой задаче имеется только два неизвестных, или степени свободы (degrees of freedom — DOF), и она может быть легко решена с помощью ручки и бумаги. Но в общем случае, ваши матрицы будут насчитывать от тысяч до миллиона DOF’s, и нахождение решения вышеуказанного матричного уравнения является наиболее требовательной, в вычислительном смысле, частью задачи. При решении таких систем линейных уравнений на компьютере, следует также иметь понятие о числе обусловленности, — мере чувствительности решения к изменению входных данных. Хотя в среде COMSOL, число обусловленности никогда непосредственно не вычисляется (так как по временным затратам это сравнимо с решением самой задачи), мы будем говорить о нем в относительном выражении. Это число играет важную роль в численных методах, используемых при решении систем линейных уравнений.

Существуют два основных (фундаментальных) класса алгоритмов, используемых для решения \bf{K^{-1}b}: прямые и итерационные методы. Мы представим обе группы этих методов и рассмотрим их общие свойства и относительную эффективность, ниже.

Прямые методы

Решатели прямых методов, используемые в COMSOL — это MUMPS, PARDISO, и SPOOLES решатели. Все они используют метод LU-разложение, также называемой LU-факторизацией.

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

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

Failed to find a solution.
The relative residual (0.06) is greater than the relative tolerance.
Returned solution is not converged.

Если вы получили такого типа сообщение об ошибке, тогда необходимо все перепроверить, чтобы убедиться, что задача поставлена корректно.

Итерационные методы

Итерационные решатели в среде COMSOL охватывают множество различных подходов, но все они концептуально достаточно просты для понимания, будучи по существу подобныМетод сопряжённых градиентов. К другим методам относятся generalized minimum residual method (обобщенный метод минимальных невязок) и Стабилизированный метод бисопряжённых градиентов, и множество их вариаций, но все они ведут себя схожим образом.

В отличие от прямых решателей, итерационные методы приближаются к решению постепенно, более чем за один вычислительный шаг. Следовательно, при решении задачи итерационным способом, можно наблюдать за уменьшением оценочной ошибки решения с ростом числа итераций. Для хорошо-обусловленных задач, сходимость будет равномерно монотонной. Если вы имеете дело с задачей не (достаточно) хорошо-обусловленной, тогда сходимость будет медленнее. Осцилляционное поведение итерационного решателя зачастую сигнализирует о том, что задача не корректно поставлена, например, когда задача является недостаточно ограниченной. Типичный график сходимости для итерационного решателя приведен на рисунке ниже:

Convergence Решение Линейных Систем Уравнений: Прямой и Итерационный Решатели

По умолчанию, модель считается сошедшейся, когда оценка ошибки (решения) в итерационном решателе становится меньше чем 10-3. Этот параметр контролируется в окне Настройки Решателя:

tolerance Решение Линейных Систем Уравнений: Прямой и Итерационный Решатели

Эта погрешность может быть слабее (меньше по порядку величины) для более быстрого решения, или жестче, для наилучшей точности на текущей сетке разбиения. Погрешность всегда должна быть больше машинной точности представления чисел (2.22×10-16) и числа обусловленности (которое зависит от задачи). В принципе, нет смысла делать требование к погрешности излишне жестким, так как входные данные в вашей модели, чаще всего, определены с точностью до второго знака после запятой. Если вы все-таки решите изменить относительную погрешность, мы настоятельно рекомендуем не изменять ее более чем на порядок по сравнению с решением. Помните, что вы найдете решение с меньшей погрешностью только лишь для текущего разбиения сетки и, часто, более эффективным решением будет измельчение сетки.

Большим преимуществом итерационных методов является использование ими памяти, которое значительно меньше, чем у прямых решателей при решении задач такой же размерности (числа уравнений). Существенным недостатком является то, что итерационные решатели не всегда «просто работают». Различная физика требует различных настроек итерационного решателя в зависимости от природы решаемых уравнений.

К счастью, в среде COMSOL уже есть встроенные по умолчанию настройки решателя для любой физической задачи. COMSOL автоматически определит раздел физики решаемой задачи, а также ее размер, и подберет решатель — прямой или итерационный — для этого случая. По умолчанию, итерационные решатели выбираются, исходя из требований наилучшей точности и наименьшей используемой памяти, и не требуют никакого вмешательства со стороны пользователя для своей настройки.

Основные Выводы по Прямым и Итерационным Методам Решения

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


Загрузка комментариев...

Темы публикаций


Теги