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

Напомним метод Гаусса решения системы линейных уравнений Ах=b. Для простоты, будем считать А невырожденной матрицей, и все ее угловые миноры отличны от нуля. Положим , . Матрицу коэффициентов при неизвестных на k-ом шаге обозначим через А(k), правые части уравнений — через b(k), матрицу — через . На k-1 шаге система уравнений имеет вид:

Из предложения о невырожденности угловых миноров А следует .

Итерация метода Гаусса заключается в исключении из всех уравнений, кроме k-го, переменной . Для этого из i-го уравнения, где i=1,…,n, i≠k, вычтем k-ое уравнение, умноженное на . Таким образом, , и , при . Или, что тоже самое , и .

Рациональный вариант метода Гаусса, его трудоемкость

Выразим элементы через элементы исходной системы . Для этого обозначим через минор матрицы , расположенный на пересечении строк и столбцов . На k-ом шаге ко всем строкам матрицы прибавлялись k-ая строка с некоторыми коэффициентами. Следовательно, любой минор, матрицы , содержащий k-ую строку, не изменяется на k-ой итерации алгоритма. Таким образом, каждый минор матрицы , содержащий первые k-строк, совпадает с соответствующим минором матрицы . Обозначим через множество номеров 1,2,…,k. В силу сказанного выше, справедливы равенства , , при i,j>k, и при , j>k. Матрица - диагональная, - верхнетреугольная, - отличается от диагональной матрицы только i-ым столбцом. Во всех случаях, их определитель равен произведению элементов, расположенных на главной диагонали. Тем самым установлены тождества , при i,j>k, и при , j>k. Все элементы матрицы , расположенные в первых k столбцах матрицы и не лежащие на главной диагонали, равны нулю. Следовательно, элементы матрицы , расположенные в первых k столбцах, на k-ой итерации метода Гаусса не изменятся. В частности, , где , и . Подставим полученное равенство в установленные ранее тождества, выведем равенства , при i,j>k, и при , j>k. Преобразуем полученные равенства к виду , при i,j>k, и при , j>k.

Ниже нам понадобится неравенство Адамара для определителя матрицы A

Заметим, что из полученных формул следует, что все промежуточные величины в методе Гаусса, ограничены сверху полиномом от длины входной информации. Пусть элементы — целые числа, не превосходящие по абсолютной величине α. Тогда любой минор k-го порядка этой матрицы, по неравенству Адамара, не превосходит . Таким образом, числитель и знаменатель элементов не превосходит , и длина не больше 2n(log α + log n). Отметим, эти рассуждения верны, если числитель и знаменатель каждого рационального числа сокращать на их наибольший делитель. Число элементарных арифметических операций метода Гаусса . Общая трудоемкость метода получается .

Полностью целочисленный вариант метода Гаусса

Данная трудоемкость получается при использовании рациональной арифметики. Однако, можно обойтись и без использования рациональной арифметики. Отметим, что общий знаменатель i-ой строки матрицы равен при i>k и при i≤k. Помножив каждую строку матрицы на ее общий знаменатель, получим целочисленную матрицу .

Выведем формулы пересчета от матрицы к . Величина равна при i>k, при i=k, и при i<k. Отметим, что . По формулам пересчета от матрицы к выводим, при i>k, при i<k, и . Подставим в эти формулы вместо элементов матрицы их выражение через элементы матрицы получим равенства при , и .

Из вышесказанного вытекает следующий вариант метода Гаусса:

d:=1 {ячейка для хранения }

k:=1 {номер итерации}

F:=true {признак невырожденности матрицы}

while (k<=n) and F do begin

if A[k, k]=0 {проверка ведущей строки}

then begin

i:=k+1;

while (i<=n) and (A [i,k]=0) do i:=i+1;

if i<=n {ведущая строка найдена}

then begin j:=k; {перестановка строк i и k}

while j<=n do begin c:=A[i,j]; A[i,j]:=A[k,j]; A[k,j]:=c; j:=j+1; end;

c:=b[i]; b[i]:=b[k]; b[k]:=c; end

else F:=false; {матрица вырождена}

end;

if F

then begin {k-ая итерация}

i:=1; {номер строки}

while i <=n do begin

if i <>k

then begin

for j:=k+1 to n do A[i,j]:=(A[i,j]xA[k, k]-A[k,j]xA[i,k])/d;

b[i]:=(b[i] x A[k,k] - b[k] x A[i,k])/d.

А[i,k]:=0;

A[i,i]:=A[k,k];

end;

i:=i+1; end;

end;

d:=A[k,k];

k:=k+1;

end;

Трудоемкость этого метода, при использовании самого быстрого алгоритма умножения, равна . Выигрыш, по сравнению с предыдущей версией алгоритма, здесь достигается за счет отказа от использования операции взятия наибольшего общего делителя чисел. Отметим, что после работы алгоритма, в ячейке d будет храниться определитель матрицы А. Если в качестве b взять столбцы единичной матрицы, то в качестве решения будут получаться столбцы присоединенной матрицы. Таким образом, трудоемкость нахождения обратной, присоединенной матрицы и определителя равна . Описанный алгоритм легко модифицируется для нахождения общего решения системы линейных уравнений Ах=b в общем случае, когда А — прямоугольная матрица.