後退代入

この章の目標

上三角行列の連立方程式を後退代入で解く方法を理解し、前進代入との対比で LU 分解の全体像を把握する。

前提知識

目次

1. 定義と原理

後退代入（back substitution）は、上三角行列 $U$ を係数行列とする連立一次方程式

$$U\mathbf{x} = \mathbf{b}$$

を解くアルゴリズムである。上三角行列では $u_{ij} = 0 \; (i > j)$ であるから、最後の行は1変数のみの方程式 $u_{nn} x_n = b_n$ となり、ここから $x_n$ が直ちに求まる。得られた $x_n$ を一つ上の行に代入すれば $x_{n-1}$ が求まり、これを繰り返すことで全ての変数を決定できる。

展開して書くと

$$\begin{pmatrix} u_{11} & u_{12} & \cdots & u_{1n} \\ 0 & u_{22} & \cdots & u_{2n} \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & u_{nn} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{pmatrix} = \begin{pmatrix} b_1 \\ b_2 \\ \vdots \\ b_n \end{pmatrix}$$

であり、$u_{ii} \neq 0$（$U$ が非特異）であれば解が一意に存在する。

後退代入：上三角行列 Ux=b を下から上へ解く順序 U 2 1 −1 0 3 2 0 0 4 x₁ x₂ x₃ = 8 7 4 下から上へ 1 2 3 1 最終行は未知数1つ：　4·x₃ = 4 → x₃ = 4 / 4 = 1　（即座に確定） 2 確定した x₃ を上の行へ代入：　3·x₂ + 2·(1) = 7 → x₂ = (7 − 2) / 3 = 5/3 3 さらに上の行へ：　2·x₁ + (5/3) − (1) = 8 → x₁ = (8 − 5/3 + 1) / 2 = 11/3 各 xᵢ = ( bᵢ − 既知項の和 ) / uᵢᵢ　（対角要素で割る）
図1. 後退代入の流れ。上三角行列 $U$ は対角の下がすべて $0$（ゼロの階段）なので、最終行 $4x_3=4$ は未知数が $1$ つだけ。$x_3$ を確定して一つ上の行へ代入し $x_2$ を、さらに上へ代入して $x_1$ を求める。①②③の順、すなわち下から上へ解いていく。各成分は $x_i = \left(b_i - \sum_{j>i} u_{ij}x_j\right)/u_{ii}$ で得られる。

2. 公式

$$x_n = \dfrac{b_n}{u_{nn}}$$
$$x_i = \dfrac{1}{u_{ii}} \left(b_i - \displaystyle\sum_{j=i+1}^{n} u_{ij} x_j\right), \quad i = n-1, n-2, \ldots, 1$$

各 $x_i$ は、右辺 $b_i$ から既に求まっている $x_{i+1}, \ldots, x_n$ の寄与を差し引いた後、対角要素 $u_{ii}$ で割ることで得られる。

3. アルゴリズム

function backSubstitution(U, b, n):
    x[n] = b[n] / U[n][n]
    for i = n-1 downto 1:
        sum = 0
        for j = i+1 to n:
            sum = sum + U[i][j] * x[j]
        x[i] = (b[i] - sum) / U[i][i]
    return x

内側のループは $i$ に応じて $n - i$ 回の乗算と加算を行う。

4. 計算量

$n \times n$ の上三角行列に対する後退代入の演算回数は以下の通りである。

演算回数
除算$n$
乗算$\dfrac{n(n-1)}{2}$
加減算$\dfrac{n(n-1)}{2}$
合計$n^2$ （$O(n^2)$）

ガウスの消去法の前方消去（$O(n^3/3)$）と比べて、後退代入のコストは非常に軽い。全体の計算量に占める割合は小さいが、前方消去で蓄積した丸め誤差に注意が必要である。

5. ガウス消去法・LU分解での位置づけ

ガウスの消去法は2つのフェーズからなる。

  1. 前方消去（forward elimination）: 拡大係数行列に行基本変形を施し、上三角形に変形する。$O(n^3/3)$。
  2. 後退代入（back substitution）: 上三角系を解く。$O(n^2/2)$。

LU 分解 $A = LU$ を用いる場合は

  1. $L\mathbf{y} = \mathbf{b}$ を前進代入で解く。$O(n^2/2)$。
  2. $U\mathbf{x} = \mathbf{y}$ を後退代入で解く。$O(n^2/2)$。

LU 分解を一度計算しておけば、異なる右辺ベクトル $\mathbf{b}$ に対して前進代入＋後退代入の $O(n^2)$ のみで解が得られる。

6. 数値安定性

後退代入自体は後退安定（backward stable）であり、丸め誤差の増大は穏やかである。ただし以下の点に注意が必要である。

  • 対角要素 $u_{ii}$ が非常に小さい場合、除算によって誤差が増幅される。
  • 前方消去で蓄積した誤差は後退代入で取り除けない。ピボット選択が重要である。
  • $U$ の条件数 $\kappa(U)$ が大きい場合、結果の精度は $\varepsilon_{\mathrm{mach}} \cdot \kappa(U)$ のオーダーで劣化する。

7. 計算例

例1: 3×3 上三角系

$\begin{pmatrix} 2 & 1 & -1 \\ 0 & 3 & 2 \\ 0 & 0 & 4 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 8 \\ 7 \\ 4 \end{pmatrix}$

ステップ計算結果
$x_3$$4 / 4$$x_3 = 1$
$x_2$$(7 - 2 \times 1) / 3$$x_2 = 5/3$
$x_1$$(8 - 1 \times 5/3 - (-1) \times 1) / 2$$x_1 = 11/3$

解は $\mathbf{x} = (11/3,\; 5/3,\; 1)^T$ である。

8. よくある質問

Q1. 後退代入とは？

上三角行列 $U\mathbf{x} = \mathbf{b}$ を最後の変数 $x_n$ から順に求めていくアルゴリズムである。ガウスの消去法やLU分解の最終ステップとして不可欠である。

Q2. 計算量はいくらですか？

$n \times n$ の上三角行列に対して $O(n^2)$ である。ガウスの消去法の前方消去 $O(n^3)$ と比べてはるかに軽い。

Q3. 前進代入との違いは？

後退代入は上三角行列 $U\mathbf{x} = \mathbf{b}$ を逆順に解くのに対し、前進代入は下三角行列 $L\mathbf{y} = \mathbf{b}$ を順方向に解く。LU 分解では両方を組み合わせて使う。

9. 参考資料