Алгебра · объяснение и практика

Сколько корней между границами: проверка знаков без приближённого поиска

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

Неизвестное x показывает найденное значение — пять.

В теме Многочлены: деление и корни · Учебная карта

Главная мысль

Последовательность Штурма позволяет посчитать корни, не находя их координаты. Нужно построить цепочку отрицательных остатков, подсчитать перемены знаков на двух границах и вычесть правое число из левого. Границы в выбранном интерфейсе не являются корнями исходного многочлена.

Метод и постановка

Начните с самого многочлена и его производной. Каждый следующий член равен остатку деления двух предыдущих, взятому с противоположным знаком. Минус является частью конструкции: произвольная замена его плюсом разрушает правило перемен знаков. Когда остаток нулевой, цепочка заканчивается. Рациональная арифметика помогает различать точный ноль и маленькое численное приближение.

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

Проверка и границы вывода

Разность двух количеств перемен знака даёт число различных действительных корней внутри. Кратный корень учитывается как одна точка. Результат поэтому не обязан совпадать со степенью или числом корней с алгебраическими кратностями. Комплексные корни в этот счёт не входят. Нулевой ответ означает отсутствие действительных корней именно на данном открытом интервале, а не отсутствие корней где-либо.

Для независимой проверки используйте многочлен с известным разложением и отдельно случай с повторным множителем. Проверка только многочленов со всеми простыми корнями не выявляет путаницу с кратностями. Метод также не обещает приближения координат: после подсчёта можно сужать интервалы другой процедурой, сохраняя проверки границ. Знак выражения на концах сам по себе недостаточен: между одинаковыми знаками может находиться два или больше корней. Именно дополнительная цепочка различает такие случаи и делает ответ содержательнее обычной проверки смены знака.

Пример

У P=x³−x корни −1,0,1. Интервал (−3/2,3/2) содержит все три, хотя вычислять десятичные приближения не нужно.

Для P=(x−1)² на интервале (0,2) ответ равен одному различному корню. Одинаковый положительный знак P на концах не означает пустой интервал корней.

От чтения к действию

А теперь — вы

Метод сообщил один корень для (x−1)² на (0,2). Почему не два?

Частые вопросы

Кратный корень считается несколько раз?

Нет. Здесь считается число различных корней, независимо от их кратности.

Можно ставить границу точно в корень?

В этом интерфейсе нет: обе границы должны иметь ненулевое P. Это сохраняет однозначную открытую интервальную договорённость.

Углублённый разбор

Кратные корни и квадратсвободная часть перед Штурмом

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

Перед началом: Производная многочлена; Точный полиномиальный НОД.

Один общий делитель отделяет различные корни от повторений

Работаем с ненулевым многочленом над рациональными числами, нормируя НОД старшим коэффициентом 1. Если P=(x−α)ᵐh и h(α)≠0, то P′ содержит этот множитель в степени m−1. Поэтому НОД(P,P′) содержит его ровно с этой степенью, а Q=P/НОД(P,P′) оставляет α один раз.

Q имеет те же различные корни, что P, и не содержит повторных множителей. Для вещественного счёта можно строить цепочку Штурма по Q меньшей степени. Однако замена сама по себе теряет число повторений. Если требуется сумма алгебраических кратностей на интервале, нужно сохранить дополнительную информацию, а не выдать число различных точек за ответ.

Повторяйте НОД, сохраняя квадратсвободные слои

Положим G₀ равным монической нормализации P, затем Gᵢ₊₁=НОД(Gᵢ,Gᵢ′), пока не получим 1. Каждый шаг уменьшает положительную кратность каждого оставшегося корня на единицу. Отношение Sᵢ=Gᵢ/Gᵢ₊₁ квадратсвободно и содержит именно корни, чья исходная кратность больше i.

Следовательно, исходная кратность корня равна числу слоёв Sᵢ, в которых он встречается. Произведение всех слоёв возвращает G₀ телескопически. Это даёт два контроля: точное восстановление многочлена и нужную повторяемость каждого множителя. Отдельные слои могут совпадать; это содержательное свидетельство повторной кратности, а не причина удалить дубликат.

Подсчёт по интервалу можно делать послойно

Если на границах нет корней, число различных корней слоя находится обычным точным методом Штурма. Сумма этих чисел по всем слоям даёт число корней P с кратностями внутри интервала. А первый слой S₀ даёт число различных точек. Таким образом, два разных запроса получают разные, явно подписанные ответы.

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

Два корня, пять повторений

Условие. Для P=(x−1)³(x+2)² найдите квадратсвободные слои и восстановите кратности корней, не смешивая их с числом различных точек.

  1. G₁=НОД(P,P′)=(x−1)²(x+2). После следующего НОД получаем G₂=x−1, затем G₃=1.
  2. Слои S₀=P/G₁=(x−1)(x+2), S₁=G₁/G₂=(x−1)(x+2), S₂=G₂/G₃=x−1.
  3. Корень 1 встречается в трёх слоях, поэтому имеет кратность 3. Корень−2 встречается в двух, его кратность 2.
  4. В интервале(−3,2) каждый из первых двух слоёв имеет два корня, последний — один. Различных точек 2, сумма кратностей 2+2+1=5.

Ответ. Слои:(x−1)(x+2),(x−1)(x+2),x−1; кратности 1→3,−2→2.

Проверка. Произведение трёх слоёв точно равно P. Прямая проверка производных в 1 и−2 даёт первый ненулевой порядок 3 и 2 соответственно, независимо подтверждая обе кратности.

Где легко ошибиться. Не удаляйте одинаковые квадратсвободные слои как лишние. Их повторение хранит исходную кратность, которую первый квадратсвободный многочлен уже не различает.

Проверьте понимание

Какова сумма кратностей внутри(−3,2) в задаче?

Вопросы к этой главе

Нужно вычислять сами корни для такого разложения?

Нет. Полиномиальные НОД и деления выполняются точно над рациональными коэффициентами. Связь с отдельными корнями нужна для доказательства смысла слоёв.

Слой может содержать комплексные корни?

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

Сверить определения и условия

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

  • Manuel Eberl: A Formalisation of Sturm’s Theorem

    Первичная формализация автора: вебом прочитаны §2.5.1 о p/gcd(p,p′), оптимизация кратных корней и count-roots-between с условиями концов. Многослойное восстановление кратностей и изолирующие интервалы конкретных многочленов главы рассчитаны отдельно.

Точная изоляция корня рациональными границами

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

Перед началом: Цепочка Штурма; Рациональные границы.

Сохраняйте число корней каждого рабочего интервала

Для квадратсвободного P с рациональными коэффициентами построим цепочку Штурма. Обозначим V(t) число перемен знака её ненулевых значений. Если P(a) и P(b) ненулевые, то V(a)−V(b) даёт число корней в(a,b). Счёт 0 позволяет отбросить интервал, счёт 1 уже даёт изоляцию, больший счёт требует дальнейшего разделения.

Разбивая интервал рациональной серединой c, сначала проверяют P(c). Если она ненулевая, два новых счётчика должны суммироваться в старый. Если середина сама корень, её выделяют отдельно и применяют явно оговорённую обработку концов. Нельзя подставить корневую границу в формулу с условием ненулевых концов и молча сохранить прежнюю трактовку открытого интервала.

Точный сертификат перемен знака
ГраницаЗнаки цепочкиV
−2+ − + − +4
−3/2− + − − +3
−1+ + − − +2
1+ − − + +2
3/2− − − + +1
2+ + + + +0

Узость и единственность являются разными сертификатами

Если нужна численная точность ε, продолжают делить уже изолированный интервал до ширины не больше 2ε. Его середина тогда отличается от единственного корня не более чем на ε. Одна малая ширина без счётчика 1 могла бы описывать пустой промежуток либо содержать несколько очень близких корней.

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

Знаки исходного многочлена не заменяют цепочку

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

Вычисляйте знаки рационально: знак очень малого значения с плавающей точкой способен ошибочно поменять счётчик. Промежуточные нулевые члены цепочки пропускают по определению V. Для независимого контроля удобно выбрать многочлен с отдельной факторизацией, которая позволяет проверить расположение корней без повторения вычисленной цепочки.

Две положительные пары за одинаковыми знаками

Условие. Изолируйте все корни P=x⁴−5x²+6, используя рациональные границы−2,−3/2,−1,1,3/2,2.

  1. Цепочка равна P,4x³−10x,(5/2)x²−6,(2/5)x,6. Все её остаточные равенства проверяются точным делением.
  2. Числа перемен знака на перечисленных границах равны 4,3,2,2,1,0. На внешних положительных концах 1 и 2 сам P равен 2, но счётчик между ними падает на 2.
  3. Получаем по одному корню в(−2,−3/2),(−3/2,−1),(1,3/2),(3/2,2). В(−1,1) корней нет.
  4. Найдено четыре различных корня, что равно степени P. Поэтому других действительных корней вне этих интервалов уже нет.

Ответ. Четыре указанных интервала содержат ровно по одному корню и образуют полный изолирующий список.

Проверка. Факторизация P=(x²−2)(x²−3) даёт±√2,±√3. Неравенства 1<2<9/4<3<4 независимо размещают их в тех же четырёх интервалах.

Где легко ошибиться. Не объявляйте короткий интервал изолирующим без доказательства количества корней. И не теряйте точный корень, если очередная рациональная середина сама обращает P в ноль.

Проверьте понимание

Сколько корней P лежит в(1,2), несмотря на P(1)=P(2)?

Вопросы к этой главе

Изолирующие интервалы обязаны быть одинаковой длины?

Нет. Требуются непересечение и ровно один корень в каждом. Длины выбирают по дальнейшей задаче: только различить корни либо ещё обеспечить нужную ошибку приближения.

Почему здесь не нужна отдельная внешняя граница?

Четыре непересекающихся интервала уже содержат четыре различных корня многочлена степени 4. Это исчерпывает его возможные корни; для общего многочлена такой аргумент может не сработать.

Сверить определения и условия

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

  • Manuel Eberl: A Formalisation of Sturm’s Theorem

    Первичная формализация автора: вебом прочитаны §2.5.1 о p/gcd(p,p′), оптимизация кратных корней и count-roots-between с условиями концов. Многослойное восстановление кратностей и изолирующие интервалы конкретных многочленов главы рассчитаны отдельно.

Положительность многочлена по коэффициентам Бернштейна

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

Перед началом: Биномиальная формула; Замена переменной на конечном отрезке.

Базис образует разбиение единицы

На [0,1] многочлены B_(k,n)(t)=C(n,k)tᵏ(1−t)^(n−k) неотрицательны, а их сумма равна единице. Если p(t)=Σb_kB_(k,n)(t), то каждое значение p является выпуклой комбинацией коэффициентов b_k. Поэтому min b_k≤p(t)≤max b_k на всём отрезке, включая концы.

Все строго положительные b_k дают достаточный сертификат p>0. Все неотрицательные дают p≥0, но не обязательно строгий положительный запас. Коэффициенты степенного базиса не обладают тем же смыслом на произвольном отрезке; перед применением сертификата необходимо действительно перейти в нужный базис и проверить точное полиномиальное тождество.

Локализация меняет коэффициенты, сохраняя сам многочлен

Для [a,b] сначала подставляют x=a+(b−a)t. Деление исходного отрезка в точке c создаёт два новых многочлена по локальным переменным, каждый снова записывается в базисе Бернштейна. Новые коэффициенты можно получить алгоритмом де Кастельжо — последовательными выпуклыми смесями старых коэффициентов.

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

Неудачный сертификат не равен отрицательному ответу

Наличие отрицательного b_k означает лишь, что текущая выпуклая оболочка коэффициентов заходит ниже нуля. Сам график может оставаться строго положительным. Тогда уточнение разбиения способно убрать лишнюю ширину оболочки. В отличие от проверки конечной сетки, положительные коэффициенты контролируют все точки каждого подотрезка.

Если многочлен имеет нуль внутри, строгий положительный сертификат на всём отрезке невозможен. А если коэффициенты только неотрицательны, нужно отдельно разбирать возможное достижение нуля и нужную постановку: доказательство отсутствия отрицательных значений слабее явной нижней границы больше нуля. Численные округления коэффициентов без направленного контроля могут разрушить строгость сертификата.

Отрицательный общий коэффициент исчезает после деления

Условие. Докажите p(x)=x²−x+3/10>0 на [0,1] с помощью квадратичного базиса Бернштейна и одного деления в x=1/2. Найдите гарантированную нижнюю границу.

  1. В базисе степени два имеем p=b₀(1−x)²+2b₁x(1−x)+b₂x². Сравнение коэффициентов даёт b=(3/10,−1/5,3/10). Общая нижняя оценка −1/5 ничего не доказывает о положительности.
  2. Средние соседей равны 1/20 и 1/20, а следующее среднее тоже 1/20. Де Кастельжо даёт левую тройку (3/10,1/20,1/20) и правую (1/20,1/20,3/10).
  3. Все шесть локальных коэффициентов не меньше 1/20. Поскольку локальные базисы неотрицательны и суммируются к единице, p(x)≥1/20 на каждой половине и на всём [0,1].
  4. Прямой пересчёт на левой половине x=t/2 даёт t²/4−t/2+3/10 и ту же левую тройку. Правая половина симметрична относительно x=1/2.
  5. Независимо выделяем квадрат: p=(x−1/2)²+1/20. В точке 1/2 нижняя граница достигается, поэтому полученный сертификат оказался точным.

Ответ. p(x)≥1/20>0 на [0,1]. Одного деления достаточно; исходный отрицательный коэффициент не означал отрицательного значения функции.

Проверка. Сравнение степенных коэффициентов обеих локальных записей и выделение квадрата независимо подтверждают нижнюю границу и её достижение.

Где легко ошибиться. Не делайте вывод p<0 из отрицательного коэффициента Бернштейна. Это отказ конкретной достаточной проверки, а не найденная точка с отрицательным значением.

Проверьте понимание

Какую точную положительную нижнюю границу даёт указанное деление пополам?

Вопросы к этой главе

Почему одной проверки в пяти узлах недостаточно?

Между узлами многочлен может опускаться ниже проверенных значений. Бернштейнов сертификат работает на всём подотрезке благодаря неотрицательности базиса, а не только в точках выборки.

Нужно ли увеличивать степень для деления отрезка?

Нет. В примере обе локальные записи остаются квадратичными. Меняются коэффициенты после аффинной замены переменной, а не степень исходного многочлена.

Сверить определения и условия

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

  • T. Hamadneh: Bounding polynomials in Bernstein forms

    Прочитаны свойство выпуклой оболочки в §3.1.7 и описание локализации посредством разбиения. Вся диссертация не заявляется прочитанной. Рациональный квадратичный пример и таблица де Кастельжо вычислены независимо.

Рекурсия Шура: все корни строго внутри единичного круга

Многочлен может не иметь действительных корней и всё же нарушать требование |z|<1. Рекурсия Шура проверяет сразу весь комплексный набор: на каждой стадии сравнивает крайние коэффициенты и понижает степень. Последовательность строгих проверок даёт необходимый и достаточный критерий, а не приближённую картинку корней.

Перед началом: Комплексные корни и их модули; Рациональная арифметика и коэффициенты многочлена.

Порядок коэффициентов определяет взаимный многочлен

Вещественный многочлен конечной степени с ненулевым старшим коэффициентом; открытый единичный круг.

Пусть P(z)=a₀zⁿ+a₁zⁿ⁻¹+…+aₙ, где a₀≠0 и все коэффициенты вещественны. Здесь индексы идут от старшей степени. Взаимный многочлен P*(z)=zⁿP(1/z) имеет коэффициенты в обратном порядке. На единичной окружности |P*|=|P|. В нуле P* равно a₀, даже когда постоянный коэффициент самого P нулевой.

Произведение модулей всех корней равно |aₙ/a₀|. Поэтому |aₙ|<|a₀| необходимо, если каждый корень строго внутри круга. Одной этой проверки недостаточно: два корня могут иметь произведение меньше единицы, когда один из них снаружи. Например, у z²−2z+1/4 один корень больше единицы, хотя постоянный коэффициент мал.

Понижение степени сохраняет строгое свойство

При |aₙ|<|a₀| построим Q(z)=[a₀P(z)−aₙP*(z)]/z. Постоянный член числителя точно сокращается. Старший коэффициент равен a₀²−aₙ² и ненулевой, поэтому степень Q на единицу меньше. Деление всех коэффициентов Q на старший не меняет его корни; такая нормировка удобна для следующего шага.

Смысл шага можно проверить на границе. Если P не имеет там нуля, то |aₙP*|<|a₀P|, и сравнение Руше показывает: числитель имеет столько же внутренних нулей, сколько P. Один нуль числителя уже выделен как множитель z, поэтому N(P)=N(Q)+1. Граничный нуль P одновременно был бы граничным нулём Q; обратное тоже верно при строгом неравенстве крайних коэффициентов. Отсюда P имеет все n корней внутри тогда и только тогда, когда Q имеет все n−1 корней внутри.

Строгая граница и смысл отрицательного ответа

Рекурсия заканчивается ненулевой константой после n успешных проверок. Константа уже не имеет корней и не добавляет нового условия. Если на какой-либо стадии |aₙ|≥|a₀|, строгое расположение всех исходных корней внутри исключено. При равенстве нельзя объявлять, что каждый корень лежит на окружности: известен только провал строгого общего свойства.

Точные дроби позволяют отличить равенство от небольшого запаса. Это особенно полезно около границы устойчивости, где десятичный расчёт способен сменить знак сравнения. Инструмент не ищет координаты и не сообщает число внешних или граничных корней. Его ответ уже: выполнено ли требование ко всему набору корней данного многочлена.

Три последовательных строгих проверки

Условие. Для P(z)=z³−7z²/12−z/24+1/24 постройте рекурсию Шура и решите, все ли корни лежат строго в |z|<1.

  1. Первый отражательный коэффициент k₃=a₃/a₀=1/24. Его модуль меньше единицы; после вычитания взаимного многочлена старший коэффициент числителя равен 575/576.
  2. Деление на z и нормировка дают Q(z)=z²−67z/115−2/115. Постоянный коэффициент k₂=−2/115 также удовлетворяет строгому условию.
  3. Следующее понижение имеет ненормированные коэффициенты 13221/13225 и −7839/13225. После нормировки получаем R(z)=z−67/113, поэтому k₁=−67/113.
  4. Третье сравнение строгое: 67<113. Последний шаг оставляет ненулевую константу. Значит, все три корня исходного P находятся в открытом единичном круге.

Ответ. Все три корня строго внутри |z|<1; коэффициенты проверок: 1/24, −2/115, −67/113.

Проверка. Независимое разложение P=(z−1/2)(z−1/3)(z+1/4) возвращает все коэффициенты. Модули трёх явно найденных корней меньше единицы, что проверяет вывод без повторения рекурсии.

Где легко ошибиться. Не останавливайтесь на малом произведении модулей корней. Оно является только первой необходимой проверкой; полный критерий требует всей цепочки понижений.

Строгая устойчивость многочлена в единичном круге

От 2 до 9 рациональных коэффициентов от старшей степени; старший ненулевой. Модуль каждого≤1000, знаменатель≤1000. Проверяется, что ВСЕ корни лежат строго в |z|<1. Равенство на проверяемой границе не даёт строгого сертификата; это не подсчёт граничных корней.

Данные для расчёта

Проверьте понимание

Для разобранного P(z)=z³−7z²/12−z/24+1/24 что доказывают все три строгие проверки?

Вопросы к этой главе

Что происходит при нулевом постоянном коэффициенте?

Первый коэффициент проверки равен нулю, условие строго выполнено. Шаг просто выделяет корень z=0 и продолжает проверку оставшейся части; нулевой корень расположен внутри круга.

Можно ли заменить строгие знаки нестрогими?

Нет. При равенстве старший коэффициент пониженного многочлена обнуляется и использованная эквивалентность уже не применяется. Отдельный анализ граничных корней требует другого алгоритма.

Сверить определения и условия

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

  • UCCS, Modern DSP — Schur–Cohn Stability Test, §5.2.1

    Критерий отражательных коэффициентов и рекурсия взаимного многочлена. Порядок коэффициентов в нашей главе явно выбран от старшей степени; дробный пример и независимое разложение подготовлены отдельно.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться