基礎:演算法、近似與誤差

適定問題

/ well-POHZD /

依照阿達瑪(Hadamard)提出的意義,一個問題是適定的,當它表現得像一個合理的問題該有的樣子:它有解、該解唯一、且解連續地依賴於資料——意思是輸入的小變化只造成答案的小變化。這三個條件——存在性、唯一性、對資料的穩定依賴——是計算的通行證。

第三個條件是最微妙、對計算也最重要的。即使答案存在且唯一,若輸入的微小晃動——某個測量的末位偏差,或機器中的一次捨入——能使輸出劇烈擺盪,這個問題就很危險。連續依賴是一個承諾:答案對於真實資料與真實算術中那些微小而不可避免的不完美,是穩健的。可以把它想成在選擇任何方法之前,先問問題本身:真正的答案,是否真的是真正輸入的一個穩定函數?

適定性是問題的性質,不是你用來解它的任何演算法的性質。它是該先檢查的對的事:若底層問題適定,你才可以去尋找一個好而穩定的方法;若不適定,沒有任何演算法能救你,你必須重新表述或對問題做正則化。(注意:適定是一個是非概念;在適定問題之中,條件數接著定量地衡量答案有多敏感。)

對行列式非零的方陣 A 解 A x = b 是適定的:唯一的 x 存在,且 b 的小變化只使 x 略微移動。對帶雜訊的測量資料做微分則是典型的不適定——極小的雜訊會使導數劇烈擺盪。

存在性 + 唯一性 + 對資料的連續(穩定)依賴——阿達瑪的三條件。

適定是容易計算的必要而非充分條件:一個適定問題仍可能非常病態(程度上敏感,雖在極限意義下穩定),即使用完美的演算法也會損失精度。

又称
properly posed problemHadamard well-posed良態問題(廣義)