Методы решения СЛАУ. Метод Гаусса

  2. Анализ существующих методов решения задачи 

  Прямые  методы решения СЛАУ. К прямым (или точным) методам решения СЛАУ относятся алгоритмы, которые в предположении, что вычисления ведутся без округлений, позволяют получить точное решение системы за конечное число арифметических действий. Чаще всего решение задач такими методами осуществляется поэтапно: на первом этапе систему преобразуют к тому или иному простому виду, на втором - решают упрощенную систему и получают значения неизвестных.

  Запишем систему линейных алгебраических уравнений  в развернутом виде: 

                                                       (2.1) 

  где x₁, x₂,..., x_n - неизвестные величины, b₁, b₂,..., b_n - элементы правой части. Если определитель системы отличен от нуля, то она имеет единственное решение. Для удобства дальнейших преобразований обозначим элементы правой части а_i(n+1) и запишем расширенную матрицу размерами n´(n+1), которая содержит всю информацию о системе:  

  A =                                                  (2.2) 

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

  Приведем  формальное описание схем некоторых прямых методов.

1. Метод Гаусса (схема единственного деления). Алгоритм метода состоит из двух этапов. Первый этап называется прямым ходом метода и заключается в последовательном исключении неизвестных из уравнений, т.е. в приведении матрицы А к верхнему треугольному виду (ниже главной диагонали все нули). Для этого на первом шаге разделим первое уравнение системы на а₁₁ (предположим, что коэффициент а₁₁ ¹ 0, в противном случае осуществляем перестановку уравнений системы). Обозначим коэффициенты полученного приведенного уравнения , домножим его на коэффициент а₂₁ и вычтем из второго уравнения системы, исключая тем самым х₁ из второго уравнения (обнуляя коэффициент а₁₂ матрицы). Поступим аналогично с остальными уравнениями и получим новую систему, матрица которой в первом столбце, кроме первого элемента, содержит только нули, т.е.

 

                                                   (2.3) 

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

                   ( 2.4) 

  и матрицу  размерами (n - k) (n - k+1), элементы которой вычисляются по формулам  

                (2.5)  

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

  Обратный  ход метода Гаусса заключается в последовательном определении компонент решения, начиная с х_n и заканчивая х₁, по следующим формулам: 

           (2.6) 

  Прямой  ход состоит из n - 1 шагов исключения.

  1-й  шаг. Целью этого шага является исключение неизвестного x₁ из уравнений с номерами i = 2, 3, …, n. Предположим, что коэффициент a₁₁ ¹ 0. Будем называть его главным элементом 1-го шага.

  Найдем  величины 

  q_i1 = a_i1/a₁₁   (i = 2, 3, …, n)                                                                         (2.7)  

  называемые  множителями 1-го шага. Вычтем последовательно из второго, третьего, …, n-го уравнений системы первое уравнение, умноженное соответственно на q₂₁, q₃₁, …, q_n1. Это позволит обратить в нуль коэффициенты при x₁ во всех уравнениях, кроме первого. В результате получим эквивалентную систему 

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

  a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾ ,

  a₃₂⁽¹⁾x₂ + a₃₃⁽¹⁾x₃ + … + a_3n⁽¹⁾x_n = b₃⁽¹⁾ ,                                                           (2.8)

  .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

  a_n2⁽¹⁾x₂ + a_n3⁽¹⁾x₃ + … + a_nn⁽¹⁾x_n = b_n⁽¹⁾ . 

  в которой a_ij⁽¹⁾ и b_ij⁽¹⁾ вычисляются по формулам 

  a_ij⁽¹⁾ = a_ij − q_i1a_1j    ,    b_i⁽¹⁾ = b_i − q_i1b₁                                                            (2.9) 

  2-й  шаг. Целью этого шага является исключение неизвестного x₂ из уравнений с номерами i = 3, 4, …, n. Пусть a₂₂⁽¹⁾ ≠ 0, где a₂₂⁽¹⁾ – коэффициент, называемый главным (или ведущим) элементом 2-го шага. Вычислим множители 2-го шага 

  q_i2 = a_i2⁽¹⁾ / a₂₂⁽¹⁾   (i = 3, 4, …, n)                                                                 (2.10) 

  и вычтем последовательно из третьего, четвертого, …, n-го уравнения системы второе уравнение, умноженное соответственно на q₃₂, q₄₂, …, q_m2. В результате получим систему 

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

              a₂₂⁽¹⁾x₂ +  a₂₃⁽¹⁾x₃ + … +  a_2n⁽¹⁾ =  b₂⁽¹⁾ ,                   (2.11)

                    a₃₃⁽²⁾x₃ + … +  a_3n⁽²⁾x_n =  b₃⁽²⁾ ,                      

  .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .                           

                    a_n3⁽²⁾x₃ + … +  a_nn⁽²⁾x_n =  b_n⁽²⁾ . 

  Здесь коэффициенты a_ij⁽²⁾ и b_ij⁽²⁾ вычисляются по формулам 

  a_ij⁽²⁾ = a_ij⁽¹⁾ – q_i2a_2j⁽¹⁾   ,    b_i⁽²⁾ = b_i⁽¹⁾ – q_i2b₂⁽¹⁾.                                                (2.12) 

  Аналогично  проводятся остальные шаги. Опишем очередной k-й шаг.

  k-й шаг. В предположении, что главный (ведущий) элемент k-го шага a_kk^(k–1) отличен от нуля, вычислим множители k-го шага 

  q_ik = a_ik^(k–1) / a_kk^(k–1)   (i = k + 1, …, n)                                                           (2.13) 

  и вычтем последовательно из (k + 1)-го, …, n-го уравнений полученной на предыдущем шаге системы k-e уравнение, умноженное соответственно на q_k+1,k, q_k+2,k, …, q_nk.

  После (n - 1)-го шага исключения получим систему уравнений 

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

              a₂₂⁽¹⁾x₂ + a₂₃⁽¹⁾x₃ + … + a_2n⁽¹⁾x_n = b₂⁽¹⁾ ,                           (2.14)

                    a₃₃⁽²⁾x₃ + … + a_3n⁽²⁾x_n = b₃⁽²⁾ ,

        .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .   .

                                a_nn^(n–1)x_n = b_n^(n–1) . 

  матрица A^(n-1) которой является верхней треугольной. На этом вычисления прямого хода заканчиваются.

  Обратный  ход. Из последнего уравнения системы находим xn. Подставляя найденное значение x_n в предпоследнее уравнение, получим x_n–1. Осуществляя обратную подстановку, далее последовательно находим x_n–1, x_n–2, …, x₁. Вычисления неизвестных здесь проводятся по формулам 

  x_n = b_n^(n–1) / a_nn^(n–1),                                                                                        (2.15)

  x_k = (b_n^(k–1) – a_k,k+1^(k–1)x_k+1 – … – a_kn^(k–1)x_n) / a_kk^(k–1), (k = n – 1, …, 1). 

  Необходимость выбора главных элементов. Заметим, что вычисление множителей, а также обратная подстановка требуют деления на главные элементы a_kk^(k–1). Поэтому если один из главных элементов оказывыется равным нулю, то схема единственного деления не может быть реализована. Здравый смысл подсказывает, что и в ситуации, когда все главные элементы отличны от нуля, но среди них есть близкие к нулю, возможен неконтролируемый рост погрешности.

2. Метод Гаусса с выбором главного элемента. Метод заключается в том, что при прямом ходе в алгоритме метода Гаусса на каждом шаге исключения производится выбор наибольшего по модулю элемента в качестве ведущего. Этого достигают перестановкой строк или столбцов матрицы коэффициентов. Наиболее распространённой в вычислительной практике является стратегия выбора главного элемента столбца - нахождение максимального по модулю элемента k-го столбца матрицы и использование его в качестве ведущего элемента на k-м шаге исключения. В этом случае для невырожденных систем гарантируется, что ведущие элементы не равны нулю, и уменьшается погрешность при делении и последующем вычитании при преобразованиях. Рекомендуется также масштабировать предварительно каждое уравнение исходной системы, разделив на его наибольший по абсолютной величине коэффициент. Это делает рост элементов промежуточных матриц ограниченным.

  В методе Гаусса с выбором главного элемента по столбцу гарантируется, что |q_ik| ≤ 1 для всех k = 1, 2, …, n – 1 и i = k + 1, …, n. Отличие этого варианта метода Гаусса от схемы единственного деления заключается в том, что на k-м шаге исключения в качестве главного элемента выбирают максимальный по модулю коэффициент a_ikk при неизвестной x_k в уравнениях с номерами i = k + 1, …, n. Затем соответствующее выбранному коэффициенту уравнение с номером i_k меняют местами с k-м уравнением системы для того, чтобы главный элемент занял место коэффициента a_kk^(k-1). После этой перестановки исключение неизвестного x_k производят, как в схеме единственного деления. 

  

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