Mathematica: точки ветвления действительных корней многочлена

Я выполняю поиск грубой силы для «градиентных экстремалей» в следующем примере функции

fv[{x_, y_}] = ((y - (x/4)^2)^2 + 1/(4 (1 + (x - 1)^2)))/2;

Это включает в себя нахождение следующих нулей

gecond = With[{g = D[fv[{x, y}], {{x, y}}], h = D[fv[{x, y}], {{x, y}, 2}]},
 g.RotationMatrix[Pi/2].h.g == 0]

Что Reduce с радостью делает для меня:

geyvals = y /. Cases[List@ToRules@Reduce[gecond, {x, y}], {y -> _}];

geyvals — это три корня кубического многочлена, но выражение здесь слишком велико.

Теперь к моему вопросу: для разных значений x разные числа этих корней являются реальными, и я хотел бы выбрать значения x, где разветвляются решения, чтобы собрать воедино экстремали градиента вдоль дна долины (из fv) . В данном случае, поскольку многочлен только кубический, я, вероятно, мог бы сделать это вручную, но я ищу простой способ заставить Mathematica сделать это за меня?

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

Редактировать 2: Поскольку кажется, что реальная проблема намного интереснее, чем корневое ветвление: rcollyer предлагает использовать ContourPlot непосредственно на gecond, чтобы получить экстремали градиента. Чтобы сделать это полным, нам нужно разделить долины и хребты, что делается путем просмотра собственного значения гессиана, перпендикулярного градиенту. Поставив галочку на «долины» как RegionFunction, мы останемся только с линией долины:

valleycond = With[{
    g = D[fv[{x, y}], {{x, y}}], 
    h = D[fv[{x, y}], {{x, y}, 2}]},
  g.RotationMatrix[Pi/2].h.RotationMatrix[-Pi/2].g >= 0];
gbuf["gevalley"]=ContourPlot[gecond // Evaluate, {x, -2, 4}, {y, -.5, 1.2},
   RegionFunction -> Function[{x, y}, Evaluate@valleycond], 
   PlotPoints -> 41];

Что дает только линию дна долины. Включая некоторые контуры и седловую точку:

fvSaddlept = {x, y} /. First@Solve[Thread[D[fv[{x, y}], {{x, y}}] == {0, 0}]]
gbuf["contours"] = ContourPlot[fv[{x, y}],
   {x, -2, 4}, {y, -.7, 1.5}, PlotRange -> {0, 1/2},
   Contours -> fv@fvSaddlept (Range[6]/3 - .01),
   PlotPoints -> 41, AspectRatio -> Automatic, ContourShading -> None];
gbuf["saddle"] = Graphics[{Red, Point[fvSaddlept]}];
Show[gbuf /@ {"contours", "saddle", "gevalley"}]

В итоге получаем такой сюжет:

Контурный график fv с наложенной линией долины


person Janus    schedule 14.12.2010    source источник
comment
Я делал это вручную несколько раз, так что +1. Надеюсь, кто-нибудь найдет способ.   -  person Dr. belisarius    schedule 14.12.2010
comment
@белизарий. Точно - делал это несколько раз, и это неприятность. На этот раз я не могу беспокоиться, так как мне действительно нужен результат только для сюжета, где, если быть до конца честным, простое предположение выглядело бы хорошо... Будем надеяться, что у кого-то есть умная идея :)   -  person Janus    schedule 14.12.2010
comment
@ Янус, прости мое невежество, но как gecond дает тебе экстремалов? Я просто не вижу этого.   -  person rcollyer    schedule 15.12.2010
comment
@ Янус, неважно. Я нашел документ, в котором они обсуждаются, в частности, eqn 3.3 из springerlink.com/content. /1432-881x/69/4 точно соответствует gecond.   -  person rcollyer    schedule 15.12.2010
comment
@rcollyer: Спасибо за ссылку: я наткнулся на несколько статей с потенциальными реакциями, но этот выпуск кажется хорошей подборкой. Это на самом деле тривиально, если вы понимаете, что условие GE эквивалентно требованию, чтобы градиент был собственным вектором кривизны. На самом деле я пришел из этого направления и нашел работу по «градиентным экстремалам» только после того, как сделал немало повторных открытий. Дж. Матем. физ. У 23p732 есть хорошее обсуждение без координат, но тема восходит к Максвеллу и Кейли :)   -  person Janus    schedule 16.12.2010
comment
@janus, если бы вас просто интересовали экстремали градиента и не слишком заботили их формулы, вы могли бы просто ContourPlot[g.RotationMatrix[Pi/2].h.g == 0].   -  person rcollyer    schedule 16.12.2010
comment
@janus, в качестве пояснения, вас интересуют точки ветвления, или будет достаточно метода для создания (по крайней мере, неявной) формулы для реальных корней?   -  person rcollyer    schedule 16.12.2010
comment
@rcollyer, нет, мне не нужны точки ветвления. Я предполагаю, что неявный метод - это тот, который вы добавили в свой ответ? Я все еще пытаюсь понять ваш ответ - прокомментирую ниже.   -  person Janus    schedule 17.12.2010
comment
@janus, я пытаюсь воспроизвести контуры твоего сюжета. Судя по их внешнему виду, я предполагаю, что вы используете RegionFunction, что это было?   -  person rcollyer    schedule 17.12.2010
comment
@rcollyer Извините, некоторое время не в сети. Я думаю, что это был просто PlotRange, я включу полный код сюжета выше.   -  person Janus    schedule 22.12.2010


Ответы (4)


Не уверен, что это (с опозданием) помогает, но, похоже, вас интересуют дискриминантные точки, то есть, где и полиномиальные, и производные (относительно y) исчезают. Вы можете решить эту систему для {x,y} и отбросить сложные решения, как показано ниже.

fv[{x_, y_}] = ((y - (x/4)^2)^2 + 1/(4 (1 + (x - 1)^2)))/2;

gecond = With[{g = D[fv[{x, y}], {{x, y}}], 
   h = D[fv[{x, y}], {{x, y}, 2}]}, g.RotationMatrix[Pi/2].h.g]

In[14]:= Cases[{x, y} /. 
  NSolve[{gecond, D[gecond, y]} == 0, {x, y}], {_Real, _Real}]

Out[14]= {{-0.0158768, -15.2464}, {1.05635, -0.963629}, {1., 
  0.0625}, {1., 0.0625}}
person Daniel Lichtblau    schedule 13.01.2011
comment
Спасибо, Даниил! Вы правы, это именно те точки, за которыми я гнался — ловит как точки ветвления, так и пересечения корней: значения с кратным корнем, так что P(a,x)==0 и dP(a,x)/dx=0. - person Janus; 14.01.2011

Если вы хотите только отобразить результат, используйте StreamPlot[] для градиентов:

grad = D[fv[{x, y}], {{x, y}}];
StreamPlot[grad, {x, -5, 5}, {y, -5, 5}, 
           RegionFunction -> Function[{x, y}, fv[{x, y}] < 1],
           StreamScale -> 1]

Возможно, вам придется повозиться с точностью графика, StreamStyle и RegionFunction, чтобы добиться идеального результата. Особенно полезным было бы использование решения для дна долины для программного заполнения StreamPoints.

person Timo    schedule 14.12.2010
comment
Спасибо, Тимо. Проблема с диаграммой потоков заключается в том, что «линии падения», как известны результирующие линии, математически гарантированно отклоняются от стационарных путей (крайних значений градиента), см., например, Дж. Матем. физ. 23p732. Особенно в интересных регионах :) Также: у меня есть хороший алгоритм для поиска долины - этот вопрос был больше о корневом ветвлении. - person Janus; 15.12.2010

Обновлено: см. ниже.

Я бы подошел к этому сначала, визуализируя воображаемые части корней:

график мнимых частей корней

Это сразу говорит вам о трех вещах: 1) первый корень всегда действителен, 2) вторые два являются сопряженными парами и 3) существует небольшая область около нуля, в которой все три действительны. Кроме того, обратите внимание, что исключения избавились только от особой точки в x=0, и мы можем понять, почему, когда увеличим масштаб:

увеличьте фотографию выше с x от 0 до 1,5

Затем мы можем использовать EvalutionMonitor для генерирования списка корней напрямую:

Map[Module[{f, fcn = #1}, 
            f[x_] := Im[fcn];
            Reap[Plot[f[x], {x, 0, 1.5}, 
                  Exclusions -> {True, f[x] == 1, f[x] == -1}, 
                  EvaluationMonitor :> Sow[{x, f[x]}][[2, 1]] // 
            SortBy[#, First] &];]
   ]&, geyvals]

(Обратите внимание, что спецификация Part немного странная, Reap возвращает List того, что посеяно как второй элемент в List, так что получается вложенный список. Кроме того, Plot не выбирает точки прямым способом, поэтому SortBy.) Может быть более элегантный способ определить, где два последних корня становятся комплексными, но, поскольку их мнимые части кусочно-непрерывны, кажется, что проще выполнить его методом грубой силы.

Правка: поскольку вы упомянули, что вам нужен автоматический метод для генерации, когда некоторые корни становятся сложными, я исследовал, что происходит, когда вы подставляете y -> p + I q. Теперь это предполагает, что x реально, но вы уже сделали это в своем решении. В частности, я делаю следующее

In[1] := poly = g.RotationMatrix[Pi/2].h.g /. {y -> p + I q} // ComplexExpand;
In[2] := {pr,pi} = poly /. Complex[a_, b_] :> a + z b & // CoefficientList[#, z] & //
         Simplify[#, {x, p, q} \[Element] Reals]&;

где второй шаг позволяет мне изолировать действительную и мнимую части уравнения и упростить их независимо друг от друга. Делаем то же самое с общим двумерным полиномом f + d x + a x^2 + e y + 2 c x y + b y^2, но делаем как x, так и y комплексными; Я отметил, что Im[poly] = Im[x] D[poly, Im[x]] + Im[y] D[poly,[y]], и это может относиться и к вашему уравнению. Делая x реальным, мнимая часть poly становится q раз некоторой функцией x, p и q. Итак, установка q=0 всегда дает Im[poly] == 0. Но это не говорит нам ничего нового. Однако, если мы

In[3] := qvals = Cases[List@ToRules@RReduce[ pi == 0 && q != 0, {x,p,q}], 
          {q -> a_}:> a];

мы получаем несколько формул для q с участием x и p. Для некоторых значений x и p эти формулы могут быть воображаемыми, и мы можем использовать Reduce, чтобы определить, где Re[qvals] == 0. Другими словами, мы хотим, чтобы «мнимая» часть y была реальной, а этого можно добиться, разрешив q быть равным нулю или чисто мнимым. Построение области, где Re[q]==0, и наложение экстремальных линий градиента через

With[{rngs = Sequence[{x,-2,2},{y,-10,10}]},
Show@{
 RegionPlot[Evaluate[Thread[Re[qvals]==0]/.p-> y], rngs],
 ContourPlot[g.RotationMatrix[Pi/2].h.g==0,rngs 
      ContourStyle -> {Darker@Red,Dashed}]}]

дает

график x-y, показывающий экстремали градиента и область, где есть 3 действительных корня

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

person rcollyer    schedule 14.12.2010
comment
Мне нравится идея использования встроенной логики Plot для увеличения ключевых моментов. Поэкспериментировав с этим, кажется, что требуется некоторая постобработка, чтобы обнаружить резкие изгибы. - person Janus; 15.12.2010
comment
+1 за огромные усилия! И отметка для простого контурного построения gecond: это не совсем ответ на корневое разветвление, но это умное решение моей актуальной проблемы. Добавил к моему вопросу дополнительную информацию о долинах / хребтах. - person Janus; 17.12.2010
comment
@janus, если бы я знал, что получу галочку за построение экстремалей, я бы сделал это намного, намного раньше. :) - person rcollyer; 17.12.2010
comment
Я согласен, что не совсем кошерно ставить галочку для не-строго-ответа, но не похоже, что кто-то еще работает над корневым ответвлением, и я действительно никогда не думал о простом выполнении ContourPlot, так что это действительно решило мою проблему. актуальная проблема... - person Janus; 17.12.2010
comment
@ Янус, не волнуйся об этом. Он прибил его, пока я просто ковырялся в темноте. так что не беда. - person rcollyer; 14.01.2011

Закончилось тем, что я попробовал себя, так как целью действительно было сделать это «без рук». Я оставлю вопрос открытым на некоторое время, чтобы посмотреть, найдет ли кто-нибудь лучший способ.

В приведенном ниже коде используется деление пополам для заключения в скобки точек, в которых CountRoots изменяет значение. Это работает для моего случая (обнаружение сингулярности при x = 0 - чистая удача):

In[214]:= findRootBranches[Function[x, Evaluate@geyvals[[1, 1]]], {-5, 5}]
Out[214]= {{{-5., -0.0158768}, 1}, {{-0.0158768, -5.96046*10^-9}, 3}, {{0., 0.}, 2}, {{5.96046*10^-9, 1.05635}, 3}, {{1.05635, 5.}, 1}}

Выполнение:

Options[findRootBranches] = {
   AccuracyGoal -> $MachinePrecision/2,
   "SamplePoints" -> 100};

findRootBranches::usage = 
  "findRootBranches[f,{x0,x1}]: Find the the points in [x0,x1] \
  where the number of real roots of a polynomial changes.
  Returns list of {<interval>,<root count>} pairs.
  f: Real -> Polynomial as pure function, e.g f=Function[x,#^2-x&]." ; 

findRootBranches[f_, {xa_, xb_}, OptionsPattern[]] := Module[
  {bisect, y, rootCount, acc = 10^-OptionValue[AccuracyGoal]},
  rootCount[x_] := {x, CountRoots[f[x][y], y]};

  (* Define a ecursive bisector w/ automatic subdivision *)
  bisect[{{x1_, n1_}, {x2_, n2_}} /; Abs[x1 - x2] > acc] := 
   Module[{x3, n3},
    {x3, n3} = rootCount[(x1 + x2)/2];
    Which[
     n1 == n3, bisect[{{x3, n3}, {x2, n2}}],
     n2 == n3, bisect[{{x1, n1}, {x3, n3}}],
     True, {bisect[{{x1, n1}, {x3, n3}}], 
      bisect[{{x3, n3}, {x2, n2}}]}]];

  (* Find initial brackets and bisect *)
  Module[{xn, samplepoints, brackets},
   samplepoints = N@With[{sp = OptionValue["SamplePoints"]},
      If[NumberQ[sp], xa + (xb - xa) Range[0, sp]/sp, Union[{xa, xb}, sp]]];
   (* Start by counting roots at initial sample points *)
   xn = rootCount /@ samplepoints;
   (* Then, identify and refine the brackets *)
   brackets = Flatten[bisect /@ 
      Cases[Partition[xn, 2, 1], {{_, a_}, {_, b_}} /; a != b]];
   (* Reinclude the endpoints and partition into same-rootcount segments: *)
   With[{allpts = Join[{First@xn}, 
       Flatten[brackets /. bisect -> List, 2], {Last@xn}]},
    {#1, Last[#2]} & @@@ Transpose /@ Partition[allpts, 2]
    ]]]
person Janus    schedule 15.12.2010
comment
-1: это не определяет случаи, когда два корня пересекаются друг с другом. - person Janus; 15.12.2010
comment
Итак, найти точное местоположение корневого пересечения вполне выполнимо, так как Mathematica может выполнять последовательное расширение корневых объектов: x/.First@Solve[0==Normal@Quiet@Series[r1-r2,{x,x0,1}],x]. Теперь, как обнаружить потенциальные пересечения, не так очевидно... - person Janus; 16.12.2010