線形方程式系

未知数が1つである方程式のシステム

${\displaystyle 2x=4}$

解決策があります

${\displaystyle x=2.}$

しかし、興味深い線形システムのほとんどは、少なくとも2つの方程式から構成されている。

最も単純な非自明な線形システムは、2つの方程式と2つの変数から構成されます。

${\displaystyle {\begin{alignedat}{5}2x&&\;+\;&&3y&&\;=\;&&6&\\4x&&\;+\;&&9y&&\;=\;&&15&.\end{alignedat}}}$

このような連立方程式を解く方法の一つは次のとおりです。まず、上の式を解いて、${\displaystyle x}$に関しては${\displaystyle y}$:

${\displaystyle x=3-{\frac {3}{2}}y.}$

次に、このxの式を下の式に代入します。

${\displaystyle 4\left(3-{\frac {3}{2}}y\right)+9y=15.}$

これにより、変数のみを含む単一の方程式が得られます。${\displaystyle y}$解くと${\displaystyle y=1}$、これを式に代入すると${\displaystyle x}$収量${\displaystyle x={\frac {3}{2}}}$この方法は、追加の変数を持つシステムにも一般化できます（下記の「変数の消去」または初等代数に関する記事を参照）。

非常に役立つ見方の一つは、各未知数が線形結合における列ベクトルの重みであると考えることです。

${\displaystyle x_{1}{\begin{bmatrix}a_{11}\\a_{21}\\\vdots \\a_{m1}\end{bmatrix}}+x_{2}{\begin{bmatrix}a_{12}\\a_{22}\\\vdots \\a_{m2}\end{bmatrix}}+\dots +x_{n}{\begin{bmatrix}a_{1n}\\a_{2n}\\\vdots \\a_{mn}\end{bmatrix}}={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{bmatrix}}}$

これにより、ベクトル空間（より一般的には加群）のあらゆる言語と理論を適用することが可能になります。例えば、左辺（ LHS）のベクトルの可能なすべての線形結合の集合をスパンと呼び、方程式は右辺のベクトルがそのスパン内にある場合にのみ解を持ちます。スパン内のすべてのベクトルが、与えられた左辺のベクトルの線形結合としてちょうど1つの式を持つ場合、解は一意になります。いずれにせよ、スパンは、ちょうど1つの式を保証する線形独立なベクトルの基底を持ち、その基底に含まれるベクトルの数（次元）はmまたはnより大きくなることはありませんが、それより小さくなることもあります。これは、 m個の独立なベクトルがあれば右辺（RHS）に関係なく解が保証され、そうでなければ保証されないため重要です。

ベクトル方程式は、次の形式の 行列方程式と同等である。$${\displaystyle A\mathbf {x} =\mathbf {b} }$$ where A is an m×n matrix, x is a column vector with n entries, and b is a column vector with m entries.^[4]

$${\displaystyle A={\begin{bmatrix}a_{11}&a_{12}&\cdots &a_{1n}\\a_{21}&a_{22}&\cdots &a_{2n}\\\vdots &\vdots &\ddots &\vdots \\a_{m1}&a_{m2}&\cdots &a_{mn}\end{bmatrix}},\quad \mathbf {x} ={\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}},\quad \mathbf {b} ={\begin{bmatrix}b_{1}\\b_{2}\\\vdots \\b_{m}\end{bmatrix}}.}$$ The number of vectors in a basis for the span of the columns vectors in A is now expressed as the rank of the matrix.

For a system involving two variables (x and y), each linear equation determines a line on the xy-plane. Because a solution to a linear system must satisfy all of the equations, the solution set is the intersection of these lines, and is hence either a line, a single point, or the empty set.

For three variables, each linear equation determines a plane in three-dimensional space, and the solution set is the intersection of these planes. Thus the solution set may be a plane, a line, a single point, or the empty set. For example, as three parallel planes do not have a common point, the solution set of their equations is empty; the solution set of the equations of three planes intersecting at a point is single point; if three planes pass through two points, their equations have at least two common solutions; in fact the solution set is infinite and consists in all the line passing through these points.^[6]

For n variables, each linear equation determines a hyperplane in n-dimensional space. The solution set is the intersection of these hyperplanes, and is a flat, which may have any dimension lower than n.

一般的に、線形システムの挙動は、方程式の数と未知数の数の関係によって決まります。ここで「一般的に」とは、方程式の係数の特定の値によっては、異なる挙動が生じる可能性があることを意味します。

• 一般に、未知数の数よりも方程式の数が少ない連立方程式は、無限に多くの解を持つが、解を持たない場合もある。このような連立方程式は、不確定系と呼ばれる。
• 一般的に、方程式の数と未知数の数が同じシステムには、ただ一つの解が存在する。
• 一般に、未知数の数よりも方程式の数が多い連立方程式には解が存在しない。このような連立方程式は、過剰決定系とも呼ばれる。

最初のケースでは、解集合の次元は一般にn − mに等しくなります。ここで、nは変数の数、mは方程式の数です。

以下の図は、2つの変数の場合におけるこの三区分を示しています。

最初のシステムには無限に多くの解があり、それは青い線上のすべての点です。2番目のシステムにはただ1つの解があり、それは2つの線の交点です。3番目のシステムには解がありません。なぜなら、3つの線は共通点を持たないからです。

上記の図は最も一般的なケース（一般ケース）のみを示していることに留意する必要があります。2つの方程式と2つの未知数からなる連立方程式は、2つの直線が平行な場合は解を持たない可能性があり、3つの方程式と2つの未知数からなる連立方程式は、3つの直線が1点で交わる場合は解を持つ可能性があります。

線形方程式系は、方程式が線形従属である場合、または方程式が矛盾していて未知数の数よりも方程式の数が少ない場合、一般の場合とは異なる挙動を示す。

線形システムの方程式は、いずれの方程式も他の方程式から代数的に導出できない場合に独立である。方程式が独立している場合、各方程式は変数に関する新しい情報を含み、いずれかの方程式を削除すると解集合のサイズが大きくなる。線形方程式の場合、論理的独立性と線形独立性は同じである。

例えば、方程式

${\displaystyle 3x+2y=6\;\;\;\;{\text{および}}\;\;\;\;6x+4y=12}$

これらは独立ではありません。2倍に拡大すると同じ方程式になり、同じグラフが生成されます。これは、連立一次方程式における等価性の例です。

より複雑な例では、方程式は次のようになります。

${\displaystyle {\begin{alignedat}{5}x&&\;-\;&&2y&&\;=\;&&-1&\\3x&&\;+\;&&5y&&\;=\;&&8&\\4x&&\;+\;&&3y&&\;=\;&&7&\end{alignedat}}}$

これらは独立ではありません。なぜなら、3番目の式は他の2つの式の和だからです。実際、これらの式のいずれも他の2つから導き出すことができ、また、いずれか1つの式を削除しても解集合には影響しません。これらの式のグラフは、1点で交わる3本の直線になります。

線形システムは、解がない場合には矛盾しており、そうでない場合は一貫性があると言われます。^{[ 7 ]}システムが矛盾している場合は、方程式から矛盾を導き出すことができ、それは常に0 = 1 という記述に書き換えることができます。

例えば、方程式

${\displaystyle 3x+2y=6\;\;\;\;{\text{and}}\;\;\;\;3x+2y=12}$

これらは矛盾しています。実際、2番目の式から最初の式を引いて、その結果の両辺に1/6を掛けると、0 = 1となります。これらの式をxy平面上にグラフ化すると、一対の平行線になります。

3 つの線形方程式は、そのうちの 2 つが互いに整合していても、矛盾が生じる可能性があります。たとえば、次の方程式は

${\displaystyle {\begin{alignedat}{7}x&&\;+\;&&y&&\;=\;&&1&\\2x&&\;+\;&&y&&\;=\;&&1&\\3x&&\;+\;&&2y&&\;=\;&&3&\end{alignedat}}}$

これらは矛盾しています。最初の2つの式を足し合わせると、3x + 2y = 2となり、これを3番目の式から引くと0 = 1となります。これらの式のうち、任意の2つに共通の解が存在します。同様の現象は、任意の数の式でも起こり得ます。

一般に、連立方程式の左辺が線形従属であり、定数項がその従属関係を満たさない場合、矛盾が生じる。左辺が線形独立である連立方程式は常に矛盾がない。

言い換えれば、ルーシェ・カペリの定理によれば、拡大行列のランクが係数行列のランクより大きい場合、任意の方程式系（過剰決定系か否かを問わず）は矛盾している。一方、これら2つの行列のランクが等しい場合、その系は少なくとも1つの解を持つ。解は、ランクが変数の数に等しい場合に限り一意である。そうでない場合、一般解はk個の自由パラメータを持ち、ここでkは変数の数とランクの差である。したがって、このような場合には無限の解が存在する。方程式系のランク（すなわち、拡大行列のランク）は[変数の数] + 1を超えることは決してない。つまり、任意の数の方程式を持つ系は、独立方程式の数が最大で[変数の数] + 1である系に常に還元できる。

同じ変数セットを使用する2つの線形システムは、 2番目のシステムの各方程式が最初のシステムの方程式から代数的に導出でき、かつその逆も成り立つ場合に同値である。2つのシステムは、両方とも矛盾しているか、またはそれぞれの方程式が他方の方程式の線形結合である場合に同値である。したがって、2つの線形システムは、同じ解集合を持つ場合に限り同値である。

解集合が有限の場合、それは単一の要素に縮小されます。この場合、一意解は、左辺が未知数の名前、右辺が対応する値である一連の方程式によって記述されます。たとえば、${\displaystyle (x=3,\;y=-2,\;z=6)}$未知数の順序が固定されている場合（例えばアルファベット順） 、解は次のような値のベクトルとして記述できます。${\displaystyle (3,\,-2,\,6)}$前の例について。

無限個の解を持つ集合を記述する場合、通常、いくつかの変数は自由変数（または独立変数、あるいはパラメータ）として指定され、任意の値をとることが許されます。残りの変数は、自由変数の値に依存します。

例えば、次のシステムを考えてみましょう。

${\displaystyle {\begin{alignedat}{7}x&&\;+\;&&3y&&\;-\;&&2z&&\;=\;&&5&\\3x&&\;+\;&&5y&&\;+\;&&6z&&\;=\;&&7&\end{alignedat}}}$

この連立方程式の解集合は、以下の式で表すことができます。

${\displaystyle x=-7z-1\;\;\;\;{\text{and}}\;\;\;\;y=3z+2{\text{.}}}$

ここで、zは自由変数であり、xとyはzに依存します。解集合内の任意の点は、まずzの値を選択し、次にそれに対応するxとyの値を計算することによって得られます。

各自由変数は解空間に1つの自由度を与え、その数は解集合の次元に等しくなります。例えば、上記の方程式の解集合は直線です。これは、パラメータzの値を指定することで解集合内の点を選択できるためです。より高次の無限解は、平面、あるいはより高次元の集合を表す場合があります。

自由変数の選択が異なると、同じ解集合でも異なる記述になる場合があります。例えば、上記の方程式の解は、次のように記述することもできます。

${\displaystyle y=-{\frac {3}{7}}x+{\frac {11}{7}}\;\;\;\;{\text{and}}\;\;\;\;z=-{\frac {1}{7}}x-{\frac {1}{7}}{\text{.}}}$

ここで、xは自由変数であり、yとzは従属変数である。

連立一次方程式を解く最も簡単な方法は、変数を繰り返し消去することです。この方法は次のように説明できます。

1. 最初の式において、いずれかの変数を他の変数を用いて表してください。
2. この式を残りの式に代入します。これにより、方程式と未知数がそれぞれ1つずつ減った連立方程式が得られます。
3. システムが単一の線形方程式に還元されるまで、手順1と2を繰り返します。
4. この方程式を解き、解全体が求められるまで逆代入を繰り返してください。

例えば、次のシステムを考えてみましょう。

${\displaystyle {\begin{cases}x+3y-2z=5\\3x+5y+6z=7\\2x+4y+3z=8\end{cases}}}$

最初の式をxについて解くと、${\displaystyle x=5+2z-3y}$、これを2番目と3番目の式に代入すると、

${\displaystyle {\begin{cases}y=3z+2\\y={\tfrac {7}{2}}z+1\end{cases}}}$

これら2つの式の左辺はどちらもyに等しいので、右辺を等しくすると、次の式が得られます。

${\displaystyle {\begin{aligned}3z+2={\tfrac {7}{2}}z+1\\\Rightarrow z=2\end{aligned}}}$

z = 2 を 2 番目または 3 番目の式に代入するとy = 8 となり、yとzの値を最初の式に代入するとx = −15 となります。したがって、解集合は順序付き三つ組です。${\displaystyle (x,y,z)=(-15,8,2)}$。

行削減（ガウス消去法とも呼ばれる）では、線形システムは拡大行列として表現される^{[ 8 ]。}

${\displaystyle \left[{\begin{array}{rrr|r}1&3&-2&5\\3&5&6&7\\2&4&3&8\end{array}}\right]{\text{.}}}$

この行列は、基本行操作を使用して簡約行階段形になるまで変更されます。基本行操作には 3 つの種類があります。^{[ 8 ]}

タイプ1：2つの行の位置を入れ替える。

タイプ 2 : 行にゼロ以外のスカラーを掛けます。

Type 3: Add to one row a scalar multiple of another.

Because these operations are reversible, the augmented matrix produced always represents a linear system that is equivalent to the original.

There are several specific algorithms to row-reduce an augmented matrix, the simplest of which are Gaussian elimination and Gauss–Jordan elimination. The following computation shows Gauss–Jordan elimination applied to the matrix above:

${\displaystyle {\begin{aligned}\left[{\begin{array}{rrr|r}1&3&-2&5\\3&5&6&7\\2&4&3&8\end{array}}\right]&\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&-4&12&-8\\2&4&3&8\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&-4&12&-8\\0&-2&7&-2\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&1&-3&2\\0&-2&7&-2\end{array}}\right]\\&\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&1&-3&2\\0&0&1&2\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&3&-2&5\\0&1&0&8\\0&0&1&2\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&3&0&9\\0&1&0&8\\0&0&1&2\end{array}}\right]\sim \left[{\begin{array}{rrr|r}1&0&0&-15\\0&1&0&8\\0&0&1&2\end{array}}\right].\end{aligned}}}$

The last matrix is in reduced row echelon form, and represents the system x = −15, y = 8, z = 2. A comparison with the example in the previous section on the algebraic elimination of variables shows that these two methods are in fact the same; the difference lies in how the computations are written down.

Cramer's rule is an explicit formula for the solution of a system of linear equations, with each variable given by a quotient of two determinants.^[9] For example, the solution to the system

${\displaystyle {\begin{alignedat}{7}x&\;+&\;3y&\;-&\;2z&\;=&\;5\\3x&\;+&\;5y&\;+&\;6z&\;=&\;7\\2x&\;+&\;4y&\;+&\;3z&\;=&\;8\end{alignedat}}}$

is given by

${\displaystyle x={\frac {\,{\begin{vmatrix}5&3&-2\\7&5&6\\8&4&3\end{vmatrix}}\,}{\,{\begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix}}\,}},\;\;\;\;y={\frac {\,{\begin{vmatrix}1&5&-2\\3&7&6\\2&8&3\end{vmatrix}}\,}{\,{\begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix}}\,}},\;\;\;\;z={\frac {\,{\begin{vmatrix}1&3&5\\3&5&7\\2&4&8\end{vmatrix}}\,}{\,{\begin{vmatrix}1&3&-2\\3&5&6\\2&4&3\end{vmatrix}}\,}}.}$

For each variable, the denominator is the determinant of the matrix of coefficients, while the numerator is the determinant of a matrix in which one column has been replaced by the vector of constant terms.

Though Cramer's rule is important theoretically, it has little practical value for large matrices, since the computation of large determinants is somewhat cumbersome. (Indeed, large determinants are most easily computed using row reduction.) Further, Cramer's rule has very poor numerical properties, making it unsuitable for solving even small systems reliably, unless the operations are performed in rational arithmetic with unbounded precision.

If the equation system is expressed in the matrix form ${\displaystyle A\mathbf {x} =\mathbf {b} }$, the entire solution set can also be expressed in matrix form. If the matrix A is square (has m rows and n=m columns) and has full rank (all m rows are independent), then the system has a unique solution given by

${\displaystyle \mathbf {x} =A^{-1}\mathbf {b} }$

where ${\displaystyle A^{-1}}$ is the inverse of A. More generally, regardless of whether m=n or not and regardless of the rank of A, all solutions (if any exist) are given using the Moore–Penrose inverse of A, denoted ${\displaystyle A^{+}}$, as follows:

${\displaystyle \mathbf {x} =A^{+}\mathbf {b} +\left(I-A^{+}A\right)\mathbf {w} }$

where ${\displaystyle \mathbf {w} }$は、すべての可能なn × 1 ベクトルにわたる自由パラメータのベクトルです。解が存在するための必要十分条件は、を使用して得られる潜在的な解が${\displaystyle \mathbf {w} =\mathbf {0} }$満足する${\displaystyle A\mathbf {x} =\mathbf {b} }$つまり、${\displaystyle AA^{+}\mathbf {b} =\mathbf {b} .}$この条件が満たされない場合、方程式系は矛盾しており、解がありません。条件が満たされる場合、システムは一貫性があり、少なくとも 1 つの解が存在します。たとえば、上記のAが正方行列でフルランクである場合、${\displaystyle A^{+}}$単純に等しい${\displaystyle A^{-1}}$そして一般解方程式は次のように簡略化される。

${\displaystyle \mathbf {x} =A^{-1}\mathbf {b} +\left(I-A^{-1}A\right)\mathbf {w} =A^{-1}\mathbf {b} +\left(I-I\right)\mathbf {w} =A^{-1}\mathbf {b} }$

前述のとおり、${\displaystyle \mathbf {w} }$は完全に解から除外され、単一の解だけが残ります。しかし、他のケースでは、${\displaystyle \mathbf {w} }$自由パラメータベクトルには無限の潜在値が存在する。${\displaystyle \mathbf {w} }$この方程式には無限の解が存在する。

3つまたは4つの方程式からなる連立方程式は手計算で容易に解くことができますが（クラコフ式を参照）、より大規模な連立方程式にはコンピュータがよく使用されます。連立一次方程式を解くための標準的なアルゴリズムは、いくつかの修正を加えたガウス消去法に基づいています。まず、不正確な結果につながる可能性があるため、小さな数による除算を避けることが重要です。これは、必要に応じて方程式の順序を変更することによって行うことができます。このプロセスはピボットと呼ばれます。次に、このアルゴリズムは厳密にはガウス消去法を実行するのではなく、行列AのLU分解を計算します。これは主に整理ツールですが、同じ行列Aで異なるベクトルbを持つ複数の連立方程式を解く必要がある場合は、はるかに高速になります。

行列Aが何らかの特殊な構造を持つ場合、それを利用してより高速または高精度なアルゴリズムを得ることができます。例えば、対称正定値行列を持つシステムは、コレスキー分解を用いることで2倍の速さで解くことができます。レビンソン再帰法は、トープレッツ行列に対する高速な手法です。また、多くのゼロ要素を持つ行列（いわゆる疎行列）に対しても特別な手法が存在し、これらは応用分野でよく見られます。

非常に大規模なシステムでは、そうでなければ時間やメモリを過剰に消費してしまうため、全く異なるアプローチがしばしば採用されます。その考え方は、解の初期近似値（必ずしも正確である必要はありません）から始め、この近似値を数ステップで変更して真の解に近づけていくというものです。近似値が十分に正確になったら、それをシステムの解とみなします。これが反復法と呼ばれる手法につながります。疎行列の場合、ランダム性を導入することで反復法の速度が向上します。^{[ 10 ]}反復法の一例としてヤコビ法があり、行列は${\displaystyle A}$対角成分に分割される${\displaystyle D}$および非対角成分${\displaystyle L+U}$最初の推測${\displaystyle {\mathbf {x}}^{(0)}}$はアルゴリズムの開始時に使用されます。以降の各推定値は、反復方程式を使用して計算されます。

${\displaystyle {\mathbf {x}}^{(k+1)}=D^{-1}({\mathbf {b}}-(L+U){\mathbf {x}}^{(k)})}$

推測の差が${\displaystyle {\mathbf {x}}^{(k)}}$そして${\displaystyle {\mathbf {x}}^{(k+1)}}$が十分に小さい場合、アルゴリズムは解に収束したと言われる。 ^{[ 11 ]}

線形方程式系に対する量子アルゴリズムも存在する。^{[ 12 ]}

すべての同次システムには、少なくとも1つの解、すなわちゼロ解（または自明解）が存在し、これは各変数にゼロの値を割り当てることによって得られます。システムが非特異行列（det( A ) ≠ 0）を持つ場合、それが唯一の解となります。システムが特異行列を持つ場合、無限個の解を持つ解集合が存在します。この解集合には、以下の追加特性があります。

1. uとvが同次系の解を表す2つのベクトルである場合、ベクトルの和u + vもまたその系の解となる。
2. u が同次系の解を表すベクトルであり、rが任意のスカラーである場合、r uもその系の解となります。

これらはまさに、解集合がR ⁿの線形部分空間となるために必要な性質である。特に、同次系の解集合は、対応する行列Aの零空間と同じである。

線形システムの解と、それに対応する同次システムの解の間には密接な関係がある。

${\displaystyle A\mathbf {x} =\mathbf {b} \qquad {\text{and}}\qquad A\mathbf {x} =\mathbf {0} .}$

具体的には、p が線形システムA x = bの特定の解である場合、解の集合全体は次のように記述できます。

${\displaystyle \left\{\mathbf {p} +\mathbf {v}$ :\mathbf {v} {\text{は}}A\mathbf {x} =\mathbf {0} \right\}の任意の解である。}

幾何学的に言えば、これはA x = bの解集合がA x = 0の解集合の平行移動であることを意味します。具体的には、最初のシステムの平面は、同次システムの線形部分空間をベクトルpで平行移動することによって得られます。

この推論は、システムA x = b が少なくとも 1 つの解を持つ場合にのみ適用されます。これは、ベクトルb が線形変換Aの像に含まれる場合に限り発生します。

• アントン、ハワード（1987）『初等線形代数（第5 版）』ニューヨーク：ワイリー、ISBN 0-471-84819-0
• ボーレガード、レイモンド A.、フレイリー、ジョン B. (1973)『線形代数入門：群、環、体へのオプション入門』ボストン：ホートン・ミフリン社、ISBN 0-395-14017-X
• バーデン、リチャード L.、フェアーズ、J. ダグラス (1993)、数値解析(第 5 版)、ボストン:プリンドル、ウェーバー、シュミット、ISBN 0-534-93219-3
• カレン、チャールズ・G. (1990)、『行列と線形変換』、マサチューセッツ州：ドーバー出版、ISBN 978-0-486-66328-9
• Golub, Gene H.; Van Loan, Charles F. (1996), Matrix Computations (3rd  ed.), Baltimore: Johns Hopkins University Press , ISBN 0-8018-5414-8
• ハーパー、チャーリー（1976）、『数理物理学入門』、ニュージャージー州：プレンティス・ホール、ISBN 0-13-487538-9
• Harrow, Aram W.; Hassidim, Avinatan; Lloyd, Seth (2009)、「線形方程式系の量子アルゴリズム」、Physical Review Letters、103 (15) 150502、arXiv : 0811.3171、Bibcode : 2009PhRvL.103o0502H、doi : 10.1103/PhysRevLett.103.150502、PMID 19905613、S2CID 5187993  
• スターリング、メアリー・J. (2009)、『線形代数入門』、インディアナ州インディアナポリス：ワイリー、ISBN 978-0-470-43090-3
• ホワイトロー、TA（1991）、『線形代数入門（第2 版）』、CRC Press、ISBN 0-7514-0159-5