О разрешимости систем символьных полиномиальных уравнений и приложении

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

О РАЗРЕШИМОСТИ СИСТЕМ СИМВОЛЬНЫХ ПОЛИНОМИАЛЬНЫХ УРАВНЕНИЙ И ПРИЛОЖЕНИИ
© Егорушкин О. И. *, Колбасина И. В. *, Сафонов К. В. *
Сибирский государственный аэрокосмический университет имени академика М. Ф. Решетнева, г. Красноярск
Разработаны подходы к решению систем некоммутативных полиномиальных уравнений, основанные на связи с соответствующими коммутативными уравнениями. Результаты имеют приложение в теории автоматического управления.
Ключевые слова: некоммутативное кольцо, полиномиальные уравнения, формальный степенной ряд, коммутативный образ.
1. Рассмотрим систему полиномиальных уравнений
Р (2,X) = 0,} = (1)
где х (хь …, хп), х (хь. хт) — переменные из кольца с некоммутативной операцией умножения и коммутативной операцией сложения- для них определена также коммутативная операция умножения на комплексные числа. Система (1) решается относительно переменных хь …, хп в виде формальных степенных рядов (ФСР) от переменных х1, …, хт. Такие системы имеют прикладное значение, частности, они порождают определенные классы формальных языков: контекстно--свободных, непосредственно составляющих, в нормальной форме Грейбах и др. В теории программирования система (1) рассматривается как грамматика над терминальными символами х1,., хт -словами языка, и нетерминальными символами хь …, хп, необходимыми для задания грамматики [1−3]. Важное приложение таких уравнений лежит в области теории управляющих систем [4].
Однако, подходы к решению таких систем практически не разработаны. Задача исследования состоит в получении условий совместности и несовместности системы (1), что позволило бы в дальнейшем разрабатывать методы решения.
В данной работе исследуется связь некоммутативной системы (1) с её коммутативным аналогом, называемым коммутативным образом системы, даются некоторые условия совместности и несовместности.
2. Уточним, что означает равенство двух ФСР от переменных х1, …, хт. над указанным кольцом. Упорядочим члены ФСР следующим образом: сгруп-
* Старший преподаватель кафедры Прикладной математики.
* Аспирант кафедры Прикладной математики.
& quot- Заведующий кафедрой Прикладной математики, доктор физико-математических наук, доцент.
пируем все мономы от хь …, хт в однородные многочлены, которые расположим по возрастанию степеней, затем, переходя от меньшей степени к большей, нумеруем мономы каждого однородного многочлена в лексикографическом порядке. Таким образом, нулевой номер присваивается моному нулевой степени (единице кольца), номера 1, …, т — мономам х1, …, хт, линейная комбинация которых образует однородный многочлен первой степени, далее в лексикографическом порядке нумеруются мономы однородного многочлена второй степени и т. д. При таком упорядочивании все возможные мономы от символов х1,., хт единственным образом записываются в виде последовательности {и,}да,=0, играющей роль универсального базиса ФСР от х1, …, хт, теперь каждый ряд 5 можно однозначно записать в виде разложения по универсальному базису:
да
5 = Е& lt- Щ & gt- щ, (2)
1=0
здесь & lt-5, и& gt- - числовой коэффициент при мономе и?.
Наконец, будем считать, что два ФСР равны в том и только в том случае, когда равны соответствующие числовые коэффициенты этих рядов при мономах универсального базиса. Теперь имеет смысл вопрос не только о существовании, но и единственности решения системы уравнений (1).
Дадим следующее определение. Будем говорить, что система уравнений (1) имеет бесконечно много решений, если её общее решение зависит хотя бы от одного произвольного ФСР от переменных х1, …, хт.
3. Поставим в соответствие ФСР (2) его коммутативный образ а (5) — степенной ряд, который получается из 5 в предположении, что символы х1, …, хт обозначают коммутативные переменные, принимающие значения из поля комплексных чисел.
В этом предположении любой моном ui можно записать в виде
х ('- ¦¦¦'- х1& quot-, где щ — число вхождений (степень) degx. (uI) символа в моном. Если
обозначить мультииндекс, а = (аь …, от), то можно записать, а = degx (uI¦) и далее равенства:
да да
С1(5) = а (^& lt- 5, Щ & gt- Щ) = Х& lt- 5, Щ & gt- С1(и1) =
'-=° '-=° (3)
= Х (X & lt- 5, Щ & gt-)ха =Х СщХ0.
а а=degx (щ) а
Впервые коммутативный образ ФСР рассмотрел А. Л. Семёнов, использовав его как инструмент решения ряда алгоритмических проблем [5].
Обозначим г = г (х) = ^(х), …, гп (х)) решение системы (1), представленное ФСР.
Имеет место следующая теорема.
Теорема 1. Если х = х (х) — решение некоммутативной системы уравнений (1) в виде символьных ФСР, то коммутативные ФСР х = с/(х (х)) над полем комплексных чисел сходятся в окрестности нуля, определяя ростки голоморфных алгебраических функций, и являются решением коммутативной системы уравнений
с1(Р1(х, х)) -… — а (Р" (2, х)) = 0. (4)
Для доказательства заметим, что имеют место равенства:
еЩ (х, х)) и,^)) = (2(х), х)) —) — ^0• сг (и,) — 0,] - 1,…, п,
т. е. с/(х (х)) — решение системы уравнений (3).
Таким образом, если некоммутативная система (1) совместна, то и коммутативная система (4) совместна. Обратное, вообще говоря, неверно. Так, система уравнений
X — х2 = 0,
X х 2 х^ I х2х — 0
— несовместная, тогда как её коммутативный образ имеет бесконечно много решений: XI = х2 = ^ где t — произвольное комплексное число или функция.
Кстати, этот пример опровергает гипотезу о том, что система (1) имеет решение х = х (х) в виде ФСР тогда и только тогда, когда система (4) имеет решение в виде вектор-функции х = х (х) голоморфной в начале координат.
Обозначим два множества ростков аналитических множеств в нуле:
а (Бр) — {х — а (х (х)): Р^(х (х), х) — 0-у — 1,…, п},
Р) — {х — х (х): с,(Р (х (х) х)) — 0 У — п}.
С учётом приведенного примера и сделанных обозначений, теорему 1 можно сформулировать следующим образом.
Теорема 1. Имеет место включение: с/(5р) с SCI¦(P).
Кроме того, теореме 1 эквивалентна следующая теорема.
Теорема 2. Если коммутативная система уравнений (4) несовместна, то и некоммутативная система (1) несовместна.
Таким образом, условия несовместности системы коммутативной уравнений представляют интерес.
Естественно, что интерес представляют также условия единственности решения и бесконечности числа решений системы уравнений (1).
Дадим следующее определение. Будем говорить, что система уравнений (1) имеет бесконечно много решений, если совокупность её решений зависит хотя бы от одного произвольного ФСР от переменных хь …, хт.
Так, система из двух одинаковых уравнений х1×1 — г2×2 = 0 имеет решение = 5×2, г2 = х15, где 5 — произвольный ФСР от х1, …, хт, а значит, эта система имеет бесконечно много решений.
Пусть
0(С1(Р1): — С1(РП)) = щд (а (Р, (2, х))) D (zl,¦¦¦, 2п) д^
— якобиан системы уравнений (4) относительно переменных г1, …, х".
Известна следующая теорема.
Теорема [см.: 6, с. 39]. Если имеет место равенство
Р (а (Р)… сг (Рп)) ^
0(2Х,…, 2п) ,
то система уравнений (4) при каждом х либо не имеет решения в пространстве С& quot-, либо все её решения в этом пространстве — неизолированные.
Однако, для некоммутативных систем уравнений (1) подобная альтернатива (решений нет — решений бесконечно много) не имеет место.
В качестве примера рассмотрим систему, состоящую из двух одинаковых уравнений:
I х222 Х^Х^ - 0^
Коммутативный образ этой системы имеет якобиан, тождественно равный нулю, тем не менее, исходная система некоммутативных уравнений имеет единственное решение.
В самом деле, записав уравнение в виде х1(г1 — х2) + х2(г2 — х1) = 0, получим, что первое слагаемое принадлежит левостороннему идеалу, порождённому х1, а второе — левостороннему идеалу, порождённому х2. Очевидно, что сумма этих слагаемых может быть равна нулю только в случае, когда равны нулю оба слагаемых: — х2 = 0, г2 — х1 = 0. Следовательно, исходная система уравнений имеет единственное решение = х2, г2 = х1.
Пример системы двух одинаковых уравнений
Х (2)(2)+ х2(2г)(2) = 0,
имеющей четыре решения, показывает, что такие системы могут иметь любое конечное число решений.
Таким образом, в случае, когда якобиан коммутативного образа системы тождественно равен нулю, исходная система некоммутативных уравнений может: не иметь решений, иметь конечное число решений, иметь бесконечно много решений.
Учитывая, что одно уравнение /= 0 равносильно системе из п уравнений / = … = /= 0, якобиан которой тождественно равен нулю, сформулируем
замечание о решениях таких систем применительно к одному некоммутативному уравнению P1(z, x) = 0: такие уравнения могут не иметь решений, иметь конечное, а также бесконечное число решений. В этом состоит принципиальное отличие от уравнений над полем комплексных чисел.
Причиной такого эффекта является то, что некоммутативное полиномиальное уравнение может быть равносильно системе таких уравнений, например, уравнение x1A1 + x-A2 = 0 равносильно, как мы видели, системе уравнений A1 = A2 = 0.
Список литературы
1. Сафонов К. В., Егорушкин О. И. О синтаксическом анализе и проблеме
B.М. Глушкова распознавания контекстно-свободных языков Хомского // Вестник Томского государственного университета. — 2006. — № 17. — С. 63−67.
2. Safonov K. V On conditions for the sum of a power series to be algebraic and rational // Mathematical Notes. — 1987. — № 3 (41). — P. 185−189.
3. Safonov K.V. On Power Series of Algebraic and Rational functions in Cn // Journal of Math. Analysis and Applications. — 2000. — V 243. — Р. 261−277.
4. Salomaa A., Soitolla M. Automata-Theoretics Aspects of Formal Power Series. — N. -Y.: Springer Verlag? 1978. — 171 p.
5. Семёнов А. Л. Алгоритмические проблемы для степенных рядов и контекстно-свободных грамматик // Доклады А Н СССР. — 1973. — Т. 212. -
C. 50−52.
6. Айзенберг Л. А., Южаков А. П. Интегральные представления и вычеты в многомерном комплексном анализе. — Новосибирск: Наука? 1979. — 367 с.
КРИТЕРИИ И СРЕДСТВА ОЦЕНКИ КАЧЕСТВА ФУНКЦИОНИРОВАНИЯ РАСПРЕДЕЛЕННОЙ СИСТЕМЫ ОБРАБОТКИ ИНФОРМАЦИИ
© Костюков А. А. *
Пензенский государственный университет, г. Пенза
В статье освещаются подходы к оценке качества распределенной вычислительной системы. Подробно описываются критерии и средства оценки, а также дается заключение об их применимости на практике, и степени отражения настоящего положения вещей.
Ключевые слова: распределённые вычислительные системы, моделирование нагрузки, кластерные системы, оценка распределенной вычислительной системы.
* Аспирант кафедры Математического обеспечения и применения ЭВМ.

ПоказатьСвернуть
Заполнить форму текущей работой