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

Под названием “метод Гаусса” фигурирует группа методов, объе­диненных идеей последовательного исключения неизвестных. Наи­более популярным является метод, основанный на так называемой схеме единственного деления; этот метод имеет также и ряд модификаций. Кроме решения систем уравнений метод Гаусса весьма эффек­тивен и для решения некоторых других задач.

Будем далее считать матрицу системы (3.1) невырожденной. Суть метода Гаусса состоит в преобразовании системы (3.1) к равносильной ей системе с треугольной матрицей, из которой затем последовательно (обратным ходом) получаются значения всех неизвестных. Сам по себе метод Гаусса относится к точным методам. Это означает, что если точно выполнять все требуемые в нем действия, то будет получено точное решение, поскольку по­грешность метода в данном случае равна нулю. Понятно, однако, что из-за вычислительных ошибок (включая ошибки округления, а также возможные ошибки исходных данных) этот идеал прак­тически недостижим.

Идея последовательного исключения неизвестных может быть реализована различными вычислительными схемами. Ниже рассматривается алгоритм, который полу­чил название схемы единственного деления.

Подвергнем систему (3.1) следующему преобразованию. Счи­тая, что (ведущий элемент), разделим на а ₁₁коэффициен­ты первого уравнения:

. (3.2)

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

Затем, оставив первое уравнение в покое, над остальными урав­нениями системы совершим аналогичное преобразование: выбе­рем из их числа уравнение с ведущим элементом и исключим с его помощью из остальных уравнений неизвестное х ₂. Повторяя этот процесс, вместо системы (3.2) получим равносильную ей систему с треугольной матрицей:

x₁+ x₂+ x₃+…+ x_n=

x₂+ x₃+…+ x_n= (3.3)

…………………………………

x_n=

Из системы (3.3) последовательно находят значения неизвест­ных .

Таким образом, процесс решения системы (3.1) по методу Га­усса распадается на два этапа. Первый этап, состоящий в последо­вательном исключении неизвестных, называют прямым ходом. Вто­рой этап вычислений — нахождение значений неизвестных — принято называть обратным ходом.

Процесс решения системы линейных уравнений по схеме един­ственного деления с контролем ручных вычислений рассмотрим на примере 3.1. Ручные вычисления по схеме единственного деле­ния удобно оформлять в виде специальной расчетной таблицы (табл. 3.1).

Пример 3.1. Решить систему линейных уравнений

2, 34х₁-4, 21х₂-11, 61x₃ = 14, 41;

8, 04 х₁+5, 22x₂+0, 27 х₃ = -6, 44;

3, 92 х₁-7, 99х₂+8, 37х₃ = 55, 56.

В раздел А табл.3.1 вносятся коэффициенты исходной системы и свободные члены. Для исключения случайных ошибок в схеме единственного деления предусматривается текущий конт­роль правильности вычислений; с этой целью в схему вычисле­ний включены столбец контрольных сумм и столбец строчных сумм S.

Контроль в прямом ходе основывается на следующей идее. После того как в раздел А внесены коэффициенты и свободные члены исходной системы, находят контрольные суммы — суммы коэф­фициентов и свободных членов по строкам — и вносят их в стол­бец (в табл. 3.1 это числа 0, 93; 7, 09; 59, 86).

Таблица 3.1

Раздел	х1	x2	x3	Свободные члены		S
А	2, 34 8, 04 3, 92	-4, 21 5, 22 -7, 99	-11, 61 0, 27 8, 37	14, 41 6, 44 55, 56	0, 93 7, 09 59, 86
	-1, 799	-4, 962	6, 158	0, 397	0, 398
А1		19, 685 -0, 938	40, 161 27, 819	-55, 951 31, 420	3, 895 58, 302	3, 894 58, 302
		2, 040	-2, 842	0, 198	0, 198
А2			29, 732	28, 756	58, 488	58, 487
			0, 967	1, 967
В				0, 967 -4, 816 2, 293	1, 967 -3, 816 -3, 293

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

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

После нахождения контрольных сумм первым преобразовани­ем в схеме единственного деления является деление элементов первой строки (включая столбец ) на ведущий элемент 2, 34. За­пись результатов производится в четвертую строку раздела А. Здесь же впервые выполняют контроль: сравнивают результат обычно­го текущего преобразования контрольной суммы первой строки (все вычисления в табл. 3.1 для сокращения записей ведутся до трех знаков после запятой):

и строчную сумму: 1-1, 799-4, 962+6, 158=0, 398.

Расхождение в третьем знаке после запятой в данном случае объясняет­ся накоплением вычислительной ошибки в результате округлений.

Используя четвертую строку раздела А, можно приступить к преобразованию второй и третьей строк этого раздела (исключе­нию неизвестного х₁ из 2-го и 3-го уравнений системы). Результа­ты этих преобразований образуют соответственно первую и вто­рую строки раздела А₁. Эти преобразования выполняют по следу­ющему правилу: каждый элемент первой строки раздела А₁ равен разности соответствующего элемента второй строки раздела А и произведения его “проекций” на первый столбец и последнюю строку раздела А; аналогичным способом вторая строка раздела А₁ получается из третьей строки раздела А.

Например, для вычисления первого элемента первой строки раздела А₁ берется элемент 5, 22 из второй строки раздела А и изнего вычитается произведение 8, 04•(-1, 799), т.е. 5, 22+8, 04•1, 799=19, 6848 19, 685. Аналогично второй элемент второй строки раз­дела А₁ образуется вычитанием из числа 8, 37 произведения 3, 92•(-4, 962), т.е. 8, 37 + 3, 92•4, 962=27, 8191 27, 819.

В общем случае, если b — вычисляемый элемент нового разде­ла, а — соответствующий элемент предыдущего раздела, причем и — соответственно его вертикальная и горизонтальная “про­екции”, можно записать формулу b=а-р_вр_г. После заполнения каждой строки нового раздела производится контроль.

Третья строка раздела А₁ образуется делением первой строки на ведущий элемент 19, 685, после чего аналогичным образом за­полняются строки раздела А₂.

Разделом А₂ заканчивается прямой ход. В столбце свободных членов последней строки этого раздела уже получено значение неизвестного х₃ =0, 967. Значения остальных неизвестных последовательно находят вычитанием из свободных членов соответствую­щих строк прямого хода, начинающихся с единицы, суммы про­изведений их коэффициентов на соответствующие значения ра­нее найденных неизвестных.

Так, для получения х₂ проделывают вычисления:

х₂ =-2, 842-2, 040•0, 967=-4, 8157 -4, 816.

Процесс нахождения неизвестных составляет обратный ход (раз­дел В в табл. 3.1). Контроль в обратном ходе ведется путем сравне­ния значений неизвестных, получаемых в столбце свободных чле­нов, с соответствующими числами из столбца (они образуются в результате действий, аналогичных действиям по нахождению значений неизвестных, с той разницей, что вместо свободных членов используются соответствующие числа из столбца ). Суть контроля состоит в том, что при безошибочном выполнении вы­числений числа в столбце должны быть ровно на единицу больше соответствующих значений неизвестных из столбца свободных членов. Этот эффект имеет простое обоснование. Введя в вычисления столбец и проделывая с его элементами те же действия, что и с элементами столбца свободных членов, мы фактически с самого начала наряду с решением исходной системы параллельно решали вторую систему, у которой свободные члены образованы из свободных членов исходной системы, сложенных с коэффициентами соответствующих уравнений. Очевидно, что решениями второй системы должны быть числа, на единицу большие значе­ний неизвестных исходной системы.

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

2, 34•2, 293-4, 2•(-4, 816) - 11, 6•0, 967 =14, 411;

8, 04•2, 293 + 5, 22•(-4, 816) + 0, 27• 0, 967 = -6, 441;

3, 92•2, 293-7, 99•(-4, 816) + 8, 3 •0, 967 = 55, 562.

Значения разностей между свободными членами исходной си­стемы и результатами подстановки в уравнения системы найден­ных значений неизвестных называют невязками. В рассмотренном примере невязки имеют следующие значения:

=14, 41-14, 411 = -0, 001;

=-6, 44-(-6, 441) = 0, 001;

=55, 56-55, 561 = 0, 001.

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

Обозначим приближенные значения неизвестных, полученные в ходе решения системы, как (i =1, 2, …, n). Исходная система имеет вид Ax=b; если же в нее подставить вместо х, то в правой части вместо b фактически окажется некоторое : . Вычитая одну систему из другой, получим (правая часть последнего равенства и есть невязка ). Рассматривая как неизвестную величину у и решая систему уравнений Ау = полу­чим новое приближение к точному решению: , где реально полученное (т.е. приближенное) решение новой системы. Таким образом, можно последовательно уточнять решения системы, полученной методом Гаусса. На самом деле именно компоненты вектора (а не невязки) и позволяют судить о точности приближенного решения.