2014 dxdy logo

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

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




На страницу Пред.  1, 2
 
 Re: Равенство алгебраических чисел
Сообщение10.02.2013, 10:41 
Xaositect в сообщении #682044 писал(а):
Нет. Следует из результатов Тарского о разрешимости.


Это здорово, а то мне уже начало казаться, что почва уходит из под ног.

И все же изначально меня интересовал другой вопрос: могут ли две записи алгебраических чисел в радикалах отвечать одному и тому же вещественному числу, но при этом быть неприводимы друг к другу путем конечной цепочки элементарных алгебраических преобразований. По поводу последних - я могу попыться перечислить возможные их виды, но мне почему-то казалось, что здесь и так довольно однозначно понятно о каких преобразованиях идет речь. Возможно я здесь чего-то не понимаю?

 
 
 
 Re: Равенство алгебраических чисел
Сообщение10.02.2013, 11:07 
aeg в сообщении #682052 писал(а):
могут ли две записи алгебраических чисел в радикалах отвечать одному и тому же вещественному числу, но при этом быть неприводимы друг к другу путем конечной цепочки элементарных алгебраических преобразований. По поводу последних - я могу попыться перечислить возможные их виды
Перечислите, иначе просто непонятно, о чём речь. Заодно объясните, что Вы понимаете под "алгебраическим числом в радикалах". Без строгих определений здесь (в вопросе о невозможности чего-либо) вообще нечего обсуждать.

 
 
 
 Re: Равенство алгебраических чисел
Сообщение10.02.2013, 11:42 
Запись алгебраического числа в радикалах опредляется грамматикой:

$A \to A \sigma A$

$A \to \sqrt [N] A$

$A \to N $

$A \to (A)$

$N \to 1 | 2 | 3 | ... $

$\sigma \to + | - | \cdot |  \div $

Описывать преобразования в подобном виде не хочется, хотя это можно было бы сделать, я все же попытаюсь на словах:
1. Вынесение общего множетеля за скобки, раскрытие скобок.
2. Уможение числителя и знаменателя на одно и то же выражение, сокращение числителя и знаменателя на общий множитель.
3. Внесение сомножителей под общий знак корня, разделение корней (степень корня предполагается одинаковой).
4. Приведение подобных слагаемых, то есть слагаемых у которых все сомножители, стоящие под знаком корня совпадают. Соответственно, разделение произведений на подобные слагаемые.
5. Возведение в степень подкоренного выражения с соотвествующим умножением степени корня. Соотвественно, сокращение степеней подкоренного выражения и корня.
6. Объединение вложенных корней в один корень, разделение корня на два вложенных.

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

Наверняка я чего-то упустил, но так или иначе мне кажется в общем понятно о каком наборе преобразований идет речь.

 
 
 
 Re: Равенство алгебраических чисел
Сообщение10.02.2013, 12:28 
Аватара пользователя
aeg в сообщении #682070 писал(а):
Соотвественно, сокращение степеней подкоренного выражения и корня
Стоп.
Тут вылезают модули. Соответственно, в грамматику выражения придется добавить $A\to |A|$ и в преобразования - какой-то способ разобраться с модулем.

 
 
 
 Re: Равенство алгебраических чисел
Сообщение10.02.2013, 12:34 
aeg в сообщении #682070 писал(а):
Описывать преобразования в подобном виде не хочется
Это понятно, но задачу нужно чётко сформулировать (как мне, неспециалисту в матлогике, кажется). Для практических приложений в компьютерной алгебре важен алгоритм проверки равенства $\alpha=0$, где $\alpha$ --- "алгебраическое число в радикалах". Более общая задача --- это упрощения вложенных радикальных выражений. В конкретных системах компьютерной алгебры она как-то решена, но до идеала далеко.

 
 
 
 Re: Равенство алгебраических чисел
Сообщение10.02.2013, 12:54 
Xaositect в сообщении #682085 писал(а):
Стоп.
Тут вылезают модули


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

-- 10.02.2013, 16:00 --

nnosipov в сообщении #682086 писал(а):
Для практических приложений в компьютерной алгебре важен алгоритм проверки равенства


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

 
 
 
 Re: Равенство алгебраических чисел
Сообщение10.02.2013, 13:17 
Ну, какой-то алгоритм предложить можно. Если $\alpha$ --- "алгебраическое число в радикалах", то $P(\alpha)=0$ для некоторого многочлена $P(x)$ с рациональными коэффициентами. Находим такой многочлен, локализуем его корни, приближённо вычисляем $\alpha$ и сравниваем с найденными корнями. Другое дело --- найти и реализовать алгоритм, который бы всё это делал побыстрее.

 
 
 
 Re: Равенство алгебраических чисел
Сообщение10.02.2013, 13:41 
nnosipov в сообщении #682101 писал(а):
Ну, какой-то алгоритм предложить можно. Если --- "алгебраическое число в радикалах", то для некоторого многочлена с рациональными коэффициентами. Находим такой многочлен, локализуем его корни, приближённо вычисляем и сравниваем с найденными корнями. Другое дело --- найти и реализовать алгоритм, который бы всё это делал побыстрее.


Ну если нас интересует примерное решение, то почему бы сразу не вычислять само выражение? Если только из соображений минимизации погрешности. Другое дело, что хотелось бы иметь все же точное решение. Ведь совершенно нежелательна ситуация, когда в результате упрощения два слагаемых взаимно уничтожатся лишь потому, что они почти равны по модулю.

Я впрочем уже не рассчитваю, что смогу реализовать такое сравнение, но хотелось бы все же понять, возможно ли это в принципе.

 
 
 
 Re: Равенство алгебраических чисел
Сообщение10.02.2013, 13:49 
Аватара пользователя
aeg в сообщении #682092 писал(а):
Ведь если для двух "существенно различных" выражений алгебраических чисел может иметь место равенство их значений, то совершенно непонятно как такую задачу решать.

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

 
 
 
 Re: Равенство алгебраических чисел
Сообщение10.02.2013, 14:01 
aeg в сообщении #682103 писал(а):
Другое дело, что хотелось бы иметь все же точное решение.
Я имел в виду алгоритм, который именно доказывает равенство $\alpha=0$, если оно имеет место. Здесь всё точно.

 
 
 
 Re: Равенство алгебраических чисел
Сообщение11.02.2013, 09:22 
nikvic в сообщении #682104 писал(а):
НОД двух многочленов ищется известно как.

Если делать по "известно как", то возникает проблема с ростом коэффициентов. Там экспоненциальный рост количества цифр.

 
 
 [ Сообщений: 26 ]  На страницу Пред.  1, 2


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group