連立一次方程式を解くための高速アルゴリズム
1. 序章
考えられるすべての物理システムまたは科学的問題には、そのコアに線形代数方程式のシステムが含まれます。 たとえば、曲線をデータポイントのセットに適合させたり、コスト関数を最適化したり、電気ネットワークを分析したりするには、線形方程式を解く必要があります。
計算線形代数の基本的なタスクのいくつかは次のとおりです。
- 連立一次方程式を解く
- 正方行列の逆行列を見つける
- 行列式の計算
このような基本的なタスクを実行するためのアルゴリズムの応用入門は次のとおりです。
このチュートリアルでは、行列をより単純なレゴブロックに分解する方法を学びます。 これらの小さなレゴブロックでの操作は、元のマトリックスでの操作よりも簡単なことがよくあります。
2. 部分的なピボットによるガウスの消去法
3つの線形方程式の基本システムを考えてみましょう。
3つの未知数で。 このシステムは、次のように行列形式で記述できます。
連立一次方程式を解くための高校のアルゴリズムは、方程式に対して基本行演算を実行することで構成されます。 方程式に対して演算を実行すると、その右辺にも影響するため、すべてを追跡することは、拡大行列を使用して最も簡単に実行できます。
係数行列のエントリを最初のピボットと呼び、エントリを2番目のピボットと呼びます。 通常のガウスの消去法では、基本的な考え方は、thピボットの下の列のすべてのエントリを。に等しくすることです。
したがって、重要な要件は、ピボット要素が常にゼロ以外である必要があることです。 ピボットがゼロ以外になるように、行とを交換する必要がある場合があります。 最も一般的な方法は、最大になるようにを選択することです。 これは部分ピボットと呼ばれます。
システムの左側と右側の両方で基本演算を実行したため、結果として得られる連立方程式は、元のシステムと同等です。 と同じ解ベクトルを持っています。
は、すべての非ゼロ要素（対角線上のピボット）を含む上三角行列であることに注意してください。
擬似コードの形式で部分的にピボットするガウスの消去法アルゴリズムを以下に示します。
結果として得られる連立方程式は、逆代入によって簡単に解くことができます。
電気回路網の例の電流の解ベクトルはです。
3. LU分解
2つの行列の積として行列を書くことができると仮定します。
ここで、は下三角行列、は上三角行列です。 このような分解を使用して、連立一次方程式を解くことができます。
まず、次のようなベクトルを解きます。
そして解決する
下三角系の解法は、前方置換によって行うことができます。
上三角システムの解法は、逆代入によって行うことができます。 このようにして、因数分解を使用して連立方程式の解を見つけることができます。
1つの線形連立方程式を2つの連続する連立方程式に分割する利点は何ですか？
3.1. LU分解アルゴリズム
非特異な正方行列とします。 行列の因数分解をブロック形式で書いてみましょう。
上記の行列のブロック形式では、エントリはスカラー、行ベクトル、列ベクトル、および行列です。
上記のブロック行列方程式の左辺と右辺を比較すると、次のことがわかります。
と行列の成分を解くためにこれらの方程式を再配置すると、次のようになります。
最初の3つの方程式をすばやく評価して、行列の最初の行と列を取得できます。 次に、最後の方程式の右辺を評価できます。これにより、シューア補行列が得られます。 したがって、方程式が残ります。これは、再帰的に解くことができるサイズの小さなサブ問題です。
この直感的なアイデアに基づいて、単純なアルゴリズムを考案します。
4. QR分解
-decompositionと同様に、非常に便利な別の行列因数分解、いわゆる-decompositionがあります。
4.1. グラムシュミット過程
の基礎で作業しているとします。 から正規直交基底を構築することに関心があります。
私たちは、次元空間のいくつかの基礎をすでに知っていると仮定します。 私たちの目標は、この情報を使用して直交基底を構築することです。
直交基底要素を1つずつ作成します。 最初は正規性について心配していないので、最初の直交基底要素に条件がないため、選択しても害はありません。
、、は元の基準で表示されるため、注意してください。 から始めて、2番目の基底ベクトルは最初の基底ベクトルに直交する必要があります：。 と直交ベクトルの適切なスカラー乗法として書くことが可能であると仮定します。 設定：
ここで、は決定されるスカラーです。
直交性条件は次のようになります。
その結果：
したがって：
次に、以下を構築します。
から最初の2つの直交基底要素の倍数を引くことによって。 との両方に直交したい。 これにより、2つの方程式が得られます。
それゆえ
このようにして、一般的なグラムシュミットの公式を確立することができます
4.2. グラムシュミットプロセスの変更
基本的なグラムシュミットアルゴリズムを手にした状態で、実用的および理論的な利点の両方を備えた再定式化を見てみましょう。 これは、基底から直接正規直交基底ベクトルを構築するために使用できます。
まず、基本的なグラムシュミット公式の各直交基底ベクトルを正規化されたバージョンに置き換えます。
ここで、元の基底ベクトルは、下三角システムを介して、直交基底ベクトルで表すこともできます。
係数は、これらの式から直接計算できます。 の正規直交基底ベクトルを使用した方程式の内積をとると、次のようになります。
それゆえ：
一方、th方程式の内積をそれ自体と一緒に取ると、次のようになります。
したがって、次のように計算することで取得できます。
これらの係数がすべて揃ったら、下三角システムは前方置換を使用して簡単に解くことができます。
4.3. 直交行列
列が次元ユークリッド空間の直交基底を形成する行列は、直交行列と呼ばれます。 直交行列には、幾何学や物理学から結晶学、量子力学、偏微分方程式に至るまで、多数のアプリケーションがあります。 3次元空間における物体の回転運動は、直交行列によって記述されます。
数学的には、正方行列は、次の条件を満たす場合、直交と呼ばれます。
行列の直交性は、行列を簡単に反転できることを意味します。
4.4. QR分解
の基底とし、グラムシュミット過程から生じる対応する正規直交基底とします。 列ベクトルの両方のセットを組み立てて、非特異行列を形成します。
の正規直交基底を形成するため、は直交行列です。 行列の乗算式を考慮すると、グラムシュミット方程式を行列形式に再キャストできます。
修正されたグラムシュミットプロセスを簡単に実装できます。
4.5. QR分解を使用した線形システムの解法
行列の分解がわかれば、線形連立方程式を解くのはかなり効率的です。 私たちが持っているのは：
行列は上三角行列であるため、システムは逆置換アルゴリズムを使用して非常に簡単に解くことができます。
5. 結論
この記事では、変数を削除して線形方程式を解く高校の方法を確認しました。 行列の因数分解は、より複雑なアルゴリズムの構成要素であることを学びました。
今日、サイズの正方行列を含むシステムを解くための因数分解の実装は、 MATLAB 、 Eigen 、 LAPACK 、 Linpack、 NAG、など。
