Mathematica: точки ветвления для вещественных корней многочлена - PullRequest
7 голосов
/ 14 декабря 2010

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

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 для получения экстремалей градиента.Чтобы сделать это полным, нам нужно разделить долины и гребни, что делается путем рассмотрения собственного значения гессиана, перпендикулярного градиенту.Помещая чек на «valleynes» в виде 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"}]

В итоге получается график, подобный следующему:

Contour plot of fv with the valley line superposed

Ответы [ 4 ]

5 голосов
/ 13 января 2011

Не уверен, что это (запоздало) помогает, но, похоже, вас интересуют дискриминантные точки, то есть когда полиномиальные и производные (по 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}}
3 голосов
/ 14 декабря 2010

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

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

plot of the imaginary parts of the roots

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

zoom in of above photo with x between 0 and 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]&;

, где второй шаг позволяет мне выделить действительные и мнимые части уравнения и упростить их независимо друг от друга.Делать то же самое с общим 2D-полиномом, 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 plot showing gradient extremals and region where there are 3 real roots

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

3 голосов
/ 14 декабря 2010

Если вы хотите построить только результат, используйте 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 программно.

0 голосов
/ 15 декабря 2010

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

Приведенный ниже код использует разделение пополам, чтобы заключить точки, где 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]
    ]]]
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...