Метод сопряженных градиентов - это наиболее популярный метод для решения системы линейных уравнений с разреженной симметричной положительно определенной матрицей. Алгоритм обладает тремя притягательными чертами. Во-первых, он использует только операцию умножения матрицы системы на вектор, т.е. может применяться как для решения задач, в которых матрица системы задана в явной форме, так и для решения задач, в которых матрица доступна только через операцию умножения на вектор. Во-вторых, алгоритм требует фиксированного времени на каждую итерацию, независимо от числа осуществленных итераций (в некоторых алгоритмах это условие не выполняется). Третьим достоинством является то, что алгоритм всегда сходится.
Метод сопряженных градиентов является одним из методов подпространств Крылова, т.е. методов, строящих ортогональный базис подпространства span{ r0 , Ar0 , A 2r0 , ..., A ir0 } для некоторого стартового вектора r0 . Решение исходной системы Ax = b ищется на этом подпространстве путем минимизации невязки. Два свойства алгоритма, отмеченные выше, вытекают из того, что для построения ортогонального базиса используются последовательное умножение стартового вектора на матрицу A и трехчленные рекуррентные соотношения для ортогонализации генерируемых векторов (отсюда постоянные затраты на одну итерацию - каждый новый вектор ортогонализируется путем операций только с двумя предыдущими векторами).
Из всего многообразия приближенных методов принципиально важными при численном решении различных инженерных задач являются методы итерационные. Итерационные методы используются во многих приложениях численных задач. Например, в компьютерном инжиниринге решатель процессора представляет дифференциальное уравнение, описывающее поведение инженерного объекта, в виде эквивалентной системы алгебраических уравнений, затем приводит систему алгебраических уравнений к матричному виду и выполняет в итоге решение последовательными приближениями.
Метод итераций (от латинского iteration - повторение), строго говоря, следует назвать методом последовательных приближений. Он интересен тем, что позволяет найти решение с некоторой заранее заданной точностью, кроме того, мелкие ошибки, допущенные в процессе вычислений, впоследствии исправляются, то есть метод является самоисправляющимся. Метод последовательных приближений легко программируется, его удобно использовать в компьютерных вычислениях.
Альтернативой итерационным методам являются прямые методы. По сравнению с прямыми методами итерационные методы сокращают время решения и запрашивает меньше ресурсов компьютера при анализе больших моделей. Итерационные методы являются алгоритмически более простыми и в меньшей степени используют структуру матрицы. Итерационные решатели дают сходящееся от итерации к итерации, приближенное решение. Однако сходимость обычных итерационных методов крайне медленная (например, метод простой итерации в случае плохо обусловленной матрицы). Алгоритмически более сложными являются неявные итерационные методы, в которых решение на новой итерации находится тем или иным прямым методом; но преимуществом неявных методов является существенно более быстрая сходимость.
На результат итерационного процесса влияют ошибки алгоритма и ошибки округления. При использовании итерационных методов ошибки округления не накапливаются. Главное отличие итерационных методов заключается в необходимости предварительно задать начальные значения искомых параметров.
В общем случае итерационный решатель предпочтительно использовать для больших и сложных задач. Он дает возможность получить более эффективное решение пространственных задач различной физической природы (поле температур, акустическое и электромагнитное поля) и других трудоемких видов анализа, математическая сторона которых описывается разреженными, симметричными, положительно определенными матрицами.
Итерационные методы интересны здесь в связи с методом конечных элементов и компьютерным инжинирингом. Основная идея метода конечных элементов состоит в том, что любую непрерывную величину, такую, как температура, давление и перемещение, можно аппроксимировать дискретной моделью, которая строится на множестве кусочно-непрерывных функций, определенных на конечном числе подобластей. Кусочно-непрерывные функции определяются с помощью значений непрерывной величины в конечном числе точек рассматриваемой области. В общем случае непрерывная величина заранее не известна и нужно определить значения этой величины в некоторых внутренних точках области. Дискретную модель, однако, очень легко построить, если сначала предположить, что числовые значения этой величины в каждой внутренней точке области известны. После этого можно перейти к общему случаю. Итак, при построении конкретной модели непрерывной величины поступают следующим образом:
1. В рассматриваемой области фиксируется конечное число точек. Эти точки называются узловыми точками или просто узлами.
2. Значение непрерывной величины в каждой узловой точке считается переменной, которая должна быть определена.
3. Область определения непрерывной величины разбивается на конечное число подобластей, называемых элементами. Эти элементы имеют общие узловые точки и в совокупности аппроксимируют форму области.
4. Непрерывная величина апроксимируется на каждом конечном элементе функцией, которая определяется с помощью узловых значений этой величины. Для каждого элемента определяется своя функция, но функции подбираются таким образом, чтобы сохранялась непрерывность величины вдоль границ элемента.
Для решения систем линейных алгебраических уравнений (СЛАУ) в методе конечных элементов (МКЭ) требуется выбрать метод решения. Окончательное решение о применении итерационных или прямых методов решения СЛАУ необходимо принимать на основе анализа структуры исследуемой математической задачи. Прямые методы решения СЛАУ более выгодно использовать, если необходимо решать много одинаковых систем с различными правыми частями, или если матрица А не является положительно-определенной. Кроме того, существуют задачи с такой структурой матрицы, для которой прямые методы всегда предпочтительнее, чем итерационные.
