Численные методы линейной алгебры

Глава 2. Прямые методы решения систем линейных

алгебраических уравнений

Итак, требуется решить систему линейных алгебраических уравнений

Ax=b. (2.1)
Заметим, что везде речь будет идти только о случае когда матрица А – квадратная, т.е. число уравнений совпадает с числом неизвестных, причем будет предполагаться, что система (2.1) имеет единственное решение.
Методы решения (2.1) можно разделить на две группы: прямые методы (в которых нахождение решения заканчивается за конечное число действий), итерационные методы (в которых находятся не само решение, а некоторая последовательность векторов х^(к) такая, что ).


2.1. Метод Гаусса

Рассмотрим классический метод Гаусса [2-11]. Сначала перепишем систему (2.1) в развернутой форме

(2.2)
Пусть а₁₁0. Если а₁₁=0, то поменяем местами первое и второе уравнения в (2.2), если а₂₁0, то поменяем местами первое и третье уравнения и т.д. Все a_i1 не могут равняться нулю, так как detA0. Тогда из первого уравнения системы (2.2) будем иметь
х₁+₁₂х₂+…+_1nх_n=₁ , (2.3)
где _1j=a_1j/a₁₁ , (j>1), ₁=b₁/a₁₁ .
С использованием уравнения (2.3) можно исключить х₁ из всех оставшихся уравнений (2.2). В результате получим
(2.4)
где =a_ij-a_i1_1j , =b_i- a_i1₁ , (i, j2).
На этом первый этап процесса исключения заканчивается. Индекс (1) в коэффициентах , показывает номер первого этапа.
Переходя к второму этапу процесса исключения разделим первое уравнение в (2.4) на при 0, тогда получим
х₂+₂₃х₃+…+_2nх_n=₂ , (2.5)
где _2j= / , (j>2), ₂= / .
Далее с помощью уравнения (2.5), описанным выше способом, исключим все х₂ из уравнений (2.4).
Продолжая далее, на к-ом этапе будем иметь уравнение, с помощью которого исключим к-ое неизвестное, т.е.
х_к+_{к к+1}х_к+1+…+_кnх_n=_k , (2.6)
где _кj= / , (jк+1), _к= / , (2.7)
= - _кj , = - _к , (i, jк+1). (2.8)
Собирая уравнения (2.3)-(2.6), полученных на всех этапах получим систему уравнений с верхней треугольной матрицей
х₁+₁₂х₂+₁₃х₃+…+_1nх_n=₁ ,
х₂+₂₃х₃+…+_2nх_n=₂ , (2.9)
………………………
х_n=_n .
Таким образом, алгоритм решения СЛАУ классическим методом Гаусса состоит из двух шагов:

1. 
   первый – прямой ход.
   

По формулам (2.7), (2.8) вычисляются коэффициенты _ij и _i (i, j=1,…, n).

2. 
   второй – обратный ход.
   

Определяются неизвестные x_i по формуле (2.9), которую можно записать в виде
x_i=_i - , (i=n, n-1,…,1).


Определение 2.1. Элементы а₁₁, , …, ,… называются ведущими элементами.