15

自分で実装できるように、Levenberg-Marquardt 曲線近似アルゴリズムがどのように機能するかを学びたいと考えているプログラマーです。読者が数学者ではなくプログラマーである場合に、それがどのように機能するかを詳細に説明できる優れたチュートリアルはどこにありますか。

私の目標は、このアルゴリズムを opencl に実装して、ハードウェア アクセラレーションを実行できるようにすることです。

4

5 に答える 5

28

関数を最小化することは、表面の最低点を見つけようとするようなものです。丘陵地を歩いていて、最低点に到達しようとしていると考えてください。下り坂になる方向を見つけて、下り坂がなくなるまで歩きます。次に、下り坂になる新しい方向を選択し、下り坂がなくなるまでその方向に歩きます。最終的には（うまくいけば）、下り坂の方向がなくなるポイントに到達するでしょう。その後、(ローカル) 最小になります。

LM アルゴリズムと他の多くの最小化アルゴリズムは、このスキームを使用します。

最小化される関数が F で、反復の点 x(n) にいるとします。F(x(n+1)) < F(x(n)) となる次の反復 x(n+1) を見つけたいと考えています。つまり、関数の値が小さくなります。x(n+1) を選択するには、x(n) からの方向とステップ サイズ (その方向に移動する距離) の 2 つが必要です。LM アルゴリズムは、これらの値を次のように決定します。

まず、点 x(n) における F の線形近似を計算します。下り坂の方向は一次関数の方が分かりやすいので、線形近似関数を使って下り坂の方向を求めます。次に、この選択した方向にどこまで進むことができるかを知る必要があります。近似線形関数が x(n) 付近の大きな領域の F の適切な近似値である場合、かなり大きなステップを取ることができます。それが x(n) に非常に近いだけの適切な近似である場合、非常に小さなステップしか取ることができません。

これが LM が行うことです。x(n) で F の線形近似を計算し、下り坂の方向を示します。次に、線形関数が x(n) で F をどれだけ適切に近似しているかに基づいて、ステップの大きさを計算します。LM は、このように決定された方向に基本的にステップを踏み、F の線形近似がどれだけ減少したかを実際の関数 F がどれだけ減少したかを比較することによって、近似関数がどれほど優れているかを把握します。それらが近い場合、近似関数は適切であり、少し大きなステップを取ることができます. それらが近くない場合、近似関数は適切ではないため、後退してより小さなステップを実行する必要があります。

于 2009-10-30T19:27:03.327 に答える
13
于 2009-07-16T09:39:21.150 に答える
5

LM アルゴリズムの基本的な考え方は数ページで説明できますが、高速で堅牢な製品レベルの実装には、多くの微妙な最適化が必要です。最新技術は、Moré らによる Minpack の実装であり、Moré 1978 ( http://link.springer.com/content/pdf/10.1007/BFb0067700.pdf ) および Minpack ユーザーガイド ( http ://www.mcs.anl.gov/~more/ANL8074b.pdf )。コードを調べるには、私の C 翻訳 ( https://jugit.fz-juelich.de/mlz/lmfit ) の方がおそらく元の Fortran コードよりもアクセスしやすいでしょう。

于 2013-08-01T09:31:32.713 に答える
3

数値レシピを試してください(Levenberg-Marquardt はセクション 15.5 にあります)。それはオンラインで入手でき、アルゴリズムを詳細に説明していることがわかりました（完全なソースコードがあり、どれだけ詳細を取得できるか...）、それでもアクセスしやすい.

于 2009-07-16T09:38:56.737 に答える
1

私はパデュー大学のコースからのこれらのメモを使用して、MATLAB で一般的なレーベンバーグ・マルカート曲線近似アルゴリズムをコード化しました。このアルゴリズムは、数値導関数を計算し、したがってが近似パラメーターのベクトルでf(x;p)ある形式の任意の関数を受け入れます。p

于 2009-10-30T22:20:15.550 に答える