Оглавление
- 1 Результирующий
- 1.1 Определение результирующей
- 1.2 Обозначение и степени
- 1.3 Определение через матрицу Сильвестра
- 1.4 Свойства результирующей
- 1.5 Инвариантность с помощью кольцевых гомоморфизмов
- 1.6 Вычисление результирующей многочленов
- 1.7 Инвариантность при изменении переменной
- 1.8 Инвариантность при изменении многочленов
- 1.9 Общие свойства результирующей
- 1.10 Вычисление результирующей
- 1.11 Псевдорезультативные последовательности
- 1.12 Использование быстрого умножения
- 1.13 Применение к полиномиальным системам
- 1.14 Случай двух уравнений с двумя неизвестными
- 1.15 Общий случай
- 1.16 Другие области применения
- 1.17 Однородная результирующая
- 1.18 Результирующая Маколея
- 1.19 Результирующая общих однородных многочленов
- 1.20 Результирующая многочленов над полем
- 1.21 Вычислимость
- 1.22 U-результирующая
- 1.23 Определение U-результирующей
- 1.24 Свойства U-результирующей
- 1.25 Расширение на большее количество полиномов
- 1.26 Определение матрицы Маколея
- 1.27 Вычисление U-результирующей
- 1.28 Временная сложность
- 1.29 Практическое применение
- 1.30 Полный текст статьи:
- 2 Результат – Arc.Ask3.Ru
Результирующий
-
Определение результирующей
- Результирующая двух многочленов — это полиномиальное выражение их коэффициентов, равное нулю, если многочлены имеют общий корень или общий множитель.
- В старых текстах результирующая также называется устраняющей.
- Результирующая широко используется в теории чисел и компьютерной алгебре.
-
Обозначение и степени
- Результирующая обозначается res(A, B) или Res(A, B).
- В приложениях результирующая зависит от нескольких неопределенных величин, что указывается нижним индексом.
- Степени многочленов используются при определении результирующей.
-
Определение через матрицу Сильвестра
- Результирующая определяется как определитель матрицы Сильвестра.
- Матрица Сильвестра имеет e столбцов ai и d столбцов bj.
- Если коэффициенты многочленов принадлежат целочисленной области, результирующая равна произведению корней многочленов.
-
Свойства результирующей
- Результирующая является уникальной функцией коэффициентов двух многочленов.
- Если R является подкольцом другого кольца, результирующая одинакова для обоих колец.
- Если d = 0 или e = 0, результирующая равна произведению ведущих коэффициентов.
- Результирующая равна нулю тогда и только тогда, когда многочлены имеют общий делитель или корень.
-
Инвариантность с помощью кольцевых гомоморфизмов
- Результирующая инвариантна при кольцевых гомоморфизмах, сохраняющих степени многочленов.
- Если степени гомоморфизмов не совпадают, результирующая может быть равна нулю.
- Если ведущий коэффициент одного из многочленов равен a0, результирующая умножается на φ(a0)e-f.
- Если ведущий коэффициент другого многочлена равен b0, результирующая умножается на (-1)e(d-f)φ(b0)d-f.
-
Вычисление результирующей многочленов
- Результирующая многочленов с целыми коэффициентами быстрее вычисляется по модулю простых чисел.
- Результирующая специализации двух многочленов является специализацией результирующего.
-
Инвариантность при изменении переменной
- Результирующая не меняется при линейных и проективных изменениях переменной.
- Результирующая равна нулю при изменении переменной.
-
Инвариантность при изменении многочленов
- Результирующая зависит от степеней многочленов и констант.
- Результирующая инвариантна при изменении многочленов.
-
Общие свойства результирующей
- Результирующая является абсолютно неприводимым многочленом.
- Результирующая однородна по разным степеням переменных.
- Результирующая устраняет общие нули многочленов.
-
Вычисление результирующей
- Теоретически результирующую можно вычислить через произведение разностей корней, но это неэффективно.
- Результирующая может быть вычислена через определитель матрицы Сильвестра, но это требует много арифметических операций.
- Евклидов алгоритм для многочленов позволяет вычислить результирующую за O(de) арифметических операций.
-
Псевдорезультативные последовательности
- Введены для избежания дробей и вычислений коэффициентов с помощью GCD.
- Результирующая восстанавливается с помощью китайской теоремы об остатках.
-
Использование быстрого умножения
- Быстрое умножение целых чисел и многочленов позволяет использовать алгоритмы с лучшей временной сложностью.
-
Применение к полиномиальным системам
- Результирующие уравнения используются для решения систем полиномиальных уравнений.
- Они позволяют решать системы из двух уравнений с двумя неизвестными и общие системы.
-
Случай двух уравнений с двумя неизвестными
- Результирующая R = resy(P, Q) является многочленом от x.
- Значение α из x является корнем из R, если существует β, что P(α, β) = Q(α, β) = 0 или deg(P(α, y)) < d и deg(Q(α, y)) < e.
- Решения системы получаются путем вычисления корней из R и общего корня из P(α, y), Q(α, y) и resx(P, Q).
-
Общий случай
- Результирующие значения могут быть применены к общей полиномиальной системе уравнений, но это приводит к множеству ложных решений.
- Метод, введенный в конце 19-го века, использует новые неопределенности для устранения одного неизвестного.
- Процесс повторяется до получения одномерных многочленов.
-
Другие области применения
- Теория чисел: дискриминант многочлена равен resx(f(x), f'(x)).
- Алгебраическая геометрия: результирующая позволяет вычислить пересечение двух плоских алгебраических кривых.
- Символическая интеграция: метод Лазарда-Риобу-Трагера минимизирует число алгебраических чисел в первообразной.
- Компьютерная алгебра: результирующая является фундаментальным инструментом в компьютерной алгебре.
-
Однородная результирующая
- Однородная результирующая P и Q равна результирующей P(x, 1) и Q(x, 1) при рассмотрении их как многочленов степеней p и q.
- Результирующая равна нулю тогда и только тогда, когда P и Q имеют ненулевой общий нуль над алгебраически замкнутым полем.
- Результирующая инвариантна при проективном изменении переменных.
-
Результирующая Маколея
- Результирующая Маколея обобщает однородную результирующую на n однородных многочленов.
- Результирующая Маколея равна нулю тогда и только тогда, когда многочлены имеют общий ненулевой нуль.
- Результирующая может быть определена с помощью определителей и работает при кольцевых гомоморфизмах.
-
Результирующая общих однородных многочленов
- Однородный многочлен степени d от n переменных может иметь до (n + d – 1)n – 1 коэффициентов.
- Результирующая определяется с помощью матрицы Маколея, которая является матрицей над мономиальным базисом.
- Общий результирующий показатель Маколея является неприводимым многочленом и однороден по степени B/d в коэффициентах P.
-
Результирующая многочленов над полем
- Результирующая многочленов над полем k равна нулю тогда и только тогда, когда P имеют ненулевой общий нуль в алгебраически замкнутом расширении k.
- Результирующая отлична от нуля, если ⟨x1, …, xn⟩D ⊆ ⟨P1, …, Pn⟩, где D = d1 + … + dn – n + 1.
-
Вычислимость
- Вычисление результирующей может быть сведено к вычислению определителей и полиномиальных наибольших общих делителей.
- Общий результирующий результат представляет собой многочлен очень высокой степени, что делает его вычислимость практически невозможной.
- Вычисление результирующей имеет смысл только для многочленов с коэффициентами в поле или многочленами от нескольких неопределенных величин.
-
U-результирующая
- U-результирующая используется для решения систем полиномиальных уравнений.
- U-результирующая является результирующей n многочленов P1, …, Pn-1, Pn, где Pn = u1x1 + … + unxn.
-
Определение U-результирующей
- U-результирующая — это однородная линейная форма с новыми неопределенными u1, …, un.
- Обозначение u1 или U1 для этих коэффициентов традиционно и является источником термина U-результирующий.
-
Свойства U-результирующей
- U-результирующая равна нулю тогда и только тогда, когда общие нули P1, …, Pn-1 образуют проективное алгебраическое множество положительной размерности.
- Если U-результирующая не равна нулю, её степень равна границе Безу d1 ⋯ dn-1.
- U-результирующая разлагается на произведение линейных форм по алгебраически замкнутому расширению k.
- Коэффициенты линейных множителей являются однородными координатами общих нулей P1, …, Pn-1.
-
Расширение на большее количество полиномов
- Дэниел Лазард расширил понятие U-результирующей на случай, когда число многочленов может отличаться от n-1.
- Вычисление выполняется с помощью процедуры исключения по Гауссу и символьного определителя.
-
Определение матрицы Маколея
- Матрица Маколея определяется как матрица над базисом одночленов в x1, …, xn.
- Линейная карта (Q1, …, Qk+1) ↦ P1Q1 + … + Pk+1Qk+1, где Qi проходит по линейному пространству, состоящему из нуля и однородных многочленов степени D-di.
-
Вычисление U-результирующей
- Уменьшая матрицу Маколея с помощью исключения Гаусса, получаем квадратную матрицу линейных форм в u1, …, un.
- Определителем этой матрицы является U-результирующая.
- U-результирующая равна нулю тогда и только тогда, когда P1, …, Pk имеют бесконечно много общих проективных нулей.
- Когда U-результирующая не равна нулю, она преобразуется в линейные множители по любому алгебраически замкнутому расширению k.
-
Временная сложность
- Количество строк матрицы Маколея меньше, чем (ed)n, где e ~ 2,7182 и d — среднее арифметическое степеней Pi.
- Все решения системы полиномиальных уравнений с конечным числом проективных нулей могут быть определены во времени dO(n).
- Эта оценка почти оптимальна, так как при равных входных значениях временная сложность полиномиальна по отношению к ожидаемому числу решений.
-
Практическое применение
- Вычисление может быть практически осуществимым при небольших значениях n, k и d.