算法の設計と解析 第 2 回
講義日:10月
18
日情報工学・・・どうやって数学を解くか?
例として,2次方程式
ax 2 + bx + c = 0
を解くことを考える.解の公式より,x = −b ± √
b 2 − 4ac 2a
である.ex.)
x 2 − x − 1 = 0 x = 1 ± √
5 2
√ a (a ∈ R, a ≥ 0)
を求める式は,qx n+1 = 1
2 (x n + a
x n ) (1)
n→∞ lim x n = √
a (2)
しかし,これを有限の処理しかできない計算機で解く場合,実数または複素数で解を求める必要がある.
そこで,ある自然数
N
に対して,|x N − x ∞ | ≤ ² N
(0 ≤ ² N ¿ 1)
を終了条件とし,繰り返し計算をすることで解を得る.
すなわち,ある小さな整数
² N
に対して,|x N+1 − x N | ≥ ² N
である間,式
(1)
を繰り返すことで計算機上での解が得られる.これを疑似コードに書き直すと, 疑似コード
² N ≥ 0 ∃N, n := 0, x 0 := 0 while |x n+1 − x n | ≥ ² N do
begin
x n+1 := 1 2 ³ x n + x a
n
´ n := n+1
end
次に,上の式が実際に解を持つ事を示す.
方法
1)
図による説明[Z
[ Z C Z :
: :
:
:
方法
2)
式による説明x N+1 = f (x n ), f (x) = 1 2
³ x + a
x
´ x 6= 0
|x n+1 − x n | = |f (x n ) − f (x n+1 )|
=
¯ ¯
¯ ¯ 1 2
µ x n + a
x n
¶
− 1 2
µ
x n−1 − a x n−1
¶¯ ¯
¯ ¯
= 1 2
¯ ¯
¯ ¯ (x n − x n−1 ) + a
x n x n−1 (x n−1 − x n )
¯ ¯
¯ ¯
≤ 1 2
µ
|x n − x n−1 | + a x n x n−1
|x n−1 − x n |
¶
= 1 2
µ
1 + a x n x n−1
¶
|x n−1 − x n |
となり,
1 2
µ
1 + a x n x n−1
¶
≤ 1
なので, 式(1)
は解を持つ.接線の方程式
y − f (x n ) = f 0 (x n )(x − x n )
において,y= 0
との交点のx
座標をx n+1
とすると,−f (x n ) = f 0 (x n )(x n+1 − x n )
⇔ − f(x n )
f 0 (x n ) = x n+1 − x n
⇔ x n+1 = x n − f (x n ) f 0 (x n )
ここで,f(x) = x 2 − a f 0 (x) = 2x
なので,x n+1 = 1 2
µ x n + a
x n
¶
が得られる.この方法は中間値の定理に基づく.
【中間値の定理】
区間
a ≤ x ≤ b
において,f(x)
が連続かつ単調ならば,min(f(a), f(b)) ≤ C ≤ max(f (a), f(b))
なるある 実数C
に対して,f(c) = C
となる実数c (a ≤ c ≤ b)
が唯一存在する.方法
4)
二分法ニュートン法では関数の微分を利用したが,二分法では微分値を用いない.
アルゴリズム
1. f (x)
の単調区間[a, b]
を決める.2. f (α) · f (β ) < 0 (a < α < β ≤ b)
を決める.3. r = α+β 2
とおく.4. |α − β| < ² → r
がf (x) = 0
の解5. f (α) · f (r) < 0 → β := α+β 2
f (α) · f (r) ≥ 0 → α := α+β 2
として3
に戻る疑似コード
f (α) · f (β) < 0 a < α < β < b, γ = α+β 2 while |α − β | ≥ ² do
begin
if f (α) · f (γ) < 0 then β = α+β 2
else α = α+β 2
end
ǩ
Ǫ ǩǪ
Ǫ̉
(a) step1
ǩ ǩǪ Ǫ ǩ̉
(b) step2
図
1:
二分法今までは
1
変数について述べてきたが,ここからは2
変数の場合について述べる.ex. 1) R 2 → R 2
w = F (x) =
à g(x, y) h(x, y)
!
x n+1 := x n − J (x n ) −1 F (x n ) (3)
に代入して解く.ここで,J
(x n )
はF (x n )
のヤコビアン(Jacobian)
であり,J (x n ) =
à g x g y
h x h y
!
となる.
Ex 2) C → C z = x + iy
とし,u = g(x, y), v = h(x, y) w = f (z) = g(x, y) + ih(x, y)
とおくと,
Ã
u v
!
=
à g(x, y) h(x, y)
!
と表すことができる.これを式
(3)
に代入する.z ∈ C
において,g(x, y), h(x, y)の間にコーシー・リーマンの関係式が成立する.∂g
∂x = ∂h
∂y , ∂g
∂y = − ∂h
∂x
コーシーリーマンの拘束より,z
k = x k + iy k
に対してx k+1 = x k +
µ hg y − gh x
|g x | 2 + |h x | 2
¶ ¯¯ ¯
¯ ¯
x=x
ky=y
ky k+1 = y k +
µ hg x − gh y
|g y | 2 + |h y | 2
¶ ¯¯ ¯
¯ ¯
x=x
ky=y
kとなる.