← 戻る 方程式の近似解法 › ニュートン法の2次収束 定理 証明済み
ニュートン法の2次収束 内容
r r r f f f f ′ ( r ) ≠ 0 f'(r) \ne 0 f ′ ( r ) = 0 r r r r r r C = max ∣ f ′ ′ ∣ 2 min ∣ f ′ ∣ C=\dfrac{\max|f''|}{2\min|f'|} C = 2 min ∣ f ′ ∣ max ∣ f ′′ ∣ ∣ x n + 1 − r ∣ ≤ C ∣ x n − r ∣ 2 |x_{n+1}-r| \le C\,|x_n-r|^2 ∣ x n + 1 − r ∣ ≤ C ∣ x n − r ∣ 2
なぜ正しいのか?
接線は滑らかな曲線に対して非常に良い近似であるため、その誤差はすでに進んだ距離の2乗に比例し、正しい桁数は次のステップでほぼ倍になる。
証明の概略 ステップ1(現在の推測値のまわりでテイラー展開する)。f f f ξ n \xi_n ξ n x n x_n x n r r r f ( r ) = f ( x n ) + f ′ ( x n ) ( r − x n ) + 1 2 f ′ ′ ( ξ n ) ( r − x n ) 2 f(r) = f(x_n) + f'(x_n)(r-x_n) + \tfrac12 f''(\xi_n)(r-x_n)^2 f ( r ) = f ( x n ) + f ′ ( x n ) ( r − x n ) + 2 1 f ′′ ( ξ n ) ( r − x n ) 2
ステップ2(根の条件を代入する)。f ( r ) = 0 f(r)=0 f ( r ) = 0 0 = f ( x n ) + f ′ ( x n ) ( r − x n ) + 1 2 f ′ ′ ( ξ n ) ( r − x n ) 2 0 = f(x_n) + f'(x_n)(r-x_n) + \tfrac12 f''(\xi_n)(r-x_n)^2 0 = f ( x n ) + f ′ ( x n ) ( r − x n ) + 2 1 f ′′ ( ξ n ) ( r − x n ) 2 f ′ ( x n ) f'(x_n) f ′ ( x n ) r r r f ′ ( r ) ≠ 0 f'(r) \ne 0 f ′ ( r ) = 0 f ′ f' f ′ r − x n r - x_n r − x n 0 = f ( x n ) f ′ ( x n ) + ( r − x n ) + f ′ ′ ( ξ n ) 2 f ′ ( x n ) ( r − x n ) 2 0 = \dfrac{f(x_n)}{f'(x_n)} + (r-x_n) + \dfrac{f''(\xi_n)}{2f'(x_n)}(r-x_n)^2 0 = f ′ ( x n ) f ( x n ) + ( r − x n ) + 2 f ′ ( x n ) f ′′ ( ξ n ) ( r − x n ) 2
ステップ3(ニュートンのステップを認識する)。整理すると r − ( x n − f ( x n ) f ′ ( x n ) ) = − f ′ ′ ( ξ n ) 2 f ′ ( x n ) ( r − x n ) 2 r - \left(x_n - \dfrac{f(x_n)}{f'(x_n)}\right) = -\dfrac{f''(\xi_n)}{2f'(x_n)}(r-x_n)^2 r − ( x n − f ′ ( x n ) f ( x n ) ) = − 2 f ′ ( x n ) f ′′ ( ξ n ) ( r − x n ) 2 x n + 1 x_{n+1} x n + 1 e n = x n − r e_n = x_n - r e n = x n − r r − x n + 1 = − f ′ ′ ( ξ n ) 2 f ′ ( x n ) e n 2 r - x_{n+1} = -\dfrac{f''(\xi_n)}{2f'(x_n)}\,e_n^2 r − x n + 1 = − 2 f ′ ( x n ) f ′′ ( ξ n ) e n 2 e n + 1 = − f ′ ′ ( ξ n ) 2 f ′ ( x n ) e n 2 e_{n+1} = -\dfrac{f''(\xi_n)}{2f'(x_n)}\,e_n^2 e n + 1 = − 2 f ′ ( x n ) f ′′ ( ξ n ) e n 2
ステップ4(定数を評価する)。絶対値をとり ∣ f ′ ′ ( ξ n ) ∣ |f''(\xi_n)| ∣ f ′′ ( ξ n ) ∣ 1 / ∣ f ′ ( x n ) ∣ 1/|f'(x_n)| 1/∣ f ′ ( x n ) ∣ max ∣ f ′ ′ ∣ \max|f''| max ∣ f ′′ ∣ 1 / min ∣ f ′ ∣ 1/\min|f'| 1/ min ∣ f ′ ∣ C = max ∣ f ′ ′ ∣ 2 min ∣ f ′ ∣ C=\dfrac{\max|f''|}{2\min|f'|} C = 2 min ∣ f ′ ∣ max ∣ f ′′ ∣ ∣ x n + 1 − r ∣ ≤ C ∣ x n − r ∣ 2 |x_{n+1}-r| \le C\,|x_n-r|^2 ∣ x n + 1 − r ∣ ≤ C ∣ x n − r ∣ 2 C ∣ x 0 − r ∣ < 1 C\,|x_0-r| < 1 C ∣ x 0 − r ∣ < 1 ∣ x n − r ∣ |x_n - r| ∣ x n − r ∣ 0 0 0 ∣ x n + 1 − r ∣ ≤ C ∣ x n − r ∣ 2 |x_{n+1}-r| \le C\,|x_n-r|^2 ∣ x n + 1 − r ∣ ≤ C ∣ x n − r ∣ 2
ステップごとの証明
この定理のステップごとの証明はまだありません。