ガウス消去法

数学において、ガウス消去法（行簡約法とも呼ばれる）は、連立一次方程式を解くためのアルゴリズムである。これは、対応する係数行列に対して一連の行ごとの操作を行うことで構成される。この方法は、行列のランク、正方行列の行列式、および可逆行列の逆行列を計算するためにも使用できる。この方法は、カール・フリードリヒ・ガウス（1777年～1855年）にちなんで名付けられた。

行列の行縮小を行うには、一連の基本行操作を用いて行列を修正し、行列の左下隅が可能な限りゼロで埋め尽くされるようにします。基本行操作には次の3種類があります。

2つの行を入れ替えて、
行にゼロ以外の数を掛け、
ある行の倍数を別の行に加える。

これらの操作を用いることで、行列は常に簡約行階段形に変換できます。つまり、ゼロでない行はすべてゼロの行の上にあり、ゼロでない行の左端のゼロでない要素は 1 であり、これらの先頭の 1 を含む列の他の要素はすべて 0 であり、ゼロでない行の先頭の 1 は前の行の先頭の 1 の右側にあります。この最終形式は一意であり、つまり、使用する行操作の順序に依存しません。たとえば、次の行操作の順序 (最初のステップと 3 番目のステップで異なる行に対して 2 つの基本操作が実行される) では、3 番目の行列と 4 番目の行列が行階段形であり、最終行列が一意の簡約行階段形になります。 ${\begin{bmatrix}1&3&1&9\\1&1&-1&1\\3&11&5&35\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&2&2&8\end{bmatrix}}\to {\begin{bmatrix}1&3&1&9\\0&-2&-2&-8\\0&0&0&0\end{bmatrix}}\to {\begin{bmatrix}1&0&-2&-3\\0&1&1&4\\0&0&0&0\end{bmatrix}}$

行操作を使用して行列を簡約行階段形に変換することは、ガウス・ジョルダン消去法。この場合、ガウス消去上三角（未簡約）の行階段形になるまでの過程を指します。計算上の理由から、連立一次方程式を解く際には、行列が完全に簡約化される前に行操作を停止することが望ましい場合があります。

アルゴリズムの定義と例

行簡約化のプロセスは、基本的な行操作を利用し、2つの部分に分けられます。最初の部分（前方消去と呼ばれることもあります）は、与えられたシステムを行階段形に変換し、そこから解がない、唯一の解がある、または無限に多くの解があるかどうかを判断します。2番目の部分（後方代入と呼ばれることもあります）は、解が見つかるまで行操作を使い続けます。つまり、行列を簡約行階段形に変換します。

アルゴリズムを分析する上で非常に役立つもう一つの視点は、行簡約によって元の行列の行列分解が得られるという点です。基本行操作は、元の行列の左側に基本行列を乗算することと見なすことができます。

あるいは、1行を簡約化する一連の基本演算は、フロベニウス行列による乗算とみなすことができる。この場合、アルゴリズムの最初の部分ではLU分解を計算し、2番目の部分では元の行列を、一意に決定される可逆行列と一意に決定される簡約行階段行列の積として書き出す。

行操作

行列の行に対して実行できる基本的な行操作には、次の3種類があります。

2列を入れ替える。
行にゼロ以外のスカラーを掛ける。
ある行のスカラー倍数を別の行に加算する。

行列が連立一次方程式に関連付けられている場合、これらの操作は解集合を変更しません。したがって、連立一次方程式を解くことが目的であれば、これらの行操作を使用することで問題が解きやすくなる可能性があります。

梯形陣形

行列の各行について、その行がゼロのみで構成されていない場合、最も左にあるゼロ以外の要素をその行の先頭要素（またはピボット）と呼びます。2 つの先頭要素が同じ列にある場合、タイプ 3の行操作を使用して、それらの要素の 1 つをゼロにすることができます。次に、行交換操作を使用することで、すべてのゼロ以外の行について、先頭要素が上の行の先頭要素の右側に来るように行を常に並べ替えることができます。この場合、行列は行階段形であると言われます。この形式では、行列の左下部分はゼロのみで構成され、すべてのゼロ行はゼロ以外の行の下にあります。「階段形」という言葉がここで使用されているのは、行がそのサイズによって大まかにランク付けされ、最も大きい行が上、最も小さい行が下にあると考えることができるためです。

例えば、次の行列は行階段形であり、先頭の要素は赤色で示されています。 ${\begin{bmatrix}0&\color {red}{\mathbf {2} }&1&-1\\0&0&\color {red}{\mathbf {3} }&1\\0&0&0&0\end{bmatrix}}.$

これは階段状配列です。なぜなら、0行目が一番下にあり、2行目（3列目）の先頭のエントリが、1行目（2列目）の先頭のエントリの右側にあるからです。

行列は、すべての先頭要素が 1 に等しく (これはタイプ 2 の基本行操作を使用することで実現できます)、かつ先頭要素を含むすべての列において、その列の他のすべての要素がゼロである場合 (これはタイプ 3 の基本行操作を使用することで実現できます)、簡約行階段形であると言われます。

アルゴリズムの例

次の連立一次方程式の解の集合を見つけて記述することが目標だとします。 ${\begin{alignedat}{4}2x&{}+{}&y&{}-{}&z&{}={}&8&\qquad (L_{1})\\-3x&{}-{}&y&{}+{}&2z&{}={}&-11&\qquad (L_{2})\\-2x&{}+{}&y&{}+{}&2z&{}={}&-3&\qquad (L_{3})\end{alignedat}}$

下の表は、連立方程式とその関連する拡大行列に同時に適用される行簡約処理です。実際には、連立方程式を方程式で扱うことは通常なく、コンピュータによる処理に適した拡大行列を使用します。行簡約の手順は次のように要約できます。L 1 より下のすべての方程式から x を消去し $、$ 次に $L$ 2 より下のすべての方程式から y を消去します $。$ $これ$ により $、連立方程式は$ 三角行列になります。その後、逆代入を使用して、各未知数を解くことができます $。$

2 列目には、実行された行操作が示されています。最初のステップでは、 $L$ $2$ に $⁠$ $3$ $/$ $2$ $⁠$ $L$ $1$ を加えることで、 $x が$ $L 2 から削除されます。次に、L$ $3$ にL $1$ $を$ 加える $こと$ $で$ 、 $x が$ $L$ $3$ から削除されます。これらの行操作は、表では次のようにラベル付けされています。 ${\begin{aligned}L_{2}+{\tfrac {3}{2}}L_{1}&\to L_{2},\\L_{3}+L_{1}&\to L_{3}.\end{aligned}}$

$3行目からy$ も消去すると、結果として三角形式の線形方程式系が得られ、アルゴリズムの最初の部分が完了します。計算の観点からは、変数を逆順に解く方が速く、これは後退代入と呼ばれるプロセスです。解は $z = -1$ 、 $y = 3$ 、 $x = 2$ であることがわかります。特に、この場合、元の方程式系には一意の解が存在します。

行列が行階段形になった時点で停止するのではなく、表に示されているように、行列が簡約行階段形になるまで続けることもできます。行列が簡約されるまで行を簡約していくプロセスは、階段形になった後に停止する方法と区別するために、ガウス・ジョルダン消去法と呼ばれることがあります。

歴史

ガウス消去法は、証明なしではあるものの、中国の数学書『九章算術』第八章「長方形配列」に登場します。その使用法は、2～5個の方程式を含む18の問題で示されています。この書名で最初に言及されたのは西暦179年ですが、その一部は紀元前150年頃に書かれていました。^[¹^]^[²^]^[³^] 3世紀には劉徽によって注釈が付けられました。

^{Grcar [ 4 ]}によると、消去法による線形方程式の解法は、古代からユーラシアのいくつかの文化で独自に発明され、ヨーロッパでは後期ルネサンス（1550 年代）までに手順の具体的な例が発表された。当時すでにこの手順は数学者にとって基本的なものであり、専門家への説明は不要と考えられていた可能性が高く、そのため、当時までにヨーロッパの少なくともいくつかの場所で実践されていたという事実を除いて、その詳細な歴史を知ることはできないかもしれない。

ヨーロッパにおけるこの方法は、アイザック・ニュートンのノートに由来する。^{[ 4 ]}^{[ 5 ]} 1669年から1670年にかけて、ニュートンは、自分が知っている代数学の本には連立方程式を解くためのレッスンが欠けていると書き、それを補った。ケンブリッジ大学は、ニュートンが学問の道を去ったずっと後の1707年に、最終的にそのノートを『Arithmetica Universalis』として出版した。このノートは広く模倣され、18世紀末までに（現在ガウス消去法と呼ばれる）方法は代数学の教科書の標準的なレッスンとなった。カール・フリードリヒ・ガウスは1810年に対称消去法の記法を考案し、19世紀にはプロの手計算者が最小二乗問題の通常の方程式を解くために採用した。^{[ 6 ]}高校で教えられているアルゴリズムは、この分野の歴史に関する混乱の結果として、1950年代になって初めてガウスにちなんで名付けられた。^{[ 7 ]}

ガウス消去法という用語を、行列が階段行列になるまでの手順のみを指すために使用し、ガウス・ジョルダン消去法という用語を、簡約階段行列で終わる手順を指すために使用する著者もいる。この名前は、 1888年にヴィルヘルム・ジョルダンによって記述されたガウス消去法の変形であるため使用されている。しかし、この方法は、同じ年に発表されたクラセンの論文にも登場する。ジョルダンとクラセンはおそらく独立してガウス・ジョルダン消去法を発見した。^{[ 8 ]}

アプリケーション

歴史的に見ると、行簡約法の最初の応用例は連立一次方程式の解法です。以下に、このアルゴリズムのその他の重要な応用例をいくつか示します。

行列式の計算

ガウス消去法によって正方行列の行列式を計算できる仕組みを説明するには、基本行操作が行列式をどのように変化させるかを思い出す必要があります。

2行を入れ替えると、行列式は-1倍になる。
行にゼロ以外のスカラーを掛けると、行列式にも同じスカラーが掛けられます。
ある行に別の行のスカラー倍数を加えても、行列式は変わりません。

正方行列 $A$ にガウス消去法を適用して行階段行列 $B$ が得られる場合、上記の規則を用いて行列式に掛けられたスカラーの積を $dとする。すると、$ $Aの行列式は、$ $B$ の対角要素の積を $d$ で割った商となる。 $\det(A)={\frac {\prod \operatorname {diag} (B)}{d}}.$

計算上、 $n \times n$ 行列の場合、この方法は $O(n 3)$ 回の算術演算しか必要としないが、行列式のライプニッツ公式を使用すると、 $(n\,n!)$ 演算回数は、（式の被加数と各被加数での乗算回数の積）であり、再帰的ラプラス展開では、部分行列式を記憶して一度だけ計算する場合、 $O(n 2 n)$ の演算が必要となります（線形結合の演算回数と、列によって決まる計算対象の部分行列式の数の積）。最も高速なコンピュータでも、 $n$ が20 を超えると、これら 2 つの方法は非現実的、またはほぼ非現実的になります。

行列の逆行列を求める

ガウス消去法の変形であるガウス・ジョルダン消去法は、存在する場合、行列の逆行列を求めるために使用できます。A $が$ $n \times n$ の正方行列である場合、存在する場合は行簡約を使用してその逆行列を計算できます。まず、 $n \times n の$ 単位行列を $A$ の右側に追加して、 $n \times 2 n の$ ブロック行列 $[A | I]$ を形成します。次に、基本行操作を適用して、この $n \times 2 n$ 行列の簡約階段形を求めます。行列 $Aは、単位行列$ $I$ に簡約できる場合に限り可逆です。この場合、最終的な行列の右ブロックは $A -1です。アルゴリズムが左ブロックを$ $I$ に簡約できない場合、 $A$ は可逆ではありません。

例えば、次の行列を考えてみましょう。 $A={\begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix}}.$

この行列の逆行列を求めるには、次の行列に単位行列を追加し、行簡約化して3 × 6行列にする。 $[A|I]=\left[{\begin{array}{ccc|ccc}2&-1&0&1&0&0\\-1&2&-1&0&1&0\\0&-1&2&0&0&1\end{array}}\right].$

行操作を実行することで、この拡大行列の簡約行階段形が次のようになることを確認できます。 $\left[{\begin{array}{rrr|rrr}1&0&0&{\frac {3}{4}}&{\frac {1}{2}}&{\frac {1}{4}}\\0&1&0&{\frac {1}{2}}&1&{\frac {1}{2}}\\0&0&1&{\frac {1}{4}}&{\frac {1}{2}}&{\frac {3}{4}}\end{array}}\right]=:[I|B].$

各行の操作は、基本行列による左積と考えることができます。右側を見ると、これらの基本行列の積は $B で$ あることがわかります( $B = BI$ なので)。一方、左側を見ると、これらの行列の積を $A$ に左から乗算すると単位行列が得られることがわかります。つまり、 $BA = I$ です。したがって、 $B = A -1$ となり、これが求める逆行列です。この逆行列を求める手順は、任意のサイズの正方行列に適用できます。

ランクと基数の計算

$ガウス消去法は、任意のm \times n$ 行列 $A$ に適用できます。このようにして、例えば、いくつかの 6 × 9 行列を、次のような行階段形を持つ行列に変換できます。 $T={\begin{bmatrix}a&*&*&*&*&*&*&*&*\\0&0&b&*&*&*&*&*&*\\0&0&0&c&*&*&*&*&*\\0&0&0&0&0&0&d&*&*\\0&0&0&0&0&0&0&0&e\\0&0&0&0&0&0&0&0&0\end{bmatrix}},$ ここで、星印は任意のエントリであり、 $a 、 b 、 c 、 d 、 e$ はゼロ以外のエントリです。この階段行列 $Tには、$ $A$ に関する豊富な情報が含まれています。Tには 5 つのゼロ以外の行があるため、 $A$ のランクは 5 です $。A$ の列によって張られるベクトル空間は $、$ その列 1、3、4、7、9 ( $T$ の $a$ $、$ $b$ $、$ $c$ $、$ $d$ $、$ $e$ を含む列) からなる基底を持ち、星印は、 $A$ の他の列が基底列の線形結合としてどのように表されるかを示しています。

これらはすべて、特定の行階段形式である簡約行階段形式にも当てはまります。

計算効率

行簡約を実行するために必要な算術演算の数は、アルゴリズムの計算効率を測定する方法の 1 つです。たとえば、 $n 個$ の未知数に対する $n$ 個の方程式のシステムを、行列が階段形になるまで行操作を実行し、その後各未知数を逆順に解くことで解くには、 $n$ $($ $n$ $+ 1)/2 回$ の除算、 $(2$ $n$ $3$ $+ 3$ $n$ $2$ $- 5$ $n$ $)/6 回の$ 乗算、および $(2$ $n$ $3$ $+ 3$ $n$ $2$ $- 5$ $n$ $)/6 回$ の減算^[⁹^]が必要で、合計で約 $2$ $n$ $3$ $/3 回$ の演算が必要です。したがって、算術的複雑度(時間的複雑度、各算術演算は入力のサイズに関係なく 1 単位の時間を要する) は $O($ $n$ $3$ $)$ です。

この複雑さは、各算術演算にかかる時間がほぼ一定の場合、全体の計算に必要な時間の良い尺度となります。これは、係数が浮動小数点数で表現されている場合、または係数が有限体に属している場合に該当します。係数が整数または正確に表現された有理数である場合、中間エントリは指数関数的に大きくなる可能性があるため、ビット複雑度は指数関数的になります。^{[ 10 ]} ただし、Bareiss アルゴリズムは、中間エントリのこの指数関数的増加を回避する Gaussian 消去法の変種です。同じ算術複雑度 $O(n3)$ $で、ビット複雑度はO(n5)$ であり $、$ したがって、強力な多項式時間複雑度 $を$ 持ちます。

ガウス消去法とその派生法は、数千の方程式と未知数を含む連立方程式に対してコンピュータ上で使用できます。しかし、数百万の方程式を含む連立方程式では計算コストが膨大になります。このような大規模な連立方程式は、一般的に反復法を用いて解かれます。係数が規則的なパターンに従う連立方程式には、特定の解法が存在します（連立一次方程式を参照）。

ベライスアルゴリズム

ガウス消去法の最初の強力な多項式時間アルゴリズムは、 1967年にジャック・エドモンズによって発表されました。 ^{[ 11 ]}^{： 37}独立して、ほぼ同時に、エルヴィン・バライスは、ガウス消去法の除算なしの変種に適用される次の指摘に基づく別のアルゴリズムを発見しました。

標準的なガウス消去法では、各行からを減算します。 $R_{i}$ ピボット行の下 $R_{k}$ 倍数 $R_{k}$ による $r_{i,k}/r_{k,k},$ どこ $r_{i,k}$ そして $r_{k,k}$ ピボット列のエントリは $R_{i}$ そして $R_{k},$ それぞれ。

代わりに、ベライスのバリアントは、 $R_{i}$ と ${\textstyle {\frac {r_{k,k}R_{i}-r_{i,k}R_{k}}{r_{k-1,k-1}}}.}$ これにより、標準的なガウス消去法と同じゼロ要素を持つ行階段形が生成されます。

ベライス氏の主な指摘は、この変種によって生成される各行列要素は、元の行列の小行列の行列式であるということである。

特に、整数エントリから始めると、アルゴリズムで発生する除算は整数になる正確な除算になります。したがって、すべての中間エントリと最終エントリは整数です。さらに、アダマールの不等式は中間エントリと最終エントリの絶対値の上限を提供し、したがってビット複雑度は ${\tilde {O}}(n^{5}),$ ソフトO表記法を使用します。

さらに、最終エントリのサイズの上限がわかっているため、複雑さ ${\tilde {O}}(n^{4})$ モジュラ計算に続いて中国剰余演算またはヘンゼルリフティングを行うことで得られる。

その結果として、以下の問題は同じビット複雑度で強力な多項式時間で解くことができる。^{[ 11 ]}^{： 40}

与えられたm個の有理ベクトルが線形独立であるかどうかをテストする
有理行列の行列式の計算
有理方程式系Ax = bの解を計算する
非特異有理行列の逆行列を計算する
有理行列のランクを計算する

数値不安定性

考えられる問題の一つは、非常に小さな数で割る可能性によって引き起こされる数値的不安定性です。たとえば、行の先頭の係数がゼロに非常に近い場合、行列を行簡約するには、その数で割る必要があります。これは、ゼロに近い数に存在していた誤差が増幅されることを意味します。ガウス消去法は、対角優位行列または正定値行列に対して数値的に安定しています。一般的な行列の場合、ガウス消去法は、部分ピボットを使用する場合、通常は安定していると考えられていますが、安定している行列でも不安定になる例があります。^{[ 12 ]}^{[ 13 ]}

一般化

ガウス消去法は、実数だけでなく、あらゆる体上で実行できる。

ブッフベルガーのアルゴリズムは、ガウス消去法を多項式方程式系に一般化したものです。この一般化は、単項式の順序という概念に大きく依存しています。変数の順序の選択は、ガウス消去法において既に暗黙のうちに行われており、ピボット位置を選択する際に左から右へ作業を進めるという形で現れます。

2 階を超えるテンソルのランクを計算することはNP 困難です。^{[ 14 ]}したがって、 $P \neq NP$ の場合、高階テンソル(行列は2 階テンソルの配列表現です) に対してガウス消去法の多項式時間類似法は存在しません。

擬似コード

前述のように、ガウス消去法は、与えられた $m \times n$ 行列 $A を$ 行階段形の行列に変換します。

以下の擬似コードでは、は、1 から始まるインデックスを持つ、行列 $Aの$ $i$ 行 $j$ 列目の要素A[i, j]を表します。変換はインプレースで実行されるため、元の行列は失われ、最終的に行階段形に置き換えられます。

h := 1 /*ピボット行の初期化*/ k := 1 /*ピボット列の初期化*/ h ≤ mかつk ≤ nの場合： /* k番目のピボットを見つける： */ i_max := argmax (i = h ... m, abs(A[i, k])) if A[i_max, k] = 0: /*この列にピボットがないため、次の列に進みます*/ k := k + 1 それ以外の場合： 行を交換する（h、i_max） /*ピボットより下のすべての行に対して実行: */ for i = h + 1 ... m: f := A[i, k] / A[h, k] /*ピボット列の下部をゼロで埋めます。 */ A[i, k] := 0 /*現在の行の残りのすべての要素に対して実行します。 */ for j = k + 1 ... n: A[i, j] := A[i, j] - A[h, j] * f /*ピボット行とピボット列を増やす*/ h := h + 1 k := k + 1

このアルゴリズムは、先に説明したアルゴリズムとは若干異なり、絶対値が最大のピボットを選択します。ピボット位置で行列の要素がゼロの場合、このような部分的なピボット選択が必要になることがあります。いずれにしても、浮動小数点を使用して数値を表現する場合、ピボットの絶対値を可能な限り最大にすることで、アルゴリズムの数値安定性が向上します。 ^{[ 15 ]}

この手順が完了すると、行列は行階段形になり、対応する連立方程式は後退代入によって解くことができる。

参考文献

↑ 「DOCUMENTA MATHEMATICA、Vol. Extra Volume: Optimization Stories (2012)、9-14」。www.emis.de。2022年12月2日取得。
↑カリンガー 1999 、pp. 234–236
↑ティモシー・ガワーズ、ジューン・バロー＝グリーン、イムレ・リーダー（2008年9月8日）。『プリンストン数学事典』プリンストン大学出版局、607ページ。ISBN 978-0-691-11880-2。
1 2 Grcar 2011a 、pp. 169–172
↑ Grcar 2011b 、 783～785ページ
↑ローリッツェン、 3ページ
↑ Grcar 2011b 、p. 789
↑ Althoen, Steven C.; McLaughlin, Renate (1987)、「ガウス・ジョルダン還元：簡単な歴史」、The American Mathematical Monthly、94 (2)、Mathematical Association of America: 130–142、doi : 10.2307/2322413、ISSN 0002-9890、JSTOR 2322413
↑フェアブラザー 1988 、p.12
↑ Fang, Xin Gui; Havas, George (1997). 「整数ガウス消去法の最悪ケースの複雑さについて」 . 1997年国際シンポジウム「記号代数計算」議事録. ISSAC '97. キヘイ、マウイ島、ハワイ、アメリカ合衆国: ACM. pp. 28–31 . doi : 10.1145/258726.258740 . ISBN 0-89791-875-4。
1 2マーティン・グレッシェル; Lovász, ラスロー; Schrijver, Alexander (1993)、「幾何学的アルゴリズムと組み合わせ最適化」、アルゴリズムと組み合わせ、第 1 巻。2 (第 2版)、Springer-Verlag、ベルリン、土井: 10.1007/978-3-642-78240-4、ISBN 978-3-642-78242-8MR 1261419
↑ゴラブとヴァン・ローン 1996 、§3.4.6
↑ John Urschel:「ガウス消去法における数値的安定性」、2025年6月/7月、AMS通知、pp.605-613。
↑ Hillar, Christopher; Lim, Lek-Heng (2009-11-07). "ほとんどのテンソル問題はNP困難である". arXiv : 0911.1393 [ cs.CC ].
↑クルガリン、セルゲイ；ボルズノフ、セルゲイ（2021）。Pythonによる代数と幾何。Cham。doi : 10.1007 / 978-3-030-61541-3。ISBN 978-3-030-61540-6。{{cite book}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)

参考文献

アトキンソン、ケンドール A. (1989)、数値解析入門（第 2 版）、ニューヨーク:ジョン・ワイリー・アンド・サンズ、ISBN 978-0471624899。
Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; Trivedi, Kishor S. (2006), Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications (2nd ed.), Wiley-Interscience , ISBN 978-0-471-79156-0。
カリンガー、ロナルド（1999）、『数学の文脈史』、プレンティス・ホール、ISBN 978-0-02-318285-3。
Farebrother, RW (1988)、線形最小二乗計算、統計学：教科書とモノグラフ、Marcel Dekker、ISBN 978-0-8247-7661-9。
Lauritzen, Niels,学部生向け凸性: フーリエとモツキンからクーンとタッカーまで。
Golub, Gene H. ; Van Loan, Charles F. (1996), Matrix Computations (3rd ed.), Johns Hopkins, ISBN 978-0-8018-5414-9。
Grcar, Joseph F. (2011a)、「通常の消去法がガウス消去法になった経緯」、Historia Mathematica、38 (2): 163–218、arXiv : 0907.2397、doi : 10.1016/j.hm.2010.06.003、S2CID 14259511
Grcar, Joseph F. (2011b)、「ガウス消去法の数学者たち」（PDF）、アメリカ数学会報、58（6）：782–792
Higham, Nicholas (2002),数値アルゴリズムの精度と安定性(第 2 版), SIAM , ISBN 978-0-89871-521-7。
カッツ、ビクター・J. (2004)、『数学史簡略版』、アディソン・ウェスリー、ISBN 978-0-321-16193-2。
Kaw, Autar; Kalu, Egwu (2010). "数値計算法とその応用：第4.6章ガウス消去法" (PDF) (第1 版). 南フロリダ大学。2012年9月7日にオリジナルからアーカイブされたPDF 。
Lipson, Marc; Lipschutz, Seymour (2001), Schaum's outline of theory and problems of linear algebra , New York: McGraw-Hill , pp. 69–80 , ISBN 978-0-07-136200-9
Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)、「セクション 2.2」、Numerical Recipes: The Art of Scientific Computing (第 3 版)、ニューヨーク: Cambridge University Press、ISBN 978-0-521-88068-82012年3月19日にオリジナルからアーカイブされ、 2011年8月8日に取得されました。

外部リンク

インタラクティブな教育ツール

[1] 「DOCUMENTA MATHEMATICA、Vol. Extra Volume: Optimization Stories (2012)、9-14」。www.emis.de。2022年12月2日取得。

[2] カリンガー 1999 、pp. 234–236

[princeton-3] ティモシー・ガワーズ、ジューン・バロー＝グリーン、イムレ・リーダー（2008年9月8日）。『プリンストン数学事典』プリンストン大学出版局、607ページ。ISBN 978-0-691-11880-2。

[harvnb|Grcar|2011a|pp=169–172-4] 1 2 Grcar 2011a 、pp. 169–172

[5] Grcar 2011b 、 783～785ページ

[6] ローリッツェン、 3ページ

[7] Grcar 2011b 、p. 789

[8] Althoen, Steven C.; McLaughlin, Renate (1987)、「ガウス・ジョルダン還元：簡単な歴史」、The American Mathematical Monthly、94 (2)、Mathematical Association of America: 130–142、doi : 10.2307/2322413、ISSN 0002-9890、JSTOR 2322413

[9] フェアブラザー 1988 、p.12

[10] Fang, Xin Gui; Havas, George (1997). 「整数ガウス消去法の最悪ケースの複雑さについて」 . 1997年国際シンポジウム「記号代数計算」議事録. ISSAC '97. キヘイ、マウイ島、ハワイ、アメリカ合衆国: ACM. pp. 28–31 . doi : 10.1145/258726.258740 . ISBN 0-89791-875-4。

[:0-11] 1 2マーティン・グレッシェル; Lovász, ラスロー; Schrijver, Alexander (1993)、「幾何学的アルゴリズムと組み合わせ最適化」、アルゴリズムと組み合わせ、第 1 巻。2 (第 2版)、Springer-Verlag、ベルリン、土井: 10.1007/978-3-642-78240-4、ISBN 978-3-642-78242-8MR 1261419

[12] ゴラブとヴァン・ローン 1996 、§3.4.6

[13] John Urschel:「ガウス消去法における数値的安定性」、2025年6月/7月、AMS通知、pp.605-613。

[14] Hillar, Christopher; Lim, Lek-Heng (2009-11-07). "ほとんどのテンソル問題はNP困難である". arXiv : 0911.1393 [ cs.CC ].

[15] クルガリン、セルゲイ；ボルズノフ、セルゲイ（2021）。Pythonによる代数と幾何。Cham。doi : 10.1007 / 978-3-030-61541-3。ISBN 978-3-030-61540-6。{{cite book}}: CS1メンテナンス: 場所の発行元が見つかりません (リンク)

[

[

[

Grcar [ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[

[ 10 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

ガウス消去法

アルゴリズムの定義と例

行操作

梯形陣形

アルゴリズムの例

歴史

アプリケーション

行列式の計算

行列の逆行列を求める

ランクと基数の計算

計算効率

ベライスアルゴリズム

数値不安定性

一般化

擬似コード

関連項目

参考文献

参考文献

外部リンク

関連するトピック

連立一次方程式

アルゴリズムである。これは、対応する係数

行列

ランク、