К ОЦЕНКЕ ЭФФЕКТИВНОСТИ ЦЕЛОЧИСЛЕННОГО МЕТОДА ГАУССА
доцент Л.Р. Родкина, ВГУЭС, г. Владивосток
к.ф.-м.н., доцент А.Ф. Родкин, ДВФУ, филиал в г. Артеме

Целочисленный метод Гаусса (ЦМГ) был предложен авторами, в основном,  как представлялось, для разработки тренажерно-обучающих (компьютерных) программ по линейной алгебре. Цель заключалась в том, чтобы работа с такой вычислительной программой в точности соответствовала работе с такими же вычислениями в аудитории. Но первой операцией в стандартном методе Гаусса (МГ) является деление всех коэффициентов при неизвестных в первом уравнении  на коэффициент a11 при первой неизвестной x1, приводящее к появлению дробных элементов, чего мы избегаем на занятиях в аудитории. В алгебраической формулировке это означает, что, если (расширенная) матрица системы линейных уравнений (СЛУ) 
AX = B						(1)
целочисленная, то все вычисления надо проводить в целых числах, а решение  записывать в виде отношения двух целых чисел, т.е.  рациональным числом.
Обозначенную нами задачу можно сформулировать следующим образом. Пусть СЛУ (1) - целочисленная. В стандартном МГ решение системы (1) ищется в поле рациональных чисел Q. Поле рациональных чисел Q является абелевой (коммутативной) группой по сложению (+) и абелевой группой (исключая 0) по умножению (). Но для того, чтобы в процессе решения не было дробных чисел надо отказаться от операции деления - по второй операции умножения множество К (исключая 0) должно быть полугруппой с единицей, т.е. кольцом [1]. Сам же элемент 1 в кольце К может быть получен с помощью первой операции сложения (и обратной - вычитания) и второй - умножения.  Итак, для целочисленной СЛУ (1) в стандартном МГ решение ищется в поле рациональных чисел Q. В ЦМГ решение (преобразования) системы (1) проводится в кольце целых чисел (без операции деления), окончательный результат записывается рациональным числом (в виде отношения двух целых чисел) [2].
Эти соображения были воплощены в разработке алгоритма вычислений определителей целочисленных матриц по методу Гаусса [3] и реализованы в виде компьютерных программ. В работе [4] приведены функции на языке Clipper, реализующие алгоритм вычисления определителей целочисленных матриц по ЦМГ [3]. На этом же языке был разработан комплекс программ “Matrix” для решения основных задач линейной алгебры – решения систем линейных уравнений, вычисления определителей и обратных матриц по целочисленному методу Гаусса.
В результате работы и экспериментов с этими программами появилось понимание того, что такой подход к решению  СЛУ может быть использован не только в демонстрационно-тренажерных целях, но и для практических применений - практических вычислений по методу Гаусса, приводящих к отысканию  решений СЛУ любых (больших) размерностей и без известных в этой задаче проблем [5].
 К каким осложнениям приводит отказ от деления в стандартном методе Гаусса и замене его в ЦМГ многократными сложениями (вычитаниями) и умножениями для получения единицы?  В стандартном МГ единица получается очень просто - в одну (наиболее вычислительно-объемную) операцию деления. В ЦМГ единица может быть получена  в результате многократных сложений (вычитаний) и умножений. Но эта операция деления, делающая алгоритм метода Гаусса тривиально простым, приводит к появлению приближенных коэффициентов, накоплению ошибок и, следовательно, к проблеме  их контроля. 
Основной структурной единицей в ЦМГ является lk-итерация преобразования k-й строки с помощью разрешающего элемента ali l-й строки, введенная в [2]. Под lk - итерацией с разрешающим элементом ali (ali<aki) понимается элементарное преобразование элементов k-й строки, соответствующее делению элемента aki по модулю ali (для простоты считаем ali и aki положительными и ali<aki):
a'ki  = aki  - [aki /ali]* ali ,              				        (2)
где [aki /ali] – наибольшее целое число, не превосходящее aki /ali.
В результате применения одной итерации в рассматриваемом столбце получается элемент a'ki, по модулю меньший разрешающего элемента ali. Повторяем lk -итерацию к этой паре строк с разрешающим элементом a'ki. Результатом  проведения двух или более итераций в данной  паре строк будет появление нуля на месте одного из преобразуемых элементов i-го столбца (a'ki = 0, если ali = 1 или ali является делителем aki). Если получится 0, то в этой строке неизвестная xi  - исключена (локальная цель достигнута) и дальше процесс продолжается с наименьшим в этом столбце разрешающим элементом ali.  Если же  a'ki = 1 (или a'li = 1), то, переставляя строки так, чтобы диагональным элементом стала полученная единица a'ii = 1, придем к начальным условиям стандартного МГ.
Таким образом, вопрос о возможности использования ЦМГ в целях решения практических задач - решения систем линейных уравнений больших размерностей - связан с выяснением следующего обстоятельства: на сколько (или во сколько) затратнее операция вычисления единицы с помощью многократных сложений и умножений в кольце целых чисел К по сравнению с вычислением ее с помощью  единственной операции деления в поле рациональных чисел Q?
Рассмотрим детальнее процесс lk – итераций. Пусть преобразования по ЦМГ доведены до i-го столбца, т.е. во всех предыдущих столбцах ниже главной диагонали все элементы – нулевые,  все  неизвестные  с первой до (i-1) – исключены. Следующий шаг – с помощью диагонального элемента  aii  преобразовать все элементы, лежащие ниже, в нулевые.
1). Если aii  = 1, то, вычитая из  k-й строки  i-ю, умноженную на aki, получим в k-й строке 0 (аналогично (в цикле) и во всех строках, лежащих ниже i-й):
a'ki  = aki  - aii aki  = aki  - 1* aki = 0.
2). Если aii   1, то единица ищется среди элементов, лежащих ниже.  Если aki =1, то, переставляя i-ю и k-ю строки,   получим условие 1).
3). Общий случай - среди элементов, начиная с диагонального, единиц нет. Алгоритм ЦМГ состоит в следующем. Из всех этих элементов выбирается минимальный по величине и (после перестановки строк, если требуется) этот элемент устанавливается диагональным. Так как, после этого aii  - наименьший по величине, то к любой строке k ниже i-й можно применять lk -итерации (точнее ik –итерации и первой среди них будет k = i+1 строка). В результате первой ik –итерации, соответствующей делению  элемента aki  по модулю aii  (0 < aii <aki)), получим:
a'ki  = aki  - [aki /aii]* aii ,
где a'ki – остаток от деления:   0  a'ki    aii – 1.
Переставляя i-ю и k-ю строки,  придем к условию: диагональный элемент a'ii  - наименьший по величине и продолжаем итерации в этих строках. Так как, после каждого шага остаток a'ki  становится по величине меньше диагонального (разрешающего) элемента aii, то после конечного числа шагов получим остаток a'ki = 0. Предпоследний (не равный нулю) остаток  a'ki = d при d  1 является наибольшим общим делителем элементов aii  и  aki и остаток  a'ki = 1, если aii  и  aki – взаимно простые числа.  Если  a'ki  1, то ik –итерации применяются к следующей  k = i+2 строке  с разрешающим элементом a'ii = d, но этот элемент меньше исходного aii и, следовательно, число следующих итераций может быть значительно меньше. Если  же a'ki  = 1 (после перестановки строк a'ii = 1, благоприятный исход),  то все остальные элементы в этом столбце в цикле преобразуются в нули с использованием в каждой строке только по одной операции умножения и вычитания в целых числах.
Обозначим  a = aki , b = aii (b < a), тогда ik -итерация означает деление a по модулю b:
a = mb + r1 ,						(3)

где  m = [a/b] – наибольшее целое число, не превосходящее a/b,
 r1 – остаток от деления (0  r1  b - 1) [1].
Следующий шаг  ik-итерации соответствует  делению b по модулю r1:
b = m1 r1 +  r2 ,  
и далее
r1 = m2r2 +  r3 ,
r2 = m3r3 +  r4 ,
…	    						(4)
rn-1 = mnrn +  rn+1.

Для взаимно простых чисел a и b процесс заканчивается при rn = 1 (rn+1 = 0).
Таким образом, оценка эффективности целочисленного метода Гаусса связана с оценкой среднего числа ik –итераций, т.е. числа делений предыдущего остатка rj-1 по модулю последующего остатка rj.
Экспериментальную (статистическую) оценку среднего числа ik –итераций можно получить, задавая случайные числа a и b и подсчитывая соответствующее число ik –итераций. Задача вычисления для произвольных  a и b последнего отличного от нуля остатка rn  0 (rn+1 = 0) соответствует алгоритму Евклида нахождения наибольшего общего делителя D(a,b) натуральных чисел a и b. С точки зрения приложений для метода ЦМГ, неблагоприятный случай - если a и b имеют общий делитель d0  1, тогда нуль в k-й строке получится “раньше”, но поиск единицы продолжится в следующих i(k+1)–итерациях. Если же числа a и b взаимно простые, то наибольший общий делитель D(a,b) = rn = 1, на этом процесс ik –итераций в этой паре строк заканчивается и, далее, вся лежащая ниже часть i-го столбца обнуляется только двумя наиболее экономичными операциями – умножения и сложения (вычитания) в целых числах.
Если одно из двух взаимно простых чисел (а именно, большее - a) - простое, то при любом b < a пара (a, b) будет взаимно простой, т.е. последний в ik-итерациях отличный от нуля остаток rn = 1, что является благоприятным исходом в методе ЦМГ. Ниже приведены предварительные результаты оценок числа ik-итераций такой задачи. Для трех наибольших до 1000 простых чисел a  A = {997, 991, 983} в таблице № 1 приведены числа ik-итераций для всех чисел b от 1 до 1000 (т.е. для всех взаимно простых пар {(ai, bj) ai  A, bj  {1, 2, …, 1000}} и, в том числе, по одной паре, не являющейся взаимно простой при bj = ai и D(ai, bj) = ai  1).  В таблице № 2 показано в процентах, что большое число итераций (для a = 997) связано только с числами b, находящимися в сравнительно узком интервале: bj (-, +), где    2a/3, а  зависит от b и n. Распределение fb/a(n) числа ik-итераций близко к нормальному с заметной положительной асимметрией S > 0 и математическим ожиданием Mx  = nmax / 2.  Для всех приведенных ai среднее число ik-итераций Mx = 6 (средняя строка таблицы), частота появлений шести итераций составляет 21-22%.
Таблица №1				Таблица № 2
ai	997	991	983		ai	997	997	
n	1-1000	1-1000	1-1000		n	10-1010	400-900	
1	2	2	2		1	0,1%	0	
2	11	23	3		2	0,7%	0,1%	
3	37	51	41		3	3,5%	1,0%	
4	113	89	113		4	11,5%	5,2%	
5	191	172	184		5	19,2%	15,4%	
6 	208	211	221		6 	21,0%	21,8%	
7	192	190	201		7	19,4%	21,8%	
8	136	148	131		8	13,6%	18,2%	
9	68	76	62		9	6,8%	9,8%	
10	30	28	28		10	3,0%	4,6%	
11	10	8	12		11	1,0%	1,6%	
12	2	2	2		12	0,2%	0,4%	

Литература

1.	Калужнин Л.А. Введение в общую алгебру. М., Наука, ФМЛ, 1973 г. 448с.
2.	Родкин А.Ф. Алгоритм метода Гаусса преобразования матриц в кольце целых чисел. 40-я Всероссийская межвузовская НТК "Фундаментальные и прикладные вопросы физики и математики".  Сб. докл., т.1, ч. 2,  Владивосток, Изд. ТОВВМУ им. С.О. Макарова, 1997 г., с.163-165.
3.	Родкина Л.Р., Родкин А.Ф. Алгоритм вычислений определителей  целочисленных матриц по методу Гаусса. Всероссийская НТК,  посвященная 150-летию со дня рождения С.О. Макарова. Сб. докл., т.2., Владивосток, изд. ТОВМИ, 1998 г., с.190-192.
4.	Родкина Л.Р., Родкин А.Ф. Вычисление определителей целочисленных  матриц по методу Гаусса. Концепции методики преподавания - 2002 в сфере высшего образования. Материалы научно-методической конференции, сентябрь 2002, г. Артем, изд. ДВГУ, Владивосток, 2002 г., с. 49-52. 
5.	Родкина Л.Р., Родкин А.Ф.  О точном методе решения систем линейных уравнений. Материалы научно-практической конференции, вып.1, (апр., 2004, г. Артем), изд. ДВГУ, Владивосток, 2004 г., с. 93-96.