ЦЕЛОЧИСЛЕННЫЕ ПРЕОБРАЗОВАНИЯ МАТРИЦ
И ЧИСЛА ФИБОНАЧЧИ

Л.Р. Родкина, доцент кафедры электроники ИИИБС ВГУЭС
А.Ф. Родкин, к.ф.-м.н., доцент АИ ДВФУ

ФГБОУ ВПО Владивостокский государственный университет экономики и сервиса, Владивосток

Целочисленные преобразования  матриц  используются в целочисленном методе Гаусса (ЦМГ), предложенным авторами первоначально в демонстрационно-обучающих целях, затем – для практических задач решения систем линейных уравнений [3,4]. Разумеется, такой способ решения систем линейных уравнений (СЛУ) общеизвестен и им пользуются практически всегда при небольшом числе неизвестных.
В развитии этого метода можно выделить три этапа:
1)	формализация – определение алгебраической структуры, на которой рассматривается ЦМГ;
2)	разработка алгоритмов ЦМГ в этой алгебраической структуре;
3)	оценка эффективности целочисленного метода Гаусса.
Так как в ЦМГ нет операции деления, то алгебраической структурой, на которой рассматривается ЦМГ, является кольцо целых чисел [1]. Этот подход был  реализован в разработке алгоритмов вычисления определителей и решений СЛУ в целых числах и создании программ их практического применения [3,4]. 
Оценку эффективности целочисленного метода Гаусса можно провести в сравнении с (стандартным) методом Гаусса (МГ) в поле рациональных чисел Q. Отправной точкой в методе Гаусса является наличие единичного элемента при первой неизвестной первого уравнения, который получается в МГ делением всех коэффициентов первого уравнения на коэффициент  a11  при первой неизвестной.  
В ЦМГ этот единичный элемент может быть получен в результате последовательных операций вычисления остатков от деления предыдущего по модулю последующего, представляющих алгоритм Евклида вычисления наибольшего общего делителя, в ЦМГ эта процедура называется lk-итерацией - преобразование k-й строки расширенной матрицы целочисленной СЛУ с помощью разрешающего элемента ali l-й строки  [1,3,4].
Под lk - итерацией с разрешающим элементом ali (ïaliï<ïakiï) понимается элементарное преобразование (ЭП) элементов k-й строки, соответствующее делению  элемента aki  по модулю (разрешающего элемента) ali (для простоты считаем ali и aki положительными и ali<aki):
a'ki  = aki  - [aki /ali]* ali ,              				        (1)

где [aki /ali] – наибольшее целое число, не превосходящее aki /ali.
Так как в ЦМГ разрешающим элементом всегда является диагональный (для i-го столбца  ali = aii ), то, обозначая a = aki , b = aii (b < a), для ik –итерации (1) получим:
a = mb + r1 ,											(2)
где  m = [a/b] – целая часть a/b,
 r1 – остаток от деления (0 £ r1 £ b - 1) [1,3].
Следующий шаг  ik-итерации соответствует  делению b по модулю r1:
b = m1 r1 +  r2 ,  
и далее	
r1 = m2r2 +  r3 ,
r2 = m3r3 +  r4 ,											(3)
.......................
rn-1 = mnrn + rn+1,
где rn+1 = 0.
Так как каждый следующий остаток rk меньше предыдущего, то через конечное число шагов получим rn+1 = 0. Предпоследний (не равный нулю) остаток d = rn   в соответствии с алгоритмом Евклида является наибольшим общим делителем d = D(a,b) чисел a и b. Если  d = rn = 1, то a и b взаимно простые числа. Именно этот случай представляет для нас  наибольший интерес – во-первых, наличие единицы является начальным условием метода Гаусса и, во-вторых,  число операций, в результате которых в ЦМГ будет получена единица, дает оценку эффективности этого метода.
Рассматривая процедуру (3) в обратном порядке и меняя индексацию, получим

r2 = m1r1 ,
r3 = m2r2 +  r1 ,
r4 = m3r3 +  r2 , 										(4)
.......................
rn+1 = mnrn + rn-1.

Если в этой последовательности все mi  - не меняются (mi = a1 = const), тогда 

ri+1 = a1ri + a0ri-1,     (a0= 1)

или 				      			 ri+2 = a1ri+1 + a0ri,									(5)

то (5) является возвратной последовательностью 2-го порядка с коэффициентами a1 и a0  (a0 = 1) [2].  Если же оба коэффициента возвратной последовательности (5) равны 1, т.е. 

ri+2 = ri+1 + ri,										(6)

то последовательность (6) является последовательностью Фибоначчи с очень простой закономерностью – каждый следующий член последовательности (начиная с 3-го) равен сумме двух предыдущих членов [2]. Эта последовательность имеет вид:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, …			(7)

Так как все частные mi в алгоритме Евклида для чисел Фибоначчи равны единице: mi = [ri-1/ ri] = 1, то наибольшее число операций алгоритм Евклида дает для двух соседних чисел Фибоначчи, т.е., например,  для любой пары чисел x, y < 1000 число операций вычисления D(x,y) меньше, чем число операций в этой же процедуре для последней до 1000 пары чисел Фибоначчи D(610,987). В [4,5] для оценки числа операций вычисления единицы в ЦМГ подсчитывалось число операций алгоритма Евклида для всех взаимно простых пар вида {(997, bj)ïbj Î {1, 2, …, 1000}} (исключая bj=997), т.е. всех пар (ai, bj), в которых ai = 997 – наибольшее до 1000 простое число и при любом bj<1000 (кроме bj = 997). Наибольшее число операций, которое при этом было получено,  Mp = 12  (в двух случаях). Наибольшее число операций вычисления D(x,y) для указанных чисел Фибоначчи 610 и 987  Mf = 14 (непосредственно следует из вида (7)). Среднее число операций, полученное в [4,5],  Mср = Mmax/2 = 6  - составляет приблизительно 21%. 
Для оценки максимального числа операций в алгоритме Евклида вычисления наибольшего общего делителя D(a,b) (a и b - соседние числа Фибоначчи) известно условие:
Mf  <  5Cf ,
где Cf – количество цифр наименьшего из чисел a и b в десятичной системе счисления [2].
 Для приведенных чисел Фибоначчи 610 и 987  Cf = 3  и максимальное число операций в алгоритме Евклида
Mf  <  5*3 =15,

фактически же для любой пары чисел, меньших 1000,  Mp £ 14.
Последовательность Фибоначчи (7) – не единственная, удовлетворяющая определяющему условию (6), – последовательность (7) образована двумя первыми элементами 1, 1: 1+1=2, 1+2=3 и т.д. Если в качестве двух первых образующих взять другие числа и строить следующие согласно (6), то получится другая последовательность Фибоначчи, например:

3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521, 843, 1364, …			(8)

Для (8) число операций вычисления D(521,843) равно 13. 
Итак, для систем линейных уравнений с коэффициентами при неизвестных aij по  модулю не превосходящих 103 (ïaijï < 103) максимальное число операций для получения единичного диагонального элемента в ЦМГ не больше 14: Mmax £ 14.  Для равномерного распределения коэффициентов по величинам среднее число таких преобразований Mср = 6  - составляет около 20%. Приведенные оценки показывают, что 
целочисленный метод Гаусса может составить альтернативу стандартному методу Гаусса отыскания решений систем линейных уравнений в поле рациональных чисел.

Литература

1.	Калужнин Л.А. Введение в общую алгебру. М., Наука, ФМЛ, 1973 г. 448с.
2.	Маркушевич А.И. Возвратные последовательности. М.,”Наука”,1983 г.,48с.
3.	Родкин А.Ф. Алгоритм метода Гаусса преобразования матриц в кольце целых чисел. 40-я Всероссийская межвузовская научно-техническая конференция "Фундаментальные и прикладные вопросы физики и математики"  .  Сб. докл., т.1, ч. 2,  Владивосток, Изд. ТОВВМУ им. С.О. Макарова, 1997 г., с.163-165.
4.	Родкина Л.Р., Родкин А.Ф. О построении пары взаимно простых чисел. Материалы XIII Международной научно-практической конференции “Интеллектуальный потенциал вузов – на развитие Дальневосточного региона России и стран АТР”. Кн. 1. -  Владивосток, изд. ВГУЭС, 2011 г., с.47-51.
5.	Родкина Л.Р., Родкин А.Ф. К оценке эффективности целочисленного метода Гаусса. Материалы 54-й Всероссийской научной конференции "Фундаментальные и прикладные вопросы естествознания"  .  Сб. докл., т. III,   Владивосток,  ТОВВМИ им. С.О. Макарова, ВУНЦ ВМФ “ВМА”, 2011 г., с.156-160.