Локализация Вещественных Корней (PDF)
Document Details
![PleasantBohrium1176](https://quizgecko.com/images/avatars/avatar-2.webp)
Uploaded by PleasantBohrium1176
Н.В. Зубов, О.В. Мутлу, М.Н. Зубова
Tags
Summary
This article presents Sturm's theorem and Euclid's algorithm, which determines the number of negative and positive real roots of a polynomial. The method applies to finding real roots of polynomials.
Full Transcript
Системы. Методы. Технологии образование коэффициентов (9) является порядка / Л. Д. Блистанова и [и др.] // допустимым. Теорема доказана. Труды средневолжского математического о-ва. 2002. Т 3-4, № 1. С. 250-251. Работа выполнена при финансо...
Системы. Методы. Технологии образование коэффициентов (9) является порядка / Л. Д. Блистанова и [и др.] // допустимым. Теорема доказана. Труды средневолжского математического о-ва. 2002. Т 3-4, № 1. С. 250-251. Работа выполнена при финансовой 5. Метод понижения порядка при поддержке РФФИ (пр. № 10-08-00624, 10- исследовании динамических свойств сис- 07-00286). тем автоматического регулирования / Л. Литература Д.Блистанова, И. В. Зубов, Н. В Зубов, Н. А. Северцев // Автоматика и телемеха- 1. Харитонов В.Л. Асимптотическая ника. 2005. № 2. С. 17-22. устойчивость семейства систем линейных 6. Конструктивные методы теории дифференциальных уравнений // Диффе- устойчивости и их применение к задачам ренц. уравнения. 1978. Т. 14, № 11. С. численного анализа / Л.Д. Блистанова [ и 2086-2088. др.]. СПб.: Изд-во НИИ Химии СПбГУ, 2. Биркгоф Дж. Д. Динамические 2002. 119 с. системы. М.; Л., 1941. 320 с. 7. Исследование устойчивости реше- 3. Блистанова Л.Д. Конструктивные ний дифференциальных уравнений / А. В. методы исследования устойчивости сис- Зубов [и др.]. СПб.: Мобильность плюс, тем с последействием. М. , 2004. 203 с. 2009. 224 с. 4. Критерий робастной устойчиво- сти для стационарных систем большого УДК 517.929 Н.В. Зубов*, О.В. Мутлу, М.Н. Зубова ЛОКАЛИЗАЦИЯ ВЕЩЕСТВЕННЫХ КОРНЕЙ С ПОМОЩЬЮ АЛГОРИТМА ШТУРМА В статье приведена известная теорема Штурма и реализующий эту теорему алго- ритм Евклида, позволяющий определить число отрицательных и положительных дей- ствительных корней многочлена. Ключевые слова: многочлен, корень, интервал, число перемен знака в системе, по- следовательность. Одной из основных задач современно- управлений и методов их синтеза, крите- го этапа развития науки, техники и тех- риев устойчивого, надежного и безопас- нологии являются фундаментальные ис- ного функционирования систем, имею- следования в области моделирования, щих различные особенности. управления, качественного и количест- Большинство математических моде- венного анализа динамики сложных лей, используемых при описании слож- управляемых систем. В связи с усложне- ных технических систем и технологиче- нием технических средств и систем ских процессов, претендующих на неко- управления необходимо разрабатывать торую целостность, представляют собой все более тонкие качественные и количе- динамические системы, функционирова- ственные методы исследования поведе- ние которых описывается системами ния решений динамических систем, по- обыкновенных дифференциальных урав- строения для этих систем программных нений. Если проводить исследование уп- * - автор, с которым следует вести переписку. 74 II. Моделиров ание и управление в технически х сист ема х рощенных математических моделей, не Определение 2. Пусть α – действи- учитывающих наличие различного рода тельное число, не являющееся корнем неопределенностей, возникающих как в многочлена f 0 ( z ) , т. е. f 0 (α) ≠ 0 , тогда силу различного рода неточностей и эм- число перемен знака W (α) в последова- пирических приближений при описании динамических характеристик объекта, так тельности чисел f 0 (α) , f1 (α) , K , f k (α) и влияния процессов износа, старения и (нулевые значения не учитываются) на- деградации, то можно прийти к неверным зывается числом перемен знаков в систе- техническим и технологическим решени- ме Штурма многочлена f 0 ( z ) при z = α. ям. Эти решения будут не только эконо- Теорема Штурма. Если действитель- мически невыгодны, но и увеличат веро- ные числа a < b таковы, что f s (a ) ≠ 0 , ятность аварий и катастроф. Необходимость исследований теории f s (b) ≠ 0 , ( s = 0,K, k − 1) и многочлен устойчивости полиномов и их характери- f 0 ( z ) не имеет кратных действительных стик неустойчивости диктуется, во- корней, тогда число действительных кор- первых, современными потребностями ней многочлена f 0 ( z ) , лежащих на про- науки и техники и ее приложениями в межутке [a, b] , равно W (a) − W (b). практических задачах, связанных с кон- струированием и моделированием про- Доказательство. Очевидно, что вели- цессов управления в технике, экономике, чина W ( z ) как функция действительного биологии и т. д., а во-вторых, наличием аргумента может изменяться тогда и большого числа нерешенных задач, пря- только тогда, когда ее аргумент z при мо связанных с инженерной практикой. своем возрастании совпадет с одним из Фактически, результаты, полученные в действительных корней α j системы теории устойчивости полиномов, позво- многочленов Штурма f0 ( z) , f1 ( z ) , ляют обеспечивать динамическую безо- пасность управляемых систем на этапе их K , f k ( z ) , т. к. один или несколько из этих конструирования и эксплуатации. многочленов в этой точке обратятся в Определение 1. Системой Штурма ноль (примут нулевые значения). называется последовательность много- Покажем, что при увеличении величи- членов с действительными коэффициен- ны z и ее прохождении через действи- тами f 0 ( z ) , f1 ( z ) , K , f k ( z ) , удовлетво- тельную величину α j , не являющуюся ряющих условиям: корнем многочлена f 0 ( z ) , а являющуюся 1. Многочлен f k ( z ) не имеет дейст- одним из корней (возможно кратных) од- вительных корней. ного или нескольких многочленов f1 ( z ) , 2. Если α – действительный корень K , f k −1 ( z ) , величина W ( z ) не изменится. многочлена f s ( z ) , т. е. f s (α) = 0 , то вы- Пусть номер s такой, что f s ( a j ) = 0 , то- полняются строгие неравенства гда из свойства 2 системы Штурма выте- f s −1 (α) ⋅ f s +1 (α) < 0 , s ∈ (1,K, k − 1). кает, что величины f s −1 ( a j ) и f s +1 (a j ) 3. Если α – действительный корень разных знаков. Обозначим через ε > 0 многочлена f 0 ( z ) , т. е. f 0 (α) = 0 , то мно- положительную величину, такую, что на гочлен f 0 ( z ) ⋅ f1 ( z ) при z = α изменяет интервале (α j − ε, α j + ε) многочлены знак с минуса на плюс. fi ( z ) , (0 ≤ i < k ) , для которых f i ( α j ) ≠ 0 , Заметим, что из свойства 2 этого опре- сохраняют знак. Такая положительная деления вытекает, что в системе Штурма величина всегда найдется в силу того, что у соседних многочленов действительные эти многочлены являются непрерывными корни не совпадают. функциями и не равны нулю в точке α j. 75 Системы. Методы. Технологии Тогда все тройки ( f s −1 ( z ) , f s ( z ) , f s +1 ( z ) ) многочлены fi ( z ) , (0 ≤ i < k ) , для кото- при изменении z от α j − ε до α j + ε со- рых f i ( α j ) ≠ 0 , сохраняют знак. Тогда храняют одну перемену знака. Действи- величина W ( z ) уменьшается на единицу тельно, в силу выбора числа ε > 0 вели- при изменении z от α j − ε до α j + ε , т. чины f s −1 ( z ) сохраняют на интервале к., во-первых, знак f 0 ( z ) меняется при (α j − ε, α j + ε) один и тот же знак, проти- z = α j (кратность корня α j равна едини- воположный знаку величины f s +1 ( z ) , ко- це по условию теоремы), а знак f1 ( z ) со- торая также сохраняет знак на этом ин- храняется, и во-вторых, число перемен тервале. Отсюда вытекает, что вне зави- симости от того, как поменялся знак у знаков в системе многочленов f 2 ( z ) , величины f s ( z ) при переходе z через K , f k ( z ) при изменении z от α j − ε до величину α j , число перемен знака у α j + ε не меняется (это было доказано в этих троек равно единице. Это видно из первой части теоремы). следующего представления возможных Итак, при прохождении аргумента z перемен знаков – тройки (+, ?, -) или (-, ?, через действительный корень α j много- +) имеют одну перемену знака вне зави- члена f 0 ( z ) величина W ( z ) уменьшается симости от того, как изменился знак на единицу. Следовательно, число дейст- среднего элемента. Таким образом, если в системе много- вительных корней многочлена f 0 ( z ) , ле- членов Штурма выделить тройки, для ко- жащих на промежутке [a, b] , равно торых f s ( a j ) = 0 , то многочлены fi ( z ) не W (a) − W (b) , т. к. при изменении z от a входящие в эти тройки на интервале до b величина W ( z ) уменьшается на (α j − ε, α j + ε) , сохраняют свой знак, а в число корней многочлена f 0 ( z ) , лежащих выделенных тройках при переходе z че- на этом промежутке. Теорема доказана. рез величину α j число перемен знака Замечание 1. Если b → ∞ , то величи- сохраняется и равно единице. Отсюда на W (b) = W (+∞) определяется числом вытекает, что число перемен знака в сис- перемен знака коэффициентов многочле- теме Штурма многочлена f 0 ( z ) на ин- нов f 0 ( z ) , f1 ( z ) , K , f k ( z ) , стоящих при тервале (α j − ε, α j + ε) сохраняется не- старших степенях z , т. к. при z → ∞ по- изменным, т. к. при переходе z через ве- ведение многочленов fi ( z ) , (0 ≤ i < k ) и личину α j перемена знаков возможна их знаки определяются знаками коэффи- циентов, стоящих при старшей степени z. только у многочленов, равных нулю в Нетрудно видеть, что величина W (0) данной точке α j , а они находятся между равна числу перемен знаков в последова- многочленами разных знаков, сохраняю- тельности f 0 (0) , f1 (0) , K , f k (0) , т. е. щие эти знаки при данном переходе, что никак не влияет на общее число перемен числу перемен знаков среди свободных знака. членов многочленов f0 ( z) , f1 ( z ) , Пусть теперь α j – действительный ко- K , fk ( z). рень многочлена f 0 ( z ). Из свойства 3 При a → −∞ величина W ( a) = W (−∞) системы Штурма следует, что f1 (α j ) ≠ 0 , определяется числом перемен знака в по- следовательности но возможно f s ( a j ) = 0 для некоторых am0 ⋅ ( −1) mo , am1 ⋅ ( −1) m1 , K , amk ⋅ (−1) mk , номеров (1 < s < k ). Возьмем число ε > 0 таким, что на интервале (α j − ε, α j + ε) 76 II. Моделиров ание и управление в технически х сист ема х где mi степень многочлена fi ( z ) , а ami f 0 ( z ) ⋅ f1 ( z ) также меняет в этой точке его коэффициент, стоящий при старшей знак с минуса на плюс. степени z. 4. Если величина f s ( α) = 0 , то вели- Таким образом, у многочлена f 0 ( z ) чины f s −1 (α ) ≠ 0 и f s +1 ( α) ≠ 0 , а величина число отрицательных вещественных кор- f s −1 (α ) f s +1 (α ) < 0. Ибо при выполнении ней равно величине W (−∞) − W (0) , а чис- хотя бы одного из равенств f s −1 (α ) = 0 ло положительных вещественных корней равно величине W (0) − W (+∞). или f s +1 ( α) = 0 из формул (1) вытекает, Замечание 2. Если многочлен f 0 ( z ) что справедливо и второе равенство и да- лее по цепочке формул (1) выполняются имеет кратные корни на промежутке соотношения [a, b] , то величина W (a) − W (b) есть чис- f s −2 (α) = 0 , K, f1 (α ) = 0, f 0 (α) = 0 , ло различных действительных корней из что противоречит п. 1. Итак, мы показа- интервала [a, b]. ли, что если f s ( α) = 0 , то f s −1 (α ) ≠ 0 и Замечание 3. Если f 0 ( z ) – многочлен f s +1 ( α) ≠ 0. Тогда, умножая величину с действительными коэффициентами, не имеющий кратных действительных кор- f s −1 (α) на f s +1 (α ) , из формул (1) получим ней, то всегда можно построить систему f s −1 (α ) f s +1 (α ) = − f s2+1 (α ) < 0. многочленов Штурма, разделив много- Из пунктов 1-5 вытекает, что постро- член f 0 ( z ) на многочлен f1 ( z ) = f 0′( z ) по енная система многочленов (1) является алгоритму Евклида, заменив знаки у всех системой Штурма. остатков на противоположные Замечание 4. В предыдущем разделе Rs ( z ) = − f s ( z ). мы показали, что любой многочлен мож- f 0 ( z ) = f1 ( z )Q1 ( z ) − f 2 ( z ) но представить в виде произведения про- стых многочленов, имеющих только про- f1 ( z ) = f 2 ( z )Q2 ( z ) − f3 ( z ) стые корни. Это позволяет применять ме- M (1) тод Штурма к любым многочленам, f s −1 ( z ) = f s ( z )Qs ( z ) − f s +1 ( z ) предварительно представив их в виде f s − 2 ( z ) = f s −1 ( z )Qs −1 ( z ) − f s ( z ) произведения простых многочленов, применяя далее этот метод отдельно для M каждого из сомножителей. f k −2 ( z ) = f k −1 ( z )Qk −1 ( z ) − f k ( z ) Работа выполнена при финансовой Действительно: поддержке РФФИ (пр. № 10-08-00624, 10- 1. Многочлены f 0 ( z ) и f1 ( z ) имеют 07-00286). в силу замечания различные корни. 2. Многочлен f k ( z ) в силу теоремы Литература является числом и не имеет действитель- 1. Курош А. Г. Курс высшей алгеб- ных корней. ры. М.: Наука, 1971. 431 с. 3. Если действительная величина α 2. Зубов А. В. Стабилизация и управ- является корнем многочлена f 0 ( z ) , т. е. ление в динамических системах. СПб.: f 0 (α) = 0 и многочлен f 0 ( z ) в этой точке СПбГУ, 2007. 132 с. возрастает, то f 0′(α) > 0 и, следовательно, 3. Стрекопытова М. В. Исследование равновесных движений. СПб.: СПбГУ, многочлен f 0 ( z ) ⋅ f1 ( z ) меняет в этой точ- 2007. 95 с. ке знак с минуса на плюс. Если же мно- 4. Зубова А. Ф. Математические ме- гочлен f 0 ( z ) в этой точке убывает, то тоды исследования надежности колеба- f 0′(α ) < 0 и, следовательно, многочлен тельных систем в технике и технологиче- ских процесса. СПб.: СПбГУ, 2007. 339 с. 77 Системы. Методы. Технологии 5. Зубов А. В., Зубов Н. В. Теория численного анализа. СПб.: Изд-во НИИ устойчивости и применение к задачам Химии СПбГУ, 2010. 102 с. 6. УДК 519.71;62.50 В.В. Осипов ИДЕЙНЫЕ ОСНОВЫ МЕТОДА ТОЧЕЧНЫХ ПРЕДСТАВЛЕНИЙ Предлагается приближенно-аналитический аппарат математического моделиро- вания линейных динамических систем, названный методом точечных представлений, использующий точечное представление функций и операторов. Ключевые слова: метод точечных представлений, точечное моделирование. Метод точечных представлений как циированным с N-сеткой (2), которая яв- метод математического моделирования ляется чебышевской сеткой. динамических систем, описываемых ли- Установлено, что такая сетка – наи- нейными дифференциальными уравне- лучшая среди всевозможных ортогональ- ниями различного типа, обладает боль- ных сеток по целому ряду показателей шими аналитическими возможностями, качества интерполяционного приближе- весьма конструктивен и эффективен. Эти ния функции и, следовательно, интерпо- качества метода связаны прежде всего с ляционные конструкции различного типа, особыми алгебраическими свойствами восстанавливающие функцию f(τ) по ее аналитического аппарата, которые ис- точечному изображающему N-вектору (1) пользуются для описания точечных пред- – наиболее точные приближающие моде- ставлений как конечномерных моделей ли этой функции. функции и операторов. Рассмотрим теперь пространство В основе метода лежит простая идея. M(0,1) всех кусочно-непрерывных функ- Любой непрерывной на [0,1] функции ций, определенных на [0,1]. Сделаем его f(τ) и, следовательно, элементу гильбер- нормированным, вводя Sup-норму: това пространства L2 (0,1) ставится в со- f = Sup f (τ) f (τ) ∈ M (0,1). (3) ответствие N-мерный вектор τ∈[0,1] f T = Colon[f (τ1( N ) ),...f (τ (νN ) ),...f (τ (NN ) )] ,(1) Тогда С(0,1) – пространство всех не- прерывных на [0,1] функций – становится составленный из отсчетов этой функции в подпространство в М(0,1), причем узлах ортогональной N-сетки: ϕ = Sup ϕ(τ) = Max ϕ(τ) τ∈[0,1] τ∈[ 0,1] {τ (N) ν } / CosNπτν( N ) = 0 ⇔ τ ν( N ) = ϕ(τ) ∈ C (0,1) ⊂ M (0,1). Относительно введенной нормы про- 2ν − 1 (2) = (ν = 1, N). странства М(0,1) и С(0,1) окажутся пол- 2N ными, т. е. банаховыми пространствами. Заметим, что пространство М(0,1) одно- Вектор fT назван точечным изобра- временно является и гильбертовым про- жающим вектором функции f(τ), ассо- странством L2(0,1). Поскольку произве- 78