出典 しゅってん 百科 ひゃっか 事典 じてん
反復 はんぷく 法 ほう 英 えい iterative method )とは、数値 すうち 解析 かいせき 分野 ぶんや 手法 しゅほう 反復 はんぷく 計算 けいさん 用 もち 総称 そうしょう 対 たい 有限 ゆうげん 回 かい 手順 てじゅん 解 かい 得 え 数値 すうち 解法 かいほう 直接 ちょくせつ 法 ほう 英 えい direct method )と呼 よ [1] [2] [3] 反復 はんぷく 法 ほう 適当 てきとう 初期 しょき 点 てん
x
0
{\displaystyle x_{0}}
出発 しゅっぱつ 反復 はんぷく 式 しき
x
i
+
1
=
x
i
+
d
i
{\displaystyle x_{i+1}=x_{i}+d_{i}}
点 てん 列 れつ
{
x
i
}
{\displaystyle \{x_{i}\}}
生成 せいせい 最終 さいしゅう 的 てき 最適 さいてき 解 かい 収束 しゅうそく [1] [2] [3] アルゴリズム が単純 たんじゅん 古 ふる 用 もち 様々 さまざま 関数 かんすう 族 ぞく
{
f
(
X
)
}
{\displaystyle \{f(\mathbf {X} )\}}
提案 ていあん
与 あた 関数 かんすう f についてf (x ) = 0 を満 み 値 ね x を得 え 目的 もくてき 反復 はんぷく 法 ほう 一般 いっぱん 的 てき 以下 いか
初期 しょき 値 ち x 0 ∈ R n 定 さだ i = 0 とおく。漸 やや 化 か 式 しき
x
i
+
1
=
g
(
x
i
)
{\displaystyle x_{i+1}=g(x_{i})}
によりx i + 1求 もと g はf より決 き 関数 かんすう 適当 てきとう 判断 はんだん 基準 きじゅん
r
(
x
i
,
x
i
+
1
)
≤
ϵ
(
ϵ
>
0
)
{\displaystyle r(x_{i},x_{i+1})\leq \epsilon \quad (\epsilon >0)}
が成 な 立 た 収束 しゅうそく 表現 ひょうげん 停止 ていし xi を解 かい i → i + 1 とし、ステップ2へ戻 もど 通常 つうじょう 判断 はんだん 基準 きじゅん
r
(
x
i
,
x
i
+
1
)
=
|
x
i
+
1
−
x
i
|
{\displaystyle r(x_{i},x_{i+1})=|x_{i+1}-x_{i}|}
などが採 と 関数 かんすう g の取 と 方 かた 種々 しゅじゅ 方法 ほうほう
関数 かんすう f が適当 てきとう 滑 なめ 関数 かんすう f の零 れい 点 てん 求 もと 関数 かんすう g を
g
(
x
)
=
x
−
f
(
x
)
f
′
(
x
)
{\displaystyle g(x)=x-{\frac {f(x)}{f'(x)}}}
ととれば、これはニュートン法 ほう となる[2] 収束 しゅうそく 場合 ばあい 次 じ 収束 しゅうそく 英 えい Quadratic convergence ) となる[2] 根 ね
a
{\displaystyle a}
Δ でるた
x
i
≜
x
i
−
a
{\displaystyle \Delta x_{i}\triangleq x_{i}-a}
Δ でるた
x
i
+
1
=
f
′
′
(
a
)
2
f
′
(
a
)
(
Δ でるた
x
i
)
2
+
O
[
Δ でるた
x
i
]
3
{\displaystyle \Delta x_{i+1}={\frac {f^{\prime \prime }(a)}{2f^{\prime }(a)}}(\Delta x_{i})^{2}+O[\Delta x_{i}]^{3}}
ハレー法 ほう （英語 えいご 版 ばん
g
(
x
)
=
x
−
f
(
x
)
f
′
(
x
)
−
f
″
(
x
)
f
(
x
)
2
f
′
(
x
)
{\displaystyle g(x)=x-{\frac {f(x)}{f'(x)-{\frac {f''(x)f(x)}{2f'(x)}}}}}
ととる。これは収束 しゅうそく 場合 ばあい 次 じ 収束 しゅうそく
Δ でるた
x
i
+
1
=
3
(
f
′
′
)
2
−
2
f
′
f
′
′
′
12
(
f
′
)
2
(
Δ でるた
x
i
)
3
+
O
[
Δ でるた
x
i
]
4
{\displaystyle \Delta x_{i+1}={\frac {3(f^{\prime \prime })^{2}-2f^{\prime }f^{\prime \prime \prime }}{12(f^{\prime })^{2}}}(\Delta x_{i})^{3}+O[\Delta x_{i}]^{4}}
上記 じょうき アルゴリズム では、i +1回 かい 目 め 近似 きんじ 解 かい x i +1直前 ちょくぜん 近似 きんじ 解 かい x i 関数 かんすう 一般 いっぱん 化 か 不動点 ふどうてん 反復 はんぷく 法 ほう [2] [6] l 点 てん 反復 はんぷく 法 ほう
x
i
+
1
=
g
(
x
i
,
x
i
−
1
,
…
,
x
i
−
l
+
1
)
,
l
≥
1
{\displaystyle x_{i+1}=g(x_{i},x_{i-1},\ldots ,x_{i-l+1}),\qquad l\geq 1}
という形 かたち 表 あらわ ニュートン法 ほう は l = 1割 わり 線 せん 法 ほう l = 2場合 ばあい 反復 はんぷく 関数 かんすう g f (α あるふぁ 満 み 真 しん 解 かい α あるふぁ 対 たい
g
(
α あるふぁ ,
α あるふぁ ,
…
,
α あるふぁ )
=
α あるふぁ
{\displaystyle g(\alpha ,\alpha ,\ldots ,\alpha )=\alpha }
を満 み α あるふぁ g 不動点 ふどうてん 英 えい Fixed point ) と呼 よ [2] [5]
l = 1場合 ばあい 反復 はんぷく 法 ほう 収束 しゅうそく 性 せい 十分 じゅうぶん 条件 じょうけん 次 つぎ 不動点 ふどうてん 定理 ていり 成 な 立 た 不動点 ふどうてん 反復 はんぷく 法 ほう
x
i
+
1
=
g
(
x
i
)
{\displaystyle x_{i+1}=g(x_{i})}
は、反復 はんぷく 関数 かんすう g 以下 いか 条件 じょうけん 満 み 唯一 ゆいいつ 不動点 ふどうてん α あるふぁ 収束 しゅうそく
g (x )区間 くかん I = [a , b ]連続 れんぞく すべての x ∈ I 対 たい g (x ) ∈ I
すべての x , y ∈ I , x ≠ y 対 たい
|
g
(
x
)
−
g
(
y
)
|
<
L
|
x
−
y
|
{\displaystyle |g(x)-g(y)|<L|x-y|}
を満 み x , y 無関係 むかんけい 定数 ていすう L (0 ≦ L < 1)存在 そんざい 不動点 ふどうてん 定理 ていり 条件 じょうけん 成 な 立 た 適当 てきとう 初期 しょき 値 ち x 0 ∈ I 選 えら 反復 はんぷく 計算 けいさん 行 おこな x i 区間 くかん I 内 うち 唯 ただ 一 ひと 存在 そんざい 不動点 ふどうてん α あるふぁ 収束 しゅうそく 示 しめ [2] [5]
矢部 やべ 博 ひろし 工学 こうがく 基礎 きそ 最適 さいてき 化 か 応用 おうよう 初版 しょはん 数理 すうり 工学 こうがく 社 しゃ 年 ねん 月 がつ 日 にち ISBN 4-901683-34-9 。 藤野 ふじの 清次 せいじ 張 ちょう 反復 はんぷく 法 ほう 数理 すうり 朝倉書店 あさくらしょてん Saad, Y. (2003). Iterative methods for sparse linear systems. SIAM .
Hageman, L. A., & Young, D. M. (2012). Applied iterative methods. Courier Corporation.
Traub, J. F. (1982). Iterative methods for the solution of equations. American Mathematical Society .
Greenbaum, A. (1997). Iterative methods for solving linear systems. SIAM . Kelley, C. T. (1995). Iterative methods for linear and nonlinear equations. SIAM .
Ortega, J. M., & Rheinboldt, W. C. (1970). Iterative solution of nonlinear equations in several variables. SIAM . Kelley, C. T. (1999). Iterative methods for optimization. SIAM .
Samuel, J. L. S., & Pizzo, K. J. T. (1972). Iterative methods for nonlinear optimization problems. Prentice-Hall, Englewood Cliffs. 
![{\displaystyle \Delta x_{i+1}={\frac {f^{\prime \prime }(a)}{2f^{\prime }(a)}}(\Delta x_{i})^{2}+O[\Delta x_{i}]^{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c61a96af051ad283ae1ff698860ed8e099bd5657)
![{\displaystyle \Delta x_{i+1}={\frac {3(f^{\prime \prime })^{2}-2f^{\prime }f^{\prime \prime \prime }}{12(f^{\prime })^{2}}}(\Delta x_{i})^{3}+O[\Delta x_{i}]^{4}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1bf38c0361d84183b0dd9569bbd36196ca6da6fe)
カテゴリ