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

 и его модификации.

 

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

Рассмотрим систему n линейных уравнений с n неизвестными

                                                  (1.1)

Предполагаем, что матрица A - (aij) системы невырожденная и тогда она имеет единственное решение. Систему (1.1) можно записать в матричной форме

Ax = b                                                                           (1.2)

где b = (b1, b2,…, bn)T -  вектор свободных членов, x = (x1, x2,…, xn)T - вектор неизвестных. Эффективность способов решения СЛАУ (1.1) зависит от структуры и свойств матрицы A.

Решение системы (1.1) можно найти по правилу Крамера , где d = det A, di получается d из заменой i - го столбца столбцом свободных членов системы. Но при вычислении определителей n - порядка потребуется порядка n!операций и метод Крамера неустойчив. Аналогичные недостатки имеет матричный способ уравнения (1.2) по формуле x = A-1 b.

Решим систему (1.1) по методу Гаусса, приведя ее к ступенчатому виду.

1 этап. Предполагаем, что a11 ¹ 0 (в противном случае переставим уравнения в системе местами). Разделим первое уравнение системы (1.1) на a11, в результате получим уравнение

.                             (1.3)

Затем из каждого из оставшихся уравнений вычитаем уравнение (1.3) умноженное на соответствующий коэффициент ai1. После этого приходим к равносильной ей системе.

 

 

 но такое решение приводит к вычислению определителей порядка

                                                      (1.4)

где .

2 этап. Предполагаем, что  ¹ 0, делим второе уравнение системы (1.4) на  и исключаем x3 из всех уравнений, начиная с третьего приходим к системе:

                                                      (1.5)

где .

Продолжая этот процесс исключения неизвестных мы придем от (1.1) к равносильной ей СЛАУ

                                                       (1.5)

Коэффициенты преобразованной системы на k-м шаге вычисляются по формулам

           (1.6)

Процесс сведения (1.1) к треугольной называется прямым ходом метода Гаусса.. Из системы (1.5) находим ее решения по формулам:

                                                        (1.7)

Нахождение решений по формулам (1.7) называется обратным ходом метода Гаусса.

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

При преобразовании СЛУ над контрольными суммами производят те же операции, что и над свободными членами уравнений. В результате этого контрольный элемент полученного уравнения равняется сумме коэффициентов этого уравнения.

В обратном ходе рассматривают вместе с системой Ax = b систему Ax* = KS, решения которой связаны с решениями исходно системы соотношением x*i = xi  +1, i = 1, 2,…, n.Если эти соотношения выполняются, то решение системы найдено правильно.

Пример. Решить по методу Гаусса систему

 

 

Шаг

 

Элементы матриц

Столбец

свободных

членов

Столбец

сумм

KS

xi

xi*

0

 

 

1

2

3

1

4

7

2

5

9

5

-1

-13

9

10

6

9

10

6

 

 

1

1

1

2

5

9

9

x1 = -39/2

x3* = -37/2

 

 

2

4

1

3

-11

-28

-8

-21

-8

-21

 

 

2

 

1

1/2

-11/2

-4

-4

x2 = -5/2

x3* = -3/2

 

 

 

1

-6

-5

-5

x3 = -6

x3* = -5

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


Блок-схема решения СЛУ метода Гаусса с постолбцовым выводом ведущего элемента:

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

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

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

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

Алгоритм метода Гаусса с постолбцовым выбором главного элемента:

Ввод: матрица A[i,j]системы порядка n, матрица b[i] свободны членов из n элементов.

Вывод: матрицу x[i] решения системы.

   {Прямой ход метода Гаусса}

 Цикл по k: =1, 2, …,n-1 выполнять

      {Выбор главного элемента в k -м столбце}           

        i0:= k, i:= k; c:= |A[i0 ,k]|;

        2. Если  i < n, то i:= i+1 .Если с £ |A[i,k]|, то i0:= i,c:= |A[i ,k]|.

            Идти к 2.

        Если c = 0,то система не имеет решений. Конец.

              Иначе, если i0 <> k, то

                   {переставляем i0-ю и k-ю строки местамиi}

              Цикл по j: =k, …, n выполнять с: = A[k,j]; A[k,j]:= A[i0,j]; A[i0,j]:=c.; конец цикла по j.

                  с: = B[k]; B[k]:= B[i0]; B[i0]:=c

         {Деление k -го уравнения на главный элемент}

            Цикл по j: = k +1, …, n  A[k,j]:= A[k,j]/A[k,k]; конец цикла по j.

k:=k+1

 
           B[k]:= B[k]/A[k,k];

            {Элементарное преобразование}

          Цикл по i: = k +1, …, n выполнять B[i]:= B[i] -A[i,k]*B[k];

                 Цикл по j: = k +1, …, n выполнять  A[i,j]:= A[i,j] -A[i,k]*A[k,j]; конец цикла по j.

              конец цикла по i.

     Если A[n,n] = 0, то система не имеет решений. Конец.

     Иначе  {Обратный ход метода Гаусса}:

     X[n]:= B[n,n]/ A[n,n];

     Цикл по k: = n-1, …,1 выполнять

               X[k]:= B[k];

               Цикл по j: = k +1, …, n выполнять X[k]:= X[k] - X[j]*A[k,j]; конец цикла по j.

       Конец цикла по k.

Конец.