加法シュワルツ法

数学において、ヘルマン・シュワルツにちなんで名付けられた加法シュワルツ法は、偏微分方程式の境界値問題を、より小さな領域の境界値問題に分割し、その結果を加算することによって近似的に解きます。

概要

偏微分方程式（PDE）は、あらゆる科学分野において現象をモデル化するために用いられています。説明のために、例として物理問題とそれに伴う境界値問題（BVP）を挙げます。読者がBVPの表記法に馴染みがなくても、BVPを記述するとどのような形になるかを示すことが目的です。

(モデル問題)左端が 1 度、他の端が 0 度に保たれた正方形の金属板を長時間放置した後の熱分布は、次の境界値問題を満たします。

${\begin{aligned}&f_{xx}(x,y)+f_{yy}(x,y)=0\\&f(0,y)=1;\;f(x,0)=f(x,1)=f(1,y)=0\end{aligned}}$

ここで、

f

は未知の関数、

f xx

と

f yy は

それぞれx

と

y

に関する2番目の偏微分を表します。

ここで、定義域は $[0,1]\times[0,1]の$ 正方形です。

この問題は紙上で正確に解けるため、コンピュータは必要ありません。しかし、これは例外的なケースであり、ほとんどの境界値問題（BVP）は正確に解くことができません。唯一の可能性は、コンピュータを用いて近似解を求めることです。

コンピュータで解決する

これを実現する典型的な方法は、正方形 $[0,1]\times[0,1]$ 内で等間隔に $fを$ サンプリングする ことです。例えば、 $x$ 方向に $x$ $= 0.1、0.2、\dots、0.8、0.9で8サンプル、$ $y$ 方向に同様の座標で8サンプルを採取します。すると、正方形の(0.2,0.8)や(0.6,0.6)のような場所で64個のサンプルが得られます。コンピュータプログラムの目的は、これらの64点における $f$ の値を計算することであり、これは正方形の抽象的な関数を求めるよりも簡単と思われます。

いくつかの困難があります。例えば、正方形内の64点におけるfしか分かっていない状態では、 $f xx (0.5,0.5)$ を計算することはできません。これを克服するために、微分に関する何らかの数値近似法、例えば有限要素法や有限差分法が用いられます。ここではこれらの困難を無視し、問題の別の側面に焦点を当てます。

線形問題を解く

この問題を解くためにどの方法を選ぶにせよ、大規模な線形方程式系を解く必要があります。高校で習った線形方程式系を思い出す人もいるかもしれません。それは次のようなものです。

2a+5b=12

*

$6a-3b=-3$

$これは2つの未知数（ a$ と $b$ ）を持つ2つの方程式からなる連立方程式です。上記のBVPを上記の方法で解くと、64個の未知数を持つ64個の方程式からなる連立方程式を解く必要があります。これは現代のコンピュータにとっては難しい問題ではありませんが、サンプル数を増やすと、現代のコンピュータでさえBVPを効率的に解くことができなくなります。

領域分割

ここで、領域分割法について考えてみましょう。領域 $[0,1] \times [0,1] を$ 2 つのサブ領域 $[0,0.5] \times [0,1]$ と $[0.5,1] \times [0,1]$ に分割すると、それぞれのサブ領域にはサンプル点が半分しか含まれなくなります。そこで、それぞれのサブ領域でモデル問題のバージョンを解こうとしますが、今度は各サブ領域のサンプル点は 32 個だけです。最終的に、各サブ領域の解が与えられれば、それらを統合して $[0,1] \times [0,1]$ における元の問題の解を得ることができます。

問題の大きさ

線形システムの観点から言えば、64個の未知数を持つ64個の方程式からなる連立方程式を、32個の未知数を持つ32個の方程式からなる2つの連立方程式に分割しようとしています。これは以下の理由から明らかな利点となります。システム(*)をもう一度見てみると、6つの重要な情報があることがわかります。それは、aとbの係数（1行目は2.5、2行目は6.-3）、そして右辺（12.-3と書きます）です。一方、1個の未知数を持つ1個の方程式からなる「連立方程式」を2つ取ると、次のようになります。

$2a=12$ $-3b=-3$

このシステムには重要な情報が4つしかないことがわかります。これは、コンピュータプログラムにとって、1×1システムを2つ解く方が、1×2システムを1つ解くよりも簡単であることを意味します。1×1システムのペアは、1つの2×2システムよりも単純だからです。64×64システムと32×32システムはここでは説明できないほど大きすぎますが、類推的に、64×64システムは4160個の情報を持ち、32×32システムはそれぞれ1056個の情報を持ち、これは64×64システムの約4分の1に相当します。

領域分割アルゴリズム

残念ながら、技術的な理由により、64点のグリッド（64×64の線形方程式系）を32点のグリッド2つ（32×32の線形方程式系2つ）に分割して、64×64の方程式系の解を得ることは通常不可能です。その代わりに、実際には以下のアルゴリズムが実行されます。

64×64 システムの近似解から始めます。
64×64 システムから 2 つの 32×32 システムを作成し、近似解を改善します。
2 つの 32×32 システムを解きます。
2 つの 32×32 ソリューションを「組み合わせて」、64×64 システムのおおよそのソリューションを改善します。
解決策がまだ良くない場合は、2 から繰り返します。

このアルゴリズムが64×64基数系を解くよりも優れている点は2つあります。まず、アルゴリズムの繰り返し回数が少ない場合、2つの32×32基数系を解く方が、64×64基数系を解くよりも効率的である可能性があります。次に、2つの32×32基数系を同じコンピュータで解く必要がないため、このアルゴリズムを並列実行することで複数のコンピュータのパワーを活用できます。

実際、並列処理を使わずに1台のコンピュータで64×64システムではなく2つの32×32システムを解くのは、効率的とは言えません。しかし、3つ以上のサブドメインを使用する場合、状況は変わります。例えば、16×16の問題を4つ使用すれば、たとえ領域分割アルゴリズムを数回反復処理する必要があったとしても、これらの問題を解く方が1つの64×64問題を解くよりも効率が良くなる可能性があります。

技術的な例

ここでは、読者が偏微分方程式に精通していることを前提としています。

偏微分方程式を解きます

u_{xx}+u_{yy}=f

**

私たちは無限に有界性を課します。

領域 $R 2 を$ 2つの重なり合う部分領域 $H 1 = (-\infty, 1] \times R$ と $H 2 = [0, +\infty) \times R$ に分解します。各部分領域において、以下の形式の境界値問題（BVP）を解きます。

${\begin{aligned}u_{xx}^{(j)}+u_{yy}^{(j)}&=f\;\;{\text{ in }}H_{j}\\u^{(j)}(x_{j},y)&=g(y)\end{aligned}}$

ここで $、x 1 = 1$ 、 $x 2 = 0$ であり、もう一つの境界条件として無限大有界性をとる。上記の問題の解 $u (j)$ $をS(f, g)と表記する。S$ $は$ 双線型であることに注意する。

Schwarz アルゴリズムは次のように進行します。

偏微分方程式の近似解 $u (1) 0$ と $u (2) 0$ $をそれぞれH 1$ と $H 2$ の部分領域で求めます。kを0に初期化し $ます$ 。
$j$ $= 1, 2$ で $u (j) k + 1 = S(f, u (3 - j) k (x j))$ を計算します。
$k を$ 1 ずつ増やし、十分な精度が得られるまで 2 を繰り返します。

参照

参考文献

スミス、バリー、ビョルスタッド、ウィリアム・グロップ (1996). 『楕円型偏微分方程式のための領域分割、並列多段階法』ケンブリッジ大学出版局. ISBN 0-521-49589-X。
Toselli, Andrea; Widlund, Olof B. (2004).領域分割法 - アルゴリズムと理論. Springer Series in Computational Mathematics, Vol. 34. ISBN 978-3-540-20696-5。

外部リンク

ドメイン分割法の公式ページ