6.5. Прямые методы решения систем линейных уравнений с исключением неизвестных. Метод Гаусса

Рассмотрим квадратную систему линейных уравнений порядка n:

(6.12)

Эквивалентными преобразованиями уравнений называют такое изменение их формы, при котором сохраняются их решения. Для систем уравнений (не только линейных), в частности, эквивалентными преобразованиями являются следующие.

1. Сложение или вычитание уравнений.

2. Умножение или деление всех членов уравнения на постоянное ненулевое число.

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

Основная идея метода исключения состоит в том, что за счет эквивалентных преобразований уравнений системы (6.12) в ней:

1) из уравнений системы с номерами 2,...,n устраняется неизвестное х₁

2) из уравнений системы с номерами 3,...,n - неизвестное х₂,

3) из уравнений системы с номерами 4,...,n - неизвестное х₃ и т.д.

При этом в матрице системы под главной диагональю обнуляются 1) элементы столбца 1; 2) элементы столбца 2; 3) элементы столбца 3 и т.д., т.е. матрица последовательно приводится к верхнему треугольному виду.

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

Метод исключения Гаусса содержит два основных этапа эквивалентных преобразований уравнений системы:

1) прямой ход – приведение исходной матрицы к треугольному виду за счет последовательного исключения неизвестных из уравнений системы и

2) обратный ход – приведение полученной матрицы к диагональному виду также за счет последовательного исключения неизвестных.

В качестве операций, определяющих скорость выполнения алгоритма приняты: 1) сравнение, 2) сложение и вычитание,3) умножение, 4) деление. Числа операций данных операций для задачи размерности n обозначим как c(n), s(n), m(n), d(n). В дальнейшем при расчете чисел операций и оценке сложности будем рассматривать случай, когда система имеет единственное решение, т.е. определитель матрицы А не равен нулю. При этом достигается максимальная сложность алгоритма.

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

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

1) существует ли единственное решение системы,

2) в случае положительного ответа на первый вопрос – привести матрицу системы к треугольному верхнему виду таким образом, чтобы погрешности вычислений были минимально возможными.

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

Для минимизации вычислительной погрешности в каждой строке матрицы i (1in-1) выбирается элемент с максимальным модулем. Его называют главным элементом строки и путем перестановки порядка неизвестных помещают данный элемент на главную диагональ матрицы. Для контроля текущего положения неизвестных в уравнениях системы введем целочисленный вектор порядка неизвестных Р. Каждый его элемент p_i задает текущий номер столбца матрицы A, который соответствует неизвеcтному x_i исходной системы уравнений.

Для проверки наличия нулевой строки в матрице системы необходимо дополнительно рассмотреть малое положительно число  > 0, учитывающее точность задания исходных коэффициентов системы, погрешности вычислений, порядок системы. Условие приближенного равенства нулю главного элемента m_i строки i имеет вид  m_i < .

Если оно выполняется, то это означает, что путем эквивалентных преобразований в матрице системы выделена практически нулевая строка и из свойств определителя следует: det(A)=0. При этом система не имеет единственного решения.

Прямой ход можно представить в виде последовательного выполнения начальных присваиваний и шагов с номерами i (1in), на которых обрабатываются элементы строки i, лежащие на главной диагонали и правее ее, а также все аналогичные элементы нижележащих строк i +1,..., n.

Начальные присваивания. Всем элементам p_i вектора порядка неизвестных Р. присваиваем значения, равные i (1in): p_i:= i.

Шаг i (1in) включает выполнение следующих действий.

1. Поиск главного элемента m_i строки i. Для него также фиксируется номер столбца j_mi. Если модуль m_i мал (m_i< ), то определитель матрицы близок к нулю и полагаем, что решение системы не существует, выход из алгоритма с отрицательным ответом.

Если же модуль значения главного элемента m_i равен или превышает , то продолжаем выполнение алгоритма.

Общее число сравнений для строки i равно (n - i +1).

2. При (j_mi  i) в матрице А меняем местами столбцы с номерами j_mi и i, а в вектореР меняем местами значения соответствующих элементов: p_i  p_jmi .

3. Преобразование нижележащих строк матрицы и элементов вектораВ с номерами k = i +1,..., n для обнуления элементов столбца i, лежащих под главной диагональю. Для этого вначале рассчитывается отношение (-a_ki/a_ii), затем на него умножаются все элементы i-строки от i до n, после чего складываются все элементы строк i и k в столбцах с номерами от (i+1) до n. Также на отношение (-a_ki/a_ii) умножается элемент b_i свободного столбца и складывается с элементов b_k, после чего получается новое значение элемента b_k: b_k :=b_k + (-a_ki/a_ii) b_i .

Для каждой строки k и соответствующего элемента свободного вектора затрачиваем операции: сложений и умножений - по (n-i)+1; делений 1. Поскольку ниже строки i лежит (n-i) строк, то общее число затрачиваемых операций при обработке строки i и всех нижележащих cтрок равно:

- сравнений: c_i(n) = (n-i+1);

- сложений и умножений: s_i(n) = d_i(n) = (n-i)((n-i)+1)= (n-i)²+(n-i) ;

- делений: m_i(n) =1*(n-i) = (n-i).

Исходная система уравнений (6.12) после выполнения эквивалентных преобразований при прямом ходе в случае ненулевого определителя матрицы примет вид:

(6.13)

Трудоемкость прямого хода. Суммируя числа операций по всем строкам с номерами i (1in), получаем, что при выполнении прямого хода метода Гаусса затрачивается следующее количество операций рассмотренного вида (c_пр(n), s_пр(n), m_пр(n), d_пр(n)):

- сравнений: c_пр(n) = n +(n-1)+ …+1 = n(n+1)/2;

- сложений и умножений: s_пр(n) = m_пр(n) = [(n-1)²+(n-2)²+…+1²+0²]+[(n-1)+(n-2)+…+1+0] = (n-1)n(2n-1)/6 + n(n+1)/2 = n (n²-1)/3;

- делений: d_пр(n) = (n-1)+(n-2)+ …+0 = n(n-1)/2.

Выполненные оценки показывают, что сложность прямого хода – кубическая О(n³).

Обратный ход. Задача – путем эквивалентных преобразований системы уравнений выполнить обнуление всех элементов матрицы А, лежащих выше главной диагонали. Строки матрицы i и компоненты свободного вектора обрабатываются в обратном порядке - от i=n до i=1.

По аналогии с прямым ходом вначале рассмотрим обработку произвольной строки с номером i и всех строк, лежащих выше нее (от k=i-1 до k=1), а также соответствующих компонент свободного вектора. При обработке каждой строки k вначале определяется отношение (-a_ki/a_ii). Затем на него умножается элемент b_i свободного столбца и складывается с элементов b_k, после чего получается новое значение элемента b_k: b_k :=b_k + (-a_ki/a_ii) b_i .

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

(6.14)

Разделив все элементы свободного вектора B на соответствующие диагональные элементы матрицы А: х_i := b_i /a_ii ; (1 ≤ i ≤ n), получим решение системы, в котором неизвестные переставлены согласно векторуР. При этом дополнительно будет выполнено n делений.

Искомые решения {х_i } исходной системы (6.12), получаем, переставляя полученные после обратного хода значения { х_i } с учетом компонент вектора порядка неизвестных Р:

х_i :=х _pi ; (1 ≤ i ≤ n).

Трудоемкость обратного хода. Суммируя числа операций по всем строкам с номерами i (1in), с учетом дополнительных n операций деления получаем, что при выполнении обратного хода затрачивается следующее количество операций:

- сравнения: c_обр(n) =0;

- сложения и умножения: s_обр(n) = d_обр(n)) = (n-1) + (n-2) +…+ 0 = n(n-1)/2;

- деления: d_обр = s_обр(n) + n = n(n-1)/2 + n = n(n+1)/2.

Сложность обратного хода – квадратическая О(n²).

Трудоемкость и сложность алгоритма метода Гаусса. Суммируя числа операций для прямого и обратного ходов, получим числа операций для всего алгоритма:

- сравнения: c(n) = с_пр(n) + с_обр(n) = n(n+1)/2;

- сложений и умножений: m(n) = s(n) = s_пр(n) + s_обр(n) = n (n²-1)/3 + n(n-1)/2 = n(n-1)(2n+5)/6;

- делений: d(n) = d _пр(n) + d_обр(n) = n(n-1)/2 + n(n+1)/2 = n².

Наиболее быстро растут числа сложений и умножений – как n³/3. Сложность алгоритма – кубическая О(n³).

При одинаковой сложности метод Гаусса затрачивает примерно в 3 раза меньше операций сложения и умножения по сравнению с методом, использующим обращенную матрицу (п.6.4.). Следовательно, он более оптимален по трудоемкости.

Пример 1. Применить метод Гаусса для решения системы уравнений из примера 1 п.6.4.

Решение. Для более краткой записи решения по методу Гаусса матрицу системы и ее свободный вектор записывают рядом в расширенной матрице A_p.

Прямой ход.

1. Начальное присваивание. В вектор порядка неизвестныхР заносим значения: p₁:= 1, p₂:= 2, p₃:= 3.

2. Обработка строки 1. Так как в первой строке матрицы системы максимальный по модулю (главный) элемент стоит на главной диагонали, структуру системы сохраняем.

Вторую строку расширенной матрицы складываем с первой, умноженной на коэффициент (-а₂₁/а₁₁) = 5/4 =1,2; третью складываем с первой, умноженной на коэффициент (-а₃₁/а₁₁) = 6/4 =1,5. В результате получим новый вид расширенной матрицы A_p1:

3. Обработка строки 2. Максимальный по модулю (главный) элемент второй строки стоит в третьем столбце. Меняем местами второй и третий столбцы матрицы A_p1 (обозначим матрицу A_p1), в векторе переставляет местами второй и третий элементы: Р = (1,3,2). Третью строку расширенной матрицы складываем со второй, умноженной на коэффициент (-а₃₂/а₂₂) = 6/47. В результате после завершения прямого хода получим расширенную матрицу A_пр следующего вида:

Обратный ход.

1. Обнуление элементов столбца 3, стоящих над главной диагональю: вторую строку расширенной матрицы складываем с третьей, умноженной на коэффициент (-а₂₃/а₃₃) = -141/112; первую складываем с третьей, умноженной на коэффициент (-а₁₃/а₃₃) = 47/28. В результате получим расширенную матрицу A_p3:

2. Обнуление элементов столбца 2, стоящих над главной диагональю: вторую строку расширенной матрицы складываем с третьей, умноженной на коэффициент (-а₁₂/а₂₂) = -12/47. В результате получим расширенную матрицу A_обр, в которой матрица системы имеет диагональный вид:

Определение решения.

1. Разделив свободные коэффициенты на диагональные элементы матрицы, получим решение системы, в котором неизвестные переставлены согласно векторуР :

х₁:= b₁ /a₁₁ = 8/4 = 2;

х₂:= b₂ /a₂₂ = (-47/4)/(47/4) = -1;

х₃:= b₃ /a₃₃ = (28/47)/(28/47) = 1.

2. С учетом вектора порядка неизвестныхР = (1,3,2), находим искомое решение {х_i } исходной системы: х₁:= х_p1 = х₁ = 2; х₂:= х_p2 = х₃ =1; х₃:= х_p3 = х₂ = -1.

Вопросы для проверки знаний.

1. Какие преобразованиями уравнений называют эквивалентными ?

2. Какие эквивалентные преобразования используют при решении систем линейных уравнений ?

3. В чем заключается основная идея метода исключения ?

4. Из каких двух основных частей состоит метод Гаусса решения систем линейных уравнений ?

5. Назовите две основные задачи прямого хода метода Гаусса.

6. В чем заключаются главные задачи каждого шага прямого хода ?

7. К какому виду приводится система линейных уравнений после прямого хода ?

8. Будет ли матрица системы приведена к треугольному виду, если ее определитель равен нулю ?

9. В чем состоит задача обратного хода ?

10. К какому виду приводится система линейных уравнений после обратного хода?

11. Почему при одинаковой кубической сложности алгоритмов метод Гаусса решения систем линейных уравнений предпочтительнее метода, основанного на использовании обратной матрицы?

Практическое задание.

1. Решить методом Гаусса систему линейных уравнений: