Метод многовариантного деления пополам

Question

Мне нужен алгоритм для выполнения двумерного метода деления пополам для решения нелинейной задачи 2x2.Пример: два уравнения f(x,y)=0 и g(x,y)=0, которые я хочу решить одновременно.Я очень хорошо знаком с 1D-бисекцией (а также с другими численными методами).Предположим, я уже знаю, что решение лежит между границами x1 < x < x2 и y1 < y < y2.

В сетке начальные границы:

    ^
    |   C       D
y2 -+  o-------o
    |  |       |
    |  |       |
    |  |       |
y1 -+  o-------o
    |   A       B
    o--+------+---->
       x1     x2

и я знаю значения f(A), f(B), f(C) and f(D) кака также g(A), g(B), g(C) and g(D).Чтобы начать деление пополам, я думаю, нам нужно разделить точки по краям, а также по центру.

    ^
    |   C   F   D
y2 -+  o---o---o
    |  |       |
    |G o   o M o H
    |  |       |
y1 -+  o---o---o
    |   A   E   B
    o--+------+---->
       x1     x2

Теперь рассмотрим возможности комбинаций, такие как проверка того, выглядит ли f(G)*f(M)<0 AND g(G)*g(M)<0 подавляющим.Может быть, я делаю это немного слишком сложным, но я думаю, что должна быть многомерная версия деления пополам, точно так же, как Ньютон-Рафсон может быть легко изменен с помощью операторов градиента.приветствуются.

Answer 1

Я только что наткнулся на ответ на этот вопрос с ometrictools.com и C ++ code .

edit: код теперь на github .

Answer 2

Извините, хотя бисекция работает в 1-м, она выходит из строя в более высоких измерениях.Вы просто не можете разбить двумерную область на субрегионы, используя только информацию о функции в углах области и точке внутри.По словам Мика Джаггера, «Вы не всегда можете получить то, что хотите» .

Answer 3

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

Например, посмотрите на это изображение:

Невозможно отличить квадраты ABED и EFIH только по данным *Поведение 1012 * и g() на их границе.Тем не менее, ABED не содержит общего нуля, а EFIH -.

Это будет похоже на запросы регионов, использующие, например,.кД-деревья, если вы можете точно определить, что регион не содержит ноль, например,f.Тем не менее, это может быть медленным при некоторых обстоятельствах.

Answer 4

Это похоже на поиск критических точек в векторных полях (см. http://alglobus.net/NASAwork/topology/Papers/alsVugraphs93.ps).

Если у вас есть значения f (x, y) и g (x, y) в вершинах вашегочетырехугольник, и вы находитесь в дискретной задаче (например, у вас нет аналитического выражения для f (x, y) и g (x, y), а также значений в других местах внутри четырехугольника), тогда вы можете использовать билинейную интерполяциючтобы получить два уравнения (для f и g). Для двумерного случая аналитическое решение будет квадратным уравнением, которое, согласно решению (1 корень, 2 действительных корня, 2 мнимых корня), может иметь 1 решение, 2 решения,нет решений, решений внутри или за пределами вашего четырехугольника.

Если вместо этого у вас есть аналитические функции f (x, y) и g (x, y) и вы хотите их использовать, это бесполезно. Вместо этого вы можетеразделите ваш четырехугольник рекурсивно, однако, как это уже указывалось jpalecek ( 2-й пост ), вам понадобится способ остановить ваши деления, выбрав тест, которыйМогу заверить, что внутри четырехугольника не будет нулей.

Answer 5

Если , вы можете предположить (согласно вашему комментарию к щепкам), что f (x, y) = 0 определяет непрерывную монотонную функцию y = f2 (x), т.е. для каждого x1 <= x <= x2 есть уникальное решение для y (вы просто не можете выразить это аналитически из-за грязной формы f), и аналогично y = g2 (x) - непрерывная монотонная функция, тогда есть способ найти совместное решение . </p>

Если бы вы могли вычислить f2 и g2, то вы могли бы использовать 1-й метод деления пополам на [x1, x2] для решения f2 (x) -g2 (x) = 0. И вы можете сделать это, используя 1-й деление пополам на [y1, y2] снова для решения f (x, y) = 0 для y для любого заданного фиксированного x, который вы должны рассмотреть (x1, x2, (x1 + x2) / 2 и т. Д.) - здесь полезна непрерывная монотонность - и аналогично для g. Обязательно обновляйте x1-x2 и y1-y2 после каждого шага.

Этот подход может быть неэффективным, но должен работать. Конечно, многие функции с двумя переменными не пересекают плоскость z как непрерывные монотонные функции.