91

第 8 章 ノルム，条件数，連立一次方程式の誤差解析
ノルムは数値線型代数学に不可欠なツールである。
m × n 行列の mn 個の要素をたった一つの数値にまとめてしまうという能力があってこそ，摂動理論や丸め誤差解析を簡単明瞭な形で表現できるのである。反面，ひどいスケーリングになってしまったり，疎行列のような行列構造を生かしきれないといった問題もあるので，ベクトル・行列の要素単位で数値を見た方がいいケースも多い。それでも誤差解析を行う者にとって，ノルムは価値のある道具であることは間違いないのである。

N.J.Nigham, “Accuracy and Stability of NumericalAlgorithms 2nd ed.”, (SIAM)
p しかし，ベクトル x のノルム ∥x∥ は，たとえば =x2 + y2 とか = |x| + |y| とか = max(|x|, |y|) なので，たとえ何らかの標準化をしたところで，x が電圧で y が電流であるというような場合，どうして ∥x∥ が物理的に意味のある量であると考えられようか。そして，物理的に無意味なものを扱う計算過程を許すような数値計算論が健全であるといえようか。
このような，数値計算の常識以前の常識のことが気にかかるのであるが，著者自身も歯切れのよい解答は持ち合わせていないのが残念である。
伊里正夫・藤野和建「数値計算の常識」(共立出版)

今日の科学技術計算においては大規模な線型計算が多用されるため，理工系初年度で習う線型代数学ではあまり扱わない各種のノルム (norm) という概念が必須のものとなる。ここでは有限次元のベクトルや行列に対するノルムを定義し，その応用として，連立一次方程式の誤差解析とそこで使用する条件数 (condition number) を定義する。

8.1

ベクトルと行列のノルム，条件数ノルムとは，簡単に言うと R や C における絶対値 | · | の拡張概念ということになる。絶対値はa, b ∈ C という二数の「距離」を表現するために用いられるものである。つまり，|a − b| が 0 に近ければ，a, b は「近い」と言える。|a| = |a − 0| であるから，これが 0 に近ければ 0 との距離が近いということになる。よって，ノルムも n 次元空間 Cn もしくは Rn におけるベクトル間の距離を表

第8章

92

ノルム，条件数，連立一次方程式の誤差解析わすものと考えてよい。逆に言えば，距離を表現するに足る性質さえ満たしていれば，それは全てノルムであるということになる。
定義 8.1.1 (ノルムの性質)∀a ∈ Cn (または Rn 以下同様) に対して定義される R への写像 ∥a∥ ∈ R が次の三つの性質を全て満足する時，∥ · ∥ を Cn におけるノルムと呼ぶ。

1. ∀a ∈ Cn (or Rn 以下同様) に対して，∥a∥ ≥ 0となる。

2. ∀α ∈ C(または R 以下同様)，∀a ∈ Cn に対し，
∥αa∥ = |α| · ∥a∥を満足する。

3. ∀a, b ∈ Cn に対し∥a + b∥ ≤ ∥a∥ + ∥b∥ (三角不等式)を満足する。
後で行列のノルムも定義するが，上の条件を全て満足する所は全く同じである。
一般的には次の p ノルムがある。
定義 8.1.2 (p ノルム)a = [a1 · · · an ]T ∈ Cn に対し， nX p 1/p
∥a∥ p =  |ai | i=1をベクトルの p ノルムと呼ぶ。
よく使用されるのは p = 1, 2, ∞ の場合である。これをそれぞれ 1 ノルム, 2 ノルム (またはユークリッドノルム), 無限大ノルムと呼ぶ。

1 ノルム ∥a∥1 =nX|ai |i=1

ユークリッドノルム ∥a∥2 =vt n
X|ai |2=p(a, a)i=1

無限大ノルム ∥a∥∞ = max |ai |ix = [x1 x2 ]T ∈ R2 の時，それぞれのノルムが 1 になる位置を図示したのが図 8.1 である。もし円の定義を，「原点からの距離 (= ノルム) が一定の点の集まり」とするのであれば，これらは全て円ということになる。
数値計算ではベクトル列 x1 , x2 ,..., xk , ... を形成するアルゴリズムが多いが，有限次元の線型空間

C や Rn においては，あるノルムを用いて収束，即ち limk→∞ ∥xk ∥ p = ∥a∥ p となるものが，別のノルn8.1. ベクトルと行列のノルム，条件数

93x21x1-1x1x 1||= 1x 2= 1||||||

x ∞-1||||= 1

図 8.1: ∥x∥1 = ∥x∥2 = ∥x∥∞ = 1 となるベクトルの位置

ムでは発散，即ち limk→∞ ∥xk ∥q = ∞ となってしまう，という事態は起こらない。もちろんその逆も起こらない。実際，任意のベクトル ∥ · ∥ p と ∥ · ∥q との間には，∀x ∈ Cn に対して∥x∥ p ≤ α pq ∥x∥qという定数 α pq ≥ 0 が存在する。よく用いられる 3 つのノルムにおける α pq は表 8.1 のようになる。

表 8.1: 1 ノルム，ユークリッドノルム，無限大ノルム間における α pqp→q↓

1211

√n2∞

1111∞n√n1行列のノルムはベクトルのノルムをベースにして定義されるものが普通である。代表的なものとしては次の p ノルムがある。
定義 8.1.3 (行列の p ノルム)∀A ∈ Mn (C)(または Mn (R) 以下同様) に対し，
∥Ax∥ px,0 ∥x∥ p∥A∥ p = supと定義される ∥ · ∥ p を行列の p ノルムと呼ぶ。

第8章

94ノルム，条件数，連立一次方程式の誤差解析

これによって，行列の 1 ノルム，ユークリッドノルム，無限大ノルムも同様に定義されることになる。
nX∥Ax∥1|ai j |1 ノルム ∥A∥1 = sup= maxjx,0 ∥x∥1i=1q∥Ax∥2
ユークリッドノルム ∥A∥2 = sup= max λi (A∗ A) (ここで λi (A) は A の固有値)
ix,0 ∥x∥2nX
∥Ax∥∞
= max
|ai j |
無限大ノルム ∥A∥∞ = supix,0 ∥x∥∞j=1

なお，行列の p ノルムとベクトルの p ノルムとの間には，∀A ∈ Mn (C)，∀x ∈ Cn に対して

∥Ax∥ p ≤ ∥A∥ p · ∥x∥ pという関係がある。よって，∀A, B ∈ Mn (C) に対しても∥AB∥ p ≤ ∥A∥ p · ∥B∥ pが成り立つ。
さて，これでベクトルと行列に絶対値の拡張概念であるノルムを導入できた訳だが，そうすると，ベクトルや行列にも絶対誤差と相対誤差が定義できることになる。今まではなるべく一般的な定義を Cn や Mn (C) に対して述べてきたが，本書では今のところ複素数を要素とする行列やベクトルを用いたアルゴリズムを扱っていないので，誤差の定義は Rn ， Mn (R) 止まりとする。
定義 8.1.4 (ベクトルの誤差)

a ∈ Rn を真の値，ea ∈ Rn をその近似値とする。このときE(ea) = ∥a − ea∥(8.1)

をea の絶対誤差と言う。更に

∥a − ea∥ E(ea)


=∥a∥
∥a∥rE(ea) =  ∥a − ea∥ = E(ea)(a , 0)(8.2)(a = 0)をea の相対誤差と言う。特にノルムが ∥ · ∥ p であるときにはE p (ea) = ∥a − ea∥ p , rE p (ea) =E p (ea)∥a∥ pと書くことにする。

e ∈ Mn (R) に対して，E(A),e E p (A),e rE(A),e
行列についても同様に，真値 A ∈ Mn (R) とその近似値 Ae が定義できる。
rE p (A)
最後に，連立一次方程式の誤差解析において重要なファクターである，行列の条件数を定義する。

8.2. 連立一次方程式の誤差解析

95

定義 8.1.5 (行列の条件数)
正則行列 A ∈ Mn (R) の条件数 κ(A) をκ(A) = ∥A∥ · ∥A−1 ∥と定義する。 p ノルムを用いたものを κ p (A) と書く。
結論から先に言うと，この κ(A) が非常に大きい行列 A を悪条件である (ill-conditioned) と呼び，行列成分，定数ベクトル成分に含まれる初期誤差や，解法の過程で発生した丸め誤差を条件数倍して，数値解に忍び込む可能性が高い，といわれている。次節ではその解説を行う。
問題 8.1.1次の行列 A ∈ M2 (R) の条件数 κ1 (A) 及び κ∞ (A) を求めよ。

 1
A = 08.2

−1 

2

連立一次方程式の誤差解析

連立一次方程式 (7.1) を実際にコンピュータで計算しようとすると，一般的には行列，ベクトル成分は丸められて誤差が混入していると考えられる。また，解法の過程でも丸め誤差が混入するのが普通である。よって，これらを全て，行列あるいは定数ベクトルに忍び込んだ初期誤差として解釈することにすれば，解こうとする (7.1) は

eeAx=ebという形に化けているということが出来る。では最終的に得られる ex に含まれる誤差 E(ex) はどうなっているのだろうか。
それを解析する基になる補題，定理を示すことにする。
補題 8.2.1 (定数項 b に誤差がある場合)
連立一次方程式

A(x + E(ex)) = b + E(eb)においてrE(ex) ≤ κ(A) · rE(eb)である。
(証)
E(ex) = A−1 E(eb) から∥E(ex)∥ ≤ ∥A−1 ∥ ∥E(eb)∥を得る。更に，∥b∥ ≤ ∥A∥ ∥x∥ から与式を得る。

(証明終)

第8章

96

ノルム，条件数，連立一次方程式の誤差解析

補題 8.2.2 (係数行列 A に誤差がある場合)

e(A + E(A))(x+ E(ex)) = bにおいて∥E(ex)∥e≤ κ(A) · rE(A)∥x + E(ex)∥である。
(証)

x===からA−1 beA−1 (A + E(A))(x+ E(ex))
e + E(ex + E(ex) + A−1 E(A)(xx))

e + E(e−E(ex) = A−1 E(A)(xx))。

従って，∥E(ex)∥≤=e · ∥x + E(e∥A−1 ∥ ∥E(A)∥x)∥e∥E(A)∥∥A−1 ∥ ∥A−1 ∥ ·· ∥x + E(ex)∥∥A∥

より，与式を得る。

(証明終)定理 8.2.3 (係数行列，定数項共に誤差を含んでいるとき)e(A + E(A))(x+ E(ex)) = b + E(eb)e < 1 ならば，なるとき ∥A−1 E(A)∥rE(ex) ≤κ(A)e1 − ∥A−1 E(A)∥erE(eb) + rE(A)

である。
(証)
e の固有値は 1 + λ(A−1 E(A))
e だから，λ(A−1 E(A))
e によらず，正則になる。従って，
I + A−1 E(A)e −1 = I − A−1 E(A)(Ie + A−1 E(A))
e −1(I + A−1 E(A))
が成立するから，よって，

e −1 ∥ ≤ 1 + ∥A−1 E(A)∥e ∥(I + A−1 E(A))
e −1 ∥∥(I + A−1 E(A))
e −1 ∥ (1 − ∥A−1 E(A)∥)
e ≤1∥(I + A−1 E(A))

からe −1 ∥ ≤∥(I + A−1 E(A))

1e1 − ∥A−1 E(A)∥8.2. 連立一次方程式の誤差解析

97を得る。
eここで (A + E(A))(x+ E(ex)) = b + E(eb) と Ax = b より

e + (A + E(A))E(eeE(A)xx) = E(eb)。
これに，左から A−1 をかけると

e + (I + A−1 E(A))E(eeA−1 E(A)xx) = A−1 E(eb)
これを E(ex) について解くと，

e −1 A−1 (E(A)xe − E(eE(ex) = (I + A−1 E(A))
b))。
よって，

∥E(ex)∥∥x∥≤≤e e −1 ∥∥A−1 ∥ ∥E(A)∥e + ∥E(b)∥ ∥(I + A−1 E(A))∥x∥−1e∥A ∥e + ∥E(b)∥  。
∥E(A)∥e∥b∥
1 − ∥A−1 E(A)∥ここで ∥x∥ ≤ ∥A∥∥b∥ より与式を得る。

(証明終)1を用いて，
この不等式は ∥A−1 ∥ ≥ ∥A∥rE(ex) ≤κ(A)e∥E(A)∥1−∥A∥
e + rE(e· rE(A)b)(8.3)という形にしたものが主に用いられる。
今まで見てきた不等式がいずれも条件数をファクターとして持つ不等式になっていることが分かった。以上をまとめると

1. 定数項のみに誤差がある場合 —rE(ex) ≤ κ(A) · rE(eb)2. 係数行列のみに誤差がある場合 —∥E(ex)∥e≤ κ(A) · rE(A)∥x + E(ex)∥3. 双方に誤差がある場合 —rE(ex) ≤κ(A)e1 − ∥A−1 E(A)∥erE(eb) + rE(A)となる。
このうち，2. では ∥E(ex)∥ が ∥x∥ より小さいことが前提となる。∥E(ex)∥ > ∥x∥ では∥E(ex)∥≈1∥x + E(ex)∥

第8章

98

ノルム，条件数，連立一次方程式の誤差解析となり，評価式の意味がなくなってしまう。
e3. での ∥E(A)∥/∥A∥< 1 という条件は，たちの悪い問題では満たされないこともあり，注意する必要がある。
上の不等式はいずれも，行列・ベクトルノルムは同じものであるが，有限次元のノルムの同値性から，都合の良いものを組み合わせて使うこともできる。
これらの不等式を利用して，初期誤差の摂動の限界を調べる。よって計算に必要な桁数はeの精度桁, e
計算に必要な桁数 ≥ log10 (κ(A)) + max(Abの精度桁)(8.4)となる。

e の精度桁，e
ここで言う，Ab の精度桁とは，それぞれの成分の中で最も有効桁の少ない成分のものを意味する。
この式は大雑把なもので，完璧を期すならば，丸め誤差の累積の効果を見込んで + log10 n を加えると良い。ただ，次数が大きくなったとき，この 3 倍になる可能性がある事を Wilkinson が指摘していることを述べておく。

8.3 Hilbert 行列の数値例
行列に誤差が混入した場合の，その固有値の摂動については，Wilkinson[42] が理論的な考察を数多く行っている。しかし実際，どのような場合に，どの程度の影響が与えられるのかを，彼の得た結果から予測することは難しい。その原因には，具体例が乏しいことも挙げられる。
本稿では，それを実対称行列の場合に限定することで，行列の要素に誤差が混入することにより起こる固有値の変動を一種の摂動と考え，それに伴う連立一次方程式への影響について，具体例を基に説明する。
なお，以下の計算は SparcStation IPX と Sun Fortran(単精度 2 進 24 ビット) で行なった。

8.3.1 固有値の摂動Courant-Fischer(Min-Max) の定理から，次の Weyl の定理が容易に導きだされる。
定理 8.3.1 (Weyl の定理)

A, B : n × n Hermite 行列,λi (A) : A の i 番目の固有値 (λ1 (A) ≤ λ2 (A) ≤ · · · ≤ λn (A))とするとき，λi (A) + λ1 (B) ≤ λi (A + B) ≤ λi (A) + λn (B) (i = 1, 2, · · · , n)。

(8.5)

Wilkinson はこれとほぼ同じことを [42](p.101〜p.102) で証明している。
この B が行列 A の入力誤差行列で，しかも対称であるとすると，もし|bi j | ≤ ε (i, j = 1, 2, · · · , n)(8.6)|λi (B)| ≤ nε (i = 1, 2, · · · , n)

(8.7)

であれば

8.3. Hilbert 行列の数値例

99であることは Rayleigh-Ritz の定理から明らかである。よって|λi (A + B) − λi (A)| ≤ nε (i = 1, 2, · · · , n)(8.8)

を得る。即ち，固有値の絶対誤差は入力誤差の最大値のせいぜい n 倍で抑えることができる。
現在広く利用されている対称行列用の固有値ルーチンは，もととなる行列の上三角（もしくは下三角）成分のみ用いて計算する。従って，初期誤差行列の対称性は理論的にも厳密に保たれていると考えてよい。
以下，この定理を具体例で確認する。
例題 8.3.2
悪条件で名高い，Hilbert 行列A =
 1
 1
 2
 ..
 .
 1n=1213······

1n1n+11n+1···

12n−1..
.

..
.




[ai j ]の固有値を求める。その際，行列の成分 ai j = i+ 1j−1 を1. 単精度 — 2 進仮数部 24 ビット
2. 倍精度 — 2 進仮数部 53 ビットで計算し，それらを 4 倍精度の固有値ルーチンで解いたのが，下表の第 1 列，第 2 列である。第 3列は 1 列，2 列の差であり，単精度行列には入力誤差が入るので，この誤差による固有値の摂動量を表わしている。

Table 1 Hilbert 行列の固有値 (Dimension:10)
単精度
倍精度
単−倍
1230.1751920E + 01
0.3429295E + 00
0.3574183E − 01

0.17519196702651775E + 010.34292954848350908E + 000.35741816271639246E − 010.945007773E − 070.364589606E − 070.183592214E − 07450.2530897E − 020.1287263E − 030.25308907686700395E − 020.12874961427636959E − 030.645588386E − 080.233577239E − 076780.4739574E − 050.1260786E − 06
−0.2991611E − 070.47296892931844192E − 05
0.12289677387895489E − 060.21474388118628759E − 080.988459762E − 080.318180201E − 080.320635455E − 079100.3893632E − 070.2016819E − 070.22667468977874495E − 100.10930958726131586E − 120.389136475E − 070.201680775E − 07Hilbert 行列では，成分の計算で丸め誤差が発生する。これを単精度計算で行なったから，(8.6)
における ε の値はこの場合|ε| ≤ 0.39736 × 10−7(8.9)

第8章

100

ノルム，条件数，連立一次方程式の誤差解析で抑えられる。従って，n|ε| ≤ 0.39736 × 10−6 となり，(8.8) の評価式が成立していることがわかる。
次に，単精度行列の固有値を単精度，倍精度，4 倍精度の QR 分解法 (第 11 章参照) で求めてみると，Table 2 入力誤差を伴った Hilbert 行列の固有値 (Dimension:10)
単精度
倍精度
4 倍精度
12.1751903E + 1.3429263E + 0.17519195757643918E + 1.34292951202454800E + 0.1751919575764400115265046698972405E + 1.3429295120245483831332434491462269E + 0

34.3574016E − 1.2530411E − 2.35741834630860338E − 1.25308972245537668E − 2.3574183463086068413928879039309898E − 1.2530897224553907639524862478389967E − 2567.1286942E − 3.4697030E − 5.1872392E − 6.12872625655238820E − 3.47395738908145271E − 5.12607857589827829E − 6.1287262565524067111394681549549803E − 3.4739573890812540318719227082233544E − 5.1260785758921314694322830850406264E − 689−.4769931E − 7.1464610E − 7−.29916106699545878E − 7.38936315021525424E − 7−.2991610670133025173381936144839310E − 7.3893631502537948889724916900161644E − 710.3607411E − 7.20168186899426792E − 7.2016818689443467672841476423905832E − 7となり，固有値は殆ど変化していない。
これは最小固有値が成分計算で発生した丸め誤差により摂動を起こし，本来もっと小さくなるはずの order が停留しているためである。

8.3.2 連立一次方程式への影響
前節で見たように，行列の固有値は悪条件性が高ければ高いほど摂動の量が大きい。しかも Hilbert行列の場合，次数を上げても最小固有値の order はせいぜい入力誤差のそれぐらいにしかならない。
従って，条件数もあまり変化しなくなる。試みに，各 Dimension の，単精度・倍精度・4 倍精度のHilbert 行列の条件数を求めてみると，Table 3 Hilbert 行列の条件数

Dimension

κ2 (単精度)κ2 (倍精度)

κ2 (4 倍精度)

50.4737947E+060.4766073E+060.4766073E+06

10150.8686551E+080.3260381E+100.1602714E+140.1246449E+200.1602629E+140.6116566E+21

200.8902582E+100.4053651E+190.2452156E+29となり，成分計算の精度が少ないと，行列の Dimension を上げたとき，真の最小固有値が ε 以下になっても，条件数はほとんど変化しない。このようなとき，連立一次方程式の数値解にはどのような影響があるのだろうか。次の例でそれを示す。

8.3. Hilbert 行列の数値例

101

Table 4 連立一次方程式の数値解の精度桁

右の表は，次のような条件下で求めた連立一次定数項

単精度

倍精度

4 倍精度

方程式の数値解の − log10 (相対誤差) である。

12

1.796
0.391

11.76610.43626.73225.60334−0.450−0.889

9.728
9.733

25.10525.279567−0.856−0.619−1.010

9.106
8.687
8.860

25.31126.76825.305890.109−0.789

9.331
9.083

25.48527.33510−0.441

9.654

25.467係数行列 全て単精度の Hilbert 行列。
数値解法 4 倍精度の共役勾配法 (第 10 章参照)。
真の解 xi =定数項 bi =√i (i = 1, 2, · · · , 10)。

P10j=1 ai j√

j を単精度，倍精度，4 倍精度で計算した。

上の表から，それぞれの計算桁からの損失桁は，ほぼ条件数 (10+8 ) 以下で抑えられていることが示された。
以上の数値例から次の結論を得る。

1. 固有値を求めるときに，行列が良条件であれば，計算精度を初期誤差の order よりも少し多めにとることで，丸め誤差の影響を避けることができる。

2. 行列が悪条件の時は，初期誤差による摂動が大きく，計算の精度を上げても，特に最小固有値が化けてしまい，真の固有値を求めることが不可能になることがある。

3. 逆に，連立一次方程式を解く際には，条件数が大きくならないことから，計算による丸め誤差の影響は少なくなる。但し，初期誤差による摂動のため，精度の良い解は望めない。

演習問題
1. 次の正則行列 A について，以下の問いに答えよ。
 3 −1 0 
A =  −1 3 −1 

0 −1 3(a) A の逆行列は (1)1 3A−1 =21 131(2)33(3)となる。空欄を埋め，逆行列を完成させよ。

(b) κ1 (A), κ∞ (A) をそれぞれ求めよ。
2. ∀a, b ∈ C に対して，絶対値 | · | はノルムの性質を全て満足することを示せ。

第8章

102

ノルム，条件数，連立一次方程式の誤差解析

3. 1 ノルム, ユークリッドノルム, 無限大ノルムがノルムの性質を満足していることを示せ。また，それぞれのノルムの値を計算するのに必要な演算 (加減算，乗算，除算，平方根等) の回数を求めよ。
4. 正則行列 A ∈ Mn (R) に対して，∥A−1 ∥ ≥ 1/∥A∥ であることを示せ。
5. 特に A が実対称行列であれば
κ2 (A) =maxi |λi (A)|mini |λi (A)|であることを示せ。ここで λi (A) (i = 1, 2, ..., n) は A の固有値である。

6. A ∈ Mn (R) における Frobenius ノルム ∥A∥F はvt n nXX∥A∥F =|ai j |2i=1 j=1と定義される。これがノルムの条件を満足することを示せ。

(8.10)