ПРОГРАММИРОВАНИЕ, 2008, № 2, с. 14-19
— КОМПЬЮТЕРНАЯ АЛГЕБРА
УДК 681.3.06
ВЫЧИСЛЕНИЕ ДОМИНИРУЮЩИХ ВЕЩЕСТВЕННЫХ
КОРНЕЙ МНОГОЧЛЕНОВ *
© 2008 г. Д. Штефанеску
Бухарестский университет Румыния, Бухарест E-mail: stef@rms.unibuc.ro Поступила в редакцию 01.06.2007 г.
Вычисление доминирующих положительных корней многочленов от одной переменной играет ключевую роль в алгоритмах изоляции вещественных корней. Мы предлагаем новый аппарат для вычисления доминирующих вещественных корней и сравниваем его с другими методами. Полученные нами результаты для корней, больших единицы, лучше, чем классические оценки Лагранжа и Лонгшампа. Мы также обсуждаем новое улучшение результата о границах для положительных корней, которое может применяться ко всем многочленам с переменами знаков.
ВВЕДЕНИЕ
Рассмотрим многочлен Р от одной переменной с вещественными коэффициентами и хотя бы одним положительным корнем. Заметим, что такие многочлены имеют хотя бы одну перемену знаков. Без потери общности предположим, что старший коэффициент многочлена Р положителен.
Напомним, что доминирующий корень многочлена Р - это наибольший по абсолютной величине корень. Оценка доминирующих положительных вещественных корней играет большую роль для изоляции вещественных корней многочленов от одной переменной (см., например, [1] и [2]). Существует несколько методов оценивания вещественных положительных доминирующих корней. Некоторые из этих методов пользуются границами для комплексных корней. Среди методов, ориентированных только на вещественные корни, наиболее часто используется метод Лагранжа и его расширения. Другие методы предложены Киустелидисом [3] и Штефанеску [4, 5]. В настоящей статье мы получаем новые оценки для положительных доминирующих корней и сравниваем их с оценками, полученными этими методами.
1. ОЦЕНКИ ДЛЯ ДОМИНИРУЮЩИХ КОРНЕЙ
Существует много оценок для корней многочленов от одной переменной с комплексными коэффициентами (см., например, [6]). Их можно также применять к многочленам с вещественными коэффициентами. Однако, для вещественных корней можно получить более точные оценки.
1.1. Классические оценки
Наиболее известной является следующая оценка для положительных корней, полученная Лагранжем.
Теорема 1 (Лагранж). Пусть Р(Х) = = аоХ* + • • • + атХЛ~т - ат+1Х(1~т~1 ± ■ ■ ■ ± 6 ЩХ] , где все аг- > 0, ао, ат+\ > 0 . Положим
¿—г
А = maxja,; coeff < о} .
Число
L i = l +
А\ 1Кт+1)
а0
"Перевод с англ. Е.В. Панкратьева.
является оценкой сверху для положительных корней многочлена Р.
Другая оценка, связанная с теоремой 1, получена Лонгшампом:
Теорема 2 (Лонгшамп). Пусть Р(Х) = = аоХ* + • • • + атХл~т - ат+1Х(1~т~1 ± ■ ■ ■ ± ±0,(1 £ ЩА] , где все сц > 0, ао, ат+\ > 0 и
А = тах{а,; соеИ^А^"8) < о} .
Число
Ь 2 = 1 +
А
ао + аг +----аГ1
является оценкой сверху для положительных корней многочлена Р.
2. НОВЫЕ ОЦЕНКИ
Оценки Ь1 и ¿2 можно улучшить, а также можно получить оценки, справедливые для многочленов, вещественные корни которых меньше, чем 1. Напомним некоторые из них.
Теорема 3 (Штефанеску [4]). Пусть Р(Х) = = аоХ* + • • • + атХЛ~т - ат+1Х(1~т~1 ± ■ ■ ■ ± ±0,(1 £ ЩА] , где все аг- > 0, ао, ат+1 > 0 . Положим
Число
1 + тах
А = тах{аг; соеИ^А^"8) < о} рА
«о + «1 + дА
1/(ш-«+1)
+ а3/
1 /(т —5+2)"
ва0-\-----Ь 2а5_2 + а5_1
А = тах{аг; соеИ^А^"8) < о}
Число
1 + тах
рА
ао + • дА
■ + а£
1/(т-з+1)
1/(т-з + 2)
ва0 + ■
+ 2а8-2 + ав-1 2 гА
з(з - 1 )а0 + (з - 1)(з - 2)сц+- • - + 2а8_2
1/(т-з + 3) '
является оценкой сверху для положительных корней многочлена Р при любых в £ {2, 3,..., то} и р > 0 , д > 0 , г > 0 таких, что р + Я + г = 1.
Дж. Б. Киустелидис [3] и недавно Д. Штефанеску [4] получили оценки, справедливые также для многочленов с доминирующими корнями, меньшими единицы. Эти оценки могут пригодиться для уменьшения стоимости СР-алгоритмов изоляции корней (см. [1, 2]).
Теорема 5 (Киустелидис [3]). Пусть Р(X) = = Xй - ЪгХ<г"т1-----ЪкХ(1~т" + д(Х), где коэффициенты многочлена д(Х) положительны и Ь\ > 0, ..., Ък > 0 . Число
К(Р) = 2-тах{ь\/т\...,ь1/тк}
является оценкой сверху для положительных корней многочлена Р.
Теорема 6 (Штефанеску [4]). Предположим, что число перемен знаков коэффициентов многочлена Р( X) £ К [А] четно. Если
Р(Х) = С1Х^ - &1А"11 + с2Х^-_ъ2Хт* + • • • + скХ*» - ЪкХт* + д(А) ,
где д(А) е Е+[А], сг > 0, Ьг > 0, (1г > тог > ¿г+г для всех г, то число
{ (Ъл \ ^(^-Ш!)
= тах
Ск
является оценкой сверху для положительных корней многочлена Р при любых в £ {1,2, ..., то} и р > 0 , д > 0 таких, что р + д = 1.
Теорема 4 (Штефанеску [5]). Пусть Р(А) = = аоА^ + • • • + атХЛ~т - ат+1 Х^"1"1 ± • • • ± 6 ЩА] , где все аг- > 0, ао, ат+1 > 0 . Положим
является оценкой сверху для положительных корней многочлена Р.
3. НОВЫЕ ГРАНИЦЫ
Мы дадим две новых границы для вещественных корней многочленов от одной переменной. Теорема 7. Пусть
Р(А) = а!Х^ + а2Х^ + • • • + а,Xй' - 61 А61 --Ь2Х^-----Ь3Х^ + д(Х) £ Е[А],
где д £ Е+[А] , щ > 0 , Ь3 > О, = deg(P) и (1\ > ¿2 >■■■> (1е. Верхняя граница для положительных корней многочлена Р дается формулой
1
тах
1<г<в
1<3<г
/3,5^0
ЧаЬ3 ] <' - е3
(53аг I
для любых ßj > 0 , 7jk > О таких, что
d-t
з=1
з •
E7ji = 1, где Jji = 0, если dt < е %=1
Доказательство. При ж > 0 мы имеем
s t
Р(х) = - =
для всех ßj > 0, Е ßj = 1 и ajk > 0, Е «j^ =
3 = 1 к=1
= 1, j = l,2,...,i.
Доказательство. Пусть ж G IR, х > 0. Мы
имеем:
Р(х) >axd-J2 ЬзхЧ =
3 = 1
г = 1
3 = 1
(2)
Ü=i
j=i
= EM • - Е6
iXc> =
\3 = 1
t / s
\г = 1
U = 1
= Е (aßjXd~e> - bj) •
j = l \г = 1 /
= ¿(¿/3,^- (Еъч) ^ =
3 = 1 \г = 1
t / s
= Е Е(/>.
j=l \г=1
3 = 1
(1) Последнее выражение положительно, если
1
\г = 1
>
Ь3 \ d~e3
aßj
'j ^ ^
- Ъг !>: ) ^ .
Следовательно, Р(х) > 0, как только
1
>
Ijibj \ <1 - е3 ßjüi )
для всех ] = 1, 2,..., Ь , (3^ ф 0 . Это доказывает, что В1(Р) - верхняя граница для положительных корней многочлена Р.
Чтобы получить границу ^(-Р), рассмотрим х > 1 и у = ж — 1 и разложим по у и х. Получим:
для всех ] = 1, 2,..., Ь , I = 1, 2,..., в , ^ ф 0 Это дает требуемую границу. Теорема 8. Пусть
Р(Х) = аХЛ - &1Х61 - Ъ2Хе2-----
-ЬгХ«+д(Х) е ВД,
□
Xd = (1 + y)d~eiXei =
(3)
Следовательно,
где d = deg(P), а > 0, bj > 0, g G P(x) > axd-J^b
ej > ej.|_i для всех j. Верхняя граница для положительных корней многочлена Р дается формулой
з=1
d ах
В(Р) = min {В1{Р),В2{Р)}
= (5>j
t
= Е axd ~ ьзхЧ)=
где
з=1
1
= Е а» Е
ВАР) = шах Г 6j
В2(Р) =
з=1
d — e.
(4)
= Е*ечМЕ
j=i
d — e.
з l „ ,k
УК ~bi =
= 1 + max i<j<t
max
1 \k
ajkbj
J=1
где
d—e
k=0
9З(У) = «ßj E' ( d kej )yk~bj
t
t
t
e, X 3 =
e
j
X J l =
d — e
j —
k
d — e
k
e
1</с<а—е^
Однако,
(1—е^
зМ> Е (^/Цй кез V
- (е1=13 а1к) Ь, =
(5)
с1—е
А к 4 \ук~ а1к Ь3 I .
Поэтому д3 (у) > 0 при условии, что /
у > тах
1 \к
а]кЬ3
А "V
/
для всех (3^ ф 0 . Следовательно, Р(х) > 0, как только
у > тах
/3,^0
тах
1 \ к
а1кЬ1
А" 7'
Это доказывает, что -Вг(-Р) также является верхней границей для положительных корней многочлена Р. □
Замечания:
В теоремах 7 и 8 имеется несколько вариантов выбора параметров (3^ , и . Наиболее естественный выбор получается, если две последовательности представляют арифметические или геометрические прогрессии. Оптимальный выбор определяется значениями отношений
Рассмотрим, например, параметры (3^ в границе В\ из теоремы 8. Рассмотрим следующий выбор параметров /3 :
0-1- - -
Ра - \ г , • • •, г , г
Рь =
1 1 1
1 1
2' 22'' "'г*-1' 24' 24
(6)
(7)
Пусть Р(Х) = Xе1 - ЬхХл~1 - Ъ2Хс1-4-— &з Х^-4 + д(Х) , где д - многочлен с положительными коэффициентами.
Таблица 1
Размер Оптимальный выбор
&1 > &2 > Ь3 > 1 (7)
&1 > 1, Ъ2 < 1/4, Ь3 < 1/4 (7)
&1 < 1/3, &2 > 1, 63 > 1, Щ < Ь* (6)
Таблица 2
/31 /32 /Зз ВЛР)
0.1 0.1 0.8 12.00
0.15 0.15 0.7 8.00
0.2 0.2 0.6 6.00
0.3 0.3 0.4 4.00
0.4 0.3 0.3 3.00
0.5 0.25 0.25 2.40
0.6 0.3 0.1 2.14
0.62 0.23 0.15 1.94
0.7 0.2 0.1 2.14
0.8 0.1 0.1 2.57
0.9 0.05 0.05 3.24
В этом случае мы имеем: '1 1 1
/За =
3' 3' 3 1 1 1
2'4'4
Рь =
и получаем границы
В1а(Р) = тах{361,(362)1/3,(363)1/4}, В1Ь(Р) = тах{261,(462)1/3,(463)1/4}-
Оптимальный выбор между (6) и (7) зависит от размера коэффициентов Некоторые случаи, когда можно легко найти оптимальный выбор, перечислены в таблице 1.
Рассмотрим теперь конкретный многочлен
Р(Х) = Ха-1.2Ха-1-1.7 Ха~6-2.1Х,1-4+д(Х),
где д е Е+[Х] и (I > 5 .
Имеем: Ь\ = 1.2, = 1-7, = 2.1. Таким образом, мы имеем очень близкие значения для ¿>1, Ь^3 и ьУА . Тогда для различных значений (3\, /32 и (Зз мы получаем результат, показанный в таблице 2.
Мы видим, что наилучшая граница получается при
(Ръ(32,(33) = (0.62 , 0.23 , 0.15).
1</с<а — е3
Таблица 3
А
¿1 ь2 К ВР1 ВР2 ВР3 ЬРИ
2.246 2.5 2.632 1.651 1.565 1.461 1.346
(8)
О < х <
713^2
> М , где М = тах
7Ж
0,I аф3
(9) (10)
И мы не получаем верхней границы, если М <
[Ьаз
713^2
4. ПРИЛОЖЕНИЯ
Сравним границы, приведенные в теоремах 7 и 8, со следующими границами:
/ Л \ 1/(т + 1)
(Лагранж),
ао + «1 Н-----1- ап
Заметим, что оптимальный выбор достаточно близок к выбору (7).
Замечание. Условие "7ji = 0, если < е^" в теореме 7 является существенным.
Действительно, рассмотрим многочлен
Р(Х) = агХ7 + а2Х5 + а3Х3 - ЪхХА - Ь2Х2 ,
где все аг- ф 0 , ^ ф 0, и представим его в виде
Р(Х) =
= № + ¡32)агХ7 - (711 + Т12 + 71з)&1Х4+
+ (/31 + /32)а2Х5 - (721 + 722 + 72З)&1^2+ + (/31 + (32)а3Х3,
где все ф 0 .
При х > 0 это дает
Р(х) =
= (Ргагх7 - 711&1Ж4) + ([32а\х7 - У2\Ъ2х2) + + (Рга2х5 - 712&1Ж4) + (р2а2х5 - у22Ь2х2) + + ([1га3х3 - 713&1Ж4) + ((З2а3х3 - у23Ъ2х2) .
В соответствии с нашим методом левые скобки в третьей строке формулы (8) должны быть положительными при условии, что х больше некоторой величины. Но это возможно только, если 713 = 0. В противном случае мы должны иметь
Ь2{Р) = 1 + (Лонгшамп),
К{Р) = 2та х{Ь)/[,1~ч)}
(Киустелидис) ,5*1 (Р) =
(/ А \1/(т+1) = 1 + тах < (-
\V2ao,
(Штефанеску),
¿2 (Р) =
= 1 + тах
А
2 (а0 + а,!)
1 /г
2 А
3(12ао + ба^а^ + 2а2 + а3) А х1/2
1/3
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.