Метод характеристического множества Ву
Алгоритм решения систем полиномиальных уравнений

Метод Вэньцзюня Ву — это алгоритм решения многомерных полиномиальных уравнений, представленный в конце 1970-х годов китайским математиком Вэнь-Цун Ву . Этот метод основан на математической концепции характеристического множества , представленной в конце 1940-х годов Дж. Ф. Риттом . Он полностью независим от метода базиса Грёбнера , представленного Бруно Бухбергером (1965), даже если базисы Грёбнера могут использоваться для вычисления характеристических множеств. [1] [2]

Метод У является мощным для доказательства механических теорем в элементарной геометрии и обеспечивает полный процесс решения для определенных классов задач. Он использовался в исследованиях в его лаборатории (KLMM, Ключевая лаборатория математической механизации в Китайской академии наук) и по всему миру. Основные направления исследований метода У касаются систем полиномиальных уравнений положительной размерности и дифференциальной алгебры , где результаты Ритта стали эффективными. [3] [4] Метод У применялся в различных научных областях, таких как биология, компьютерное зрение , кинематика роботов и особенно автоматические доказательства в геометрии. [5]

Неформальное описание

Метод Ву использует деление полиномов для решения задач вида:

∀ х , у , з , … я ( х , у , з , … ) ⟹ ф ( х , у , з , … ) {\displaystyle \forall x,y,z,\dots I(x,y,z,\dots )\implies f(x,y,z,\dots )\,}

где f — полиномиальное уравнение , а I — конъюнкция полиномиальных уравнений . Алгоритм является полным для таких задач в комплексной области .

Основная идея алгоритма заключается в том, что вы можете разделить один многочлен на другой, чтобы получить остаток. Повторное деление приводит либо к исчезновению остатка (в этом случае утверждение I подразумевает f истинно), либо к остатку, который невозможно сократить (в этом случае утверждение ложно).

Более конкретно, для идеала I в кольце k [ x 1 , ...,  x n ] над полем k , характеристическое множество (Ритта) C для I состоит из множества многочленов от I , которое имеет треугольную форму: многочлены от C имеют различные основные переменные (см. формальное определение ниже). При наличии характеристического множества C для I , можно решить, равен ли многочлен f нулю по модулю I . То есть тест принадлежности проверяем для I , при условии характеристического множества I .

Характеристический набор Ритта

Характеристическое множество Ритта — это конечное множество полиномов в треугольной форме идеала. Это треугольное множество удовлетворяет определенному минимальному условию относительно порядка Ритта и сохраняет многие интересные геометрические свойства идеала. Однако оно может не быть его системой образующих.

Обозначение

Пусть R — многомерное кольцо многочленов k [ x 1 , ..., x n ] над полем k . Переменные упорядочены линейно в соответствии с их нижним индексом: x 1 < ... < x n . Для непостоянного многочлена p в R наибольшая переменная, эффективно представленная в p , называемая главной переменной или классом , играет особую роль: p можно естественным образом рассматривать как одномерный многочлен по своей главной переменной x k с коэффициентами в k [ x 1 , ..., x k −1 ]. Степень p как одномерного многочлена по своей главной переменной также называется его главной степенью.

Треугольный набор

Множество T непостоянных многочленов называется треугольным множеством , если все многочлены в T имеют различные главные переменные. Это естественным образом обобщает треугольные системы линейных уравнений .

заказ Ритт

Для двух непостоянных полиномов p и q мы говорим, что p меньше q относительно порядка Ритта и записываем это как p  < r  q , если выполняется одно из следующих утверждений:

(1) основная переменная p меньше основной переменной q , то есть mvar( p ) < mvar( q ),
(2) p и q имеют одну и ту же основную переменную, и основная степень p меньше основной степени q  , то есть mvar( p ) = mvar( q ) и mdeg( p ) < mdeg( q ).

Таким образом, ( k [ x 1 , ...,  x n ],< r ) образует вполне частичный порядок . Однако порядок Ритта не является полным порядком : существуют полиномы p и q такие, что ни p  < r  q , ни p  > r  q . В этом случае мы говорим, что p и q несравнимы. Порядок Ритта сравнивает ранг p и q . Ранг, обозначаемый rank( p ), непостоянного полинома p определяется как степень его основной переменной: mvar( p ) mdeg( p ) и ранги сравниваются путем сравнения сначала переменных, а затем, в случае равенства переменных, степеней.

Упорядочение Ритта на треугольных множествах

Важнейшим обобщением порядка Ритта является сравнение треугольных множеств. Пусть T  = {  t 1 , ...,  t u } и S  = ​​{  s 1 , ...,  s v } — два треугольных множества, такие, что многочлены в T и S сортируются по возрастающей в соответствии с их основными переменными. Мы говорим, что T меньше S относительно порядка Ритта, если выполняется одно из следующих утверждений

  1. существует k  ≤ min( u ,  v ) такое, что rank( t i ) = rank( s i ) для 1 ≤  i  <  k и t k  < r  s k ,
  2. u  >  v и ранг( t i ) = ранг( s i ) для 1 ≤  i  ≤  v .

Кроме того, существуют несравнимые треугольные множества относительно порядка Ритта.

Характеристический набор Ритта

Пусть I — ненулевой идеал k[x 1 , ..., x n ]. Подмножество T множества I является характеристическим множеством Ритта для I, если выполняется одно из следующих условий:

  1. T состоит из одной ненулевой константы k,
  2. T — треугольное множество, и T минимально относительно порядка Ритта в множестве всех треугольных множеств, содержащихся в I.

Полиномиальный идеал может обладать (бесконечно) многими характеристическими наборами, поскольку упорядочение Ритта является частичным порядком.

Характеристический набор Ву

Процесс Ритта–Ву, впервые разработанный Риттом и впоследствии модифицированный Ву, вычисляет не характеристику Ритта, а расширенную характеристику, называемую набором характеристик Ву или восходящей цепью.

Непустое подмножество T идеала ⟨F⟩ , порожденное F, является характеристическим множеством Ву для F, если выполняется одно из следующих условий:

  1. T = {a}, где a — ненулевая константа,
  2. T — треугольное множество, и существует подмножество G множества ⟨F⟩ , такое что ⟨F⟩ = ⟨G⟩ и каждый многочлен из G псевдоприводим к нулю относительно T.

Характеристическое множество Ву определяется множеством F полиномов, а не идеалом ⟨F⟩ , порожденным F. Также можно показать, что характеристическое множество Ритта T для ⟨F⟩ является характеристическим множеством Ву для F. Характеристические множества Ву могут быть вычислены с помощью алгоритма Ву CHRST-REM, который требует только вычисления псевдоостатка и не требует факторизации.

Метод характеристического множества Ву имеет экспоненциальную сложность; были введены улучшения в вычислительной эффективности с помощью слабых цепей, регулярных цепей , насыщенных цепей [6]

Разложение алгебраических многообразий

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

В ( Ф ) = Вт ( Т 1 ) ∪ ⋯ ∪ Вт ( Т е ) , {\displaystyle V(F)=W(T_{1})\cup \cdots \cup W(T_{e}),}

где W ( T i ) — разность V ( T i ) и V ( h i ), здесь h i — произведение начальных чисел многочленов относительно T i .

Смотрите также

Ссылки

  1. ^ Corrochano, Eduardo Bayro; Sobczyk, Garret, ред. (2001). Геометрическая алгебра с приложениями в науке и технике . Бостон, Массачусетс: Birkhäuser. стр. 110. ISBN 9780817641993.
  2. ^ П. Обри, Д. Лазар, М. Морено Маза (1999). О теориях треугольных множеств. Журнал символических вычислений, 28(1–2):105–124
  3. ^ Хьюберт, Э. Факторизация свободных алгоритмов разложения в дифференциальной алгебре. Журнал символических вычислений, (май 2000 г.): 641–662.
  4. ^ Пакет Maple (программное обеспечение) diffalg .
  5. ^ Чжоу, Шан-Цзин; Гао, Сяошань; Чжан, Цзин Чжун. Машинные доказательства в геометрии . World Scientific, 1994.
  6. ^ Chou SC, Gao XS; Алгоритм разложения Ритта–У и доказательство теорем геометрии. Proc of CADE, 10 LNCS, #449, Берлин, Springer Verlag, 1990 207–220.
  • P. Aubry, M. Moreno Maza (1999) Треугольные множества для решения полиномиальных систем: сравнительная реализация четырех методов. J. Symb. Comput. 28(1–2): 125–154
  • Дэвид А. Кокс, Джон Б. Литтл, Донал О'Ши. Идеалы, многообразия и алгоритмы. 2007.
  • Хуа-Шань, Лю (24 августа 2005 г.). "WuRittSolva: Реализация метода характеристических наборов Ву-Ритта". Архив библиотеки Wolfram . Wolfram . Получено 17 ноября 2012 г. .
  • Хек, Андре (2003). Введение в Maple (3-е изд.). Нью-Йорк: Springer. С. 105, 508. ISBN 9780387002309.
  • Ритт, Дж. (1966). Дифференциальная алгебра. Нью-Йорк, Dover Publications.
  • Дунмин Ван (1998). Методы устранения. Шпрингер-Верлаг, Вена, Шпрингер-Верлаг
  • Дунмин Ван (2004). Практика исключения, Imperial College Press, Лондон ISBN 1-86094-438-8 
  • Wu, WT (1984). Основные принципы доказательства механических теорем в элементарных геометриях. J. Syst. Sci. Math. Sci., 4, 207–35
  • Wu, WT (1987). Теорема о нулевой структуре для решения полиномиальных уравнений. MM Research Preprints, 1, 2–12
  • Сяошань, Гао; Чуньмин, Юань; Гуйлинь, Чжан (2009). «Метод характеристических множеств Ритта-У для обычных разностных полиномиальных систем с произвольным порядком». Acta Mathematica Scientia . 29 (4): 1063– 1080. CiteSeerX  10.1.1.556.9549 . doi :10.1016/S0252-9602(09)60086-2.
  • пакет wsolve Maple
  • Метод набора характеристик
Retrieved from "https://en.wikipedia.org/w/index.php?title=Wu%27s_method_of_characteristic_set&oldid=1206585633"