Главная > Математика > Основы компьютерной алгебры с приложениями
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

7.3.3. Теорема Винсента: расширение и приложения

В этом разделе мы обсуждаем теорему Винсента 1836 г., которая является основой обоих методов цепных дробей отделения вещественных корней уравнения.

Мы начинаем с тщательного исследования правила о знаках Кардано-Декарта (теорема 7.2.6), утверждающего, что число положительных корней полиномиального уравнения не может превосходить числа v перемен знаков в последовательности его коэффициентов, и если — четное число.

Более внимательное рассмотрение теоремы 7.2.6 показывает, что это довольно слабое предложение; оно дает точное число положительных корней полиномиального уравнения только в следующих двух частных случаях [ниже, когда мы допускаем терминологическую вольность и говорим «перемена знаков», мы имеем в виду перемены знаков в последовательности коэффициентов полинома

Если нет перемен знаков, то нет и положительных корней, . Если имеется одна перемена знаков, то имеется один положительный корень.

Как мы увидим впоследствии, эти два частных случая играют важную роль. Более того, справедливо также утверждение, обратное к i, поскольку имеет место следующая

Лемма 7.3.6 (Стодола). Если полиномиальное уравнение

с вещественными коэффициентами имеет только корни с отрицательными вещественными частями, то все его коэффициенты положительны и, следовательно, не дают перемен знаков.

Доказательство. Пусть — — вещественные, а — комплексные корни уравнения , где по предположению для всех пит. Полином может быть выражен в виде произведения с для всех Однако все коэффициенты этих сомножителей положительны, и, следовательно, коэффициенты произведения также будут все положительны, и, таким образом, перемены знаков отсутствуют.

Относительно второго частного случая теоремы 7.2.6 (случай упомянутый выше) заметим, что его обращение в общем случае неверно, в чем можно убедиться на примере полиномиального уравнения у которого имеется один положительный корень, но три перемены знаков. Однако при более ограничительных условиях обратное также верно; формально это выражается следующим образом:

Лемма 7.3.7 (Akritas-Danielopoulos, 1985). Пусть — полиномиальное уравнение степени с вещественными коэффициентами без кратных корней, имеющее один положительный корень и корней с отрицательными вещественными частями (комплексные корни появляются попарно сопряженными) и такое, что его корни могут быть выражены в виде

, где

Тогда в форме распределения по степеням содержит ровно одну перемену знаков в последовательности своих коэффициентов.

Доказательство. С точностью до постоянного множителя полином может быть записан в виде

где

— сумма, состоящая из членов Ясно, что можно переписать в виде

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

а поскольку по предположению для мы получаем

Поэтому можно написать

где и, следовательно

Затем нам нужно показать, что отношение уменьшается с увеличением к, иными словами, Однако это тривиально, поскольку, пользуясь мы получаем

и

и нам нужно теперь доказать, что

Действительно, это неравенство справедливо, поскольку, с одной стороны,

и, с другой стороны,

Таким образом, так как и отношение уменьшается с увеличением к, мы доказали теорему.

Тщательно проанализировав два частных случая теоремы 7.2.6, мы можем теперь сформулировать теорему Винсента, существенно от них зависящую [см. также историческое замечание 5, (Akritas et al., 1978; Lloyd, 1979; Poggendorff, 1863)].

Теорема 7.3.8 (Vincent, 1836). Если в полиномиальном уравнении с рациональными коэффициентами и без кратных корней сделать последовательно подстановки вида

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

в то время как в первом случае корней нет.

Доказательство. Доказательство этой теоремы можно найти в оригинальной работе Винсента, и здесь оно опускается. Вместо этого непосредственно ниже мы представляем доказательство более общей теоремы.

Очевидно, что эта теорема обрабатывает только положительные корни; отрицательные корни исследуют, заменяя на в исходном полиномиальном уравнении. Общность этой теоремы не ограничивается предположением, что не должно быть кратных корней, потому что, как и в случае теоремы Штурма, мы можем сначала применить разложение на свободные от квадратов множители. Сам Винсент говорил, что теорему 7.3.8 сформулировал в 1827 г. Фурье, но он не дал какого-либо ее доказательства (или если и дал, то оно никогда не было найдено); более того, Лагранж использовал главную идею этой теоремы гораздо раньше.

Зависимость теоремы Винсента от теоремы Бюдана легко заметить, если каждую подстановку вида заменить эквивалентной парой подстановок

Интуитивно цель ряда последовательных подстановок вида применяемых к уравнению состоит в том, чтобы один из его положительных корней оказался внутри интервала (0,1), а все остальные — в или наоборот, за исключением, конечно, случая, когда 1 — корень. В первом случае последующая подстановка даст в результате уравнение с одним только корнем в , в то время как во втором случае тот же результат достигается с помощью подстановки .

В теореме 7.3.8 естественно возникает вопрос относительно максимума числа подстановок вида необходимых, чтобы получить полиномиальное уравнение с не более чем одной переменой знаков. Ответ дается следующей теоремой (см. историческое замечание 6).

Теорема 7.3.9 (Винсент-Успенский-Акритас). Пусть — полиномиальное уравнение степени рациональными коэффициентами и без кратных корней, и пусть — наименьшее расстояние между любыми двумя из его корней. Пусть — наименьший индекс, такой, что

где есть элемент последовательности Фибоначчи и

Пусть — произвольное неотрицательное целое число, и пусть — произвольные положительные целые числа. Тогда подстановка

эквивалентна ряду последовательных подстановок вида преобразует уравнение в уравнение которое имеет не более одной перемены знаков.

Локазательство. Чтобы доказать теорему, достаточно показать, что после последовательных подстановок вида вещественные части всех комплексных корней, также как все вещественные корни, за исключением, может быть, одного, становятся отрицательными. (Чрезвычайно важно отметить, что корни преобразованного уравнения группируются вокруг —1.)

Действительно пусть есть подходящая дробь для цепной дроби

Из разд. 2.2.3 нам известно, что для мы имеем

Так как то, следовательно, . Далее, может быть выражено в виде

откуда следует, что

Ясно, что если о — любой корень уравнения то величина определяемая формулой (V4), является соответствующим корнем преобразованного уравнения а. Предположим, что о — комплексный корень уравнения т.е. . В этом случае вещественная часть соответствующего корня равна

и обязательно отрицательна, если Если, наоборот, значение a, очевидно, содержится между двумя последовательными подходящими дробями абсолютное значение разности между которыми равно Следовательно,

откуда следует, что

Из (V5) и (V6) мы заключаем, что значение отрицательно, если Чтобы доказать, что это так в нашем случае, прежде всего заметим, что, поскольку — минимальное расстояние между любыми двумя корнями уравнения мы имеем

откуда получаем более того, мы знаем, что и, согласно (V1), что Тогда, очевидно, откуда следует, что Из последних двух неравенств мы получаем доказав, таким образом, что это

очевидным образом верно для всех комплексных корней преобразованного уравнения

b. Предположим теперь, что — вещественный корень уравнения и рассмотрим сначала случай, когда для всех вещественных корней

Из (V4) следует, что все вещественные корни преобразованного уравнения будут отрицательными; более того, по предположению все комплексные корни уравнения имеют отрицательные вещественные части. Следовательно, по лемме не имеет перемен знаков.

Предположим, теперь, что для некоторого вещественного корня о

Тогда, очевидно, содержится между двумя последовательными подходящими дробями и, следовательно, Пусть — любой другой корень, вещественный или комплексный, уравнения — соответствующий корень преобразованного уравнения. Тогда, с учетом того, что

из (V4) следует, что

или

где

Теперь

и, следовательно,

Из последнего выражения и второго неравенства формулы (VI) мы заключаем, что Таким образом, корни преобразованного уравнения соответствующие корням уравнения которые все отличны от имеют вид

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

где

то преобразованный полином может быть записан в виде

Поскольку полином удовлетворяет всем предположениям леммы 7.3.7, он содержит в точности одну перемену знаков, и, очевидно, то же верно для преобразованного полинома

Нам осталось рассмотреть теперь только случай, когда в (V7) имеет место равенство, т.е.

Если то из (V4) мы видим, что и, очевидно, у преобразованного уравнения нет перемен знаков (лемма 7.3.6). В случае мы имеем и преобразованное уравнение редуцируется к степени Поскольку снова все корни имеют отрицательные вещественные части, мы заключаем из леммы 7.3.6, что не имеет перемен знаков. Таким образом, мы полностью доказали теорему.

Из теоремы 7.3.9 ясно видно, что — желаемая граница числа подстановок вида которые должны быть выполнены, чтобы получить уравнение с не более чем одной переменой знаков в последовательности его коэффициентов.

Следствие 7.3.10. В предположениях теоремы 7.3.9

Доказательство. По определению — наименьший индекс, такой, что одновременно выполняются оба неравенства (VI). Ясно, что одно из этих неравенств (а возможно, оба) не будет выполняться, если мы уменьшим на единицу; предположим, что не выполняется первое, так что

Применяя соотношение (с правой частью уравнения, округленной до ближайшего целого), где из (V9) получаем, что откуда заключаем, что

Более того, напомним, что из теоремы 7.2.12 (Mahler, 1964) мы имеем

Если мы объединим (V10) и (VII) и примем во внимание тот факт, что то следствие будет доказано. [Тот же результат получается, если предположить, что не выполнено второе неравенство

В большинстве представляющих интерес случаев и, таким образом, мы можем считать, что

Теорема 7.3.9 может использоваться для отделения вещественных корней полиномиального уравнения. Чтобы видеть, как она применяется, заметим следующее (для ясности и лучшего понимания мы повторяем некоторые части доказательства теоремы 7.3.9, где теперь заменяется на у):

i. Подстановка цепной дроби (V3) может также быть записана как

где есть подходящая дробь для цепной дроби

и, как уже говорилось, для к мы имеем

ii. Расстояние между двумя последовательными подходящими дробями равно Ясно, что наименьшее значение встречается, когда для всех i. Тогда число Фибоначчи. Это объясняет, почему существует связь между числами Фибоначчи и расстоянием Д в теореме 7.3.9.

iii. Пусть — уравнение, полученное из после подстановки вида (V13), соответствующей ряду сдаигов и инверсий. Заметим, что (V13) отображает интервал на х-интервал, неупорядоченные концевые точки которого — последовательные подходящие дроби Если длина этого х-интервала меньше, чем , то он содержит не более одного корня уравнения а соответствующее уравнение имеет не более одного корня в интервале .

iv. Если у — этот положительный корень уравнения то соответствующий корень уравнения может легко быть получен из (V13). Мы знаем только, что находится в интервале поэтому, подставляя вместо у в (V13) один раз 0, а другой мы получаем для положительного корня изолирующий интервал, неупорядоченные концевые точки которого — это Каждому положительно-му корню соответствует своя цепная дробь; нужно вычислить не более m неполных частных для отделения любого положительного корня. (Как мы уже упоминали, отрицательные корни могут быть отделены, если мы заменим на — в исходном уравнении.)

<< Предыдущий параграф Следующий параграф >>
Оглавление