第7回環瀬戸内応用数理研究部会シンポジウム2003

Transcription

1

2

3

4 (I + R)Gauss-Seidel () Ax = b (.) PAx = P b,., A R n n L-, P, x, b., A A = I L U., I, L U A,. 99, Gunawardena, P = I + S, Gauss-Seidel [2]., S { aii+, i n, S =(s ij )=, otherwise,., (I + S) α (I + αs), α [3]., (I + S) (I + S max ) [4]., S max { S max =(s m aiki, i n, ij )=, otherwise, k i = min{j a ij = max i+ k n a ik }., A U (I + U) [8]., (I + U) (I + βu) [5, 7], β.,, Gauss-Seidel., A n., A n,..

5 2 n., R P = I + R, { anj, j n, R =(r nj )=, otherwise,., (I + R)A = A R a R ij (2.2) a ij, i n, j n, a R n ij = a nj a nk a kj, j n, k=., A R A R = M R N R., M R A R, N R. Gauss-Seidel. M R, N R M R = I L + R RL RU, N R = M R A R = U. n k= a nk a kn M R., (2.3), A R Gauss-Seidel MR N R n k= a nk a kn,. A = M N, A R = M R N R., A = M N, A R = M R N R Gauss-Seidel. 3, Gauss-Seidel A = M N, A R = M R N R. 3. A = I L U L-., A = M N, A R = M R N R.

6 , A = M N., A M-, A >O (Varga [9; Corollary 3.2])., A = M N (Varga [9; Theorem 3.9])., A R = M R N R. (I + R) O, (I + R)Ax = A R x Ax x. A R. A R O (Axelsson [; Lemma 6.]). D, E RU,, (3.) MR = [I +(I D) (L R + RL + E) +{(I D) (L R + RL + E)} 2 + +{(I D) (L R + RL + E)} n ](I D). L R O, L R + RL + E O. a nk a kn <, (I D) O, MR O., A R = M R N R, (Varga [9; Theorem 3.29]). 3.2 A L-. A = M N Gauss-Seidel., T z = ρ(t )z z., T = M N. n k= T. ( T T = T ) T (n ) (n )., T Perron-Frobenius, ρ(t ),T y = ρ(t )y y >. z z = ρ(t ) T y y. T z = ( T y T y ), ρ(t )z = ( T y ρ(t )y ) = ( T y T y ),, T z = ρ(t )z, ρ(t )=ρ(t ), T z = ρ(t )z z.

7 3.3 [2] T., (a) z (z ) αz T z, α ρ(t ). (b) z T z βz, ρ(t ) β, T, z, αz T z βz, α ρ(t ) β, z. 3.4 A L-. A = M N, (I + R)A = M R N R Gauss-Seidel., ρ(m R N R) ρ(m N) < (3.2) Mz = ρ(m N) Nz A = M N. Az =(M N)z = M(I M N)z = ρ(m N) Nz. ρ(m N), R O N = N R = U (3.3) M R (M MR = {(M R N) (M N)}z = {(I + R)A A}z = RAz., (3.2). (3.4) M R (M MR )Nz. MR O (M MR )Nz,, (M MR = M Nz MR Rz = ρ(m N)z M R N R z. 3.3 (b) ρ(m N) <, ρ(m R N R) ρ(m N) <.

8 [] O. Axelsson, Iterative Solution Methods, CAMBRIDGE UNIVERSITY PRESS, 994. [2] A. D. Gunawardena, S. K.Jain and L. Snyder, Modified Iterative Methods for Consistent Linear Systems, Linear Algebra Appl (99) [3] T. Kohno, H. Kotakemori, H. Niki, Improving the Modified Gauss-Seidel Method for Z-matrices, Linear Algebra Appl., 267(997)3-23. [4] H. Kotakemori, K. Harada, M. Morimoto and H. Niki, A comparison theorem for the iterative method with the preconditioner (I + S max ), J. Comput. Appl. Math., 45(22) [5] H. Kotakemori, H. Niki and N. Okamoto, Accelerated iterative method for Z-matrices, J. Comput. Appl. Math., 75(996) [6] M. Morimoto, K. Harada, M. Sakakihara, H. Sawami, The Gauss-Seidel iterative method with the preconditioner (I + S + S m ), Japan Journal of Industrial and Applied Mathematics,(To appear). [7],,,, (I + βu) Gauss-Seidel,, Vol.6, No.4,(996) [8] M. Usui, H. Niki, N. Okamoto, Adaptive Gauss Seidel method for linear systems, Intern. J. Computer Math., 5(994) [9] R.S. Varga, Matrix Iterative Analysis, Springer, 2.

9

10 Ax = b () A R nn xb A A = M N M () x (k+) = M Nx (k) + M b, (k =, 2, ), (2) A H A M N ρ(m N) < [][5]Gauss-Seidel MN Gauss-Seidel A H Gauss H H Gunawardena P = I + S [2] P = I + S max [4] H A H () P P Ax = P b P A H 2 2. A = (a ij ) R n n a ij, i j Z a ii > ( i n) Z L A A M

11 2.2 A = (a ij ) R n n, { aij, for i = j α ij = a ij, for i j < A >= (α ij ) < A > M < A > O A H 2.3 [3] A A = M N M (a) < M > N M H (b) < A >=< M > N H,. 2.4 [3] A = M N H, A M H ρ(m N) ρ(< M > N ) <. 2.5 A = (a ij ) R n n a ii n a ij (3) j= j i,. (3) i,,. (3) i,. 2.6 A i t i t i = n a ij j= j i a ii (i =, 2,, n) 2.7 n A A H

12 3 H H H A P P A H P = P (k) P (3) P (2) P () A (k) = P A A () = A P (k), j = i P (k) = (p (k) ij ) = a(k ) im i a (k ), j i, t (k ) i > m i m i, otherwise m i = min{j : a (k ) ij = max a il } i k A (k ) P (k) A (k ) P (k) t (k ) l n l i P (3) P (2) P () Ax = P (3) P (2) P () b P = P (k) L P (k ) U P (3) U A(k) = P A A () = A (k) P P (k) L P (k) L U = (p (k)l ij ) = U P (2) L P () j = i, a(k ) im i a (k ) m i m i j < i, t (k ) i >, otherwise. m i = min{j : a (k ) ij = max l i a(k ) il } P (k) U = (p (k)u ij ) = j = i, a(k ) im i a (k ) m i m i j > i, t (k ) i >, otherwise. P (k) (k) L P U P (k) (k) L P U m i = min{j : a (k ) ij = max i+ l n a(k ) il } A(k ) P (3) U P (2) L P () U Ax = P (3) U P (2) L P () U b

13 P Ax = P b (4) 2.7 H () (4) (4) Gauss-Seidel P A = M p N p P A M p N p P A H < P A >=< M p > < N p > H H 2.4 ρ((m p ) N p ) ρ(< M p > N p ) < A (k) Gauss-Seidel φ = in Ω = (, ) (, ) Aφ = b. A H, H, Gauss-Seidel Gauss. φ (k+) φ (k) 2 / φ (k+) 2 2. φ(, y) =., φ(x, ) = φ(, y) = φ(x, ) =.., 4 2..H Gauss + Gauss-Seidel [s] [s] [s] [s] Gauss-Seidel [s] [s] [s] ( PC CPU Pentium4 2.4MHz, memory 52MB)

14 5 H H H Gauss H CPU [] A.Berman and R.J.Plemmons, Nonnegative Matrices in the Mathmatical Sciences,SIAM,philadelphia(994). [2] A.D.Gunawardena, S.K.Jain, and L.Snyder, Modified Iterative Methodsfor Consistent Linear Systems, LinearAlgebraanditsApplications., 54-56(99) [3] A.Frommer, D.B.Szyld, H-splittings and two-stage iterative methods,numerische Mathematik.63 (992) [4] H.Kotakemori, K.Harada, M.Morimoto, and H.Niki, A comparison theorem for the iterative method with the preconditioiner(i +S max ), J.Comput.Appl.Math.,45(22) [5] R.S.Varga, Matrix Iterative Analysis 2nd edition, Springer(2).

15

16 Optimization Lay-out Problem in 3-dimensional Finite Element Space I. ARIO and T. ISHII 2 Dept. of Civil and Environmental Engineering, Hiroshima University, -4- Kagamiyama, Higashi-Hiroshima, , Japan 2 The Japan Research Institute, Limited, 6 Ichiban-cho, Chiyoda-ku, Tokyo Abstract This paper presents an iterative structural design technique that uses local control conditions and the stiffness of individual members. A lattice truss is modeled as an assemblages of a number of repeating unit cells to undergo finite element analysis in order to feed-back the results for the stiffness of each member. Further iteration enable for the identification of a topology with the use of the local stress conditions without mathematical optimization. The analysis of widely used shape-layout problems has proposed technique. Key Words: nonlinear equilibrium equation, structural optimization, shape-layout problem, iterative stiffness control Introduction The work of Bendsøe and Kikuchi (988) on continuum body topology optimization using the homogeneous material method, and recent advances in computing technology have enabled for a number of significant researches in the field of structural design. For example [3, 4] proposed the repeating method and Honma and Tosaka[5] presented condition equations for structural control and performed an analysis of structural design using repeated calculations. Xie & Steven[6] developed Evolutionary Structural Optimization (ESO), which based on repeated Finite Element Method calculation and shape control. However problems with this technique include the selection of unnecessary members and the replacement of unnecessary members after the process has finished. Ohmori et. al [7] proposed deletion standards using stress contours and local areas, and suggested an expanded ESO method with one-sided deletion. In this paper, we propose a structural design method using simple local rules of nonmathematical optimization similar to the ESO method. It is a nonlinear repeating system with a feedback response system for design variables (stiffness). The identification of an optimum design is difficult with structural optimization methods such as the mathematical optimization and sensitivity analysis methods due to control conditions such as stress and weight. Even when such conditions are satisfied, the result is not always a nonlinear global optimum solution. The proposed system uses an expanded design area in which elements can be revived, a process that is not possible with the original ESO method. In addition, the stress response to design variables can be feed back into the system. 2 Structural Design Method In this section, the concept of the design method based on local stresses member is introduced. The part of this manuscript have been presented in the citation []

17 2. Concept of layout problem We define a truss design area Ω containing finite design variables as The nonlinear equation is defined as x = (,x (m), )T R M in Ω () F (u,p,x) = (2) Now u R N is the displacement vector, and p R is the loading parameter. Finally, we search for solutions (u,p,x) that satisfy the discrete equilibrium equation(2). If we locally consider linear problem near to the equilibrium point in equation (2),the incremental equation is Jũ + F F p + p x x = (3) Where denotes incremental variables. Let J(u,p,x) = F u be the tangent stiffness matrix. However, then this objection to this method is to structural optimization, for example minimum weight maximum stiffness [8] is described as s.t. M x (m) min (4) m= x min x (m) x max, σ min σ (m) σ max, u min u (m) u max, m =,,M. (5) The main aim of this technique is not the identification of a mathematical optimum, but to identify the local stress control conditions of each member. We identify a topology calculating by the stiffness of member. If the aim of the structural optimization is to minimize weight, the main problem is to balance the entire structure system. In this research, stress share control design variable, consequently the proposed method identifies a rational structure which satisfies the stress condition. 2.2 Structural design using to a section feedback control When change of stiffness alternation is limited part of the structure, the structure can be analyzed with a higher degree of accuracy using the direct method. However the use of an iteration method is more applicable for the modification of an entire structure. Modification of the stiffness matrix is defined as feedback which provides each member with a stress response. We control the stiffness, to satisfy the equilibrium equation. Let us establish an initial design variable x () and an equilibrium point (u,p,x () ) for weight or displacement control. The stress in each member is defined as σ min σ (m) σ max, m =,,M (6) σ (ν) = W ( ) u (ν), ν =,, (7)

18 . It is the displacement function of each node. Here ν is defined as the number of iterations, and σ (ν) =(,σ (m) (ν), )T, is defined as u (ν) =(,u (m) (ν), )T. Furthermore, the present design variable (stiffness) x (ν) is resolved into x (ν+). We then define the resolve rate γ. A new design variable is also resolved into x (ν+) = F ( γ,σ (ν) ), = F ( γ,w ( u (ν) )), ν =,, (8) We ensure that the stiffness matrix is also renewed. solutions (u (ν+),p,x (ν+) ) of the equilibrium equation This result enable us to identify J(u,p,x (ν+) )ũ (ν+) = F p p (9) 2 We substitute this solution into equation (7) and perform a series of repeated calculation, such that the convergence stress and displacement conditions are sat. In other words, the nodal displacement and design variable are expressed as u (ν) = F ( p, x (ν) ), x (ν+) = F ( γ,w(u (ν) ) ), ν =,, () by repeated calculation of the equilibrium equation. If γ,p,w is included, multi-dimensional and multi-feed back of the nonlinear repeat calculation is expressed as x (ν+) = F(x (ν) )=F(F( F(x () ))), = F ν (x () ), ν =,,, (). We adopt a limited stress condition and variable based on local rules. 3 Examples 3. Problem of the coat hook The design of a simple coat hook subjected to vertical load p at a free point far from a wall, is a widely known structural design problem. In this case, we try as the bench model of the layout formation using the proposed analysis method. The lattice structure which is shown in Fig. is modeled using 6 6 elements, and we establish a fixed point whose aspect ratio is.5. This fixed point is third node to the inside from the top and bottom edges of the design area. All initial member stiffness which is design variables are (EA = ). The maximum stiffness is assumed to be EA max =, and the load parameter initiates stiffness control under p/ea =.. The stress with respect to time is shown in Fig.2. In this figures member thickness is a magnitude of stress. Horizontal members at the center and corners adopt a zero stress state in the initial step. A void is observed in Fig.2(c), after which reinforcement members can be seen. In particular, final truss structure was formed of the compression member between two tension members near to the bearing point. Finally, an ideal frame structure which is made from up members with the maximum set condition member stiffness can be seen in Fig.2. The contents in this section will be presented on the day. 2 Now this solution is defined as displacement vector u (ν+) for weight control.

19 Figure : Lattice truss of 6 6 cells (a) step (b) step 2 (c) step 4 (d) step 6 (e) step 8 (f) step 9 Figure 2: Process of optimum formation of 6 6 cells

20 ;; yy ;; yy ;y ;; yy Figure 3: Michell s problem in 3-dimensional space (a) forming at step 4 side view at step 4 (b) forming at step side view at step (c) forming at step 3 side view at step 3 Figure 4: Process of the arch structure forming

21 4 Conclusion We have shown a process for the development of truss structures using the forces in members as a force flow in the design area, and fed back this information as a structural variable without mathematical optimization or the sensitivity analysis method. Especially, we could show possibility that we can make structural design or shape (structural beauty or smart structures) by computing analysis method in this research. For example efficacy of structural design and change for small or light. Further research will focus on dynamic solutions for optimum material layouts and slim structures. References [] Ario, I. and Ishii, T. : Structural Design using Repeated Stiffness Control, Proceedings of China-Japan-Korea Joint Symposium on Optimization of Structural and Mechanical Systems, 2, (22), [2] Bendsøe, M. P. and Kikuchi, N. : Generating Optimal Topologies in Structural Design using a Homogenization Method, Computer Methods in Applied Mechanics and Engineering, 7, (988), [3] Suzuki, K. and Kikuchi, N. : A homogenization method for shape and topology optimization, Computer Methods in Applied Mechanics and Engineering, 93, (99), [4] Schwarz, S., Maute, K. and Ramm, E. : Topology and shape optimization for elastoplastic structural response, Comput. Methods Appl. Mech. Engrg. 9, (2), [5] Honma, T. and Tosaka, N. : Ahape Analysis and Optimization of Structure using an Iterative Caluculation Method, J. Struct. Constr. Eng., AIJ (in Japanese), 52, (997), [6] Xie, Y.M. and Steven, G.P. Evolutionary Structural Optimization, Springer, 997. [7] Ohmori, H., Cui, C., and Suzuki, N.Creation of Structural Form by Extended ESO Method Trough Usage of Contour Lines, Structural Engineering Symposium, AIJ (in Japanese), 47B, (2), 7-4. [8] M. P. Bendsøe : Optimization of structural topology, shape and material, Berlin, Heidelberg, New York : Springer, 995.

22 Bilinear.,,,.,.,,.,,.,., Shubin Bilinear ), Bilinear,,,,,., Bilinear. 2. Bilinear u t + (c u) + (c 2u) = (t>, <x,y<,c,c 2 : ) x y () u(x, y, ) = ϕ(x, y) ( <x,y< ) u n+ i,j = u n i,j t x (c u i+/2,j c u i /2,j ) t y (c 2u i,j+/2 c 2 u i,j /2 ). (2) Bilinear, u i±/2,j,u i,j±/2, (Riemann Solver) { u L i±/2,j if c i±/2,j u i±/2,j = u R i±/2,j if c i±/2,j < { u L i,j±/2 if c 2i,j±/2 u i,j±/2 = u R i,j±/2 if c 2i,j±/2 < (3) (4),, Bilinear. x c, u L i+/2,j. u L i+/2,j. ABCDEF ul i+/2,j, i, j xy B i,j, t n+ i +/2 CF, t n, u, -. t n

23 ABED u, t n+ i +/2, t n t t n+ ABCDEF u. F ( x 2, y 2,tn+ ) ( x 2 c t, y 2,tn ) ( x 2, y 2,tn ) B i,j D E C ( x 2, y 2,tn+ ) y t x A ( x 2 c t, y 2,tn ) B ( x 2, y 2,tn ) : x () ABCDEF. u t + c u x +(c 2 u) y dxdydt = (5) ABCDEF c 2 u c 2, c t yu L i+/2,j = c udydt (6) BCEF = u dxdy + (c 2 u) dxdt (c 2 u) dxdt ABDE, u M, u dxdy = c t yu M (7) ABDE ABC. (6). DEF u M = u i,j + ( x c t) u x,i,j (8) 2 u L i+/2 = u M + t 2 y (Γ Γ + ) (9) 2

24 Γ,Γ + c 2 u ABC, DEF, DEF. c,c 2, 2 Γ +. t n t n+ DEF, DEF DEFG u. DEFG, u., Γ + Γ,() (c u) y u Bilinear x,. F ( x 2, y 2,tn+ ) ( x 2 c t, y 2,tn ) D E ( x 2, y 2,tn ) B i,j y t G ( x 2 c t, y 2 c 2 t, t n ) x 2: DEF m(def),m(deg) DEF, DEG, u L DEF = u dxdy = u m m(deg). u m (x, y) =( x c t, y 2 3 c 2 t) u, DEG u m = u i,j + 3 x 4c t 6 u xi,j + 3 y 2c2 t 6 u yi,j (). u L DEF,uR DEF Γ. Γ + = c 2 u DEF () { u L u DEF = DEF if c 2 u R DEF if c 2 < (2) ABC j, u R i+/2,j i +. ul i,j±/2,ur i,j±/2. c,c 2,, 3

25 c,c 2. 3., 6, 5 5. x, y c = c 2 =.,,. u(x, y, ) = exp[ 6{(x 3) 2 +(y 3) 2 }] (3) c = c 2 =.,,,,,,,. Bilinear, Lax-Wendroff LW., x, y, z c =c 2 =c 3 =.. u(x, y, z, ) = exp[ 6{(x.5) 2 +(y.5) 2 +(z.5) 2 }] (4), Bilinear., 3,Bilinear L-W, T =.36 u. (a) Bilinear (b) L-W 3: 2, L-W,,, Bilinear,, L-W.,,(5), 4

26 4. E = i,j u i,j u(x, y, t) (5) L-W 2 Residual E of Bilinear and LaxWendroff Bilinear_2D.dat LaxWendroff_2D.dat 8 Residual E Time 4: Bilinear L-W 4.2 Bilinear L-W Bilinear,. Bilinear L-W, u t +(c u) x +(c 2 u) y =,.,α b,α l u t + (c u) + (c 2u) = α b x y : Bilinear (6) u t + (c u) + (c 2u) = α l x y : L W (7) α b = { 2 ( t)c ( x) 2 4 ( t)2 c 2 ( x)+ 6 ( t)3 c 3 }u xxx (x, y, t) { 2 ( t)c 2( y) 2 4 ( t)2 c 2 2 ( y)+ 6 ( t)3 c 3 2 }u yyy(x, y, t) (8) α l = c c 2 ( t) 2 u xy { 6 c3 ( t)3 6 c ( t)( x) 2 }u xxx { 6 c3 2( t) 3 6 c 2( t)( y) 2 }u yyy 2 c2 c 2 ( t) 3 u xxy (x, y, t) 2 c c 2 2( t) 3 u xyy (x, y, t) (9) L-W u xy,, Bilinear,,. 4.3 Bilinear Bilinear,. 5 Bilinear,L-W,u, yz 5

27 ,,, T =,.,.2,.3., Bilinear. 6 Bilinear L-W,, Bilinear. (a) Bilinear (b) L-W 5: yz 5 45 Residual E of Bilinear and LaxWendroff Bilinear_3D.dat LaxWendroff_3D.dat 4 35 Residual E Time 6: 5.,, u i±/2,j,u i±/2,j,k,, Shubin Bilinear,,, L-W. Bilinear,,,, Lax-Wendroff,,.,u xy,. ) J.B.Bell,C. N.Dawson and G. R.Shubin, J.Comput. Phys. 74,pp.-24(988) 6

28 ö ý š Þ y V T V V Í V Þ T V Ô T "! # $ % & ' ( (;2< )+*, -/ * :,2=2,>=2?A@2B5=DC>E2F,2=DBG=DH>I2J2B5=DF ;>< ) S PSfrag replacements K L>MON PRQRSUTWV, XRY[Z]\_^[Za`Rbdc 3 edcgf+hji+kmlonqp Nehari csrrtrurvxw+y{zr RXR}R~ yoƒx s RˆR RuRvUŠWc RŒWgŽdcg qlm ( ). R, žzr RXR} R ymƒx s š gœ žc Ÿ šž U Rcs cjf h ĩ k c g qg mª«g žƒ j l²±u³ ǵ gµxÿ ˆ gugv lžf hsĩ k ugv _ º¹ V. Nehari gĝ Wc rgtjugv l_f hi»k¼ugv»w l²½ ¾A mª [8]. c»pºà, Ŕ RµdŸ Á c, Âxª cgf+hji+käã šrsx YdŸjÅjÆRÇxw+yžŸ XRYxf+hji kèurv, É Dl sêažë \_^xw+y_ÿ \_^xf+h i+k¼u v, `RbRÌdc ÅjÆRÇxw+y_Ÿ `Rbxf+h V_ÓgÔWÕgÖ i+k ugvuã Í. κÏxc Ŕ gµuÿ g gˆr gugvaðrgtuf+hºi kñurvqžcgòrcs RŒ ºŽdc ŠWc WØj~g RÙ [5, 7]. PSfrag replacements θ S S n θ S p n L L n r θ S n PSfrag replacements p p 2 S 2 θ θ D S θ n PSfrag replacements L L n θ C C n C 2 r n r 2 L 2 θ 2 L 2 : 3 edcrgtxf+hji+kèurvxw yú RuRvWŠWc RŒgÛWjŽ ÜºÝ _Þgß Vžâ cž½g¾uë gœ ºŽxc à á غãjägỞåWæ çéègêuÿ ëìxíuhmîgïñðxšžògóxcsô õ W øéù8yoƒwªwš. úg, ºRu vdcº R RóD²r tru vdc erûql ƒdü, jru vxw yðrrt u vwšwc RŒUjŽA, rrtrurvdw+yú RuRvUŠWc RŒWjŽ jý+ Úª, T TWV þày ÁRÿ dcjàjá ôrõwjž l šxp ql [4]. ºRuRvxw+yñrRtRuRvxŠWc RŒUjŽdcgº Úª, rgtrurvxw+yú RugvWŠWc RŒWjŽdcgqlo RŒRÛWjŽdcg Až ¹» UjË. ÜºÝ Î ÏUc gˆ xcj u v»ºý mª Á, Nehari c 3 euc r tuf h ik¼ugvrš c Œ ºŽ c ôgõql Î àjá l²½r¾d mªwš [3]. â ÜjÝ, غãgäRá lmøxš T T yúcjà á lorgt f+hji+kèurvxw+ymîjïdcgºrurvwšwcº RŒRÛWjŽ»côRõ UØ Ë U ƒ»ú Ÿgw. cºcºî, rrtuf+hºi kèugvxã µažÿ f+h i+kúl RüžzR gxr}gâ Î"!WË U Í. ÜjÝ y_cºàjá, RŒWºŽdc l_î#dc $&%dÿ'&(uý l)*,+"-./g cg

29 Þ Þ Í T Þ T T V Þ Í V ö ö Þ T â V T Í T e Þ ö â V Þ T T Þ Í Ã ö V T "32"4#5 â ìrxc á oªùdyñƒ غãjägá l76 ØgË šwp Ájc â. "32845 Ø ãgägáq '8(Uý l²«g gv»:9»šg ;8<=RŸ ãjäuã,= ì c A >g 8? ô õd 7/sã Wl '&B Úª ôrõ l & xë šxp_àjá [6]C"D&E à µqlo±3*gªr RuRvdc R T ú '8( F G» sƒ psÿ,h8?, 6&I:J&9 ƒu sãgädcrád²ð»šsògódc ôrõ lk&l. ƒ, ŒxjŽ»cg &M šjª, µdã Ÿ * yúw Žxý &N&O»c,PxƒWŸWš H?sã ä l7gµww yrqd oª,9dç Ws:g WË. ž ºÃ ª, rgt f h ik¼ugvxc p, T&U VjT «gvg xchswã _Ÿ š:h&?, ƒdú cjàjáqls cuúgú6wø Ë U Ÿ š. V Z Îgà#VWYX :Vgµ3[žÆq mª [_ÆUf h ikml²n p_î Ïxc sþgß gu vuw y{rgtxf h ĩ k ugv Š \8] c gœwjžxcg : mªv Ø ãrägá gœw Ždcºàjá l 6 Ø Ë l Ø Ë àºáql²½ ¾ mª š PgQgSV ÜºÝ []., c àºáql gœgûwºžxcjà á» ØUš ö Á c. ƒuw»ø, T g RˆR RuRvdc RŒRÛWjŽdcg ØjãRäRáW áql76wø Ë UžÃ. PSfrag replacements *R V Joukowski ^`_badcfe 2 Nhgjilkbmondprqtsvuxw PRQgSxT TWV ½R¾WË àjá, gœrû jžuc"y#z {8 Àº gurvww+y{rrtgurv ŠWc RŒ jžxcô õ ºŽxý l)* ª M»çR}RÙUÃRÍ. žƒ T ÜjÝ sþgß, [4] c ½R¾UË RŒgÛ jžxch&?dágÿ. ú~,*,/žr tgugv»žx YUf h ĩ k¼ugv+l7 Ø ž H? l7d ܺÝ, yž, ÞRß gujvuw yðrrtrurv ŠWc RŒWjŽdcºàjáql ƒrë., y v C 2 C f(z) L 2 L θ θ θ x u D C n RuRv L n XgYxf+hji+kÈuRv 2: RuRvA²XRYxf+hºi+kÈuRv z X }R~»c Jordan =[Æ C,..., C n l µdžë µdÿ n ˆR cr u v D w+y / w XR}R~dcŔ RµdŸ V n RˆR dcxrydf+hji+k¼urv S ŠWc RŒWjŽqlo C D w+y S ŠWcjjŽxý w = f(z) / Þ8 f( ) =, f ( ) =, g x8m8 Laurent c «Š& 8Œ šupˆ8 c ÁUÎ"»ž«ú CW c, f hºi käc,@89a𠺎xý ÁRž«ú ( 2). R, XRYxf+hji+kÈuRvdcjÅjÆxf+hji+k ÃŽ&AsŸgË Œql θ, f(z) l T D $&%dÿ,'&(xý g(z), h(z) l_øxšjª M»çRCW c Užw+y, >dc, ºŽUý V f(z) &Œ [žæ l ºË. f(z) = z + e iθ i(g(z) + ih(z)) () C,, C n l²»š žxgyxÿ f+hĩ k L,, L n Ë Im (e iθ f) = p m, z C m, m =,, n, (2) 2

30 V â Þ T Þ T C Þ Þ Ô V V Þ C ö T Í Í C T e T Þ V T V Ô V V T &, p m V f+hji+k c,@&9ql xë Rùxc«Þ T C» sƒ l g(z) c &Œ mª Å".ü sÿ C» xys, R»&M& g(z) + Im(e iθ z) = p m, z C m, m =,, n (3) ˆ& Š& &Œ w+y / g(z), h(z) V g( ) + ih( ) =, (4) Ë ŸjœxÀ g( ) = h( ) = Ÿ ý ql ºŸ ƒ»ü Ÿ y_ÿ š#cjû/ (4) xã & dë ƒxü () Š8 &Œ dc f(z) È8 l ºËx WžÃjœ w cºî"&ouw+y7/ RŒWºŽdc ºcW psÿ,$ %dÿ,'&(xý g(z), h(z) l) * +"- ƒ > â, ØjãRäRáql_Øxšºª g(z), h(z) c ôrõqloydÿ»pc f(z) côgõ F (z) l MçRC» z mk &M& gµ, ζ lj V &Œ F (z) = z + e iθ i(g(z) + ih(z)), (5) G(z) + ih(z) = n N l Q lj log (z ζ li ) (6) C l c d# sã är l= j= C" R«Q lj Rµ ~» & n N l Q lj log z mk ζ li P m = Im(e iθ z mk ), m =, 2,, n, k =, 2,, N m (7) l= j= ÚÎ"š&Odc *Rc &Œ N l j= l jëd p s«3* rrtrugvdcerû» Íjœ".Wª$&%dŸ,'8(xý kèurvjý ÚªWÁRÿ ÎWc, Y8œxw+y_Ÿ Q lj =, l =, 2,, n (8) c «R ql ¹» U, \_^xf hji+k urv[z T `Rbxf+hji ˆ& Wà& j ql+"-xë UžÃ. ^`_badcfe 3 Nhgjilkbmondpož`qtsvuxw ÜºÝ žþgß TWV RŒgÛ ºŽdcºàºá, zj RXg}g~dc r tgurvxc»sã ä l79, F (z) c H8?q ÿ:» Øjãgägá lmøušjª gœgû jžxc ôgõ lñyqp. &Ÿ Ã, r tuf hºik¼ugvql²±u³ w T8U Xg}g~ ãgä+l7j"9wë "* cžugv Uc HSWà mÿ š. g ;x, ju v D à gˆ Í ƒuü, rrtxf hji+kèurv»snqpsf+h i+k P Ÿ. c \], Joukowski T= l_øxšr : & &WjŽql WØ Ë UžÃ ( 3). ƒx, rrt urvsnapsf+hji+k_: i+k ÃgÎ"!xË Joukowski \&] l_øxš, rrtxf+hji+k¼urvrâ l Í \ dc R RuRvWŠj RŒWjŽxË. W >dcx p Ÿ jžxý ψ(w) l_øxš. ψ(w) = 2 (w + w W w W2 ) ψ, (9) V V Š& &Œ &, W, W 2 f+hºi+k g dcô õ, ψ ψ(w) à f(z) Š &Œ Þ T c,ˆ& :R xë º R c#ˆ& l jëw 8*Rcº«, V X Yxf+hji+k urvdch&? sÿ. W, W 2 ôrõ jžwý w = F (z) l_øuš ª, Usð»šsògó ) * U_à 3 f c ψ = ( W W 2 )/4 T [2].

31 á Þ Þ V T T V c Ô c Þ T Í V V T T V Í Þ Þ Þ V Þ Þ Ë Þ T V Ô T V Þ z Þ V V Ô V \ r txf hji+k]urv S c ψ(w) U ŽAlmuRv D W, D lú±d³ºzr X }ql z XR}DsË. T&U z XR} ~ D c g sãrä l J&9xË c ª ÇdŸ,H&SUÃ. Ž «x, D c,rµ C sÿ, c s»ÿsê\ g~ž xò" xžãrä ζ,..., ζn l 9YRü jš. D w+y D ŠWcôRõR gœwjž z = F (z ) l,mç. F (z ) ψ(w) c,?& xý N F (z ) = z + Q j log(z ζj ) () j= l_øxšjª, f (w) loôrõxë, R«& Q,..., Q N f (w) F N (w) = F (ψ(w)) = ψ(w) + Q j log(ψ(w) ζ j ). () Rµ &Œ, j= Sfrag replacements S l jëd Wp s«3* W F (z k ) cž. L θ z k = F N (zk ) = z k + Q j log(z k ζ j ) (k =,..., N ), (2) p j=. &, z k = ψ (F (z k )) V ψ(w) loˆ D ú PSfrag replacements rrtrurvxãd\_^xf+h \&] i+k¼u v erûdc ψ(w) D C ζ2 ζ PSfrag replacements ζ N F (z ) 3: & &WjŽ ψ(w) l_øxš H&? àºá, ψ(w) c, & Al Ë D }RÙxÃ Í F Gq s ý z 2 z C z N. W ψ (w) ψ ± (w) = 2 (w ± w W w W2 ) ψ (3) l²ugvucˆ8 8O»s ± oª,²8ø³? œ#.. ψ(w) c 8 l ü, 3 T T exc rrtuf h i k¼ugv ÿ Î cºà pj WžÃ. TWV Þ V ÎjÏdc RˆR Ru v, rrtxf hji+kèurvsnapsf+hgi+k c urv D c R ós µ Úª z jÿ. cx psÿ,h8?d ψ(w) cu RpsŸ, 8 8WºŽ+l7WØ Ë àºá+ls RcWúRú 6 Ø Ë U š. x ψ l xë Usà gÿ \]. Joukowski T R l ¹2øRºdËd U crf hºi kúl»>¼ šjªwš»ç WÁ Ã, f+h i k{c Ã,½ ÚºŽxý c & xc *R }gùdÿ ψ ± c,h&?rç¾jã szà Ÿ. ú, f+h i+ká dcô õdcò óá Â= Ë UsÃÃ&<+ ƒ. ƒ, xt z cgf+hji+kmlonqps RuRvxw+yÐrRtxf+hji+kÈuRvWŠWc RŒWjŽdcg»&MRšjªWÁ $&ÄxË. Ë W¾X, TUV z c[sæxf+hji+kúlonqps RuRvql p * /jugvrâ lž Ž»Ë Ÿ çr/ f hji+k{c, z c ŒUgŽql UØWË à áalm½ ¾8 _ªWš []. W, ºcjàjáqlñ R RˆR RuRvdc gœrûwjždcg 6 Ø Ë Uglo. ƒ»ú c, 3ƒU Å š, º u vql D, rrtdf hºi+k u v S nap P n cgf hji+kúl L,..., L n, f hºi kæ R xc ôgõql_ jƒ Çjƒ W, W 2,..., W n, W n2 ÚË. Î cgf h i k ch&?uc ψ 4, 2

32 l T T Þ ö Þ T V Þ C š Þ V V T Þ V V Þ T Í T Þ Þ Þ Þ Š T ì ÿ: P Š8 &Œ cgf hi k L l (l {,..., n}) l È ymw Ÿ" [sæ Cl, y²ƒx :ˆ& l7» Ë gœ jžxcºjžwý ψ l l W l, W l2 l:»ĩ k c,é8 qúë \8] Joukowski T žåwæ šjª, xë UžÃ. ψ l W»ø, L l R xcgf+hji+k C l c dc[sæxf hji+kðjž ƒ cjjž ƒ c8 [sæd P n c[sæ»f+hji+kúlon»ÿ»pourval D (l), D (l) lo±x³ z RXR} z (l) XR}AžË. Þ Y2&4"5 RˆR dch&? & &WjŽ ψ(w) l WØ Ë àºá z XR}&MRšºª zr &. D l_øxš â ØjãRäRá, Í log(z ζ ),..., log(z ζ N ) (4), w XR}&MRšjª jžuý ψ l7wøq s så&êxý l_øxš â ØjãRäRáA:Ë ŸgËx WžÃ log(ψ(w) ζ ),..., log(ψ(w) ζ N ) (5) T. R Rˆ dc,h&?á, žƒ+ÿ log(ψ l (w) ζ (l) ),..., log(ψ l(w) ζ (l) ), l =,..., n (6) â loå8êxý žë ØjãgäRá lo ƒxü, T z&àdÿ & 8WºŽqlÚØxš Þ 32&4"5 UžŸ ç{z f+hi+kúl²nqp Rugvql7Ì8ø pj U_Ã. Uúø, () czg & ìwc Í#?&.ÎÐÏºË Çql (6) cåêxý c Í"?&. & xë šxpj U. >»,/jf hĩ ká c 8NOxc l² C gĝ xc H8?»: 8 ºŽ ψ(w) TWV lúøuš àºá, f+h i+kéc, ψ(w) W»øž\ C ~ d ƒ, F (z ) V,Ó c, 8 jf hºĩ kñ c, &N O»8Ò ÚŸ š. Îgà, g gĝ xcjgugv»mgšºªjøuš å8êuý V (6) V Ô g xc 8N8O cg " šjª Á Õ&Ö _Ÿ š. x, ôrõwjžxý &N Oql. *W ψ (w),, ψ n (w) TWV c Í?Wœ".ql_Ødš C» c, &N&Odc Í"?Wœ".dc, šÿjš ŸW² žã "ØÐjÃ/» R l_øxš WRžË C"R~+»øÄôRõWjŽxý N J(w) = n ψ l (w) (7) n l= l Ù & xë ÃÚ y²ƒ Wà"& dc Þ V CÛ& g«& Úª «3* / f (w) F (w) = J(w) + e iθ i (G(z) + ih(z)) (8) G(z) + ih(z) = n N l Q li log(ψ (l) (w) ζ (l) li ) (9) l= i= z (l) XR}g~d T & g U_Ã. z (l),..., z(l) nn n (l =,..., n) W»ø³>dcˆ z mk = F (z (l) mk ) = J(w mk) + n N l Q lj log(z(l) mk ζ(l) j ), m =,..., n, k =,..., N m, (2) l= j= g V w mk = F (z mk ), z (l) mk = ψ l (F (z mk)) ψ l (w) l²ˆ8 d F (z mk ) cž. ÜjÝ ú, \_^ /`RbUf+hºi kèurv ŠWcs RŒ jž»"wšºªwá dcjàjáxã yoƒ D (l) ú y_c ½R¾ FGq ž ºý ž Ϋ& ψl (w) W dø_ÿ 5

33 Ý A Þ C / 4 ÜÞÝ ß \] N Joukowski ådæ çðåêdý lžø»š ª â Þ ß, Ø ã ä á W Œ ÛW Ž»cgà áal F=Gq, Þgß T V Þgß g gˆr ugvdc gœ ÛWºŽxcg» A mªwá:6 Ø l Ø» ž. à8á Ž&â 8ãR l _ŸgÃ+y{½R¾ s àjádc &ä8oql å&æxë çjèêéìë [] Okano, D., Terazono, M., Ogata, H. and Amano, K.: Numerical conformal mapping from domains with multiple slits onto the canonical slit domains by the charge simulation method, Information, Vol.6, No., pp.7 8 (23). [2] Okano, D., Ogata, H., and Amano, K.: Stagnation Point Analysis by the Numerical Conformal Mapping Using the Charge Simulation Method, Theoretical and Applied Mechanics Proceedings of the 5th Japan National Congress on Theoretical and Applied Mechanics, Vol.5, pp (2). ÜºÝ [3] Ù, í, î à#ï8ð, X&ñ¾ò, ógé8ˆ8ô â : ÞRß Ö" &ø ù"ú Ø ãgägá» ǵ gµxÿs g gĝ gu vxc Î Ÿ gœwjždcjàjá, õ8ö& & / Vol.42/ No.3/ pp (2). Ü Ý [4] Ù â Þjß Ö, #ø ùú : Ø ãºäºádmåwæ»ç³ûràügÿ jœrž c à á, õ#ö" " pp (99). ö [5] ý þ ÿ :zr ÓRÔ ÕRÖ P &ø / / 989. [6] «gy â : ØjãRäRáA_ c WØ&/ / / 983. [7] ý þ ÿ ÓRÔWÕRÖ : ( )/ / 973. [8] Nehari, Z.: Conformal Mapping, McGraw-Hill, NewYork, 952., Vol.3, No.5, 6

34 SOR. PVM(Parallel Virtual Machine) SOR(Successive Over Relaxation) SOR 2. Ω={(x, y) <x<, <y<} 2 u x u =2x(x ) + 2y(y ) (x, y) Ω y2 () u(x, y) = (x, y) Ω. u(x, y) =x(x ) y(y ) (2) Ω x y h (x i,y j )=(ih, jh)u(x i,y j )= u i,j () u i+,j 2u i,j + u i,j h 2 + u i,j+ 2u i,j + u i,j h 2 = f i,j. (3) f i,j =2x i (x i ) + 2y j (y j ) SOR u (k+) i,j =( ω)u (k) ij + ω 4 (h2 f ij + u (k+) i,j + u(k+) i,j + u(k) i+,j + u(k) i,j+ ) (4) ω k

35 Area Area2 Area3 Area j A j i Area2 j B i i : 2: JSOR JSORω JSOR ) SOR 2 Area A Area2 B Area2 B Area A JSOR k + k Area A i = imax Area2 B k SOR (4) Area2 B i = u (k+) i,j =( ω)u (k) ij + ω 4 (h2 f ij + u (k) i,j + u(k+) i,j + u(k) i+,j + u(k) i,j+ ) (5) u i,j k + k SOR i = (k ) ω ω 2 ω (ω,ω 2,ω) JSORω 3.2 PSOR PSORω PSOR k + 3 PSOR Area2 B Area3 B i = Area C Area2 C Area A Area2 2

36 A i = imax i = k + JSOR PSOR Area Area2 Area3 A C B A C B i=imax i= i=imax i= i 3: PSOR Area Area2 Area Area2 i,j+ A i-,j i,j+ i-,j i,j i+,j B A i,j B i+,j i,j- i,j- j i=imax i= j j i=imax i= j i i i i 4: i = imax 5: i = 4 Area Area2 A i = imax u (k+) i,j =( ω)u (k) ij + ω 4 (h2 f ij + u (k+) i,j + u(k+) i,j + u(k+) i+,j + u(k) i,j+ ) (6) Area2 B u i+,j k + (k +) 5 Area2 Area B i = u (k+) i,j =( ω)u (k) ij + ω 4 (h2 f ij + u (k) i,j + u(k+) i,j + u(k) i+,j + u(k) i,j+ ) (7) 3

37 (5) PSOR SOR Xie 2) JSORω PSORω 4. JSOR JSORω PSOR PSORω () ω SOR JSOR JSORω PSOR PSORω : SOR JSOR JSORω PSOR PSORω (.97) 97(.968) 58(.98) 885(.97) 842(.97) (.988) 5273(.986) 373(.992) 2243(.988) 22(.988) (.994) 767(.992) 7356(.996) 4525(.994) 4274(.994) SOR SOR JSOR SOR JSORω JSOR SOR SOR PSOR SOR PSOR Xie 2) PSORω PSOR PSOR PSORω 2 JSORω PSORω ω. ω ω 2. JSORω ω ω JSORω ω 2 ω ω 2 PSORω ω ω 2 ω 4

38 JSORω ωω ω 2 ω ω ω 2 2: ω ω ω 2 2 2(JSORω ) (JSORω ) (JSORω ) (PSORω ) (PSORω ) (PSORω ) Ω={(x, y, z) < x<, <y<, <z<} 2 u x u y u z 2 = 2 (x, y, z) Ω u(x, y, z) = (x, y, z) Ω (8) u i,j,k = 3 JSORω ω =.98ω =.8ω 2 =.8 PSORω ω =.97ω =.98ω 2 =.98 3: SOR JSOR JSORω PSOR PSORω SOR PSOR JSOR JSORω JSOR PSORω PSOR 6. SOR SOR 5

39 JSOR JSOR JSORω JSOR JSOR PSOR SOR PSOR ) D. Xie, New Parallel Iteration Methods, New Nonlinear Multigrid Analysis, and Application in Computational Chemistry, Ph.D. Thesis, UH/MD Research report 28, University of Houston, Houston, TX(995). 2) D. Xie, L. Adams, New Parallel SOR Method by Domain Partitioning, SIAM J. Sci. Comput. 2, No. 6, pp (999) 6

40 xn+ = axn( xn) a > cr 2 c k z e dxdydz = k =, c=.59 V π 2 / k k 4.7% xn+ = 4 xn( xn) 2 x 2 e dx= π

41

42

43

44 CG **** *** (CG) () (2) Windows (BMP) () () (2) () ( []) [4](2) ([3, 5]) [2] () CG 2 CG 2 2. () ( 2.)

45 [] ( 2.2) ( 2.3) aaaaaaaaabbbbbccccdddddd a 2 b 5 3 c 4 d 6 a9b5c4d6 2. ( 2.4)

46 ( ) [2] adabaeadaacaabbf bbcddddef f a b c d e f ( 2.6) (26) (5) (7) (4) () a c e f b d (8) (2) (2) (3) (5) (6) 3

47 2 a b c d e f 2 (8+5+6) (2 + 2) = = 44() 26() = 28() ( 3.)[3, 5] x k x k y () k,y(2) k,...,y(n) k ( 3.2) () 3 y k () 4 () y k y k y k () 5 () 2 y k x k () 6 y k e k e k = x k 4 N i= a k y (i) k

48 L E E = L L e 2 k = L k= ( L x k k= N i= a i y (i) k ) 2 E a i = (i =, 2,...,N) a i 4 CG 2 () JPEG [4] [] C.C.Cutler, Differential quantization for television signals, U.S. Patent 2, 65, 36. July 29, 952. [2] D.A.Huffman, A method for the construction of minimum redundancy codes, Proc. IRE, 4, 98-, 95. [3] N.Kuroki, T.Nomura, M.Tomita and K.Hirano, Lossless image compression by two dimensional linear prediction with variable coefficients, IEICE Trans. Fundamentals, E75-A, no.7, , July 992. [4] 65, , 23. 5

49 [5] X.Wu and K.U.Barthel, Piecewise 2D autoregression for predictive image coding, Proc. 998 IEEEE Intl. Conf. Image Processing (ICIP 98), III, 9-94, Chicago, Oct

50 . N H B = ωj,k α aα j,k aα j,k () j= α=x,y,z k [A, B] =AB BA[a α j,k,aα j,k ]=[a α j,k,aα j,k ]=[a α j,k,aα j,k ]= δ j,j δ k,k δ α,α H I = N j= α=x,y,z b α j = k S α j b α j (2) g α j,k (aα j,k + aα j,k ) (3) [Sj x,s y j ]=iδ jj Sj z (4) [S y j,sz j ]=iδ jj Sx j (5) [Sj z,sx j ]=iδ jj Sy j (6) H S (t) H(t) H(t)=H S (t)+h B + H I (7) (8) 2 P (t) U (t) = e ihbt/ U S (t), (9)

51 U S (t) = + U I (t) = + n= n= ( i ) n t t tn dt dt 2 dt n H S (t ) H S (t n ), () ) n t ( i W (t) = U (t) H I U (t) = b α j (t) = k N dt t j= α=x,y,z tn dt 2 dt n W (t ) W(t n ), () U S (t) Sj αu S(t)bj α (t), (2) gj,k α {aα j,k exp(iωα j,k t)+aα j,k exp( iωα j,kt)} (3) P (t) P (t) =U (t)u I (t)p ()U I (t) U (t) (4) T P () = ρ() ρ eq (5) ρ eq = e β(ω B H B ),e βω B = Tr B {e βh B } (6) P (t) ρ(t) = Tr B {P (t)} (7) = Tr B {U s (t)u I (t)p ()U I (t) U s (t) } (8) = m= n= t ( i dt t U S (t )U S (t 2 ) S α 2 j 2 ) m ( ) i n N tm dt 2 N j j m= α α m=x,y,z j j n= α α n=x,y,z t n t t dt m d t d t 2 d t n S(t)U S (t ) S α j U S (t 2 ) U S (t m ) S αm j m U S (t m )U S () ρ()u S () U S ( t n ) S αn j n U S ( t n ) U S ( t 2 ) S α 2 j 2 U S ( t 2 )U S ( t ) S α j U S ( t )U S (t) Tr B {ρ eq b αn ( t j n )b α n ( t n j n ) b α ( t n j )b α j (t )b α 2 j 2 (t 2 ) b αm j m (t m ) b α j (t) B m(t m ) Bloch-De Dominicis Tr B {ρ eq B n (t n )B n (t n ) B (t )} = B n (t n )B n (t n ) B (t ) B (2) (if n = odd) P BP = (n) (t P (n) )B P (n ) (t P (n ) ) B B P (n 2) (t P (n 2) )B P (n 3) (t P (n 3) ), (2) B B P (2) (t P (2) )B P () (t P () ) (if n = even) B } (9) 2

52 a α j,k aα a α j,k aα a α j,k a B =, α j,k =, (22) B j,k =, a α j,k B aα j,k =, (23) B j,k = δ j,j δ k,k δ α,α B e β ω, (24) k a α j,k aα j,k P (n, n,, ) B = δ j,j δ k,k δ α,α e β ω k, (25) P (n) >P(n 2) > >P(4) >P(2), (26) P (n) >P(n ),P(n 2) >P(n 3),,P(4) >P(3),P(2) >P(). (27) (P (n),p(n ),,P()) P ρ(t) () : ρ(t) (2) α α l j l j t t = Dlj α l α j (t, t ) Dj α j α (t, t )=D2j α j α (t, t )=djj αα (t, t ) Dj α 2j α (t, t )=D2j α 2j α (t, t )=djj αα (t, t ) d αα jj (t, t )=δ jj δ αα k ( g α j,k ) 2 {e iω k(t t ) + 2 cos(ω k(t t )) e βω k } (3) t t = Ĝ(t, t ) Ĝ(t, t ) [Ĝ(t, t )] = λ g(t, t ) λ ν g(t, t ) ν (λ,ν)(λ,ν ) ( g(t, t )=+ i ) n t t tn dt dt 2 dt n H S (t ) H S (t n ) t t t n= 3

53 (4) ˆV α lj [ ˆV α j ] [ ] ˆV 2j α (λ,ν)(λ,ν ) (λ,ν)(λ,ν ) = i λ S α lj λ ν ν = i λ λ ν S α lj ν (5). (6) (5) (λ, ν)(λ,ν ) λ ρ() ν λ ν λ ρ(t) ν 3 ρ(t) ρ(t) ρ(t) d dt ρ(t) = i [ρ(t),h s(t)] iλ 2 [ Tr B Sj α bj α (t),u s (t)u I (t)p ()U I (t) U s (t) ] (28) j= α=x,y,z 2 (28) d dt λ ρ(t) ν = i λ [ρ(t),h s(t)] ν + t [ ] dt ˆM(t, t ) λ ν (λ,ν)(λ,ν ) λ ρ(t ) ν, (29) ˆM(t, t ) () () ( ). 2,3 4

54 2: 2 3: 4 H S (t) =J(t)S S B j (t) S j, (3) ˆM(t, t ) 4 j= 5

55

56 Abstract 5. [] fat-tail.4 Levy [2] quotation quotation [4--7]

57 2 [3,4,5] m m 2 m=,2,3,4,5 m= 3 m m=4 m=3 8 3 m= m=2 m=3 m=4 m=3 3 T T 2. 5 tick Tick bid ask

58 bid ask bid ask bid ask bid ask P( )=P( )=P()=.5 () usdjpy.a,,,, m 2 m () P( )=P( )=P()=.5 ( ) Fig. P( )P( ) 'gosap' Fig. P( )( ) 'P' 'P' Fig.2(a) 5 P( ), P( ) Partition size=2, 'P' 'P' Fig.2(b) P( ), P( ).

59 'P' 'P' 'P' 'P' Fig.3 m=2 P( ), P( ), P( ), P( ) 'P' 'P' 'P' 'P' 'P' 'P' 'P' 'P' Fig.4 m=3 P( )P( )P( ) 'P' 'P' 'P' 'P' 'P' 'P' 'P' 'P' 'P' 'P' 'P' 'P' 'P' 'P' 'P' 'P' Fig.5 m=4 P( ), P( ),, P( )2 m=4 Fig.2(a) 2 Fig.2(b) Fig.3 m=2 Fig Fig.2 P( ) Fig.3 P( )=.78 ±.5 P( )=.68 ±.3 P( )= P( )=P( ) =.7 (3) Fig.4 8 m=3 Fig P( )=P( )=P( ) (4) x C(T)(3) x 2 ( T) = { < x ( T+ t) x ( t) > -< x ( T+ t) >< x ( t) > }/ σ C (5) Fig.2 5 () P( )=P( )=.5 Fig.2(a)() P( ) =.7 >> P( ) =.29 (2) x(t)x(t+t) C(T) (3) C(T) Fig.6 T=3, 4 C(T) 3

60 'ujall-corr'.8.6 T= Fig.6 C(T)T T 3, m=3 m=4 3 4 m= m3,4 'ujcut-s' 'ujcut-s2' 'ujcut-s3' 'ujcut-s4' x y.75 (4) M(x, y) = H(x)-H(x y) = - P(x)log P(x) + P(x y)log P(x x 2 x y 2 y) (6) m2 m x H(x) y x H(x,y) y x (6) P(x) P(x y) 2,, 52, -5, P(x),P(x y) 2-5, 2 2,-52, 2, m=-4 Fig.7 Fig.7 m=(y=,) m=2(y=,,,)m=3(,,,) m=4(,) m= m=2 2 m=2 m= Fig.7 m= { }

61 [7] C(2) : tick [] Bachelier L. Théorie de la speculation, Doctor Thesis. Annales Scientifiques de l Ecole Normale Sperieure III-7:2-86; Translation (964) : P.H. Cootner(Ed.) the Random character of stock market prices, MIT Press, 7--8, 9 [2] R.N. Mantegna and H.E. Stanley, Scaling Behavior in the Dynamics of an Economic Index Nature, 376, 46-49, 995. [3] Toru Ohira, et.al. Predictability of Currency Exchange Market, Physica A 38, , 22 [4] Mieko Tanaka-Yamawaki, Stability of Markovian Structure Observed in High Frequency Foreign Exchange Data, New Trends in Optimization and Computer Algorithms (December 9-3,2, Kyoto); [5] Mieko Tanaka-Yamawaki, Ann. Inst. Statist. Math. (AISM), vol. 55 (23) in press. [6] Mieko Tanaka-Yamawaki A Study on the Predictability of High-frequency Financial Data, Proceedings of the 7 th International Symposium on Artificial Life and Robotics, vol., pp.74-77, 22

62 A Parallel Algorithm for the Linear Complementarity Problem with an M-matrix Lei Li Faculty of Engineering Hosei University Koganei, Tokyo Japan Abstract The linear complementarity problem LCP(A, q) which consists of finding a vector z 2 R n such that Az + q ; z ; z T (Az + q) =; where A 2 R n n and q 2 R n are a given real matrix and an real vector, respectively. This paper proposes an O(n 2 ) parallel algorithm (or O(n) parallel algorithm) by using n processors (or n 2 processors) for solving the LCP(A, q) with A is an M-matrix. Ablock form of the algorithm is also discussed. Introduction We know that the following Linear Complementarity Problem [] often appear in fields of the mathematical programming. LCP(A, q): Let A 2 R n n and q 2 R n,finding one orallrealvectors z with satisfying Az + q ; z ; () z T (Az + q) =: Recall that a matrix A 2 R n n is called a P -matrix if all of its principal minors are positive. It is well known that for any real vectors q 2 R n, LCP(A, q) has an unique solution if and only if A is a P - matrix [2]. Testing whether an n-by-n real matrix is a P -matrix, seems inevitably of exponential time complexity. As it is shown in Coxson [3], this problem is co-np-complete. The time complexity for testing P - matrix problem has been reduced [4] from O(n 3 2 n )to O(2 n ) by applying recursively a criterion for P - matrices based on Schur complementation. For solving LCP(A, q), some traditional methods, including the principal method and the complementary algorithm have been shown [2]. Recently,some authors discussed the verification methods [5] for LCP(A, q), and the multisplitting methods [;6] for large sparse LCP(A, q). If A is a special matrix, it is an interesting problem to show the computational time complexity for the LCP(A, q). Y. Fathi presented an O(2 n ) computational time complexity for LCP(A, q) associated with positive definite matrix A by thetwo well known complementary pivot methods [7]. We know that M- matrices A =(a ij ) n n is an important class of special matrix with satisfying a ii > ; a ij» ; i 6= j; A ; We have proposed an O(n 3 ) recursive algorithm for solving LCP(A, q) witha is an n nm-matrix [8]. In this paper,we will consider its parallel version. 2 Analysis of the Problem In order to introduce the new algorithm,we show the following Lemma at first. Lemma Let A be a M-matrix,then (i) If q<,then LCP(A, q) has a solution z = A ( q): (ii) If q,then LCP(A, q) has a solution z =: Proof: Because A is a M-matrix,so A and for any vector q,lcp(a, q) has an unique solution. If q<,then z = A ( q) ; is a solution of LCP(A, q). If q,then z =; is a solution of LCP(A, q).

63 Next,we consider general case for q =(q ;q 2 ;:::;q n ) T ; with q i < andq j for some i and j. For such vector q,when q,we canmake q < by exchanging the order of two elements q and q i in q. It is to say that we can consider equivalent problem LCP(A, q ): A z + q ; z ; (z ) T (A z + q )=; where A still be an M-matrix by exchanging all elements of st rowandith row,and then st clumne and ith clumne in A. z is a vector by exchanging two elements z and z i in z,and q is a vector by exchanging two elements q and q i in q. For example,let A 2 : q z 2 z z 2 z 3 A ; A A ; then by transforming LCP(A, q),we have the following LCP(A, q ) 4 2 A 2 3 :5 A ; 2 q z 2 z 3 z 2 z A ; A : From the above discussion, we can assume q < for LCP(A, q). Now consider a recursive form of the LCP(A, q), a b A = T ; c A Λ z z = ; q = z Λ q q Λ ; where A Λ is order n M-matrix, b and c are order n nonnegative vectors, a > andq <, z Λ and q Λ are two vectors with the length n. So,LCP(A, q) can be written as a z b T z Λ + q ; cz + A Λ z Λ + q Λ ; z ; z Λ ; z (a z b T z Λ + q )+z T Λ ( cz + A Λ z Λ + q Λ )=: So we have z (a z b T z Λ + q )=; z T Λ ( cz + A Λ z Λ + q Λ )=: divide them to two parts,we get and From (2), or But from a z b T z Λ + q ; z ; (2) z (a z b T z Λ + q )=; A Λ z Λ cz + q Λ ; z Λ ; (3) z T Λ (A Λ z Λ cz + q Λ )=: z = a z b T z Λ + q =: a > ; q < ; z Λ ; b T and (2),we know z 6=,so Substitute (4) to (3),we have Denote z = a (b T z Λ q ): (4) (A Λ a cb T )z Λ + a cq + q Λ ; z Λ ; (5) z T Λ ((A Λ a cb T )z Λ + a cq + q Λ )=: μa = A Λ a cb T ;

64 μq = a cq + q Λ ; then (5) becomes the following LCP( μ A, μq) with the size n : μaz Λ +μq ; z Λ ; (6) z T Λ ( μ AzΛ +μq) =: Theorem μ A is an M-matrix. Proof: We first show μ A still be a Z-matrix. In fact, because A is an M-matrix,so all 2 2 principal minors are positive. Thus all diagonal elements in μ A are positive and off-diagonal elements are non-positive. μa ii > ; μa ij» ; i 6= j We consider the following block decomposition of A. A = A = A = A = a c I a bt μ A a bt μ A μ A a ( + bt μ A μa c a a bt A Λ a cbt a c I a c a c ) a a bt μ A μa ; ; ; I : Because A has no any negative element, so all elements in A μ are nonnegative. μa : μa =(μa ij ) n n satisfies following conditions. μa ii > ; μa ij» ; i 6= j; So μ A still be an M-matrix. μa : 3 Algorithm and the Time Complexity From the above discussion,order n LCP(A, q) can be reduced to order n LCP( A, μ μq), where A and μa are M-matrices. We will consider its parallel algorithm and the time complexity inthissection. Parallel Algorithm : Step. Find the first negative element in q, and translate the problem LCP(A, q) into LCP(A, q ). It is needed for O() steps of comparing and swapping in n processors (or n 2 processors). Step 2. Make A μ and μq from A and q. O(n) (or O()) arithmetic operations are needed by using n processors (or n 2 processors). Step 3. If the order of A μ is greater than or equal to 2,then return to Step. Step 4. Make z over inversing the orders of the transformations. The greatest load of computing is in Step 2, and the sum of the parallel time complexity can be denote as O(n 2 )(nprocessors) or O(n) (n 2 processors). 4 A Block Form of the New Algorithm In this section, we consider a block form of the new algorithm for sequantial algorithm or parallel algorithm. We consider general case for We can block q to q =(q ;q 2 ;:::;q n ) T : q =(q s ;q t ); where q s <, q t by exchanging some elements in q. It is to say thatwe can consider equivalent problem LCP(A, q ): A z + q ; z ; (z ) T (A z + q )=; where A still be an M-matrix by exchanging some rows and clumnes in A. z is a vector by exchanging some elements in z,and q is a vector by exchanging some elements in q. For example,let 3 :5 A = B : :5 A ; :5 3 q = z = 2 2 z z 2 z 3 z 4 C A ; C A then by transforming LCP(A, q),we have the following LCP(A, q ) 4 :5 2 A = B :5 3 :5 3 A ; 2 :5 3

65 q = z = 2 2 z 3 z 4 z z 2 C A ; C A : From the above discussion,we can assume q s <, q t for LCP(A, q). Now consider a block form of the LCP(A, q), where A A 22 A B A = ; C A 22 z = q = : p pm-matrix, zs z t qs : (n p) (n p) M-matrix, B : p (n p) nonnegative matrix, C: (n p) p nonnegative matrix, q s <, q t. So,LCP(A, q) can be written as q t A z s Bz t + q s ; Cz s + A 22 z t + q t ; z s ; z t ; z s (A z s Bz t + q s )+z T t ( Cz s + A 22 z t + q t )=: So we have z s (A z s Bz t + q s )=; z T t ( Cz s + A 22 z t + q t )=: divide them to two parts,we get A z s Bz t + q s ; ; ; z s ; (7) From (7), Bz t + q s < and Lemma,we know z s = A (Bz t q s ) ; (9) is the solution of (7). Substitute (9) to (8),we have Denote (A 22 CA z T t ((A 22 CA B)z t + CA q s + q t ; z t ; () B)z t + CA q s + q t )=: μa = A 22 CA B; μq = CA q s + q t ; then () becomes the following LCP( μ A, μq) withthe size n p: μaz t +μq ; z t ; () z T t ( μ Azt +μq) =: Theorem 2 A μ is an M-matrix. Proof: In fact, because A and A 22 are M- matrices,and CA B ; so μa ij» ; i 6= j We consider the following block decomposition of A. A = A = A C I I A B μ A I A A = B A μ A μ I A B A 22 CA B A C I A CA I ; ; ; A A = (I + B A μ CA ) B μ A A : μa CA μa Because A has no any negative element, so all elements in A μ are nonnegative. μa : and z s (A z s Bz t + q s )=; A 22 z t Cz s + q t ; z t ; (8) z T t (A 22 z t Cz s + q t )=: μa =(μa ij ) n n satisfies following conditions. μa ij» ; i 6= j; μa : So A μ stillbeanm-matrix.

66 From the above discussion,order n LCP(A, q) can be reduced to order n p LCP( A, μ μq), where A and μa are M-matrices. It is obvious that we can get a recursive fast and parallel algorithm. Block Parallel Algorithm : Step. Find all negative elements in q,and translate the problem LCP(A, q) into LCP(A, q ). Step 2. Make A μ and μq from A and q. Step 3. If μq, then μz =, go to Step 4, else return to Step. Step 4. Make z over inversing the orders of the transformations. [8] Lei Li and Yoshinori Okubo, "A Recursive Algorithm for the Linear Complementarity Problem", INFORMATION, Vol. 4,pp ,2. [9] X. Chen,Y. Shogenji and M. Yamasaki,"Verification for Existence of Solutions of Linear Complementarity Problems", Report in Shimane University, Conclusion We proposedano(n 2 )(oro(n)) parallel algorithm for solving the LCP(A, q) with A is an M-matrix by n processors (or n 2 processors) based on a recursive technology. A block form of the algorithm was also discussed. We can also consider other special matrix classes or iterative methods for general case. For examples,positive semidefinite matrix (Convex quadratic programming),nonnegative matrix (bimatrix game problem) and Z-matrix (Free boundary problem) etc. References [] R.W. Cottle,J.S. Pang and R.E. Stone, The Linear Complementarity Problem, Academic Press, San Diego,992. [2] A. Berman and R.J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, SIAM, Philadephia,994. [3] G.E. Coxson, "The P-matrix problem is co-npcomplete," Mathematical Programming, Vol. 64, pp ,994. [4] M.J. Tsatsomeros and Lei Li, "A Recursive Test for P-Matrices," BIT, Vol. 4,pp. 4-44,2. [5] G.E. Alefeld,X. Chen and F.A. Potra,"Numerical validation of Solutions of Linear complementarity problems," Numer. Math.,to appear. [6] Z.Z Bai,"On the convergence of the multisplitting methods for the linear Complementarity Problem", SIAM J. Matrix Anal. Appl., Vol. 2, pp ,999. [7] Y. Fathi,"Computational Complexity of LCPs Associated with Positive Definite Matrices", Math. Programming, Vol. 7,pp ,979.

67

68 A Markov modulated random walk with exponential upward and exponential downward jumps. B-ISDN ATM 98 [] Kella[3] Kroese and Scheinhardt[6] [4],[4]. Sengupta[2] GI/PH/ Rogers[], Asmussen[2] [3],[4] [9] [5] GI/G/

69 2. fm (t)g S = f 2 ::: ng C + U + D C U D (C + U + D)e = e fm (t)g = f i g i2s U,D N U (t) N D (t) i 2 S v(i) v i j 2 S F U ij (x), F D ij (x) U ij(x) = U ij F U ij (x),d ij(x) = U ij F D ij (x) X ord (t) fy ord (t)g L(Y ord (t) X ord ()) X ord () = X() t Y ord (t) = Z t v(m (u))du (2.) X ord (t) = L(Y ord (t) X ord ()) = Y ord (t) + maxfx ord () ; inf ut Y ord (u)g: (2.2) fx(t)g Y (t) = Y ord (t) + Z t B U M (w;)m (w) (w)dn U (dw) ; Z t B D M (w;)m (w) (w)dn D (dw) (2.3) B U ij (w) BD U ij (w) Fij (x) F D ij (x) w Assumption 2. () i j 2 S F U ij (x) = (x )( ; expf;u ij xg) F D ij (x) = (x )( ; expf;d ij xg): U b D U () D() b Uij (x) D ij (x) i j v v() ::: v(n) fm (t) X(t)g fy (t)g Lemma 2. (Loynes [7]) X(t) X(t), E[Y ()] = v e + b U ()e ; b D ()e < : (2.4) 2

70 f b f A(x) A() b x = (x ::: x n ) (x) v S + = fi 2 Sjv(i) > g S ; = fi 2 Sjv(i) < g: E[Y ()] = + u ; d. = (v)e u = U b ()e d = D b ()e: 3. skip free Sengupta[2], Rogers[], Takine and Hasegawa[5], Asmussen[2], Takada[3] and Takada and Miyazawa[4] 3. i j 2 S S C = S,S U = fup ij ji j 2 S U ij > g, S U = fdown ij ji j 2 S D ij > g, e S = S C [ S U [ S D S (+U ) = S + [ S U, S (;D) = S ; [ S D e C U ij > D kl > i j k l 2 S U U j i D D l k u i d k ; UC ( U ), ; CU (U) ; UC ( U ) = ( U ). ( U n ) C A ; CU B (U) u..... u n ; UC ( D ), ; CD (D) S e C e fm(t)g f C ; CU (U) ; CD (D) B C ec ; UC ( U ) ;( U ) A ; DC ( D ) ;( D ) C A : 3

71 8 >< v(i) (i 2 S) Z t+ ev(i) = (i 2 S >: U ) Y e (t) = Y e (t+) = ev fm(w) dw: (3.) ; (i 2 S D ) (3.) X(t) e = L ey (t) X() X(t)g e 3.2 Theorem 3. lim fm(t) = M(t) a.e lim ey (t) = Y (t) a.e lim!!! ex(t) = X(t) a.e: Theorem 3.2 > h i E ey () = ()E[Y ()] () = + u + d > (3.2) 3.3 G i (x) = P (X x M = i) eg i (x) = P ( e X x f M = i) Theorem 3.2 lim! e Gi (x) = G i (x) Lemma 3. (Rogers [],Takada and MiyazawaTM 22 ) i 2 e S e G i (x) eg i (x) = ; e(i)[(i R 2 ) expfxq ge ] i : (3.3) e G i (x) b e Gi () b G() e (ev) ; C e = E[ Y e ()]( + ; U D ): (3.4) js (+U ) j 2 Q js (+U ) j js (;D) j R 2 (ev) ; C e Wiener-Hopf!!! (ev) ; C e I R 2 I R 2 Q 2 = (3.5) R 2 I 22 R 2 I 22 2 ;Q 22 4

72 js ; [ S D j 2 = ( ; D ) (3.5) js ; [ S D j 2 Q 22 (3.5) Q R 2 2 b e G() = c e G C () c e G U () c e G D () (3.4) ceg C ()(v) ; (C + b U() + b D(;)) = ()( + u ; d) ( + ; ) + b(;) (3.6) ceg U () = G ce ()e C U (I + U ( )) ; (3.7) ceg D () = G e c D () + ()( + u ; d) D (;I + ( D )) ; (3.8)! nx b() = D (I + ( D )) ; ; DC ( D ) = k=d ki > D ki D ki + D ki i2s : (3.9) Theorem u ; d < i 2 S x G i (x) = (i)( ; [(I R 2 ) expfxq ge ] i ): bg() (v) ; (C + b U () + b D(;)) = ( + u ; d) ( + ; ) + b(;) : (3.) Remark 3. skip free + x = infft > jx + Y (t) >, ; x = infft > jx + Y (t) < x Z (x) = Y ( x ) skip free Z (x) PH PH 5. Remark 5

73 References [] Anick, D. Mitra, D. and Sondhi, M.M. (982) The Bell System Technical Journal. Vol. 6, No. 8, [2] Asmussen, S. (995) Stochastic Models. (), [3] Kella, O. (996). The Annals of Applied Probability. 6(), [4] Kella, O. (2) Queueing Systems. 37,4-6. [5] Kella O., Perry D. and W. Stadje. (23). Probability in the Engineering and Informational Sciences. 7(), -22. [6] Kroese, D. and Scheinhardt, W. (2) Queueing Systems. 37, [7] Loynes, R.M. (962) Proceedings of Cambridge Philosophical Society. 58, [8] Miyazawa, M. (994) Queueing Systems. 5, -58. [9] Miyazawa, M. and Takada, H. (22) The Journal of Applied Probability. 39, [] Rogers, L. C. G. (994) Annals of Applied Probability. Vol.4, No.2, [] Seneta, E. (98) Non-negative Matrices and Markov Chains. Second Edition. Springer-Verlag, New York, Heidelberg, Berlin. [2] Sengupta, B. (989) Advances in Applied Probability. 2, [3] Takada, H. (2) Journal of the Operations Research Society of Japan. 44(4), [4] Takada, H. and Miyazawa, M. (22) Stochastic Models. 8(4), [5] Takine, T. and Hasegawa, T. (994) Stochastic Models. (),

74 (Tsuyako Miyakoda Λ ' 2+ffl + ' +(ffl=2) a + ' b = () ' 2f'; 6= j' ν j < ;ν 2 Rg, ab 6= ; a 2 < 4b; a> ' = '(t); jfflj < 2; ffl; t 2 R ' a 6= jfflj fi an almost free damping vibration equation ' = e t (2) N 2+ffl N +(ffl=2) ' 2+ffl = 2+ffl e t (3) ' +(ffl=2) = +(ffl=2) e t (4) 2+ffl + +(ffl=2) a + b =: (5) +(ffl=2) = ffi Λ miyakoda@ist.osaka-u.ac.jp ffi 2 + ffia + b =: (6)

75 ( (a=2) + i! = re i (7) ffi = (a=2) i! = re i (8) r cos = a=2; r sin =!; (9) (4b a 2 )=4 =! 2 : () jfflj < 2 = ffi 2=(2+ffl) = ' = 8 < : ( P (re i ) k= ( ffl=2)k () (re i )P k= ( ffl=2)k (2) e Gt [cos Ht + i sin Ht] ' (ffl) () (3) e Gt [cos Ht i sin Ht] ' (ffl) (2) (4) G = G(r; ;ffl)=r S(ffl) cos S(ffl); (5) H = H(r; ;ffl)=r S(ffl) sin S(ffl); (6) jfflj <<, S(ffl) = X k= ( ffl 2 )k ; S(ffl) ß ffl 2 : ' ' ( e Pt [cos Qt + i sin Qt] ' () (7) e Pt [cos Qt i sin Qt] ' (2) (8) P = P (r; ;ffl)=r (ffl=2) cos f (ffl=2)g; (9) Q = Q(r; ;ffl)=r (ffl=2) sin f (ffl=2)g; (2) 2

76 2 ffl ' m+ffl + ' m+ffl 2 a + ' b = (2) ' 2f'; 6= j' ν j < ;ν 2 Rg m 2 Z + m = m =2 m =3 ' +ffl + ' +ffl 2 ' 2+ffl + ' 2+ffl 2 ' 3+ffl + ' 3+ffl 2 a + ' b = (22) a + ' b = (23) a + ' b = (24) 23 ffl ffl = ' + ' 2 a + ' b = (25) ffl =22 ffl = ' 3 + ' 3 a + ' b = (26) 2 ffl =24 ffl = 23 ' () j () = e (a=2)t fcos!t + i sin!tg p p 4b a = e (a=2)t 2 4b a 2 fcos t + i sin tg; (27) 2 2 ' (2) j () = e (a=2)t fcos!t i sin!tg p p 4b a = e (a=2)t 2 4b a 2 fcos t i sin tg (28) 2 2 (23) ffl (22) (24) ffl 'j ffl () (Note) N-ractional Calculus 3

77 References [] K. Nishimoto, Fractional Calculus, Vol.(984),Vol.2(987),Vol.3(989), Vol.4(99), Vol.5(996),Descartes Press,Koriyama,Japan. [2] T. Miyakoda and K. Nishimoto, N-method to fractional differential equations, J.Fractional Calculus, 5,7-2 (999). [3] T. Miyakoda, On an almost free damping vibration equation using N- fractional calculus, J.Computational and Applied Mathematics, 44, (22). 4

78

79

80

81

82

83

84

85

86

87

88 '' ' κφ + u( x) φ = φ 2 = κ φ u( x) φ t φ ( ) = C + C exp( u( x) dx)dx x 2 '' ' f + a( x) f + b( x) f = x), f ( ) x x x f( 2 x k, k, k + f f ( xk ) f 2 ( xk ) ( xk ) f 2 ( xk ) ( x ) f ( x ) f k + 2 k + f f k f k k + = [] 2 u ( x ) = const. [2,3]

89 u(x) h u ( x) = i = L i N f ( x) ( x) f ( x) =, N ( ) ( ) k 2 N = exp( ui Li ( x) dx) i = dx L xk = = ui Li xk = u N i M ( x )= L ( x) dx ( ) 2 exp(m i x ) dx i i 2 d φ dx + 6 x x ( x) dφ ( x) 2 x < 3 3 x < x dx = h φ ( x) ( I 3x + I 3 6) 2 C + C2 I 6 πe 3erf 3x C + C2( 3e 3e I 6 πe = C + C2( 3e I 6 πe 3erf πe 3erf( 2I 3 ) 2 3erf ( I ) 3 ) 29 2 ( I 3) + 6 πe 3erf( 3x 7 6 3) x < 3 3 x < x C,C 2 2 f h '' + a h ( x) f h ' + b h ( x) f h = h '' h ' h = f + a( x) f + b( x f G ( x) )

90 h f, f h h { f () = α, f ( ) = β},{ f () = α, f () = β} G(x) b( x) b h ( x) f f h C max G( x) x C h [5] 2 φ φ = u 2 t x ( x, t) 2 m+ m+ φ φ u + 2 m+ x (, t m + φ x m m ( x, t ) φ = φ x δt δt h u u x t x ) ( ) 2 2 φ x m φ 2 y m+ u u y x ( x, y ) m+ 2 φ x φ δt m+ 2 = φ δt m+ φ m+ m+ 2 ( x, y) φ = φ j i y δt δt m, m+ Pe= Pe=5

91 2 ( ) Pe=5 Pe SFEM 3 Pe 2/3=6.66 SFEM ( ) h 2 u x Max[Pe]=2,h=/3 SFEM 2 upwind []Mickens, E. R., Nonstandard finite difference models of differential equations, World Science(944). [2]Patankar, S.V., Numerical Heat Transfer and Fluid Flow, Hemisphere Publishing Corporation (98). [3],, (994). [4]Ikeuchi,M., Skakihara, M. and Niki, H., Stability of finite element solutions for steady-state convective diffusion equations, Trans. IECE Japan vol. E.65 (982). [5]Protter, M.H. and Weinberger, H. F., Maximum Principles in Differential Equations, Prentice-Hall, INC. (967).

92 = (H n ζ n λh n η n λg n )R n α n λh n+ P n (2.5) BiCG () GP-BiCG [6], [][2][3]., BiCG.,.,.,,,. 2 BiCG (2.) 2., BiCG (2.2) (2.3) 3. R n+, H n+ G n. ζ n η n. R n+ = R n α n λp n, P n = R n + β n P n (2.) H n+ = H n λg n, G n = ζ n H n + η n G n (2.2) H n+ = H n ζ n λh n η n λg n (2.3) BiCG GP-BiCG, r n+ (:= H n+ R n+ ), H n+ GP-BiCG, R n+. GPBiCG : r n+ := H n+ R n+ = (H n ζ n λh n η n λg n )R n+ (2.4) : r n+ := H n+ R n+ = H n+ (R n α n λp n ), 4. 2 GP-BiCG 4.. w n H(λ) n n +., 2., 2 a r n.

93 : GP-BiCG 7 4 H(λ) G(λ) R(λ) P (λ) p n H n (λ)p n (λ)r n n y n λg n (λ)r n+ (λ)r n n + t n H n (λ)r n+ (λ)r n n + u n λg n (λ)p n (λ)r n n z n G n (λ)r n+ (λ)r n n + r n+ H n+ (λ)r n+ (λ)r n + n + w n λh n (λ)p n+ (λ)r n n + 2: 5 4 H(λ) G(λ) R(λ) P (λ) p n H n (λ)p n (λ)r n n (a r n ) H n+ (λ)r n (λ)r n + n u n λg n (λ)p n (λ)r n n z n G n (λ)r n+ (λ)r n n + y n+ λg n (λ)r n+ (λ)r n n + r n+ H n+ (λ)r n+ (λ)r n + n + 3. H n+ R n+ = H n+ R n α n λh n+ P n (3.) r n+ := t n α n w n (3.2) (H n+ R n = H n R n ζ n λh n R n η n λg n R n ) (3.3) (a r n := r n ζ n Ar n η n y n ) (3.4) λg n R n+ = H n R n H n+ R n α n λh n P n + α n λh n+ P n (3.5) y n+ = r n t n α n Au n (3.6) H n+ P n+ = H n+ R n+ + β n (H n P n λg n P n ) (3.7) p n+ := r n+ + β n (p n u n ) (3.8) λg n P n = λζ n H n P n + η n (λg n R n + β n λg n P n ) (3.9) u n := ζ n Ap n + η n (y n + β n u n ) (3.) G n R n+ = (ζ n H n + η n G n )R n α n λg n P n (3.) z n := ζ n r n + η n z n α n u n (3.2)., r. 2 ζ n η n, r n+ (:= H n+ R n+ ) [4][5],, (Associate Residual) a r n (:= H n+ R n )., 2

94 LU. K. [ ] x is an initial guess, r = b Ax, r is random number, β =, for n =,, until r n ε r p n = r n + β n (p n u n ) (3.3) α n = (r, r n)/(r,ap n) (3.4) ζ n,η n = f(r n, Ar n, y n ) (3.5) ( a r n = r n ζ n Ar n η n y n ) ( := H n+ R n ) (3.6) u n = ζ n Ap n + η n (y n + β n u n ) (3.7) z n = ζ n r n + η n z n α n u n (3.8) y n+ = Az n (3.9) x n+ = x n + α n p n + z n (3.2) r n+ = r n α n Ap n Az n (3.2) β n = (α n /ζ n ) (r, r n+)/(r, r n) (3.22) end for. [ LU ] x is an initial guess, r = b Ax, r is random number, β =, for n =,, until r n ε r p n = K r n + β n (p n u n ) (3.23) α n = (r, r n)/(r,ap n) (3.24) ζ n,η n = f(r n, AK r n, y n ) (3.25) u n = ζ n K Ap n + η n (K y n + β n u n ) (3.26) z n = ζ n K r n + η n z n α n u n (3.27) y n+ = Az n (3.28) x n+ = x n + α n p n + z n (3.29) r n+ = r n α n Ap n Az n (3.3) β n = (α n /ζ n ) (r, r n+ )/(r, r n ) (3.3) end for γ Toeplitz., b =(,,, ) T. γ

95 55,. 2, 2 [, ] 2 : (A(x, y)u x ) x (A(x, y)u y ) y + γb(x, y)u x = F (x, y), B(x, y) =2e 2(x2 +y 2). A(x, y),f(x, y)., x, y N 5 (N ) 2. γ... N 257. ILU() GP-BiCG.,, r n 2 / b Ax 2 2., r =. VPP-5 PE ,.,, GP-BiCG GP-BiCG. A = 2 2 γ u= u= F = 2 u= A= 4 A= 5 A= 2 u= 3: Toeplitz 2 () GP-BiCG Toeplitz : vdv : r = (E =log ( b Ax n 2 )) (E) GP-BiCG -8. E< E< E< E< E< E< E< E< () -.56 (-.63) -.93 ().566 (.97) (.4) : vdv : r = r (E =log ( b Ax n 2 )) (E) GP-BiCG -7. E< E< E< E< E< E< E< E< E< E< () -.47 (-.6) -.86 ().64 (.9) (.) 33. 4

96 CPU Time Toeplitz Matrix, n=6384, CPU Time(sec.) Present GPBiCG CPU Time van der Vorst problem 4, n=256^2, preconditioning Present GPBiCG Gamma Parameter Res=Log( b-ax _2) : Toeplitz : γ vs. CPU () van der Vorst problem 4, n=256^2, preconditioning, random -8 present Parameter Res=Log( b-ax _2) 2: vdv: 2 CPU () van der Vorst problem 4, n=256^2, preconditioning, random -8 GPBiCG Parameter 3: vdv: (r =) 4: vdv: GP-BiCG (r =) van der Vorst problem 4, n=256^2, preconditioning present van der Vorst problem 4, n=256^2, preconditioning GPBiCG -9-9 Res=Log( b-ax _2) Res=Log( b-ax _2) Parameter Parameter 5: vdv: (r =r ) 6: vdv: GP-BiCG (r =r ) 5

97 3, GP-BiCG 3/4.., ,.., GP-BiCG,.,. 2.,. 3. r, r, r = r, (.566/.64=.937) (= H n+ R n ) BiCG.,,,.,, ()., BiCG, (= H n+ R n+ )., BiCG. [] Fujino, S., A remark on sequence of polynomial of Zhang s product method, The proceedings of SCAN22, Paris, Sept. 22, pp [2], BiCG, 22, 22.9, p.32. [3] Fujino, S., Complexity on the order of polynomial sequence used in GPBiCG method and its effect to convergence, Trans. of INFORMATION, 6(23), pp [4] Gutknecht, M.H., Variants of Bi-CGSTAB for matrices with complex spectrum, SIAM, J. Sci. Comput., 4(993), pp [5] van der Vorst, H.A.: Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems, SIAM J. Sci. Stat. Comput., 3(992), pp [6] Zhang, S.-L., GPBi-CG: Generalized product-type methods based on Bi-CG for solving nonsymmetric linear systems, SIAM J. Sci. Comput., 8(997), pp

98 Ã!"$#&%'!)(+*-,/./, ,/ FGHJILKMONJPRQJPJQJS<TJUOVXWOYJZJ[JQJ\^] _J`BaJb KMcNJPJQJYJZJdJeRf<gJhOi^] jlknm opqrsut+vwxyzu{u ~}u+ ƒu u + + ˆ Š ŠŒŽ & Šš œo ž& Ÿ O E ƒ Š7 Ÿ E E 7ª «7 c ƒe E± ƒe Ž ²E ³ ƒ Œ ƒ 7 µ ² Ÿ E 7 t7o peqeres ƒeȩ¹eº Ž7» ¼ ze½e¾ Š E 7œÀ ƒ 7 ÁE Ã7ÄEÅ Æ 7µ Ç7ŸÉÈEÊEÈ ËEÌEE Ž EÊ EÍcÎ Ã7Ï Ç7ÐE 7œÉÑEÒEÓ ª t Ÿ 'ˆ E ƒ }EÔE E}Eº Ã7ÕEÖEÆ 7µ Ç ƒr ÙØÛÚÝÜÞÜÞß àþá Š â ã ä å ŽÍOÎE Ÿ ƒ ä å à ÈEË 7ªEæEç Ž è Ä»Eé ê ƒeëeìeí ÈEËEÌEE Ž ˆ ÃîEï Æ 'ð ñ òôóöõø ù ú ûcü ý þ ÿ þ ÿ! #"%$&'()$ *+,-./ #9: þ ÿ 5;<%=%>? þ ÿ 4 9@%AB%C $EDFHGJILKNMPORQLSUTV"XWYQJZ[ T\IRSX]VT^SU_PG[Z 9 ` a #"b$ 4Xcbdfeg5 * 7ih jlki/ nmoqp, 9o br rnsrtbuwv xzy {V }D!~I ^GJ]V Pƒ T^SUTiH_PGJƒ T ˆ 9 `%a ~U 4Šc%dweŒ - 587Žh%j8kŽ/2m ~U -% %% þ ÿ q X %*2 þ ÿ2š2 - d mœp. px9 bž Ÿ~U - 5 b 5. +V, j þ ÿ >qp, b L mbo/ `ª Eþ ÿ >qp, ~U - «h d 4Š9 - % 9 ±² =25³ ü - 5 µ / 9 -,2¹ #"º$»%¼ 5 ½ ¾ j 3 45 ÀqkŠ/, j Á m k 9bo Â% 5ÃÄ/ Å9o Æ ÿ%ç %ÈÉ 5 Ê 345 6jm oÿ3 9ËfÌºÍ œ 9ÎfϺРþuÿñdóòz P PWUGÕÔ[ ]nqlsut ~NÖz ØT\WY T 9 `aúùû^üþý 4Šc dee ßà 7 $ áqâ px ãä åõ æl mçî Ï Ð þ ÿ - 9 ÒŒèÓé ê Ç DÓÒŒè GJW SU_PGJOJGJIQëƒ ì QLSU GJI e ßà Ð þ ÿí Žîðï o %¹ Î Ïbd b þ ÿ ñ òbó d $b moqp, 9 ô%õ25 þ ÿ 4 þ ÿšö þ&üø 2Å9 Æ ÿ%ù¹úû%üø $% m % 9 Ð þ ÿ ô%õ tu2 þoü2 4Žýõþ84ÿ 5 p ž% ü j n 9 sbtbuw 9 d ü nîbï ž 'þ ü jb9 ýrõ þq4 ÿ ø 5 nm ž 9 - % Ä/% ½. = 8 j ¹% 9 n=r kv.nå!b< p,"w 9Vo n= * ¹ 8 j84 o/ 4 Oü pš9 o = *2 ¹ ù2 j4 o # - (%$ & 4Žj ' (Eþcü m 3 ' ( *),+.-//32546 D879 9: ;< = e 4 >@?Þ/%9A= B),+.-//32546DCE-GF5HI+.JK4LMH%NKJKF5OH D `a 9 SUGJƒ 4Šcd eþ4p>a?/2mð þ ÿ îðï 3 * Î Ï d 5 QPT\IPì\ 4 QSR MP]nQŽ * Òz~NÖz % å m k 9κÏ% -œº º ôºõ º$œUTWV p 9 #" $2»¼ X < Ç %Y + ¹ 5 Z@P[ \8k %* ] ÙÛ^ÜÞÝ D8X < Ç Î%Ï%Ð þ ÿ 9D^ SYQ`_P ƒ ì\t Z èòz~nöz e æõ 4a>b?ç/œ fººÿ Þm2ÄÞ º9 ckf4 Udfœ 9 e _QëWY Y_PT\IP JG k ¹Òz~NÖz zèò $ fl 4a>@?Þ/2 %º g%h p, j2%5þ9o ô%õ $2 ^ Òz~NÖz $ 4 i24 jlk Zl m k 9mn Z[WUGJ P P IPOŠ j, 9 ÎrÏr -oqp!#w r¹ zr8z[wugj P P IPOi $þ GR NS è s ƒ SUT\WYQLSU GJIºD Î%Ï% -%# t eþ4 >@?/2 %$ 5%i u Zvw ghq /, j xl fl m p. p ü 5 kx9 o y z < / { D~} 9 r e p. Å kš/ ƒ 9[\ P ¹ GR NS è s ƒ SUT\WYQLSU GJInš ž ˆ p, j ü jm ËÌÍ 9 GR NS è s ƒ SUT\WYQLSU GJI * ÎÏ - # ü 7Œ9bÎÏ - 9Š ¾ Z[WUGJ P P IPO þ j ü 5œkUZUv ; p j Z[WUGJ P P IPO¹þ üœ D `a 9 3 ' ( *)-GO,Œ3F5HU),+.-// P> e g h d m 3 9 D! eî Ï - * važ 5 / 9 D! e #"%$» ¼ Ä () 2¹ù 2 d29 o8p, 9 D! e ½% 5 ø kž/ Å9 v žoü% Ž 2 Å ÿ Žþ ¹ &ü 7, 9 ü k 687 /% : š d2m% 9Ë%ÌÍ œ h8pš % y ² þ ÿ d ž, >qp, [lpxj»b¼ ùlÿ m 5 / mþë b 9 pij Û ] ÙÛ^ÜÞÝ D!~]V PWUG. JT Z ^ Òz~NÖz e wøn 4 = y pš9o ù ª dm «± ±² ³ µ >?; <= þ ÿ þ ÿ ¹ lº D å Q ã e œ #"Þ$b - 7 3w4 d Vm3r3 9 Éùw»P¼½» ; þ ÿ 9 ¹ 9 ºŽEù D» -" *¾ ÀÁl ² 4Žd2Þm3 4 9 #" $2 õ $œ `%a %*2 /m%仼 Å <=4Šd m Æ ÇPÈqÉ Ê Ë É Ì Í

99 ! '! $ & & ' $ &,,, &, à Ú/Ø!#" " " $ % & % %!')( & % *+ % ' %,.- %/$ % % %,.- % $ % + % ß 2 2 %, ( ;: ÚÝÜ < % & %,.- %,.-=')( & % %!' %,.- %,.->/ < % %? à Ú/Ø 3b3 9 bbíd å Q ã 4ij ü 9 D å Q ã e DÀ «9Ẽ ü ; þ ÿ} F m3 þ 4P>A?/ m 2 ¹ bº '( 'þl mnd D å Q å e # þ ÿú2 wgj = GK 5MLGN d * b þ ÿ :ž? 9 #"b$» ¼ ù 5 ù OQP /m þ ÿyr% yù2 S% 2Å 9% l2 o Ä Äô õ d 3 4 ü j m k 97T nb D å Q å ez4vubw ü bb X9Y pi9þo nb >p, #"%$ «hdm #"º$ õ $ `a * & m%仼 Å <=4Šd m Æ Z\[M] ^_@ÇPÈDÉ Ê Ë É Ì ` > à > Qa Ú/Ø!#" " " $ % & % =a %b')( & % *+ % ' %,.- %/$ % % %,.- % $ % + % ß 2 2 %, ( ;: ÚÝÜ < % & %,.- =a %,.-c')( & % =a %!' %,.- a %,.-./ < % %? à Ú/Ø d egfghgigjlk 3---,/m n5o=p qsrstsusvswyx{z} }~ss s þ ÿqj= K LN P& $ 4 p, 9 %% þ ÿ % þ ÿ 2 Ð þ ÿ Î%Ï : $ 5 mw3 * +n,}2 wm Gƒ þ ÿ Î à 9 J= ã Î LQNdm%ÎÏÐ þ ÿ * q Ð þ ÿ Î Ï - dm Ñ 9 ) Þîðï ld;ˆ îðï e D æ Q ã e 3b3 9 f mg BŠ þ ÿ 9 >GŠ þ ÿ 9 º ŒG þ ÿ 4Xd mþî Ï Ð þ ÿ D ÙÛ^ÜÞÝ e õ $ ` a Ž d å m ÙÛ^ÜÞÝ -+y Ø ã š ~»\ ã œ ž Ÿ H 4) -+ -+y Ø ã š ~»\ ã -+ =. ã š ~» ã œ Ÿ H 4) > ã ; å š ~»\ ã œ ª ï Ÿ œ Ÿ œ Ÿ H 4) -+ H 4) -+ m õ $ r n 9 œ Ÿ 'þ ÿ º «â 'ÿ 9 >BŠ þ ÿ «± â >GŠ 9 R šþ d m œ Ÿ m ²G³ D e Mµl p d m a7 Vw 7ŗ œ Ÿ ¹ w ôbõ w 9 º o%ž2 Ð þ ÿ ÎÏ -Q» ¼ 5\½kŽ/m}¾ 4 9 þ ÿ2yq %yù}à\sáqâ}ãqä ÅGÆÇÃ\ÈÉËÊ Â Ì\ÍÇÎ Í}ÏÇÐ Ñ\ÒsÓ ÔQÕÖÇ ØÙËÚ ÛÇÜ Ý ¾ Î\Þß ÀÇàâá ãåää+æèçéêå Ì Í Î ¾ ë ÀÇàâá ãåä7ì!ãîíèïðá ñ çò ïôó ñ íèõï 'þ ÿ «ö GøGÅBùcú û ë ügýÿþë Ý ø Åàâá ãåää+æèçé Þß Û9Ü ë ø ÎÏ Ä GÜ Ý ãåá æ #%$&('! "! " '! #!*) #%$!./%" #%$&! " ï±í2!ï '! #%$!./%" 3 ï±çàÿæ ï±çà ãåá ùcú û +-,! " #! þ Â98ËÊÅ #%$! " ;:9<(=?>A@ #! " Î;BDC E?F\Î\ÕQÖ ë ý ÜMÝ ¾ ÎHG I J9Ä ÏLK Ù ½ Ú Û Â :*M ën À OGÔGÙ ÅQP R S :DT HU VyÓ Û ÜMÝ Â 8 Ê Å ¾ Î ÞGß Ä Ï9Ð : N ÎHW XGÕGÖY HZ9ÎMÍ Ä GÜ ë [ ÚH ÔGÝ \9ÎH] ^ Å`_ba c Îd e f ÄHg h i jgümý \ ¾k Å lgé m}à n Ü Â9ÃGÄ Gø9Ä 4 ø þpogý Ï lé m G I q : 4srutvwQx þ y zsó Û Â { 5~} Ý { rutvwqx 9} ãåრ-" ï±çà ãåá ãåრˆ! "! ãåá C 3- $ ˆ Š! " $ ï±çà ãåá ãåá C 3Œ3,Ž

100 ' $ $ X " ' þ $ $ X " & ' $ $ S Ç!./%" $! " & ' '! ï±çà ãåá ï±çà ãåá ¾ ÎHG I J k Å W X : N ÎMÕGÖ9 HZ}ÎMÍ k Ü ¾}ë sóû}ü\ý Ê K Ù Å G9I J Ì\Í ùcú û Î\Í}Î Ò Ä Ú lqésê Ù k Ü Ý ÂQÅ 9:}Î fç  Û}ÜQÎ k Å P9R S Î ÇÎ ÔÝ "!$#&%('*)+,%.-/23%245!$687:9<;>=@?>A>B>C>DFE G IH5JIK ÎL c Ä Ï KôÙ ½ ÚVÛ Â P R S : À \ Î 9: M9Î\ÕQÖ ë Ê Ù9OÔ Ä\Å G9I J M 4ON ÐQP Ê SR>TVULW YX þ Ä Bø ÎBÏ[Z û ù:\^]:_ `2a ë b Û}Ü Þß À ÓÚ Ä ¾}ë ÑHy zsó Û Â { c } { d } Ý ãåá C æ $! ) $! $ ï±í2!ï! $ 3! ùcú û + 7! "! þ ï±çàÿæ ï±çà ãåá ¾ Û9 >e ú(f*ù+ Z û ù:\^]hg ù:_ ú&` ë b Û}ÜMÝ P R S :9Î i jqõqö W( kçüqî k Å_bac Î l mon"p q  Ð\Î rs9 tvuü\ý G9I 9:} QÏ}Ðw xy Ä Ü Â Ã lsm pzw z{} GÜ Å ~ BÌMÍ ùcú û + 7 Îz Ä Ï Ð Å d e k Î rs y }Îztƒ só Û}ÜMÝ I!$ Iˆ +5-[ I/2!ŠQ 4 6IŒ y z ý Ü _ e ]cúž&\* G IH5JIK k Å G I J ÎÕ Ö $! " Àz S ý Ü ëz.]cú e2e _ `2aÀ 7 ph Ý Á Î.]cú e2e _ `2a ë ÌMÍ ùcú û Îz  ýs z ÎGÏ Ä BÜMÝ, 6I š ì!ãîíœ ž Ÿ š $! " ª «4 ø '! 7 6 Î ë Î7ÌÍ ùcú û +-,Ä Ï7Ü Ò Ó Ô7ÕBÖ Î ± ë² É ø ÎÏY Ä Û}Ü Ý ãåá æ ùcú û + 7 '! ) æ #%$&('! "! " '! # ùcú û +-,!*) #%$!./%" #%$;&! "! " '! # ï±í2!ï! 4256 c þ #%$!./%" 3 ï±çà æ ï±çàÿæ ï±çà ãåá ³ Á Î PLR S[ G IH5JIKÅ e ú(f*ù+ Z û ù:\^]hg ù:_ ú&`á G IH5JIKÅ êú&µ2 û \.]cú e2e _ `2aôÀ H, e ]cúž&\* G IH5JIK Î G I q :}ÎU V¹º} ø ÎÏ Ä ë Ã Ú Û}Ü Ý SAI NV SAI NV- pf I SAI NV f or i =,», n- f or i =,», n- f or i =,», n- ¼½ ¾ dr oppi ng end f or t ol - t - M= Z D Z Å Æ ÈÊÉÊËÊÌ dr oppi ng ¼ ½¾ t ol - ÁÀŠÂÄà end f or ¼ ½ ¾ post f i l t er at i on t ol - 2 doubl e dr oppi ng ¼ ½ ¾ t ol - 2 dr oppi ng ¼ ½ ¾ t ol - end f or t - t - M= Z D Z Å Æ M= Z D Z ÅÆ ÍI Î ÏÑÐÓÒÓÔÓÕ ÖÏÓÐÑØÓÙ WÍÚÇ Û ÜÝßÞ ]:_ \ Þ úàá\^]iâ(ã 4, 6 5 aäiå þ Î nþ$æ k K Â Ý Uçèéê ëè ìí} _ ìí À î O Ê Åðï Ä LÛÜÝ _ôóšú& e _ û \^]$Ž&\^]hf _ ú&`zã 6 5 À OBÔ Â Ý S ýsõ ÙSö SøSùS k K Â Ý _ba c ÎHd e ² Éúû zü Wýþ ÎÍ, > Bø Î ëz ë Ê Â Ý9 J ý õ Ù, ë QÜQÏ( Ä\ÉÇÃÅ QÍ! yqù ë Ê Â Ý" lm p WÇ :ÇÎ $#W ë&%(' Í ë Ê Å \ ) k À&*,+ K Â Ý :Ç yù9w X ÀD, Ä Z - mëê Â Ý Qø}Ä. ÔÙ Å #ÇÎ;G I9q : P R9S G IH5JIKÅ e ú(f*ù+ Z û ù:\^]hg ù:_ ú&`àz~ O Ê Â G I q : P R G IH5JIK + e/ Å y z ý Ü êú&µ2 û \I.]cú e2e _ `2a À G I q : P R S v rutvwqx ë (&2 ý Ü Ý G IH5JIK k BÌ Í ùcú û +-,À( 6 (ã43 6, ã k 6,6587 k,ž, Ý Ð:9 m Ó:;  Ý=<8> Å G IH5JIK + e/ ë v rutvwqx k Å ÌÍ ùcú û +-, %? Ä ë Ð Å B 7 EƒFÎBÌÍ ùcú û + 7 ÎMÍ9 Å G I J BÄ OBÔ9ÜHB, EƒFMÎGÌÍ ùcú û +-, Î ÍÇÎ öa@, 6 CBã 6 ö k ÎÍ À 6 ã 5$7 k y ked ÝyÐF9 m ÓF; Å < Á ÎLR > : Ä W Ê Ù ^ DD Ý ÐÎGÌÍ Î ël Î _ba c ÎLSr}s ÄÁ ÔGÙG õ Â Ý ÍI HJIÓ?LKÓ=LMÓBON PRQTSLU U8V J8W Î ŸX[Z Ú \9KÙ Â R >L: Î=]? ë J Ô Â[^=_ À,Ä o7ý Ý L:a` _ G2Gb c 7 c d g ù:]:_ e d g ]gf&\šù { â } Z Ú Å :h` _ G2Gb c 5 ãi % J G Icj~ cki % J G Gl ` nmsç oqpz r {, } Z Ú Å : b s `æ,+ 7 i % G d b l 6 c ú&µut2_ogp{ j } Î t ú& \ e g a&\vz ÚQ [8p w ëç Ox Ê ÙÚ Ä î O Ê Â Ý ÍI yjzl{l 7 Ä Å : Ä W Ê Ù}Ì Í(}&9 m ÓT;  ë rs &"}Ñ t Z K  ] ^}Î&~ (} oý Ý GÄq. ÔGÙ Å Þ ]:\*óšú&` 6 P R SÅ7ùcú û +-,ī ùcú û + 7

101 : #W ijõö ^&_ 4 W þ ` _ G2Gb c 7 c 5 ã d 7 â, j 5 d! Í ^&_ ` _ G2Gb c 5 ã j j c 7 Ž "$#%&' ÎUV JW J G Icj~ c cj~ c ãcj 5 J G UV J G Gl ` ãc(âcj~, 5 d&dž D j)(* T>$, - b s `æ,+ 7 7,^c D â c ã D 7 jj - ò./,îuv JW G d b 7 ã j,,*â&â D cjj >éë - Á ÎGÌMÍ ÎMÍ ÅS]hg,+ i&]hg 7 + z :32. Ï54 rutvwqx k6 Õ879Lo;: Ä W ý Ü ÅðH;ù:\^] l m p W Å Þ ]:\+ ù P R S Î rs ÅH;ù:\^]+ ù _ba c Î d e k Î ð r[s Å b úù+ ù Q^ð r[s Å ]hg ù:_ ú + ù G IH5JIK Hd e k Îzr sn}, 6 ë Ê Â ëz Îzr sbîl[} ý ÝLS r}sbî=<?> ýsõ ÙA@ k} ÜÝ ÂÅ 5 Ä ³ Á Î P R9S ÎÌ\Í}ÎB ^$;(}&9  ^ DD ÝyÐMÎC+ Î5D?E7C9JoF:9ÎL ë D?ESr s G&} oý Ý G IH5JIK k y k,ž, ÝsÐ ÎD8EÍ k Ü\Ýn ÎIHJ k Ê W8J} K8LIM IN Ú Û}Ü+ k Ü Ý 7 ë 5 Ï Ð Å GÎL: Ä W Ê Ù Ñ Å=O ÎGLI q 9: Ä õ Ù v rutvwqx y ÇÎ ðr s9 tqô ) ë Z ÜÝ ± Ä Å êú&µ2 û \Q.]cú e2e _ `2a }CP ÊV v rutvwqx y }Î rs} Q Ä 4 rs ú 6 j 5 BRTS UWV þ k ËÓ ;  Ý<$> Å G IH5JIK + e/ k IM ( K  u$nëú Û\Ô ) ë IXÔQÝ 9:ZY ë ÄI[\ Î?8] }I^8_ ý Ü ë Å 9: b s `æ,+ 7 k Å l m p W C`Sk ÊVÂ Ý : G d b k Å lsmss ÎLr sb Ð [\ Ó Û( Z K  ŠP9R9S Î rsq uk Ê Â Ý : J G Icj~ c k Å lm plw9îzk9îzø ^ \ÒsÓÔa\ÛG Ñ Å P9R S :ÇÎ ijqõö W ( Ô Â}à y ÇÎ rsq ` k Ê Â ÝyÓQÚ Ä Å G I J}Ä 6 Õ79Lo$:}Ñ Q Ä k Ê Â Ý n,5äå : J G Gl ` Ä W ý Ü G IH5JIK + e/ Ä. agübìmí ùcú û +-, ë ùcú û + 7 ÎMÍ 4 ùcú û +-,5Ä W ý ÜLön@ k oÿþ Y ë ÎzrsGÎ b } ogý Ý %q? Ä Å3nAcdcîÄMÅ : J G Gl ` Ä W ý Ü Å y z Ê Â v rutvwqx Äq. aqüqì\í ùcú û +-, ë ùcú û + 7 Î\Í 4 % ö$@ þ Y ë Î r sqî b } oý ÝÔ ÛÇÎ n k Ñ Åe Ó >ZfÎIgÇ r}s {@ } }q ý Ýð ÂGÅ ÌMÍ ùcú û +-, MÍ }\9Î F$h Ä ë Ð Å Ì Í ùcú û + 7 Ì Í ùcú û +-,VÄ W ý Ü ö@ }F$h Ä ë K Â Ý n, Ï Ð Å G IH5JIK + e/. G I J k OBÔ ÜBÌÍ ùcú û +, Î Í \ÒËÓÔ ë yð ÇÎ r s9 t Ô ) ë 9 Z ÜMÝ q ÄÅ ÌÍ ùcú û +-, ÎMÍY z Ô ëz Å r}s IiÓu;ÜIjf Ü\Ý \ÇÎ ÂÇà Šr s &"ÇÑ tqôçì\í ùcú û +-, Î ë Ä e ú(f*ù+ Z û ù:\^]hg ù:_ ú&` };? ë rsq { Ük$@ e ÔQÝ ÂÅ y }Î r s Äq. ÔBÙr}sztSƒ9Î5MS Y ClGÛ ÜGÎG Å ÌÍ ùcú û + 7 Î Í ÌMÍ ùcú û +-, ÎMÍ}Î, 6 ã ö Z Ú 7 6 ã ömø9î Í } ë Ü ë k Ü ) ë Z Ü Ý ÓGÚ ÄMÅncdc Ï9Ð Å v rutvwqx k GÌ Í ùcú û +-, ÎMÍ Ä Ï9ÚQ ys 9ÎLSr s Ltƒ Ó Û Â ) ë Z ÜMÝ \ÇÎ k Ñ Å r sqî t ƒ Ä "}Ñ h9i Z K  ë QÌ\Í ùcú û + 7 Î\Í( QÌ\Í ùcú û +-, Î\ÍÇÎ 5 ö Bã ö?msø ÎÍ Î ël k} K  Ý?o Î ) ë Z Ú Å êú&µ2 û \.]cú e2e _ `2a Î! M f Z ÜMÝ p qsrut lgé m G I q : Ä ÏGÜHG I J Î k.]cú e2e _ `2a } ôø` v rutvwqx P`R`S } ỳ z Ê Â Ý \ Ê Ù Å v rutvwqx Å G I J Ä Õ ý ÜLSr}s ë _ba c Î d9e k Î;^ r sî tƒ Ä. ÔQÙ Å M O( Ü ) ë }8v}Ú ZÄ}ÊÂ Ý ÂÅ < Ä rs Î t ƒ 8 a k u Å 6 Õ(879ao$:ÇÎ k Ä Ñ M Y Ü ) ë Z K Â Ý ÓÚ Ä Å.]cú e2e _ `2a k î O ý Üz Á ÎGÌMÍ 4 ùcú û +-,ī ùcú û + 7 þ ÎY +MÅ ÌMÍ ùcú û + 7 Î\ÍÇ Ì\Í ùcú û +-, Î\Í}Î 5 Bã ö8møçî Í,}w Û b rs &" Ä Ü ) ë Ñ Z K Â Ý xzys{u } ~ =ƒ ˆŠ C Œ =Žˆ š œž ˆ Ÿ ; Ž š ª ˆ ž«ÿš Œ ˆ ± ² ³ ; Ÿª ˆ µ ² ˆ ¹ ˆ «d~ ºŸºŸ» Œ }¼ =ƒ ˆŠ ƒ Œ ½ ¾ «½ Œ ÀŒ ½ ÂÁ à T Œ T š Ä š š ňà ƈ ¹ š Ÿ Žˆ ˆ Ÿ ƒ Æ Ÿ œžá ǹ Ç ŸŽˆ ±À; ŽÈ µ É Ê ÌËŒÍ Ÿ µ ˆ ± ˆ Î ¾ ƒ Ÿ ;š Á³ ˆ Ç Â~Ï Ðž~ ºŸºŸÑ¹Ò dš š Œ ~Ÿ~»¹Ó Ô ~Ÿ~ Õ¹º Œ }»=ƒ ˆŠ Œ ƒá ª ª Á = ËŒÖ$Œ Æ ÂÁ à Œ ŸØ Á à š š ňà ˆ ¹ š Ÿ Žˆ ˆ Ÿ ˆ Çn = Ÿ œžá ǹ ÊÇ ŸŽˆ ± ; ŽÈ µ É Ê ÙËŒ Ÿ µ ˆ ± ˆ Î ƒ Ÿ $ š Á ˆ Ç d¼ÿ¼ Ð ¼ ÚŸÚŸÚ¹Ò dš š Œ ~» ~ Û Ô ~»Ÿ»¹¼±Œ }Õ =ƒ ˆŠ È Œ d ÂÁ à Œ Ü ŸØ Á ƈ Ÿ;š ª Ê Š ³ ˆ ˆ Ÿ?š Ÿ Žˆ ˆ Ÿ $ ;šd ˆ ˆ ¹ =Ž Î ˆ Äà ³ ˆ ²Á ; ŒÝ ˆ Œ ª ÇŒ š š ªŠŒ ºŸºÐ ¼ ÚŸÚ ~Ò dš š Œ ~ Ô¼ Ú Œ }Ó ÃÞ8ß;àâá? T = ³ ˆ Ån = ã¹ ¾ä;å8æIçÃèIéIêIëâìIíIî ïðñò óô5õö öøùúûü? ¼ ÚŸÚ¹¼±Œ» Œ }Ñ¾Ö ã¹ µ ŒýŒ ¾þ ÿ ¾3 ŸØ Á n É «šd ; ŽÜ â Ÿ ³ Á ˆ Ç š? š š ňà ˆ ¹ ½š Ÿ Žˆ ˆ Ÿ ˆ Ê Š Ž = ²Á ; Œ Ý ˆ Œ ª ÇŒ š š ªŠŒ ÛÐ ¼ ÚŸÚ ~Ò dš š Œ ~ Ñ¹Ó Ô ~Ï º Œ }Ï ¾Ö ŸÁ ˆ ýœ µ š F = ³ ˆ Ø=š ÇŸ ŸŒ ±³ š Œ Á ŒÎ²ã¹ ŸÁ ˆ š ŸŒ ± ;ª }ÛC = ³ ˆ ÅC = ã¹ Æ Ø=š ÇŸ ŸŒ ±³ š à Œ ˆ ŒÇŸ Ÿ = ³ ˆ Å = ã¹ }ºC ¾ ˆœž ˆ ãd WËŒýŒ Ÿ 5Ž ½ FŒýŒ 5ˆ ˆ ¹ Ÿª Á ˆ Ÿ ;; Ž ƒª ˆ ž«æ ˆ À ; ˆ ±Êà ³ ˆ Å=ˆ ž«;; ³ ˆ à ³ ˆ ÅÈ È = à ˆ ½ ƒ Ÿ;š Á ˆ Ÿ» ~¹Ðž~ º¹ÏŸÏŸÒ dš š Œ ~ Õ¹Û Ô ~ ѹ¼±Œ } ~ Ú= ² ˆ ¹ ˆ «Wª ˆ Ž µ š = ³ ˆ ÅZ Ø š ÇŸ ŸŒ ±³ š Œ ˆ ŸŒÁ ÂŒ ŽÁ š à ³ ˆ

102 ! #"$&%(' ) *,+-./ d g ù:]:_ e Þ ]:\*óšú&` 6 ùcú û +-, ùcú û + 7 ]hg,+ ]hg 7 + H;ù:\^] 6 Þ ]:\+ ù H;ù:\^]+ ù b úù+ ù ]hg ù:_ ú + ù G IH5JIK 6 D â 6,, 6 Ž â D j, D 6, 5,Ž, 6 â c, 6 Ž ` _ G2Gb c 7 c G IH5JIK + e/ 6 D 6 D â 6,, 6 Ž â D j, D 6, 5,Ž, 6 â c, 6 Ž v rutvwqx 6 (ã 6, 56 d 5 RTS U2 ã â&â 6 â(ã d 6 j ã j 6 dž 6 d c G IH5JIK 6 &d c 6,*â, 6 Ž D c D j c 56 â,ž, ãc,ž, D â, 6 Ž ` _ G2Gb c 5 ã G IH5JIK + e/ 6 &d 6, ã c 6,*â, 6 Ž, 7 5 ã c 56 D, Cj~,Ž,Ž,^c 6 D 5 v rutvwqx 6 Cj 6,^c 56 d 5 6 âcj jd D,, j 6 7 âž, â,*â 6 d&â G IH5JIK 6 &d c 6 j D, 6 Ž, 7 D 6 D,Ž, 6 c, 7 6 5, 6 Ž J G Icj~ c G IH5JIK + e/ 6 &d 6 D c 6 j D, 6 Ž, D ã 6 D, 6 â,ž, 6 j 6 D ã v rutvwqx 6, 5 6 c ã&ã 7 6 â&d 6 dž â D d 6 5 ã 6 d D ã 6 DD RTS UWV G IH5JIK 6, âž, 6 Ž jjd, 7 d 6 â,ž, j ã, 7 5, 6 Ž J G Gl ` G IH5JIK + e/ 6, 7 6, âž, 6 Ž jjd, 7 d 6 â,ž, j ã, 7 5, 6 Ž v rutvwqx 6,Ž, 6 c D ã 7 6 c 6 âcj d&â 5, D 6 7 â&d&â â&âcj 6 j 5 G IH5JIK 6, 5 d 6 j,, 6 Ž cp, 5 c c D 6 d 7, 7 7 d,, 6 Ž b s `æ,+ 7 G IH5JIK + e/ 6, 5 6, 5 d 6 j,, 6 Ž cp, 5 c c D 6 d 7, 7 7 d,, 6 Ž v rutvwqx 6 (ã 6 7 ã 56 d 5 6 ãc 7 (ã, 6 D,Ž, D, 5 RTS3 R G IH5JIK 6 &d, 6,*â, 6 Ž D 5,^c 5,*d(ã 5 &â, 6 Ž G d b G IH5JIK + e/ 6 &d 6 &d, 6,*â, 6 Ž D 5,^c 5,*d(ã 5 &â, 6 Ž v rutvwqx 6 (ã 6 Cj ã c 6 c ã RTS UÂU â 5, ã j, ã 7 Cj 6 dcj 45 6! 78 9 : <;=;?>&@ AB C D "$&%E') EC D./ d g ù:]:_ e Þ ]:\*óšú&` 6 ]hg,+ ]hg 7 + H;ù:\^] 6 Þ ]:\+ ù H;ù:\^]+ ù b úù+ ù ]hg ù:_ ú + ù G IH5JIK â 6,, 6 Ž â D j, D 6, 5,Ž, 6 â c, 6 Ž ` _ G2Gb c 7 c G IH5JIK + e/ j 6 D â, 6 Ž 7, 7Ž7 7 6 jâ, j Ž, 6 d D v rutvwqx 7 6 jd RTSF U D d D 6 ã&ã â 6, j â 6 j 5 6 j c G IH5JIK 56 d 5, 6 Ž, 7 D 5 ã 5 c 6 5, 7 ã j, 7 D 7, 6 Ž ` _ G2Gb c 5 ã G IH5JIK + e/ 56 d 5, 6 Ž 7, 5 d&d 5 c 6 5, ã d D,*dŽ 5, 6 7 c v rutvwqx 7 6 j 5 6 j ã,ž,*â(ã 5, 56 ã, Ž&â, 7Ž7 6 j D G IH5JIK c 6 &d, 6 Ž, 5 âž 6 d(ã, 7 6 7, 7 6 â 5, 6 Ž J G Icj~ c G IH5JIK + e/ c 6 &d, 6 Ž 7 c ã 5 6 d(ã,*d 6 7,*d 6 â&â, v rutvwqx 56,^c 6 jj,ž, 7Ž7 6 5 j â 6 5 d â 6 j 5 RTSGIH G IH5JIK 56 Ž, 6 Ž D &d 5 5, 6 7, ã 7 D, ã dž, 6 Ž J G Gl ` G IH5JIK + e/ 56 Ž, 6 Ž, 7 d 7 â 5, 6 7,*dCjj, j~&â, 6 D v rutvwqx 7 6 ã j 6 â&d jd 5 â 7, 6 7,Ž, &d,ž, 7 j 6 j 7 G IH5JIK â 6 7,, 6 Ž 5 dž D j 7 6 â jd, 6 Ž b s `æ,+ 7 G IH5JIK + e/ â 6 7,, 6 Ž ã âž&d j 7 6 â 7 d(ã 5Ž5 â, 6 7Ž7 v rutvwqx 7 6 d D RTSFIF 5 c(â&d, 6 â, j 5,*â 5 RTSGIG G IH5JIK â 6 j 7, 6 Ž, 7 â&d, &â 5 c, 6 Ž G d b G IH5JIK + e/ â 6 j 7, 6 Ž 7 &d&d, c 5 d, 6 7 â v rutvwqx 7 6 d D RTSF J,*d, 7 d 7 cp, 7 dcj 6 j D K

103 Ê Z 4 â Ã! "!$# &%! '( À) *+,+-,/.2,4365 Ä! "! # &%! '(87