Алгоритм аннулирующей редукции

Наиболее эффективным в практическом отношении методом построения минимального многочлена является метод аннулирующей редукции. Задача сводится к поиску обращающейся в ноль линейной комбинации векторов (1.40)

l, l¹=Al , l²=Al¹ , ... , l^r=Al^r- (1.40)

при минимальном их числе p+1. Указанная линейная комбинация ищется с помощью формирования векторов

l_*⁰=l, l_*¹ , l_*² , ... , l_*^r

с возрастающим числом нулевых элементов вплоть до образования нулевого вектора l_*^p, дающего соотношение (1.41)

l ^p+d₁ l ^{p -1}+d₂ l ^p-2+ ... +d_p-1 l ¹+d_p l =0 (1.41)

Алгоритму аннулирующей редукции придана удобная табличная форма.

Пусть задан вектор l и требуется построить его минимальный многочлен вида (1.42)

d(s)= s ^p+d₁ s ^p-1+d₂ s ^p-2+ ... +d_p-1 s+d_p (1.42)

Таким образом, возникает задача поиска коэффициентов линейной комбинации (1.41). Для решения этой задачи рассматривается ряд векторов l_*^r, r=0,1,2,..., l_*⁰=l, определяющихся по формуле (1.43)

l_*^r=Al_*^r-1+g_k^rl_*^k , r=1,2, (1.43)

Коэффициенты линейной комбинации (1.43) g_r^k выбираются на каждом шаге r, с учетом условия, что в каждом последующем конструируемом векторе число нулевых элементов должно возрастать.

Алгоритм начинается с первого шага r=1. Для этого в исходном векторе l выбирается элемент d, с номером m , такой что

d=l_m¹ 0 (1.44)

Составляется линейная комбинация

l_*¹=Al+g₀¹l,

коэффициент g₀¹ выбирается так, чтобы выполнялось условие

l_*¹_m=0.

Тогда он вычисляется по формуле

g₀¹=-(Al)_m / d

На втором шаге редукции при r=2 в векторе l_*¹ выбирается элемент d₁, с номером m₁¹m, такой, что

l_*¹_m1¹0

Составляется линейная комбинация

l_*²=Al_*¹+g₀²l+g₁²l_*¹ ,

коэффициенты g₀² и g₁² выбираются с учетом условий

l_*²_m= 0 , l_*²_m1= 0.

Тогда искомые коэффициенты определяются по формулам

g₀²=-(Al_*¹)_m / d

g₁²=-[(Al_*¹)_m1 +g₀² l_m1 ]/ d_1.

Выбранные элементы d и d₁ называются ведущими элементами векторов l и l_*¹ соответственно.

Далее указанная процедура продолжается индуктивно для построения векторов вида (1.43). Можно записать соотношения для полученных векторов:

1. l_*¹_m=0.

2. l_*²_m= 0 , l_*²_m1= 0.

............................................ (1.45)

r-2. l_*^r-2_m= 0 , l_*^r-2_m1= 0 , ... , l_*^r-2_{m r-3}= 0 .

r-1. l_*^r-1_m= 0 , l_*^r-1_m1= 0 , ... , l_*^r-1_{m r-3}= 0 , l_*^r-1_{m r-2}= 0 .

где m, m₁, ... , m_r-2 - номера ведущих элементов векторов l_*⁰=l, l_*¹ , l_*² , ... , l_*^r-2 соответственно.

Предположим, что на шаге r выбирается элемент d_r-1 с номером m_r-1 , причем

d_r-1= l_*^r-1_{m r-1}¹ 0

Тогда, выполняя указанную выше процедуру построения линейной комбинации и выбора коэффициентов, конструируется вектор l_*^r со всеми нулевыми компонентами.

Для удобства формирования таблицы вводятся обозначения:

f_*^r=Al_*^r-1 , r=1,2, ... (1.46)

А для векторов l_*^r будет справедливо выражение

l_*^r=f ^r+g_k^rl_*^k (1.47)

Учитывая соотношение (1.45) можно записать

l_*^r_m= f_m^r + g₀^r l_m

l_*^r_m1= f_{m 1}^r + g₀^r l_{m 1}+g₁^r l_*¹_m1

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

l_*^r_mk= f_m^r_k + g₀^r l_{m k}+g₁^r l_*¹_mk+ ... +g_k^r l_*^k_mk (1.48)

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

l_*^r_mr-1= f_m^r_r-1 + g₀^r l_{m r-1}+g₁^r l_*¹_mr-1+ ... +g_r-1^r l_*^r-1_mr-1

Если учесть, что на r - ом шаге редукции требуется образовать нуль-вектор, то есть выполнить условия

l_*^r_m= 0 , l_*^r_m1= 0 , ... , l_*^r_{m r-2}= 0 , l_*^r_{m r-1}= 0 , (1.49)

то из соотношения (1.48) определяются коэффициенты g_k^r :

g₀^r =-f_m^r / d

g₁^r=-(f_m1^r+g₀^r l_m1) / d₁

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

g_k^r=-(f_mk^r+g₀^r l_mk+g₁^r l_*¹_mk+ ...+ g_k-1^r l_*^k-1_mk-1) / d_k (1.50)

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

g_r-1^r=-(f_mr-1^r+g₀^r l_mr-1+g₁^r l_*¹_mr-1+ ...+ g_r-2^r l_*^r-2_mr-1) / d_r-1

Таким образом, при построении линейной комбинации векторов (1.47) с учетом выбора коэффициентов (1.50) образуется вектор l_*^r , у которого r элементов с номерами m, m₁, ... , m_r-1 равны 0. Каждый из построенных векторов l_*^r , r=1,2,... может быть представлен в виде линейной комбинации векторов l, l¹=Al , l²=Al¹ , ..., l^r=Al^r-1 вида

l_*^r =l^r+d₁l^r-1+d₂l^r-2+ ... +d_r-1l¹+d_rl (1.51)

Если при r=p вектор l_*^p равен нулю, то равенство (1.51) принимает вид (1.41). Так как это равенство по построению образуется впервые, то с учетом соотношения (1.41) формируется минимальный многочлен с коэффициентами:

d₁=d₁^p , d₂=d₂^p , ..., d_p-1= d_p-1^p, d_p=d_p^p (1.52)

Для построения таблицы вводятся обозначения:

h^r1= f ^r + g₀^r l

h^r2= h^r1+g₁^r l_*¹

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

h^rk= h^rk-1+g_k^r l_*^r-1 (1.53)

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

h^rr-1= h^rr-2+g_r-2^r l_*^r-2 , r=2,3,...

Тогда вектор l_*^r формируется по формуле

l_*^r= h^rr-1+g_r-1^r l_*^r-1 (1.54)

а соотношение (1.50) принимает вид

g₀^r =-f_m^r / l_m

g₁^r=- h^r1_m1 / l_*¹_m1

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

g_k^r=- h^rk_mk / l_*^k_mk (1.55)

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

g_r-1^r=- h^rr-1_mr-1 / l_*^r-1_mr-1 , r=2,3,...

Получая коэффициенты g_k^r из соотношений (1.53),(1.55) при k=0,1,...,r-1, можно вычислить коэффициенты линейной комбинации (1.51). Для этого подставляется выражение (1.51) в (1.40) и приравниваются коэффициенты при векторах l^r-1,l^r-2,...,l¹,l. В итоге получается соотношение

d₁^r=d₁^r-1+ g_r-1^r

d₂^r=d₂^r-2+ g_r-1^rd₁^r-1+ g_r-2^r

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

d_k^r=d_k^r-1+ g_r-1^rd_k-1^r-1+ g_r-2^rd_k-2^r-2+ ... +g_r-k+1^rd₁^r-k+1+ g_r-1^r (1.56)

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

d_r-1^r=d_r-1^r-1+ g_r-1^rd_r-2^r-1+ g_r-2^rd_r-3^r-2+ ... +g₂^rd₁²+ g₁^r

d_r^r=0+ g_r-1^rd_r-1^r-1+ g_r-2^rd_r-2^r-2+ ... +g₂^rd₂²+ g₁^rd₁¹+ g₀^r

Вычислениям по соотношению ( 1.56 ) можно придать табличную форму (табл 1.1). Формируя строки, указанные в таблице, умножая их на g_k^r , при k=0,1,... указанные колонкой справа и складывая соответственно элементы этих строк по столбцам, получаются коэффициенты линейной комбинации (1.51) по найденным на предыдущих шагах.

Выполняя вычисления последовательно при r = 1, 2, ..., p в последней таблице получим коэффициенты минимального многочлена ( 1.52 ). Указанному рекурентному процессу можно придать следующую форму :

d ^r(s)= s^r + d₁^r s^r-1+ d₂^r s^r-2 + ... +d_r-1^r s + d_r^r, r = 0, 1, ..., p (1.57)

d ⁰(s)= 1

Таблица 1.1

k	sr sr-1 sr-2 sr-3 ... s2 s1 s0	gkr
0 1 2 ... r-1 r	0 0 0 0 ... 0 0 1 0 0 0 0 ... 0 1 d11 0 0 0 0 ... 1 d12 d22 ................................................................................ 0 1 d1r-1 d2r-1 ... dr-3r-1 dr-2 r-1 dr-1 r-1 1 d1r-1 d 2r-1 dr-3r-1 ... dr-2 r-1 dr-1 r-1 0	g0r g1r g2r . gr-1r 1
S	1 d1r d 2r dr-3r ... dr-2 r dr-1 r dr r

Многочлены выражения ( 1.57 ) связаны рекурентным соотношением :

d ^r(s)= sd ^r-1(s)+ g_k^rd ^k(s), r = 1, 2, ... p (1.58)

где d ⁰(s)= 1.

Учитывая, что коэффициенты g_k^r определены выше, можно записать согласно (1.58) соотношение :

d₁⁰(s)= 1

d₂¹(s)= s + g¹

d₃²(s)= s d ¹(s)+ g₁² d ¹(s)+ g₃² (1.59)

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

d ^r(s)= s d ^r-1(s)+ g_r-1^r d ^r-1(s)+ g_r-2^r d ^r-2(s)+ ... + g₁^r d ¹(s)+ g ^r

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

на последнем шаге вычислений определяются коэффициенты минимального многочлена d (s)= d ^p(s)

d ^p(s)= s d ^p-1(s)+ g_k^pd ^k(s) (1.60 )

Полную схему вычислений для построения минимального многочлена на основе соотношений ( 1.53, 1.54, 1.56, 1.46, 1.40 ) можно представить в табличной форме ( табл. 1.2 ), представляющей собой фрагмент алгоритма на r-ом шаге.

Таблица заполняется числами * последовательно по шагам k = 0, 1, ... r. Строки левой части таблицы заполняются значениями элементов векторов, а строки правой части - значениями коэффициентов многочленов при степенях s^k , k = 0, 1, ..., n. В последней строке таблицы получаем слева компоненты l_*^r₁ , l_*^r₂ , ..., l_*^r_n вектора l_*^r , а справа коэффициенты 1, d₁ ^r, ..., d _r^r , при указанных вверху степенях многочлена d ^r(s).

Таблица 1.2

k		1 2 3 ... n	dk	gkr	sr sr-1 ... s2 s1 s0
0 1 2 . r-1	f r g0rl h r1 g1 r l*1 hr2 g2r l*2 ... hrr-1 gr-1r l*r-1	* * * ... * * * * ... * * * * ... * * * * ... * * * * ... * * * * ... * .................. * * * ... * * * * ... *	* * * . *	* * * . *	* * * * * * ................................ * ... * * * 1 * ... * * *	g0 r d o(s) g01r d 1(s) g2 r d 2(s) ...... gr-1r d r-1(s) sd r-1(s)
r	l*r	* * * ... *			1 * ... * * *	d r(s)

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