過剰決定システム

数学では、方程式の数が未知数より多い場合、その方程式系は過剰決定系である と見なされます。 ^{[1] [要出典]過剰決定系は、ランダムな係数で構築された場合、ほとんどの場合}矛盾します（解がありません）。ただし、一部の方程式がシステム内で複数回出現する場合や、一部の方程式が他の方程式の線形結合である場合など、過剰決定系には解が存在する場合があります。

この用語は、制約カウントの概念で説明できます。各未知数は、利用可能な自由度と見なすことができます。システムに導入された各方程式は、 1 つの自由度を制限する制約と見なすことができます。したがって、方程式の数と自由変数の数が等しい場合に、臨界ケースが発生します。自由度を与えるすべての変数に対して、対応する制約が存在します。過剰決定ケースは、システムが過剰に制約されている場合、つまり方程式の数が未知数を上回っている場合に発生します。対照的に、不足決定ケースは、システムが不足制約されている場合、つまり方程式の数が未知数の数より少ない場合に発生します。このようなシステムには、通常、無限の数の解があります。

3 > 2 であるため過剰決定であり、図 1 に対応する 3 つの方程式と 2 つの未知数 ( XとY )のシステムを考えます。$${\displaystyle {\begin{aligned}Y&=-2X-1\\Y&=3X-2\\Y&=X+1.\end{aligned}}}$$

線形方程式の各ペアには、1 つの解があります。1 番目と 2 番目の方程式 (0.2、-1.4)、1 番目と 3 番目の方程式 (-2/3、1/3)、2 番目と 3 番目の方程式 (1.5、2.5) です。ただし、3 つすべてを同時に満たす解はありません。図 2 と 3 は、すべての線上に点がないため矛盾している他の構成を示しています。このようなシステムは矛盾していると見なされます。

過剰決定系が実際に解を持つ唯一のケースは、図 4、5、および 6 で示されています。これらの例外は、過剰決定系に十分な線形従属方程式が含まれており、独立方程式の数が未知数の数を超えない場合にのみ発生します。線形従属とは、一部の方程式が他の方程式を線形に組み合わせることで得られることを意味します。たとえば、Y  =  X  + 1 と 2 Y  = 2 X  + 2 は線形従属方程式です。これは、2 番目の方程式が最初の方程式の 2 倍で得られるためです。

どのような線形方程式系も、行列方程式として記述できます。前の方程式系 (図 1) は、次のように記述できます。 係数行列の行(方程式に対応) の数は列 (未知数に対応) の数より多く、システムが過剰決定されていることを意味します。この行列の階数は 2 で、システム内の従属変数の数に対応します。 ^[2]線形システムは、係数行列が拡張行列(余分な列が追加された係数行列で、その列は定数の列ベクトルです) と同じ階数である場合にのみ、矛盾しません。拡張行列の階数は 3 なので、システムは矛盾しています。ヌル度は0 で、ヌル空間にはゼロベクトルのみが含まれ、したがって基底がないことを意味します。 $${\displaystyle {\begin{bmatrix}2&1\\-3&1\\-1&1\\\end{bmatrix}}{\begin{bmatrix}X\\Y\end{bmatrix}}={\begin{bmatrix}-1\\-2\\1\end{bmatrix}}}$$

線形代数では、行空間、列空間、および零空間の概念が行列の特性を決定する上で重要です。上記の制約と自由度に関する非公式な議論は、これらのより正式な概念に直接関係しています。

同次ケース (すべての定数項がゼロ) は常に一貫しています (自明な、すべてゼロの解が存在するため)。線形従属方程式の数に応じて、自明な解だけが存在する場合と、自明な解に加えて他の解の無限セットが存在する場合の 2 つのケースがあります。

線形方程式のシステムを考えます。L _i = 0 (1 ≤ i ≤ M )、変数X ₁、X ₂、...、X _N、ここで各L _{i は}X _iの加重和です。すると、X ₁ = X ₂ = ⋯ = X _N = 0 は常に解になります。M < Nの場合、システムは不確定であり、常に無限の解が存在します。実際、解の空間の次元は常に少なくともN − Mです。

M ≥ Nの場合、すべての値が 0 になる以外に解は存在しない可能性があります。方程式系に十分な依存関係 (線形従属方程式) があり、独立した方程式の数が最大でN − 1 である場合にのみ、他の解が無限に存在します。ただし、M ≥ Nの場合、独立した方程式の数はNまで大きくなる可能性があり、その場合は自明な解が唯一の解になります。

線形方程式のシステムL _i = c _i (1 ≤ i ≤ M )では、変数X ₁、X ₂、...、X _Nにおいて、方程式は線形従属である場合があります。実際、線形独立方程式の数はN +1 を超えることはできません。N個の未知数とM個の方程式 ( M > N )を持つ過剰決定システムでは、次のケースが考えられます。

• M = N +1 であり、すべての M 方程式は線形独立です。 この場合、解は生成されません。 例: x = 1、x = 2。
• M > Nですが、線形独立なのはK方程式のみです ( K < MかつK ≤ N +1)。これには 3 つのサブケースが考えられます。
  • K = N +1。この場合、解は生成されません。例: 2 x = 2、x = 1、x = 2。
  • K = N。この場合、単一の解が得られるか、または解が得られないかのどちらかになります。後者は、1 つの方程式の係数ベクトルが他の方程式の係数ベクトルの加重和で複製できるが、他の方程式の定数項に適用された加重和が 1 つの方程式の定数項を複製しない場合に発生します。解が 1 つの例: 2 x = 2、x = 1。解がない例: 2 x + 2 y = 2、x + y = 1、x + y = 3。
  • K < N。このケースでは、無限に多くの解が存在するか、または解が存在しないかのいずれかになります。後者は、前のサブケースと同様に発生します。無限に多くの解が存在する例: 3 x + 3 y = 3、2 x + 2 y = 2、x + y = 1。解が存在しない場合の例: 3 x + 3 y + 3 z = 3、2 x + 2 y + 2 z = 2、x + y + z = 1、x + y + z = 4。

これらの結果は、ガウス消去法を使用して、システムの係数の拡張行列を行階段形式にすると理解しやすくなります。この行階段形式は、与えられたシステムと同等の方程式システムの拡張行列です（まったく同じ解を持ちます）。元のシステムの独立した方程式の数は、階段形式の非ゼロ行の数です。階段形式の最後の非ゼロ行に、最後の列にある 1 つの非ゼロ項目しかない場合（方程式 0 = c を与え、c は非ゼロ定数）、および場合にのみ、システムは矛盾しています（解がありません）。それ以外の場合、階段形式の非ゼロ行の数が未知数の数に等しい場合は、解が 1 つだけ存在し、非ゼロ行の数が変数の数より少ない場合は、解が無限に存在します。

言い換えると、ルーシェ・カペリ定理によれば、拡大行列の階数が係数行列の階数よりも大きい場合、方程式系（過剰決定方程式であろうとなかろうと）は矛盾します。一方、これら 2 つの行列の階数が等しい場合、系には少なくとも 1 つの解が存在する必要があります。階数が変数の数に等しい場合のみ、解は一意です。それ以外の場合、一般解にはk 個の自由パラメータがあり、k は変数の数と階数の差です。したがって、このような場合には解が無限に存在します。

行列代数を使用すると、すべての正確な解が得られるか、または解が存在しないことが示されます。線形方程式系#行列解を参照してください。

通常の最小二乗法は、過剰決定システムの近似解を求めるのに使用できます。システム の最小二乗法は、問題 から得られ 、その解は正規方程式 で表すことができます。^[3] ここで、は転置行列を表します。ただし、が存在する場合 (つまり、Aが列全体の階数である場合) です。この公式を使用すると、正確な解が存在しない場合に近似解が見つかり、正確な解が存在する場合に正確な解が得られます。ただし、良好な数値精度を実現するには、AのQR 分解を使用して最小二乗問題を解くことをお勧めします。^[4]${\displaystyle A\mathbf {x} =\mathbf {b} ,}$$${\displaystyle \min _{\mathbf {x} }\lVert A\mathbf {x} -\mathbf {b} \rVert ,}$$ $${\displaystyle \mathbf {x} =\left(A^{\mathsf {T}}A\right)^{-1}A^{\mathsf {T}}\mathbf {b} ,}$$${\displaystyle {\mathsf {T}}}$ ${\displaystyle \left(A^{\mathsf {T}}A\right)^{-1}}$

（縦長の）行列のQR分解は、行列を積の形で表現したものである。 ${\displaystyle A}$

${\displaystyle A=QR,}$

ここで、は行列 の範囲にまたがる（背の高い）半正規直交行列であり、 は（小さな）正方直角三角行列です。 ${\displaystyle Q}$${\displaystyle A}$${\displaystyle R}$

ノルムを最小化する問題の解は次のように与えられる。 ${\displaystyle \|Ax-b\|^{2}}$

${\displaystyle x=R^{-1}Q^{T}b,}$

実際には、計算する代わりに、右三角システム上で 後退置換を実行する必要がある。${\displaystyle R^{-1}}$

${\displaystyle Rx=Q^{T}b.}$

（縦長の）行列の特異値分解（SVD）は、行列を積の形で表現したものである。 ${\displaystyle A}$

${\displaystyle A=USV^{T},}$

ここで、は行列 の範囲に及ぶ (背の高い) 半正規直交行列、は対角線に沿って負でない特異値を持つ (小さな) 正方対角行列、は(小さな) 正方正規直交行列です。 ${\displaystyle U}$${\displaystyle A}$${\displaystyle S}$${\displaystyle V}$

ノルムを最小化する問題の解は次のように与えられる。 ${\displaystyle \|Ax-b\|^{2}}$

${\displaystyle x=VS^{-1}U^{T}b.}$

有限次元空間では、方程式系は次のように記述または表現できる。

${\displaystyle \left\{{\begin{array}{ccc}f_{1}(x_{1},\ldots ,x_{n})&=&0\\\vdots &\vdots &\vdots \\f_{m}(x_{1},\ldots ,x_{n})&=&0\end{array}}\right.}$

または、 ${\displaystyle \mathbf {f} (\mathbf {x} )=\mathbf {0} }$

${\displaystyle \mathbf {f} (\mathbf {x} )=\left[{\begin{array}{c}f_{1}(x_{1},\ldots ,x_{n})\\\vdots \\f_{m}(x_{1},\ldots ,x_{n})\end{array}}\right]\;\;\;{\mbox{and}}\;\;\;\mathbf {0} =\left[{\begin{array}{c}0\\\vdots \\0\end{array}}\right]}$

ここで はの点、は実関数または複素関数です。 の場合、システムは過剰決定系です。対照的に の場合、システムは不十分決定系です。 ^{[5] [6]}${\displaystyle \mathbf {x} =(x_{1},\ldots ,x_{n})}$${\displaystyle R^{n}}$${\displaystyle C^{n}}$${\displaystyle f_{1},\ldots ,f_{m}}$${\displaystyle m>n}$${\displaystyle m<n}$

過剰決定系を解くための効果的な方法として、ガウス・ニュートン反復法は、ヤコビ行列が単射となる解に局所的に二次収束します。 ${\displaystyle \mathbf {f} (\mathbf {x} )}$

この概念は、多項式方程式や偏微分方程式などのより一般的な方程式系にも適用できます。多項式方程式系の場合、過剰決定系に解が存在するものの、どの方程式も他の方程式の結果ではなく、任意の方程式を削除すると新しい系に複数の解が存在するという状況が発生することがあります。たとえば、 には1 つの解がありますが、各方程式自体には 2 つの解があります。 ${\displaystyle (x-1)(x-2)=0,(x-1)(x-3)=0}$${\displaystyle x=1,}$

• 圧縮センシング
• 一貫性の証明
• 積分可能性条件
• 最小二乗法
• ムーア・ペンローズ擬似逆行列
• ルーシェ・カペリ (またはルーシェ・フロベニウス) の定理