Точные и приближённые методы решения систем линейных уравнений

Во многих областях науки и техники, при решении различных задач, возникает необходимость расчета систем линейных уравнений, которые иногда являются сильно разреженными. Поскольку обычно такие системы уравнений имеют большой порядок, то найти их решение возможно только с применением вычислительной техники. Для решения подобных задач можно использовать прямые методы (Гаусса, Крамера), и приближенные (градиентного спуска, Зейделя и др.). Прямые методы дают точное решение (ошибка может быть только из-за выхода величин при преобразованиях за пределы точности типов для используемой платформы), но обычно требуют большее количество итераций. Приближенные методы обычно работают быстрее, но могут требовать особых начальных условий или какой-либо подготовки исходных данных, и решение не всегда сходится. Рассмотрим реализацию метода Гаусса, модифицированный для решения разреженных систем линейных уравнений. Данный метод не является «математическим», а скорее «алгоритмическим» и показывает, как путем простых приемов можно ускорить расчет в сотни раз.

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

Описание метода

Метод Гаусса заключается в обнулении нижней (или верхней) полуматрицы a[i,k], где строка i=2..N, столбец k=1..i-1. Используя известное правило, что решение системы не изменится, если к одному из ее уравнений добавить другое, умноженное на произвольный коэффициент, строки матрицы поочередно, начиная с первой, домножаются на специальные коэффициенты и суммируются со всеми ниже лежащими строками. Коэффициенты подбираются таким образом, чтобы каждая строка обнуляла соответствующий ей (i=k) ниже лежащий столбец (только его поддиагональную часть). Так первая строка обнуляет первый столбец A[2..N,1], вторая – второй A[3..N,2] и т.д. до предпоследней строки. Коэффициенты рассчитываются так: например для того чтобы обнулить первый столбец нужно первую строку домножить на k=-A[2,1]/A[1,1] и прибавить ко второй, затем на k=-A[3,1]/A[1,1] и прибавить к третей и т.д. После операция повторяется со второй строкой (она домножается на соответствующие коэффициенты и складывается со всеми нижележащими строками) и т.д. до предпоследней. В результате получается матрица, под главной диагональю которой остаются одни нули. Теперь в последнем уравнении остался только один коэффициент – соответственно можно легко вычислить значение последней неизвестной: X[N]=B[N]/A[N,N], где B – вектор свободных членов уравнений, который кстати, также участвует в преобразованиях при обнулении матрицы A. В предпоследнем уравнении осталось два коэффициента, и последняя неизвестная уже известна, можно вычислить предпоследнюю: X[N-1]=(B[N-1]-A[N-1,N]*X[N])/A[N-1,N-1]. Таким образом, используя обратный ход, можно вычислить все неизвестные. В процессе преобразования матрицы не должны обнуляться коэффициенты главной диагонали. Если такое происходит, то матрица не была факторизована или неправильно составлены уравнения. Или же данная система имеет не одно решение.

Алгоритм решения СЛАУ методом Гаусса подразделяется на два этапа.

· На первом этапе осуществляется так называемый прямой ход, когда путём элементарных преобразований над строками систему приводят к ступенчатой или треугольной форме, либо устанавливают, что система несовместна. А именно, среди элементов первого столбца матрицы выбирают ненулевой, перемещают его на крайнее верхнее положение перестановкой строк и вычитают получавшуюся после перестановки первую строку из остальных строк, домножив её на величину, равную отношению первого элемента каждой из этих строк к первому элементу первой строки, обнуляя тем самым столбец под ним. После того, как указанные преобразования были совершены, первую строку и первый столбец мысленно вычёркивают и продолжают пока не останется матрица нулевого размера. Если на какой-то из итераций среди элементов первого столбца не нашёлся ненулевой, то переходят к следующему столбцу и проделывают аналогичную операцию.

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

Метод Крамера (Крамера правило) — способ решения квадратных систем линейных алгебраических уравнений с ненулевым определителем основной матрицы (причем для таких уравнений решение существует и единственно) Для системы n линейных уравнений с n неизвестными (над произвольным полем)

с определителем матрицы системы Δ, отличным от нуля, решение записывается в виде

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

Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода.