計算情報学Ｉ
名古屋大学 情報文化学部
自然情報学科３年
第７回

鈴木泰博
情報文化学部・大学院情報科学研究科
複雑系科学専攻

Science ofinteractions

問題別正答率
1-1 計算回数の数え上げ

40.7%

1-2 精度の評価

22.2%

2 ガウスの消去法

81.4%

3 LU分解40.7%

4-1 ガウスの消去法のアルゴリズム

7.4%

4-2 計算量の評価

11.1%
Science ofinteractions

Agenda

計算情報学 Ｉ 第７回
1.
2.
3.
4.

逐次近似法(2分法）
逐次代入法
ニュートン法解の収束についてScience ofinteractions

方程式の根を求める数値計算手法
f ( x) = x 2 + 2 x − 1 = 0解の公式により求めることが可能。
でも。。
•5次以上の多項式の場合は？
•特殊関数が含まれる場合は？
…
数値計算が必要となる。

Science ofinteractions

逐次近似法～2分法
解の候補となる空間を2分することで区間縮小を行い近似する方法

x 2 = 11 を満たすxを開平算を用いずに計算するには。。
32=9, 42=16より、解は3と4の間にあると大よその見当をつける（第1近似）
そして、解の存在する区間を順次狭めていく（逐次近似）
3< α <

4→

3< α <

3.5→

3.25

< α <

3.5→

3.25

< α < 3.375 →3.3125 < α < 3.375 →3+ 42
3 + 3.52
3.25 + 3.52
3.25 + 3.375
2...

=3.5,(3.5) 2==3.25,(3.25) 2= 10.56...

=3.375,(3.375) 2

=

11.39

= 3.3125, (3.3125) 2=10.97

12.25

Science ofinteractions2分法の原理～中間値の定理
関数f(x)が区間a,b(a≠b)で連続なとき、もし、f(a)>0, f(b)<0なるa,bが存在すればf(α)=0となるような根αがaとbの間に少なくとも1つは存在する。

f(b)>0f(b)>0a

根αf(α)=0 baαβΓbf(a)<0f(a)<0Science ofinteractions中間値の定理の証明＝２分法の原理
証明のスケッチ

収束判定条件有限の縮小で解に到達できるかわからないので、以下の判定条件を用いる。

実数の連続性

半分に切って解を含んでいる方を残す

a −b<ε2
この条件を満たしたら計算を止めてこの値を近似値とする。その場合、真の値との誤差は高々εとなる。

≒∞Science ofinteractions

2分法のアルゴリズム
f(c) > 0a 根αa 根αcbaf(c) < 0f(c) > 0cab根α根α bc bScience ofinteractions2分法のアルゴリズム（１） f(a)<0, f(b)>0を満たすように変数a,bの値を設定する。
（２） 以下c:=(a + b) / 2|a – b| / 2 < εならばステップ(3)へ
fc:=f( c )fc > 0 ならば b:=c
もし、 fc < 0ならば a:=c
fc = 0 ならばステップ(3)へを繰り返す（３） c を答えとする
Science ofinteractions

2分法の計算量
２分法で最も計算の手間がかかるのはf(c)の計算なので、その回数を見積もれば計算量が測れる。計算終了までに要する繰り返し回数は、収束条件を満たした場合はfcを計算しないので、条件を満たす１回前までをＮ回とすると、

a −b<ε
N +12をみたす最小のＮである。すなわち、⎛| a −b |⎞N > log 2 ⎜⎟ −1⎝ ε ⎠を満たす最小のＮとなる。

Science ofinteractions2分法の計算例
f ( x) = e − x − x 2 = 0f ( 0) = 1 > 0f (1) = −1 < 0より、a=1, b=0 とおく

解を小数点以下5桁まで計算するため、ε=5.0 x 10-6 とおく⎛| a −b |⎞log 2 ⎜⎟ − 1 = 16.609... 計算に必要な計算回数は17回⎝ ε ⎠演習 2分法をプログラミングし実際に17回で収束するか確認せよ。
ちなみに、17回目で0.7034683、18回目で0.7034645(a – b = 3.8 x 10-6より、(a – b)/2 < ε)Science ofinteractions

逐次代入法
最も原始的な近似解法
f(x)をx = g( x )と変形した方程式を、x k+1 = g( xk) と逐次に代入することにより解く方法

x = cos x
x1 = 1 (rad)x2 = cos x1 = cos 1….

なにしろ簡単なので昔から広く使われてきた。でも、収束が遅い。

x k+1 = cos xk
演習：逐次代入法をプログラミングしこの問題をといてみよ。
50回ぐらいで 0.739085133が得られるはず。
Science ofinteractions

逐次代入法の収束性
f(x) = 0 の解をαとし、領域Iを | x – α | < εを満たす全ての点の集合とする。
いま、 f( x ) = 0をx = g( x )として逐次近似を行なう場合、g( x ), g´( x )がIで連続で、Iに含まれる全ての点に対し|g´( x )|≦K< 1となる正の定数kが存在し、初期近似値がIに選ばれていれば、解はαに収束する。

この領域内部では全ての点で |g´ ( x )| < 1
領域 Iαx0
ならば解はαに収束
Science ofinteractions

逐次代入法の原理
f(x) = 0 の解をαとし、領域Iを | x – α | < εを満たす全ての点の集合とする。
いま、 f( x ) = 0をx = g( x )として逐次近似を行なう場合、g( x ), g´( x )がIで連続で、Iに含まれる全ての点に対し|g´( x )|≦K< 1となる正の定数kが存在し、初期近似値がIに選ばれていれば、解はαに収束する。
αは逐次代入xi+1 = g (xi) ①

証明のスケッチの解であるから、α=g(α)であり、これを①から辺々ひくと、
x i+1 – α = g (xi) – g(α） ②
平均値の定理より、 g(xi) – g(α)=g´(τi)(xi –α）
i = 0 に対しては仮定より、τ０がIに含まれ、|g´(τ0)|<1である。
これと②より、|x1 –α|=|g´(τ0)|・|x0 –α|≦|x0 –α|が成立し、xiもまたIに含まれ、解により近い値となる。
k回目の反復計算での誤差(xk – α)をekとすれば、|e i+1|=|g´(τi)|・|ei|≦K|ei|, (i =0,1,…)となる。
よって、この式を繰り返し適用することにより、|e i+1|≦K|ei|≦K2|e i-1|≦…≦K i+1|e0|が得られる。

平均値の定理f(x)を区間a,bで連続、かつ微分可能な関数とする。このとき、区間a,bに次の関係を満たすcが少なくとも１つ存在する。

f ′(c) =f (b) − f (a )b−a

ここで K<1より、
lim k i+1 = 0 ( i→∞)よって lim |e i+1|=0 ( i→∞）となる。
したがって、lim xi = α(i→∞）。

Science ofinteractions区間の縮小の程度を決めるだから解近傍でのg´(τ)が小さいほど収束が早くなる。

逐次代入法の原理|e i+1|=|g´(τi)|・|ei|≦K|ei|, (i =0,1,…)
ここがポイントより、|e i+1|≦K|ei|≦K2|e i-1|≦…≦K i+1|e0|

評価のために定数Ｋで変数g´(τi)を上から押さえるK<1より、
lim k i+1 = 0 ( i→∞),lim |e i+1|=0 ( i→∞）⇒lim xi = α(i→∞）。

y=g(x)y=x

y=x

y=g(x)
x0x2 α x3x1

区間I収束する場合 Ｋ＝| g´( x ) | < 1x2

x1 x0 α
区間I発散する場合 Ｋ＝| g´( x ) | > 1

Science ofinteractions収束の速さの評価
反復式 x k+1 = φ( xk) ①の解（真の値）をx真とする。また、第k近似解xkの誤差をek = xk – x 真 つまり、xk = x真 + ek
①より、xk+1 = φ (x真 + ek)。これをテイラー展開すると、

x k +1 = Φ ( x真 ) + Φ ′( x真 )ek +Φ ′′( x真 )2ek

2

φ(x真)=x真、かつ、xk+1 = x真+ ek+1より、誤差の評価

2′
ek +1 = Φ ( x真 )ek + O(ek )≅ Cek|f(x真)|が>1 … 発散
<1 … 収束
この値に収束の速度が依存「1次収束」、もしくは、「収束次数が１」である
Science ofinteractions

ニュートン法•きわめてシンプルだが、収束が早く実用的•他のより複雑な手法と比べてもさほど遜色がない•唯一の難点はf’’(x)の計算が必要なこと

初期値を適当に選ぶ
k = 0,1,2,...,の順にf ( xk )x k +1 = x k −f ′( x k )接線の勾配 f’(xk)

収束判定
f(xk)
xk+2xk+1xk

f ′( x k ) =f ( xk )x k − x k +1 より。
Science ofinteractions

演習

与えられた数aの平方根をニュートン法で解く場合の反復式を求めよ。

Science ofinteractions

解答与えられた数aの平方根をニュートン法で解く場合の反復式を求めよ。

x2 − a = 0
f ( x) = x 2 − aより、
f ′( x) = 2 xaxk +2xk( x k − a)x k +1 = x k −=2x k2
この反復式を用いることで、繰り返し回数は１回から２回になる。
Science ofinteractions収束の速さの評価
反復式 x k+1 = φ( xk) ①の解（真の値）をx真とする。また、第k近似解xkの誤差をek = xk – x 真 つまり、xk = x真 + ek
①より、xk+1 = φ (x真 + ek)。これをテイラー展開すると、

ek +1 = Φ ′( x真 )ek +Φ ′′( x真 )2

ek + ...
2|f(x真)|が>1 … 発散
<1 … 収束
この値に収束の速度が依存

f(x真)=x真、かつ、xk+1 = x真+ ek+1より、

ek +1 = Φ ′( x真 )ek +Φ ′′( x真 )2

ek + ...
2f ( x){ f ′( x)}2 − f ( x) f ′′( x)Φ ( x) = x −⇒ Φ ′( x) = 1 −′f ( x){ f ′( x)}2ek +1 ≅ Cek2 + O(ek3 )「2次収束」

より、φ’(x真)=0Science ofinteractions

（数値）解析的な背景
これまで紹介してきた反復法には次のような解析的な背景がある。
定理１ 閉区間 Ｉ から Ｉ への関数 g(x)が x, y ∈ I ならば、

| g ( x) − g ( y ) |≤ L | x − y |, (0 ≤ L < 1)を満たすならば、gは I 内にただ一つの解αを持ち、xn+1 = g(xn)はαに収束する。
（このようなｇは縮小写像 contractive mappingと呼ばれる）。
注)一般にこのような条件を満たすとき、ｇはリプシッツ(Lipschitz)条件を満たすといい、Ｌをリプシッツ定数をいう。
証明 解の存在と収束性の証明については、中間値の定理を用いた収束性の証明と同様であるので省略する。
解の唯一性の証明は、もしα以外に解β, β=g(β)があったと仮定すると、| β − α |=| g ( β ) − g (α ) |≤ L | β − α |より、Ｌ＝１となり条件に矛盾することにより得られる。
縮小写像の原理を応用するポイントはリプシッツ定数Ｌ＜１である！
Science ofinteractions