Деление многопеременных многочленов.

[st4s1k]

Добрый день, пишу на языке программирования Java программу, осуществляющую все возможные операции над многочленами. По началу использовал однопеременные многочлены и для их решения применял метод Горнера: https://en.wikipedia.org/wiki/Horner%27s_method

Но мне захотелось написать универсальный класс Polynomial, который мог бы позволить решение любых многочленов (с любым количеством переменных).

Многочлен в программе имеет форму отсортированного связного списка, и каждая ячейка этого списка является одночленом, который состоит из двух полей:

1. Коэффициент (реальное число)
2. Бинарное дерево (ключ, значение), где ключ это переменная, а значение это степень в которую эта переменная возведена. Грубо говоря, тоже список, с уникальными элементами (переменными) и значением привязанным к этим элементам списка (степень).

Я уже реализовал такие операции как:

1. Сложение двух многочленов, или многочлена и одночлена
2. Вычитание (то же самое сложение, только с многочленом/одночленом помноженным на "-1")
3. Умножение многочлена на одночлен / многочлен.

Я дошёл до реализации деления многочлена на одночлен/многочлен и попал в тупик. В интернете я нашёл несколько примеров деления многочленов с двумя переменными, но они слишком простые и не учитывают всех возможных ситуаций.

Вот несколько ссылок, которые я нашёл:

• Одночлен:
  https://www.calc.ru/Odnochlen-Podobnyye ... hlena.html
• Деление однопеременных многочленов:
  https://en.wikipedia.org/wiki/Polynomial_long_division
  https://www.purplemath.com/modules/polydiv2.htm
  https://study.com/academy/lesson/how-to-divide-polynomials-with-long-division.html
• Деление многопеременных многочленов:
  https://www.mathsisfun.com/algebra/polynomials-division-long.html
  http://ko.mujica.org/math/algebra/multiplying-factoring-expression/dividing_polynomials/polynomial-division.html
  https://study.com/academy/lesson/division-of-polynomials-with-two-variables.html

Можете пожалуйста направить меня, где я мог бы найти информацию по необходимой мне проблеме: "Универсальй алгоритм осуществления деления одного многопеременного многочлена, на другой" ?

Заранее большое спасибо.

Пример:

$$f(a, b, c, d) = 4ac^3 + 3.14b^3cd+2abd+a+1$$

$$g(a, b, d) = 3a^2 + 2ad + b^2 + d$$

Чему будет равно:

$$h(a, b, c, d) = \frac {f(a, b, c, d)} {g(a, b, d)} = \frac {4ac^3 + 3.14b^3cd+2abd+a+1} {3a^2 + 2ad + b^2 + d} = ? $$

[Someone]

Мне, однако, очень интересно, что такое "решение многочлена", для которого применяется метод Горнера. Особенно в свете того, что

st4s1k в сообщении #1356774 писал(а):

пишу на языке программирования Java программу, осуществляющую все возможные операции над многочленами.

[st4s1k]

Someone, вот, можете посмотреть: https://github.com/st4s1k/Control-Theory-Toolset
Правда код не рабочий, т.к. я сейчас перехожу от массивов и однопеременных многочленов, к объектам, связным спискам и многопеременным многочленам. Но вы можете найти функцию деления в папке "src", файл Polynomial.java. Если честно, её писал не я, я вдохновился уже существующей реализацией другого человека. Но многое я изменил, так что кроме функции main() и функции деления многочленов div(), там от первоисточника ничего не осталось. Всё остальное реализовал сам. Учусь на 4 (последнем) курсе Технического Университета Молдовы, Факультет: Вычислительной Техники, Информатики и Микроэлектроники, специальность Автоматика, в основном изучаем теорию систем.
Оправдался...)

[Pphantom]

Тема перемещена из форума «Математика (общие вопросы)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);
- формулировку проблемы надо сделать более внятной, пока что неясно, что вы понимаете "решением многочленов".

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Pphantom]

Тема перемещена из форума «Карантин» в форум «Computer Science»

[Someone]

st4s1k в сообщении #1356786 писал(а):

Правда код не рабочий

Меня не код интересует, тем более — нерабочий. Меня интересует, почему я, профессиональный математик, не знаю, что такое "решение многочлена". Объясните, пожалуйста, что такое "решение многочлена".
Интересно также, что Вы подразумеваете под

st4s1k в сообщении #1356774 писал(а):

все возможные операции над многочленами.

[st4s1k]

Внимание!
Хотелось бы уточнить. Мне необходимо найти универсальный математический алгоритм для осуществления операции деления между двумя многопеременными многочленами.

Спасибо за винимание)

-- 25.11.2018, 20:27 --

Someone в сообщении #1356809 писал(а):

st4s1k в сообщении #1356786 писал(а):

Правда код не рабочий

Меня не код интересует, тем более — нерабочий. Меня интересует, почему я, профессиональный математик, не знаю, что такое "решение многочлена". Объясните, пожалуйста, что такое "решение многочлена".

Извините, возможно я неправильно выражаюсь, я отредактировал свой вопрос по требованию модератора.

Цитата:

Интересно также, что Вы подразумеваете под

st4s1k в сообщении #1356774 писал(а):

все возможные операции над многочленами.

А по поводу этого, я имею ввиду простые операции:

1. Сложение
2. Вычитание
3. Умножение
4. Деление

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

[Xaositect]

В отличие от случая с одной переменной, деление с остатков для многочленов от многих переменных однозначно не определено.

-- Вс ноя 25, 2018 19:44:13 --

Если есть гарантия, что первый многочлен делится на второй, то представьте многочлен как многочлен от одной переменной $x$, коэффициенты которого - многочлены от остальных переменных, и делите так же, как в случае одной переменной.

[Someone]

st4s1k в сообщении #1356810 писал(а):

Извините, возможно я неправильно выражаюсь, я отредактировал свой вопрос по требованию модератора.

Но модератор написал Вам то же самое, что и я:

Pphantom в сообщении #1356788 писал(а):

неясно, что вы понимаете "решением многочленов".

-- Вс ноя 25, 2018 22:04:08 --

st4s1k в сообщении #1356810 писал(а):

Под "решением многочлена" я подразумеваю замену одной, несколько, или всех переменных значениями, либо другими многочленами.

Эта "операция" называется "подстановкой" или "заменой". Употреблять слово "решение" где попало не следует, у него есть свои общепринятые значения.

[st4s1k]

st4s1k в сообщении #1356774 писал(а):

Но мне захотелось написать универсальный класс Polynomial, который мог бы позволить решение любых многочленов (с любым количеством переменных).

Упустил это

st4s1k в сообщении #1356774 писал(а):

Можете пожалуйста направить меня, где я мог бы найти информацию по необходимой мне проблеме: "Универсальй алгоритм осуществления деления одного многопеременного многочлена, на другой" ?

Думал проблема тут была

-- 25.11.2018, 21:37 --

И так. Нет явно установленного алгоритма деления многопеременных многочленов. Значит тему можно закрывать? Или как здесь принято.

[Someone]

(st4s1k)

st4s1k в сообщении #1356832 писал(а):

Значит тему можно закрывать? Или как здесь принято.

Здесь не принято закрывать тему без серьёзной причины. Обычно тему закрывают для того, чтобы принудительно прекратить обсуждение. Если же обсуждение прекратилось само собой, то тему не закрывают.

[dmd]

st4s1k в сообщении #1356774 писал(а):

Чему будет равно:

$$h(a, b, c, d) = \frac {f(a, b, c, d)} {g(a, b, d)} = \frac {4ac^3 + 3.14b^3cd+2abd+a+1} {3a^2 + 2ad + b^2 + d} = ? $$

Деление с остатком по каждой конкретной переменной из трёх $a,b,d$:

[st4s1k]

dmd, кстати, тоже думал о таких программных пакетах, как Wolfram Mathematica, MathWorks MATLAB, они же решают как-то эти задачи. Может есть итеративный способ их решения, не знаю, не нашёл. Я тоже задумался о факторизации; пока я слабо представляю себе что это такое, точнее представление есть, а вот знаний и навыков нет, надо будет больше углубиться в эту тему, может там есть ответ на мой вопрос.

[g______d]

По поводу теории нужно начать отсюда:

https://en.wikipedia.org/wiki/Gröbner_basis#Reduction

или с книги Кокс, О'Ши, Литтл "Идеалы, многообразия и алгоритмы".

[st4s1k]

g______d,
Благодарю!