1 収束の次数 定義 1.1. r ∈ R r\in\R r ∈ R ( x k ) k ∈ N ≥ 0 (x_k)_{k\in\N} ( x k ) k ∈ N ≥ 0 r r r k ∈ N ≥ 0 k\in\N k ∈ N ≥ 0 x k ≠ r x_k\ne r x k = r e k : = x k − r e_k:=x_k-r e k := x k − r
実数q > 1 q>1 q > 1 C ∈ ( 0 , + ∞ ) C\in(0,+\infty) C ∈ ( 0 , + ∞ ) lim k → ∞ ∣ e k + 1 ∣ / ∣ e k ∣ q = C \lim_{k\to\infty}\lvert e_{k+1}\rvert/\lvert e_k\rvert^q=C lim k → ∞ ∣ e k + 1 ∣ / ∣ e k ∣ q = C ( x k ) (x_k) ( x k ) r r r 次数 (order of convergence )q q q C C C 漸近定数 (asymptotic error constant )2 2 2 二次収束 (quadratic convergence )
C ∈ ( 0 , 1 ) C\in(0,1) C ∈ ( 0 , 1 ) lim k → ∞ ∣ e k + 1 ∣ / ∣ e k ∣ = C \lim_{k\to\infty}\lvert e_{k+1}\rvert/\lvert e_k\rvert=C lim k → ∞ ∣ e k + 1 ∣ / ∣ e k ∣ = C ( x k ) (x_k) ( x k ) r r r 1 1 1 線形収束 (linear convergence )C C C lim k → ∞ ∣ e k + 1 ∣ / ∣ e k ∣ = 0 \lim_{k\to\infty}\lvert e_{k+1}\rvert/\lvert e_k\rvert=0 lim k → ∞ ∣ e k + 1 ∣ / ∣ e k ∣ = 0 ( x k ) (x_k) ( x k ) r r r 超線形収束 (superlinear convergence ) 補題 1.2. r ∈ R r\in\R r ∈ R ( x k ) k ∈ N ≥ 0 (x_k)_{k\in\N} ( x k ) k ∈ N ≥ 0 r r r k ∈ N ≥ 0 k\in\N k ∈ N ≥ 0 x k ≠ r x_k\ne r x k = r
( x k ) (x_k) ( x k ) r r r q q q C C C q ′ q' q ′ C ′ C' C ′ q = q ′ q=q' q = q ′ C = C ′ C=C' C = C ′ ( x k ) (x_k) ( x k ) r r r q > 1 q>1 q > 1 ( x k ) (x_k) ( x k ) r r r 命題 1.3. r ∈ R r\in\R r ∈ R ( x k ) k ∈ N ≥ 0 (x_k)_{k\in\N} ( x k ) k ∈ N ≥ 0 r r r k ∈ N ≥ 0 k\in\N k ∈ N ≥ 0 x k ≠ r x_k\ne r x k = r e k : = x k − r e_k:=x_k-r e k := x k − r d k : = − log 10 ∣ e k ∣ d_k:=-\log_{10}\lvert e_k\rvert d k := − log 10 ∣ e k ∣
( x k ) (x_k) ( x k ) C C C lim k → ∞ ( d k + 1 − d k ) = − log 10 C > 0 \lim_{k\to\infty}(d_{k+1}-d_k)=-\log_{10}C>0 lim k → ∞ ( d k + 1 − d k ) = − log 10 C > 0 ( x k ) (x_k) ( x k ) q > 1 q>1 q > 1 C C C lim k → ∞ ( d k + 1 − q d k ) = − log 10 C \lim_{k\to\infty}(d_{k+1}-qd_k)=-\log_{10}C lim k → ∞ ( d k + 1 − q d k ) = − log 10 C lim k → ∞ d k + 1 / d k = q \lim_{k\to\infty}d_{k+1}/d_k=q lim k → ∞ d k + 1 / d k = q 証明. q ≥ 1 q\ge1 q ≥ 1 d k + 1 − q d k = − log 10 ( ∣ e k + 1 ∣ / ∣ e k ∣ q ) d_{k+1}-qd_k=-\log_{10}(\lvert e_{k+1}\rvert/\lvert e_k\rvert^q) d k + 1 − q d k = − log 10 (∣ e k + 1 ∣ / ∣ e k ∣ q ) log 10 \log_{10} log 10 ( 0 , + ∞ ) (0,+\infty) ( 0 , + ∞ ) ∣ e k + 1 ∣ / ∣ e k ∣ q → C > 0 \lvert e_{k+1}\rvert/\lvert e_k\rvert^q\to C>0 ∣ e k + 1 ∣ / ∣ e k ∣ q → C > 0 d k + 1 − q d k → − log 10 C d_{k+1}-qd_k\to-\log_{10}C d k + 1 − q d k → − log 10 C q = 1 q=1 q = 1 (1) であり、C < 1 C<1 C < 1 − log 10 C > 0 -\log_{10}C>0 − log 10 C > 0 q > 1 q>1 q > 1 ∣ e k ∣ → 0 \lvert e_k\rvert\to0 ∣ e k ∣ → 0 d k → + ∞ d_k\to+\infty d k → + ∞ K K K k ≥ K k\ge K k ≥ K d k > 0 d_k>0 d k > 0 k ≥ K k\ge K k ≥ K
d k + 1 d k = q + d k + 1 − q d k d k \frac{d_{k+1}}{d_k}=q+\frac{d_{k+1}-qd_k}{d_k} d k d k + 1 = q + d k d k + 1 − q d k であり、右辺の第二項の分子は収束し分母は+ ∞ +\infty + ∞ d k + 1 / d k → q d_{k+1}/d_k\to q d k + 1 / d k → q ▨
定義 1.5. d ∈ N ≥ 1 d\in\NN d ∈ N ≥ 1 R d \R^d R d ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ x ∗ ∈ R d x_*\in\R^d x ∗ ∈ R d ( x k ) k ∈ N ≥ 0 (x_k)_{k\in\N} ( x k ) k ∈ N ≥ 0 x ∗ x_* x ∗ R d \R^d R d C ≥ 0 C\ge0 C ≥ 0 k 0 ∈ N ≥ 0 k_0\in\N k 0 ∈ N ≥ 0 k ≥ k 0 k\ge k_0 k ≥ k 0 k ∈ N ≥ 0 k\in\N k ∈ N ≥ 0
∥ x k + 1 − x ∗ ∥ ≤ C ∥ x k − x ∗ ∥ 2 \lVert x_{k+1}-x_*\rVert\le C\lVert x_k-x_*\rVert^2 ∥ x k + 1 − x ∗ ∥ ≤ C ∥ x k − x ∗ ∥ 2 が成り立つとき、( x k ) (x_k) ( x k ) x ∗ x_* x ∗ 少なくとも二次で収束する (converge at least quadratically )
命題 1.6.
r ∈ R r\in\R r ∈ R ( x k ) k ∈ N ≥ 0 (x_k)_{k\in\N} ( x k ) k ∈ N ≥ 0 r r r k ∈ N ≥ 0 k\in\N k ∈ N ≥ 0 x k ≠ r x_k\ne r x k = r ( x k ) (x_k) ( x k ) r r r 2 2 2 ( x k ) (x_k) ( x k ) R \R R r r r d ∈ N ≥ 1 d\in\NN d ∈ N ≥ 1 R d \R^d R d ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ R d \R^d R d ( x k ) k ∈ N ≥ 0 (x_k)_{k\in\N} ( x k ) k ∈ N ≥ 0 x ∗ ∈ R d x_*\in\R^d x ∗ ∈ R d k 1 ∈ N ≥ 0 k_1\in\N k 1 ∈ N ≥ 0 k ≥ k 1 k\ge k_1 k ≥ k 1 k k k x k ≠ x ∗ x_k\ne x_* x k = x ∗ lim k → ∞ ∥ x k + 1 − x ∗ ∥ / ∥ x k − x ∗ ∥ = 0 \lim_{k\to\infty}\lVert x_{k+1}-x_*\rVert/\lVert x_k-x_*\rVert=0 lim k → ∞ ∥ x k + 1 − x ∗ ∥ / ∥ x k − x ∗ ∥ = 0 証明. (1) を示す。e k : = x k − r e_k:=x_k-r e k := x k − r 2 2 2 L : = lim k → ∞ ∣ e k + 1 ∣ / ∣ e k ∣ 2 L:=\lim_{k\to\infty}\lvert e_{k+1}\rvert/\lvert e_k\rvert^2 L := lim k → ∞ ∣ e k + 1 ∣ / ∣ e k ∣ 2 k 0 ∈ N ≥ 0 k_0\in\N k 0 ∈ N ≥ 0 k ≥ k 0 k\ge k_0 k ≥ k 0 k k k ∣ e k + 1 ∣ / ∣ e k ∣ 2 ≤ L + 1 \lvert e_{k+1}\rvert/\lvert e_k\rvert^2\le L+1 ∣ e k + 1 ∣ / ∣ e k ∣ 2 ≤ L + 1 ∣ e k + 1 ∣ ≤ ( L + 1 ) ∣ e k ∣ 2 \lvert e_{k+1}\rvert\le(L+1)\lvert e_k\rvert^2 ∣ e k + 1 ∣ ≤ ( L + 1 ) ∣ e k ∣ 2 ( x k ) (x_k) ( x k ) r r r ( x k ) (x_k) ( x k ) C = L + 1 C=L+1 C = L + 1 k 0 k_0 k 0 r r r
(2) を示す。C ≥ 0 C\ge0 C ≥ 0 k 0 ∈ N ≥ 0 k_0\in\N k 0 ∈ N ≥ 0 k ≥ k 0 k\ge k_0 k ≥ k 0 k k k ∥ x k + 1 − x ∗ ∥ ≤ C ∥ x k − x ∗ ∥ 2 \lVert x_{k+1}-x_*\rVert\le C\lVert x_k-x_*\rVert^2 ∥ x k + 1 − x ∗ ∥ ≤ C ∥ x k − x ∗ ∥ 2 k ≥ max { k 0 , k 1 } k\ge\max\{k_0,k_1\} k ≥ max { k 0 , k 1 } ∥ x k − x ∗ ∥ > 0 \lVert x_k-x_*\rVert>0 ∥ x k − x ∗ ∥ > 0
0 ≤ ∥ x k + 1 − x ∗ ∥ ∥ x k − x ∗ ∥ ≤ C ∥ x k − x ∗ ∥ 0\le\frac{\lVert x_{k+1}-x_*\rVert}{\lVert x_k-x_*\rVert}\le C\lVert x_k-x_*\rVert 0 ≤ ∥ x k − x ∗ ∥ ∥ x k + 1 − x ∗ ∥ ≤ C ∥ x k − x ∗ ∥ である。∥ x k − x ∗ ∥ → 0 \lVert x_k-x_*\rVert\to0 ∥ x k − x ∗ ∥ → 0 0 0 0 ▨
例 1.7. j ∈ N ≥ 0 j\in\N j ∈ N ≥ 0 a 2 j : = 1 a_{2j}:=1 a 2 j := 1 a 2 j + 1 : = 2 a_{2j+1}:=2 a 2 j + 1 := 2 ( e k ) k ∈ N ≥ 0 (e_k)_{k\in\N} ( e k ) k ∈ N ≥ 0 e 0 : = 1 / 4 e_0:=1/4 e 0 := 1/4 e k + 1 : = a k e k 2 e_{k+1}:=a_ke_k^2 e k + 1 := a k e k 2 0 < e k ≤ 1 / 4 0<e_k\le1/4 0 < e k ≤ 1/4 0 < a k ≤ 2 0<a_k\le2 0 < a k ≤ 2 2 e k ≤ 1 / 2 2e_k\le1/2 2 e k ≤ 1/2 0 < e k + 1 ≤ 2 e k ⋅ e k ≤ e k / 2 ≤ 1 / 4 0<e_{k+1}\le2e_k\cdot e_k\le e_k/2\le1/4 0 < e k + 1 ≤ 2 e k ⋅ e k ≤ e k /2 ≤ 1/4 k k k k ∈ N ≥ 0 k\in\N k ∈ N ≥ 0 0 < e k ≤ 1 / 4 0<e_k\le1/4 0 < e k ≤ 1/4 e k + 1 ≤ e k / 2 e_{k+1}\le e_k/2 e k + 1 ≤ e k /2 e k ≤ 2 − k / 4 → 0 e_k\le2^{-k}/4\to0 e k ≤ 2 − k /4 → 0 ( e k ) (e_k) ( e k ) 0 0 0 k k k ∣ e k + 1 ∣ = a k ∣ e k ∣ 2 ≤ 2 ∣ e k ∣ 2 \lvert e_{k+1}\rvert=a_k\lvert e_k\rvert^2\le2\lvert e_k\rvert^2 ∣ e k + 1 ∣ = a k ∣ e k ∣ 2 ≤ 2 ∣ e k ∣ 2 R \R R 0 0 0 k k k e k ≠ 0 e_k\ne0 e k = 0 ∣ e k + 1 ∣ / ∣ e k ∣ 2 = a k \lvert e_{k+1}\rvert/\lvert e_k\rvert^2=a_k ∣ e k + 1 ∣ / ∣ e k ∣ 2 = a k 1 1 1 2 2 2 ( e k ) (e_k) ( e k ) 0 0 0 2 2 2
2 二分法 補題 2.1. a < b a<b a < b f : [ a , b ] → R f\colon[a,b]\to\R f : [ a , b ] → R ( a n ) n ∈ N ≥ 0 (a_n)_{n\in\N} ( a n ) n ∈ N ≥ 0 ( b n ) n ∈ N ≥ 0 (b_n)_{n\in\N} ( b n ) n ∈ N ≥ 0 n ∈ N ≥ 0 n\in\N n ∈ N ≥ 0 a ≤ a n ≤ a n + 1 < b n + 1 ≤ b n ≤ b a\le a_n\le a_{n+1}<b_{n+1}\le b_n\le b a ≤ a n ≤ a n + 1 < b n + 1 ≤ b n ≤ b f ( a n ) f ( b n ) < 0 f(a_n)f(b_n)<0 f ( a n ) f ( b n ) < 0 b n − a n → 0 b_n-a_n\to0 b n − a n → 0
各n ∈ N ≥ 0 n\in\N n ∈ N ≥ 0 ( a n , b n ) (a_n,b_n) ( a n , b n ) f f f
⋂ n ∈ N ≥ 0 [ a n , b n ] \bigcap_{n\in\N}[a_n,b_n] ⋂ n ∈ N ≥ 0 [ a n , b n ] r r r f ( r ) = 0 f(r)=0 f ( r ) = 0 a n → r a_n\to r a n → r b n → r b_n\to r b n → r 任意のn ∈ N ≥ 0 n\in\N n ∈ N ≥ 0 x ∈ [ a n , b n ] x\in[a_n,b_n] x ∈ [ a n , b n ] ∣ x − r ∣ ≤ b n − a n \lvert x-r\rvert\le b_n-a_n ∣ x − r ∣ ≤ b n − a n ∣ ( a n + b n ) / 2 − r ∣ ≤ ( b n − a n ) / 2 \lvert(a_n+b_n)/2-r\rvert\le(b_n-a_n)/2 ∣( a n + b n ) /2 − r ∣ ≤ ( b n − a n ) /2
証明. (1) を示す。f ( a n ) < 0 < f ( b n ) f(a_n)<0<f(b_n) f ( a n ) < 0 < f ( b n ) f f f [ a n , b n ] [a_n,b_n] [ a n , b n ] f ( a n ) > 0 > f ( b n ) f(a_n)>0>f(b_n) f ( a n ) > 0 > f ( b n ) − f -f − f [ a n , b n ] [a_n,b_n] [ a n , b n ] §D1.12 定理 1.1 を適用する。
(2) を示す。[ a n , b n ] [a_n,b_n] [ a n , b n ] 0 0 0 §D1.7 命題 3.2 により共通部分はただ一点r r r a n ≤ r ≤ b n a_n\le r\le b_n a n ≤ r ≤ b n 0 ≤ r − a n ≤ b n − a n 0\le r-a_n\le b_n-a_n 0 ≤ r − a n ≤ b n − a n 0 ≤ b n − r ≤ b n − a n 0\le b_n-r\le b_n-a_n 0 ≤ b n − r ≤ b n − a n a n → r a_n\to r a n → r b n → r b_n\to r b n → r f f f r r r f ( a n ) f ( b n ) → f ( r ) 2 f(a_n)f(b_n)\to f(r)^2 f ( a n ) f ( b n ) → f ( r ) 2 f ( r ) 2 ≤ 0 f(r)^2\le0 f ( r ) 2 ≤ 0 f ( r ) = 0 f(r)=0 f ( r ) = 0
(3) を示す。r ∈ [ a n , b n ] r\in[a_n,b_n] r ∈ [ a n , b n ] [ a n , b n ] [a_n,b_n] [ a n , b n ] r r r b n − a n b_n-a_n b n − a n r r r ( b n − a n ) / 2 (b_n-a_n)/2 ( b n − a n ) /2 ▨
定義 2.2. a < b a<b a < b f : [ a , b ] → R f\colon[a,b]\to\R f : [ a , b ] → R f ( a ) f ( b ) < 0 f(a)f(b)<0 f ( a ) f ( b ) < 0 a 0 : = a a_0:=a a 0 := a b 0 : = b b_0:=b b 0 := b n ∈ N ≥ 0 n\in\N n ∈ N ≥ 0 a n < b n a_n<b_n a n < b n f ( a n ) f ( b n ) < 0 f(a_n)f(b_n)<0 f ( a n ) f ( b n ) < 0 a n , b n a_n,b_n a n , b n m n : = ( a n + b n ) / 2 m_n:=(a_n+b_n)/2 m n := ( a n + b n ) /2
f ( m n ) = 0 f(m_n)=0 f ( m n ) = 0 m n m_n m n f ( m n ) ≠ 0 f(m_n)\ne0 f ( m n ) = 0 f ( a n ) f ( m n ) < 0 f(a_n)f(m_n)<0 f ( a n ) f ( m n ) < 0 a n + 1 : = a n a_{n+1}:=a_n a n + 1 := a n b n + 1 : = m n b_{n+1}:=m_n b n + 1 := m n f ( m n ) ≠ 0 f(m_n)\ne0 f ( m n ) = 0 f ( a n ) f ( m n ) > 0 f(a_n)f(m_n)>0 f ( a n ) f ( m n ) > 0 a n + 1 : = m n a_{n+1}:=m_n a n + 1 := m n b n + 1 : = b n b_{n+1}:=b_n b n + 1 := b n (3) の場合、f ( m n ) f(m_n) f ( m n ) f ( a n ) f(a_n) f ( a n ) f ( a n ) f(a_n) f ( a n ) f ( b n ) f(b_n) f ( b n ) f ( m n ) f ( b n ) < 0 f(m_n)f(b_n)<0 f ( m n ) f ( b n ) < 0 (2) と(3) のどちらの場合もa n + 1 < b n + 1 a_{n+1}<b_{n+1} a n + 1 < b n + 1 f ( a n + 1 ) f ( b n + 1 ) < 0 f(a_{n+1})f(b_{n+1})<0 f ( a n + 1 ) f ( b n + 1 ) < 0 二分法 (bisection method )
定理 2.3. a < b a<b a < b f : [ a , b ] → R f\colon[a,b]\to\R f : [ a , b ] → R f ( a ) f ( b ) < 0 f(a)f(b)<0 f ( a ) f ( b ) < 0 n ∈ N ≥ 0 n\in\N n ∈ N ≥ 0 f ( m n ) ≠ 0 f(m_n)\ne0 f ( m n ) = 0
すべてのn ∈ N ≥ 0 n\in\N n ∈ N ≥ 0 [ a n + 1 , b n + 1 ] ⊂ [ a n , b n ] [a_{n+1},b_{n+1}]\subset[a_n,b_n] [ a n + 1 , b n + 1 ] ⊂ [ a n , b n ] b n − a n = 2 − n ( b − a ) b_n-a_n=2^{-n}(b-a) b n − a n = 2 − n ( b − a )
各n ∈ N ≥ 0 n\in\N n ∈ N ≥ 0 ( a n , b n ) (a_n,b_n) ( a n , b n ) f f f
f f f r r r n ∈ N ≥ 0 n\in\N n ∈ N ≥ 0 r ∈ [ a n , b n ] r\in[a_n,b_n] r ∈ [ a n , b n ] ∣ m n − r ∣ ≤ 2 − ( n + 1 ) ( b − a ) \lvert m_n-r\rvert\le2^{-(n+1)}(b-a) ∣ m n − r ∣ ≤ 2 − ( n + 1 ) ( b − a ) τ > 0 \tau>0 τ > 0 n ≥ log 2 ( ( b − a ) / τ ) − 1 n\ge\log_2((b-a)/\tau)-1 n ≥ log 2 (( b − a ) / τ ) − 1 ∣ m n − r ∣ ≤ τ \lvert m_n-r\rvert\le\tau ∣ m n − r ∣ ≤ τ 証明. 定義 2.2 (2) と定義 2.2 (3) のどちらの場合も[ a n + 1 , b n + 1 ] [a_{n+1},b_{n+1}] [ a n + 1 , b n + 1 ] [ a n , b n ] [a_n,b_n] [ a n , b n ] n n n (1) が成り立つ。定義 2.2 によりf ( a n ) f ( b n ) < 0 f(a_n)f(b_n)<0 f ( a n ) f ( b n ) < 0 (1) によりa ≤ a n ≤ a n + 1 < b n + 1 ≤ b n ≤ b a\le a_n\le a_{n+1}<b_{n+1}\le b_n\le b a ≤ a n ≤ a n + 1 < b n + 1 ≤ b n ≤ b b n − a n → 0 b_n-a_n\to0 b n − a n → 0 補題 2.1 を適用することができる。(2) は補題 2.1 (1) である。補題 2.1 (2) のr r r f ( r ) = 0 f(r)=0 f ( r ) = 0 n n n r ∈ [ a n , b n ] r\in[a_n,b_n] r ∈ [ a n , b n ] 補題 2.1 (3) により∣ m n − r ∣ ≤ ( b n − a n ) / 2 = 2 − ( n + 1 ) ( b − a ) \lvert m_n-r\rvert\le(b_n-a_n)/2=2^{-(n+1)}(b-a) ∣ m n − r ∣ ≤ ( b n − a n ) /2 = 2 − ( n + 1 ) ( b − a ) n ≥ log 2 ( ( b − a ) / τ ) − 1 n\ge\log_2((b-a)/\tau)-1 n ≥ log 2 (( b − a ) / τ ) − 1 2 − ( n + 1 ) ( b − a ) ≤ τ 2^{-(n+1)}(b-a)\le\tau 2 − ( n + 1 ) ( b − a ) ≤ τ ▨
3 不動点反復 定義 3.1. D ⊂ R D\subset\R D ⊂ R g : D → R g\colon D\to\R g : D → R x 0 ∈ D x_0\in D x 0 ∈ D x 0 , … , x k ∈ D x_0,\dots,x_k\in D x 0 , … , x k ∈ D x k + 1 : = g ( x k ) x_{k+1}:=g(x_k) x k + 1 := g ( x k ) k ∈ N ≥ 0 k\in\N k ∈ N ≥ 0 x k ∈ D x_k\in D x k ∈ D ( x k ) k ∈ N ≥ 0 (x_k)_{k\in\N} ( x k ) k ∈ N ≥ 0 x 0 x_0 x 0 g g g 不動点反復 (fixed-point iteration )f : D → R f\colon D\to\R f : D → R x ∈ D x\in D x ∈ D λ ( x ) ≠ 0 \lambda(x)\ne0 λ ( x ) = 0 λ : D → R \lambda\colon D\to\R λ : D → R g ( x ) : = x − λ ( x ) f ( x ) g(x):=x-\lambda(x)f(x) g ( x ) := x − λ ( x ) f ( x ) g ( x ) = x g(x)=x g ( x ) = x λ ( x ) f ( x ) = 0 \lambda(x)f(x)=0 λ ( x ) f ( x ) = 0 λ ( x ) ≠ 0 \lambda(x)\ne0 λ ( x ) = 0 g g g f f f
補題 3.2. I ⊂ R I\subset\R I ⊂ R g : I → R g\colon I\to\R g : I → R I I I I I I L ≥ 0 L\ge0 L ≥ 0 I I I t t t ∣ g ′ ( t ) ∣ ≤ L \lvert g'(t)\rvert\le L ∣ g ′ ( t )∣ ≤ L x , y ∈ I x,y\in I x , y ∈ I ∣ g ( x ) − g ( y ) ∣ ≤ L ∣ x − y ∣ \lvert g(x)-g(y)\rvert\le L\lvert x-y\rvert ∣ g ( x ) − g ( y )∣ ≤ L ∣ x − y ∣
証明. x < y x<y x < y [ x , y ] ⊂ I [x,y]\subset I [ x , y ] ⊂ I ( x , y ) (x,y) ( x , y ) I I I §D1.14 定理 3.1 によりg ( y ) − g ( x ) = g ′ ( c ) ( y − x ) g(y)-g(x)=g'(c)(y-x) g ( y ) − g ( x ) = g ′ ( c ) ( y − x ) c ∈ ( x , y ) c\in(x,y) c ∈ ( x , y ) ∣ g ( y ) − g ( x ) ∣ ≤ L ( y − x ) \lvert g(y)-g(x)\rvert\le L(y-x) ∣ g ( y ) − g ( x )∣ ≤ L ( y − x ) ▨
定理 3.3.
I ⊂ R I\subset\R I ⊂ R g : I → I g\colon I\to I g : I → I q ∈ [ 0 , 1 ) q\in[0,1) q ∈ [ 0 , 1 ) x , y ∈ I x,y\in I x , y ∈ I ∣ g ( x ) − g ( y ) ∣ ≤ q ∣ x − y ∣ \lvert g(x)-g(y)\rvert\le q\lvert x-y\rvert ∣ g ( x ) − g ( y )∣ ≤ q ∣ x − y ∣ g g g I I I x ∗ x^* x ∗ x 0 ∈ I x_0\in I x 0 ∈ I g g g ( x k ) (x_k) ( x k ) x ∗ x^* x ∗ ∣ x k − x ∗ ∣ ≤ q k 1 − q ∣ x 1 − x 0 ∣ ( k ∈ N ≥ 0 ) , ∣ x k − x ∗ ∣ ≤ q 1 − q ∣ x k − x k − 1 ∣ ( k ∈ N ≥ 1 ) \lvert x_k-x^*\rvert\le\frac{q^k}{1-q}\lvert x_1-x_0\rvert\quad(k\in\N),\qquad\lvert x_k-x^*\rvert\le\frac{q}{1-q}\lvert x_k-x_{k-1}\rvert\quad(k\in\NN) ∣ x k − x ∗ ∣ ≤ 1 − q q k ∣ x 1 − x 0 ∣ ( k ∈ N ≥ 0 ) , ∣ x k − x ∗ ∣ ≤ 1 − q q ∣ x k − x k − 1 ∣ ( k ∈ N ≥ 1 ) U ⊂ R U\subset\R U ⊂ R g : U → R g\colon U\to\R g : U → R C 1 C^1 C 1 x ∗ ∈ U x^*\in U x ∗ ∈ U g ( x ∗ ) = x ∗ g(x^*)=x^* g ( x ∗ ) = x ∗ ∣ g ′ ( x ∗ ) ∣ < 1 \lvert g'(x^*)\rvert<1 ∣ g ′ ( x ∗ )∣ < 1 ∣ g ′ ( x ∗ ) ∣ < q < 1 \lvert g'(x^*)\rvert<q<1 ∣ g ′ ( x ∗ )∣ < q < 1 q q q δ > 0 \delta>0 δ > 0 J : = [ x ∗ − δ , x ∗ + δ ] J:=[x^*-\delta,x^*+\delta] J := [ x ∗ − δ , x ∗ + δ ] J ⊂ U J\subset U J ⊂ U g ( J ) ⊂ J g(J)\subset J g ( J ) ⊂ J x 0 ∈ J x_0\in J x 0 ∈ J g g g k ∈ N ≥ 0 k\in\N k ∈ N ≥ 0 ∣ x k − x ∗ ∣ ≤ q k ∣ x 0 − x ∗ ∣ \lvert x_k-x^*\rvert\le q^k\lvert x_0-x^*\rvert ∣ x k − x ∗ ∣ ≤ q k ∣ x 0 − x ∗ ∣ (2) の仮定の下でg ′ ( x ∗ ) ≠ 0 g'(x^*)\ne0 g ′ ( x ∗ ) = 0 (2) のδ \delta δ J J J t t t g ′ ( t ) ≠ 0 g'(t)\ne0 g ′ ( t ) = 0 x 0 ∈ J ∖ { x ∗ } x_0\in J\setminus\{x^*\} x 0 ∈ J ∖ { x ∗ } k k k x k ≠ x ∗ x_k\ne x^* x k = x ∗ e k : = x k − x ∗ e_k:=x_k-x^* e k := x k − x ∗ e k + 1 / e k → g ′ ( x ∗ ) e_{k+1}/e_k\to g'(x^*) e k + 1 / e k → g ′ ( x ∗ ) ( x k ) (x_k) ( x k ) x ∗ x^* x ∗ ∣ g ′ ( x ∗ ) ∣ \lvert g'(x^*)\rvert ∣ g ′ ( x ∗ )∣ g ′ ( x ∗ ) = 0 g'(x^*)=0 g ′ ( x ∗ ) = 0 x 0 ∈ J x_0\in J x 0 ∈ J k k k x k ≠ x ∗ x_k\ne x^* x k = x ∗ ( x k ) (x_k) ( x k ) x ∗ x^* x ∗ 証明. (1) を示す。I I I R \R R R \R R §D1.10 定理 1.1 により完備であるから、§E2.5 定理 3.2 により距離∣ x − y ∣ \lvert x-y\rvert ∣ x − y ∣ I I I g g g q q q §E2.7 定理 2.2 によりg g g x ∗ x^* x ∗ x 0 ∈ I x_0\in I x 0 ∈ I x ∗ x^* x ∗ §E2.7 系 2.3 である。
(2) を示す。g ′ g' g ′ x ∗ x^* x ∗ δ > 0 \delta>0 δ > 0 J ⊂ U J\subset U J ⊂ U t ∈ J t\in J t ∈ J ∣ g ′ ( t ) ∣ ≤ q \lvert g'(t)\rvert\le q ∣ g ′ ( t )∣ ≤ q 補題 3.2 をJ J J x ∈ J x\in J x ∈ J ∣ g ( x ) − x ∗ ∣ = ∣ g ( x ) − g ( x ∗ ) ∣ ≤ q ∣ x − x ∗ ∣ ≤ q δ \lvert g(x)-x^*\rvert=\lvert g(x)-g(x^*)\rvert\le q\lvert x-x^*\rvert\le q\delta ∣ g ( x ) − x ∗ ∣ = ∣ g ( x ) − g ( x ∗ )∣ ≤ q ∣ x − x ∗ ∣ ≤ q δ g ( J ) ⊂ J g(J)\subset J g ( J ) ⊂ J x 0 ∈ J x_0\in J x 0 ∈ J k k k x k ∈ J x_k\in J x k ∈ J ∣ x k + 1 − x ∗ ∣ ≤ q ∣ x k − x ∗ ∣ \lvert x_{k+1}-x^*\rvert\le q\lvert x_k-x^*\rvert ∣ x k + 1 − x ∗ ∣ ≤ q ∣ x k − x ∗ ∣
(3) を示す。g ′ g' g ′ x ∗ x^* x ∗ g ′ ( x ∗ ) ≠ 0 g'(x^*)\ne0 g ′ ( x ∗ ) = 0 δ \delta δ J J J g ′ ≠ 0 g'\ne0 g ′ = 0 x ∈ J ∖ { x ∗ } x\in J\setminus\{x^*\} x ∈ J ∖ { x ∗ } §D1.14 定理 3.1 によりg ( x ) − x ∗ = g ( x ) − g ( x ∗ ) = g ′ ( ξ ) ( x − x ∗ ) g(x)-x^*=g(x)-g(x^*)=g'(\xi)(x-x^*) g ( x ) − x ∗ = g ( x ) − g ( x ∗ ) = g ′ ( ξ ) ( x − x ∗ ) ξ \xi ξ x x x x ∗ x^* x ∗ ξ ∈ J \xi\in J ξ ∈ J g ( x ) ≠ x ∗ g(x)\ne x^* g ( x ) = x ∗ x 0 ≠ x ∗ x_0\ne x^* x 0 = x ∗ k k k x k ≠ x ∗ x_k\ne x^* x k = x ∗ x = x k x=x_k x = x k e k + 1 = g ′ ( ξ k ) e k e_{k+1}=g'(\xi_k)e_k e k + 1 = g ′ ( ξ k ) e k ∣ ξ k − x ∗ ∣ ≤ ∣ e k ∣ \lvert\xi_k-x^*\rvert\le\lvert e_k\rvert ∣ ξ k − x ∗ ∣ ≤ ∣ e k ∣ e k → 0 e_k\to0 e k → 0 g ′ g' g ′ e k + 1 / e k = g ′ ( ξ k ) → g ′ ( x ∗ ) e_{k+1}/e_k=g'(\xi_k)\to g'(x^*) e k + 1 / e k = g ′ ( ξ k ) → g ′ ( x ∗ ) ∣ g ′ ( x ∗ ) ∣ ∈ ( 0 , 1 ) \lvert g'(x^*)\rvert\in(0,1) ∣ g ′ ( x ∗ )∣ ∈ ( 0 , 1 ) ( x k ) (x_k) ( x k ) ∣ g ′ ( x ∗ ) ∣ \lvert g'(x^*)\rvert ∣ g ′ ( x ∗ )∣ g ′ ( x ∗ ) = 0 g'(x^*)=0 g ′ ( x ∗ ) = 0 k k k x k ≠ x ∗ x_k\ne x^* x k = x ∗ e k + 1 / e k = g ′ ( ξ k ) → 0 e_{k+1}/e_k=g'(\xi_k)\to0 e k + 1 / e k = g ′ ( ξ k ) → 0 ▨
命題 3.4. D ⊂ R D\subset\R D ⊂ R g : D → R g\colon D\to\R g : D → R x ∗ ∈ D x^*\in D x ∗ ∈ D δ 0 > 0 \delta_0>0 δ 0 > 0 ( x ∗ − δ 0 , x ∗ + δ 0 ) ⊂ D (x^*-\delta_0,x^*+\delta_0)\subset D ( x ∗ − δ 0 , x ∗ + δ 0 ) ⊂ D g ( x ∗ ) = x ∗ g(x^*)=x^* g ( x ∗ ) = x ∗ g g g x ∗ x^* x ∗ ∣ g ′ ( x ∗ ) ∣ > 1 \lvert g'(x^*)\rvert>1 ∣ g ′ ( x ∗ )∣ > 1 x 0 ∈ D x_0\in D x 0 ∈ D g g g ( x k ) (x_k) ( x k ) x ∗ x^* x ∗ K ∈ N ≥ 0 K\in\N K ∈ N ≥ 0 k ≥ K k\ge K k ≥ K k k k x k = x ∗ x_k=x^* x k = x ∗
証明. 1 < ρ < ∣ g ′ ( x ∗ ) ∣ 1<\rho<\lvert g'(x^*)\rvert 1 < ρ < ∣ g ′ ( x ∗ )∣ ρ \rho ρ ∣ ( g ( x ) − g ( x ∗ ) ) / ( x − x ∗ ) ∣ → ∣ g ′ ( x ∗ ) ∣ \lvert(g(x)-g(x^*))/(x-x^*)\rvert\to\lvert g'(x^*)\rvert ∣( g ( x ) − g ( x ∗ )) / ( x − x ∗ )∣ → ∣ g ′ ( x ∗ )∣ x → x ∗ x\to x^* x → x ∗ 0 < δ ≤ δ 0 0<\delta\le\delta_0 0 < δ ≤ δ 0 0 < ∣ x − x ∗ ∣ < δ 0<\lvert x-x^*\rvert<\delta 0 < ∣ x − x ∗ ∣ < δ ∣ g ( x ) − x ∗ ∣ ≥ ρ ∣ x − x ∗ ∣ \lvert g(x)-x^*\rvert\ge\rho\lvert x-x^*\rvert ∣ g ( x ) − x ∗ ∣ ≥ ρ ∣ x − x ∗ ∣ x k → x ∗ x_k\to x^* x k → x ∗ K K K k ≥ K k\ge K k ≥ K ∣ x k − x ∗ ∣ < δ \lvert x_k-x^*\rvert<\delta ∣ x k − x ∗ ∣ < δ j ≥ K j\ge K j ≥ K x j ≠ x ∗ x_j\ne x^* x j = x ∗ k ≥ j k\ge j k ≥ j x k ≠ x ∗ x_k\ne x^* x k = x ∗ ∣ x k + 1 − x ∗ ∣ ≥ ρ ∣ x k − x ∗ ∣ > 0 \lvert x_{k+1}-x^*\rvert\ge\rho\lvert x_k-x^*\rvert>0 ∣ x k + 1 − x ∗ ∣ ≥ ρ ∣ x k − x ∗ ∣ > 0 k ≥ j k\ge j k ≥ j ∣ x k − x ∗ ∣ ≥ ρ k − j ∣ x j − x ∗ ∣ \lvert x_k-x^*\rvert\ge\rho^{k-j}\lvert x_j-x^*\rvert ∣ x k − x ∗ ∣ ≥ ρ k − j ∣ x j − x ∗ ∣ ρ k − j ∣ x j − x ∗ ∣ → + ∞ \rho^{k-j}\lvert x_j-x^*\rvert\to+\infty ρ k − j ∣ x j − x ∗ ∣ → + ∞ k ≥ j k\ge j k ≥ j ∣ x k − x ∗ ∣ ≥ δ \lvert x_k-x^*\rvert\ge\delta ∣ x k − x ∗ ∣ ≥ δ k ≥ K k\ge K k ≥ K ∣ x k − x ∗ ∣ < δ \lvert x_k-x^*\rvert<\delta ∣ x k − x ∗ ∣ < δ j ≥ K j\ge K j ≥ K x j = x ∗ x_j=x^* x j = x ∗ ▨
例 3.6. g − ( x ) = x − x 3 g_-(x)=x-x^3 g − ( x ) = x − x 3 g + ( x ) = x + x 3 g_+(x)=x+x^3 g + ( x ) = x + x 3 0 0 0 g ± ′ ( 0 ) = 1 g_\pm'(0)=1 g ± ′ ( 0 ) = 1 x 0 ∈ ( 0 , 1 ) x_0\in(0,1) x 0 ∈ ( 0 , 1 ) g − g_- g − 0 < x k + 1 = x k ( 1 − x k 2 ) < x k 0<x_{k+1}=x_k(1-x_k^2)<x_k 0 < x k + 1 = x k ( 1 − x k 2 ) < x k ( − x k ) (-x_k) ( − x k ) §D1.7 定理 1.1 を適用すると( x k ) (x_k) ( x k ) L ∈ [ 0 , x 0 ] L\in[0,x_0] L ∈ [ 0 , x 0 ] g − g_- g − L = L − L 3 L=L-L^3 L = L − L 3 L = 0 L=0 L = 0 e k + 1 / e k = 1 − x k 2 → 1 e_{k+1}/e_k=1-x_k^2\to1 e k + 1 / e k = 1 − x k 2 → 1 ( x k ) (x_k) ( x k ) q > 1 q>1 q > 1 ∣ e k + 1 ∣ / ∣ e k ∣ q = ( 1 − x k 2 ) x k 1 − q → + ∞ \lvert e_{k+1}\rvert/\lvert e_k\rvert^q=(1-x_k^2)x_k^{1-q}\to+\infty ∣ e k + 1 ∣ / ∣ e k ∣ q = ( 1 − x k 2 ) x k 1 − q → + ∞ q q q x 0 > 0 x_0>0 x 0 > 0 g + g_+ g + x k + 1 = x k ( 1 + x k 2 ) > x k x_{k+1}=x_k(1+x_k^2)>x_k x k + 1 = x k ( 1 + x k 2 ) > x k ( x k ) (x_k) ( x k ) §D1.7 定理 1.1 によりあるL ≥ x 0 > 0 L\ge x_0>0 L ≥ x 0 > 0 L = L + L 3 L=L+L^3 L = L + L 3 L = 0 L=0 L = 0 L > 0 L>0 L > 0 ( x k ) (x_k) ( x k ) + ∞ +\infty + ∞
4 Newton 法 定義 4.1. I ⊂ R I\subset\R I ⊂ R f : I → R f\colon I\to\R f : I → R x ∈ I x\in I x ∈ I f ′ ( x ) ≠ 0 f'(x)\ne0 f ′ ( x ) = 0 x x x t ↦ f ( x ) + f ′ ( x ) ( t − x ) t\mapsto f(x)+f'(x)(t-x) t ↦ f ( x ) + f ′ ( x ) ( t − x )
N f ( x ) : = x − f ( x ) f ′ ( x ) N_f(x):=x-\frac{f(x)}{f'(x)} N f ( x ) := x − f ′ ( x ) f ( x ) をもつ。x 0 ∈ I x_0\in I x 0 ∈ I x k ∈ I x_k\in I x k ∈ I f ′ ( x k ) ≠ 0 f'(x_k)\ne0 f ′ ( x k ) = 0 x k + 1 : = N f ( x k ) x_{k+1}:=N_f(x_k) x k + 1 := N f ( x k ) Newton 法 (Newton's method )k ∈ N ≥ 0 k\in\N k ∈ N ≥ 0 x k ∈ I x_k\in I x k ∈ I f ′ ( x k ) ≠ 0 f'(x_k)\ne0 f ′ ( x k ) = 0 ( x k ) (x_k) ( x k ) D : = { x ∈ I ∣ f ′ ( x ) ≠ 0 } D:=\{x\in I\mid f'(x)\ne0\} D := { x ∈ I ∣ f ′ ( x ) = 0 } N f ( x ) = x − λ ( x ) f ( x ) N_f(x)=x-\lambda(x)f(x) N f ( x ) = x − λ ( x ) f ( x ) λ = 1 / f ′ \lambda=1/f' λ = 1/ f ′ N f N_f N f 定義 3.1 によりN f N_f N f D D D f f f
補題 4.2. I ⊂ R I\subset\R I ⊂ R f : I → R f\colon I\to\R f : I → R C 2 C^2 C 2 r ∈ I r\in I r ∈ I f ( r ) = 0 f(r)=0 f ( r ) = 0 x ∈ I x\in I x ∈ I f ′ ( x ) ≠ 0 f'(x)\ne0 f ′ ( x ) = 0 x x x r r r ξ \xi ξ
N f ( x ) − r = f ′ ′ ( ξ ) 2 f ′ ( x ) ( x − r ) 2 N_f(x)-r=\frac{f''(\xi)}{2f'(x)}(x-r)^2 N f ( x ) − r = 2 f ′ ( x ) f ′′ ( ξ ) ( x − r ) 2 が成り立つ。
証明. x = r x=r x = r f ( r ) = 0 f(r)=0 f ( r ) = 0 N f ( r ) = r N_f(r)=r N f ( r ) = r ξ = r \xi=r ξ = r x ≠ r x\ne r x = r §D1.16 定理 2.1 をn = 2 n=2 n = 2 x x x r r r x x x r r r ξ \xi ξ
0 = f ( r ) = f ( x ) + f ′ ( x ) ( r − x ) + f ′ ′ ( ξ ) 2 ( r − x ) 2 0=f(r)=f(x)+f'(x)(r-x)+\frac{f''(\xi)}{2}(r-x)^2 0 = f ( r ) = f ( x ) + f ′ ( x ) ( r − x ) + 2 f ′′ ( ξ ) ( r − x ) 2 である。両辺をf ′ ( x ) f'(x) f ′ ( x ) f ( x ) / f ′ ( x ) = ( x − r ) − f ′ ′ ( ξ ) 2 f ′ ( x ) ( x − r ) 2 f(x)/f'(x)=(x-r)-\frac{f''(\xi)}{2f'(x)}(x-r)^2 f ( x ) / f ′ ( x ) = ( x − r ) − 2 f ′ ( x ) f ′′ ( ξ ) ( x − r ) 2 N f ( x ) − r = x − f ( x ) / f ′ ( x ) − r N_f(x)-r=x-f(x)/f'(x)-r N f ( x ) − r = x − f ( x ) / f ′ ( x ) − r ▨
定理 4.3. I ⊂ R I\subset\R I ⊂ R f : I → R f\colon I\to\R f : I → R C 2 C^2 C 2 r ∈ I r\in I r ∈ I f ( r ) = 0 f(r)=0 f ( r ) = 0 f ′ ( r ) ≠ 0 f'(r)\ne0 f ′ ( r ) = 0 K : = ( ∣ f ′ ′ ( r ) ∣ + 1 ) / ∣ f ′ ( r ) ∣ K:=(\lvert f''(r)\rvert+1)/\lvert f'(r)\rvert K := (∣ f ′′ ( r )∣ + 1 ) / ∣ f ′ ( r )∣ δ > 0 \delta>0 δ > 0 J : = [ r − δ , r + δ ] ⊂ I J:=[r-\delta,r+\delta]\subset I J := [ r − δ , r + δ ] ⊂ I x 0 ∈ J x_0\in J x 0 ∈ J ( x k ) (x_k) ( x k ) e k : = x k − r e_k:=x_k-r e k := x k − r
すべてのk ∈ N ≥ 0 k\in\N k ∈ N ≥ 0 x k ∈ J x_k\in J x k ∈ J ∣ e k + 1 ∣ ≤ K e k 2 \lvert e_{k+1}\rvert\le Ke_k^2 ∣ e k + 1 ∣ ≤ K e k 2 ∣ e k + 1 ∣ ≤ ∣ e k ∣ / 2 \lvert e_{k+1}\rvert\le\lvert e_k\rvert/2 ∣ e k + 1 ∣ ≤ ∣ e k ∣ /2 x k → r x_k\to r x k → r k k k x k = r x_k=r x k = r j ≥ k j\ge k j ≥ k j j j x j = r x_j=r x j = r
すべてのk k k x k ≠ r x_k\ne r x k = r e k + 1 / e k 2 → f ′ ′ ( r ) / ( 2 f ′ ( r ) ) e_{k+1}/e_k^2\to f''(r)/(2f'(r)) e k + 1 / e k 2 → f ′′ ( r ) / ( 2 f ′ ( r )) f ′ ′ ( r ) ≠ 0 f''(r)\ne0 f ′′ ( r ) = 0 ( x k ) (x_k) ( x k ) r r r 2 2 2 ∣ f ′ ′ ( r ) / ( 2 f ′ ( r ) ) ∣ \lvert f''(r)/(2f'(r))\rvert ∣ f ′′ ( r ) / ( 2 f ′ ( r ))∣ f ′ ′ ( r ) = 0 f''(r)=0 f ′′ ( r ) = 0 ∣ e k + 1 ∣ / e k 2 → 0 \lvert e_{k+1}\rvert/e_k^2\to0 ∣ e k + 1 ∣ / e k 2 → 0 ( x k ) (x_k) ( x k ) r r r 2 2 2
証明. f ′ f' f ′ f ′ ′ f'' f ′′ r r r δ > 0 \delta>0 δ > 0 J ⊂ I J\subset I J ⊂ I K δ ≤ 1 / 2 K\delta\le1/2 K δ ≤ 1/2 t ∈ J t\in J t ∈ J ∣ f ′ ( t ) ∣ ≥ ∣ f ′ ( r ) ∣ / 2 \lvert f'(t)\rvert\ge\lvert f'(r)\rvert/2 ∣ f ′ ( t )∣ ≥ ∣ f ′ ( r )∣ /2 ∣ f ′ ′ ( t ) ∣ ≤ ∣ f ′ ′ ( r ) ∣ + 1 \lvert f''(t)\rvert\le\lvert f''(r)\rvert+1 ∣ f ′′ ( t )∣ ≤ ∣ f ′′ ( r )∣ + 1 x ∈ J x\in J x ∈ J f ′ ( x ) ≠ 0 f'(x)\ne0 f ′ ( x ) = 0 補題 4.2 のξ \xi ξ J J J
∣ N f ( x ) − r ∣ ≤ ∣ f ′ ′ ( r ) ∣ + 1 2 ⋅ ∣ f ′ ( r ) ∣ / 2 ( x − r ) 2 = K ( x − r ) 2 ≤ K δ ∣ x − r ∣ ≤ ∣ x − r ∣ 2 \lvert N_f(x)-r\rvert\le\frac{\lvert f''(r)\rvert+1}{2\cdot\lvert f'(r)\rvert/2}(x-r)^2=K(x-r)^2\le K\delta\lvert x-r\rvert\le\frac{\lvert x-r\rvert}{2} ∣ N f ( x ) − r ∣ ≤ 2 ⋅ ∣ f ′ ( r )∣ /2 ∣ f ′′ ( r )∣ + 1 ( x − r ) 2 = K ( x − r ) 2 ≤ K δ ∣ x − r ∣ ≤ 2 ∣ x − r ∣ であり、N f ( x ) ∈ J N_f(x)\in J N f ( x ) ∈ J k k k (1) の評価が成り立つ。∣ e k ∣ ≤ 2 − k ∣ e 0 ∣ \lvert e_k\rvert\le2^{-k}\lvert e_0\rvert ∣ e k ∣ ≤ 2 − k ∣ e 0 ∣ x k → r x_k\to r x k → r N f ( r ) = r N_f(r)=r N f ( r ) = r x k = r x_k=r x k = r r r r
すべてのk k k x k ≠ r x_k\ne r x k = r 補題 4.2 によりe k + 1 / e k 2 = f ′ ′ ( ξ k ) / ( 2 f ′ ( x k ) ) e_{k+1}/e_k^2=f''(\xi_k)/(2f'(x_k)) e k + 1 / e k 2 = f ′′ ( ξ k ) / ( 2 f ′ ( x k )) ξ k \xi_k ξ k x k x_k x k r r r ξ k → r \xi_k\to r ξ k → r x k → r x_k\to r x k → r f ′ , f ′ ′ f',f'' f ′ , f ′′ e k + 1 / e k 2 → f ′ ′ ( r ) / ( 2 f ′ ( r ) ) e_{k+1}/e_k^2\to f''(r)/(2f'(r)) e k + 1 / e k 2 → f ′′ ( r ) / ( 2 f ′ ( r )) f ′ ′ ( r ) ≠ 0 f''(r)\ne0 f ′′ ( r ) = 0 定義 1.1 (1) のq = 2 q=2 q = 2 f ′ ′ ( r ) = 0 f''(r)=0 f ′′ ( r ) = 0 ∣ e k + 1 ∣ / ∣ e k ∣ = ( ∣ e k + 1 ∣ / e k 2 ) ∣ e k ∣ → 0 \lvert e_{k+1}\rvert/\lvert e_k\rvert=(\lvert e_{k+1}\rvert/e_k^2)\lvert e_k\rvert\to0 ∣ e k + 1 ∣ / ∣ e k ∣ = (∣ e k + 1 ∣ / e k 2 ) ∣ e k ∣ → 0 ∣ e k + 1 ∣ / e k 2 \lvert e_{k+1}\rvert/e_k^2 ∣ e k + 1 ∣ / e k 2 0 0 0 2 2 2 ▨
例 4.4. f ( x ) = x 2 − 2 f(x)=x^2-2 f ( x ) = x 2 − 2 I = ( 0 , + ∞ ) I=(0,+\infty) I = ( 0 , + ∞ ) r = 2 r=\sqrt2 r = 2 N f ( x ) = ( x + 2 / x ) / 2 N_f(x)=(x+2/x)/2 N f ( x ) = ( x + 2/ x ) /2 f ′ ′ = 2 f''=2 f ′′ = 2 補題 4.2 は
N f ( x ) − 2 = ( x − 2 ) 2 2 x N_f(x)-\sqrt2=\frac{(x-\sqrt2)^2}{2x} N f ( x ) − 2 = 2 x ( x − 2 ) 2 となる。x 0 = 1 x_0=1 x 0 = 1
x 1 = 3 2 , x 2 = 17 12 , x 3 = 577 408 , x 4 = 665857 470832 x_1=\frac32,\quad x_2=\frac{17}{12},\quad x_3=\frac{577}{408},\quad x_4=\frac{665857}{470832} x 1 = 2 3 , x 2 = 12 17 , x 3 = 408 577 , x 4 = 470832 665857 であり、誤差はe 1 ≈ 8.58 × 10 − 2 e_1\approx8.58\times10^{-2} e 1 ≈ 8.58 × 1 0 − 2 e 2 ≈ 2.45 × 10 − 3 e_2\approx2.45\times10^{-3} e 2 ≈ 2.45 × 1 0 − 3 e 3 ≈ 2.12 × 10 − 6 e_3\approx2.12\times10^{-6} e 3 ≈ 2.12 × 1 0 − 6 e 4 ≈ 1.59 × 10 − 12 e_4\approx1.59\times10^{-12} e 4 ≈ 1.59 × 1 0 − 12 x k x_k x k 2 \sqrt2 2 k ≥ 1 k\ge1 k ≥ 1 x k > 2 x_k>\sqrt2 x k > 2 e k + 1 / e k 2 = 1 / ( 2 x k ) e_{k+1}/e_k^2=1/(2x_k) e k + 1 / e k 2 = 1/ ( 2 x k ) k = 1 , 2 , 3 k=1,2,3 k = 1 , 2 , 3 1 / 3 1/3 1/3 6 / 17 6/17 6/17 204 / 577 204/577 204/577 1 / ( 2 2 ) ≈ 0.353553 1/(2\sqrt2)\approx0.353553 1/ ( 2 2 ) ≈ 0.353553 1 / ( 2 2 ) = ∣ f ′ ′ ( r ) / ( 2 f ′ ( r ) ) ∣ 1/(2\sqrt2)=\lvert f''(r)/(2f'(r))\rvert 1/ ( 2 2 ) = ∣ f ′′ ( r ) / ( 2 f ′ ( r ))∣ 定理 4.3 (2) の漸近定数である。d k : = − log 10 e k d_k:=-\log_{10}e_k d k := − log 10 e k k = 1 , 2 , 3 , 4 k=1,2,3,4 k = 1 , 2 , 3 , 4 1.07 1.07 1.07 2.61 2.61 2.61 5.67 5.67 5.67 11.80 11.80 11.80 命題 1.3 (2) によりd k + 1 − 2 d k → log 10 ( 2 2 ) ≈ 0.4515 d_{k+1}-2d_k\to\log_{10}(2\sqrt2)\approx0.4515 d k + 1 − 2 d k → log 10 ( 2 2 ) ≈ 0.4515 d 4 − 2 d 3 ≈ 0.4515 d_4-2d_3\approx0.4515 d 4 − 2 d 3 ≈ 0.4515 [ 1 , 2 ] [1,2] [ 1 , 2 ] 定理 2.3 (3) の上界2 − ( n + 1 ) 2^{-(n+1)} 2 − ( n + 1 ) e 4 e_4 e 4 n n n 39 39 39 2 − 40 ≈ 9.09 × 10 − 13 2^{-40}\approx9.09\times10^{-13} 2 − 40 ≈ 9.09 × 1 0 − 13 2 − 39 ≈ 1.82 × 10 − 12 2^{-39}\approx1.82\times10^{-12} 2 − 39 ≈ 1.82 × 1 0 − 12 m 39 m_{39} m 39 m 0 , … , m 38 m_0,\dots,m_{38} m 0 , … , m 38 f f f x 4 x_4 x 4 x 0 , … , x 3 x_0,\dots,x_3 x 0 , … , x 3 f f f f ′ f' f ′
例 4.5.
f ( x ) = x 3 − 2 x + 2 f(x)=x^3-2x+2 f ( x ) = x 3 − 2 x + 2 f ′ ( x ) = 3 x 2 − 2 f'(x)=3x^2-2 f ′ ( x ) = 3 x 2 − 2 f ( 0 ) = 2 f(0)=2 f ( 0 ) = 2 f ′ ( 0 ) = − 2 f'(0)=-2 f ′ ( 0 ) = − 2 N f ( 0 ) = 1 N_f(0)=1 N f ( 0 ) = 1 f ( 1 ) = 1 f(1)=1 f ( 1 ) = 1 f ′ ( 1 ) = 1 f'(1)=1 f ′ ( 1 ) = 1 N f ( 1 ) = 0 N_f(1)=0 N f ( 1 ) = 0 x 0 = 0 x_0=0 x 0 = 0 0 , 1 , 0 , 1 , … 0,1,0,1,\dots 0 , 1 , 0 , 1 , … f f f s : = 2 / 3 s:=\sqrt{2/3} s := 2/3 f f f [ − s , s ] [-s,s] [ − s , s ] [ s , + ∞ ) [s,+\infty) [ s , + ∞ ) [ − s , + ∞ ) [-s,+\infty) [ − s , + ∞ ) f ≥ f ( s ) = 2 − 4 3 s > 2 3 f\ge f(s)=2-\frac43s>\frac23 f ≥ f ( s ) = 2 − 3 4 s > 3 2 ( − ∞ , − s ] (-\infty,-s] ( − ∞ , − s ] f f f f ( − 2 ) = − 2 < 0 < f ( − s ) f(-2)=-2<0<f(-s) f ( − 2 ) = − 2 < 0 < f ( − s ) f f f ( − 2 , − s ) (-2,-s) ( − 2 , − s ) f ( x ) = arctan x f(x)=\arctan x f ( x ) = arctan x r = 0 r=0 r = 0 f ′ ( x ) = 1 / ( 1 + x 2 ) ≠ 0 f'(x)=1/(1+x^2)\ne0 f ′ ( x ) = 1/ ( 1 + x 2 ) = 0 N f ( x ) = x − ( 1 + x 2 ) arctan x N_f(x)=x-(1+x^2)\arctan x N f ( x ) = x − ( 1 + x 2 ) arctan x 0 < 1 < π / 3 0<1<\pi/3 0 < 1 < π /3 cos \cos cos [ 0 , π ] [0,\pi] [ 0 , π ] cos 1 > 1 / 2 \cos1>1/2 cos 1 > 1/2 tan 1 < 2 \tan1<2 tan 1 < 2 arctan 2 > 1 \arctan2>1 arctan 2 > 1 x ≥ 2 x\ge2 x ≥ 2 ( 1 + x 2 ) arctan x > 1 + x 2 (1+x^2)\arctan x>1+x^2 ( 1 + x 2 ) arctan x > 1 + x 2 N f ( x ) < − ( x 2 − x + 1 ) ≤ − ( x + 1 ) N_f(x)<-(x^2-x+1)\le-(x+1) N f ( x ) < − ( x 2 − x + 1 ) ≤ − ( x + 1 ) N f N_f N f ∣ x ∣ ≥ 2 \lvert x\rvert\ge2 ∣ x ∣ ≥ 2 ∣ N f ( x ) ∣ > ∣ x ∣ + 1 \lvert N_f(x)\rvert>\lvert x\rvert+1 ∣ N f ( x )∣ > ∣ x ∣ + 1 ∣ x 0 ∣ ≥ 2 \lvert x_0\rvert\ge2 ∣ x 0 ∣ ≥ 2 ∣ x 1 ∣ > ∣ x 0 ∣ + 1 \lvert x_1\rvert>\lvert x_0\rvert+1 ∣ x 1 ∣ > ∣ x 0 ∣ + 1 k ≥ 1 k\ge1 k ≥ 1 ∣ x k ∣ > ∣ x 0 ∣ + k \lvert x_k\rvert>\lvert x_0\rvert+k ∣ x k ∣ > ∣ x 0 ∣ + k ∣ x k ∣ > 2 \lvert x_k\rvert>2 ∣ x k ∣ > 2 ∣ x k + 1 ∣ > ∣ x k ∣ + 1 > ∣ x 0 ∣ + k + 1 \lvert x_{k+1}\rvert>\lvert x_k\rvert+1>\lvert x_0\rvert+k+1 ∣ x k + 1 ∣ > ∣ x k ∣ + 1 > ∣ x 0 ∣ + k + 1 k k k k ≥ 1 k\ge1 k ≥ 1 ∣ x k ∣ > ∣ x 0 ∣ + k \lvert x_k\rvert>\lvert x_0\rvert+k ∣ x k ∣ > ∣ x 0 ∣ + k 命題 4.6. I ⊂ R I\subset\R I ⊂ R m ≥ 2 m\ge2 m ≥ 2 h : I → R h\colon I\to\R h : I → R C 1 C^1 C 1 r ∈ I r\in I r ∈ I h ( r ) ≠ 0 h(r)\ne0 h ( r ) = 0 f ( x ) : = ( x − r ) m h ( x ) f(x):=(x-r)^mh(x) f ( x ) := ( x − r ) m h ( x ) δ > 0 \delta>0 δ > 0 J : = [ r − δ , r + δ ] ⊂ I J:=[r-\delta,r+\delta]\subset I J := [ r − δ , r + δ ] ⊂ I x 0 ∈ J ∖ { r } x_0\in J\setminus\{r\} x 0 ∈ J ∖ { r } ( x k ) (x_k) ( x k ) k k k x k ∈ J ∖ { r } x_k\in J\setminus\{r\} x k ∈ J ∖ { r } ( x k ) (x_k) ( x k ) r r r ( m − 1 ) / m (m-1)/m ( m − 1 ) / m
証明. f ′ ( x ) = ( x − r ) m − 1 D ( x ) f'(x)=(x-r)^{m-1}\,D(x) f ′ ( x ) = ( x − r ) m − 1 D ( x ) D ( x ) : = m h ( x ) + ( x − r ) h ′ ( x ) D(x):=mh(x)+(x-r)h'(x) D ( x ) := mh ( x ) + ( x − r ) h ′ ( x ) D ( r ) = m h ( r ) ≠ 0 D(r)=mh(r)\ne0 D ( r ) = mh ( r ) = 0 D D D D ≠ 0 D\ne0 D = 0 r r r
Φ ( x ) : = ( m − 1 ) h ( x ) + ( x − r ) h ′ ( x ) D ( x ) \Phi(x):=\frac{(m-1)h(x)+(x-r)h'(x)}{D(x)} Φ ( x ) := D ( x ) ( m − 1 ) h ( x ) + ( x − r ) h ′ ( x ) は連続であってΦ ( r ) = ( m − 1 ) / m \Phi(r)=(m-1)/m Φ ( r ) = ( m − 1 ) / m δ > 0 \delta>0 δ > 0 J ⊂ I J\subset I J ⊂ I J J J D ≠ 0 D\ne0 D = 0 ∣ Φ ( x ) − ( m − 1 ) / m ∣ ≤ 1 / ( 2 m ) \lvert\Phi(x)-(m-1)/m\rvert\le1/(2m) ∣ Φ ( x ) − ( m − 1 ) / m ∣ ≤ 1/ ( 2 m ) x ∈ J ∖ { r } x\in J\setminus\{r\} x ∈ J ∖ { r } f ′ ( x ) ≠ 0 f'(x)\ne0 f ′ ( x ) = 0
N f ( x ) − r = ( x − r ) − ( x − r ) h ( x ) D ( x ) = ( x − r ) Φ ( x ) N_f(x)-r=(x-r)-\frac{(x-r)h(x)}{D(x)}=(x-r)\Phi(x) N f ( x ) − r = ( x − r ) − D ( x ) ( x − r ) h ( x ) = ( x − r ) Φ ( x ) である。m ≥ 2 m\ge2 m ≥ 2 Φ ( x ) ∈ [ ( 2 m − 3 ) / ( 2 m ) , ( 2 m − 1 ) / ( 2 m ) ] ⊂ ( 0 , 1 ) \Phi(x)\in[(2m-3)/(2m),(2m-1)/(2m)]\subset(0,1) Φ ( x ) ∈ [( 2 m − 3 ) / ( 2 m ) , ( 2 m − 1 ) / ( 2 m )] ⊂ ( 0 , 1 ) N f ( x ) ∈ J ∖ { r } N_f(x)\in J\setminus\{r\} N f ( x ) ∈ J ∖ { r } k k k x k ∈ J ∖ { r } x_k\in J\setminus\{r\} x k ∈ J ∖ { r } ∣ e k + 1 ∣ ≤ 2 m − 1 2 m ∣ e k ∣ \lvert e_{k+1}\rvert\le\frac{2m-1}{2m}\lvert e_k\rvert ∣ e k + 1 ∣ ≤ 2 m 2 m − 1 ∣ e k ∣ x k → r x_k\to r x k → r e k + 1 / e k = Φ ( x k ) → ( m − 1 ) / m ∈ ( 0 , 1 ) e_{k+1}/e_k=\Phi(x_k)\to(m-1)/m\in(0,1) e k + 1 / e k = Φ ( x k ) → ( m − 1 ) / m ∈ ( 0 , 1 ) ▨
5 割線法 定義 5.1. I ⊂ R I\subset\R I ⊂ R f : I → R f\colon I\to\R f : I → R x , y ∈ I x,y\in I x , y ∈ I
f [ x , y ] : = f ( y ) − f ( x ) y − x f[x,y]:=\frac{f(y)-f(x)}{y-x} f [ x , y ] := y − x f ( y ) − f ( x ) をf f f x , y x,y x , y 差商 (divided difference )
定義 5.2. I ⊂ R I\subset\R I ⊂ R f : I → R f\colon I\to\R f : I → R x 0 , x 1 ∈ I x_0,x_1\in I x 0 , x 1 ∈ I k ≥ 1 k\ge1 k ≥ 1 x k − 1 , x k ∈ I x_{k-1},x_k\in I x k − 1 , x k ∈ I
f ( x k ) = 0 f(x_k)=0 f ( x k ) = 0 x k x_k x k f ( x k ) ≠ 0 f(x_k)\ne0 f ( x k ) = 0 f [ x k − 1 , x k ] ≠ 0 f[x_{k-1},x_k]\ne0 f [ x k − 1 , x k ] = 0 x k + 1 : = x k − f ( x k ) f [ x k − 1 , x k ] x_{k+1}:=x_k-\frac{f(x_k)}{f[x_{k-1},x_k]} x k + 1 := x k − f [ x k − 1 , x k ] f ( x k ) x k + 1 x_{k+1} x k + 1 ( x k − 1 , f ( x k − 1 ) ) (x_{k-1},f(x_{k-1})) ( x k − 1 , f ( x k − 1 )) ( x k , f ( x k ) ) (x_k,f(x_k)) ( x k , f ( x k )) f ( x k ) ≠ 0 f(x_k)\ne0 f ( x k ) = 0 x k + 1 ≠ x k x_{k+1}\ne x_k x k + 1 = x k f ( x k ) ≠ 0 f(x_k)\ne0 f ( x k ) = 0 f [ x k − 1 , x k ] = 0 f[x_{k-1},x_k]=0 f [ x k − 1 , x k ] = 0 x k + 1 x_{k+1} x k + 1 この反復を 割線法 (secant method )x k + 1 x_{k+1} x k + 1 f f f x 0 , … , x k x_0,\dots,x_k x 0 , … , x k k + 1 k+1 k + 1 f ′ f' f ′
補題 5.3. I ⊂ R I\subset\R I ⊂ R f : I → R f\colon I\to\R f : I → R C 2 C^2 C 2 r ∈ I r\in I r ∈ I f ( r ) = 0 f(r)=0 f ( r ) = 0 ψ : I → R \psi\colon I\to\R ψ : I → R x ≠ r x\ne r x = r ψ ( x ) : = f [ x , r ] \psi(x):=f[x,r] ψ ( x ) := f [ x , r ] ψ ( r ) : = f ′ ( r ) \psi(r):=f'(r) ψ ( r ) := f ′ ( r )
ψ \psi ψ I I I x ∈ I x\in I x ∈ I x x x r r r c c c ψ ′ ( x ) = f ′ ′ ( c ) / 2 \psi'(x)=f''(c)/2 ψ ′ ( x ) = f ′′ ( c ) /2 ψ ′ ( r ) = f ′ ′ ( r ) / 2 \psi'(r)=f''(r)/2 ψ ′ ( r ) = f ′′ ( r ) /2 ψ ′ \psi' ψ ′ r r r 相異なるx , y ∈ I x,y\in I x , y ∈ I f ( x ) ≠ f ( y ) f(x)\ne f(y) f ( x ) = f ( y ) s : = y − f ( y ) / f [ x , y ] s:=y-f(y)/f[x,y] s := y − f ( y ) / f [ x , y ] s − r = ( x − r ) ( y − r ) ψ [ x , y ] f [ x , y ] s-r=(x-r)(y-r)\frac{\psi[x,y]}{f[x,y]} s − r = ( x − r ) ( y − r ) f [ x , y ] ψ [ x , y ]
証明. (1) を示す。x ≠ r x\ne r x = r x x x ψ ( t ) = f ( t ) / ( t − r ) \psi(t)=f(t)/(t-r) ψ ( t ) = f ( t ) / ( t − r ) ψ \psi ψ x x x ψ ′ ( x ) = ( f ′ ( x ) ( x − r ) − f ( x ) ) / ( x − r ) 2 \psi'(x)=\bigl(f'(x)(x-r)-f(x)\bigr)/(x-r)^2 ψ ′ ( x ) = ( f ′ ( x ) ( x − r ) − f ( x ) ) / ( x − r ) 2 §D1.16 定理 2.1 をn = 2 n=2 n = 2 x x x r r r x x x r r r c c c 0 = f ( x ) + f ′ ( x ) ( r − x ) + f ′ ′ ( c ) ( r − x ) 2 / 2 0=f(x)+f'(x)(r-x)+f''(c)(r-x)^2/2 0 = f ( x ) + f ′ ( x ) ( r − x ) + f ′′ ( c ) ( r − x ) 2 /2 f ′ ( x ) ( x − r ) − f ( x ) = f ′ ′ ( c ) ( x − r ) 2 / 2 f'(x)(x-r)-f(x)=f''(c)(x-r)^2/2 f ′ ( x ) ( x − r ) − f ( x ) = f ′′ ( c ) ( x − r ) 2 /2 ψ ′ ( x ) = f ′ ′ ( c ) / 2 \psi'(x)=f''(c)/2 ψ ′ ( x ) = f ′′ ( c ) /2 h ≠ 0 h\ne0 h = 0 r + h ∈ I r+h\in I r + h ∈ I §D1.16 定理 2.1 をn = 2 n=2 n = 2 r r r r + h r+h r + h r r r r + h r+h r + h c h c_h c h f ( r + h ) = f ′ ( r ) h + f ′ ′ ( c h ) h 2 / 2 f(r+h)=f'(r)h+f''(c_h)h^2/2 f ( r + h ) = f ′ ( r ) h + f ′′ ( c h ) h 2 /2
ψ ( r + h ) − ψ ( r ) h = f ( r + h ) / h − f ′ ( r ) h = f ′ ′ ( c h ) 2 \frac{\psi(r+h)-\psi(r)}{h}=\frac{f(r+h)/h-f'(r)}{h}=\frac{f''(c_h)}{2} h ψ ( r + h ) − ψ ( r ) = h f ( r + h ) / h − f ′ ( r ) = 2 f ′′ ( c h ) である。h → 0 h\to0 h → 0 c h → r c_h\to r c h → r f ′ ′ f'' f ′′ ψ ′ ( r ) = f ′ ′ ( r ) / 2 \psi'(r)=f''(r)/2 ψ ′ ( r ) = f ′′ ( r ) /2 c c c ∣ c − r ∣ ≤ ∣ x − r ∣ \lvert c-r\rvert\le\lvert x-r\rvert ∣ c − r ∣ ≤ ∣ x − r ∣ x → r x\to r x → r ψ ′ ( x ) = f ′ ′ ( c ) / 2 → f ′ ′ ( r ) / 2 \psi'(x)=f''(c)/2\to f''(r)/2 ψ ′ ( x ) = f ′′ ( c ) /2 → f ′′ ( r ) /2
(2) を示す。すべてのt ∈ I t\in I t ∈ I f ( t ) = ( t − r ) ψ ( t ) f(t)=(t-r)\psi(t) f ( t ) = ( t − r ) ψ ( t )
f [ x , y ] − ψ ( y ) = ( y − r ) ψ ( y ) − ( x − r ) ψ ( x ) − ( ( y − r ) − ( x − r ) ) ψ ( y ) y − x = ( x − r ) ψ [ x , y ] f[x,y]-\psi(y)=\frac{(y-r)\psi(y)-(x-r)\psi(x)-\bigl((y-r)-(x-r)\bigr)\psi(y)}{y-x}=(x-r)\psi[x,y] f [ x , y ] − ψ ( y ) = y − x ( y − r ) ψ ( y ) − ( x − r ) ψ ( x ) − ( ( y − r ) − ( x − r ) ) ψ ( y ) = ( x − r ) ψ [ x , y ] であり、
s − r = ( y − r ) − ( y − r ) ψ ( y ) f [ x , y ] = ( y − r ) f [ x , y ] − ψ ( y ) f [ x , y ] = ( x − r ) ( y − r ) ψ [ x , y ] f [ x , y ] s-r=(y-r)-\frac{(y-r)\psi(y)}{f[x,y]}=(y-r)\frac{f[x,y]-\psi(y)}{f[x,y]}=(x-r)(y-r)\frac{\psi[x,y]}{f[x,y]} s − r = ( y − r ) − f [ x , y ] ( y − r ) ψ ( y ) = ( y − r ) f [ x , y ] f [ x , y ] − ψ ( y ) = ( x − r ) ( y − r ) f [ x , y ] ψ [ x , y ] である。▨
定理 5.4. I ⊂ R I\subset\R I ⊂ R f : I → R f\colon I\to\R f : I → R C 2 C^2 C 2 r ∈ I r\in I r ∈ I f ( r ) = 0 f(r)=0 f ( r ) = 0 f ′ ( r ) ≠ 0 f'(r)\ne0 f ′ ( r ) = 0 C : = ( ∣ f ′ ′ ( r ) ∣ + 1 ) / ∣ f ′ ( r ) ∣ C:=(\lvert f''(r)\rvert+1)/\lvert f'(r)\rvert C := (∣ f ′′ ( r )∣ + 1 ) / ∣ f ′ ( r )∣ δ > 0 \delta>0 δ > 0 J : = [ r − δ , r + δ ] ⊂ I J:=[r-\delta,r+\delta]\subset I J := [ r − δ , r + δ ] ⊂ I x 0 , x 1 ∈ J x_0,x_1\in J x 0 , x 1 ∈ J e k : = x k − r e_k:=x_k-r e k := x k − r
定義 5.2 (3) の場合は起こらず、すべての項はJ J J k ≥ 1 k\ge1 k ≥ 1 k k k x k = r x_k=r x k = r x k + 1 x_{k+1} x k + 1 k ≥ 1 k\ge1 k ≥ 1 ∣ e k + 1 ∣ ≤ C ∣ e k ∣ ∣ e k − 1 ∣ \lvert e_{k+1}\rvert\le C\lvert e_k\rvert\lvert e_{k-1}\rvert ∣ e k + 1 ∣ ≤ C ∣ e k ∣ ∣ e k − 1 ∣ ∣ e k + 1 ∣ ≤ ∣ e k ∣ / 2 \lvert e_{k+1}\rvert\le\lvert e_k\rvert/2 ∣ e k + 1 ∣ ≤ ∣ e k ∣ /2 割線法がどの段でも停止しないならば、すべてのk k k x k ≠ r x_k\ne r x k = r ( x k ) (x_k) ( x k ) r r r
証明. f ′ f' f ′ f ′ ′ f'' f ′′ r r r δ > 0 \delta>0 δ > 0 J ⊂ I J\subset I J ⊂ I C δ ≤ 1 / 2 C\delta\le1/2 C δ ≤ 1/2 t ∈ J t\in J t ∈ J ∣ f ′ ( t ) ∣ ≥ ∣ f ′ ( r ) ∣ / 2 \lvert f'(t)\rvert\ge\lvert f'(r)\rvert/2 ∣ f ′ ( t )∣ ≥ ∣ f ′ ( r )∣ /2 ∣ f ′ ′ ( t ) ∣ ≤ ∣ f ′ ′ ( r ) ∣ + 1 \lvert f''(t)\rvert\le\lvert f''(r)\rvert+1 ∣ f ′′ ( t )∣ ≤ ∣ f ′′ ( r )∣ + 1 x , y ∈ J x,y\in J x , y ∈ J §D1.14 定理 3.1 によりf [ x , y ] = f ′ ( α ) f[x,y]=f'(\alpha) f [ x , y ] = f ′ ( α ) α ∈ J \alpha\in J α ∈ J ∣ f [ x , y ] ∣ ≥ ∣ f ′ ( r ) ∣ / 2 > 0 \lvert f[x,y]\rvert\ge\lvert f'(r)\rvert/2>0 ∣ f [ x , y ]∣ ≥ ∣ f ′ ( r )∣ /2 > 0 f ( x ) ≠ f ( y ) f(x)\ne f(y) f ( x ) = f ( y ) y ≠ r y\ne r y = r f ( y ) = f ( y ) − f ( r ) = f ′ ( β ) ( y − r ) ≠ 0 f(y)=f(y)-f(r)=f'(\beta)(y-r)\ne0 f ( y ) = f ( y ) − f ( r ) = f ′ ( β ) ( y − r ) = 0 J J J f ( y ) = 0 f(y)=0 f ( y ) = 0 y = r y=r y = r 補題 5.3 (1) によりψ \psi ψ §D1.14 定理 3.1 によりψ [ x , y ] = ψ ′ ( γ ) \psi[x,y]=\psi'(\gamma) ψ [ x , y ] = ψ ′ ( γ ) γ ∈ J \gamma\in J γ ∈ J ψ ′ ( γ ) = f ′ ′ ( c ) / 2 \psi'(\gamma)=f''(c)/2 ψ ′ ( γ ) = f ′′ ( c ) /2 c c c γ \gamma γ r r r J J J ∣ ψ [ x , y ] ∣ ≤ ( ∣ f ′ ′ ( r ) ∣ + 1 ) / 2 \lvert\psi[x,y]\rvert\le(\lvert f''(r)\rvert+1)/2 ∣ ψ [ x , y ]∣ ≤ (∣ f ′′ ( r )∣ + 1 ) /2 補題 5.3 (2) によりs : = y − f ( y ) / f [ x , y ] s:=y-f(y)/f[x,y] s := y − f ( y ) / f [ x , y ]
∣ s − r ∣ ≤ C ∣ x − r ∣ ∣ y − r ∣ ≤ C δ ∣ y − r ∣ ≤ ∣ y − r ∣ 2 \lvert s-r\rvert\le C\lvert x-r\rvert\lvert y-r\rvert\le C\delta\lvert y-r\rvert\le\frac{\lvert y-r\rvert}{2} ∣ s − r ∣ ≤ C ∣ x − r ∣ ∣ y − r ∣ ≤ C δ ∣ y − r ∣ ≤ 2 ∣ y − r ∣ を満たし、s ∈ J s\in J s ∈ J
k ≥ 1 k\ge1 k ≥ 1 x k − 1 , x k x_{k-1},x_k x k − 1 , x k J J J x k = r x_k=r x k = r f ( x k ) = 0 f(x_k)=0 f ( x k ) = 0 定義 5.2 (1) により停止する。x k ≠ r x_k\ne r x k = r f ( x k ) ≠ 0 f(x_k)\ne0 f ( x k ) = 0 f [ x k − 1 , x k ] ≠ 0 f[x_{k-1},x_k]\ne0 f [ x k − 1 , x k ] = 0 定義 5.2 (2) が適用され、上の評価をx = x k − 1 x=x_{k-1} x = x k − 1 y = x k y=x_k y = x k x k + 1 ∈ J x_{k+1}\in J x k + 1 ∈ J (2) の二つの評価を得る。x k + 1 ≠ x k x_{k+1}\ne x_k x k + 1 = x k (1) と(2) が成り立つ。
(3) を示す。割線法が停止しないならば、(1) によりすべてのk ≥ 1 k\ge1 k ≥ 1 x k ≠ r x_k\ne r x k = r x 0 = r x_0=r x 0 = r 補題 5.3 (2) によりe 2 = 0 e_2=0 e 2 = 0 2 2 2 x 0 ≠ r x_0\ne r x 0 = r (2) により∣ e k ∣ ≤ 2 − ( k − 1 ) ∣ e 1 ∣ → 0 \lvert e_k\rvert\le2^{-(k-1)}\lvert e_1\rvert\to0 ∣ e k ∣ ≤ 2 − ( k − 1 ) ∣ e 1 ∣ → 0 ∣ e k + 1 ∣ / ∣ e k ∣ ≤ C ∣ e k − 1 ∣ → 0 \lvert e_{k+1}\rvert/\lvert e_k\rvert\le C\lvert e_{k-1}\rvert\to0 ∣ e k + 1 ∣ / ∣ e k ∣ ≤ C ∣ e k − 1 ∣ → 0 ▨
補題 5.5. ρ ∈ [ 0 , 1 ) \rho\in[0,1) ρ ∈ [ 0 , 1 ) ( w k ) k ∈ N ≥ 0 (w_k)_{k\in\N} ( w k ) k ∈ N ≥ 0 ( ε k ) k ∈ N ≥ 1 (\varepsilon_k)_{k\in\NN} ( ε k ) k ∈ N ≥ 1 k ∈ N ≥ 1 k\in\NN k ∈ N ≥ 1 ∣ w k ∣ ≤ ρ ∣ w k − 1 ∣ + ε k \lvert w_k\rvert\le\rho\lvert w_{k-1}\rvert+\varepsilon_k ∣ w k ∣ ≤ ρ ∣ w k − 1 ∣ + ε k ε k → 0 \varepsilon_k\to0 ε k → 0 w k → 0 w_k\to0 w k → 0
証明. ε > 0 \varepsilon>0 ε > 0 k > K k>K k > K ε k ≤ ε \varepsilon_k\le\varepsilon ε k ≤ ε K ∈ N ≥ 0 K\in\N K ∈ N ≥ 0 k ≥ K k\ge K k ≥ K
∣ w k ∣ ≤ ρ k − K ∣ w K ∣ + ε ∑ i = 0 k − K − 1 ρ i ≤ ρ k − K ∣ w K ∣ + ε 1 − ρ \lvert w_k\rvert\le\rho^{k-K}\lvert w_K\rvert+\varepsilon\sum_{i=0}^{k-K-1}\rho^i\le\rho^{k-K}\lvert w_K\rvert+\frac{\varepsilon}{1-\rho} ∣ w k ∣ ≤ ρ k − K ∣ w K ∣ + ε i = 0 ∑ k − K − 1 ρ i ≤ ρ k − K ∣ w K ∣ + 1 − ρ ε である。ρ k − K → 0 \rho^{k-K}\to0 ρ k − K → 0 lim sup k → ∞ ∣ w k ∣ ≤ ε / ( 1 − ρ ) \limsup_{k\to\infty}\lvert w_k\rvert\le\varepsilon/(1-\rho) lim sup k → ∞ ∣ w k ∣ ≤ ε / ( 1 − ρ ) ε > 0 \varepsilon>0 ε > 0 w k → 0 w_k\to0 w k → 0 ▨
定理 5.6. 定理 5.4 の仮定に加えてf ′ ′ ( r ) ≠ 0 f''(r)\ne0 f ′′ ( r ) = 0 φ : = ( 1 + 5 ) / 2 \varphi:=(1+\sqrt5)/2 φ := ( 1 + 5 ) /2 A : = ∣ f ′ ′ ( r ) / ( 2 f ′ ( r ) ) ∣ A:=\lvert f''(r)/(2f'(r))\rvert A := ∣ f ′′ ( r ) / ( 2 f ′ ( r ))∣ 定理 5.4 のJ J J x 0 , x 1 x_0,x_1 x 0 , x 1 ( x k ) (x_k) ( x k ) r r r φ \varphi φ A 1 / φ = A φ − 1 A^{1/\varphi}=A^{\varphi-1} A 1/ φ = A φ − 1
証明. 定理 5.4 (3) により、すべてのk k k e k ≠ 0 e_k\ne0 e k = 0 x k → r x_k\to r x k → r k ≥ 1 k\ge1 k ≥ 1 a k : = ∣ e k + 1 ∣ / ( ∣ e k ∣ ∣ e k − 1 ∣ ) a_k:=\lvert e_{k+1}\rvert/(\lvert e_k\rvert\lvert e_{k-1}\rvert) a k := ∣ e k + 1 ∣ / (∣ e k ∣ ∣ e k − 1 ∣) 補題 5.3 (2) によりa k = ∣ ψ [ x k − 1 , x k ] ∣ / ∣ f [ x k − 1 , x k ] ∣ a_k=\lvert\psi[x_{k-1},x_k]\rvert/\lvert f[x_{k-1},x_k]\rvert a k = ∣ ψ [ x k − 1 , x k ]∣ / ∣ f [ x k − 1 , x k ]∣ §D1.14 定理 3.1 によりψ [ x k − 1 , x k ] = ψ ′ ( γ k ) \psi[x_{k-1},x_k]=\psi'(\gamma_k) ψ [ x k − 1 , x k ] = ψ ′ ( γ k ) f [ x k − 1 , x k ] = f ′ ( α k ) f[x_{k-1},x_k]=f'(\alpha_k) f [ x k − 1 , x k ] = f ′ ( α k ) γ k , α k \gamma_k,\alpha_k γ k , α k x k − 1 x_{k-1} x k − 1 x k x_k x k γ k → r \gamma_k\to r γ k → r α k → r \alpha_k\to r α k → r 補題 5.3 (1) によりψ ′ \psi' ψ ′ r r r ψ ′ ( r ) = f ′ ′ ( r ) / 2 \psi'(r)=f''(r)/2 ψ ′ ( r ) = f ′′ ( r ) /2 f ′ f' f ′ a k → ∣ f ′ ′ ( r ) / 2 ∣ / ∣ f ′ ( r ) ∣ = A > 0 a_k\to\lvert f''(r)/2\rvert/\lvert f'(r)\rvert=A>0 a k → ∣ f ′′ ( r ) /2 ∣ / ∣ f ′ ( r )∣ = A > 0 k ∈ N ≥ 0 k\in\N k ∈ N ≥ 0 y k : = ∣ e k + 1 ∣ / ∣ e k ∣ φ > 0 y_k:=\lvert e_{k+1}\rvert/\lvert e_k\rvert^{\varphi}>0 y k := ∣ e k + 1 ∣ / ∣ e k ∣ φ > 0 φ 2 = φ + 1 \varphi^2=\varphi+1 φ 2 = φ + 1 1 − φ = − 1 / φ 1-\varphi=-1/\varphi 1 − φ = − 1/ φ k ≥ 1 k\ge1 k ≥ 1
y k = a k ∣ e k ∣ ∣ e k − 1 ∣ ∣ e k ∣ φ = a k ∣ e k − 1 ∣ ∣ e k ∣ − 1 / φ = a k ( ∣ e k ∣ ∣ e k − 1 ∣ φ ) − 1 / φ = a k y k − 1 − 1 / φ y_k=\frac{a_k\lvert e_k\rvert\lvert e_{k-1}\rvert}{\lvert e_k\rvert^{\varphi}}=a_k\lvert e_{k-1}\rvert\lvert e_k\rvert^{-1/\varphi}=a_k\left(\frac{\lvert e_k\rvert}{\lvert e_{k-1}\rvert^{\varphi}}\right)^{-1/\varphi}=a_ky_{k-1}^{-1/\varphi} y k = ∣ e k ∣ φ a k ∣ e k ∣ ∣ e k − 1 ∣ = a k ∣ e k − 1 ∣ ∣ e k ∣ − 1/ φ = a k ( ∣ e k − 1 ∣ φ ∣ e k ∣ ) − 1/ φ = a k y k − 1 − 1/ φ である。w k : = log y k − ( log A ) / φ w_k:=\log y_k-(\log A)/\varphi w k := log y k − ( log A ) / φ φ 2 − φ − 1 = 0 \varphi^2-\varphi-1=0 φ 2 − φ − 1 = 0 log A − ( log A ) / φ − ( log A ) / φ 2 = 0 \log A-(\log A)/\varphi-(\log A)/\varphi^2=0 log A − ( log A ) / φ − ( log A ) / φ 2 = 0
w k = log a k − log y k − 1 φ − log A φ = ( log a k − log A ) − w k − 1 φ w_k=\log a_k-\frac{\log y_{k-1}}{\varphi}-\frac{\log A}{\varphi}=(\log a_k-\log A)-\frac{w_{k-1}}{\varphi} w k = log a k − φ log y k − 1 − φ log A = ( log a k − log A ) − φ w k − 1 であり、∣ w k ∣ ≤ φ − 1 ∣ w k − 1 ∣ + ∣ log a k − log A ∣ \lvert w_k\rvert\le\varphi^{-1}\lvert w_{k-1}\rvert+\lvert\log a_k-\log A\rvert ∣ w k ∣ ≤ φ − 1 ∣ w k − 1 ∣ + ∣ log a k − log A ∣ φ − 1 < 1 \varphi^{-1}<1 φ − 1 < 1 log \log log ∣ log a k − log A ∣ → 0 \lvert\log a_k-\log A\rvert\to0 ∣ log a k − log A ∣ → 0 補題 5.5 によりw k → 0 w_k\to0 w k → 0 y k → exp ( ( log A ) / φ ) = A 1 / φ ∈ ( 0 , + ∞ ) y_k\to\exp((\log A)/\varphi)=A^{1/\varphi}\in(0,+\infty) y k → exp (( log A ) / φ ) = A 1/ φ ∈ ( 0 , + ∞ ) 1 / φ = φ − 1 1/\varphi=\varphi-1 1/ φ = φ − 1 φ > 1 \varphi>1 φ > 1 定義 1.1 (1) のq = φ q=\varphi q = φ ▨
例 5.7. f ( x ) = x 2 − 2 f(x)=x^2-2 f ( x ) = x 2 − 2 r = 2 r=\sqrt2 r = 2 補題 5.3 のψ \psi ψ ψ ( x ) = x + 2 \psi(x)=x+\sqrt2 ψ ( x ) = x + 2 ψ [ x , y ] = 1 \psi[x,y]=1 ψ [ x , y ] = 1 f [ x , y ] = x + y f[x,y]=x+y f [ x , y ] = x + y 補題 5.3 (2) は
e k + 1 = e k e k − 1 x k − 1 + x k e_{k+1}=\frac{e_ke_{k-1}}{x_{k-1}+x_k} e k + 1 = x k − 1 + x k e k e k − 1 となる。x 0 = 1 x_0=1 x 0 = 1 x 1 = 2 x_1=2 x 1 = 2
x 2 = 4 3 , x 3 = 7 5 , x 4 = 58 41 , x 5 = 816 577 , x 6 = 47321 33461 , x 7 = 77227930 54608393 x_2=\frac43,\quad x_3=\frac75,\quad x_4=\frac{58}{41},\quad x_5=\frac{816}{577},\quad x_6=\frac{47321}{33461},\quad x_7=\frac{77227930}{54608393} x 2 = 3 4 , x 3 = 5 7 , x 4 = 41 58 , x 5 = 577 816 , x 6 = 33461 47321 , x 7 = 54608393 77227930 であり、e 5 ≈ − 2.12 × 10 − 6 e_5\approx-2.12\times10^{-6} e 5 ≈ − 2.12 × 1 0 − 6 e 6 ≈ − 3.16 × 10 − 10 e_6\approx-3.16\times10^{-10} e 6 ≈ − 3.16 × 1 0 − 10 e 7 ≈ 2.37 × 10 − 16 e_7\approx2.37\times10^{-16} e 7 ≈ 2.37 × 1 0 − 16 A = 1 / ( 2 2 ) A=1/(2\sqrt2) A = 1/ ( 2 2 ) 定理 5.6 の漸近定数はA 1 / φ ≈ 0.5259 A^{1/\varphi}\approx0.5259 A 1/ φ ≈ 0.5259 y k = ∣ e k + 1 ∣ / ∣ e k ∣ φ y_k=\lvert e_{k+1}\rvert/\lvert e_k\rvert^{\varphi} y k = ∣ e k + 1 ∣ / ∣ e k ∣ φ k = 2 , … , 6 k=2,\dots,6 k = 2 , … , 6 0.831 0.831 0.831 0.410 0.410 0.410 0.616 0.616 0.616 0.477 0.477 0.477 0.559 0.559 0.559 f f f x 6 x_6 x 6 6 6 6 3.16 × 10 − 10 3.16\times10^{-10} 3.16 × 1 0 − 10 x 7 x_7 x 7 7 7 7 2.37 × 10 − 16 2.37\times10^{-16} 2.37 × 1 0 − 16 例 4.4 の Newton 法では、f f f f ′ f' f ′ 6 6 6 x 3 x_3 x 3 2.12 × 10 − 6 2.12\times10^{-6} 2.12 × 1 0 − 6 8 8 8 x 4 x_4 x 4 1.59 × 10 − 12 1.59\times10^{-12} 1.59 × 1 0 − 12
6 停止判定 定義 6.1. f : I → R f\colon I\to\R f : I → R x 0 , x 1 , … x_0,x_1,\dots x 0 , x 1 , … [ a k , b k ] [a_k,b_k] [ a k , b k ] τ f ≥ 0 \tau_f\ge0 τ f ≥ 0 τ a b s ≥ 0 \tau_{\mathrm{abs}}\ge0 τ abs ≥ 0 τ r e l ≥ 0 \tau_{\mathrm{rel}}\ge0 τ rel ≥ 0 τ w > 0 \tau_w>0 τ w > 0 k max ∈ N ≥ 1 k_{\max}\in\NN k m a x ∈ N ≥ 1
∣ f ( x k ) ∣ ≤ τ f \lvert f(x_k)\rvert\le\tau_f ∣ f ( x k )∣ ≤ τ f 残差判定 (residual test )k ≥ 1 k\ge1 k ≥ 1 ∣ x k − x k − 1 ∣ ≤ τ a b s + τ r e l ∣ x k ∣ \lvert x_k-x_{k-1}\rvert\le\tau_{\mathrm{abs}}+\tau_{\mathrm{rel}}\lvert x_k\rvert ∣ x k − x k − 1 ∣ ≤ τ abs + τ rel ∣ x k ∣ 反復差判定 (step test )τ a b s \tau_{\mathrm{abs}} τ abs 絶対許容誤差 (absolute tolerance )τ r e l \tau_{\mathrm{rel}} τ rel 相対許容誤差 (relative tolerance )b k − a k ≤ τ w b_k-a_k\le\tau_w b k − a k ≤ τ w 区間幅判定 (interval width test )k = k max k=k_{\max} k = k m a x 反復回数の上限 (iteration limit ) 反復は、選んだ判定が初めて成り立つk k k x k x_k x k f f f ε ≥ 0 \varepsilon\ge0 ε ≥ 0 x k x_k x k ∣ x k − r ∣ ≤ ε \lvert x_k-r\rvert\le\varepsilon ∣ x k − r ∣ ≤ ε f f f r r r 誤差を保証 (error guarantee )ε \varepsilon ε ε \varepsilon ε
命題 6.2. 定義 6.1 の記号を用いる。
(H) を「f f f [ a k , b k ] [a_k,b_k] [ a k , b k ] f ( a k ) f ( b k ) < 0 f(a_k)f(b_k)<0 f ( a k ) f ( b k ) < 0 x k ∈ [ a k , b k ] x_k\in[a_k,b_k] x k ∈ [ a k , b k ] τ w \tau_w τ w x k = ( a k + b k ) / 2 x_k=(a_k+b_k)/2 x k = ( a k + b k ) /2 τ w / 2 \tau_w/2 τ w /2
(H) を「I I I x ∈ I x\in I x ∈ I λ ( x ) ≠ 0 \lambda(x)\ne0 λ ( x ) = 0 λ : I → R \lambda\colon I\to\R λ : I → R g ( x ) : = x − λ ( x ) f ( x ) g(x):=x-\lambda(x)f(x) g ( x ) := x − λ ( x ) f ( x ) g ( I ) ⊂ I g(I)\subset I g ( I ) ⊂ I q ∈ [ 0 , 1 ) q\in[0,1) q ∈ [ 0 , 1 ) ∣ g ( x ) − g ( y ) ∣ ≤ q ∣ x − y ∣ \lvert g(x)-g(y)\rvert\le q\lvert x-y\rvert ∣ g ( x ) − g ( y )∣ ≤ q ∣ x − y ∣ x , y ∈ I x,y\in I x , y ∈ I ( x k ) (x_k) ( x k ) x 0 ∈ I x_0\in I x 0 ∈ I g g g q ( τ a b s + τ r e l ∣ x k ∣ ) / ( 1 − q ) q(\tau_{\mathrm{abs}}+\tau_{\mathrm{rel}}\lvert x_k\rvert)/(1-q) q ( τ abs + τ rel ∣ x k ∣) / ( 1 − q )
(H) を「a < b a<b a < b f f f [ a , b ] [a,b] [ a , b ] ( a , b ) (a,b) ( a , b ) f ( a ) f ( b ) < 0 f(a)f(b)<0 f ( a ) f ( b ) < 0 m > 0 m>0 m > 0 t ∈ ( a , b ) t\in(a,b) t ∈ ( a , b ) ∣ f ′ ( t ) ∣ ≥ m \lvert f'(t)\rvert\ge m ∣ f ′ ( t )∣ ≥ m x k ∈ [ a , b ] x_k\in[a,b] x k ∈ [ a , b ] τ f / m \tau_f/m τ f / m
証明. (1) を示す。§D1.12 定理 1.1 をf f f − f -f − f f f f r ∈ ( a k , b k ) r\in(a_k,b_k) r ∈ ( a k , b k ) x k , r ∈ [ a k , b k ] x_k,r\in[a_k,b_k] x k , r ∈ [ a k , b k ] ∣ x k − r ∣ ≤ b k − a k ≤ τ w \lvert x_k-r\rvert\le b_k-a_k\le\tau_w ∣ x k − r ∣ ≤ b k − a k ≤ τ w x k x_k x k ∣ x k − r ∣ ≤ ( b k − a k ) / 2 ≤ τ w / 2 \lvert x_k-r\rvert\le(b_k-a_k)/2\le\tau_w/2 ∣ x k − r ∣ ≤ ( b k − a k ) /2 ≤ τ w /2
(2) を示す。定理 3.3 (1) によりg g g I I I x ∗ x^* x ∗ ∣ x k − x ∗ ∣ ≤ q ∣ x k − x k − 1 ∣ / ( 1 − q ) ≤ q ( τ a b s + τ r e l ∣ x k ∣ ) / ( 1 − q ) \lvert x_k-x^*\rvert\le q\lvert x_k-x_{k-1}\rvert/(1-q)\le q(\tau_{\mathrm{abs}}+\tau_{\mathrm{rel}}\lvert x_k\rvert)/(1-q) ∣ x k − x ∗ ∣ ≤ q ∣ x k − x k − 1 ∣ / ( 1 − q ) ≤ q ( τ abs + τ rel ∣ x k ∣) / ( 1 − q ) 定義 3.1 によりx ∗ x^* x ∗ f f f
(3) を示す。§D1.12 定理 1.1 をf f f − f -f − f f f f r ∈ ( a , b ) r\in(a,b) r ∈ ( a , b ) x k x_k x k r r r ( a , b ) (a,b) ( a , b ) §E20.2 命題 6.1 を区間[ a , b ] [a,b] [ a , b ] ∣ x k − r ∣ ≤ ∣ f ( x k ) ∣ / m ≤ τ f / m \lvert x_k-r\rvert\le\lvert f(x_k)\rvert/m\le\tau_f/m ∣ x k − r ∣ ≤ ∣ f ( x k )∣ / m ≤ τ f / m ▨
命題 6.3. r ∈ R r\in\R r ∈ R ( x k ) k ∈ N ≥ 0 (x_k)_{k\in\N} ( x k ) k ∈ N ≥ 0 r r r k k k x k ≠ r x_k\ne r x k = r e k : = x k − r e_k:=x_k-r e k := x k − r
c ∈ R c\in\R c ∈ R e k + 1 / e k → c e_{k+1}/e_k\to c e k + 1 / e k → c ∣ x k + 1 − x k ∣ / ∣ e k ∣ → ∣ 1 − c ∣ \lvert x_{k+1}-x_k\rvert/\lvert e_k\rvert\to\lvert1-c\rvert ∣ x k + 1 − x k ∣ / ∣ e k ∣ → ∣ 1 − c ∣ ( x k ) (x_k) ( x k ) r r r ∣ x k + 1 − x k ∣ / ∣ e k ∣ → 1 \lvert x_{k+1}-x_k\rvert/\lvert e_k\rvert\to1 ∣ x k + 1 − x k ∣ / ∣ e k ∣ → 1 証明. x k + 1 − x k = e k + 1 − e k x_{k+1}-x_k=e_{k+1}-e_k x k + 1 − x k = e k + 1 − e k ∣ x k + 1 − x k ∣ / ∣ e k ∣ = ∣ e k + 1 / e k − 1 ∣ → ∣ c − 1 ∣ \lvert x_{k+1}-x_k\rvert/\lvert e_k\rvert=\lvert e_{k+1}/e_k-1\rvert\to\lvert c-1\rvert ∣ x k + 1 − x k ∣ / ∣ e k ∣ = ∣ e k + 1 / e k − 1 ∣ → ∣ c − 1 ∣ (1) が成り立つ。超線形収束はe k + 1 / e k → 0 e_{k+1}/e_k\to0 e k + 1 / e k → 0 (2) はc = 0 c=0 c = 0 ▨
例 6.4.
0 < q < 1 0<q<1 0 < q < 1 g ( x ) = q x g(x)=qx g ( x ) = q x x 0 ≠ 0 x_0\ne0 x 0 = 0 x ∗ = 0 x^*=0 x ∗ = 0 e k = q k x 0 e_k=q^kx_0 e k = q k x 0 x k − x k − 1 = − ( 1 − q ) q k − 1 x 0 x_k-x_{k-1}=-(1-q)q^{k-1}x_0 x k − x k − 1 = − ( 1 − q ) q k − 1 x 0 ∣ e k ∣ = q ∣ x k − x k − 1 ∣ / ( 1 − q ) \lvert e_k\rvert=q\lvert x_k-x_{k-1}\rvert/(1-q) ∣ e k ∣ = q ∣ x k − x k − 1 ∣ / ( 1 − q ) 命題 6.2 (2) の評価は等号で成り立つ。例 3.6 のg − ( x ) = x − x 3 g_-(x)=x-x^3 g − ( x ) = x − x 3 x 0 ∈ ( 0 , 1 ) x_0\in(0,1) x 0 ∈ ( 0 , 1 ) e k + 1 / e k = 1 − x k 2 → 1 e_{k+1}/e_k=1-x_k^2\to1 e k + 1 / e k = 1 − x k 2 → 1 命題 6.3 (1) により∣ x k − x k − 1 ∣ / ∣ e k ∣ = ( ∣ x k − x k − 1 ∣ / ∣ e k − 1 ∣ ) ( ∣ e k − 1 ∣ / ∣ e k ∣ ) → 0 ⋅ 1 = 0 \lvert x_k-x_{k-1}\rvert/\lvert e_k\rvert=(\lvert x_k-x_{k-1}\rvert/\lvert e_{k-1}\rvert)(\lvert e_{k-1}\rvert/\lvert e_k\rvert)\to0\cdot1=0 ∣ x k − x k − 1 ∣ / ∣ e k ∣ = (∣ x k − x k − 1 ∣ / ∣ e k − 1 ∣) (∣ e k − 1 ∣ / ∣ e k ∣) → 0 ⋅ 1 = 0 M > 0 M>0 M > 0 ∣ e k ∣ > M ∣ x k − x k − 1 ∣ \lvert e_k\rvert>M\lvert x_k-x_{k-1}\rvert ∣ e k ∣ > M ∣ x k − x k − 1 ∣ k ≥ 1 k\ge1 k ≥ 1 ∣ x j − x j − 1 ∣ = x j − 1 3 \lvert x_j-x_{j-1}\rvert=x_{j-1}^3 ∣ x j − x j − 1 ∣ = x j − 1 3 j j j τ r e l = 0 \tau_{\mathrm{rel}}=0 τ rel = 0 τ a b s = ∣ x k − x k − 1 ∣ \tau_{\mathrm{abs}}=\lvert x_k-x_{k-1}\rvert τ abs = ∣ x k − x k − 1 ∣ k k k g − g_- g − 0 0 0 x k x_k x k 0 0 0 M τ a b s M\tau_{\mathrm{abs}} M τ abs M M M ∣ g − ′ ( 0 ) ∣ = 1 \lvert g_-'(0)\rvert=1 ∣ g − ′ ( 0 )∣ = 1 τ a b s \tau_{\mathrm{abs}} τ abs 例 4.5 (1) の反復列0 , 1 , 0 , 1 , … 0,1,0,1,\dots 0 , 1 , 0 , 1 , … k ≥ 1 k\ge1 k ≥ 1 ∣ x k − x k − 1 ∣ = 1 \lvert x_k-x_{k-1}\rvert=1 ∣ x k − x k − 1 ∣ = 1 ∣ f ( x k ) ∣ ≥ 1 \lvert f(x_k)\rvert\ge1 ∣ f ( x k )∣ ≥ 1 τ a b s + τ r e l < 1 \tau_{\mathrm{abs}}+\tau_{\mathrm{rel}}<1 τ abs + τ rel < 1 τ f < 1 \tau_f<1 τ f < 1 x k max ∈ { 0 , 1 } x_{k_{\max}}\in\{0,1\} x k m a x ∈ { 0 , 1 } f f f r ∈ ( − 2 , − 2 / 3 ) r\in(-2,-\sqrt{2/3}) r ∈ ( − 2 , − 2/3 ) 2 / 3 \sqrt{2/3} 2/3 f ( x ) = 10 − 12 ( x − 1 ) f(x)=10^{-12}(x-1) f ( x ) = 1 0 − 12 ( x − 1 ) [ 0 , 2 ] [0,2] [ 0 , 2 ] 命題 6.2 (3) の仮定をm = 10 − 12 m=10^{-12} m = 1 0 − 12 x k = 2 x_k=2 x k = 2 10 − 12 10^{-12} 1 0 − 12 τ f = 10 − 12 \tau_f=10^{-12} τ f = 1 0 − 12 τ f / m = 1 \tau_f/m=1 τ f / m = 1 x k x_k x k 1 1 1 §E20.2 例 6.2 ）。 7 区間を保持する Newton 法 定義 7.1. a < b a<b a < b f : [ a , b ] → R f\colon[a,b]\to\R f : [ a , b ] → R [ a , b ] [a,b] [ a , b ] ( a , b ) (a,b) ( a , b ) f ( a ) f ( b ) < 0 f(a)f(b)<0 f ( a ) f ( b ) < 0 x 0 ∈ ( a , b ) x_0\in(a,b) x 0 ∈ ( a , b ) a 0 : = a a_0:=a a 0 := a b 0 : = b b_0:=b b 0 := b k ∈ N ≥ 0 k\in\N k ∈ N ≥ 0 a k < x k < b k a_k<x_k<b_k a k < x k < b k f ( a k ) f ( b k ) < 0 f(a_k)f(b_k)<0 f ( a k ) f ( b k ) < 0 a k , x k , b k a_k,x_k,b_k a k , x k , b k
f ( x k ) = 0 f(x_k)=0 f ( x k ) = 0 x k x_k x k f ( x k ) ≠ 0 f(x_k)\ne0 f ( x k ) = 0 f ( a k ) f ( x k ) < 0 f(a_k)f(x_k)<0 f ( a k ) f ( x k ) < 0 a k + 1 : = a k a_{k+1}:=a_k a k + 1 := a k b k + 1 : = x k b_{k+1}:=x_k b k + 1 := x k f ( a k ) f ( x k ) > 0 f(a_k)f(x_k)>0 f ( a k ) f ( x k ) > 0 a k + 1 : = x k a_{k+1}:=x_k a k + 1 := x k b k + 1 : = b k b_{k+1}:=b_k b k + 1 := b k 次の三条件がすべて成り立つとき、Newton 法の候補点c k : = x k − f ( x k ) / f ′ ( x k ) c_k:=x_k-f(x_k)/f'(x_k) c k := x k − f ( x k ) / f ′ ( x k ) x k + 1 : = c k x_{k+1}:=c_k x k + 1 := c k f ′ ( x k ) ≠ 0 f'(x_k)\ne0 f ′ ( x k ) = 0 a k + 1 < c k < b k + 1 a_{k+1}<c_k<b_{k+1} a k + 1 < c k < b k + 1 b k + 1 − a k + 1 ≤ ( b k − a k ) / 2 b_{k+1}-a_{k+1}\le(b_k-a_k)/2 b k + 1 − a k + 1 ≤ ( b k − a k ) /2
(3) の三条件のいずれかが成り立たないとき、x k + 1 : = ( a k + 1 + b k + 1 ) / 2 x_{k+1}:=(a_{k+1}+b_{k+1})/2 x k + 1 := ( a k + 1 + b k + 1 ) /2 (2) でf ( a k ) f ( x k ) > 0 f(a_k)f(x_k)>0 f ( a k ) f ( x k ) > 0 定義 2.2 と同じ理由でf ( x k ) f ( b k ) < 0 f(x_k)f(b_k)<0 f ( x k ) f ( b k ) < 0 a k + 1 < x k + 1 < b k + 1 a_{k+1}<x_{k+1}<b_{k+1} a k + 1 < x k + 1 < b k + 1 f ( a k + 1 ) f ( b k + 1 ) < 0 f(a_{k+1})f(b_{k+1})<0 f ( a k + 1 ) f ( b k + 1 ) < 0 区間を保持する Newton 法 (safeguarded Newton method )
命題 7.2. 定義 7.1 の仮定の下で、w k : = b k − a k w_k:=b_k-a_k w k := b k − a k k k k f ( x k ) = 0 f(x_k)=0 f ( x k ) = 0
すべてのk ∈ N ≥ 0 k\in\N k ∈ N ≥ 0 [ a k + 1 , b k + 1 ] ⊂ [ a k , b k ] [a_{k+1},b_{k+1}]\subset[a_k,b_k] [ a k + 1 , b k + 1 ] ⊂ [ a k , b k ] w k + 1 < w k w_{k+1}<w_k w k + 1 < w k w k + 2 ≤ w k / 2 w_{k+2}\le w_k/2 w k + 2 ≤ w k /2 w k ≤ 2 − ⌊ k / 2 ⌋ ( b − a ) w_k\le2^{-\lfloor k/2\rfloor}(b-a) w k ≤ 2 − ⌊ k /2 ⌋ ( b − a )
f f f r r r k k k r ∈ [ a k , b k ] r\in[a_k,b_k] r ∈ [ a k , b k ] ∣ x k − r ∣ ≤ w k \lvert x_k-r\rvert\le w_k ∣ x k − r ∣ ≤ w k 証明. 停止する場合は定義 7.1 (1) による。停止しないとする。
(1) を示す。定義 7.1 (2) により[ a k + 1 , b k + 1 ] [a_{k+1},b_{k+1}] [ a k + 1 , b k + 1 ] [ a k , x k ] [a_k,x_k] [ a k , x k ] [ x k , b k ] [x_k,b_k] [ x k , b k ] a k < x k < b k a_k<x_k<b_k a k < x k < b k [ a k + 1 , b k + 1 ] ⊂ [ a k , b k ] [a_{k+1},b_{k+1}]\subset[a_k,b_k] [ a k + 1 , b k + 1 ] ⊂ [ a k , b k ] w k + 1 < w k w_{k+1}<w_k w k + 1 < w k w k + 1 ≤ w k / 2 w_{k+1}\le w_k/2 w k + 1 ≤ w k /2 w k + 2 < w k + 1 ≤ w k / 2 w_{k+2}<w_{k+1}\le w_k/2 w k + 2 < w k + 1 ≤ w k /2 w k + 1 > w k / 2 w_{k+1}>w_k/2 w k + 1 > w k /2 定義 7.1 (3) の第三条件が成り立たないから、定義 7.1 (4) によりx k + 1 x_{k+1} x k + 1 [ a k + 1 , b k + 1 ] [a_{k+1},b_{k+1}] [ a k + 1 , b k + 1 ] w k + 2 = w k + 1 / 2 < w k / 2 w_{k+2}=w_{k+1}/2<w_k/2 w k + 2 = w k + 1 /2 < w k /2 w 2 j ≤ 2 − j ( b − a ) w_{2j}\le2^{-j}(b-a) w 2 j ≤ 2 − j ( b − a ) j j j w k w_k w k w k ≤ w 2 ⌊ k / 2 ⌋ ≤ 2 − ⌊ k / 2 ⌋ ( b − a ) w_k\le w_{2\lfloor k/2\rfloor}\le2^{-\lfloor k/2\rfloor}(b-a) w k ≤ w 2 ⌊ k /2 ⌋ ≤ 2 − ⌊ k /2 ⌋ ( b − a )
(2) を示す。定義 7.1 によりf ( a k ) f ( b k ) < 0 f(a_k)f(b_k)<0 f ( a k ) f ( b k ) < 0 (1) によりa ≤ a k ≤ a k + 1 < b k + 1 ≤ b k ≤ b a\le a_k\le a_{k+1}<b_{k+1}\le b_k\le b a ≤ a k ≤ a k + 1 < b k + 1 ≤ b k ≤ b w k → 0 w_k\to0 w k → 0 補題 2.1 (2) のr r r f ( r ) = 0 f(r)=0 f ( r ) = 0 k k k r ∈ [ a k , b k ] r\in[a_k,b_k] r ∈ [ a k , b k ] x k ∈ [ a k , b k ] x_k\in[a_k,b_k] x k ∈ [ a k , b k ] 補題 2.1 (3) により∣ x k − r ∣ ≤ w k \lvert x_k-r\rvert\le w_k ∣ x k − r ∣ ≤ w k ▨
例 7.3. f ( x ) = x 2 − 2 f(x)=x^2-2 f ( x ) = x 2 − 2 [ a , b ] = [ 1 , 2 ] [a,b]=[1,2] [ a , b ] = [ 1 , 2 ] x 0 = 3 / 2 x_0=3/2 x 0 = 3/2 x > 2 x>\sqrt2 x > 2 N f ( x ) − 2 = ( x − 2 ) 2 / ( 2 x ) > 0 N_f(x)-\sqrt2=(x-\sqrt2)^2/(2x)>0 N f ( x ) − 2 = ( x − 2 ) 2 / ( 2 x ) > 0 N f ( x ) < x N_f(x)<x N f ( x ) < x 3 / 2 , 17 / 12 , 577 / 408 , … 3/2,17/12,577/408,\dots 3/2 , 17/12 , 577/408 , … 2 \sqrt2 2 f ( x k ) > 0 f(x_k)>0 f ( x k ) > 0 定義 7.1 (3) の第三条件を除いた二条件だけで受理すると、各段で[ a k + 1 , b k + 1 ] = [ 1 , x k ] [a_{k+1},b_{k+1}]=[1,x_k] [ a k + 1 , b k + 1 ] = [ 1 , x k ] w k = x k − 1 − 1 → 2 − 1 w_k=x_{k-1}-1\to\sqrt2-1 w k = x k − 1 − 1 → 2 − 1 0 0 0 0 0 0 [ a 1 , b 1 ] = [ 1 , 3 / 2 ] [a_1,b_1]=[1,3/2] [ a 1 , b 1 ] = [ 1 , 3/2 ] w 1 = 1 / 2 ≤ w 0 / 2 w_1=1/2\le w_0/2 w 1 = 1/2 ≤ w 0 /2 17 / 12 17/12 17/12 1 1 1 [ a 2 , b 2 ] = [ 1 , 17 / 12 ] [a_2,b_2]=[1,17/12] [ a 2 , b 2 ] = [ 1 , 17/12 ] w 2 = 5 / 12 > w 1 / 2 = 1 / 4 w_2=5/12>w_1/2=1/4 w 2 = 5/12 > w 1 /2 = 1/4 x 2 = 29 / 24 x_2=29/24 x 2 = 29/24 2 2 2 f ( 29 / 24 ) < 0 f(29/24)<0 f ( 29/24 ) < 0 [ a 3 , b 3 ] = [ 29 / 24 , 17 / 12 ] [a_3,b_3]=[29/24,17/12] [ a 3 , b 3 ] = [ 29/24 , 17/12 ] w 3 = 5 / 24 = w 2 / 2 w_3=5/24=w_2/2 w 3 = 5/24 = w 2 /2 N f ( 29 / 24 ) = 1993 / 1392 N_f(29/24)=1993/1392 N f ( 29/24 ) = 1993/1392 17 / 12 = 1972 / 1392 17/12=1972/1392 17/12 = 1972/1392 x 3 = 21 / 16 x_3=21/16 x 3 = 21/16
8 演習 解答. 補題 1.2 (1) を示す。線形収束を次数1 1 1 q , q ′ ≥ 1 q,q'\ge1 q , q ′ ≥ 1 ∣ e k + 1 ∣ / ∣ e k ∣ q → C ∈ ( 0 , + ∞ ) \lvert e_{k+1}\rvert/\lvert e_k\rvert^q\to C\in(0,+\infty) ∣ e k + 1 ∣ / ∣ e k ∣ q → C ∈ ( 0 , + ∞ ) ∣ e k + 1 ∣ / ∣ e k ∣ q ′ → C ′ ∈ ( 0 , + ∞ ) \lvert e_{k+1}\rvert/\lvert e_k\rvert^{q'}\to C'\in(0,+\infty) ∣ e k + 1 ∣ / ∣ e k ∣ q ′ → C ′ ∈ ( 0 , + ∞ ) q < q ′ q<q' q < q ′
∣ e k + 1 ∣ ∣ e k ∣ q ′ = ∣ e k + 1 ∣ ∣ e k ∣ q ⋅ ∣ e k ∣ q − q ′ \frac{\lvert e_{k+1}\rvert}{\lvert e_k\rvert^{q'}}=\frac{\lvert e_{k+1}\rvert}{\lvert e_k\rvert^{q}}\cdot\lvert e_k\rvert^{q-q'} ∣ e k ∣ q ′ ∣ e k + 1 ∣ = ∣ e k ∣ q ∣ e k + 1 ∣ ⋅ ∣ e k ∣ q − q ′ の右辺の第一因子はC > 0 C>0 C > 0 ∣ e k ∣ → 0 \lvert e_k\rvert\to0 ∣ e k ∣ → 0 q − q ′ < 0 q-q'<0 q − q ′ < 0 + ∞ +\infty + ∞ + ∞ +\infty + ∞ C ′ < + ∞ C'<+\infty C ′ < + ∞ q ′ < q q'<q q ′ < q q = q ′ q=q' q = q ′ C = C ′ C=C' C = C ′
補題 1.2 (2) を示す。∣ e k + 1 ∣ / ∣ e k ∣ = ( ∣ e k + 1 ∣ / ∣ e k ∣ q ) ∣ e k ∣ q − 1 \lvert e_{k+1}\rvert/\lvert e_k\rvert=(\lvert e_{k+1}\rvert/\lvert e_k\rvert^q)\lvert e_k\rvert^{q-1} ∣ e k + 1 ∣ / ∣ e k ∣ = (∣ e k + 1 ∣ / ∣ e k ∣ q ) ∣ e k ∣ q − 1 C C C q − 1 > 0 q-1>0 q − 1 > 0 0 0 0 0 0 0 ▨
問題 8.2. c > 0 c>0 c > 0 f ( x ) = x 2 − c f(x)=x^2-c f ( x ) = x 2 − c I = ( 0 , + ∞ ) I=(0,+\infty) I = ( 0 , + ∞ ) x 0 > 0 x_0>0 x 0 > 0 ( x k ) (x_k) ( x k ) k ≥ 1 k\ge1 k ≥ 1 x k x_k x k x k ≥ c x_k\ge\sqrt c x k ≥ c e k : = x k − c e_k:=x_k-\sqrt c e k := x k − c k ≥ 1 k\ge1 k ≥ 1 0 ≤ e k + 1 ≤ min { e k / 2 , e k 2 / ( 2 c ) } 0\le e_{k+1}\le\min\{e_k/2,\ e_k^2/(2\sqrt c)\} 0 ≤ e k + 1 ≤ min { e k /2 , e k 2 / ( 2 c )} x k → c x_k\to\sqrt c x k → c
解答. x > 0 x>0 x > 0 f ′ ( x ) = 2 x ≠ 0 f'(x)=2x\ne0 f ′ ( x ) = 2 x = 0 N f ( x ) = ( x + c / x ) / 2 > 0 N_f(x)=(x+c/x)/2>0 N f ( x ) = ( x + c / x ) /2 > 0 x > 0 x>0 x > 0
N f ( x ) − c = x 2 − 2 c x + c 2 x = ( x − c ) 2 2 x ≥ 0 N_f(x)-\sqrt c=\frac{x^2-2\sqrt c\,x+c}{2x}=\frac{(x-\sqrt c)^2}{2x}\ge0 N f ( x ) − c = 2 x x 2 − 2 c x + c = 2 x ( x − c ) 2 ≥ 0 であるから、k ≥ 1 k\ge1 k ≥ 1 x k ≥ c x_k\ge\sqrt c x k ≥ c e k ≥ 0 e_k\ge0 e k ≥ 0 k ≥ 1 k\ge1 k ≥ 1 e k + 1 = e k 2 / ( 2 x k ) e_{k+1}=e_k^2/(2x_k) e k + 1 = e k 2 / ( 2 x k ) x k ≥ c x_k\ge\sqrt c x k ≥ c e k + 1 ≤ e k 2 / ( 2 c ) e_{k+1}\le e_k^2/(2\sqrt c) e k + 1 ≤ e k 2 / ( 2 c ) 0 ≤ e k < x k 0\le e_k<x_k 0 ≤ e k < x k e k + 1 ≤ e k / 2 e_{k+1}\le e_k/2 e k + 1 ≤ e k /2 0 ≤ e k ≤ 2 − ( k − 1 ) e 1 → 0 0\le e_k\le2^{-(k-1)}e_1\to0 0 ≤ e k ≤ 2 − ( k − 1 ) e 1 → 0 x k → c x_k\to\sqrt c x k → c ▨
問題 8.3. f ( x ) = x + x 3 f(x)=x+x^3 f ( x ) = x + x 3 I = R I=\R I = R r = 0 r=0 r = 0 N f ( x ) = 2 x 3 / ( 1 + 3 x 2 ) N_f(x)=2x^3/(1+3x^2) N f ( x ) = 2 x 3 / ( 1 + 3 x 2 ) ∣ x 0 ∣ ≤ 1 / 2 \lvert x_0\rvert\le1/2 ∣ x 0 ∣ ≤ 1/2 x 0 ≠ 0 x_0\ne0 x 0 = 0 ( x k ) (x_k) ( x k ) k k k x k ≠ 0 x_k\ne0 x k = 0 x k → 0 x_k\to0 x k → 0 ( x k ) (x_k) ( x k ) 0 0 0 3 3 3 2 2 2
解答. f ′ ( x ) = 1 + 3 x 2 ≥ 1 f'(x)=1+3x^2\ge1 f ′ ( x ) = 1 + 3 x 2 ≥ 1 x ∈ R x\in\R x ∈ R f ′ ( x ) ≠ 0 f'(x)\ne0 f ′ ( x ) = 0
N f ( x ) = x − x + x 3 1 + 3 x 2 = x + 3 x 3 − x − x 3 1 + 3 x 2 = 2 x 3 1 + 3 x 2 N_f(x)=x-\frac{x+x^3}{1+3x^2}=\frac{x+3x^3-x-x^3}{1+3x^2}=\frac{2x^3}{1+3x^2} N f ( x ) = x − 1 + 3 x 2 x + x 3 = 1 + 3 x 2 x + 3 x 3 − x − x 3 = 1 + 3 x 2 2 x 3 である。0 < ∣ x ∣ ≤ 1 / 2 0<\lvert x\rvert\le1/2 0 < ∣ x ∣ ≤ 1/2 N f ( x ) ≠ 0 N_f(x)\ne0 N f ( x ) = 0 1 + 3 x 2 ≥ 1 1+3x^2\ge1 1 + 3 x 2 ≥ 1 x 2 ≤ 1 / 4 x^2\le1/4 x 2 ≤ 1/4
∣ N f ( x ) ∣ ≤ 2 ∣ x ∣ 3 = 2 x 2 ∣ x ∣ ≤ ∣ x ∣ 2 \lvert N_f(x)\rvert\le2\lvert x\rvert^3=2x^2\lvert x\rvert\le\frac{\lvert x\rvert}{2} ∣ N f ( x )∣ ≤ 2 ∣ x ∣ 3 = 2 x 2 ∣ x ∣ ≤ 2 ∣ x ∣ である。k k k k k k 0 < ∣ x k ∣ ≤ 2 − k ∣ x 0 ∣ ≤ 1 / 2 0<\lvert x_k\rvert\le2^{-k}\lvert x_0\rvert\le1/2 0 < ∣ x k ∣ ≤ 2 − k ∣ x 0 ∣ ≤ 1/2 k k k x k ≠ 0 x_k\ne0 x k = 0 x k → 0 x_k\to0 x k → 0 e k : = x k − 0 = x k e_k:=x_k-0=x_k e k := x k − 0 = x k
e k + 1 e k 3 = 2 1 + 3 x k 2 \frac{e_{k+1}}{e_k^3}=\frac{2}{1+3x_k^2} e k 3 e k + 1 = 1 + 3 x k 2 2 であり、x k → 0 x_k\to0 x k → 0 e k + 1 / e k 3 → 2 e_{k+1}/e_k^3\to2 e k + 1 / e k 3 → 2 ∣ e k + 1 ∣ / ∣ e k ∣ 3 → 2 \lvert e_{k+1}\rvert/\lvert e_k\rvert^3\to2 ∣ e k + 1 ∣ / ∣ e k ∣ 3 → 2 2 ∈ ( 0 , + ∞ ) 2\in(0,+\infty) 2 ∈ ( 0 , + ∞ ) 定義 1.1 (1) のq = 3 q=3 q = 3 C = 2 C=2 C = 2 ▨