1 計算グラフ 定義 1.1. n , N ∈ N ≥ 1 n,N\in\NN n , N ∈ N ≥ 1 n < N n<N n < N U ⊆ R n U\subseteq\R^n U ⊆ R n U U U n n n N N N 計算グラフ (computational graph )
各整数k k k n < k ≤ N n<k\le N n < k ≤ N P k ⊆ { 1 , … , k − 1 } P_k\subseteq\{1,\dots,k-1\} P k ⊆ { 1 , … , k − 1 } W k ⊆ R P k W_k\subseteq\R^{P_k} W k ⊆ R P k C 1 C^1 C 1 φ k : W k → R \varphi_k\colon W_k\to\R φ k : W k → R R P k \R^{P_k} R P k P k P_k P k ( w j ) j ∈ P k (w_j)_{j\in P_k} ( w j ) j ∈ P k R ∣ P k ∣ \R^{|P_k|} R ∣ P k ∣
m ∈ N ≥ 1 m\in\NN m ∈ N ≥ 1 o 1 , … , o m ∈ { 1 , … , N } o_1,\dots,o_m\in\{1,\dots,N\} o 1 , … , o m ∈ { 1 , … , N } 添字1 , … , N 1,\dots,N 1 , … , N 節点 (node )j ∈ P k j\in P_k j ∈ P k j j j k k k 先行節点 (predecessor )k k k j j j 後続節点 (successor )j j j S j : = { k ∣ n < k ≤ N , j ∈ P k } S_j:=\{k\mid n<k\le N,\ j\in P_k\} S j := { k ∣ n < k ≤ N , j ∈ P k } S j ⊆ { max ( j , n ) + 1 , … , N } S_j\subseteq\{\max(j,n)+1,\dots,N\} S j ⊆ { max ( j , n ) + 1 , … , N }
集合Ω k ⊆ U \Omega_k\subseteq U Ω k ⊆ U v k : Ω k → R v_k\colon\Omega_k\to\R v k : Ω k → R k k k Ω n : = U \Omega_n:=U Ω n := U 1 ≤ i ≤ n 1\le i\le n 1 ≤ i ≤ n v i ( x ) : = x i v_i(x):=x_i v i ( x ) := x i n < k ≤ N n<k\le N n < k ≤ N v j v_j v j j < k j<k j < k Ω k − 1 \Omega_{k-1} Ω k − 1
Ω k : = { x ∈ Ω k − 1 ∣ ( v j ( x ) ) j ∈ P k ∈ W k } , v k ( x ) : = φ k ( ( v j ( x ) ) j ∈ P k ) ( x ∈ Ω k ) \Omega_k:=\bigl\{x\in\Omega_{k-1}\bigm|(v_j(x))_{j\in P_k}\in W_k\bigr\},\qquad v_k(x):=\varphi_k\bigl((v_j(x))_{j\in P_k}\bigr)\quad(x\in\Omega_k) Ω k := { x ∈ Ω k − 1 ( v j ( x ) ) j ∈ P k ∈ W k } , v k ( x ) := φ k ( ( v j ( x ) ) j ∈ P k ) ( x ∈ Ω k ) とする。Ω : = Ω N \Omega:=\Omega_N Ω := Ω N F : Ω → R m F\colon\Omega\to\R^m F : Ω → R m F ( x ) : = ( v o 1 ( x ) , … , v o m ( x ) ) F(x):=(v_{o_1}(x),\dots,v_{o_m}(x)) F ( x ) := ( v o 1 ( x ) , … , v o m ( x )) x ∈ Ω x\in\Omega x ∈ Ω v 1 ( x ) , … , v N ( x ) v_1(x),\dots,v_N(x) v 1 ( x ) , … , v N ( x ) F ( x ) F(x) F ( x )
n < k ≤ N n<k\le N n < k ≤ N x ∈ Ω k x\in\Omega_k x ∈ Ω k j ∈ P k j\in P_k j ∈ P k
c k j ( x ) : = ∂ φ k ∂ w j ( ( v i ( x ) ) i ∈ P k ) c_{kj}(x):=\frac{\partial\varphi_k}{\partial w_j}\bigl((v_i(x))_{i\in P_k}\bigr) c k j ( x ) := ∂ w j ∂ φ k ( ( v i ( x ) ) i ∈ P k ) を節点k k k j j j 局所偏導関数 (local partial derivative )j ∈ { 1 , … , k − 1 } ∖ P k j\in\{1,\dots,k-1\}\setminus P_k j ∈ { 1 , … , k − 1 } ∖ P k c k j ( x ) : = 0 c_{kj}(x):=0 c k j ( x ) := 0
補題 1.2. U ⊆ R n U\subseteq\R^n U ⊆ R n 定義 1.1 のとおりとする。
各k ∈ { n , … , N } k\in\{n,\dots,N\} k ∈ { n , … , N } Ω k \Omega_k Ω k j ≤ k j\le k j ≤ k v j v_j v j Ω k \Omega_k Ω k C 1 C^1 C 1 Ω \Omega Ω F F F Ω \Omega Ω C 1 C^1 C 1
n < k ≤ N n<k\le N n < k ≤ N x ∈ Ω k x\in\Omega_k x ∈ Ω k D v k ( x ) = ∑ j ∈ P k c k j ( x ) D v j ( x ) Dv_k(x)=\sum_{j\in P_k}c_{kj}(x)\,Dv_j(x) D v k ( x ) = j ∈ P k ∑ c k j ( x ) D v j ( x ) 証明. k = n k=n k = n Ω n = U \Omega_n=U Ω n = U v i v_i v i i ≤ n i\le n i ≤ n C 1 C^1 C 1
n < k ≤ N n<k\le N n < k ≤ N Ω k − 1 \Omega_{k-1} Ω k − 1 v j v_j v j j < k j<k j < k Ω k − 1 \Omega_{k-1} Ω k − 1 C 1 C^1 C 1 w k : Ω k − 1 → R P k w_k\colon\Omega_{k-1}\to\R^{P_k} w k : Ω k − 1 → R P k w k ( x ) : = ( v j ( x ) ) j ∈ P k w_k(x):=(v_j(x))_{j\in P_k} w k ( x ) := ( v j ( x ) ) j ∈ P k w k w_k w k C 1 C^1 C 1 w k w_k w k C 1 C^1 C 1 Ω k = w k − 1 ( W k ) \Omega_k=w_k^{-1}(W_k) Ω k = w k − 1 ( W k ) Ω k − 1 \Omega_{k-1} Ω k − 1 W k W_k W k R n \R^n R n Ω k \Omega_k Ω k v k = φ k ∘ w k v_k=\varphi_k\circ w_k v k = φ k ∘ w k §E4.3 定理 1.1 により、v k v_k v k x ∈ Ω k x\in\Omega_k x ∈ Ω k
D v k ( x ) = D φ k ( w k ( x ) ) D w k ( x ) = ∑ j ∈ P k ∂ φ k ∂ w j ( w k ( x ) ) D v j ( x ) = ∑ j ∈ P k c k j ( x ) D v j ( x ) Dv_k(x)=D\varphi_k(w_k(x))\,Dw_k(x)=\sum_{j\in P_k}\frac{\partial\varphi_k}{\partial w_j}(w_k(x))\,Dv_j(x)=\sum_{j\in P_k}c_{kj}(x)\,Dv_j(x) D v k ( x ) = D φ k ( w k ( x )) D w k ( x ) = j ∈ P k ∑ ∂ w j ∂ φ k ( w k ( x )) D v j ( x ) = j ∈ P k ∑ c k j ( x ) D v j ( x ) が成り立つ。c k j = ∂ φ k ∂ w j ∘ w k c_{kj}=\frac{\partial\varphi_k}{\partial w_j}\circ w_k c k j = ∂ w j ∂ φ k ∘ w k v k v_k v k ∑ j ∈ P k c k j ∂ i v j \sum_{j\in P_k}c_{kj}\,\partial_iv_j ∑ j ∈ P k c k j ∂ i v j Ω k \Omega_k Ω k v k v_k v k Ω k \Omega_k Ω k C 1 C^1 C 1 v j v_j v j j < k j<k j < k Ω k ⊆ Ω k − 1 \Omega_k\subseteq\Omega_{k-1} Ω k ⊆ Ω k − 1 C 1 C^1 C 1 F F F v o i v_{o_i} v o i Ω \Omega Ω F F F C 1 C^1 C 1 ▨
補題 1.3. U ⊆ R n U\subseteq\R^n U ⊆ R n x ∈ Ω x\in\Omega x ∈ Ω 定義 1.1 のとおりとする。全微分を標準基底に関する行列と同一視し、D v j ( x ) ∈ R 1 × n Dv_j(x)\in\R^{1\times n} D v j ( x ) ∈ R 1 × n D F ( x ) ∈ R m × n DF(x)\in\R^{m\times n} D F ( x ) ∈ R m × n n ≤ k ≤ N n\le k\le N n ≤ k ≤ N j j j D v j ( x ) Dv_j(x) D v j ( x ) 1 ≤ j ≤ k 1\le j\le k 1 ≤ j ≤ k J k ( x ) ∈ R k × n J_k(x)\in\R^{k\times n} J k ( x ) ∈ R k × n n < k ≤ N n<k\le N n < k ≤ N k − 1 k-1 k − 1 I k − 1 I_{k-1} I k − 1 k k k ( c k 1 ( x ) , … , c k , k − 1 ( x ) ) (c_{k1}(x),\dots,c_{k,k-1}(x)) ( c k 1 ( x ) , … , c k , k − 1 ( x )) L k ( x ) ∈ R k × ( k − 1 ) L_k(x)\in\R^{k\times(k-1)} L k ( x ) ∈ R k × ( k − 1 ) i i i R N \R^N R N o i o_i o i Π ∈ R m × N \Pi\in\R^{m\times N} Π ∈ R m × N
J n ( x ) = I n J_n(x)=I_n J n ( x ) = I n n < k ≤ N n<k\le N n < k ≤ N J k ( x ) = L k ( x ) J k − 1 ( x ) J_k(x)=L_k(x)J_{k-1}(x) J k ( x ) = L k ( x ) J k − 1 ( x ) D F ( x ) = Π L N ( x ) L N − 1 ( x ) ⋯ L n + 1 ( x ) DF(x)=\Pi\,L_N(x)L_{N-1}(x)\cdots L_{n+1}(x) D F ( x ) = Π L N ( x ) L N − 1 ( x ) ⋯ L n + 1 ( x ) 証明. i ≤ n i\le n i ≤ n v i v_i v i i i i D v i ( x ) Dv_i(x) D v i ( x ) i i i J n ( x ) = I n J_n(x)=I_n J n ( x ) = I n n < k ≤ N n<k\le N n < k ≤ N L k ( x ) J k − 1 ( x ) L_k(x)J_{k-1}(x) L k ( x ) J k − 1 ( x ) k − 1 k-1 k − 1 J k − 1 ( x ) J_{k-1}(x) J k − 1 ( x ) D v 1 ( x ) , … , D v k − 1 ( x ) Dv_1(x),\dots,Dv_{k-1}(x) D v 1 ( x ) , … , D v k − 1 ( x ) k k k ∑ j < k c k j ( x ) D v j ( x ) = ∑ j ∈ P k c k j ( x ) D v j ( x ) \sum_{j<k}c_{kj}(x)Dv_j(x)=\sum_{j\in P_k}c_{kj}(x)Dv_j(x) ∑ j < k c k j ( x ) D v j ( x ) = ∑ j ∈ P k c k j ( x ) D v j ( x ) 補題 1.2 (2) によりこの行はD v k ( x ) Dv_k(x) D v k ( x ) L k ( x ) J k − 1 ( x ) = J k ( x ) L_k(x)J_{k-1}(x)=J_k(x) L k ( x ) J k − 1 ( x ) = J k ( x )
(1) を繰り返し用いるとJ N ( x ) = L N ( x ) ⋯ L n + 1 ( x ) J_N(x)=L_N(x)\cdots L_{n+1}(x) J N ( x ) = L N ( x ) ⋯ L n + 1 ( x ) Π J N ( x ) \Pi J_N(x) Π J N ( x ) i i i J N ( x ) J_N(x) J N ( x ) o i o_i o i D v o i ( x ) Dv_{o_i}(x) D v o i ( x ) F F F i i i v o i v_{o_i} v o i Ω \Omega Ω D F ( x ) DF(x) D F ( x ) i i i D F ( x ) = Π L N ( x ) ⋯ L n + 1 ( x ) DF(x)=\Pi\,L_N(x)\cdots L_{n+1}(x) D F ( x ) = Π L N ( x ) ⋯ L n + 1 ( x ) ▨
2 前進モード 定義 2.1. U ⊆ R n U\subseteq\R^n U ⊆ R n 定義 1.1 のとおりとする。x ∈ Ω x\in\Omega x ∈ Ω x ˙ ∈ R n \dot x\in\R^n x ˙ ∈ R n v ˙ 1 , … , v ˙ N \dot v_1,\dots,\dot v_N v ˙ 1 , … , v ˙ N
v ˙ i : = x ˙ i ( 1 ≤ i ≤ n ) , v ˙ k : = ∑ j ∈ P k c k j ( x ) v ˙ j ( n < k ≤ N ) \dot v_i:=\dot x_i\quad(1\le i\le n),\qquad\dot v_k:=\sum_{j\in P_k}c_{kj}(x)\,\dot v_j\quad(n<k\le N) v ˙ i := x ˙ i ( 1 ≤ i ≤ n ) , v ˙ k := j ∈ P k ∑ c k j ( x ) v ˙ j ( n < k ≤ N ) によりk k k k = n + 1 , … , N k=n+1,\dots,N k = n + 1 , … , N v k ( x ) v_k(x) v k ( x ) c k j ( x ) c_{kj}(x) c k j ( x ) j ∈ P k j\in P_k j ∈ P k v ˙ k \dot v_k v ˙ k x ˙ \dot x x ˙ 前進モード (forward mode )y ˙ : = ( v ˙ o 1 , … , v ˙ o m ) \dot y:=(\dot v_{o_1},\dots,\dot v_{o_m}) y ˙ := ( v ˙ o 1 , … , v ˙ o m )
定理 2.2. U ⊆ R n U\subseteq\R^n U ⊆ R n x ∈ Ω x\in\Omega x ∈ Ω x ˙ ∈ R n \dot x\in\R^n x ˙ ∈ R n v ˙ 1 , … , v ˙ N \dot v_1,\dots,\dot v_N v ˙ 1 , … , v ˙ N y ˙ \dot y y ˙ 定義 2.1 のとおりとする。任意のk ∈ { 1 , … , N } k\in\{1,\dots,N\} k ∈ { 1 , … , N } v ˙ k = D v k ( x ) x ˙ \dot v_k=Dv_k(x)\dot x v ˙ k = D v k ( x ) x ˙ y ˙ = D F ( x ) x ˙ \dot y=DF(x)\dot x y ˙ = D F ( x ) x ˙
証明. J k ( x ) J_k(x) J k ( x ) L k ( x ) L_k(x) L k ( x ) Π \Pi Π 補題 1.3 のとおりとし、n ≤ k ≤ N n\le k\le N n ≤ k ≤ N w ( k ) : = J k ( x ) x ˙ ∈ R k w^{(k)}:=J_k(x)\dot x\in\R^k w ( k ) := J k ( x ) x ˙ ∈ R k w ( k ) w^{(k)} w ( k ) j j j D v j ( x ) x ˙ Dv_j(x)\dot x D v j ( x ) x ˙ 補題 1.3 (1) によりw ( n ) = x ˙ w^{(n)}=\dot x w ( n ) = x ˙ n < k ≤ N n<k\le N n < k ≤ N w ( k ) = L k ( x ) w ( k − 1 ) w^{(k)}=L_k(x)w^{(k-1)} w ( k ) = L k ( x ) w ( k − 1 )
w j ( k ) = w j ( k − 1 ) ( j < k ) , w k ( k ) = ∑ j ∈ P k c k j ( x ) w j ( k − 1 ) w^{(k)}_j=w^{(k-1)}_j\quad(j<k),\qquad w^{(k)}_k=\sum_{j\in P_k}c_{kj}(x)\,w^{(k-1)}_j w j ( k ) = w j ( k − 1 ) ( j < k ) , w k ( k ) = j ∈ P k ∑ c k j ( x ) w j ( k − 1 ) である。w i ( n ) = x ˙ i = v ˙ i w^{(n)}_i=\dot x_i=\dot v_i w i ( n ) = x ˙ i = v ˙ i w ( k ) w^{(k)} w ( k ) ( v ˙ 1 , … , v ˙ k ) (\dot v_1,\dots,\dot v_k) ( v ˙ 1 , … , v ˙ k ) k k k w ( k ) = ( v ˙ 1 , … , v ˙ k ) w^{(k)}=(\dot v_1,\dots,\dot v_k) w ( k ) = ( v ˙ 1 , … , v ˙ k ) v ˙ k = w k ( k ) = D v k ( x ) x ˙ \dot v_k=w^{(k)}_k=Dv_k(x)\dot x v ˙ k = w k ( k ) = D v k ( x ) x ˙ 補題 1.3 (2) によりD F ( x ) x ˙ = Π J N ( x ) x ˙ = Π w ( N ) = ( v ˙ o 1 , … , v ˙ o m ) = y ˙ DF(x)\dot x=\Pi J_N(x)\dot x=\Pi w^{(N)}=(\dot v_{o_1},\dots,\dot v_{o_m})=\dot y D F ( x ) x ˙ = Π J N ( x ) x ˙ = Π w ( N ) = ( v ˙ o 1 , … , v ˙ o m ) = y ˙ ▨
例 2.3. 条件分岐を含む手続きは、分岐の各場合ごとに一つの計算グラフを実行する。手続きが計算する関数f f f F b F_b F b x x x f f f x x x D f ( x ) = D F b ( x ) Df(x)=DF_b(x) D f ( x ) = D F b ( x ) x x x f f f x x x f f f
実数x x x x ≥ 0 x\ge0 x ≥ 0 y : = x y:=x y := x x < 0 x<0 x < 0 y : = − x y:=-x y := − x f ( x ) = ∣ x ∣ f(x)=|x| f ( x ) = ∣ x ∣ x ≥ 0 x\ge0 x ≥ 0 n = 1 n=1 n = 1 N = 2 N=2 N = 2 P 2 = { 1 } P_2=\{1\} P 2 = { 1 } W 2 = R W_2=\R W 2 = R φ 2 ( w 1 ) = w 1 \varphi_2(w_1)=w_1 φ 2 ( w 1 ) = w 1 o 1 = 2 o_1=2 o 1 = 2 F + ( x ) = x F_+(x)=x F + ( x ) = x x = 0 x=0 x = 0 x ˙ = 1 \dot x=1 x ˙ = 1 F + ′ ( 0 ) = 1 F_+'(0)=1 F + ′ ( 0 ) = 1 h > 0 h>0 h > 0 ( f ( h ) − f ( 0 ) ) / h = 1 (f(h)-f(0))/h=1 ( f ( h ) − f ( 0 )) / h = 1 h < 0 h<0 h < 0 ( f ( h ) − f ( 0 ) ) / h = − 1 (f(h)-f(0))/h=-1 ( f ( h ) − f ( 0 )) / h = − 1 f f f 0 0 0 x > 0 x>0 x > 0 f f f F + F_+ F + ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) f ′ ( x ) = 1 f'(x)=1 f ′ ( x ) = 1
実数x x x x = 0 x=0 x = 0 y : = 0 y:=0 y := 0 x ≠ 0 x\ne0 x = 0 y : = x y:=x y := x f ( x ) = x f(x)=x f ( x ) = x f ′ ( 0 ) = 1 f'(0)=1 f ′ ( 0 ) = 1 x = 0 x=0 x = 0 n = 1 n=1 n = 1 N = 2 N=2 N = 2 P 2 = { 1 } P_2=\{1\} P 2 = { 1 } W 2 = R W_2=\R W 2 = R φ 2 ( w 1 ) = 0 \varphi_2(w_1)=0 φ 2 ( w 1 ) = 0 o 1 = 2 o_1=2 o 1 = 2 c 21 = 0 c_{21}=0 c 21 = 0 x ˙ = 1 \dot x=1 x ˙ = 1 0 ≠ f ′ ( 0 ) 0\ne f'(0) 0 = f ′ ( 0 ) { 0 } \{0\} { 0 } 0 0 0
3 逆モード 定義 3.1. U ⊆ R n U\subseteq\R^n U ⊆ R n 定義 1.1 のとおりとする。x ∈ Ω x\in\Omega x ∈ Ω y ˉ ∈ R m \bar y\in\R^m y ˉ ∈ R m j ∈ { 1 , … , N } j\in\{1,\dots,N\} j ∈ { 1 , … , N } j = o i j=o_i j = o i σ j : = y ˉ i \sigma_j:=\bar y_i σ j := y ˉ i j ∉ { o 1 , … , o m } j\notin\{o_1,\dots,o_m\} j ∈ / { o 1 , … , o m } σ j : = 0 \sigma_j:=0 σ j := 0 o 1 , … , o m o_1,\dots,o_m o 1 , … , o m σ j \sigma_j σ j v ˉ N , v ˉ N − 1 , … , v ˉ 1 \bar v_N,\bar v_{N-1},\dots,\bar v_1 v ˉ N , v ˉ N − 1 , … , v ˉ 1 j j j
v ˉ j : = σ j + ∑ k ∈ S j v ˉ k c k j ( x ) \bar v_j:=\sigma_j+\sum_{k\in S_j}\bar v_k\,c_{kj}(x) v ˉ j := σ j + k ∈ S j ∑ v ˉ k c k j ( x ) により定める。ここで和はj j j k k k S j = ∅ S_j=\emptyset S j = ∅ 0 0 0 S j ⊆ { j + 1 , … , N } S_j\subseteq\{j+1,\dots,N\} S j ⊆ { j + 1 , … , N } v ˉ k \bar v_k v ˉ k v ˉ j \bar v_j v ˉ j v ˉ j \bar v_j v ˉ j j j j 随伴 (adjoint )k = n + 1 , … , N k=n+1,\dots,N k = n + 1 , … , N v k ( x ) v_k(x) v k ( x ) c k j ( x ) c_{kj}(x) c k j ( x ) j ∈ P k j\in P_k j ∈ P k j = N , … , 1 j=N,\dots,1 j = N , … , 1 v ˉ j \bar v_j v ˉ j y ˉ \bar y y ˉ 逆モード (reverse mode )x ˉ : = ( v ˉ 1 , … , v ˉ n ) \bar x:=(\bar v_1,\dots,\bar v_n) x ˉ := ( v ˉ 1 , … , v ˉ n )
定理 3.2. U ⊆ R n U\subseteq\R^n U ⊆ R n x ∈ Ω x\in\Omega x ∈ Ω y ˉ ∈ R m \bar y\in\R^m y ˉ ∈ R m v ˉ 1 , … , v ˉ N \bar v_1,\dots,\bar v_N v ˉ 1 , … , v ˉ N x ˉ \bar x x ˉ 定義 3.1 のとおりとする。このときx ˉ = D F ( x ) T y ˉ \bar x=DF(x)^{\mathsf T}\bar y x ˉ = D F ( x ) T y ˉ m = 1 m=1 m = 1 y ˉ = 1 \bar y=1 y ˉ = 1 x ˉ = ∇ F ( x ) \bar x=\nabla F(x) x ˉ = ∇ F ( x )
証明. L k ( x ) L_k(x) L k ( x ) Π \Pi Π 補題 1.3 のとおりとする。n ≤ k ≤ N n\le k\le N n ≤ k ≤ N a ( k ) ∈ R k a^{(k)}\in\R^k a ( k ) ∈ R k
a j ( k ) : = σ j + ∑ l ∈ S j , l > k v ˉ l c l j ( x ) ( 1 ≤ j ≤ k ) a^{(k)}_j:=\sigma_j+\sum_{l\in S_j,\ l>k}\bar v_l\,c_{lj}(x)\qquad(1\le j\le k) a j ( k ) := σ j + l ∈ S j , l > k ∑ v ˉ l c l j ( x ) ( 1 ≤ j ≤ k ) で定める。
l > N l>N l > N l ∈ S j l\in S_j l ∈ S j a j ( N ) = σ j a^{(N)}_j=\sigma_j a j ( N ) = σ j Π T y ˉ = ∑ i = 1 m y ˉ i e o i \Pi^{\mathsf T}\bar y=\sum_{i=1}^m\bar y_i\,e_{o_i} Π T y ˉ = ∑ i = 1 m y ˉ i e o i j j j σ j \sigma_j σ j a ( N ) = Π T y ˉ a^{(N)}=\Pi^{\mathsf T}\bar y a ( N ) = Π T y ˉ
n < k ≤ N n<k\le N n < k ≤ N L k ( x ) T a ( k ) ∈ R k − 1 L_k(x)^{\mathsf T}a^{(k)}\in\R^{k-1} L k ( x ) T a ( k ) ∈ R k − 1 j j j a j ( k ) + c k j ( x ) a k ( k ) a^{(k)}_j+c_{kj}(x)\,a^{(k)}_k a j ( k ) + c k j ( x ) a k ( k ) S k ⊆ { k + 1 , … , N } S_k\subseteq\{k+1,\dots,N\} S k ⊆ { k + 1 , … , N } a k ( k ) = σ k + ∑ l ∈ S k v ˉ l c l k ( x ) = v ˉ k a^{(k)}_k=\sigma_k+\sum_{l\in S_k}\bar v_l\,c_{lk}(x)=\bar v_k a k ( k ) = σ k + ∑ l ∈ S k v ˉ l c l k ( x ) = v ˉ k j < k j<k j < k j ∈ P k j\in P_k j ∈ P k k ∈ S j k\in S_j k ∈ S j
a j ( k ) + c k j ( x ) v ˉ k = σ j + ∑ l ∈ S j , l ≥ k v ˉ l c l j ( x ) = a j ( k − 1 ) a^{(k)}_j+c_{kj}(x)\,\bar v_k=\sigma_j+\sum_{l\in S_j,\ l\ge k}\bar v_l\,c_{lj}(x)=a^{(k-1)}_j a j ( k ) + c k j ( x ) v ˉ k = σ j + l ∈ S j , l ≥ k ∑ v ˉ l c l j ( x ) = a j ( k − 1 ) である。j < k j<k j < k j ∉ P k j\notin P_k j ∈ / P k c k j ( x ) = 0 c_{kj}(x)=0 c k j ( x ) = 0 k ∉ S j k\notin S_j k ∈ / S j a j ( k ) + c k j ( x ) v ˉ k = a j ( k ) = a j ( k − 1 ) a^{(k)}_j+c_{kj}(x)\,\bar v_k=a^{(k)}_j=a^{(k-1)}_j a j ( k ) + c k j ( x ) v ˉ k = a j ( k ) = a j ( k − 1 ) a ( k − 1 ) = L k ( x ) T a ( k ) a^{(k-1)}=L_k(x)^{\mathsf T}a^{(k)} a ( k − 1 ) = L k ( x ) T a ( k )
j ≤ n j\le n j ≤ n S j ⊆ { n + 1 , … , N } S_j\subseteq\{n+1,\dots,N\} S j ⊆ { n + 1 , … , N } a j ( n ) = σ j + ∑ l ∈ S j v ˉ l c l j ( x ) = v ˉ j a^{(n)}_j=\sigma_j+\sum_{l\in S_j}\bar v_l\,c_{lj}(x)=\bar v_j a j ( n ) = σ j + ∑ l ∈ S j v ˉ l c l j ( x ) = v ˉ j a ( n ) = x ˉ a^{(n)}=\bar x a ( n ) = x ˉ 補題 1.3 (2) により
x ˉ = L n + 1 ( x ) T ⋯ L N ( x ) T Π T y ˉ = ( Π L N ( x ) ⋯ L n + 1 ( x ) ) T y ˉ = D F ( x ) T y ˉ \bar x=L_{n+1}(x)^{\mathsf T}\cdots L_N(x)^{\mathsf T}\,\Pi^{\mathsf T}\bar y=\bigl(\Pi\,L_N(x)\cdots L_{n+1}(x)\bigr)^{\mathsf T}\bar y=DF(x)^{\mathsf T}\bar y x ˉ = L n + 1 ( x ) T ⋯ L N ( x ) T Π T y ˉ = ( Π L N ( x ) ⋯ L n + 1 ( x ) ) T y ˉ = D F ( x ) T y ˉ が成り立つ。
m = 1 m=1 m = 1 §E4.3 定理 3.2 により任意のh ∈ R n h\in\R^n h ∈ R n D F ( x ) h = ⟨ ∇ F ( x ) , h ⟩ DF(x)h=\langle\nabla F(x),h\rangle D F ( x ) h = ⟨ ∇ F ( x ) , h ⟩ D F ( x ) DF(x) D F ( x ) ∇ F ( x ) T \nabla F(x)^{\mathsf T} ∇ F ( x ) T D F ( x ) T ⋅ 1 = ∇ F ( x ) DF(x)^{\mathsf T}\cdot1=\nabla F(x) D F ( x ) T ⋅ 1 = ∇ F ( x ) ▨
例 3.3. U = R 2 U=\R^2 U = R 2 2 2 2 5 5 5 P 3 = P 4 = { 1 , 2 } P_3=P_4=\{1,2\} P 3 = P 4 = { 1 , 2 } P 5 = { 3 , 4 } P_5=\{3,4\} P 5 = { 3 , 4 } W k = R P k W_k=\R^{P_k} W k = R P k
φ 3 ( w 1 , w 2 ) = w 1 w 2 , φ 4 ( w 1 , w 2 ) = w 1 + w 2 , φ 5 ( w 3 , w 4 ) = w 3 w 4 , \varphi_3(w_1,w_2)=w_1w_2,\qquad\varphi_4(w_1,w_2)=w_1+w_2,\qquad\varphi_5(w_3,w_4)=w_3w_4, φ 3 ( w 1 , w 2 ) = w 1 w 2 , φ 4 ( w 1 , w 2 ) = w 1 + w 2 , φ 5 ( w 3 , w 4 ) = w 3 w 4 , m = 1 m=1 m = 1 o 1 = 5 o_1=5 o 1 = 5 Ω = R 2 \Omega=\R^2 Ω = R 2 F ( x ) = x 1 x 2 ( x 1 + x 2 ) F(x)=x_1x_2(x_1+x_2) F ( x ) = x 1 x 2 ( x 1 + x 2 ) c 31 = v 2 c_{31}=v_2 c 31 = v 2 c 32 = v 1 c_{32}=v_1 c 32 = v 1 c 41 = c 42 = 1 c_{41}=c_{42}=1 c 41 = c 42 = 1 c 53 = v 4 c_{53}=v_4 c 53 = v 4 c 54 = v 3 c_{54}=v_3 c 54 = v 3 S 1 = S 2 = { 3 , 4 } S_1=S_2=\{3,4\} S 1 = S 2 = { 3 , 4 } S 3 = S 4 = { 5 } S_3=S_4=\{5\} S 3 = S 4 = { 5 } S 5 = ∅ S_5=\emptyset S 5 = ∅
x = ( 2 , 3 ) x=(2,3) x = ( 2 , 3 ) ( v 1 , … , v 5 ) = ( 2 , 3 , 6 , 5 , 30 ) (v_1,\dots,v_5)=(2,3,6,5,30) ( v 1 , … , v 5 ) = ( 2 , 3 , 6 , 5 , 30 )
方向x ˙ = ( 1 , 0 ) \dot x=(1,0) x ˙ = ( 1 , 0 ) ( v ˙ 1 , … , v ˙ 5 ) = ( 1 , 0 , 3 , 1 , 21 ) (\dot v_1,\dots,\dot v_5)=(1,0,3,1,21) ( v ˙ 1 , … , v ˙ 5 ) = ( 1 , 0 , 3 , 1 , 21 ) v ˙ 5 = c 53 v ˙ 3 + c 54 v ˙ 4 = 5 ⋅ 3 + 6 ⋅ 1 \dot v_5=c_{53}\dot v_3+c_{54}\dot v_4=5\cdot3+6\cdot1 v ˙ 5 = c 53 v ˙ 3 + c 54 v ˙ 4 = 5 ⋅ 3 + 6 ⋅ 1 x ˙ = ( 0 , 1 ) \dot x=(0,1) x ˙ = ( 0 , 1 ) ( v ˙ 1 , … , v ˙ 5 ) = ( 0 , 1 , 2 , 1 , 16 ) (\dot v_1,\dots,\dot v_5)=(0,1,2,1,16) ( v ˙ 1 , … , v ˙ 5 ) = ( 0 , 1 , 2 , 1 , 16 ) ∂ 1 F ( x ) = 2 x 1 x 2 + x 2 2 = 21 \partial_1F(x)=2x_1x_2+x_2^2=21 ∂ 1 F ( x ) = 2 x 1 x 2 + x 2 2 = 21 ∂ 2 F ( x ) = x 1 2 + 2 x 1 x 2 = 16 \partial_2F(x)=x_1^2+2x_1x_2=16 ∂ 2 F ( x ) = x 1 2 + 2 x 1 x 2 = 16
重みy ˉ = 1 \bar y=1 y ˉ = 1 σ 5 = 1 \sigma_5=1 σ 5 = 1 σ 1 = ⋯ = σ 4 = 0 \sigma_1=\dots=\sigma_4=0 σ 1 = ⋯ = σ 4 = 0 v ˉ 5 = 1 , v ˉ 4 = v ˉ 5 c 54 = 6 , v ˉ 3 = v ˉ 5 c 53 = 5 , v ˉ 2 = v ˉ 3 c 32 + v ˉ 4 c 42 = 16 , v ˉ 1 = v ˉ 3 c 31 + v ˉ 4 c 41 = 21 \bar v_5=1,\quad\bar v_4=\bar v_5c_{54}=6,\quad\bar v_3=\bar v_5c_{53}=5,\quad\bar v_2=\bar v_3c_{32}+\bar v_4c_{42}=16,\quad\bar v_1=\bar v_3c_{31}+\bar v_4c_{41}=21 v ˉ 5 = 1 , v ˉ 4 = v ˉ 5 c 54 = 6 , v ˉ 3 = v ˉ 5 c 53 = 5 , v ˉ 2 = v ˉ 3 c 32 + v ˉ 4 c 42 = 16 , v ˉ 1 = v ˉ 3 c 31 + v ˉ 4 c 41 = 21 ∇ F ( x ) = ( 21 , 16 ) \nabla F(x)=(21,16) ∇ F ( x ) = ( 21 , 16 )
節点1 1 1 3 , 4 3,4 3 , 4 v ˉ 1 \bar v_1 v ˉ 1 4 4 4 v ˉ 4 c 41 = 6 \bar v_4c_{41}=6 v ˉ 4 c 41 = 6 v ˉ 3 c 31 = 15 ≠ ∂ 1 F ( x ) \bar v_3c_{31}=15\ne\partial_1F(x) v ˉ 3 c 31 = 15 = ∂ 1 F ( x ) 定理 3.2 の結論は成り立たない。
4 演算費用 命題 4.1. U ⊆ R n U\subseteq\R^n U ⊆ R n x ∈ Ω x\in\Omega x ∈ Ω 定義 1.1 のとおりとする。実数の加算・減算・乗算をそれぞれ費用1 1 1 k k k n < k ≤ N n<k\le N n < k ≤ N φ k \varphi_k φ k t k ≥ ∣ P k ∣ t_k\ge|P_k| t k ≥ ∣ P k ∣ F ( x ) F(x) F ( x ) T : = ∑ k = n + 1 N t k T:=\sum_{k=n+1}^Nt_k T := ∑ k = n + 1 N t k C ≥ 1 C\ge1 C ≥ 1 k k k ( v j ( x ) ) j ∈ P k (v_j(x))_{j\in P_k} ( v j ( x ) ) j ∈ P k v k ( x ) v_k(x) v k ( x ) c k j ( x ) c_{kj}(x) c k j ( x ) j ∈ P k j\in P_k j ∈ P k C t k Ct_k C t k
一つの方向x ˙ ∈ R n \dot x\in\R^n x ˙ ∈ R n ( C + 2 ) T (C+2)T ( C + 2 ) T
一つの重みy ˉ ∈ R m \bar y\in\R^m y ˉ ∈ R m ( C + 2 ) T (C+2)T ( C + 2 ) T m = 1 m=1 m = 1 ∇ F ( x ) \nabla F(x) ∇ F ( x ) ( C + 2 ) T (C+2)T ( C + 2 ) T
すべてのv k ( x ) v_k(x) v k ( x ) c k j ( x ) c_{kj}(x) c k j ( x ) x ˙ = e 1 , … , e n \dot x=e_1,\dots,e_n x ˙ = e 1 , … , e n v ˙ \dot v v ˙ D F ( x ) DF(x) D F ( x ) ( C + 2 n ) T (C+2n)T ( C + 2 n ) T y ˉ = e 1 , … , e m \bar y=e_1,\dots,e_m y ˉ = e 1 , … , e m v ˉ \bar v v ˉ D F ( x ) DF(x) D F ( x ) ( C + 2 m ) T (C+2m)T ( C + 2 m ) T
証明. すべてのv k ( x ) v_k(x) v k ( x ) c k j ( x ) c_{kj}(x) c k j ( x ) ∑ k C t k = C T \sum_kCt_k=CT ∑ k C t k = C T
v ˙ i = x ˙ i \dot v_i=\dot x_i v ˙ i = x ˙ i i ≤ n i\le n i ≤ n v ˙ k \dot v_k v ˙ k n < k ≤ N n<k\le N n < k ≤ N ∣ P k ∣ |P_k| ∣ P k ∣ ∣ P k ∣ − 1 |P_k|-1 ∣ P k ∣ − 1 v ˙ n + 1 , … , v ˙ N \dot v_{n+1},\dots,\dot v_N v ˙ n + 1 , … , v ˙ N 2 ∑ k ∣ P k ∣ ≤ 2 T 2\sum_k|P_k|\le2T 2 ∑ k ∣ P k ∣ ≤ 2 T (1) は示された。
o 1 , … , o m o_1,\dots,o_m o 1 , … , o m σ j \sigma_j σ j y ˉ \bar y y ˉ 0 0 0 v ˉ j \bar v_j v ˉ j ∣ S j ∣ |S_j| ∣ S j ∣ ∣ S j ∣ |S_j| ∣ S j ∣ ∑ j = 1 N ∣ S j ∣ \sum_{j=1}^N|S_j| ∑ j = 1 N ∣ S j ∣ ∑ k = n + 1 N ∣ P k ∣ \sum_{k=n+1}^N|P_k| ∑ k = n + 1 N ∣ P k ∣ j ∈ P k j\in P_k j ∈ P k ( j , k ) (j,k) ( j , k ) v ˉ 1 , … , v ˉ N \bar v_1,\dots,\bar v_N v ˉ 1 , … , v ˉ N 2 ∑ k ∣ P k ∣ ≤ 2 T 2\sum_k|P_k|\le2T 2 ∑ k ∣ P k ∣ ≤ 2 T 定理 3.2 によりm = 1 m=1 m = 1 y ˉ = 1 \bar y=1 y ˉ = 1 ∇ F ( x ) \nabla F(x) ∇ F ( x ) (2) は示された。
定理 2.2 により方向e l e_l e l D F ( x ) e l DF(x)e_l D F ( x ) e l D F ( x ) DF(x) D F ( x ) l l l 定理 3.2 により重みe i e_i e i D F ( x ) T e i DF(x)^{\mathsf T}e_i D F ( x ) T e i D F ( x ) DF(x) D F ( x ) i i i v ˙ \dot v v ˙ n n n v ˉ \bar v v ˉ m m m 2 n T 2nT 2 n T 2 m T 2mT 2 m T (3) が従う。▨
5 陰関数定理による感度 命題 5.1. k , q ∈ N ≥ 1 k,q\in\NN k , q ∈ N ≥ 1 Q ⊆ R k × R q Q\subseteq\R^k\times\R^q Q ⊆ R k × R q G : Q → R k G\colon Q\to\R^k G : Q → R k C 1 C^1 C 1 ( w , p ) ∈ Q (w,p)\in Q ( w , p ) ∈ Q D u G ( w , p ) ∈ R k × k D_uG(w,p)\in\R^{k\times k} D u G ( w , p ) ∈ R k × k D p G ( w , p ) ∈ R k × q D_pG(w,p)\in\R^{k\times q} D p G ( w , p ) ∈ R k × q h ∈ R k h\in\R^k h ∈ R k r ∈ R q r\in\R^q r ∈ R q D u G ( w , p ) h = D G ( w , p ) ( h , 0 ) D_uG(w,p)h=DG(w,p)(h,0) D u G ( w , p ) h = D G ( w , p ) ( h , 0 ) D p G ( w , p ) r = D G ( w , p ) ( 0 , r ) D_pG(w,p)r=DG(w,p)(0,r) D p G ( w , p ) r = D G ( w , p ) ( 0 , r ) ( u 0 , p 0 ) ∈ Q (u_0,p_0)\in Q ( u 0 , p 0 ) ∈ Q G ( u 0 , p 0 ) = 0 G(u_0,p_0)=0 G ( u 0 , p 0 ) = 0 D u G ( u 0 , p 0 ) D_uG(u_0,p_0) D u G ( u 0 , p 0 )
p 0 p_0 p 0 V ⊆ R q V\subseteq\R^q V ⊆ R q u 0 u_0 u 0 B ⊆ R k B\subseteq\R^k B ⊆ R k C 1 C^1 C 1 u : V → B u\colon V\to B u : V → B u ( p 0 ) = u 0 u(p_0)=u_0 u ( p 0 ) = u 0 p ∈ V p\in V p ∈ V G ( u ( p ) , p ) = 0 G(u(p),p)=0 G ( u ( p ) , p ) = 0 ( w , p ) ∈ Q (w,p)\in Q ( w , p ) ∈ Q w ∈ B w\in B w ∈ B p ∈ V p\in V p ∈ V G ( w , p ) = 0 G(w,p)=0 G ( w , p ) = 0 w = u ( p ) w=u(p) w = u ( p ) (1) のV V V u u u p ∈ V p\in V p ∈ V D u G ( u ( p ) , p ) D_uG(u(p),p) D u G ( u ( p ) , p ) p ˙ ∈ R q \dot p\in\R^q p ˙ ∈ R q u ˙ : = D u ( p ) p ˙ \dot u:=Du(p)\dot p u ˙ := D u ( p ) p ˙ D u G ( u ( p ) , p ) u ˙ = − D p G ( u ( p ) , p ) p ˙ D_uG(u(p),p)\,\dot u=-D_pG(u(p),p)\,\dot p D u G ( u ( p ) , p ) u ˙ = − D p G ( u ( p ) , p ) p ˙ 証明. 開集合Q ′ : = { ( p , w ) ∣ ( w , p ) ∈ Q } Q':=\{(p,w)\mid(w,p)\in Q\} Q ′ := {( p , w ) ∣ ( w , p ) ∈ Q } C 1 C^1 C 1 F ( p , w ) : = G ( w , p ) F(p,w):=G(w,p) F ( p , w ) := G ( w , p ) D p G ( w , p ) D_pG(w,p) D p G ( w , p ) D u G ( w , p ) D_uG(w,p) D u G ( w , p ) F ( p 0 , u 0 ) = 0 F(p_0,u_0)=0 F ( p 0 , u 0 ) = 0 D u G ( u 0 , p 0 ) D_uG(u_0,p_0) D u G ( u 0 , p 0 ) §E4.8 定理 2.1 (2) をn = q n=q n = q m = k m=k m = k ( a , b ) = ( p 0 , u 0 ) (a,b)=(p_0,u_0) ( a , b ) = ( p 0 , u 0 ) p 0 p_0 p 0 V V V u 0 u_0 u 0 B B B C 1 C^1 C 1 u : V → B u\colon V\to B u : V → B ( p , w ) ∈ V × B (p,w)\in V\times B ( p , w ) ∈ V × B F ( p , w ) = 0 F(p,w)=0 F ( p , w ) = 0 w = u ( p ) w=u(p) w = u ( p ) u ( p 0 ) = u 0 u(p_0)=u_0 u ( p 0 ) = u 0 p ∈ V p\in V p ∈ V D u G ( u ( p ) , p ) D_uG(u(p),p) D u G ( u ( p ) , p )
D u ( p ) = − D u G ( u ( p ) , p ) − 1 D p G ( u ( p ) , p ) Du(p)=-D_uG(u(p),p)^{-1}D_pG(u(p),p) D u ( p ) = − D u G ( u ( p ) , p ) − 1 D p G ( u ( p ) , p ) が成り立つ。同値性をw = u ( p ) w=u(p) w = u ( p ) G ( u ( p ) , p ) = 0 G(u(p),p)=0 G ( u ( p ) , p ) = 0 (1) は示された。D u ( p ) Du(p) D u ( p ) D u G ( u ( p ) , p ) D_uG(u(p),p) D u G ( u ( p ) , p ) u ˙ = D u ( p ) p ˙ \dot u=Du(p)\dot p u ˙ = D u ( p ) p ˙ ▨
系 5.2. k , q ∈ N ≥ 1 k,q\in\NN k , q ∈ N ≥ 1 P ⊆ R q P\subseteq\R^q P ⊆ R q A : P → R k × k A\colon P\to\R^{k\times k} A : P → R k × k b : P → R k b\colon P\to\R^k b : P → R k C 1 C^1 C 1 P 0 : = { p ∈ P ∣ A ( p ) は正則 } P_0:=\{p\in P\mid A(p)\text{ は正則}\} P 0 := { p ∈ P ∣ A ( p ) は正則 } u ( p ) : = A ( p ) − 1 b ( p ) u(p):=A(p)^{-1}b(p) u ( p ) := A ( p ) − 1 b ( p ) u : P 0 → R k u\colon P_0\to\R^k u : P 0 → R k C 1 C^1 C 1 p ∈ P 0 p\in P_0 p ∈ P 0 p ˙ ∈ R q \dot p\in\R^q p ˙ ∈ R q
D u ( p ) p ˙ = A ( p ) − 1 ( D b ( p ) p ˙ − ( D A ( p ) p ˙ ) u ( p ) ) Du(p)\dot p=A(p)^{-1}\bigl(Db(p)\dot p-(DA(p)\dot p)\,u(p)\bigr) D u ( p ) p ˙ = A ( p ) − 1 ( D b ( p ) p ˙ − ( D A ( p ) p ˙ ) u ( p ) ) が成り立つ。ここで∂ l A ( p ) \partial_lA(p) ∂ l A ( p ) A A A p l p_l p l D A ( p ) p ˙ : = ∑ l = 1 q p ˙ l ∂ l A ( p ) DA(p)\dot p:=\sum_{l=1}^q\dot p_l\,\partial_lA(p) D A ( p ) p ˙ := ∑ l = 1 q p ˙ l ∂ l A ( p )
命題 5.3. k k k q q q Q Q Q G G G ( u 0 , p 0 ) (u_0,p_0) ( u 0 , p 0 ) 命題 5.1 のとおりとし、同命題のV V V B B B u u u J : Q → R J\colon Q\to\R J : Q → R C 1 C^1 C 1 j : V → R j\colon V\to\R j : V → R j ( p ) : = J ( u ( p ) , p ) j(p):=J(u(p),p) j ( p ) := J ( u ( p ) , p ) p ∈ V p\in V p ∈ V ∇ J ( u ( p ) , p ) ∈ R k × R q \nabla J(u(p),p)\in\R^k\times\R^q ∇ J ( u ( p ) , p ) ∈ R k × R q k k k ∇ u J ( u ( p ) , p ) \nabla_uJ(u(p),p) ∇ u J ( u ( p ) , p ) q q q ∇ p J ( u ( p ) , p ) \nabla_pJ(u(p),p) ∇ p J ( u ( p ) , p )
D u G ( u ( p ) , p ) T λ = ∇ u J ( u ( p ) , p ) D_uG(u(p),p)^{\mathsf T}\lambda=\nabla_uJ(u(p),p) D u G ( u ( p ) , p ) T λ = ∇ u J ( u ( p ) , p ) はただ一つの解λ ∈ R k \lambda\in\R^k λ ∈ R k j j j p p p
∇ j ( p ) = ∇ p J ( u ( p ) , p ) − D p G ( u ( p ) , p ) T λ \nabla j(p)=\nabla_pJ(u(p),p)-D_pG(u(p),p)^{\mathsf T}\lambda ∇ j ( p ) = ∇ p J ( u ( p ) , p ) − D p G ( u ( p ) , p ) T λ が成り立つ。
証明. p ∈ V p\in V p ∈ V M : = D u G ( u ( p ) , p ) M:=D_uG(u(p),p) M := D u G ( u ( p ) , p ) E : = D p G ( u ( p ) , p ) E:=D_pG(u(p),p) E := D p G ( u ( p ) , p ) 命題 5.1 (2) によりM M M M T M^{\mathsf T} M T λ \lambda λ ι : V → Q \iota\colon V\to Q ι : V → Q ι ( p ′ ) : = ( u ( p ′ ) , p ′ ) \iota(p'):=(u(p'),p') ι ( p ′ ) := ( u ( p ′ ) , p ′ ) ι \iota ι C 1 C^1 C 1 j = J ∘ ι j=J\circ\iota j = J ∘ ι §E4.3 定理 1.1 によりj j j p p p p ˙ ∈ R q \dot p\in\R^q p ˙ ∈ R q u ˙ : = D u ( p ) p ˙ \dot u:=Du(p)\dot p u ˙ := D u ( p ) p ˙ §E4.3 定理 3.2 から
D j ( p ) p ˙ = D J ( ι ( p ) ) ( u ˙ , p ˙ ) = ⟨ ∇ u J ( u ( p ) , p ) , u ˙ ⟩ + ⟨ ∇ p J ( u ( p ) , p ) , p ˙ ⟩ Dj(p)\dot p=DJ(\iota(p))(\dot u,\dot p)=\langle\nabla_uJ(u(p),p),\dot u\rangle+\langle\nabla_pJ(u(p),p),\dot p\rangle D j ( p ) p ˙ = D J ( ι ( p )) ( u ˙ , p ˙ ) = ⟨ ∇ u J ( u ( p ) , p ) , u ˙ ⟩ + ⟨ ∇ p J ( u ( p ) , p ) , p ˙ ⟩ である。命題 5.1 (2) によりM u ˙ = − E p ˙ M\dot u=-E\dot p M u ˙ = − E p ˙
⟨ ∇ u J ( u ( p ) , p ) , u ˙ ⟩ = ⟨ M T λ , u ˙ ⟩ = ⟨ λ , M u ˙ ⟩ = − ⟨ λ , E p ˙ ⟩ = − ⟨ E T λ , p ˙ ⟩ \langle\nabla_uJ(u(p),p),\dot u\rangle=\langle M^{\mathsf T}\lambda,\dot u\rangle=\langle\lambda,M\dot u\rangle=-\langle\lambda,E\dot p\rangle=-\langle E^{\mathsf T}\lambda,\dot p\rangle ⟨ ∇ u J ( u ( p ) , p ) , u ˙ ⟩ = ⟨ M T λ , u ˙ ⟩ = ⟨ λ , M u ˙ ⟩ = − ⟨ λ , E p ˙ ⟩ = − ⟨ E T λ , p ˙ ⟩ であり、任意のp ˙ \dot p p ˙ D j ( p ) p ˙ = ⟨ ∇ p J ( u ( p ) , p ) − E T λ , p ˙ ⟩ Dj(p)\dot p=\langle\nabla_pJ(u(p),p)-E^{\mathsf T}\lambda,\dot p\rangle D j ( p ) p ˙ = ⟨ ∇ p J ( u ( p ) , p ) − E T λ , p ˙ ⟩ §E4.3 定理 3.2 の勾配の一意性により∇ j ( p ) = ∇ p J ( u ( p ) , p ) − E T λ \nabla j(p)=\nabla_pJ(u(p),p)-E^{\mathsf T}\lambda ∇ j ( p ) = ∇ p J ( u ( p ) , p ) − E T λ ▨
6 反復の微分 命題 6.1. k , q ∈ N ≥ 1 k,q\in\NN k , q ∈ N ≥ 1 Q ⊆ R k × R q Q\subseteq\R^k\times\R^q Q ⊆ R k × R q φ : Q → R k \varphi\colon Q\to\R^k φ : Q → R k C 1 C^1 C 1 w 0 ∈ R k w_0\in\R^k w 0 ∈ R k D u φ D_u\varphi D u φ D p φ D_p\varphi D p φ 命題 5.1 のD u G D_uG D u G D p G D_pG D p G A j ⊆ R q A_j\subseteq\R^q A j ⊆ R q u j : A j → R k u_j\colon A_j\to\R^k u j : A j → R k A 0 : = R q A_0:=\R^q A 0 := R q u 0 ( p ) : = w 0 u_0(p):=w_0 u 0 ( p ) := w 0
A j + 1 : = { p ∈ A j ∣ ( u j ( p ) , p ) ∈ Q } , u j + 1 ( p ) : = φ ( u j ( p ) , p ) ( p ∈ A j + 1 ) A_{j+1}:=\{p\in A_j\mid(u_j(p),p)\in Q\},\qquad u_{j+1}(p):=\varphi(u_j(p),p)\quad(p\in A_{j+1}) A j + 1 := { p ∈ A j ∣ ( u j ( p ) , p ) ∈ Q } , u j + 1 ( p ) := φ ( u j ( p ) , p ) ( p ∈ A j + 1 ) により定める。
各A j A_j A j u j u_j u j A j A_j A j C 1 C^1 C 1 S j ( p ) : = D u j ( p ) ∈ R k × q S_j(p):=Du_j(p)\in\R^{k\times q} S j ( p ) := D u j ( p ) ∈ R k × q S 0 ( p ) = 0 S_0(p)=0 S 0 ( p ) = 0 p ∈ A j + 1 p\in A_{j+1} p ∈ A j + 1 S j + 1 ( p ) = D u φ ( u j ( p ) , p ) S j ( p ) + D p φ ( u j ( p ) , p ) S_{j+1}(p)=D_u\varphi(u_j(p),p)\,S_j(p)+D_p\varphi(u_j(p),p) S j + 1 ( p ) = D u φ ( u j ( p ) , p ) S j ( p ) + D p φ ( u j ( p ) , p )
p ∈ ⋂ j A j p\in\bigcap_jA_j p ∈ ⋂ j A j u j ( p ) u_j(p) u j ( p ) u ∗ u^* u ∗ ( u ∗ , p ) ∈ Q (u^*,p)\in Q ( u ∗ , p ) ∈ Q S j ( p ) S_j(p) S j ( p ) S ∈ R k × q S\in\R^{k\times q} S ∈ R k × q u ∗ = φ ( u ∗ , p ) u^*=\varphi(u^*,p) u ∗ = φ ( u ∗ , p ) ( I k − D u φ ( u ∗ , p ) ) S = D p φ ( u ∗ , p ) (I_k-D_u\varphi(u^*,p))S=D_p\varphi(u^*,p) ( I k − D u φ ( u ∗ , p )) S = D p φ ( u ∗ , p ) (2) の仮定に加えてI k − D u φ ( u ∗ , p ) I_k-D_u\varphi(u^*,p) I k − D u φ ( u ∗ , p ) p p p V V V u ∗ u^* u ∗ B B B C 1 C^1 C 1 u ~ : V → B \tilde u\colon V\to B u ~ : V → B u ~ ( p ) = u ∗ \tilde u(p)=u^* u ~ ( p ) = u ∗ p ′ ∈ V p'\in V p ′ ∈ V u ~ ( p ′ ) = φ ( u ~ ( p ′ ) , p ′ ) \tilde u(p')=\varphi(\tilde u(p'),p') u ~ ( p ′ ) = φ ( u ~ ( p ′ ) , p ′ ) ( w , p ′ ) ∈ Q (w,p')\in Q ( w , p ′ ) ∈ Q w ∈ B w\in B w ∈ B p ′ ∈ V p'\in V p ′ ∈ V w = φ ( w , p ′ ) w=\varphi(w,p') w = φ ( w , p ′ ) w = u ~ ( p ′ ) w=\tilde u(p') w = u ~ ( p ′ ) S = D u ~ ( p ) S=D\tilde u(p) S = D u ~ ( p ) 証明. (1) を示す。u 0 u_0 u 0 C 1 C^1 C 1 S 0 = 0 S_0=0 S 0 = 0 A j A_j A j u j u_j u j A j A_j A j C 1 C^1 C 1 ι j ( p ) : = ( u j ( p ) , p ) \iota_j(p):=(u_j(p),p) ι j ( p ) := ( u j ( p ) , p ) ι j : A j → R k × R q \iota_j\colon A_j\to\R^k\times\R^q ι j : A j → R k × R q C 1 C^1 C 1 A j + 1 = ι j − 1 ( Q ) A_{j+1}=\iota_j^{-1}(Q) A j + 1 = ι j − 1 ( Q ) u j + 1 = φ ∘ ι j u_{j+1}=\varphi\circ\iota_j u j + 1 = φ ∘ ι j §E4.3 定理 1.1 によりu j + 1 u_{j+1} u j + 1 A j + 1 A_{j+1} A j + 1 p ˙ ∈ R q \dot p\in\R^q p ˙ ∈ R q
D u j + 1 ( p ) p ˙ = D φ ( ι j ( p ) ) ( S j ( p ) p ˙ , p ˙ ) = D u φ ( u j ( p ) , p ) S j ( p ) p ˙ + D p φ ( u j ( p ) , p ) p ˙ Du_{j+1}(p)\dot p=D\varphi(\iota_j(p))(S_j(p)\dot p,\dot p)=D_u\varphi(u_j(p),p)\,S_j(p)\dot p+D_p\varphi(u_j(p),p)\,\dot p D u j + 1 ( p ) p ˙ = D φ ( ι j ( p )) ( S j ( p ) p ˙ , p ˙ ) = D u φ ( u j ( p ) , p ) S j ( p ) p ˙ + D p φ ( u j ( p ) , p ) p ˙ である。右辺の係数はp p p u j + 1 u_{j+1} u j + 1 C 1 C^1 C 1
(2) を示す。φ \varphi φ D u φ D_u\varphi D u φ D p φ D_p\varphi D p φ ( u ∗ , p ) ∈ Q (u^*,p)\in Q ( u ∗ , p ) ∈ Q u j + 1 ( p ) = φ ( u j ( p ) , p ) u_{j+1}(p)=\varphi(u_j(p),p) u j + 1 ( p ) = φ ( u j ( p ) , p ) j → ∞ j\to\infty j → ∞ u ∗ = φ ( u ∗ , p ) u^*=\varphi(u^*,p) u ∗ = φ ( u ∗ , p ) (1) の漸化式でj → ∞ j\to\infty j → ∞ S = D u φ ( u ∗ , p ) S + D p φ ( u ∗ , p ) S=D_u\varphi(u^*,p)S+D_p\varphi(u^*,p) S = D u φ ( u ∗ , p ) S + D p φ ( u ∗ , p )
(3) を示す。G ( w , p ′ ) : = w − φ ( w , p ′ ) G(w,p'):=w-\varphi(w,p') G ( w , p ′ ) := w − φ ( w , p ′ ) G : Q → R k G\colon Q\to\R^k G : Q → R k C 1 C^1 C 1 D u G = I k − D u φ D_uG=I_k-D_u\varphi D u G = I k − D u φ D p G = − D p φ D_pG=-D_p\varphi D p G = − D p φ (2) によりG ( u ∗ , p ) = 0 G(u^*,p)=0 G ( u ∗ , p ) = 0 D u G ( u ∗ , p ) D_uG(u^*,p) D u G ( u ∗ , p ) 命題 5.1 を( u 0 , p 0 ) = ( u ∗ , p ) (u_0,p_0)=(u^*,p) ( u 0 , p 0 ) = ( u ∗ , p ) V V V B B B u ~ \tilde u u ~
D u ~ ( p ) = ( I k − D u φ ( u ∗ , p ) ) − 1 D p φ ( u ∗ , p ) D\tilde u(p)=\bigl(I_k-D_u\varphi(u^*,p)\bigr)^{-1}D_p\varphi(u^*,p) D u ~ ( p ) = ( I k − D u φ ( u ∗ , p ) ) − 1 D p φ ( u ∗ , p ) である。(2) の等式の両辺に左から( I k − D u φ ( u ∗ , p ) ) − 1 (I_k-D_u\varphi(u^*,p))^{-1} ( I k − D u φ ( u ∗ , p ) ) − 1 S S S ▨
例 6.2. k = q = 1 k=q=1 k = q = 1 Q = ( 0 , ∞ ) × R Q=(0,\infty)\times\R Q = ( 0 , ∞ ) × R φ ( w , p ) = 1 2 ( w + p w ) \varphi(w,p)=\frac12\bigl(w+\frac pw\bigr) φ ( w , p ) = 2 1 ( w + w p ) w 0 = 1 w_0=1 w 0 = 1 命題 6.1 のu j u_j u j S j S_j S j u j + 1 ( p ) = φ ( u j ( p ) , p ) u_{j+1}(p)=\varphi(u_j(p),p) u j + 1 ( p ) = φ ( u j ( p ) , p ) w 2 = p w^2=p w 2 = p D u φ ( w , p ) = 1 2 ( 1 − p w 2 ) D_u\varphi(w,p)=\frac12\bigl(1-\frac p{w^2}\bigr) D u φ ( w , p ) = 2 1 ( 1 − w 2 p ) D p φ ( w , p ) = 1 2 w D_p\varphi(w,p)=\frac1{2w} D p φ ( w , p ) = 2 w 1
S j + 1 ( p ) = 1 2 ( 1 − p u j ( p ) 2 ) S j ( p ) + 1 2 u j ( p ) , S 0 ( p ) = 0 S_{j+1}(p)=\frac12\Bigl(1-\frac p{u_j(p)^2}\Bigr)S_j(p)+\frac1{2u_j(p)},\qquad S_0(p)=0 S j + 1 ( p ) = 2 1 ( 1 − u j ( p ) 2 p ) S j ( p ) + 2 u j ( p ) 1 , S 0 ( p ) = 0 である。u 0 ( p ) = 1 > 0 u_0(p)=1>0 u 0 ( p ) = 1 > 0 w > 0 w>0 w > 0 p > 0 p>0 p > 0 φ ( w , p ) > 0 \varphi(w,p)>0 φ ( w , p ) > 0 u j ( 4 ) > 0 u_j(4)>0 u j ( 4 ) > 0 4 ∈ ⋂ j A j 4\in\bigcap_jA_j 4 ∈ ⋂ j A j p = 4 p=4 p = 4
j 1 2 3 u j ( 4 ) 5 2 41 20 3281 1640 S j ( 4 ) 1 2 29 100 84349 336200 \begin{array}{c|ccc}
j&1&2&3\\\hline
u_j(4)&\dfrac52&\dfrac{41}{20}&\dfrac{3281}{1640}\\[2mm]
S_j(4)&\dfrac12&\dfrac{29}{100}&\dfrac{84349}{336200}
\end{array} j u j ( 4 ) S j ( 4 ) 1 2 5 2 1 2 20 41 100 29 3 1640 3281 336200 84349 p > 0 p>0 p > 0 w > 0 w>0 w > 0 w = φ ( w , p ) w=\varphi(w,p) w = φ ( w , p ) w 2 = p w^2=p w 2 = p G ( w , p ) : = w 2 − p G(w,p):=w^2-p G ( w , p ) := w 2 − p ( w , p ) ∈ Q (w,p)\in Q ( w , p ) ∈ Q G ( 2 , 4 ) = 0 G(2,4)=0 G ( 2 , 4 ) = 0 D u G ( 2 , 4 ) = 4 D_uG(2,4)=4 D u G ( 2 , 4 ) = 4 D p G ( 2 , 4 ) = − 1 D_pG(2,4)=-1 D p G ( 2 , 4 ) = − 1 命題 5.1 を( u 0 , p 0 ) = ( 2 , 4 ) (u_0,p_0)=(2,4) ( u 0 , p 0 ) = ( 2 , 4 ) u ~ : V → B \tilde u\colon V\to B u ~ : V → B p ′ ∈ V p'\in V p ′ ∈ V ( u ~ ( p ′ ) , p ′ ) ∈ Q (\tilde u(p'),p')\in Q ( u ~ ( p ′ ) , p ′ ) ∈ Q u ~ ( p ′ ) 2 = p ′ \tilde u(p')^2=p' u ~ ( p ′ ) 2 = p ′ V ⊆ ( 0 , ∞ ) V\subseteq(0,\infty) V ⊆ ( 0 , ∞ ) V V V u ~ ( p ′ ) = p ′ \tilde u(p')=\sqrt{p'} u ~ ( p ′ ) = p ′ 命題 5.1 (2) の一次方程式4 u ~ ′ ( 4 ) = 1 4\,\tilde u'(4)=1 4 u ~ ′ ( 4 ) = 1 u ~ ′ ( 4 ) = 1 4 \tilde u'(4)=\frac14 u ~ ′ ( 4 ) = 4 1 S j ( 4 ) S_j(4) S j ( 4 ) j j j u j u_j u j p p p S 2 ( 4 ) − 1 4 = 1 25 S_2(4)-\frac14=\frac1{25} S 2 ( 4 ) − 4 1 = 25 1 S 3 ( 4 ) − 1 4 = 299 336200 ≈ 8.89 × 10 − 4 S_3(4)-\frac14=\frac{299}{336200}\approx8.89\times10^{-4} S 3 ( 4 ) − 4 1 = 336200 299 ≈ 8.89 × 1 0 − 4 0 0 0 j j j u 2 ( 4 ) − 2 = 1 20 u_2(4)-2=\frac1{20} u 2 ( 4 ) − 2 = 20 1 u 3 ( 4 ) − 2 = 1 1640 ≈ 6.10 × 10 − 4 u_3(4)-2=\frac1{1640}\approx6.10\times10^{-4} u 3 ( 4 ) − 2 = 1640 1 ≈ 6.10 × 1 0 − 4 j = 3 j=3 j = 3 u j ( 4 ) u_j(4) u j ( 4 ) u ∗ u^* u ∗ S j ( 4 ) S_j(4) S j ( 4 ) 命題 6.1 (2) によりu ∗ = φ ( u ∗ , 4 ) u^*=\varphi(u^*,4) u ∗ = φ ( u ∗ , 4 ) u ∗ = 2 u^*=2 u ∗ = 2 D u φ ( 2 , 4 ) = 0 D_u\varphi(2,4)=0 D u φ ( 2 , 4 ) = 0 D p φ ( 2 , 4 ) = 1 4 D_p\varphi(2,4)=\frac14 D p φ ( 2 , 4 ) = 4 1 S j ( 4 ) S_j(4) S j ( 4 ) 1 4 = u ~ ′ ( 4 ) \frac14=\tilde u'(4) 4 1 = u ~ ′ ( 4 )
例 6.3. k = q = 1 k=q=1 k = q = 1 Q = R × R Q=\R\times\R Q = R × R φ ( w , p ) = w − w 3 + p \varphi(w,p)=w-w^3+p φ ( w , p ) = w − w 3 + p w 0 = 1 2 w_0=\frac12 w 0 = 2 1 命題 6.1 のu j u_j u j S j S_j S j p = 0 p=0 p = 0 A j = R A_j=\R A j = R u j : = u j ( 0 ) u_j:=u_j(0) u j := u j ( 0 ) S j : = S j ( 0 ) S_j:=S_j(0) S j := S j ( 0 )
u j + 1 = u j − u j 3 , S j + 1 = ( 1 − 3 u j 2 ) S j + 1 , u 0 = 1 2 , S 0 = 0 u_{j+1}=u_j-u_j^3,\qquad S_{j+1}=(1-3u_j^2)S_j+1,\qquad u_0=\frac12,\ S_0=0 u j + 1 = u j − u j 3 , S j + 1 = ( 1 − 3 u j 2 ) S j + 1 , u 0 = 2 1 , S 0 = 0 である。
0 < u j ≤ 1 2 0<u_j\le\frac12 0 < u j ≤ 2 1 u j + 1 = u j ( 1 − u j 2 ) ∈ ( 0 , u j ) u_{j+1}=u_j(1-u_j^2)\in(0,u_j) u j + 1 = u j ( 1 − u j 2 ) ∈ ( 0 , u j ) j j j 0 < u j ≤ 1 2 0<u_j\le\frac12 0 < u j ≤ 2 1 s ∈ [ 0 , 1 ) s\in[0,1) s ∈ [ 0 , 1 ) ( 1 + 2 s ) ( 1 − s ) 2 = 1 − 3 s 2 + 2 s 3 ≤ 1 (1+2s)(1-s)^2=1-3s^2+2s^3\le1 ( 1 + 2 s ) ( 1 − s ) 2 = 1 − 3 s 2 + 2 s 3 ≤ 1 s = u j 2 s=u_j^2 s = u j 2 1 u j + 1 2 = 1 u j 2 ( 1 − u j 2 ) 2 ≥ 1 + 2 u j 2 u j 2 = 1 u j 2 + 2 \frac1{u_{j+1}^2}=\frac1{u_j^2(1-u_j^2)^2}\ge\frac{1+2u_j^2}{u_j^2}=\frac1{u_j^2}+2 u j + 1 2 1 = u j 2 ( 1 − u j 2 ) 2 1 ≥ u j 2 1 + 2 u j 2 = u j 2 1 + 2 u j 2 ≤ 1 2 j + 4 u_j^2\le\frac1{2j+4} u j 2 ≤ 2 j + 4 1 u j → 0 u_j\to0 u j → 0 0 0 0 φ ( ⋅ , 0 ) \varphi(\cdot,0) φ ( ⋅ , 0 ) S 1 = 1 S_1=1 S 1 = 1 j ≥ 1 j\ge1 j ≥ 1 S j ≥ j + 2 3 S_j\ge\frac{j+2}3 S j ≥ 3 j + 2 1 − 3 u j 2 ≥ 1 − 3 2 j + 4 ≥ 0 1-3u_j^2\ge1-\frac3{2j+4}\ge0 1 − 3 u j 2 ≥ 1 − 2 j + 4 3 ≥ 0 S j ≥ 0 S_j\ge0 S j ≥ 0 S j + 1 ≥ ( 1 − 3 2 j + 4 ) j + 2 3 + 1 = j + 2 3 + 1 2 ≥ j + 3 3 S_{j+1}\ge\Bigl(1-\frac3{2j+4}\Bigr)\frac{j+2}3+1=\frac{j+2}3+\frac12\ge\frac{j+3}3 S j + 1 ≥ ( 1 − 2 j + 4 3 ) 3 j + 2 + 1 = 3 j + 2 + 2 1 ≥ 3 j + 3 j ≥ 1 j\ge1 j ≥ 1 S j ≥ j + 2 3 S_j\ge\frac{j+2}3 S j ≥ 3 j + 2 S j S_j S j I 1 − D u φ ( 0 , 0 ) = 3 ⋅ 0 2 = 0 I_1-D_u\varphi(0,0)=3\cdot0^2=0 I 1 − D u φ ( 0 , 0 ) = 3 ⋅ 0 2 = 0 p ∈ R p\in\R p ∈ R φ ( ⋅ , p ) \varphi(\cdot,p) φ ( ⋅ , p ) w 3 = p w^3=p w 3 = p p 1 / 3 p^{1/3} p 1/3 p ↦ p 1 / 3 p\mapsto p^{1/3} p ↦ p 1/3 p = 0 p=0 p = 0 反復u j u_j u j S j S_j S j 命題 6.1 (2) の仮定のうちS j ( p ) S_j(p) S j ( p ) u j ( p ) u_j(p) u j ( p )
7 有限差分との比較 例 7.2. t i : = i t_i:=i t i := i ( y 0 , y 1 , y 2 ) : = ( 1 , 1 2 , 1 4 ) (y_0,y_1,y_2):=(1,\frac12,\frac14) ( y 0 , y 1 , y 2 ) := ( 1 , 2 1 , 4 1 ) a e − b t a e^{-bt} a e − b t
L ( a , b ) : = 1 2 ∑ i = 0 2 ( a e − b t i − y i ) 2 L(a,b):=\frac12\sum_{i=0}^2\bigl(ae^{-bt_i}-y_i\bigr)^2 L ( a , b ) := 2 1 i = 0 ∑ 2 ( a e − b t i − y i ) 2 を考える。L L L R 2 \R^2 R 2 2 2 2 15 15 15 v 1 = a v_1=a v 1 = a v 2 = b v_2=b v 2 = b i i i e i = exp ( − t i v 2 ) e_i=\exp(-t_iv_2) e i = exp ( − t i v 2 ) z i = v 1 e i z_i=v_1e_i z i = v 1 e i r i = z i − y i r_i=z_i-y_i r i = z i − y i s i = 1 2 r i 2 s_i=\frac12r_i^2 s i = 2 1 r i 2 4 4 4 L = s 0 + s 1 + s 2 L=s_0+s_1+s_2 L = s 0 + s 1 + s 2 ∂ e i / ∂ v 2 = − t i e i \partial e_i/\partial v_2=-t_ie_i ∂ e i / ∂ v 2 = − t i e i ∂ z i / ∂ v 1 = e i \partial z_i/\partial v_1=e_i ∂ z i / ∂ v 1 = e i ∂ z i / ∂ e i = v 1 \partial z_i/\partial e_i=v_1 ∂ z i / ∂ e i = v 1 ∂ r i / ∂ z i = 1 \partial r_i/\partial z_i=1 ∂ r i / ∂ z i = 1 ∂ s i / ∂ r i = r i \partial s_i/\partial r_i=r_i ∂ s i / ∂ r i = r i ∂ L / ∂ s i = 1 \partial L/\partial s_i=1 ∂ L / ∂ s i = 1
重み1 1 1 s ˉ i = 1 \bar s_i=1 s ˉ i = 1 r ˉ i = z ˉ i = r i \bar r_i=\bar z_i=r_i r ˉ i = z ˉ i = r i e ˉ i = r i v 1 \bar e_i=r_iv_1 e ˉ i = r i v 1 1 1 1 z 0 , z 1 , z 2 z_0,z_1,z_2 z 0 , z 1 , z 2 2 2 2 e 0 , e 1 , e 2 e_0,e_1,e_2 e 0 , e 1 , e 2
v ˉ 1 = ∑ i = 0 2 r i e i , v ˉ 2 = − v 1 ∑ i = 0 2 t i r i e i \bar v_1=\sum_{i=0}^2r_ie_i,\qquad\bar v_2=-v_1\sum_{i=0}^2t_ir_ie_i v ˉ 1 = i = 0 ∑ 2 r i e i , v ˉ 2 = − v 1 i = 0 ∑ 2 t i r i e i を与える。方向( 0 , 1 ) (0,1) ( 0 , 1 ) e ˙ i = − t i e i \dot e_i=-t_ie_i e ˙ i = − t i e i z ˙ i = v 1 e ˙ i \dot z_i=v_1\dot e_i z ˙ i = v 1 e ˙ i r ˙ i = z ˙ i \dot r_i=\dot z_i r ˙ i = z ˙ i s ˙ i = r i r ˙ i \dot s_i=r_i\dot r_i s ˙ i = r i r ˙ i L ˙ = − v 1 ∑ i t i r i e i \dot L=-v_1\sum_it_ir_ie_i L ˙ = − v 1 ∑ i t i r i e i ∂ a L = ∑ i r i e − b t i \partial_aL=\sum_ir_ie^{-bt_i} ∂ a L = ∑ i r i e − b t i ∂ b L = − a ∑ i t i r i e − b t i \partial_bL=-a\sum_it_ir_ie^{-bt_i} ∂ b L = − a ∑ i t i r i e − b t i
( a , b ) = ( 1 , 1 2 ) (a,b)=(1,\frac12) ( a , b ) = ( 1 , 2 1 ) e 1 = 0.606530659712633 e_1=0.606530659712633 e 1 = 0.606530659712633 e 2 = 0.367879441171442 e_2=0.367879441171442 e 2 = 0.367879441171442 r 0 = 0 r_0=0 r 0 = 0 r 1 = 0.106530659712633 r_1=0.106530659712633 r 1 = 0.106530659712633 r 2 = 0.117879441171442 r_2=0.117879441171442 r 2 = 0.117879441171442 ∂ a L ( 1 , 1 2 ) = 0.107979534258878 \partial_aL(1,\frac12)=0.107979534258878 ∂ a L ( 1 , 2 1 ) = 0.107979534258878 ∂ b L ( 1 , 1 2 ) = − 0.151344957202630 \partial_bL(1,\frac12)=-0.151344957202630 ∂ b L ( 1 , 2 1 ) = − 0.151344957202630
g ( s ) : = L ( 1 , 1 2 + s ) g(s):=L(1,\frac12+s) g ( s ) := L ( 1 , 2 1 + s ) h = 2 − k h=2^{-k} h = 2 − k D h 0 g ( 0 ) D^0_hg(0) D h 0 g ( 0 ) ∂ b L ( 1 , 1 2 ) = g ′ ( 0 ) \partial_bL(1,\frac12)=g'(0) ∂ b L ( 1 , 2 1 ) = g ′ ( 0 ) g ′ ′ ′ ( 0 ) = − ∑ i t i 3 e i ( 4 e i − y i ) ≈ − 4.763 g'''(0)=-\sum_it_i^3e_i(4e_i-y_i)\approx-4.763 g ′′′ ( 0 ) = − ∑ i t i 3 e i ( 4 e i − y i ) ≈ − 4.763 i = 0 , 1 , 2 i=0,1,2 i = 0 , 1 , 2 g ( ± h ) g(\pm h) g ( ± h ) D h 0 g ( 0 ) D^0_hg(0) D h 0 g ( 0 )
k k k binary64 の誤差
厳密な差分商の誤差
h 2 6 g ′ ′ ′ ( 0 ) \frac{h^2}6g'''(0) 6 h 2 g ′′′ ( 0 )
4
− 3.110 × 10 − 3 -3.110\times10^{-3} − 3.110 × 1 0 − 3 − 3.110 × 10 − 3 -3.110\times10^{-3} − 3.110 × 1 0 − 3 − 3.101 × 10 − 3 -3.101\times10^{-3} − 3.101 × 1 0 − 3
8
− 1.211 × 10 − 5 -1.211\times10^{-5} − 1.211 × 1 0 − 5 − 1.211 × 10 − 5 -1.211\times10^{-5} − 1.211 × 1 0 − 5 − 1.211 × 10 − 5 -1.211\times10^{-5} − 1.211 × 1 0 − 5
12
− 4.732 × 10 − 8 -4.732\times10^{-8} − 4.732 × 1 0 − 8 − 4.732 × 10 − 8 -4.732\times10^{-8} − 4.732 × 1 0 − 8 − 4.732 × 10 − 8 -4.732\times10^{-8} − 4.732 × 1 0 − 8
16
− 1.845 × 10 − 10 -1.845\times10^{-10} − 1.845 × 1 0 − 10 − 1.848 × 10 − 10 -1.848\times10^{-10} − 1.848 × 1 0 − 10 − 1.848 × 10 − 10 -1.848\times10^{-10} − 1.848 × 1 0 − 10
20
5.026 × 10 − 13 5.026\times10^{-13} 5.026 × 1 0 − 13 − 7.220 × 10 − 13 -7.220\times10^{-13} − 7.220 × 1 0 − 13 − 7.220 × 10 − 13 -7.220\times10^{-13} − 7.220 × 1 0 − 13
24
3.779 × 10 − 11 3.779\times10^{-11} 3.779 × 1 0 − 11 − 2.820 × 10 − 15 -2.820\times10^{-15} − 2.820 × 1 0 − 15 − 2.820 × 10 − 15 -2.820\times10^{-15} − 2.820 × 1 0 − 15
28
− 1.257 × 10 − 9 -1.257\times10^{-9} − 1.257 × 1 0 − 9 − 1.102 × 10 − 17 -1.102\times10^{-17} − 1.102 × 1 0 − 17 − 1.102 × 10 − 17 -1.102\times10^{-17} − 1.102 × 1 0 − 17
32
− 1.490 × 10 − 9 -1.490\times10^{-9} − 1.490 × 1 0 − 9 − 4.304 × 10 − 20 -4.304\times10^{-20} − 4.304 × 1 0 − 20 − 4.304 × 10 − 20 -4.304\times10^{-20} − 4.304 × 1 0 − 20
36
2.235 × 10 − 9 2.235\times10^{-9} 2.235 × 1 0 − 9 − 1.681 × 10 − 22 -1.681\times10^{-22} − 1.681 × 1 0 − 22 − 1.681 × 10 − 22 -1.681\times10^{-22} − 1.681 × 1 0 − 22
40
− 3.157 × 10 − 6 -3.157\times10^{-6} − 3.157 × 1 0 − 6 − 6.567 × 10 − 25 -6.567\times10^{-25} − 6.567 × 1 0 − 25 − 6.567 × 10 − 25 -6.567\times10^{-25} − 6.567 × 1 0 − 25
厳密な差分商の誤差は§E20.19 定理 1.2 (2) によりh 2 6 g ′ ′ ′ ( ξ ) \frac{h^2}6g'''(\xi) 6 h 2 g ′′′ ( ξ ) ξ ∈ [ − h , h ] \xi\in[-h,h] ξ ∈ [ − h , h ] g ′ ′ ′ g''' g ′′′ h 2 6 g ′ ′ ′ ( 0 ) \frac{h^2}6g'''(0) 6 h 2 g ′′′ ( 0 ) h → 0 h\to0 h → 0 1 1 1 5 ≤ k ≤ 45 5\le k\le45 5 ≤ k ≤ 45 g ( ± h ) g(\pm h) g ( ± h ) 2 h 2h 2 h g ( ± h ) g(\pm h) g ( ± h ) §E20.19 命題 2.1 (1) によりg ( ± h ) g(\pm h) g ( ± h ) 1 h \frac1h h 1 1 ≤ k ≤ 45 1\le k\le45 1 ≤ k ≤ 45 k = 20 k=20 k = 20 5.03 × 10 − 13 5.03\times10^{-13} 5.03 × 1 0 − 13
同じ丸めの規則で前進モードと逆モードを binary64 で実行すると、得られた∂ a L \partial_aL ∂ a L ∂ b L \partial_bL ∂ b L 5.5 × 10 − 18 5.5\times10^{-18} 5.5 × 1 0 − 18 − 2.7 × 10 − 17 -2.7\times10^{-17} − 2.7 × 1 0 − 17
8 演習 解答. det A ( p ) \det A(p) det A ( p ) A ( p ) A(p) A ( p ) p p p P 0 = { p ∈ P ∣ det A ( p ) ≠ 0 } P_0=\{p\in P\mid\det A(p)\ne0\} P 0 = { p ∈ P ∣ det A ( p ) = 0 }
p 1 ∈ P 0 p_1\in P_0 p 1 ∈ P 0 G : R k × P → R k G\colon\R^k\times P\to\R^k G : R k × P → R k G ( w , p ) : = A ( p ) w − b ( p ) G(w,p):=A(p)w-b(p) G ( w , p ) := A ( p ) w − b ( p ) G G G C 1 C^1 C 1 G G G C 1 C^1 C 1 h ∈ R k h\in\R^k h ∈ R k p ˙ ∈ R q \dot p\in\R^q p ˙ ∈ R q
D u G ( w , p ) h = A ( p ) h , D p G ( w , p ) p ˙ = ( D A ( p ) p ˙ ) w − D b ( p ) p ˙ D_uG(w,p)h=A(p)h,\qquad D_pG(w,p)\dot p=(DA(p)\dot p)\,w-Db(p)\dot p D u G ( w , p ) h = A ( p ) h , D p G ( w , p ) p ˙ = ( D A ( p ) p ˙ ) w − D b ( p ) p ˙ である。G ( u ( p 1 ) , p 1 ) = 0 G(u(p_1),p_1)=0 G ( u ( p 1 ) , p 1 ) = 0 D u G ( u ( p 1 ) , p 1 ) = A ( p 1 ) D_uG(u(p_1),p_1)=A(p_1) D u G ( u ( p 1 ) , p 1 ) = A ( p 1 ) 命題 5.1 によりp 1 p_1 p 1 V V V C 1 C^1 C 1 u ~ : V → R k \tilde u\colon V\to\R^k u ~ : V → R k p ∈ V p\in V p ∈ V A ( p ) u ~ ( p ) = b ( p ) A(p)\tilde u(p)=b(p) A ( p ) u ~ ( p ) = b ( p ) A ( p ) A(p) A ( p ) A ( p ) A(p) A ( p ) A ( p ) w = b ( p ) A(p)w=b(p) A ( p ) w = b ( p ) A ( p ) − 1 b ( p ) A(p)^{-1}b(p) A ( p ) − 1 b ( p ) V ⊆ P 0 V\subseteq P_0 V ⊆ P 0 V V V u ~ = u \tilde u=u u ~ = u u u u p 1 p_1 p 1 C 1 C^1 C 1 命題 5.1 (2) により
A ( p 1 ) D u ( p 1 ) p ˙ = − ( D A ( p 1 ) p ˙ ) u ( p 1 ) + D b ( p 1 ) p ˙ A(p_1)\,Du(p_1)\dot p=-(DA(p_1)\dot p)\,u(p_1)+Db(p_1)\dot p A ( p 1 ) D u ( p 1 ) p ˙ = − ( D A ( p 1 ) p ˙ ) u ( p 1 ) + D b ( p 1 ) p ˙ であり、左からA ( p 1 ) − 1 A(p_1)^{-1} A ( p 1 ) − 1 p 1 ∈ P 0 p_1\in P_0 p 1 ∈ P 0 u u u P 0 P_0 P 0 C 1 C^1 C 1 ▨
問題 8.2. k k k q q q P P P A A A b b b P 0 P_0 P 0 u u u 系 5.2 のとおりとし、c ∈ R k c\in\R^k c ∈ R k j ( p ) : = c T u ( p ) j(p):=c^{\mathsf T}u(p) j ( p ) := c T u ( p ) p ∈ P 0 p\in P_0 p ∈ P 0 p ∈ P 0 p\in P_0 p ∈ P 0 A ( p ) T λ = c A(p)^{\mathsf T}\lambda=c A ( p ) T λ = c λ \lambda λ l ∈ { 1 , … , q } l\in\{1,\dots,q\} l ∈ { 1 , … , q }
∂ l j ( p ) = λ T ( ∂ l b ( p ) − ∂ l A ( p ) u ( p ) ) \partial_lj(p)=\lambda^{\mathsf T}\bigl(\partial_lb(p)-\partial_lA(p)\,u(p)\bigr) ∂ l j ( p ) = λ T ( ∂ l b ( p ) − ∂ l A ( p ) u ( p ) ) が成り立つことを、命題 5.3 を用いて示せ。
解答. p ∈ P 0 p\in P_0 p ∈ P 0 G ( w , p ′ ) : = A ( p ′ ) w − b ( p ′ ) G(w,p'):=A(p')w-b(p') G ( w , p ′ ) := A ( p ′ ) w − b ( p ′ ) ( w , p ′ ) ∈ R k × P (w,p')\in\R^k\times P ( w , p ′ ) ∈ R k × P J ( w , p ′ ) : = c T w J(w,p'):=c^{\mathsf T}w J ( w , p ′ ) := c T w 問題 8.1 の解答（p 1 = p p_1=p p 1 = p 命題 5.1 を( u 0 , p 0 ) = ( u ( p ) , p ) (u_0,p_0)=(u(p),p) ( u 0 , p 0 ) = ( u ( p ) , p ) u ~ : V → B \tilde u\colon V\to B u ~ : V → B V ⊆ P 0 V\subseteq P_0 V ⊆ P 0 u u u V V V j ( p ′ ) = J ( u ~ ( p ′ ) , p ′ ) j(p')=J(\tilde u(p'),p') j ( p ′ ) = J ( u ~ ( p ′ ) , p ′ ) ∇ u J = c \nabla_uJ=c ∇ u J = c ∇ p J = 0 \nabla_pJ=0 ∇ p J = 0 D p G ( u ( p ) , p ) e l = ∂ l A ( p ) u ( p ) − ∂ l b ( p ) D_pG(u(p),p)e_l=\partial_lA(p)\,u(p)-\partial_lb(p) D p G ( u ( p ) , p ) e l = ∂ l A ( p ) u ( p ) − ∂ l b ( p ) 命題 5.3 により
∂ l j ( p ) = ⟨ ∇ j ( p ) , e l ⟩ = − ⟨ D p G ( u ( p ) , p ) T λ , e l ⟩ = − λ T D p G ( u ( p ) , p ) e l = λ T ( ∂ l b ( p ) − ∂ l A ( p ) u ( p ) ) \partial_lj(p)=\langle\nabla j(p),e_l\rangle=-\langle D_pG(u(p),p)^{\mathsf T}\lambda,e_l\rangle=-\lambda^{\mathsf T}D_pG(u(p),p)e_l=\lambda^{\mathsf T}\bigl(\partial_lb(p)-\partial_lA(p)\,u(p)\bigr) ∂ l j ( p ) = ⟨ ∇ j ( p ) , e l ⟩ = − ⟨ D p G ( u ( p ) , p ) T λ , e l ⟩ = − λ T D p G ( u ( p ) , p ) e l = λ T ( ∂ l b ( p ) − ∂ l A ( p ) u ( p ) ) である。▨