WIIS

凸集合

ファルカスによる連立1次不等式の基本定理

目次

Mailで保存
Xで共有

連立1次方程式の基本定理

変数\(x_{1},\cdots ,x_{n}\in \mathbb{R} \)に関する連立1次方程式\begin{equation}\left\{
\begin{array}{c}
a_{11}x_{1}+\cdots +a_{1n}x_{n}=b_{1} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}=b_{m}\end{array}\right. \quad \cdots (1)
\end{equation}が与えられているものとします。ただし、\(a_{ij}\in \mathbb{R} \)は係数、\(b_{i}\in \mathbb{R} \)は定数項、\(x_{i}\in \mathbb{R} \)は変数です。

連立1次方程式\(\left( 1\right) \)の係数行列\(A\)と変数ベクトル\(\boldsymbol{x}\)および定数ベクトル\(\boldsymbol{b}\)を、\begin{eqnarray*}A &=&\begin{pmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{m1} & \cdots & a_{mn}\end{pmatrix}\in M_{m,n}\left( \mathbb{R} \right) \\
\boldsymbol{x} &=&\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}\end{pmatrix}\in M_{n,1}\left( \mathbb{R} \right) \\
\boldsymbol{b} &=&\begin{pmatrix}
b_{1} \\
\vdots \\
b_{m}\end{pmatrix}\in M_{m,1}\left( \mathbb{R} \right)
\end{eqnarray*}と定めれば、\begin{eqnarray*}
A\boldsymbol{x} &=&\begin{pmatrix}
a_{11} & \cdots & a_{1n} \\
\vdots & \ddots & \vdots \\
a_{m1} & \cdots & a_{mn}\end{pmatrix}\begin{pmatrix}
x_{1} \\
\vdots \\
x_{n}\end{pmatrix}\quad \because A,\boldsymbol{x}\text{の定義} \\
&=&\begin{pmatrix}
a_{11}x_{1}+\cdots +a_{1n}x_{n} \\
\vdots \\
a_{m1}x_{1}+\cdots +a_{mn}x_{n}\end{pmatrix}\quad \because \text{行列積の定義} \\
&=&x_{1}\left(
\begin{array}{c}
a_{11} \\
\vdots \\
a_{m1}\end{array}\right) +\cdots +x_{n}\left(
\begin{array}{c}
a_{1n} \\
\vdots \\
a_{mn}\end{array}\right) \\
&=&x_{1}\mathrm{col}\left( A,1\right) +\cdots +x_{n}\mathrm{col}\left(
A,n\right)
\end{eqnarray*}という変形が可能であるため、連立1次方程式\(\left( 1\right) \)を行列方程式\begin{equation}A\boldsymbol{x}=\boldsymbol{b} \quad \cdots (2)
\end{equation}として表現したり、ベクトル方程式\begin{equation}
x_{1}\mathrm{col}\left( A,1\right) +\cdots +x_{n}\mathrm{col}\left( A,n\right) =\boldsymbol{b} \quad \cdots (3)
\end{equation}として表現できます。\(\left( 1\right) ,\left( 2\right) ,\left( 3\right) \)の解集合は一致するため、これらを同一視できます。

ベクトル方程式\(\left( 3\right) \)に解が存在することとは、\begin{equation*}\exists \left(
\begin{array}{c}
x_{1} \\
\vdots \\
x_{n}\end{array}\right) \in \mathbb{R} ^{n}:x_{1}\mathrm{col}\left( A,1\right) +\cdots +x_{n}\mathrm{col}\left(
A,n\right) =\boldsymbol{b}
\end{equation*}が成り立つことを意味します。つまり、定数ベクトル\(\boldsymbol{b}\)が係数行列\(A\)の列ベクトルからなる集合\begin{equation*}\left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right)
\right\} \subset \mathbb{R} ^{m}
\end{equation*}の何らかの線型結合として表現可能であるということです。線型スパンを用いてこれを表現すると、\begin{equation}
\boldsymbol{b}\in \mathrm{span}\left( \left\{ \mathrm{col}\left( A,1\right)
,\cdots ,\mathrm{col}\left( A,n\right) \right\} \right) \quad \cdots (4)
\end{equation}となります。

線型代数における議論において明らかになったように、\(\left( 4\right) \)が成り立つことは、\begin{equation}\mathrm{span}\left( \left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right) \right\} \right) =\mathrm{span}\left( \left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right) ,\boldsymbol{b}\right\} \right) \quad \cdots (5)
\end{equation}と必要十分です。さらに、拡大係数行列を、\begin{equation*}
\widetilde{A}=\left( A,\boldsymbol{b}\right) \in M_{m,n+1}\left( \mathbb{R} \right)
\end{equation*}と定義したとき、\(\left(5\right) \)が成り立つことは、\begin{equation*}\mathrm{rank}\left( A\right) =\mathrm{rank}\left( \widetilde{A}\right)
\end{equation*}と必要十分です。

命題(連立1次方程式に解が存在するための必要十分条件)
係数行列\(A\in M_{m,n}\left( \mathbb{R} \right) \)と変数ベクトル\(\boldsymbol{x}\in M_{n,1}\left( \mathbb{R} \right) \)と定数ベクトル\(\boldsymbol{b}\in M_{m,1}\left( \mathbb{R} \right) \)が与えられているものとする。拡大係数行列を\(\widetilde{A}=\left( A,\boldsymbol{b}\right) \in M_{m,n+1}\left( \mathbb{R} \right) \)と定義する。このとき、以下の命題はお互いに必要十分である。

  1. 行列方程式\(A\boldsymbol{x}=\boldsymbol{b}\)の解\(\boldsymbol{x}\in \mathbb{R} ^{n}\)が存在する。
  2. \(\boldsymbol{b}\in \mathrm{span}\left( \left\{ \mathrm{col}\left(A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right) \right\} \right) \)が成り立つ。
  3. \(\mathrm{span}\left( \left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right) \right\} \right) =\mathrm{span}\left( \left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right) ,\boldsymbol{b}\right\} \right) \)が成り立つ。
  4. \(\mathrm{rank}\left( A\right) =\mathrm{rank}\left( \widetilde{A}\right) \)が成り立つ。

連立1次方程式に解が存在するための必要十分条件を以下のように表現することもできます。証明では階数・退化次数の定理を利用します。

命題(連立1次方程式の基本定理)
係数行列\(A\in M_{m,n}\left( \mathbb{R} \right) \)と変数ベクトル\(\boldsymbol{x}\in M_{n,1}\left( \mathbb{R} \right) \)と定数ベクトル\(\boldsymbol{b}\in M_{m,1}\left( \mathbb{R} \right) \)が与えられているものとする。このとき、\begin{equation*}\forall \boldsymbol{y}\in M_{1,m}\left( \mathbb{R} \right) :\left( \boldsymbol{y}A=0\Rightarrow \boldsymbol{yb}=0\right)
\end{equation*}が成り立つことと、行列方程式\(A\boldsymbol{x}=\boldsymbol{b}\)の解\(\boldsymbol{x}\in \mathbb{R} ^{n}\)が存在することは必要十分である。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

連立1次方程式には解が存在するかしないかのどちらか一方であるため、先の命題より以下が導かれます。

命題(連立1次方程式の基本定理)
係数行列\(A\in M_{m,n}\left( \mathbb{R} \right) \)と定数ベクトル\(\boldsymbol{b}\in M_{m,1}\left( \mathbb{R} \right) \)が与えられているものとする。このとき、以下の2つのケースのどちらか一方が成り立つ。

  1. 行列方程式\(A\boldsymbol{x}=\boldsymbol{b}\)の解\(\boldsymbol{x}\in \mathbb{R} ^{n}\)が存在する。すなわち、\begin{equation*}\forall \boldsymbol{y}\in M_{1,m}\left( \mathbb{R} \right) :\left( \boldsymbol{y}A=0\Rightarrow \boldsymbol{yb}=0\right) \end{equation*}が成り立つ。
  2. 行列方程式\(A\boldsymbol{x}=\boldsymbol{b}\)の解\(\boldsymbol{x}\in \mathbb{R} ^{n}\)が存在しない。すなわち、\begin{equation*}\exists \boldsymbol{y}\in M_{1,m}\left( \mathbb{R} \right) :\left( \boldsymbol{y}A=0\wedge \boldsymbol{yb}\not=0\right) \end{equation*}が成り立つ。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

連立1次不等式の基本定理

連立1次方程式\begin{equation}
A\boldsymbol{x}=\boldsymbol{b} \quad \cdots (1)
\end{equation}に解\(\boldsymbol{x}\in \mathbb{R} ^{n}\)が存在するための必要十分条件と、解が存在しないための必要十分条件がそれぞれ明らかになりました。では、連立1次方程式\(\left( 1\right) \)について、以下の条件\begin{equation*}\forall i\in \left\{ 1,\cdots ,n\right\} :x_{i}\geq 0
\end{equation*}すなわち、\begin{equation*}
\boldsymbol{x}\geq 0
\end{equation*}を満たす解\(\boldsymbol{x}\in \mathbb{R} ^{n}\)が存在するための必要十分条件と、そのような解が存在しないための必要十分条件をそれぞれ特定できるでしょうか。

連立1次方程式\(A\boldsymbol{x}=\boldsymbol{b}\)に解\(\boldsymbol{x}\in \mathbb{R} ^{n}\)が存在するための必要十分条件の1つは、\begin{equation*}\exists \left(
\begin{array}{c}
x_{1} \\
\vdots \\
x_{n}\end{array}\right) \in \mathbb{R} ^{n}:x_{1}\mathrm{col}\left( A,1\right) +\cdots +x_{n}\mathrm{col}\left(
A,n\right) =\boldsymbol{b}
\end{equation*}です。これは、定数ベクトル\(\boldsymbol{b}\)が係数行列\(A\)の列ベクトルからなる集合\begin{equation*}\left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right)
\right\} \subset \mathbb{R} ^{m}
\end{equation*}の何らかの線型結合として表現可能であることを意味します。線型スパンを用いてこれを表現すると、\begin{equation*}
\boldsymbol{b}\in \mathrm{span}\left( \left\{ \mathrm{col}\left( A,1\right)
,\cdots ,\mathrm{col}\left( A,n\right) \right\} \right)
\end{equation*}となります。したがって、連立1次方程式\(A\boldsymbol{x}=\boldsymbol{b}\)に\(\boldsymbol{x}\geq 0\)を満たす解\(\boldsymbol{x}\in \mathbb{R} ^{n}\)が存在するための必要十分条件は、\begin{equation*}\exists \left(
\begin{array}{c}
x_{1} \\
\vdots \\
x_{n}\end{array}\right) \in \mathbb{R} _{+}^{n}:x_{1}\mathrm{col}\left( A,1\right) +\cdots +x_{n}\mathrm{col}\left(
A,n\right) =\boldsymbol{b}
\end{equation*}となります。つまり、定数ベクトル\(\boldsymbol{b}\)が係数行列\(A\)の列ベクトルからなる集合\begin{equation*}\left\{ \mathrm{col}\left( A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right)
\right\} \subset \mathbb{R} ^{m}
\end{equation*}の何らかの錐結合として表現可能であるということです。凸錐を用いてこれを表現すると、\begin{equation*}
\boldsymbol{b}\in \mathrm{Cone}\left( \left\{ \mathrm{col}\left( A,1\right)
,\cdots ,\mathrm{col}\left( A,n\right) \right\} \right)
\end{equation*}となります。であるならば、連立1次方程式\(A\boldsymbol{x}=\boldsymbol{b}\)に\(\boldsymbol{x}\geq 0\)を満たす解\(\boldsymbol{x}\in \mathbb{R} ^{n}\)が存在しないための必要十分条件は、\begin{equation*}\boldsymbol{b}\not\in \mathrm{Cone}\left( \left\{ \mathrm{col}\left(
A,1\right) ,\cdots ,\mathrm{col}\left( A,n\right) \right\} \right)
\end{equation*}です。以降では、これらの条件を別の形で表現します。

係数行列\(A\in M_{m,n}\left( \mathbb{R} \right) \)と定数ベクトル\(\boldsymbol{b}\in M_{m,1}\left( \mathbb{R} \right) \)が与えられているものとします。ただし、係数行列の階数を、\begin{equation*}r=\mathrm{rank}\left( A\right)
\end{equation*}と表記します。このとき、以下の2つの場合のどちらか一方が成り立つことが保証されます。

1つ目のケースは、連立1次方程式\(A\boldsymbol{x}=\boldsymbol{b}\)に\(\boldsymbol{x}\geq 0\)を満たす解\(\boldsymbol{x}\in \mathbb{R} ^{n}\)が存在する場合です。これは、定数ベクトル\(\boldsymbol{b}\)が、係数行列\(A\)を構成する線型独立な列ベクトル集合の錐結合として表現されることとして表現されます。つまり、係数行列\(A\)の第\(j\)列ベクトルを、\begin{equation*}\boldsymbol{a}_{j}=\mathrm{col}\left( A,j\right) =\left(
\begin{array}{c}
a_{j1} \\
\vdots \\
a_{jm}\end{array}\right) \in M_{m,1}\left( \mathbb{R} \right)
\end{equation*}と表記するのであれば、以上の事実は、\(k\leq n\)を満たす何らかの番号\(k\in \mathbb{N} \)に対して、以下の条件\begin{equation*}\left\{ \boldsymbol{a}_{\left( 1\right) },\cdots ,\boldsymbol{a}_{\left(
k\right) }\right\} \subset \left\{ \boldsymbol{a}_{1},\cdots ,\boldsymbol{a}_{n}\right\}
\end{equation*}を満たす線型独立なベクトル集合\(\left\{ \boldsymbol{a}_{\left( 1\right) },\cdots ,\boldsymbol{a}_{\left( k\right) }\right\} \)が存在して、\begin{equation}\exists \lambda _{1},\cdots ,\lambda _{k}\geq 0:\boldsymbol{b}=\lambda _{1}\boldsymbol{a}_{\left( 1\right) }+\cdots +\lambda _{k}\boldsymbol{a}_{\left(
k\right) } \quad \cdots (1)
\end{equation}と表されることを意味します。凸錐の定義より、\(\left( 1\right) \)が成り立つことを、\begin{equation*}\boldsymbol{b}\in \mathrm{Cone}\left( \left\{ \boldsymbol{a}_{\left(
1\right) },\cdots ,\boldsymbol{a}_{\left( k\right) }\right\} \right)
\end{equation*}と表現することもできます。

2つ目のケースは、連立1次方程式\(A\boldsymbol{x}=\boldsymbol{b}\)に\(\boldsymbol{x}\geq 0\)を満たす解\(\boldsymbol{x}\in \mathbb{R} ^{n}\)が存在しない場合です。これは、係数行列\(A\)を構成する何らかの線型独立な\(r-1\)個の列ベクトル集合\begin{equation*}\left\{ \boldsymbol{a}_{\left( 1\right) },\cdots ,\boldsymbol{a}_{\left(
r-1\right) }\right\} \subset \left\{ \boldsymbol{a}_{1},\cdots ,\boldsymbol{a}_{n}\right\}
\end{equation*}と、何らかの行ベクトル\(\boldsymbol{y}\in M_{1,m}\left( \mathbb{R} \right) \)の中に、以下の条件\begin{eqnarray*}&&\left( a\right) \ \forall j\in \left\{ 1,\cdots ,r-1\right\} :\boldsymbol{ya}_{\left( j\right) }=0 \\
&&\left( b\right) \ \forall j\in \left\{ 1,\cdots ,n\right\} :\boldsymbol{ya}_{j}\geq 0 \\
&&\left( c\right) \ \boldsymbol{yb}<0
\end{eqnarray*}を満たすものが存在することとして表現されます。方向ベクトル\(\boldsymbol{y}\)と直交するとともに原点を通過する超平面は、\begin{equation*}H\left( \boldsymbol{y},0\right) =\left\{ \boldsymbol{x}\in M_{m,1}\left( \mathbb{R} \right) \ |\ \boldsymbol{yx}=0\right\}
\end{equation*}と表現されるため、条件\(\left( a\right) \)は、係数行列\(A\)を構成する線型独立な\(r-1\)個の列ベクトル\(\boldsymbol{a}_{\left( 1\right) },\cdots ,\boldsymbol{a}_{\left( r-1\right)}\)が何らかの超平面\(H\left( \boldsymbol{y},0\right) \)上に位置することを意味し、条件\(\left( b\right) ,\left( c\right) \)は、その超平面\(H\left( \boldsymbol{y},0\right) \)によってベクトル\(\boldsymbol{a}_{1},\cdots ,\boldsymbol{a}_{n}\)とベクトル\(\boldsymbol{b}\)が分離されることを意味します。

以上の命題を線型不等式の基本定理(fundamental theorem of linear inequalities)と呼びます。

命題(線型不等式の基本定理)
係数行列\(A\in M_{m,n}\left( \mathbb{R} \right) \)と定数ベクトル\(\boldsymbol{b}\in M_{m,1}\left( \mathbb{R} \right) \)が与えられているものとする。係数行列\(A\)の第\(j\in \left\{ 1,\cdots ,n\right\} \)列ベクトルを、\begin{equation*}\boldsymbol{a}_{j}\in M_{m,1}\left( \mathbb{R} \right)
\end{equation*}で表記する。さらに、\begin{equation*}
r=\mathrm{rank}\left( A\right)
\end{equation*}とする。このとき、以下の2つのケースのどちらか一方が成り立つ。

  1. \(k\leq n\)を満たす何らかの番号\(k\in \mathbb{N} \)に対して、以下の条件\begin{equation*}\left\{ \boldsymbol{a}_{\left( 1\right) },\cdots ,\boldsymbol{a}_{\left(k\right) }\right\} \subset \left\{ \boldsymbol{a}_{1},\cdots ,\boldsymbol{a}_{n}\right\}
    \end{equation*}を満たす線型独立なベクトル集合\(\left\{ \boldsymbol{a}_{\left( 1\right) },\cdots ,\boldsymbol{a}_{\left( k\right) }\right\} \)が存在して、\begin{equation*}\exists \lambda _{1},\cdots ,\lambda _{k}\geq 0:\boldsymbol{b}=\lambda _{1}\boldsymbol{a}_{\left( 1\right) }+\cdots +\lambda _{k}\boldsymbol{a}_{\left(
    k\right) }
    \end{equation*}が成り立つ。
  2. 係数行列\(A\)を構成する何らかの線型独立な\(r-1\)個の列ベクトル集合\begin{equation*}\left\{ \boldsymbol{a}_{\left( 1\right) },\cdots ,\boldsymbol{a}_{\left(r-1\right) }\right\} \subset \left\{ \boldsymbol{a}_{1},\cdots ,\boldsymbol{a}_{n}\right\}
    \end{equation*}と何らかの行ベクトル\(\boldsymbol{y}\in M_{1,m}\left( \mathbb{R} \right) \)の中に、以下の条件\begin{eqnarray*}&&\left( a\right) \ \forall j\in \left\{ 1,\cdots ,r-1\right\} :\boldsymbol{ya}_{\left( j\right) }=0 \\
    &&\left( b\right) \ \forall j\in \left\{ 1,\cdots ,n\right\} :\boldsymbol{ya}_{j}\geq 0 \\
    &&\left( c\right) \ \boldsymbol{yb}<0
    \end{eqnarray*}を満たすものが存在する。
証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

 

アルゴリズムの適用例:ケース1

先の命題の証明において提示したアルゴリズムの適用例を提示します。まずはケース1の場合です。

例(非負の解を持つ連立1次方程式)
変数\(x_{1},x_{2},x_{3}\in \mathbb{R} \)に関する連立1次方程式\begin{equation*}\left\{
\begin{array}{c}
x_{2}+x_{3}=1 \\
x_{1}+x_{2}=\frac{1}{2}\end{array}\right.
\end{equation*}が与えられているものとします。係数行列と定数ベクトルは、\begin{eqnarray*}
A &=&\left( \boldsymbol{a}_{1},\boldsymbol{a}_{2},\boldsymbol{a}_{3}\right) =\begin{pmatrix}
0 & 1 & 1 \\
1 & 1 & 0\end{pmatrix}\in M_{2,3}\left( \mathbb{R} \right) \\
\boldsymbol{b} &=&\left(
\begin{array}{c}
1 \\
\frac{1}{2}\end{array}\right) \in M_{2,1}\left( \mathbb{R} \right)
\end{eqnarray*}です。係数行列の列ベクトルと定数ベクトルを以下に図示しました。

図:列ベクトルと定数ベクトル
図:列ベクトルと定数ベクトル

図より、\(\boldsymbol{b}\)を\(\left\{ \boldsymbol{a}_{2},\boldsymbol{a}_{3}\right\} \)の錐結合として表せることが直感的に明らかであるため、この連立1次方程式は非負の解を持つことが予想されます。つまり、パターン1のケースであることです。同じことを先のアルゴリズムを用いて確認します。係数行列の階数は、\begin{equation*}\mathrm{rank}\left( A\right) =2
\end{equation*}です。そこで、2つの線型独立な列ベクトル\begin{equation*}
D_{1}=\left\{ \boldsymbol{a}_{1},\boldsymbol{a}_{2}\right\}
\end{equation*}を選びます(下図)。

図:ベクトルの選定
図:ベクトルの選定

その上で、\begin{equation*}
\boldsymbol{b}=\lambda _{1}\boldsymbol{a}_{1}+\lambda _{2}\boldsymbol{a}_{2}
\end{equation*}とおくと、\begin{equation*}
\lambda _{1}<0
\end{equation*}となるため、\(D_{1}\)から\(\boldsymbol{a}_{1}\)を消去することにより\(\left\{ \boldsymbol{a}_{2}\right\} \)を得ます。以下の行ベクトル\begin{equation*}\boldsymbol{y}=\left( -1,1\right)
\end{equation*}を選べば、\begin{eqnarray*}
\boldsymbol{ya}_{2} &=&\left( -1,1\right) \left(
\begin{array}{c}
1 \\
1\end{array}\right) =0 \\
\boldsymbol{ya}_{1} &=&\left( -1,1\right) \left(
\begin{array}{c}
0 \\
1\end{array}\right) =1 \\
\boldsymbol{yb} &=&\left( -1,1\right) \left(
\begin{array}{c}
1 \\
\frac{1}{2}\end{array}\right) =-\frac{1}{2}<0
\end{eqnarray*}が成り立ちます。その一方で、\begin{equation*}
\boldsymbol{ya}_{3}=\left( -1,1\right) \left(
\begin{array}{c}
1 \\
0\end{array}\right) =-1<0
\end{equation*}であるため、次のサイクルへ進みます。具体的には、\(D_{1}\)中の\(\boldsymbol{a}_{1}\)を\(\boldsymbol{a}_{3}\)に入れ替えると、\begin{equation*}D_{2}=\left\{ \boldsymbol{a}_{2},\boldsymbol{a}_{3}\right\}
\end{equation*}を得ます(下図)。

図:ベクトルの選定
図:ベクトルの選定

その上で、\begin{equation*}
\boldsymbol{b}=\lambda _{2}\boldsymbol{a}_{2}+\lambda _{3}\boldsymbol{a}_{3}
\end{equation*}とおくと、\begin{eqnarray*}
\lambda _{2} &=&\frac{1}{2}\geq 0 \\
\lambda _{3} &=&\frac{1}{2}\geq 0
\end{eqnarray*}となるためプロセスを終了します。以上より、これはケース1であることが明らかになりました。実際、\begin{equation*}
\left(
\begin{array}{c}
x_{1} \\
x_{2} \\
x_{3}\end{array}\right) =\left(
\begin{array}{c}
0 \\
\frac{1}{2} \\
\frac{1}{2}\end{array}\right)
\end{equation*}は与えられた連立1次方程式の非負解です。

 

アルゴリズムの適用例:ケース2

続いてケース2の場合です。

例(非負の解を持たない連立1次方程式)
変数\(x_{1},x_{2},x_{3}\in \mathbb{R} \)に関する連立1次方程式\begin{equation*}\left\{
\begin{array}{c}
x_{2}+x_{3}=1 \\
x_{1}+x_{2}=-1\end{array}\right.
\end{equation*}が与えられているものとします。係数行列と定数ベクトルは、\begin{eqnarray*}
A &=&\left( \boldsymbol{a}_{1},\boldsymbol{a}_{2},\boldsymbol{a}_{3}\right) =\begin{pmatrix}
0 & 1 & 1 \\
1 & 1 & 0\end{pmatrix}\in M_{2,3}\left( \mathbb{R} \right) \\
\boldsymbol{b} &=&\left(
\begin{array}{c}
1 \\
-1\end{array}\right) \in M_{2,1}\left( \mathbb{R} \right)
\end{eqnarray*}です。係数行列の列ベクトルと定数ベクトルを以下に図示しました。

図:列ベクトルと定数ベクトル
図:列ベクトルと定数ベクトル

図より、\(\boldsymbol{b}\)を列ベクトル\(\boldsymbol{a}_{1},\boldsymbol{a}_{2},\boldsymbol{a}_{3}\)の錐結合として表せないことが直感的に明らかであるため、この連立1次方程式は非負の解を持たないことが予想されます。つまり、パターン2のケースであることです。同じことを先のアルゴリズムを用いて確認します。係数行列の階数は、\begin{equation*}\mathrm{rank}\left( A\right) =2
\end{equation*}です。そこで、2つの線型独立な列ベクトル\begin{equation*}
D_{1}=\left\{ \boldsymbol{a}_{1},\boldsymbol{a}_{2}\right\}
\end{equation*}を選びます(下図)。

図:ベクトルの選定
図:ベクトルの選定

その上で、\begin{equation*}
\boldsymbol{b}=\lambda _{1}\boldsymbol{a}_{1}+\lambda _{2}\boldsymbol{a}_{2}
\end{equation*}とおくと、\begin{equation*}
\lambda _{1}<0
\end{equation*}となるため、\(D_{1}\)から\(\boldsymbol{a}_{1}\)を消去することにより\(\left\{ \boldsymbol{a}_{2}\right\} \)を得ます。以下の行ベクトル\begin{equation*}\boldsymbol{y}=\left( -1,1\right)
\end{equation*}を選べば、\begin{eqnarray*}
\boldsymbol{ya}_{2} &=&\left( -1,1\right) \left(
\begin{array}{c}
1 \\
1\end{array}\right) =0 \\
\boldsymbol{ya}_{1} &=&\left( -1,1\right) \left(
\begin{array}{c}
0 \\
1\end{array}\right) =1 \\
\boldsymbol{yb} &=&\left( -1,1\right) \left(
\begin{array}{c}
1 \\
-1\end{array}\right) =-2<0
\end{eqnarray*}が成り立ちます。その一方で、\begin{equation*}
\boldsymbol{ya}_{3}=\left( -1,1\right) \left(
\begin{array}{c}
1 \\
0\end{array}\right) =-1<0
\end{equation*}であるため、次のサイクルへ進みます。具体的には、\(D_{1}\)中の\(\boldsymbol{a}_{1}\)を\(\boldsymbol{a}_{3}\)に入れ替えると、\begin{equation*}D_{2}=\left\{ \boldsymbol{a}_{2},\boldsymbol{a}_{3}\right\}
\end{equation*}を得ます(下図)。

図:ベクトルの選定
図:ベクトルの選定

その上で、\begin{equation*}
\boldsymbol{b}=\lambda _{2}\boldsymbol{a}_{2}+\lambda _{3}\boldsymbol{a}_{3}
\end{equation*}とおくと、\begin{equation*}
\lambda _{2}<0
\end{equation*}となるため、\(D_{1}\)から\(\boldsymbol{a}_{2}\)を消去することにより\(\left\{ \boldsymbol{a}_{3}\right\} \)を得ます。以下の行ベクトル\begin{equation*}\boldsymbol{y}=\left( 0,1\right)
\end{equation*}を選べば、\begin{eqnarray*}
\boldsymbol{ya}_{3} &=&\left( 0,1\right) \left(
\begin{array}{c}
1 \\
0\end{array}\right) =0 \\
\boldsymbol{ya}_{2} &=&\left( 0,1\right) \left(
\begin{array}{c}
1 \\
1\end{array}\right) =1 \\
\boldsymbol{yb} &=&\left( 0,1\right) \left(
\begin{array}{c}
1 \\
-1\end{array}\right) =-1<0
\end{eqnarray*}が成り立ちます。さらに、\begin{equation*}
\boldsymbol{ya}_{1}=\left( 0,1\right) \left(
\begin{array}{c}
0 \\
1\end{array}\right) =1
\end{equation*}であるため、プロセスを終了します。以上より、これはケース2であることが明らかになりました。実際、ベクトル\(\boldsymbol{y}\)を法線ベクトルとする超平面(\(x\)軸)によって列ベクトル\(\boldsymbol{a}_{1},\boldsymbol{a}_{2},\boldsymbol{a}_{3}\)と定数ベクトル\(\boldsymbol{b}\)が分離されています。

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員専用コンテンツです
ログイン】【会員登録