Глава 3. Решение систем линейных алгебраических уравнений

Система линейных алгебраических уравнений (СЛАУ), состоящая из n уравнений, может быть записана в следующем виде

 

 

или может быть представлена в матричной форме:

где

 

 

Для СЛАУ  – это постоянные коэффициенты,  – неизвестные,  – свободные члены системы.

Решением СЛАУ является такая совокупность значений неизвестных  , которая каждое уравнение системы обращает в верное тождество.

Диагональ матрицы, проходящая слева направо, называется главной диагональю.

Если все элементы матрицы, находящиеся ниже главной диагонали, равны нулю, то такая матрица называется треугольной.

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

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

Система, в которой определитель близок, но не равен нулю, называется плохо обусловленной системой.

Непосредственный расчет определителей для больших (матриц)является очень трудоемким по сравнению с вычислительными методами.

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

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

Рассмотрим наиболее распространенные методы.

Метод Крамера

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

Решение представляется в виде

 

 

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

Система  линейных уравнений сводится к вычислению определителя порядка .

 

 

Метод Гаусса

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

Рассмотрим этот метод на примере системы трех уравнений, а затем распространим его на систему  уравнений:

 

 .

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

где

 ,  ,  ,

 

 ,  ,  .

 

Обобщим эти формулы для системы  уравнений. Обозначим через – номер строки, – номер столбца.

 

 

где

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

где

,

 

Теперь матрица системы приведена к треугольному виду, и из третьего уравнения можно найти , затем подставить его во второе уравнение и найти из него  и т.д.

 

, ,

 

Аналогично строится алгоритм для системы с произвольным числом уравнений, который включает два этапа:

1. Прямой ход – приведение матрицы системы к треугольному виду.

2. Обратный ход – вычисление искомых неизвестных.

Метод простых итераций

Метод простых итераций является одним из простейших итерационных методов. Рассмотрим метод также на примере трех линейных уравнений, а затем применим на систему  уравнений:

 

 

Предполагается, что диагональные элементы отличны от нуля, в противном случае надо переставить уравнения. Выразим неизвестные из уравнений

;

;

Зададим некоторые начальные (нулевые) приближения: , подставляя которые, мы получим новое приближение:

 

;

 

;

 

 

Обозначим через – номер итерации, тогда для  уравнений итерационные формулы можно записать следующим образом:

 

Итерации проводятся до тех пор, пока не будет выполнено следующее условие:

 

 ,

Если условие не выполняется, итерации повторяют, приняв

 

.

 

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

 

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

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

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

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

 

 

На главной диагонали находятся коэффициенты

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

Из первого уравнения системы получим

 

с другой стороны,

 

 

Следовательно,

Из второго уравнения получим

 

;

 

;

 

 

с другой стороны,

Обозначим

 

тогда

 

 

Аналогично для любого :

 

Обратная прогонкасостоит в последовательном вычислении неизвестных  Вычислим из последнего уравнения:

 

с другой стороны,

 

 

Умножим второе уравнения на вычтем его из первого, получим

 

Отсюда получим:

 

 

Далее неизвестные вычисляются по формуле

 

 

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