数値解析の問題

難易度 3期末試験の応用レベル証明問題大学数学数値解析

$n \geq 2$ とし、 $A = (a_{ij})$ を $n$ 次実正方行列で、狭義の行対角優位、すなわち
$∣ a_{ii} ∣ > j \neq = i \sum ∣ a_{ij} ∣ (i = 1, 2, \dots, n)$
を満たすものとする。 $A = D - L - U$ と分解する。ここで $D$ は $A$ の対角成分からなる対角行列、 $- L$ は $A$ の狭義下三角部分（ $j < i$ の成分 $a_{ij}$ だけを残した行列）、 $- U$ は $A$ の狭義上三角部分（ $j > i$ の成分だけを残した行列）である。ヤコビ法とガウス・ザイデル法の反復行列をそれぞれ
$M_{J} = D^{- 1} (L + U), M_{G} = (D - L)^{- 1} U$
とする。ベクトルの最大値ノルム $∥ x ∥_{\infty} = max_{i} ∣ x_{i} ∣$ と、それから誘導される行列ノルム $∥ M ∥_{\infty} = max_{∥ x ∥_{\infty} = 1} ∥ M x ∥_{\infty}$ を用いる。このとき
$∥ M_{G} ∥_{\infty} \leq ∥ M_{J} ∥_{\infty} < 1$
が成り立つことを証明せよ。ただし、誘導ノルムについて $∥ M ∥_{\infty} = max_{i} \sum_{j} ∣ m_{ij} ∣$ （最大行和）となることは用いてよい。

この問題で使うもの

ヤコビ法・ガウス・ザイデル法の収束（説明と入口の問題）
行列のノルムと条件数（説明と入口の問題）

この問題を解けるようになるまで（56 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

$∥ M_{J} ∥_{\infty}$ は最大行和の公式で直接計算できます。 $∥ M_{G} ∥_{\infty}$ は、 $∥ x ∥_{\infty} = 1$ のベクトル $x$ に対して $y = M_{G} x$ の最大値ノルムを上から評価する方針で考えましょう。

ヒント 2

各行で $l_{i} = \sum_{j < i} ∣ a_{ij} ∣/∣ a_{ii} ∣$ , $u_{i} = \sum_{j > i} ∣ a_{ij} ∣/∣ a_{ii} ∣$ とおくと $∥ M_{J} ∥_{\infty} = max_{i} (l_{i} + u_{i})$ です。 $y$ は $(D - L) y = U x$ を満たすので、成分で書くと $y_{i}$ が $y_{1}, \dots, y_{i - 1}$ と $x_{i + 1}, \dots, x_{n}$ で表せます。

ヒント 3

$∣ y_{k} ∣ = ∥ y ∥_{\infty}$ となる $k$ をとると、 $∣ y_{k} ∣ \leq l_{k} ∣ y_{k} ∣ + u_{k}$ が得られ、 $∥ y ∥_{\infty} \leq u_{k} / (1 - l_{k})$ となります。あとはこの値と $l_{k} + u_{k}$ の大小を比べます。

採点の観点と模範解答

自分で証明を書いてから、採点の観点で見比べてください。

採点の観点を見る

狭義行対角優位性から $a_{ii} \neq = 0$ を導き、 $D^{- 1}$ と $(D - L)^{- 1}$ が存在することを述べている（1 点）
最大行和の公式で $∥ M_{J} ∥_{\infty} = max_{i} \sum_{j \neq = i} ∣ a_{ij} ∣/∣ a_{ii} ∣$ を求め、対角優位性からこれが $1$ 未満であることを示している（2 点）
$∥ x ∥_{\infty} = 1$ に対し $y = M_{G} x$ が $(D - L) y = U x$ を満たすことを成分で書き、 $y_{i}$ を前の $y_{j}$ と後ろの $x_{j}$ で表している（2 点）
$∣ y_{k} ∣ = ∥ y ∥_{\infty}$ となる $k$ をとり、三角不等式で $∣ y_{k} ∣ \leq l_{k} ∣ y_{k} ∣ + u_{k}$ 、さらに $1 - l_{k} > 0$ を確認して $∣ y_{k} ∣ \leq u_{k} / (1 - l_{k})$ を導いている（3 点）
$u_{k} / (1 - l_{k}) \leq l_{k} + u_{k}$ を $l_{k} (1 - l_{k} - u_{k}) \geq 0$ に帰着して示し、 $x$ の任意性から $∥ M_{G} ∥_{\infty} \leq ∥ M_{J} ∥_{\infty}$ と結論している（2 点）

結果を記録する（このブラウザにだけ保存されます）:

模範解答を読む

準備. 各 $i$ について
$l_{i} = \frac{1}{∣ a _{ii} ∣} j < i \sum ∣ a_{ij} ∣, u_{i} = \frac{1}{∣ a _{ii} ∣} j > i \sum ∣ a_{ij} ∣$
とおく（和が空のときは $0$ ）。狭義の行対角優位性より $∣ a_{ii} ∣ > \sum_{j \neq = i} ∣ a_{ij} ∣ \geq 0$ なので $a_{ii} \neq = 0$ であり、 $l_{i}$ , $u_{i}$ は定義でき、両辺を $∣ a_{ii} ∣ > 0$ で割って
$l_{i} + u_{i} < 1 (i = 1, \dots, n) (1)$
を得る。また $l_{i} \geq 0$ , $u_{i} \geq 0$ である。

$∥ M_{J} ∥_{\infty}$ の計算. $D$ の対角成分はすべて $0$ でないので $D^{- 1}$ が存在する。 $L + U$ の $(i, j)$ 成分は $j \neq = i$ のとき $- a_{ij}$ 、 $j = i$ のとき $0$ であるから、 $M_{J} = D^{- 1} (L + U)$ の $(i, j)$ 成分は $j \neq = i$ のとき $- a_{ij} / a_{ii}$ 、 $j = i$ のとき $0$ である。最大行和の公式より
$ρ := ∥ M_{J} ∥_{\infty} = i max j \neq = i \sum \frac{∣ a _{ij} ∣}{∣ a _{ii} ∣} = i max (l_{i} + u_{i}) .$
$(1)$ より各 $l_{i} + u_{i} < 1$ で、 $i$ は有限個なので $ρ < 1$ である。

$M_{G}$ が定義できること. $D - L$ は対角成分が $a_{11}, \dots, a_{nn}$ の下三角行列で、その行列式は $a_{11} a_{22} \dots a_{nn} \neq = 0$ だから正則であり、 $M_{G} = (D - L)^{- 1} U$ は定義できる。

$∥ M_{G} ∥_{\infty} \leq ρ$ の証明. $∥ x ∥_{\infty} = 1$ を満たす任意の $x \in R^{n}$ をとり、 $y = M_{G} x$ とおく。 $(D - L) y = U x$ である。 $D - L$ の第 $i$ 行は、 $j < i$ で $a_{ij}$ 、 $j = i$ で $a_{ii}$ 、 $j > i$ で $0$ であり、 $U$ の第 $i$ 行は $j > i$ で $- a_{ij}$ 、それ以外で $0$ であるから、第 $i$ 成分を比べると
$a_{ii} y_{i} + j < i \sum a_{ij} y_{j} = - j > i \sum a_{ij} x_{j},$
すなわち
$y_{i} = - \frac{1}{a _{ii}} (j < i \sum a_{ij} y_{j} + j > i \sum a_{ij} x_{j}) (i = 1, \dots, n) (2)$
である。 $∣ y_{k} ∣ = ∥ y ∥_{\infty}$ となる添字 $k$ を 1 つとる。 $(2)$ で $i = k$ とし、三角不等式と $∣ y_{j} ∣ \leq ∣ y_{k} ∣$ , $∣ x_{j} ∣ \leq ∥ x ∥_{\infty} = 1$ を用いると
$∣ y_{k} ∣ \leq \frac{1}{∣ a _{k k} ∣} (j < k \sum ∣ a_{k j} ∣∣ y_{k} ∣ + j > k \sum ∣ a_{k j} ∣) = l_{k} ∣ y_{k} ∣ + u_{k} .$
よって $(1 - l_{k}) ∣ y_{k} ∣ \leq u_{k}$ である。 $(1)$ と $u_{k} \geq 0$ より $l_{k} < 1$ 、つまり $1 - l_{k} > 0$ なので
$∥ y ∥_{\infty} = ∣ y_{k} ∣ \leq \frac{u _{k}}{1 - l _{k}} . (3)$
次に $\frac{u _{k}}{1 - l _{k}} \leq l_{k} + u_{k}$ を示す。 $1 - l_{k} > 0$ を掛けると、これは
$u_{k} \leq (l_{k} + u_{k}) (1 - l_{k}) = l_{k} + u_{k} - l_{k}^{2} - l_{k} u_{k}$
と同値であり、移項すると $0 \leq l_{k} (1 - l_{k} - u_{k})$ となる。 $l_{k} \geq 0$ と $(1)$ より $1 - l_{k} - u_{k} > 0$ なので、これは成り立つ。したがって $(3)$ と合わせて
$∥ M_{G} x ∥_{\infty} = ∥ y ∥_{\infty} \leq l_{k} + u_{k} \leq i max (l_{i} + u_{i}) = ρ .$
$x$ は $∥ x ∥_{\infty} = 1$ を満たす任意のベクトルだったから、誘導ノルムの定義より $∥ M_{G} ∥_{\infty} \leq ρ$ である。

結論. 以上より
$∥ M_{G} ∥_{\infty} \leq ∥ M_{J} ∥_{\infty} = ρ < 1$
が示された。（特に、ガウス・ザイデル法の誤差 $e^{(m)}$ は $∥ e^{(m)} ∥_{\infty} \leq ρ^{m} ∥ e^{(0)} ∥_{\infty}$ を満たし、任意の初期値から収束する。）

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が模範解答を見ずに 3 回証明を試み、3 回証明できました
2 つの AI が独立に、模範解答の証明を 1 ステップずつ確かめました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる