• 検索結果がありません。

算法の設計と解析 第 2 回

N/A
N/A
Protected

Academic year: 2021

シェア "算法の設計と解析 第 2 回"

Copied!
5
0
0

読み込み中.... (全文を見る)

全文

(1)

算法の設計と解析 第 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)

を求める式は,q

x 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)

を繰り返すことで計算機上での解が得られる.

(2)

これを疑似コードに書き直すと, 疑似コード

² 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)

は解を持つ.

(3)

接線の方程式

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

(4)

ǩ

Ǫ ǩǪ

Ǫ̉

(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

(5)

コーシーリーマンの拘束より,z

k = x k + iy k

に対して

x k+1 = x k +

µ hg y gh x

|g x | 2 + |h x | 2

¶ ¯¯ ¯

¯ ¯

x=x

k

y=y

k

y k+1 = y k +

µ hg x gh y

|g y | 2 + |h y | 2

¶ ¯¯ ¯

¯ ¯

x=x

k

y=y

k

となる.

参照

関連したドキュメント

Amortized efficiency of list update and paging rules.. On the

 「時価の算定に関する会計基準」(企業会計基準第30号

⑥ニューマチックケーソン 職種 設計計画 設計計算 設計図 数量計算 照査 報告書作成 合計.. 設計計画 設計計算 設計図 数量計算

計量法第 173 条では、定期検査の規定(計量法第 19 条)に違反した者は、 「50 万 円以下の罰金に処する」と定められています。また、法第 172

(大防法第 18 条の 15、大防法施行規則第 16 条の 8、条例第 6 条の 2、条例規則第 6 条の

水道施設(水道法(昭和 32 年法律第 177 号)第 3 条第 8 項に規定するものをい う。)、工業用水道施設(工業用水道事業法(昭和 33 年法律第 84 号)第

(5) 帳簿の記載と保存 (法第 12 条の 2 第 14 項、法第 7 条第 15 項、同第 16

越欠損金額を合併法人の所得の金額の計算上︑損金の額に算入