2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Деление многопеременных многочленов.
Сообщение25.11.2018, 18:59 
Аватара пользователя


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

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

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

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

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

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

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

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

Пример:
$$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} = ? $$

 Профиль  
                  
 
 Re: Деление многопеременных многочленов.
Сообщение25.11.2018, 19:26 
Заслуженный участник
Аватара пользователя


23/07/05
16824
Москва
Мне, однако, очень интересно, что такое "решение многочлена", для которого применяется метод Горнера. Особенно в свете того, что
st4s1k в сообщении #1356774 писал(а):
пишу на языке программирования Java программу, осуществляющую все возможные операции над многочленами.

 Профиль  
                  
 
 Re: Деление многопеременных многочленов.
Сообщение25.11.2018, 19:52 
Аватара пользователя


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

 Профиль  
                  
 
 Posted automatically
Сообщение25.11.2018, 19:54 
Супермодератор
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Posted automatically
Сообщение25.11.2018, 20:57 
Супермодератор
Аватара пользователя


09/05/12
18266
Кронштадт
 i  Тема перемещена из форума «Карантин» в форум «Computer Science»

 Профиль  
                  
 
 Re: Деление многопеременных многочленов.
Сообщение25.11.2018, 21:16 
Заслуженный участник
Аватара пользователя


23/07/05
16824
Москва
st4s1k в сообщении #1356786 писал(а):
Правда код не рабочий
Меня не код интересует, тем более — нерабочий. Меня интересует, почему я, профессиональный математик, не знаю, что такое "решение многочлена". Объясните, пожалуйста, что такое "решение многочлена".
Интересно также, что Вы подразумеваете под
st4s1k в сообщении #1356774 писал(а):
все возможные операции над многочленами.

 Профиль  
                  
 
 Re: Деление многопеременных многочленов.
Сообщение25.11.2018, 21:18 
Аватара пользователя


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

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

-- 25.11.2018, 20:27 --

Someone в сообщении #1356809 писал(а):
st4s1k в сообщении #1356786 писал(а):
Правда код не рабочий
Меня не код интересует, тем более — нерабочий. Меня интересует, почему я, профессиональный математик, не знаю, что такое "решение многочлена". Объясните, пожалуйста, что такое "решение многочлена".

Извините, возможно я неправильно выражаюсь, я отредактировал свой вопрос по требованию модератора.
Цитата:
Интересно также, что Вы подразумеваете под
st4s1k в сообщении #1356774 писал(а):
все возможные операции над многочленами.

А по поводу этого, я имею ввиду простые операции:
  1. Сложение
  2. Вычитание
  3. Умножение
  4. Деление

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

 Профиль  
                  
 
 Re: Деление многопеременных многочленов.
Сообщение25.11.2018, 21:32 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Деление многопеременных многочленов.
Сообщение25.11.2018, 21:58 
Заслуженный участник
Аватара пользователя


23/07/05
16824
Москва
st4s1k в сообщении #1356810 писал(а):
Извините, возможно я неправильно выражаюсь, я отредактировал свой вопрос по требованию модератора.
Но модератор написал Вам то же самое, что и я:
Pphantom в сообщении #1356788 писал(а):
неясно, что вы понимаете "решением многочленов".


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

st4s1k в сообщении #1356810 писал(а):
Под "решением многочлена" я подразумеваю замену одной, несколько, или всех переменных значениями, либо другими многочленами.
Эта "операция" называется "подстановкой" или "заменой". Употреблять слово "решение" где попало не следует, у него есть свои общепринятые значения.

 Профиль  
                  
 
 Re: Деление многопеременных многочленов.
Сообщение25.11.2018, 22:26 
Аватара пользователя


18/09/14
60
st4s1k в сообщении #1356774 писал(а):
Но мне захотелось написать универсальный класс Polynomial, который мог бы позволить решение любых многочленов (с любым количеством переменных).

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

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

-- 25.11.2018, 21:37 --

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

 Профиль  
                  
 
 Re: Деление многопеременных многочленов.
Сообщение25.11.2018, 22:45 
Заслуженный участник
Аватара пользователя


23/07/05
16824
Москва

(st4s1k)

st4s1k в сообщении #1356832 писал(а):
Значит тему можно закрывать? Или как здесь принято.
Здесь не принято закрывать тему без серьёзной причины. Обычно тему закрывают для того, чтобы принудительно прекратить обсуждение. Если же обсуждение прекратилось само собой, то тему не закрывают.

 Профиль  
                  
 
 Re: Деление многопеременных многочленов.
Сообщение26.11.2018, 22:35 


16/08/05
961
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$:
Изображение

 Профиль  
                  
 
 Re: Деление многопеременных многочленов.
Сообщение27.11.2018, 01:54 
Аватара пользователя


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

 Профиль  
                  
 
 Re: Деление многопеременных многочленов.
Сообщение27.11.2018, 02:55 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Деление многопеременных многочленов.
Сообщение27.11.2018, 07:35 
Аватара пользователя


18/09/14
60
g______d,
Благодарю!

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 26 ]  На страницу 1, 2  След.

Модераторы: Toucan, maxal, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group