交互方向陰解法

数値線形代数において、交互方向陰解法（ADI法）は、シルベスター行列方程式を解くために用いられる反復法である。システム理論や制御において生じる大規模な行列方程式を解くための一般的な手法であり、^[1]メモリ効率の高い因数分解形式で解を構築することができる。^{[2] [3]また、}放物型および楕円型の偏微分方程式の数値解法にも用いられ、熱伝導のモデル化や2次元以上の拡散方程式の解法として用いられる古典的な手法でもある。 ^[4]これは演算子分割法の一例である。^[5]

この方法は1950年代半ばにハンブル・オイル社でジム・ダグラス・ジュニア、ヘンリー・ラッチフォード、ドン・ピースマンによって開発されました。 ^[6]

行列方程式のADI

方法

ADI法は、近似解の列空間と行空間を交互に更新する2段階の反復処理です。1回のADI反復は、以下のステップで構成されます。^[7]${\displaystyle AX-XB=C}$

1. を解く。ここで${\displaystyle X^{(j+1/2)}}$ ${\displaystyle \left(A-\beta _{j+1}I\right)X^{(j+1/2)}=X^{(j)}\left(B-\beta _{j+1}I\right)+C.}$

2. を解きます。ここで、 です 。${\displaystyle X^{(j+1)}}$ ${\displaystyle X^{(j+1)}\left(B-\alpha _{j+1}I\right)=\left(A-\alpha _{j+1}I\right)X^{(j+1/2)}-C}$

これらの数値はシフトパラメータと呼ばれ、収束はこれらのパラメータの選択に大きく依存します。^{[8] [9]} ADIの反復を実行するには、初期推定値とシフトパラメータが必要です。 ${\displaystyle (\alpha _{j+1},\beta _{j+1})}$ ${\displaystyle K}$ ${\displaystyle X^{(0)}}$ ${\displaystyle K}$ ${\displaystyle \{(\alpha _{j},\beta _{j})\}_{j=1}^{K}}$

ADIを使用する場合

およびの 場合、バーテルス・スチュワート法を使用してを直接解くことができます。^[10]したがって、行列ベクトル乗算と を含む線形解が安価に適用できる 場合にのみ、ADI を使用するのが有益です。${\displaystyle A\in \mathbb {C} ^{m\times m}}$ ${\displaystyle B\in \mathbb {C} ^{n\times n}}$ ${\displaystyle AX-XB=C}$ ${\displaystyle {\mathcal {O}}(m^{3}+n^{3})}$ ${\displaystyle A}$ ${\displaystyle B}$

方程式はのときのみ一意に解を持つ。ここで はのスペクトルである。 [ ^1]しかし、ADI法はと がよく分離されていて、と が正規行列である場合に特に良好なパフォーマンスを示す。これらの仮定は、例えばが正定値 である場合のリャプノフ方程式によって満たされる。これらの仮定の下では、およびのいくつかの選択に対して、ほぼ最適なシフトパラメータが既知である。^{[8] [9]}さらに、事前誤差境界を計算できるため、実装時に残差誤差を監視する必要がなくなる。 ${\displaystyle AX-XB=C}$ ${\displaystyle \sigma (A)\cap \sigma (B)=\emptyset }$ ${\displaystyle \sigma (M)}$ ${\displaystyle M}$ ${\displaystyle \sigma (A)}$ ${\displaystyle \sigma (B)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle AX+XA^{*}=C}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle B}$

上記の仮定が満たされない場合でも、ADI法は適用可能です。最適ではないシフトパラメータの使用は収束に悪影響を与える可能性があり^[1] 、また、収束はまたはの非正規性によっても影響を受けます（場合によっては収束に有利に働くこともあります）。^{[11]有理クリロフ部分空間法[12]}などのクリロフ部分空間法は、この設定においてADIよりも典型的に収束が速いことが観察されており^{[1] [3]}、これがハイブリッドADI投影法の開発につながりました。^[3]${\displaystyle A}$ ${\displaystyle B}$

シフトパラメータの選択とADI誤差方程式

適切なシフトパラメータを見つける問題は簡単ではありません。この問題は、ADIの誤差方程式を調べることで理解できます。反復計算の後、誤差は次のように表されます。 ${\displaystyle K}$

${\displaystyle X-X^{(K)}=\prod _{j=1}^{K}{\frac {(A-\alpha _{j}I)}{(A-\beta _{j}I)}}\left(X-X^{(0)}\right)\prod _{j=1}^{K}{\frac {(B-\beta _{j}I)}{(B-\alpha _{j}I)}}.}$

を選択すると、相対誤差の境界は次のようになります。 ${\displaystyle X^{(0)}=0}$

${\displaystyle {\frac {\left\|X-X^{(K)}\right\|_{2}}{\|X\|_{2}}}\leq \|r_{K}(A)\|_{2}\|r_{K}(B)^{-1}\|_{2},\quad r_{K}(M)=\prod _{j=1}^{K}{\frac {(M-\alpha _{j}I)}{(M-\beta _{j}I)}}.}$

ここでは演算子ノルムである。理想的なシフトパラメータの集合は、 を最小化する有理関数を定義する。と が正規行列であり、 と が固有分解を持つ場合 、${\displaystyle \|\cdot \|_{2}}$ ${\displaystyle \{(\alpha _{j},\beta _{j})\}_{j=1}^{K}}$ ${\displaystyle r_{K}}$ ${\displaystyle \|r_{K}(A)\|_{2}\|r_{K}(B)^{-1}\|_{2}}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A=V_{A}\Lambda _{A}V_{A}^{*}}$ ${\displaystyle B=V_{B}\Lambda _{B}V_{B}^{*}}$

${\displaystyle \|r_{K}(A)\|_{2}\|r_{K}(B)^{-1}\|_{2}=\|r_{K}(\Lambda _{A})\|_{2}\|r_{K}(\Lambda _{B})^{-1}\|_{2}}$ 。

ほぼ最適なシフトパラメータ

近似最適シフトパラメータは、 と （ただし、 と は実数直線上の互いに素な区間）のような特定のケースでは既知である。[ 8 ] ^{[ 9]}例えば、リャプノフ方程式 は、 が正定値のときにこれらの仮定を満たす。この場合、シフトパラメータは楕円積分を用いて閉じた形で表すことができ、数値的に簡単に計算できる。 ${\displaystyle \Lambda _{A}\subset [a,b]}$ ${\displaystyle \Lambda _{B}\subset [c,d]}$ ${\displaystyle [a,b]}$ ${\displaystyle [c,d]}$ ${\displaystyle AX+XA^{*}=C}$ ${\displaystyle A}$

より一般的には、閉じた互いに素な集合と（ただし、 およびが既知である）の場合、最適なシフトパラメータ選択問題は、次の値を達成する極値有理関数を見つけることによって近似的に解かれる。 ${\displaystyle E}$ ${\displaystyle F}$ ${\displaystyle \Lambda _{A}\subset E}$ ${\displaystyle \Lambda _{B}\subset F}$

${\displaystyle Z_{K}(E,F):=\inf _{r}{\frac {\sup _{z\in E}|r(z)|}{\inf _{z\in F}|r(z)|}},}$

ここで、最小値は 次数のすべての有理関数にわたって取られる。^[9]この近似問題は、ポテンシャル理論のいくつかの結果と関連しており、^{[13] [14]} 、 1877 年にゾロタレフによって= [a, b] および ^[15]に対して解かれた。この解は、 とが複素平面上で互いに素な円板である場合にも既知である。 ^[16]${\displaystyle (K,K)}$ ${\displaystyle E}$ ${\displaystyle F=-E.}$ ${\displaystyle E}$ ${\displaystyle F}$

ヒューリスティックシフトパラメータ戦略

とについての知識が少ない場合、またはまたは が非正規行列である場合、最適に近いシフトパラメータを見つけることができない可能性があります。このような状況では、適切なシフトパラメータを生成するためのさまざまな戦略を使用できます。これには、ポテンシャル理論の漸近結果に基づく戦略、行列、、、のリッツ値を使用して貪欲アプローチを定式化する戦略、^{[18]および}収束許容値が満たされるまで同じ小さなシフトパラメータのコレクションを再利用する巡回法が含まれます。^{[18] [11]}すべての反復で同じシフトパラメータが使用される場合、ADIはスミス法と呼ばれるアルゴリズムと同等です。^[19]${\displaystyle \sigma (A)}$ ${\displaystyle \sigma (B)}$ ${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A}$ ${\displaystyle A^{-1}}$ ${\displaystyle B}$ ${\displaystyle B^{-1}}$

係数付きADI

多くの応用において、とは非常に大きな疎行列であり、（ただし、 ）として因数分解できます。^[1] このような設定では、潜在的に密な行列を明示的に保存することが現実的ではない場合があります。ADIの変種である因数分解ADI ^{[3] [2]}は（ただし ）を計算するために使用できます。因数分解ADIの有効性は、 が低ランク行列で十分に近似できるかどうかに依存します。これは、 とに関するさまざまな仮定の下で真であることが知られています。^{[11] [9]}${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle C}$ ${\displaystyle C=C_{1}C_{2}^{*}}$ ${\displaystyle C_{1}\in \mathbb {C} ^{m\times r},C_{2}\in \mathbb {C} ^{n\times r}}$ ${\displaystyle r=1,2}$ ${\displaystyle X}$ ${\displaystyle ZY^{*}}$ ${\displaystyle X\approx ZY^{*}}$ ${\displaystyle X}$ ${\displaystyle A}$ ${\displaystyle B}$

放物線方程式のADI

歴史的に、ADI法は正方領域上の2次元拡散方程式を有限差分法を用いて解くために開発されました。^[4]行列方程式のADIとは異なり、放物型方程式のADIではシフトパラメータの選択は不要です。これは、各反復におけるシフトが時間ステップ、拡散係数、格子間隔などのパラメータによって決定されるためです。行列方程式のADIとの関連性は、定常状態におけるシステムに対するADI反復の作用を考えると明らかです。

例: 2次元拡散方程式

差分方程式における交互方向陰解法のステンシル図

熱伝導方程式を数値的に解く従来の方法は、クランク・ニコルソン法です。この方法では、多次元にわたる非常に複雑な方程式群が生成され、解くのに多大なコストがかかります。ADI法の利点は、各ステップで解くべき方程式の構造がより単純であり、三重対角行列アルゴリズムを用いて効率的に解くことができることです。

2次元の線形拡散方程式を考えてみましょう。

${\displaystyle {\partial u \over \partial t}=\left({\partial ^{2}u \over \partial x^{2}}+{\partial ^{2}u \over \partial y^{2}}\right)=(u_{xx}+u_{yy})}$

暗黙的なクランク・ニコルソン法では、次の差分方程式が生成されます。

${\displaystyle {u_{ij}^{n+1}-u_{ij}^{n} \over \Delta t}={1 \over 2(\Delta x)^{2}}\left(\delta _{x}^{2}+\delta _{y}^{2}\right)\left(u_{ij}^{n+1}+u_{ij}^{n}\right)}$

どこ：

${\displaystyle \Delta x=\Delta y}$

はp番目の座標 の中心となる2階差分演算子である。${\displaystyle \delta _{p}^{2}}$

${\displaystyle \delta _{p}^{2}u_{ij}=u_{ij+e_{p}}-2u_{ij}+u_{ij-e_{p}}}$

またはの場合はそれぞれまたは（およびlattice points の省略形）。 ${\displaystyle e_{p}=(1,0)}$ ${\displaystyle (0,1)}$ ${\displaystyle p=x}$ ${\displaystyle y}$ ${\displaystyle ij}$ ${\displaystyle (i,j)}$

安定性解析を実行した後、この方法は任意の に対して安定していることが示されます。 ${\displaystyle \Delta t}$

クランク・ニコルソン法の欠点は、上式の行列が一般に非常に大きなバンド幅を持つ帯状になっていることです。そのため、連立一次方程式を直接解くのは非常にコストがかかります（ただし、不完全コレスキー分解を前処理とした共役勾配法など、効率的な近似解法は存在します）。

ADI法の背後にある考え方は、差分方程式を2つに分割し、1つはx微分を暗黙的に取り、もう1つはy微分を暗黙的に取るというものである。

${\displaystyle {u_{ij}^{n+1/2}-u_{ij}^{n} \over \Delta t/2}={\left(\delta _{x}^{2}u_{ij}^{n+1/2}+\delta _{y}^{2}u_{ij}^{n}\right) \over \Delta x^{2}}}$

${\displaystyle {u_{ij}^{n+1}-u_{ij}^{n+1/2} \over \Delta t/2}={\left(\delta _{x}^{2}u_{ij}^{n+1/2}+\delta _{y}^{2}u_{ij}^{n+1}\right) \over \Delta y^{2}}}$

関係する方程式系は対称かつ三重対角（帯域幅 3 でバンド化）であり、通常は三重対角行列アルゴリズムを使用して解かれます。

この方法は無条件に安定しており、時間と空間において2次の性質を持つことが示されています。^[20] ダグラス法^[21]やf因子法^[22]など、3次元以上に使用できる、より洗練されたADI法もあります。

一般化

ADI法を演算子分割法として用いることは一般化できる。つまり、一般的な発展方程式を考えることができる。

${\displaystyle {\dot {u}}=F_{1}u+F_{2}u,}$

ここで、およびはバナッハ空間上で定義された（非線形の可能性のある）演算子です。^{[23] [24]}上記の拡散の例では、およびが成り立ちます。 ${\displaystyle F_{1}}$ ${\displaystyle F_{2}}$ ${\displaystyle F_{1}={\partial ^{2} \over \partial x^{2}}}$ ${\displaystyle F_{2}={\partial ^{2} \over \partial y^{2}}}$

ファンダメンタルADI（FADI）

ADIからFADIへの簡素化

従来のADI法を簡略化して、左辺にのみ類似の演算子を持ち、右辺には演算子を持たない「基本ADI法」にすることが可能です。これはADI法の基本（基本）スキームとみなすことができ、^{[25] [26]} 、方程式の両辺に演算子を持つ従来の陰解法の多くとは異なり、右辺に（縮約される）演算子が不要になります。FADI法は、従来のADI法の精度を損なうことなく、より単純で簡潔かつ効率的な更新方程式を実現します。

他の暗黙的メソッドとの関係

ピースマン・ラッチフォード法、ダグラス・ガン法、ディアコノフ法、ビーム・ウォーミング法、クランク・ニコルソン法などによる多くの古典的な陰解法は、右辺に演算子のない基本陰解法に簡略化できる。^[26]基本形態では、2次の時間精度のFADI法は、計算電磁気学における3次元マクスウェル方程式^{[27] [28]などに対して2次の時間精度にアップグレードできる基本局所1次元法（FLOD法）}と密接に関連している。2次元および3次元の熱伝導および拡散方程式に対しては、FADI法とFLOD法はどちらも、従来の方法に比べて単純で効率的かつ安定した方法で実装できる。^{[29] [30]}

さらに読む

• アダム・ウサディ、クリント・ドーソン（2006年3月）「ADIメソッド50周年：ジム・ダグラス、ドン・ピースマン、ヘンリー・ラッチフォードの貢献を称えて」SIAMニュース39 (2) 。2025年3月28日閲覧– ResearchGate.net経由。(長年にわたる ADI の方法とその変種のレビューを提供します。)

参考文献

1. Simoncini, V. (2016). 「線形行列方程式の計算手法」. SIAM Review . 58 (3): 377– 441. doi :10.1137/130912839. hdl : 11585/586011 . ISSN  0036-1445. S2CID  17271167.
2. Li, Jing-Rebecca ; White, Jacob (2002). 「Low Rank Solution of Lyapunov Equations」. SIAM Journal on Matrix Analysis and Applications . 24 (1): 260– 280. doi :10.1137/s0895479801384937. ISSN  0895-4798.
3. Benner, Peter; Li, Ren-Cang; Truhar, Ninoslav (2009). 「シルベスター方程式に対するADI法について」. Journal of Computational and Applied Mathematics . 233 (4): 1035– 1045. Bibcode :2009JCoAM.233.1035B. doi : 10.1016/j.cam.2009.08.108 . ISSN  0377-0427.
4. Peaceman, DW; Rachford Jr., HH (1955)、「放物型および楕円型微分方程式の数値解」、応用数学協会誌、3 (1): 28– 41、doi :10.1137/0103003、hdl : 10338.dmlcz/135399、MR  0071874。
5. * Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007). 「セクション 20.3.3. 演算子分割法の一般論」.数値計算レシピ：科学計算の芸術（第3版）. ニューヨーク：ケンブリッジ大学出版局. ISBN 978-0-521-88068-8. 2011年8月11日時点のオリジナルよりアーカイブ。2011年8月18日閲覧。
6. 「ジム・ダグラス教授」パデュー大学、2016年5月2日。 2025年3月25日閲覧。
7. Wachspress, Eugene L. (2008). 「リアプノフ方程式ソルバーへの道」. Computers & Mathematics with Applications . 55 (8): 1653– 1659. doi : 10.1016/j.camwa.2007.04.048 . ISSN  0898-1221.
8. Lu, An; Wachspress, EL (1991). 「交互方向暗黙反復法によるリアプノフ方程式の解法」. Computers & Mathematics with Applications . 21 (9): 43– 58. doi :10.1016/0898-1221(91)90124-m. ISSN  0898-1221.
9. Beckermann, Bernhard; Townsend, Alex (2017). 「変位構造を持つ行列の特異値について」. SIAM Journal on Matrix Analysis and Applications . 38 (4): 1227– 1248. arXiv : 1609.09494 . doi :10.1137/16m1096426. ISSN  0895-4798. S2CID  3828461.
10. Golub, G.; Van Loan, C. (1989).行列計算（第4版）. ボルチモア: ジョンズ・ホプキンス大学. ISBN 1421407949. OCLC  824733531。
11. Sabino, J (2007).ブロック修正スミス法による大規模リアプノフ方程式の解法.ライス大学博士論文. hdl :1911/20641.
12. Druskin, V.; Simoncini, V. (2011). 「大規模動的システムのための適応型有理クリロフ部分空間」. Systems & Control Letters . 60 (8): 546– 560. doi :10.1016/j.sysconle.2011.04.013. ISSN  0167-6911.
13. Saff, EB; Totik, V. (2013-11-11).外部場を考慮した対数ポテンシャル. ベルリン: Springer Science & Business Media. ISBN 9783662033296. OCLC  883382758。
14. Gonchar, AA (1969). 「有理関数に関連するゾロタレフ問題」.ソ連数学-スボルニク. 7 (4): 623– 635. Bibcode :1969SbMat...7..623G. doi :10.1070/SM1969v007n04ABEH001107.
15. ゾロタレフ, DI (1877). 「楕円関数のゼロからの最小および最大の偏差を持つ関数に関する問題への応用」. Zap. Imp. Akad. Nauk. サンクトペテルブルク. 30 : 1–59 .
16. Starke, Gerhard (1992年7月). 「複素平面における有理ゾロタレフ問題に対する近似循環性」. Journal of approximation Theory . 70 (1): 115– 130. doi : 10.1016/0021-9045(92)90059-w . ISSN  0021-9045.
17. Starke, Gerhard (1993年6月). 「有理関数のフェイエル・ウォルシュ点とADI反復法におけるその利用」. Journal of Computational and Applied Mathematics . 46 ( 1–2 ): 129– 141. doi : 10.1016/0377-0427(93)90291-i . ISSN  0377-0427.
18. Penzl, Thilo (1999年1月). 「大規模スパース・リアプノフ方程式のための巡回低ランク・スミス法」. SIAM Journal on Scientific Computing . 21 (4): 1401– 1418. Bibcode :1999SJSC...21.1401P. doi :10.1137/s1064827598347666. ISSN  1064-8275.
19. Smith, RA (1968年1月). 「行列方程式 XA + BX = C」. SIAM Journal on Applied Mathematics . 16 (1): 198– 201. doi :10.1137/0116017. ISSN  0036-1399.
20. 陰解法によるu _xx + u _yy = u _tの数値積分について」、応用数学協会誌、3 : 42–65、MR  0071875。
21. Douglas, Jim Jr. (1962)、「3 つの空間変数の交互方向メソッド」、Numerische Mathematik、4 (1): 41–63、doi :10.1007/BF01386295、ISSN  0029-599X、S2CID  121455963。
22. Chang, MJ; Chow, LC; Chang, WS (1991)、「非定常三次元熱拡散問題を解くための改良交互方向暗黙法」、数値熱伝達、パートB：基礎、19 (1): 69– 84、Bibcode :1991NHTB...19...69C、doi :10.1080/10407799108944957、ISSN  1040-7790。
23. Hundsdorfer, Willem; Verwer, Jan (2003).時間依存移流・拡散・反応方程式の数値解法ベルリン、ハイデルベルク: Springer Berlin Heidelberg. ISBN 978-3-662-09017-6。
24. Lions, PL; Mercier, B. (1979年12月). 「2つの非線形演算子の和の分割アルゴリズム」. SIAM Journal on Numerical Analysis . 16 (6): 964– 979. Bibcode :1979SJNA...16..964L. doi :10.1137/0716071.
25. Tan, EL (2007). 「無条件安定3次元ADI-FDTD法のための効率的なアルゴリズム」（PDF） . IEEE Microwave and Wireless Components Letters . 17 (1): 7– 9. doi :10.1109/LMWC.2006.887239. hdl :10356/138245. S2CID  29025478.
26. Tan, EL (2008). 「効率的で無条件に安定な暗黙的有限差分時間領域法の基本スキーム」(PDF) . IEEE Transactions on Antennas and Propagation . 56 (1): 170– 177. arXiv : 2011.14043 . Bibcode :2008ITAP...56..170T. doi :10.1109/TAP.2007.913089. hdl :10356/138249. S2CID  37135325.
27. Tan, EL (2007). 「3次元マクスウェル方程式に対する無条件安定LOD-FDTD法」(PDF) . IEEE Microwave and Wireless Components Letters . 17 (2): 85– 87. doi :10.1109/LMWC.2006.890166. hdl :10356/138296. S2CID  22940993.
28. Gan, TH; Tan, EL (2013). 「2次精度の時間的精度と適合発散を備えた無条件安定な基本LOD-FDTD法」(PDF) . IEEE Transactions on Antennas and Propagation . 61 (5): 2630– 2638. Bibcode :2013ITAP...61.2630G. doi :10.1109/TAP.2013.2242036. S2CID  7578037.
29. Tay, WC; Tan, EL; Heh, DY (2014). 「3次元熱シミュレーションのための局所的1次元基本法」. IEICE Transactions on Electronics . E-97-C (7): 636– 644. Bibcode :2014IEITE..97..636T. doi :10.1587/transele.E97.C.636. hdl : 10220/20410 .
30. Heh, DY; Tan, EL; Tay, WC (2016). 「集積回路の効率的な過渡熱シミュレーションのための高速交互方向暗黙法」.国際数値モデリングジャーナル：電子ネットワーク、デバイス、およびフィールド. 29 (1): 93– 108. doi :10.1002/jnm.2049. hdl : 10356/137201 . S2CID  61039449.