Метод многовариантного деления пополам
Мне нужен алгоритм для выполнения двумерного метода деления пополам для решения нелинейной задачи 2x2. Пример: два уравнения f (x, y) = 0 и g (x, y) = 0 , которые я хочу решить одновременно. Я очень хорошо знаком с 1D-бисекцией (а также с другими численными методами). Предположим, я уже знаю, что решение лежит между границами x1 y1
В сетке начальные границы:
^
| C D
y2 -+ o-------o
| | |
| | |
| | |
y1 -+ o-------o
| A B
o--+------+---->
x1 x2
и мне известны значения f (A), f (B), f (C) и f (D) , а также g (A), g (B), г (C) и 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 И g (G) * g (M) <0 кажется подавляющим. Может быть, я делаю это немного слишком сложным, но я думаю, что должна быть многомерная версия деления пополам, точно так же, как Ньютон-Рафсон может быть легко разложен с использованием градиентных операторов.
Любые подсказки, комментарии или ссылки приветствуются.
3 ответа
Извините, хотя деление пополам работает в 1-м, оно не работает в более высоких измерениях. Вы просто не можете разбить двумерную область на подобласти, используя только информацию о функции в углах области и точке внутри. По словам Мика Джаггера, «Вы не всегда можете получить то, что хотите» .
Я бы разделил область только по одному измерению, чередуя измерения. Условием существования нуля для одной функции будет «у вас есть две точки разного знака на границе области», поэтому я бы просто проверил это для двух функций. Однако я не думаю, что это сработает, поскольку нули обеих функций в определенной области не гарантируют общий ноль (это может даже существовать в другой области, которая не соответствует критерию ).
Например, посмотрите на это изображение:
Невозможно различить квадраты ABED и EFIH , учитывая только f () и g () на их границе. Однако ABED не содержит общего нуля, а EFIH содержит.
Это было бы похоже на запросы по региону, например, с использованием. kD-деревья, если вы можете с уверенностью определить, что регион не содержит нуля, например. f . Тем не менее, при некоторых обстоятельствах это может происходить медленно.
Если вы можете предположить (согласно вашему комментарию к woodchips), что f(x,y)=0 определяет непрерывную монотонную функцию y=f2(x), т.е. для каждого x1<=x<=x2 существует единственное решение для y (вы просто не можете выразить его аналитически из-за беспорядочной формы f), и аналогично y=g2(x) является непрерывной монотонной функцией, то существует способ найти совместное решение.
Если бы вы могли вычислить 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 как непрерывные монотонные функции.