シンプルで実用的！ 3人のドイツ人によって考案された線形反復法は、時代を超えた

今年12月26日は、ドイツの数学者ガウスが史上初の線形反復法を発明してから200周年にあたります。最近公開された記事「線形方程式を反復的に解く方法」では、基本的な概念から始めて、線形方程式を解くための反復法の準備知識と具体的なプロセスを明らかにしました。今回は、歴史上最も有名かつ最も単純で実用的な 2 つの 1 次定常反復法、ヤコビ反復法とガウス・ザイデル反復法の基本的な考え方と収束について説明します。

著者：ディン・ジウ（南ミシシッピ大学数学教授）

Fanpu の前回の記事「線形方程式のシステムを繰り返し解くにはどうすればよいでしょうか?」これを一般の完全距離空間に適用可能な収縮写像定理と結び付けるために、反復によって線形方程式を解くための単純な収束十分な方法のみが与えられている。

すべての道はローマに通じる

幸いなことに、他の基準も利用可能です。線分の長さという通常の概念を直接一般化して、n次元ユークリッド空間

固有値とスペクトル半径

しかし、収束には私たちが探求すべき必要十分条件が存在します。この条件では、行列のノルムではなく、行列のスペクトルが使用されます。スペクトルは、そのノルムに依存しない行列の固有の特性を与えます。正方行列のスペクトルは、そのすべての固有値からなる複素数の有限集合です。 n 次の正方行列 M が与えられたとき、複素行列 M - λI が逆行列でない場合、つまり、Mx = λx となる複素非ゼロ列ベクトル x が存在する場合、複素数 λ を M の固有値と呼びます。このxは、固有値λに対応するMの固有ベクトルと呼ばれます。行列が特異行列となるのは、その行列式がゼロの場合のみであると述べました。したがって、λ が M の固有値となるのは、det(M - λI) = 0 の場合のみであり、ここで記号 det は行列式を表します。この式の左辺のλを変数とみなすと、行列式の定義によれば、det(M - λI)の展開結果はλに関するn次多項式となるので、n次正方行列Mは最大でn個の異なる固有値を持つ。 Mのすべての固有値の最大絶対値をMのスペクトル半径と呼び、ρ(M)と表記します。

線形反復を研究する主な目的は、係数行列 A が特異でない線形方程式系 Ax = b を数値的に解くことです。

逆に、ρ(M) < 1 の場合、ρ(M) + ε < 1 となる十分に小さい正の数 ε が存在します。この一見単純な事実は、実数の基本的な性質です。一方、M の任意の固有値 λ と任意のノルム ||•|| に対して、 Rn上で、xをλに対応する固有ベクトルとします。不等式 ||M|| より、 ||×|| ≥ ||Mx|| = ||λx|| = |λ| ||×||そして x ≠ 0 の場合、先ほど得た不等式の両辺を正の数 ||x|| で割ることができ、不等式 ||M|| が得られることがわかります。 ≥ |λ| なので、行列 M のスペクトル半径 ρ(M) は値 ||M|| の下限であることがわかります。 M 内のすべてのベクトルノルムによって誘導される行列ノルムの下限です。実際、この下限は、すべてのノルム値に対応する実数セットの「最小値」です。||M||固定行列 M の、つまりこのセットのすべての下限値の中での「最大下限値」です。 「上限と下限」の概念は、微積分学における最も基本的で重要な概念です。一度本当にマスターすれば、極限理論とそれに続く連続性、微分、積分、級数などの概念も簡単に習得できるようになります。

ヤコビ反復法とガウスザイデル反復法

ここで、線形システム Ax = b を解くためのヤコビ法とガウス・ザイデル法に焦点を当てることができます。ここで、A は n 次の可逆行列です。ドイツ発祥のこの2つの古典的な反復法は、行列分解A = N - PにおけるNとPの特別な選択に基づいています。反復形式は次のように記述できます。

反復点成分計算プロセスにおけるヤコビ法とガウス・ザイデル法の重要な違いを比較してみましょう。ヤコビ反復法におけるn成分の反復式から、k-1番目の反復ベクトルのすべての成分が計算された後、k番目の反復ベクトルの成分が1つずつ計算されることがわかります。つまり、k-1 回目の反復で得られたすべてのコンポーネントは、k 回目の反復のすべてのコンポーネントを計算するために使用されます。ガウス・ザイデル反復法の場合、k 番目の反復ベクトルの i 番目の成分を計算する必要があるときはいつでも、計算済みの k-1 番目の反復ベクトルの i+1 から n 番目の成分だけでなく、現在の反復で得られた k 番目の反復ベクトルの 1 から i-1 番目の成分も計算する必要があります。言い換えれば、ガウス・ザイデル法はヤコビ法よりも「成功を強く望んでいる」ため、現在の反復ステップでキャプチャされたばかりの反復ポイント コンポーネントを、前の反復ステップで「キャプチャ」された同じ下付き文字コンポーネントと置き換えて「戦闘に入る」ように命令します。これは、ガウスとザイドルがヤコビよりも「軍隊の利用」に優れており、士気を無駄にするつもりがなかったことを示しています。

収束条件

当然、ヤコビ反復法もガウス・ザイデル反復法も、行列 A に関する特定の追加仮定がなければ収束を保証することはできません。では、「A の対角要素はゼロにはならない」という前提条件が満たされている場合、それらの収束を保証するための十分な条件は何でしょうか。

ここで、ヤコビ反復法の収束を保証するための厳密な対角優位性の要件は、既約な弱対角優位性に変更できます。つまり、上記のすべての厳密な不等式は一般的な不等式「≥」に置き換えられ、少なくとも 1 つの不等式は厳密に有効ですが、行列の既約性という追加条件が追加されます。正方行列の行と列を同じように並べ替えることができる場合（単位行列も順列行列であるため、並べ替えないことも「並べ替え」と見なされます）、結果は 2×2 ブロック上三角行列になります。つまり、行列の左下隅に少なくとも 1×1 ゼロ行列がある場合、行列は既約であると言い、そうでない場合は既約ではないと言います。

A が厳密に対角優勢な行列である場合、ガウス-ザイデル反復行列の∞ノルムはヤコビ反復行列の∞ノルム以下になります。このノルムが小さいほど、通常は収束速度が速くなります。したがって、収束速度の点では、前者の方法は後者の方法に劣りません。

この記事の最後の数学的な一皿として、ガウス・ザイデル法のもう一つのユニークな収束命題を紹介します。

線形システム Ax = b の係数行列 A が対称正定値である場合、ガウス-ザイデル反復法は収束します。

終わり

200 年前にドイツの数学者によって灯された線形反復法のたいまつは、100 年後に海を渡り、テクノロジーが発展しコンピューターが誕生したアメリカ大陸に届けられました。反復効率を最適化するために、古典的なガウス・ザイデル法から始めて、1950 年に、アメリカの数学者でコンピューター科学者の David M. Young Jr. (1923-2008、「Fanpu」で別途紹介) とアメリカの物理学者でコンピューター科学者の Stanley Phillips Frankel (1919-1978) が、ある種のアフィン結合に対する緩和係数 ω をほぼ同時に導入し、「逐次過剰緩和法 (SOR)」を生み出しました。前者はハーバード大学での博士論文「楕円型偏差分方程式を解く反復法」で SOR 法を提案しました。後者は、アメリカ数学会誌（10年後に計算数学に改名）に「偏微分方程式の反復処理の収束率」という論文を発表し、その中で彼が設計し「外挿リープマン法」と呼んだSOR法の包括的な分析を行った。 SOR 法を提案したこれら 2 つの先駆的な研究は、どちらも科学や工学で数多く登場する偏微分方程式に関連しています。これらの連続方程式を離散化して得られる大規模な疎線形方程式を電子コンピュータを使用して解く場合、反復法が第一の選択肢となります。 SOR方式が誕生した時代です。

緩和係数 ω が 1 の値を取る場合、SOR 法はガウス・ザイデル法に簡約されます。 2 つの古典的な反復法を理解することで、線形反復法の収束基準の基本的な考え方をすでに知っているため、この方法については詳しく説明せず、ここでこの記事を終了します。要約すると、19 世紀の 3 人のドイツの数学者の発明が、大規模で疎な構造化された線形方程式系の反復解法に関する現代の研究の波の源泉となっています。

2023年11月19日日曜日、米国ハッティズバーグ、サマーヒルズにて執筆

この記事は科学普及中国星空プロジェクトの支援を受けています

制作：中国科学技術協会科学普及部

制作：中国科学技術出版有限公司、北京中科星河文化メディア有限公司

特別なヒント

1. 「Fanpu」WeChatパブリックアカウントのメニューの下部にある「特集コラム」に移動して、さまざまなトピックに関する人気の科学記事シリーズを読んでください。

2. 「Fanpu」では月別に記事を検索する機能を提供しています。公式アカウントをフォローし、「1903」などの4桁の年+月を返信すると、2019年3月の記事インデックスなどが表示されます。

著作権に関する声明:個人がこの記事を転送することは歓迎しますが、いかなる形式のメディアや組織も許可なくこの記事を転載または抜粋することは許可されていません。転載許可については、「Fanpu」WeChatパブリックアカウントの舞台裏までお問い合わせください。