8. Метод Гаусса решения системы линейных уравнений и его модификации.

 

Дана система уравнений  (1). Будем считать, что матрица системы  Анеособенная. Требуется найти решение системы – вектор Х*.   

 

Метод Гаусса - это метод исключения. На k-ом  шаге осуществляется исключение неизвестной  из уравнений с номерами  i > k, k = 1,…n -1. В результате, за  n -1 шаг матрица   А  приводится к верхнему треугольному виду (прямой ход). Система приобретает вид:

 

 

 

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

 

Схема единственного деления

Для удобства вычислений используют расширенную матрицу (), (n+1)-й столбец которой –  столбец свободных членов системы - b:

.

 

 

 

 

 

Прямой ход.  На каждом из шагов с номерами k = 1, …, n-1 выбираем ведущую строку с номером  k  и ведущий элемент. Далее выполняем следующие операции.

 

            1). Все элементы ведущей строки расширенной матрицы  делим на  :

      .                                                       (2)

            2). Из всех строк расширенной матрицы с номерами i > k вычитаем ведущую строку, умноженную на элемент , получая нули под ведущим элементом: 

.                                         (3)

            3). Увеличиваем  номер  ведущей  строки:     k = k +1   и, если k < n, повторяем 1), 2).  Если   k = n, то прямой ход закончен.

 

Обратный ход.  По формулам

                          (4)

находим решение системы   T . Для оценки точности найдем вектор невязки ,  где       и  вычислим его норму  .

Схема единственного деления чувствительна к так называемым провалам главных миноров (если на k-том шаге прямого хода , то алгоритм не работает, а если близок к нулю, то возникает большая вычислительная погрешность). Поэтому на практике используют схемы с выбором главного элемента.

 

Схемы с выбором главного элемента

 

1.      Схема с выбором главного элемента без перестановки столбцов.

 

На каждом из  n -1   шагов прямого хода метода выбирают главный элемент как максимальный по модулю среди элементов  соответствующего столбца преобразованной матрицы, расположенных на главной диагонали матрицы и ниже:   ,  затем осуществляется перестановка уравнений системы (строк расширенной матрицы) так, чтобы строка с номером  заняла k-е место, стала ведущей. После перестановки осуществляются расчеты по формулам (2)-(3) и переход к следующему шагу.

 

2. Схема с выбором главного элемента с перестановкой столбцов.

 

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

 

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