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

Добро пожаловать в обсуждение систем полиномов



Редактировалось 1 раз(а). Последний 16.08.2010 00:51.

Эффективных я думаю нет.

Ну а раз известны решения каждого ур-ия, то в чем состоит проблема?

Ну, что друзья никто не знает?

Обратите внимание, что m не равно n.

А какой из градиентных методов более эффективен в таком случае? Извините если вопрос окажется глупым.

> А какой из градиентных методов более эффективен в таком случае?

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


> Поэтому мне кажется, что градиентные методы в наихудшем случае с поставленной задачей за разумное время не справятся.
> Может конечно я чего-то недопонимаю.

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

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

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



Редактировалось 1 раз(а). Последний 29.08.2010 18:57.

Упс... Ошибочка вышла. При поверхностном анализе задачи, показалось, что в принятой постановке она имеет аналитическое решение. Ошибся. Но с учетом того, что Вы меня неправильно поняли и уже настроились на численное решение, то и не сильно расстроитесь. Дабы реабилитироваться предлагаю подробный алгоритм ее численного решения. Думаю, что он вполне может претендовать на статус эффективного.
Как и раньше, решение будем искать из условия:
$ \sum_{i=1}^{m} \left((x_1-a_{i,1}) (x_2-a_{i,2})...(x_n-a_{i,n}) \right)^{2} \to min $
Выводя частные производные по искомым параметрам и приравнивая их значения к нулю, получим систему уравнений порядка n:
$ 2\sum_{i=1}^{m} (x_1-a_{i,1})(x_2-a_{i,2})^{2}(x_2-a_{i,2})^{2}...(x_n-a_{i,n})^{2} =0 $ % частная производная по $ x_1 $
$ 2\sum_{i=1}^{m} (x_1-a_{i,1})^{2}(x_2-a_{i,2})(x_2-a_{i,2})^{2}...(x_n-a_{i,n})^{2} =0 $
$ 2\sum_{i=1}^{m} (x_1-a_{i,1})^{2}(x_2-a_{i,2})^{2}(x_2-a_{i,2})...(x_n-a_{i,n})^{2} =0 $

$ ... $

$ 2\sum_{i=1}^{m} (x_1-a_{i,1})^{2}(x_2-a_{i,2})^{2}(x_2-a_{i,2})^{2}...(x_n-a_{i,n}) =0 $ % частная производная по $ x_n $

Решением этой системы является нахождение координат всех экстремумов функционала, среди которых будет и то (те), которое доставляет его минимум (найденными могут быть и максимумы). Аналитическое решение этой задачи при больших m окажется затруднительным. Поэтому в общем случае можно прибегнуть к следующей итерационной схеме решения.
Задаемся начальными значениями переменных $ x_{2}, x_{3}, ... ,x_{n} $.
Из первого уравнения системы частных производных выражаем переменную $ x_{1} $ и вычисляем ее значение относительно известных $ a_{1,1}, a_{1,2}, ... ,a_{1, n} $ и исходно заданных $ x_{2}, x_{3}, ... ,x_{n} $. Отметим, что в этом случае значение переменной $ x_{1} $ вычисляется однозначно, а полученное решение является минимум функционала при прочих заданных параметрах. Иными словами, подобная процедура приведет либо к минимизации функционала, либо оставит его значение без изменения, что может использоваться для обоснования сходимости алгоритма.
Затем аналогичные манипуляции проводим с переменной $ x_{2} $ и вторым уравнением. В качестве переменной $ x_{1} $ используем ранее рассчитанное значение.
И так далее по всем переменным, после чего переходим к следующей итерации, делая новый проход последовательно уточняя значения искомых переменных.
Думаю, что для данной задачи процедура сойдется итераций за 5-10 (конечно, все будет зависеть от n, но много итераций потребоваться не должно).

> какие должны быть x2,x3,...,xn?
Вас цитирую: "xi и aij принадлежат {0,1}", а вообще они могут быть любыми, на работоспособность это не повлияет, повлияет лишь на время оптимизации их начальное отклонение от оптимальных значений.


> Как называется этот алгоритм?
Давайте назовем его алгоритмом численного решения одного вида систем уравнений с мультипликативной нелинейностью... или можно скромно назвать моим именем. На авторство алгоритма я, конечно, не претендую. Критерий минимума среднеквадратичного отклонения и условия его удовлетворения придумали задолго до меня. Численно решать системы нелинейных уравнений придумал тоже не я. Я всего лишь собрал все это в кучу применительно к отдельно взятой задаче.


> Боюсь, что при вычислении значения x1 относительно известных a1,1,a1,2,...,a1,n и исходно заданных x2,x3,...,xn
> могут появляться дополнительные условия, что сделают решение не эффективным.

А Вы не бойтесь, Вы делайте, а не придумывайте проблемы на пустом месте. Программная реализация этого алгоритма займет не больше часа времени. Те дополнительные условия, которые Вас так напугали, соответствуют ситуациям, когда величина переменной не влияет на значение функционала. В этом случае (в случае деления на 0, что, вообще-то говоря, можно рассматривать как исключительный случай, проанализируете условия его появления) значению переменной можно присвоить любое число или просто оставить его без изменений. Во всех остальных случаях значение искомого параметра вычисляется однозначно.