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

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

 

3.1 Постановка задачи

 

Требуется найти решение системы  линейных уравнений:

 

a₁₁x₁ + a₁₂ x₂ + a₁₃x₃ + … + a_1nx_n = b₁

a₂₁x₁ + a₂₂ x₂ + a₂₃x₃ + … + a_2nx_n = b₂

a₃₁x₁ + a₃₂ x₂ + a₃₃x₃ + … + a_3nx_n = b₃                                              (3.1)

.

a_n1x₁ + a_n2 x₂ + a_n3x₃ + … + a_nnx_n = b_n

 

или в матричной форме:

 

Ax = b,                                                                                               (3.2)

 

где

a₁₁ a₁₂ a₁₃ …   a_1n   x₁    b₁

a₂₁ a₂₂ a₂₃ …   a_2n    x₂   b₂

A = a₃₁ a₃₂ a₃₃ …   a_3n   x =x_{3  ,}   b =b₃

 

a_n1 a_n2 a_n3  a_nn  x_n   b_n

 

По правилу Крамера  система n линейных уравнений имеет единственное решение, если определитель системы отличен от нуля (det A 0) и значение каждого из неизвестных определяется следующим образом:

 

x_j = ,   j = 1, …, n,                                                                           (3.3)

 

где det A_j – определитель матрицы, получаемой заменой j-го столбца матрицы A столбцом правых частей   b.

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

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

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

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

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

Эти методы будут рассмотрены в  следующих разделах.

 

3.2 Метод исключения  Гаусса. Схема единственного деления

 

Основная идея метода исключений Гаусса состоит в том, что система уравнений (3.1) приводится к эквивалентной ей системе с верхней треугольной матрицей (прямой ход исключений), а затем неизвестные вычисляются последовательной подстановкой (обратный ход исключений).

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

Прямой ход состоит из n – 1 шагов. На первом шаге исключается переменная x₁ из всех уравнений, кроме первого. Для этого нужно из второго, третьего, …, n-го уравнений вычесть первое, умноженное на величину

 

m = , i = 2, 3, …, n.                                                                         (3.4)

 

При этом коэффициенты при x₁ обратятся в нуль во всех уравнениях, кроме первого.

Введем обозначения:

 

a = a_ij – m a_1j ,  b = b_i – m b₁.                                                          (3.5)

 

Легко убедиться, что для всех уравнений, начиная со второго, a = 0, i = 2, 3, …, n. Преобразованная система запишется в виде:

 

 a₁₁x₁ + a₁₂ x₂ + a₁₃x₃ + … + a_1nx_n = b₁

a x₂ + a x₃ + … + a x_n = b

a x₂ + a x₃ + … + a x_n = b                                                       (3.6)

 

a x₂ + a x₃ + … + a x_n = b

 

Все уравнения (3.6), кроме  первого, образуют систему (n – 1)-го порядка. Применяя к ней ту же процедуру, мы можем исключить из третьего, четвертого, …, n-го уравнений переменную x₂. Точно так же исключаем переменную x₃ из последних n – 3 уравнений.

На некотором k-ом шаге в предположении, что главный элемент k-ого шага a 0, переменная x_k исключается с помощью формул:

 

m = ,

a = a – m a ,

 

b = b – m b , i, j = k + 1, k + 2, …, n.                                     (3.7)

 

Индекс k принимает значения 1, 2, …, n – 1.

При k = n – 1 получим треугольную систему:

 

a₁₁x₁ + a₁₂ x₂ + a₁₃x₃ + … + a_1nx_n = b₁

a x₂ + a x₃ + …+ a x_n = b

a x₃ + …+ a x_n = b                                                       (3.8)

 

a x_n = b

 

с треугольной матрицей A_n.

Приведение системы (3.1) к треугольному виду (3.8) составляет прямой ход метода Гаусса.

При использовании метода Гаусса нет  необходимости в предварительном  обосновании существования и  единственности решения (т. е. доказательства, что det A ¹ 0). Если на  k-ом шаге все элементы a (i = k, k + 1, …, n) окажутся равными нулю, то система (3.1) не имеет единственного решения.

Обратный ход состоит в вычислении переменных. Из последнего уравнения (3.8) определяем x_n... Подставляя его в предпоследнее уравнение, находим x_n-1, и т. д. Общие формулы имеют вид:

 

x_n = ,

x_k = (b - a x_k+1 - a x_k+2 - … - a x_n),  k = n – 1, n – 2, …, 1 (3.9)

 

Трудоемкость метода. Для реализации метода исключения Гаусса требуется примерно 2/3n³ операций для прямого хода и n² операций для обратного хода. Таким образом, общее количество операций составляет примерно 2/3n³ + n².

Пример 3.1.

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

 

2.0x₁ + 1.0x₂  – 0.1x₃ +  1.0x₄  =  2.7

0.4x₁ + 0.5x₂ +  4.0x₃ – 8.5x₄ =  21.9

0.3x₁ – 1.0x₂ + 1.0x₃ +  5.2x₄  =  – 3.9                                            (3.10)

1.0x₁ + 0.2x₂ + 2.5x₃ – 1.0x₄  =  9.9

 

Будем делать округление чисел до четырех знаков после десятичной точки.

Прямой ход. 1-ый шаг. Вычислим множители:

 

m = = = 0.2; m = = = 0.15;  m = = = 0.5.

 

Вычитая из второго, третьего и четвертого уравнений системы (3.10) первое уравнение, умноженное соответственно на m , m , m , получим новую систему:

 

2.0x₁ + 1.0x₂  – 0.1x₃ + 1.0x₄  =  2.7

0.3x₂ +  4.02x₃  – 8.70x₄  =  21.36

–1.15x₂ + 1.015x₃ + 5.05x₄ = – 4.305                                                    (3. 11)

– 0.30x₂ + 2.55x₃ – 1.50x₄  =  8.55

 

2-ой шаг. Вычислим множители:

 

m = = =  – 3.83333;     m = = = –1.0.

 

Вычитая из третьего и четвертого уравнений системы (3.11) второе уравнение, умноженное соответственно на m и m , приходим к системе:

 

2.0x₁ + 1.0x₂  – 0.1x₃ + 1.0x₄  =  2.7

0.3x₂ +  4.02x₃  – 8.70x₄  =  21.36

16. 425x₃ – 28.300x₄  = 77.575                                                       (3.12)

6.570x₃ – 10.200x₄  =  29.910

 

3-ий шаг. Вычислим  множитель:

 

m = = = 0.4.

Вычитая из четвертого уравнения  системы (3.12) третье, умноженное на m , приведем систему к треугольному виду:

 

2.0x₁ + 1.0x₂  –    0.1x₃ +        1.0x₄  =  2.7

0.3x₂ +  4.02x₃  –      8.70x₄  =  21.36

16. 425x₃ – 28.300x₄  = 77.575                                                        (3.13)

1.12x₄  =  –1.12

 

Обратный ход. Из последнего уравнения системы (3.13) находим x₄  =  1.000. Подставляя значение x₄  в третье уравнение, получим x₃ = 2.000. Подставляя найденные значения x₄ и x₃ во второе уравнение, найдем x₂ = 3.000. Наконец, из первого уравнения, подставив в него найденные значения x₄, x₃ и x₂, вычислим x₁ = –1.000.

Итак система (3.10) имеет следующее  решение:

 

x₁ = 1.000, x₂ = 2.000, x₃ = 3.000, x₄  =   – 1.000.

 

3.3 Метод исключения  Гаусса с выбором главного  элемента по столбцу

 

Хотя метод Гаусса является точным методом, ошибки округления могут привести к существенным погрешностям результата. Кроме того исключение по формулам (3.7) нельзя проводить, если элемент главной диагонали a равен нулю. Если элемент a мал, то велики ошибки округления при делении на этот элемент. Для уменьшения ошибок округления применяют метод исключения Гаусса с выбором главного элемента по столбцу. Прямой ход так же, как и для схемы единственного деления, состоит из n – 1 шагов. На первом шаге прежде, чем исключать переменную x₁, уравнения переставляются так, чтобы в левом верхнем углу был наибольший по модулю коэффициент a_i1, i =  1, 2, …, n. В дальнейшем, на k-м шаге, прежде, чем исключать переменную x_k, уравнения переставляются так, чтобы в левом верхнем углу был наибольший по модулю коэффициент a_ik, i = k, k + 1, …, n. После этой перестановки исключение переменной x_k производят, как в схеме единственного деления.

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

Пример 3.2.

Применим метод исключения Гаусса с выбором главного элемента по столбцу для решения системы уравнений (3.10) из примера 3.1. Прямой ход. 1-ый шаг. Так как коэффициент a₁₁ = 2.0 наибольший из коэффициентов первого столбца, перестановки строк не требуется и 1-ый  шаг полностью совпадает с 1-ым шагом примера 3.1.  Из второго, третьего и четвертого уравнений исключается переменная x₁ и система приводится к виду (3.11).

2-ой шаг. Наибольший  по модулю коэффициент при x₂ в системе (3.11) a = –1.15. Поэтому переставим уравнения следующим образом:

 

2.0x₁ + 1.0x₂  –     0.1x₃ +      1.0x₄  =  2.7

–1.15x₂ + 1.015x₃ + 5.05x₄ = – 4.305                                             (3.14)

0.3x₂ +   4.02x₃  –   8.70x₄  =  21.36

– 0.30x₂ +   2.55x₃ –   1.50x₄  =  8.55

 

Вычислим множители:

 

m = = =  –0.26087     m = = = 0.26087.

 

Вычитая из третьего и четвертого уравнений системы (3.14) второе уравнение, умноженное соответственно на m и m , приходим к системе:

 

2.0x₁ + 1.0x₂  – 0.1x₃ + 1.0x₄  =  2.7

–1.15x₂ + 1.015x₃ + 5.05x₄ = – 4.305                                             (3.15)

4.28478x₃  –  7.38261x₄  =  20.23696

2.28522x₃ – 2.81739x₄  =  9.67305

 

3-ий шаг. Вычислим  множитель:

 

m = = = 0.53333.

 

Вычитая из четвертого уравнения системы (3.15) третье, умноженное на m , приведем систему к треугольному виду:

2.0x₁ + 1.0x₂  – 0.1x₃ + 1.0x₄  =  2.7

–1.15x₂ + 1.015x₃ + 5.05x₄ = – 4.305                                            (3.16)

4.28478x₃  –  7.38261x₄  =  20.23696

1.11998x₄  =  –1.11998

 

Обратный ход. Обратный ход полностью совпадает с обратным ходом примера 3.1. Решение системы имеет вид:

 

x₁ = 1.000, x₂ = 2.000, x₃ = 3.000, x₄  =   – 1.000.

 

3.4 Вычисление  определителя методом исключения Гаусса

 

Из курса линейной алгебры известно, что определитель треугольной матрицы равен произведению диагональных элементов. В результате метода исключений Гаусса система линейных уравнений (3.2) с квадратной матрицей A приводится к эквивалентной ей системе (3.8) с треугольной матрицей A_n. Поэтому

 

det A = (–1)^s det A_n,

 

где s – число перестановок строк, (s = 0, если использовался метод  Гаусса по схеме единственного деления).Таким  образом,

 

det A = (–1)^s a₁₁ a a …a                                                           (3.17)

 

Итак, для вычисления определителя det A необходимо выполнить процедуру прямого хода в методе Гаусса для системы уравнений Ax = 0, затем найти произведение главных элементов, стоящих на диагонали треугольной матрицы и умножить это произведение на (–1)^s, где s – число перестановок строк.

Пример 3.3.

Вычислим определитель det A =

2.0    1.0   0.1    1.0

0.4    0.5    4.0    8.5

0.3    1.0    1.0    5.2

1.0    0.2    2.5    1.0

 

Данный определитель совпадает с определителем системы, рассмотренной в примере 3.1. Он равен  произведению диагональных элементов  треугольной матрицы (3.13):

 

det A = 2.0 × 0.30 × 16.425 × 1.12 = 11.0376.

 

Если же обратиться к  примеру 3.2, то, учитывая, что была одна перестановка строк, т.е. s = 1, получим:

 

det A = (–1) × 2.0 × (–1.15)  × 4.28478 × 1.11998 = 11.0375.

 

3.5 Вычисление  обратной матрицы методом исключения  Гаусса

 

Обратной матрицей к матрице A называется матрица A^-1, для которой выполнено соотношение:

 

A A^-1 = E,                                                                                          (3.18)

 

где E – единичная матрица:

 

1   0   0  …  0   

0   1   0  … 0

E = 0   0   1  … 0   .                                                                       (3.19)