Что такое быстрый алгоритм для поиска численного решения системы N полиномиальных уравнений от 3 неизвестных переменных?

Я ищу быстрый алгоритм для решения системы N полиномиальных уравнений от 3 неизвестных переменных. То есть, учитывая 3 функции F0(x,y,z), F1(x,y,z)... FN(x,y,z), я хочу найти x, y, z такую, что F0(x,y,z) = F1(x,y,z) = ... = FN(x,y,z) = 0.

Я пытался найти решение в нескольких разных местах, но смог найти только очень сложные статьи по таким темам, как алгебраическая геометрия или криптография. Однако мне нужен простой / быстрый алгоритм, который возвращает быстрое численное решение. Есть такой алгоритм?


algorithm math equation language-agnostic polynomial-math
person MaiaVictor    schedule 11.01.2015    source источник
comment
Многовариантный Ньютон-Рафсон был бы моей первой попыткой.   -  person John Alexiou    schedule 11.01.2015
comment
Решение нескольких полиномиальных уравнений от нескольких переменных - сложная задача. Вы вряд ли найдете простой и быстрый алгоритм, который всегда работает.   -  person tmyklebu    schedule 11.01.2015
comment
Ах, спасибо, @tmyklebu. Это отличный ответ, если вы можете предоставить источник, кстати. Было бы полезно, потому что я бы просто перестал искать. Кстати, нет даже приблизительных решений?   -  person MaiaVictor    schedule 11.01.2015
comment
Кстати, если вы просто сложите свои функции, $ \ sum F (x, y, z) = 0 $ - это всего лишь один многочлен, для которого вам нужно найти решение. Теперь ваша система может быть недооценена или переопределена, поэтому это может повлиять на разрешимость вашей проблемы в дальнейшем.   -  person Marcus Müller    schedule 12.01.2015
comment
Кстати, есть ли границы по старшему показателю? Используют ли F одинаковые экспоненты или они частично или полностью не пересекаются?   -  person Marcus Müller    schedule 12.01.2015
comment
Да, я считаю, что наивысший показатель не может быть выше ^2. Причина в том, что уравнения создаются на пересечении трехмерной линии F(t) = a + b*t и параметрической поверхности G(u,v), созданной вручную художником и в основном использующей синусы, косинусы, sqrt и т. Д. Я читал, что вы можете исключить синусы / cos, однако (раздел Тригонометрические уравнения).   -  person MaiaVictor    schedule 12.01.2015

Ответы (2)


arrow_upward
3
arrow_downward

Решение нескольких полиномиальных уравнений от нескольких переменных - сложная задача. Выполнение этого за полиномиальное время в среднем случае является 17-й проблемой Смейла. Маловероятно, что вы найдет быстрый и простой алгоритм, который действительно работает.

Вы можете посмотреть «Идеалы, разновидности и алгоритмы» Кокса, Литтла и О'Ши, чтобы познакомиться с основами Грёбнера. Алгоритм Бухбергера находит базис Грёбнера для заданного полиномиального идеала. Вы можете найти все решения данной полиномиальной системы, используя базис Грёбнера для идеала, порожденного полиномами, хотя это решение имеет несколько неудобную форму.

Метод Ньютона - основной метод решения системы нескольких нелинейных уравнений с несколькими переменными. Наивно применяемый метод Ньютона является эвристическим; он не всегда найдет решение для системы, даже если решение существует. Однако если метод Ньютона сходится, тогда он сходится очень быстро. Таким образом, задача теории проблемы, поставленной Смейлом, состоит в том, чтобы найти доказуемо хорошее начальное предположение, с которого можно было бы начать метод Ньютона.

Белтран и Пардо добились значительного прогресса в решении 17-й проблемы Смейла, дающий алгоритм, который работает в среднем для систем с ограниченной степенью, использующих арифметику с действительными числами. С тех пор он был преобразован в алгоритм конечной точности Брикелем, Кукером, Пеной и Рощиной. Какими бы увлекательными они ни были, я не знаю ни о каких реализациях или попытках реализации этих идей - мы все еще очень, очень далеки от пригодного для использования кода для решения систем полиномиальные уравнения.

person tmyklebu    schedule 11.01.2015
comment
О, это отличный ответ, большое спасибо. Только одно, извините, мне действительно любопытно. Что мешает нам написать эти алгоритмы? - person MaiaVictor; 12.01.2015
comment
@Viclib: Для Белтрана и Пардо: У нас нет реальной арифметики бесконечной точности на компьютерах. Отчасти смысл другой статьи состоит в том, что она помогает обойти эту трудность в теории. Для результата Briquel et al: Технически ничего. Но люди на самом деле не реализуют такого рода теоретические алгоритмы, потому что они, как правило, гораздо менее эффективны на практике, чем показывает их асимптотическое время выполнения. - person tmyklebu; 12.01.2015

arrow_upward
1
arrow_downward

В своем последнем комментарии вы свели исходную проблему к гораздо более простой задаче - пересечению линии x(t)=a+b*t и поверхности G(x)=0. Просто вставив линию в уравнение поверхности, вы получите одномерную задачу F(t)=G(a+b*t)=0. Там вы можете использовать одномерный метод Ньютона или методы без производных, такие как метод Иллинойса (regula falsi с поворотом) или метод Бренца. По-прежнему остается глобальная проблема определения интервалов по смене знака. Здесь вы либо имеете какое-то представление о форме поверхности, либо вам нужно табулировать функцию. Продолжение гомотопии также может иметь значение, так как близлежащие линии очень часто имеют близкие корни.

person Lutz Lehmann    schedule 27.01.2015