Теория исключений и решение систем многочленов от нескольких неизвестных

Автор темы hazzo 
ОбъявленияПоследний пост
ОбъявлениеСтуденческий конкурс в области программирования AR Start16.04.2012 10:07
ОбъявлениеЗаседание Московского математического общества 24 апреля 2012 года23.04.2012 01:32
ОбъявлениеНабор в Школу анализа данных Яндекса, отд. Биоинформатики18.05.2012 10:47
Форумы Список тем Новая тема
30.08.2010 21:47
boris_notkin
Проведите эксперимент...
Если Вы реализуете предложенный алгоритм, то убедитесь, что никаких проблем, связанных с нулями и единицами он не испытывает (хотя я, откровенно говоря, так и не понял, что Вы имели в виду). Единственная проблема, которую здесь можно действительно обсуждать, - это проблема локальных минимумов (при различных начальных условиях алгоритм может сходиться к различным значениям функционала). Но это фундаментальная проблема всех градиентных методов и решать ее нужно отдельно.
Ответить Цитировать
31.08.2010 04:49
hazzo
Эффективность под сомнением
Эксперимент не доказательство. Давайте по рассуждаем.



Редактировалось 6 раз(а). Последний 04.09.2010 16:38.
Ответить Цитировать
31.08.2010 12:22
boris_notkin
Эээээ... баста карапузики...
Вы демонстрируете упорство, что в большинстве случаев - хорошо, но при этом слабо понимаете свою задачу, a вот это плохо, т.к. пишете глупости, в которых, к тому же, умудряетесь допускать ошибки. Вы просили помощь - Вы ее получили. Уговаривать ее принять, параллельно объясняя как выразить переменную из выражения и доказывая, что умножение любого числа на 0 дает 0, я не намерен. Если возникнут не "теоретические", а прикладные вопросы, связанные с реализацией алгоритма, и Вы меня правильно попросите о помощи, не обращая свое непонимание алгоритма в утверждение о его неработоспособности, то, возможно, помогу.
Ответить Цитировать
31.08.2010 13:16
hazzo
...
boris_notkin, Прошу прощение если сказал или сделал что-то не то.
Я не говорил, что алгоритм не работает. Я сомневался в его эффективности для моей задачи. Почему, я объяснил.
Какие например глупости я написал?
Я свою задачу очень хорошо понимаю. Скорее всего Вы не понимаете, что я хочу. Я просто не вижу, что тот алгоритм который Вы описали действительно эффективен для моей задачи. Поэтому просил объяснение. У меня есть алгебраическое (аналитическое) решение данной задачи, но из-за таких же ситуаций (то есть появление разветвления) я от него отказался.
Я не разу не назвал Вас глупым. Хотя не однократно допускали ошибки.
Скажите пожалуйста какая вычислительная сложность этого алгоритма для данной задачи?
Вычислительная сложность не выражается в секундах или часах. Она выражается с использованием O нотации и для общего случая.
Если хотите помочь, то пожалуйста ответе?
Я очень признателен Вам, что пытаетесь мне помочь. Но, я не готов принять что-либо на веру.
Ещё раз простите и спасибо за помощь.

Я не спорю, а хочу Вас понять и эффективно решить свою задачу. Или понять, что эффективного решения нет.



Редактировалось 1 раз(а). Последний 05.09.2010 18:36.
Ответить Цитировать
31.08.2010 15:28
boris_notkin
О чем рассуждать?
Цитата
hazzo
Эксперимент не доказательство. Давайте по рассуждаем.

Пусть $ x_2=a_{1,2}+1, x_3=a_{1,3}+1, ... , x_n=a_{1,n}+1$

Зачем это "пусть"? Для наукообразия? В дальнейших рассуждениях от него никакого толка нет.


Цитата
hazzo
Эксперимент не доказательство. Давайте по рассуждаем.
...
Если $\sum_{i=1}^{m} (x_2-a_{i,2})^{2}(x_3-a_{i,3})^{2}...(x_n-a_{i,n})^{2}=0$
А какое значение будет иметь целевой функционал при этом "если"??? А что при таком значении функционала нужно сделать?

Цитата
hazzo
Эксперимент не доказательство. Давайте по рассуждаем.
...
Иначе $x_1=\sum_{i=1}^{m} a_{i,1}$
Здесь просто ошибка.

Цитата
hazzo
Эксперимент не доказательство. Давайте по рассуждаем.
...
У нас два случая для $x_1$. Значит нужно выполнить две проверки.
Подставляя в уравнении для $x_2, x_1=b$, где b не равно $\sum_{i=1}^{m} a_{i,1}$ получим одно уравнение.
Подставляя же в уравнении для $x_2, x_1=\sum_{i=1}^{m} a_{i,1}$ получим другое уравнение.
Если бы Вы реально подставили, а не взяли бы это утверждение с потолка, то заметили бы, что при формальном отличии эти уравнения (в описанных условиях) имеют одинаковые решения, а поэтому никакой вилки здесь не возникает.
Ответить Цитировать
31.08.2010 15:54
boris_notkin
Как собаке пятая нога...
Цитата
hazzo
У меня есть алгебраическое (аналитическое) решение данной задачи, но из-за таких же ситуаций (то есть появление разветвления) я от него отказался. Такое решение описан в книге Е.С. Ляпина "Высшая алгебра" 2009г.
Я не разу не назвал Вас глупым. Хотя не однократно допускали ошибки.
Скажите пожалуйста какая вычислительная сложность этого алгоритма для данной задачи?
Вычислительная сложность не выражается в секундах или часах. Она выражается с использованием O нотации и для общего случая.
Если у Вас есть аналитическое решение этой задачи, то можно предположить, что число неизвестных в ней невелико. А Вы должны знать, что при малых n оценка вычислительной сложности далеко не всегда отражает действительную ситуацию, а поэтому критериям для принятия решения она являться не может.
Ответить Цитировать
31.08.2010 17:44
hazzo
Спасибо boris_notkin
В моих рассуждениях нет ошибок. Вы может быть не понимаете. Число неизвестных n.

Простите если, что не так.



Редактировалось 1 раз(а). Последний 07.09.2010 08:08.
Ответить Цитировать
31.08.2010 18:10
maxal
RegularChains
В приличных матпакетах есть специальные функции для решения систем полиномиальных уравнений.
Например, в мапле для этого предназначен пакет RegularChains - см. http://www.maplesoft.com/support/help/Maple/view.aspx?path=RegularChains
Ответить Цитировать
31.08.2010 21:22
museum
В чем проблема?
Услови такое ?
Цитата

Моя система выглядит так:
(x1-a11)(x2-a12)...(xn-a1n) =0
(x1-a21)(x2-a22)...(xn-a2n) =0
.............................................
(x1-am1)(x2-am2)...(xn-amn) =0

xi и aij принадлежат {0,1}. aij - известны.

Мне кажется в таком случае (для такой системы) есть эффективный способ нахождения решений.
Здесь действительно все уравнения в виде произведений равных нулю?
Тогда эфективный алгоритм есть! Каждое уравнение эквивалентно дизъюнкции равенств. Сама система - это конъюнкция дизъюнкций. Представьте ее как дизъюнкцию конъюнкций. Осталось только выбросить несовместные конъюнкции (чтобы не было равенства одной переменной двум различным числам) , а остальные - это решения системы.
Ответить Цитировать
31.08.2010 22:30
hazzo
хм...
А как выбросить несовместные конъюнкции?
Ответить Цитировать
01.09.2010 13:48
museum
Просто стереть
Представив систему в виде дизъюнкции, Вы просто перешли к системе с "квадратной скобкой", которая объединяет решения систем-конъюнкций. Несовместные системы не дают решений и их просто удаляют из системы. Если писать на доске, то их можно стереть, а так - переписать снова, но без них.
Ответить Цитировать
Страницы: 12
« Следующая тема   Предыдущая тема »
Извините, только зарегистрированные пользователи могут публиковать сообщения в этом форуме.

Кликните здесь, чтобы войти