多變量二分法

我需要一個算法來執行二分二分法來求解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似乎勢不可擋。也許我會讓這個過於複雜，但我認爲應該有一個多維版本的Bisection，就像使用梯度運算符可以很容易地對Newton-Raphson進行多重處理一樣。

歡迎任何線索，評論或鏈接。

來源

2010-08-18 ja72

我不太明白。你的方程是什麼？它不能是f（x，y）= 0，因爲f（A）= f（B）= f（C）= f（D）= 0並且對於g也是一樣的。 – Troubadour 2010-08-18 15:39:37

我正在繪製（x，y）上面函數的域。把它想象成解決方案可能存在的表面圖。上圖中未顯示'f'和'g'的實際值。在地圖上的每個點上，我的函數'f'和'g'都有一個值，我試圖找到地圖上的哪一點使它們同時爲零。 – ja72 2010-08-18 16:48:44

@jalexiou：好的，謝謝。那真的是兩個表面。我現在明白了。 – Troubadour 2010-08-18 16:56:40

我剛從geometrictools.com和C++ code偶然發現了這個答案。

編輯：代碼現在在github。

Title

來源

2014-01-08 22:17:02 ja72

我只會沿着一個維度分割區域，交替維度。你對單個函數零存在的條件是「你在區域邊界上有兩個不同符號的點」，所以我只是檢查了這兩個函數。然而，我認爲它不會奏效，因爲特定區域中的兩個函數的零不是保證了一個公共零（這甚至可能存在於不符合該標準的不同區域中）。

例如，看一下這個圖片：

alt text

沒有辦法，你能辨別ABED和EFIH只給出f()和g()的他們的邊界行爲的平方。但是，ABED不包含共同的零和EFIH呢。

這將類似於使用eg的區域查詢。 kD樹，如果你可以肯定地確定一個地區不包含零例如。 f。不過，在某些情況下，這可能會很慢。

來源

2010-08-18 16:04:53 jpalecek

如果解決方案保證與起始範圍（x1..x2，y1..y2）一致，那麼它必須存在於其中一個子組中（假設函數是連續的），必須有一個算法，發現問題的解決方案是哪一個象限 – ja72 2010-08-18 16:44:51

@jalexiou：See edit。 – jpalecek 2010-08-18 17:17:11

對不起，雖然二分法在1-d中起作用，但它在較高維度上失敗。您只能使用關於該區域角落和內部點的函數的信息來將二維區域分解爲子區域。用米克賈格爾的話說，"You can't always get what you want"。

來源

2010-08-18 16:23:39

你能否詳細說明*「你不能」*。缺少什麼樣的信息？想想f（x，y）= 0'是上面網格上的一條曲線，'g（x，y）= 0'是另一條曲線，兩條曲線相交的地方就是我的解法，可以把它看作一對一的單調但非線性的函數 – ja72 2010-08-18 16:52:21

首先，沒有理由推測對於一些普遍問題，這對零輪廓在任何意義上都是單調的，也許你知道，但如果是這樣，那麼爲什麼你不打擾告訴我們？因爲它是，我認爲你很可能沒有這樣的信息，我可以給你一個非常簡單的功能零輪廓就是一個圓圈。 z（x，y）= x^2 + y^2 - 1 – 2010-08-18 18:14:14

這似乎是錯誤的，2D二分法並非不可能。看到ja72答案 – ThreeStarProgrammer57 2016-06-16 16:44:12

如果可以假定（每到木片您的評論）使得f（X，Y）= 0定義了一個連續的單調函數y = F2（x）時，即，對於每個X1 < = X < = X2有y的唯一解決方案（由於f的凌亂形式，你無法以分析方式表達它），同樣y = g2（x）是一個連續的單調函數，那麼有一種方法可以找到聯合解。如果你可以計算f2和g2，那麼你可以在[x1，x2]上使用1-d二分法來求解f2（x）-g2（x）= 0。你可以通過在[y1，y2]上再次使用1-d二等分來解決f（x，y）= 0對於任何給定的固定x，你需要考慮（x1，x2，（x1 + x2）/2等） - 這就是連續單調性有用的地方 - 對g也是如此。您必須確保在每步之後更新x1-x2和y1-y2。

這種方法可能效率不高，但應該有效。當然，許多雙變量函數並不像連續單調函數那樣與z平面相交。

來源

2010-08-18 22:58:41 Aniko

這是很好的方法，但我不確定它是否保留了平分的屬性。我想要一種保證收斂的方法，雖然效率不高*。再次，我知道這個問題因爲物理規律而受到限制。我會檢查出來。 – ja72 2010-08-19 17:49:55

這與尋找矢量場中的臨界點類似（見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（2nd post）指出了，所以你需要一種方法來制止一個測試，以確保你在四邊形內不會有零。

來源

2011-12-15 19:51:40 cvr

謝謝，我會嘗試雙線性解決方案。我也會看看我的NR書的靈感。 – ja72 2011-12-15 20:29:57

多變量二分法

回答

相關問題