Результат – Arc.Ask3.Ru

Оглавление1 Результирующий1.1 Определение результирующей1.2 Обозначение и степени1.3 Определение через матрицу Сильвестра1.4 Свойства результирующей1.5 Инвариантность с помощью кольцевых гомоморфизмов1.6 Вычисление результирующей […]

Оглавление

Результирующий

  • Определение результирующей

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

    • Результирующая обозначается 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.  

Полный текст статьи:

Результат – Arc.Ask3.Ru

Оставьте комментарий

Прокрутить вверх