Диссертация (1145311), страница 6
Текст из файла (страница 6)
, m; b0 6= 0).Предположим, что полиномы f (z) и g(z) не имеют общих корней (т. е. R(f ,g)6=0). Построим ганкелеву квадратичную формуH(Y, Y ) =Pn−1t 0 t1=YT tn−1j,k=0 tj+k yj ykt1 . . . tn−1...tn...tn . . . t2n−2 Y = Y T [tj+k ]n−1 Y = Y T HY,0где tp = b0 sp+m + b1 sp+m−1 + · · · + bm sp ,sj — сумма Ньютона полинома f (z).36Замечание 3. [173]H=bm bm−1 . .
. b000...bmb000. . . b1. . . bm bm−1s1 s0 s1s2... 0...... 0 sn−1sn snsn+1. . . b0 ...sn+m−1 sn+m...sn−1...sn...s2n−2...s2n−1. . . s2n+m−2(В первой матрице n строк).Теорема Эрмита — Сильвестра позволяет найти число вещественных корней полинома, удовлетворяющих алгебраическому неравенству:Теорема 11. Уравнение f (z) = 0 имеет n+ (H) − q различных вещественныхкорней таких, что g(λj ) > 0 и n− (H) − q вещественных корней таких, чтоg(λj ) < 0. Здесь q — число различных пар комплексно-сопряженных корнейуравнения f (z) = 0.Следующий результат [173] может быть полезен в вычислениях, использующих теоремы 7 и 11Теорема 12.
а) Sn = det S = D(f )/a2n−2;0б) ИмеемHn = det H =R(f, g)D(f ).a2n+m−20Для определения числа вещественных корней полинома f (z), удовлетворяющих неравенствамG1 (z) > 0, G2 (z) > 0, . . . , Gk (z) > 0.при выполнении условий R(gj , f ) 6= 0 (j = 1, k) справедлива следующая формула [134]:37Теорема 13.nrr {f = 0|G1 > 0, . .
. , Gk > 0}1Xk−1nrr {f = 0|Gj1 > 0}[(1 − 2 )nrr {f = 0} +2k−11≤j1 ≤kXnrr {f = 0|Gj1 Gj2 > 0}+=(1.17)1≤j1 <j2 ≤k+Xnrr {f = 0|Gj1 Gj2 Gj3 > 0}1≤j1 <j2 <j3 ≤k+ · · · + nrr {f = 0|G1 G2 . . . Gk > 0}]Каждое слагаемое в правой части равенства (1.17) мы можем вычислить,используя теорему 11.Результаты КронекераВ этом параграфе мы покажем, как решаются задачи теории исключенияс использованием параметров Маркова. Часто бывает удобнее использоватьименно параметры Маркова, поскольку это позволяет понизить размерностьрассматриваемых определителей.Рассмотрим два полиномаf (z) = a0 z n + a1 z n−1 + · · · + an иg(z) = b0 z m + b1 z m−1 + · · · + bm ,где a0 6= 0, b0 6= 0.
Разложим функцию g(z)/f (z) в ряд Лорана по степеням z −1 .Для того чтобы сделать это, рассмотрим разложениеdn−1dn1= n + n+1 + · · ·f (z)zzКоэффициенты dj(1.18)(j = n − 1, n, . . .) могут быть рекуррентно выражены черезкоэффициенты полинома f (z):dn−1 = 1/a0 , dn = −(a1 dn−1 )/a0 ,dn−1+p = −(a1 dn−2+p + · · · + ap dn−1 )/a0 ,p = 1, nd2n−1+p = −(a1 dn−2+p + · · · + an dn−1+p )/a0 p ≥ 0.38Если домножить разложение (1.18) на полином g(z), то получим требуемое разложениеg(z)c0 c1ck= L(z) + + 2 + · · · + k+1 · · · ,f (z)zzz(1.19)где полиномdefL(z) =cn−m−1 zm−n+cn−m z m−n−1 + .
. . +c−1 , если m ≥ n; 0,(1.20)если m < nесть частное от деления g(z) на f (z). Коэффициенты ck определяются черезкоэффициенты полинома g(z) и разложения (1.18). Так для m ≥ ncn−m−1 = b0 dn−1 , cn−m = b0 dn + b1 dn−1 , . . .ck =(dk+m b0 + dk+m−1 b1 + · · · + dn−1 bk+m−n+1 ), если k < n;(dk+m b0 + dk+m−1 b1 + · · · + dk bm ),(1.21)если k ≥ n.В случае m < n ck = 0, если k < n − m − 1, а при k ≥ n − m − 1 справедливыформулы (1.21).Построим ганкелеву матрицуc 0 c1C=cn−1c1 . . . cn−1c2 .
. .cn...cn . . . c2n−2(1.22)Известны следующие результаты (Кронекер [119, 172])Теорема 14. а) Степень D(z) = Н.О.Д.(f (z), g(z)) равна d тогда и толькотогда, когда: Cn = 0, . . . , Cn−d+1 = 0, Cn−d 6= 0. В этом случае также имеемc0c1...cn−d−1c1c2...cn−d...D(z) = (1.23),ccn−d−1...c2n−2d−3 n n−d−2nnXX XcFcF...cFj−1 jj jj+n−d−2 j j=n−dj=n−dj=n−d39где Fk := a0 z n−k + a1 z n−k−1 + · · · + an−k , а старший коэффициент Н.О.Д(f, g)равен a0 Cn−k .б) Если n > m, то полиномы v(z) и u(z), дающие линейное представлениеН.О.Д.(f, g)f (z)v(z) + g(z)u(z) = Н.О.Д.(f, g)получаются из Cn−k заменой последнего столбца на столбцы[0, −P0 (z), . .
. , −Pn−k−2 (z)]T и [1, z, . . . , z n−k−1 ]Tсоответственно. Здесь Pj (z) = c0 z j + . . . + cj .Обозначим C̃n−1 определитель матрицыc1 . . . cn−2 c0 c1c2 . . . cn−1... cn−3 cn−2 . . . c2n−5cn−1 cn . . . c2n−3.Тогда справедливо следующее утверждениеСледствие 5. Если d = 1 (Cn = 0, Cn−1 6= 0), тоD(z) ≡ Cn−1 (a0 z + a1 ) + a0 C̃n−1 ,и единственный общий корень f и g равенα=−a1 C̃n−1+a0 Cn−1!.40Следствие 6. Существует связь между Ck и (n-k)-ым субрезультантом fи g: Rn−k a02k−(n−m)= a0Ck = b0a1 . .
. . . . a2k−(n−m)−1a0 . . . . . . a2k−(n−m)−2...a0 . . .akb0 . . .bk−(n−m)...b0 . . . . . . b2k−(n−m)−2. . . . . . . . . b2k−(n−m)−1k − (n − m) строкk строк(здесь мы предположили n > m).В частности, имеемan+mCn = R(f, g).0Пример 1. Найти Н.О.Д.(2z 5 + z 4 − z 3 + 4z 2 + 2z − 2, 10z 3 + +3z 2 − 6z + 1)и его линейное представление.По формулам (1.21) вычисляем c1 , . . . , c8c0 =0, c1 =5, c2 =−1, c3 =0, c4 =−10, c5 =2, c6 =0, c7 =20, c8 =−4.Составляем матрицу (1.22)05 −10 −10 5 −10 −102C = −10 −10200 −1020 20 −1020 20 −441и вычисляем ее главные миноры (начиная с последнего): C5 = 0, C4 = 0, C3 =251 6= 0.
Согласно пункту б) теоремы deg(Н.О.Д.)=2: 0 5 −1 · f3 (z) + 0 · f4 (z) − 10 · f5 (z)Н.О.Д.(f, g) = 5 −1 0 · f3 (z) − 10 · f4 (z) + 2 · f5 (z) −1 0 −10 · f3 (z) + 2 · f4 (z) + 0 · f5 (z),где f3 = 2z 2 + z − 1, f4 = 2z + 1, f5 = 2. НОД(f, g) = 251(2z 2 + +z − 1). Дляполучения полиномов его линейного представления воспользуемся пунктом в)теоремы.
0 5 1u(z) = 5 −1 z −1 0 z 2 = −25z 2 − 5z − 1.В соответствии с теоремой deg(v(z)) = 0, и v(z) = 125.БезутиантаПолиномамf (z) = a0 z n + a1 z n−1 + · · · + an иg(z) = b0 z m + b1 z m−1 + · · · + bm ,поставим в соответствие квадратичную формуB(f, g; y0 , . . . , yn−1 ) =n−1Xc̃kl yk yl(1.24)k,l=0с производящей функциейf (x)g(y) − f (y)g(x),x−y(1.25)т. е. числа c̃kl являются коэффициентами при xk y l целой функции (1.25).Определение 7. Матрица квадратичной формы (1.24) называется безутиантой полиномов f и g, будем обозначать ее B.42Известно [20], что формы (1.24) и Y T CY имеют одинаковое число положительных и отрицательных квадратов.Теорема 15.
Для слyчая полиномов одинаковой степени безyтианта можетбыть полyчена в виде:b2 . . . b1 b2b3 . . .B= . . .... bn−1 bnbn an an−1 . . .an...−Obn−1 bn a0 a1 . . . an−2 an−1a0 a1 . . . an−2bn...Oa0a1Oa0b0a 2 a1 Ob0b1. . . a2 ...b0 b1 . . .
bn−2an an−1 b0 b1 . . . bn−2 bn−1an−=(1.26)= B1 A0 − AT1 B0 ,т. е., фактически, перемножением n × n блоков, составляющих матрицуСильвестра (1.2):M=A0 A1B0 B1с транспонированием одного из них.Замечание 4. В случае deg g = m < deg f безутианта строится для полиномов f (z) и z n−m g(z).Теорема 16. Пусть deg f = deg g = n. Для безутианты, определяемой формулой (1.24), справедливы следующие утверждения:a) Bn = det B = (−1)n(n−1)/2 R(f, g).43б) Степень Н.О.Д.(f, g) равна d тогда и только тогда, когдаBn = Bn−1 = . . . = Bn−d+1 = 0, Bn−d 6= 0.В этом случае Н.О.Д.(f, g) равен определителю, получающемуся из Bn−d заменой последнего столбца на столбецtn−1n−1n−1XXXcn−d−1,j xn−j−1 .c1j xn−j−1 , .
. . ,c0j xn−j−1 ,j=n−d−1j=n−d−1j=n−d−1Cтарший коэффициент Н.О.Д.(f, g) равен Bn−d .в) Полиномы u(x) и v(x), дающие линейное представление Н.О.Д.(f, g):Н.О.Д.(f, g) ≡ v(z)f (z) + u(z)g(z)получаются из Bn−d заменой в нем последнего столбца на[−b0 , −b0 z − b1 , . .
. , −b0 z n−d−1 − b1 z n−d−2 − . . . − bn−d−1 ]T и[a0 , a0 z + a1 , . . . , a0 z n−d−1 + a1 z n−d−2 + . . . + an−d−1 ]Tсоответственно.Теорема 17. Справедливо соотношение, связывающее Bk и k-й субрезультантполиномов f и g:Bn−k = R(k)(k ≤ n).(1.27)Существует красивый способ вычисления безутианты полиномов f и g(deg f = n, deg g = m) [152].Рассмотрим квадратные матрицы порядка n 0 1 0 ...
0 0 0 0 1 ... 0 0S = ..., J = ... 0 0 0 ... 1 00 0 0 ... 010 ... 0 1 0 ... 1 0 .1 ... 0 0 0 ... 0 044Положим S ∗ = JSJ. Обозначим также через f1 и g1 полиномы 11f1 (z) = z n f, g1 (z) = z m.zzТеорема 18. Пусть степень полинома f равна n, а степень полинома g равнаm ≤ n. Матрица безутиантыf (x)g(y) − f (y)g(x)y−xможет быть представлена в каждрой из следующих форм:[f (S ∗ )g1 (S) − g(S ∗ )f1 (S)] J,J [f (S)g1 (S ∗ ) − g1 (S)f1 (S ∗ )] ,[g1 (S)f (S ∗ ) − f1 (S)g(S ∗ )] J,J [g1 (S ∗ )f (S) − f1 (S ∗ )g(S)] J,Параметры МарковаВернемся к полиному f (z).
Представим его в видеf (z) = F1 (z 2 ) + zF2 (z 2 ),(1.28)гдеF1 (z 2 ) = an + an−2 z 2 + an−4 z 4 + an−6 z 6 + . . .F2 (z 2 ) = an−1 + an−3 z 2 + an−5 z 4 + an−6 z 6 + . . .Разложим дробь F2 (u)/F1 (u) в ряд по степеням u−1 :F2 (u)µ0 µ 1 µ2= µ−1 +− 2 + 3 + ···F1 (u)uuuЕсли n нечетно, мы должны предположить также, что a1 6= 0 (иначе µ−1 = ∞).Определение 8.
Числа µ0 , µ1 , . . . , µ2n−1 (при n = 2l) или µ−1 , µ0 , µ1 , . . . , µ2n−1(при n = 2l + 1) называются параметрами Маркова полинома f (z).45Параметры Маркова допускают рациональное представление через коэффициенты a0 , a1 , . . . , an , в частности, для n = 2l:µ−1 = 0; µ0 = a1 /a0 ; µ1 = (a2 µ0 − a3 )/a0 ;µp =(a2 µp−1 −a4 µp−2 +a6 µp−3 − . . . +(−1)p−1 a2p µ0 +(−1)p a2p+1 )/a0 (p > 1).Здесь ak := 0 для k > n.Определение 9. Определители µ0 µ1 .