ガウス・ジョーダンの消去について詳しく解説

数学では、ガウスジョルダン消去法(ガウスピボットとも呼ばれ、カールフリードリヒガウスとヴィルヘルムヨルダンにちなんで名付けられました) は、線形方程式系の解を決定したり、行列の階数を決定したり、行列の階数を計算したりするための線形代数のアルゴリズムです。可逆正方行列の逆行列。行列にガウス消去法を適用すると、その縮小された階層形式が得られます。

歴史

この方法は数学者カール・フリードリッヒ・ガウスにちなんで名付けられましたが、少なくとも^西暦1世紀から中国人には知られていました。これは、重要な中国の書籍『九章算書』または数学的芸術に関する九章で参照されており、その第 8 章を構成するもので、「方成」(長方形のレイアウト) というタイトルで記載されています。この方法は 18 の演習を使用して説明されます。劉輝は、263 年付けの非常に詳細な注釈の中で、その著者は紀元前2^世紀の中国皇帝の宰相、張宗であるとしています。

数値解析

ガウス消去法の漸近アルゴリズムの複雑さは^O ( n3 ) (ランダウ表記) であるため、行列が n*n 型の場合、必要な命令の数はⁿ³に比例します。このアルゴリズムは、数千の未知数と方程式を含むシステムのコンピューター上で使用できます。ただし、 O ( n2.807 ) にある Strassen のアルゴリズムは^、漸近的なアルゴリズムの複雑さが優れています。さらに、ガウス消去法は数値的に不安定であり、計算中に発生する丸め誤差が蓄積され、計算が正確な算術で行われない場合、求められる結果は解からかけ離れたものになる可能性があります。しかし、ガウス消去法は、計算が本質的に有限体のように正確である場における連立方程式にとっては良い方法です。

Gauss-Jordan アルゴリズムを使用した正方行列の逆行列の計算

n次の可逆正方行列A を反転することは、1 から n までの範囲の i についてn 個のシステム Af _i = e _{i を}解くことになります。これを行うには、行列Aを単位行列I _nで囲んで、 n行、2 n列のテーブルを作成します。

したがって、形式 (n, n) の行列 A=(a _ij ) を反転するには、次の拡張行列を使用します。

$$ {\Big(A\;\Big|\,I_{n}\Big) = \left(\begin{array}{ccc|ccc} a_{1,1} & \cdots & a_{1,n} & 1 & \cdots & 0 \\ \vdots & \ddots & \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,n} & \ 0 & \cdots & 1 \\ \end{array}\right)} $$

ガウス・ジョルダン変換は、このシステムを、左側のブロックが単位となる等価システムに変換することで構成されます。つまり、行列( A | I )を( I | A ^{− 1 の}形式になるように変更する必要があります) )アルゴリズムのプロパティを使用します。以下に注意してください:

$$ {l_i^k} $$
反復 k における行列 A の行 i
$$ {a_{ij}^k} $$
反復 k における行列 A のスカラー a _ij

ガウスジョーダンアルゴリズムは次のとおりです。

kの範囲は1からnまで

線があれば

$$ {i\geq k} $$

のような

$$ {a_{ik}^{k-1}\not=0} $$

この行iと行k を交換します。

$$ {l_i \leftrightarrow l_k} $$

$$ {l_k^k \leftarrow \frac{1}{a_{kk}^{k-1}} l_k^{k-1}} $$

私は1からnまで進み、

$$ {i \neq k} $$

$$ {l_i^k \leftarrow l_i^{k-1}-a_{ik}^{k-1} \times l_k^{k}} $$

それ以外の場合、 A は可逆ではないので、あきらめます (行列のランクがk − 1であることがここでわかります)。

アルゴリズムのステップkの後、列k には、1 つを除くすべてのゼロ係数が含まれます: 1 に等しい対角線の係数です。

変形:係数を探すこともできます

$$ {a_{ik}^{k-1}, i\geq k} $$

行を交換する前の最大値 (絶対値)。これにより、アルゴリズムの安定性が向上します。同様に、列を交換してより大きな係数を見つけることもできますが、これらの順列を追跡する必要があります。

逆行列Aを使用して、 Aの形式の方程式を解くことができます。 X = B 、ここでBは固定ベクトル、 X は未知のベクトルです。しかし、別のプレゼンテーションもあります。

ガウス・ジョーダンアルゴリズムを使用して連立一次方程式を解く

連立方程式Aを解きたいと考えています。 X = B 、ここでBは固定ベクトル、 X は未知のベクトルです。行列AをベクトルBで囲んで、 n行、 n + 1列のテーブルを作成します。上記と同じアルゴリズムを使用します。最後に単位行列を取得し、最後の列で目的のベクトルX を取得します。

変形: 前のアルゴリズムでは、 iに対してk + 1からnまでの内部ループのみを実行すると、上三角行列が得られます。残っているのは、「戻って」 Xの係数の値を見つけることだけです。

例

次の方程式系を考えてみましょう。

対応する行列を確立し、Gauss-Jordan の最初のステップを適用します。ピボットは 1 です。

最初の行の倍数を他の 2 行に加算してゼロを取得します (それぞれ

$$ {-3\times l_1} $$

そして

$$ {-2\times l_1} $$

);新しいピボットは 5 になります。

2 行目は 1/5 倍されます。

この 2 行目を 3 行目と最初の行に追加すると、新しいピボットは -7 になります。

3 行目を -7 で割ります。

3 行目は、1 行目と 2 行目の係数を削除するために使用します。次に、一方の側に恒等行列、もう一方の側に変数の値を持つ縮小階層形式が存在します。

システムの解決策は次のとおりです。

決定要因

このアルゴリズムでは、行列の行列式を計算することもできます。上記のアルゴリズムでは、行列式は次の積です。