Прямые методы решения систем линейных алгебраических уравнений

Использование метода Крамера  уместно для решения систем линейных уравнений небольшого порядка, поскольку он требует вычисления n+1 определителей размерности nxn. При этом затраты времени и вычислительных мощностей становятся неоправданно большими, если порядок системы велик.

Данный метод может  быть применен только для решения  квадратных определенных систем.

Матричный метод

 

Суть матричного метода решения систем линейных алгебраических уравнений или, иначе, метода обратной матрицы, заключается в следующем. Умножим обе части системы уравнений в матричной форме на матрицу А^-1, являющуюся обратной к матрице системы А:

.

Поскольку произведение матрицы на обратную к ней матрицу есть единичная матрица: – получим:

Таким образом, правая часть  полученного уравнения есть вектор-столбец  решений.

Необходимым условием применимости матричного метода является неравенство нулю определителя матрицы системы:

Алгоритм решения системы  линейных алгебраических уравнений  методом обратной матрицы:

• Находится определитель матрицы системы, проверяется, действительно ли он не равен нулю
• Находится обратная матрица к матрице системы: , где - транспонированная матрица алгебраических дополнений соответствующих элементов матрицы A.

Итак, метод обратной матрицы применим для систем линейных алгебраических уравнений, в которых число переменных равно числу уравнений и определитель матрицы, системы которых отличен от нуля.

 

Метод вращения

 

Метод вращени схож с методом Гаусса. Аналогично, здесь целью прямого хода преобразований является приведение матрицы системы к треугольному виду при помощи последовательного обнуления поддиагональных элементов всех столбцов по очереди. Можно использовать этот метод не только для формы записи системы в матричном виде.

Предположим, что с₁ и s₁ – это некоторые числа, не равные нулю. При умножении первого уравнения системы на с₁, а второго на s₁ и при их последующем сложении, получаем уравнение, которым заменяется первое уравнение системы. После этого, первое уравнение системы умножается на s₁, а второе – на с₁, они складываются, и результатом заменяется второе уравнение. В итоге, первые два уравнения системы заменяются следующими уравнениями:

Далее необходимо наложить на с₁ и s₁ следующие условия:

• Условие исключения x₁ из второго уравнения.
• Условие нормировки:

Получаем:

.

Полученные числа возможно интерпретировать как синус и косинус некого угла α₁, что и дает название метода, поскольку каждый шаг преобразования может быть рассмотрен, как вращение расширенной матрицы системы в плоскости обнуляемого индекса.

В итоге преобразований получается система:

Здесь

Затем, первое уравнение заменяется новым уравнением, которое получено сложением итогов умножения первого и третьего уравнений,  соответственно на:

Третье уравнение заменяется уравнением, которое получается при сложении итогов умножения тех же уравнений на s₂ и с₂ соответственно. В итоге, получается система:

Здесь:

 

После того, как преобразования выполнены m–1 раз, получается система:

Затем, по тому же алгоритму преобразуется матрица

После прохождения m–1 этапов прямого хода исходная система будет сведена к треугольному виду.

Далее, происходит обратный ход решения, похожий на обратный ход метода Гаусса. Значения неизвестных вычисляются последовательно, одно за другим, начиная с последнего.

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

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

Выражение

называется невязкой. Подставим в него X(0):

В зависимости от значения полученной величины можно так или иначе оценить точность найденного решения. Эта величина должна быть достаточно мала. Если же, это не так, и

,

где ε – некая требуемая точность решения, то необходимо найти такой вектор-поправку p, что

 

- точное решение системы.

То есть,

Последнее выражение равносильно следующему уравнению в матричной форме:

.

Итак, нахождение поправки сводится в итоге к решению системы, аналогичной системе:

,

но в качестве вектора-столбца  свободных членов в ней должен стоять вектор-столбец невязок.

Метод прогонки

 

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

Задачи, в которых необходимо решение подобных систем линейных уравнений, встречаются в области математической физики. Метод прогонки является частным случаем метода Гаусса и, аналогично ему, имеет прямой и обратный ход.

Первый этап, называемый прямой прогонкой, заключается в  нахождении прогоночных коэффициентов  по следующим формулам:

На втором этапе, в процессе так называемой обратной прогонки, находятся неизвестные по следующим формулам:

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

Это означаете диагональное преобладание матрицы А. При этом, хотя бы одно из неравенств должно быть строгим.

Разложение  Холецкого

 

В случае, если матрица системы А симметрична и положительно определена, для решения системы линейных алгебраических уравнений может быть применен метод Холецкого. Также его называют методом квадратных корней.

Суть данного метода заключается в следующем. Матрица системы представляется в виде разложения Холецкого:

Здесь L – нижняя треугольная матрица (квадратная матрица, в которой все элементы, находящиеся выше главной диагонали, нулевые). Элементы на диагонали матрицы L строго положительны.

Можно также привести другую запись разложения Холецкого:

Здесь – верхняя треугольная матрица.

Следует указать, что  для любой положительно-определенной симметричной матрицы разложение Холецкого всегда существует и единственно.

Элементы матрицы L вычисляются по следующим формулам:

,

при этом, вычисление производится сверху вниз и слева направо.

После того, как разложение Холецкого произведено, неизвестные  можно найти, решив две треугольные системы уравнений:

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

LU-разложение

 

Для решения систем линейных алгебраических уравнений также  можно использовать LU-разложение (LU-факторизацию) матрицы системы:

Верхнюю треугольную  и нижнюю треугольную матрицы можно найти при помощи следующего алгоритма:

Обозначим элементы матриц как:

,

при этом, диагональные элементы матрицы L:

.

Если известно LU-разложение, то определитель матрицы системы можно вычислить следующим образом:

Далее, элементы матриц L и U находятся по формулам:

Главным условием применимости данного метода для решения системы  линейных уравнений является невырожденность матрицы системы.

LUP-разложение

 

Метод решения систем уравнений с использованием LUP-разложения применим для систем с невырожденными матрицами, при этом, в сравнении с методом LU-разложения, он гораздо более устойчив.

В данном случае, матрица системы представляется в виде:

Здесь P – матрица перестановок, которая получается из единичной матрицы путем перестановки столбцов или строк.

Как и в предыдущем методе, обозначим элементы матриц как:

LUP-разложение находится по следующему алгоритму.

Допустим, матрица . Сначала на каждом i-м шаге производится нахождение максимального по модулю среди элементов i-го столбца находящихся не выше i-й строки элемента (ведущего (опорного) элемента). Затем, строка, содержащая опорный элемент, меняется местами с i-й строкой. В то же время, в матрице P производится аналогичный обмен. Если, при этом, матрица невырождена, то ведущий элемент в любом случае будет не равен нулю. Затем, каждый элемент текущего i-го столбца, который находится ниже i-й строки, делится на ведущий. После этого, из каждого элемента, который находится ниже i-й строки и i-го столбца (для которого j>i и k>i), вычитается произведение . Затем, i увеличивается на единицу. Процесс повторяется до тех пор, пока i<n. После выполнения всех шагов матрица C сможет быть представлена в следующем виде:

Здесь E – единичная матрица.

 

Заключение

 

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

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

Метод Крамера позволяет  находить решение систем линейных алгебраических уравнений, в случае, когда определитель матрицы системы не равен нулю. Метод сводится к нахождению определителей матриц порядка nxn и применению формул Крамера для нахождения неизвестных переменных. Этот метод применим для систем уравнений небольшого порядка. Если уравнений в системе больше трех, количество математических операций, нужных для вычислений, становится настолько большим, что использование метода становится нецелесообразным, и становится удобнее использовать метод Гаусса.

Метод обратной матрицы, как и метод Крамера, применим для систем линейных алгебраических уравнений, в которых число неизвестных равно числу уравнений, и в которых определитель матрицы системы не равен нулю. Эти условия накладывают соответствующие ограничения на применимость метода.