線形代数学 第11回 講義ノート

1. 講義情報と予習ガイド

講義回: 第11回
テーマ: ガウスの消去法と解の探索
関連項目: 連立一次方程式、行列の基本変形、ガウスの消去法
予習すべき内容: - 第10回の内容（連立一次方程式の行列表現） - 行列の基本操作の概念

講義資料: こちら 演習資料: こちら

2. 学習目標

本講義の終了時には以下の能力を身につけることを目標とします:

1. 連立一次方程式の行列表現と拡大係数行列の概念を理解する
2. 行列の基本変形の種類と性質を理解する
3. ガウスの消去法のアルゴリズムを理解し実行できる
4. ガウスの消去法と連立方程式の消去法の関係を理解する

3. 基本概念

3.1 連立一次方程式の行列表現と拡大係数行列（復習）

連立一次方程式は行列と係数ベクトルを用いて簡潔に表すことができます。一般的な形式は以下の通りです:

\[ \begin{cases} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n = b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n = b_2 \\ \vdots \\ a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n = b_m \end{cases} \]

この連立方程式は行列形式で次のように表現できます:

\[\mathbf{A}\mathbf{x} = \mathbf{b}\]

ここで、

\[\mathbf{A} = \begin{pmatrix} 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{pmatrix}, \quad \mathbf{x} = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix}, \quad \mathbf{b} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_m \end{pmatrix} \]

連立方程式を解く際には、係数行列と定数項をまとめた拡大係数行列（augmented matrix）を考えると便利です:

\[\left(\mathbf{A} | \mathbf{b}\right) = \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1n} & | & b_1 \\ a_{21} & a_{22} & \cdots & a_{2n} & | & b_2 \\ \vdots & \vdots & \ddots & \vdots & | & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} & | & b_m \end{pmatrix} \]

3.2 行列の基本変形

行列の基本変形は、連立方程式の解を変えずに行列の形を変える操作です。主に3種類の基本変形があります:

行列の基本変形の定義: 1. 行の交換（Row Exchange）: 2つの行を入れ替える 2. 行のスカラー倍（Row Scaling）: ある行の全ての要素を0でない定数倍する 3. 行の加減（Row Addition）: ある行の定数倍を別の行に加える

これらの基本変形は連立方程式の解を変えないという重要な性質があります。

行列の基本変形の具体例

1. 行の交換（Row Exchange）: 行列の2つの行を入れ替える操作です。例えば、以下の行列の第1行と第2行を交換すると:

\[ \begin{pmatrix} 1 & 2 & 3 \\\ 4 & 5 & 6 \\\ 7 & 8 & 9 \end{pmatrix} \rightarrow \begin{pmatrix} 4 & 5 & 6 \\\ 1 & 2 & 3 \\\ 7 & 8 & 9 \end{pmatrix} \]

このような操作は連立方程式の解には影響しません。なぜなら、方程式の順序を入れ替えただけで、方程式の内容自体は変わっていないからです。

1. 行のスカラー倍（Row Scaling）: 行列のある行の全ての要素を0でない定数倍する操作です。例えば、以下の行列の第2行を2倍すると:

\[ \begin{pmatrix} 1 & 2 & 3 \\\ 4 & 5 & 6 \\\ 7 & 8 & 9 \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 2 & 3 \\\ 8 & 10 & 12 \\\ 7 & 8 & 9 \end{pmatrix} \]

これは連立方程式では、2番目の方程式の両辺を2倍することに相当します。例えば:

\[4x + 5y + 6z = 10 \quad \rightarrow \quad 8x + 10y + 12z = 20\]

方程式の両辺を同じ定数倍しても、解は変わりません。

1. 行の加減（Row Addition）: ある行の定数倍を別の行に加える操作です。例えば、第1行の(-4)倍を第2行に加えると:

\[ \begin{pmatrix} 1 & 2 & 3 \\\ 4 & 5 & 6 \\\ 7 & 8 & 9 \end{pmatrix} \rightarrow \begin{pmatrix} 1 & 2 & 3 \\\ 0 & -3 & -6 \\\ 7 & 8 & 9 \end{pmatrix} \]

これは連立方程式では、第1方程式の(-4)倍を第2方程式に加えることに相当します:

\[ \begin{cases} x + 2y + 3z = 10 \\\ 4x + 5y + 6z = 20 \end{cases} \quad \rightarrow \quad \begin{cases} x + 2y + 3z = 10 \\\ -3y - 6z = -20 \end{cases} \]

この操作により、第2方程式からx変数が消去されました。しかし、連立方程式全体としては同じ解を持ちます。

これらの基本変形を組み合わせることで、行列を望ましい形（上三角形や対角形など）に変形することができます。例えば、以下の拡大係数行列を考えます:

\[ \begin{pmatrix} 1 & 3 & | & 5 \\ 2 & 7 & | & 11 \end{pmatrix} \]

連立方程式の解を変えずに、第1行の(-2)倍を第2行に加えると:

\[ \begin{pmatrix} 1 & 3 & | & 5 \\ 0 & 1 & | & 1 \end{pmatrix} \]

これは元の連立方程式:

\[ \begin{cases} x + 3y = 5 \\ 2x + 7y = 11 \end{cases} \]

が以下に変形されたことを意味します:

\[ \begin{cases} x + 3y = 5 \\ y = 1 \end{cases} \]

この変形により、連立方程式を後退代入で簡単に解くことができます。

3.3 ガウスの消去法の概念

ガウスの消去法は、基本変形を用いて拡大係数行列を特定の形（上三角形または階段形）に変形することで連立方程式を解くアルゴリズムです。

ガウスの消去法: 拡大係数行列に基本変形を施し、係数行列を上三角行列または階段行列に変形する方法。

ガウスの消去法には主に二つの段階があります: 1. 前進消去（Forward Elimination）: 係数行列を上三角行列に変形する 2. 後退代入（Back Substitution）: 上三角行列の形の連立方程式を解く

4. 理論と手法

4.1 ガウスの消去法の手順

ガウスの消去法のアルゴリズムは以下の通りです:

1. 拡大係数行列の作成: 連立方程式から拡大係数行列を作成
2. 前進消去:
3. 左上から始め、その列の対角成分（ピボット）を基準にする
4. ピボット以下の要素をすべて0にするように基本変形を行う
5. 次の列に移動し同様の操作を繰り返す
6. 後退代入: 変形された方程式を最後の変数から順に解いていく

4.2 ガウスの消去法の詳細アルゴリズム

より数学的に厳密に記述すると、ガウスの消去法の前進消去段階は以下のようになります:

1. \(i = 1\) から \(n-1\) まで以下の操作を繰り返す:
2. ピボット要素 \(a_{ii}\) を選ぶ
3. \(j = i + 1\) から \(m\) まで以下の操作を行う:
   • 係数 \(\mu_{ji} = a_{ji}/a_{ii}\) を計算
   • 行 \(j\) から 行 \(i\) の \(\mu_{ji}\) 倍を引く: \(\text{row}_j \leftarrow \text{row}_j - \mu_{ji} \cdot \text{row}_i\)

4.3 後退代入の手順

上三角行列に変形された連立方程式を解くための後退代入は以下のように行います:

1. 最後の変数 \(x_n\) を計算: \(x_n = b_n/a_{nn}\)
2. \(i = n-1\) から \(1\) まで逆順に以下を計算: \(\(x_i = \frac{1}{a_{ii}}\left(b_i - \sum_{j=i+1}^{n}a_{ij}x_j\right)\)\)

4.4 計算例: 3変数の連立方程式

以下の連立方程式を考えます:

\[ \begin{cases} 2x + y - z = 8 \\ -3x - y + 2z = -11 \\ -2x + y + 2z = -3 \end{cases} \]

ステップ 1: 拡大係数行列を作成

\[ \begin{pmatrix} 2 & 1 & -1 & | & 8 \\ -3 & -1 & 2 & | & -11 \\ -2 & 1 & 2 & | & -3 \end{pmatrix} \]

ステップ 2: 前進消去を行う

まず、第1列の第1行以下の要素を0にします:

• 第2行に第1行の\(\frac{3}{2}\)倍を加える:

\[ \begin{pmatrix} 2 & 1 & -1 & | & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & | & 1 \\ -2 & 1 & 2 & | & -3 \end{pmatrix} \]

• 第3行に第1行の1倍を加える:

\[ \begin{pmatrix} 2 & 1 & -1 & | & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & | & 1 \\ 0 & 2 & 1 & | & 5 \end{pmatrix} \]

次に、第2列の第2行以下の要素を0にします:

• 第3行から第2行の4倍を引く:

\[ \begin{pmatrix} 2 & 1 & -1 & | & 8 \\ 0 & \frac{1}{2} & \frac{1}{2} & | & 1 \\ 0 & 0 & -1 & | & 1 \end{pmatrix} \]

ステップ 3: 後退代入を行う

変形された連立方程式は:

\[ \begin{cases} 2x + y - z = 8 \\ \frac{1}{2}y + \frac{1}{2}z = 1 \\ -z = 1 \end{cases} \]

まず \(z = -1\) を求めます。

次に \(y\) を求めます: \(\frac{1}{2}y + \frac{1}{2} \cdot (-1) = 1\) より \(y = 3\)

最後に \(x\) を求めます: \(2x + 3 - (-1) = 8\) より \(x = 2\).

従って、解は \((x, y, z) = (2, 3, -1)\) です。

5. 演習問題

5.1 基本問題

問題1: 以下の連立方程式をガウスの消去法を用いて手計算で解きなさい:

\[ \begin{cases} 3x + 2y - z = 10 \\ -x + 3y + 2z = 5 \\ x - y + z = 0 \end{cases} \]

問題2: 以下の拡大係数行列にガウスの消去法を適用し、上三角行列の形に変形しなさい:

\[ \begin{pmatrix} 1 & 2 & 3 & | & 4 \\ 2 & 5 & 3 & | & 7 \\ 1 & 0 & 8 & | & 9 \end{pmatrix} \]

問題3: 次の連立方程式をガウスの消去法で解き、解が \((x,y,z) = (1,2,3)\) であることを確認しなさい:

\[ \begin{cases} 2x - y + z = 3 \\ x + y + z = 6 \\ x - y + 2z = 8 \end{cases} \]