Paper Menu >>
Journal Menu >>
![]() Applied Mathematics, 2011, 2, 118-122 doi:10.4236/am.2011.21013 Published Online January 2011 (http://www.SciRP.org/journal/am) Copyright © 2011 SciRes. AM A Fast Algorithm to Solve the Bitsadze Equation in the Unit Disk Daoud Mashat, Manal Alotibi Department of Mathematics, Faculty of Science, King Abdulaziz University, Jeddah, Saudi Arabia E-mail: dmashat@kau.edu.sa, dmashat63@gmail.com Received October 19, 2010; revised November 18, 2010; accepted November 24, 201 0 Abstract An algorithm is provided for the fast and accurate computation of the solution of the Bitsadze equation in the complex plane in the interior of the unit disk. The algorithm is based on the representation of the solution in terms of a double integral as it shown by Begehr [1,2], some recursive relations in Fourier space, and Fast Fourier Transforms. The numerical evaluation of integrals at 2 N points on a polar coordinate grid by straightforward summation for the double integral would require 2 ON floating point operation per point. Evaluation of such integrals has been optimized in this paper giving an asymptotic operation count of In ON per point on the average. In actual implementation, the algorithm has even better computational complexity, approximately of the order of 1O per point. The algorithm has the added advantage of working in place, meaning that no additional memory storage is required beyond that of the initial data. This paper is a result of application of many of the original ideas described in Daripa [3]. Keywords: Singular Integrals, Fast Algorithm, Bitsadze Equation 1. Introduction The solutions of many elliptic partial differential equa- tions represent in terms of singular integrals in the com- plex plane in the interior of the unit disk, as the nonho- mogeneous Cauchy-Riemann equations, the Beltrami eq- uation, the Poisson equation, etc. Then solving these eq- uations requires computing the values of the singular integrals. There are two main difficulties in the straight- forward computation of these integrals using quadrature rules. Firstly, straightforward computation of each of these integrals requires an operation count of the order 2 ON per point. This gives a net operation count of 4 ON for 2 N grid points which is computationally very in- tensive for large N. Secondly, this method also gives poor accuracy due to the presence of the singularities in the integrand. Daripa and Co-workers ([3-9]) presented fast algorithms to solve the singular integrals that arise in such solutions. By these algorithms evaluation of singu- lar integrals has been optimized, giving an asymptotic operation count of 2ln lnON N for2 N points. More- over, these algorithms have the added advantages of working in place, meaning that no additional memory storage is required beyond that of th e initial data. In this paper we follow his method to present an algo- rithm to solve an elliptic partial differential equation called the Bitsadze equation which define in the unit disk 0;1: 1Bzz in complex plane for any com- plex valued function w of complex variables ,zz B by 2 2 2 1;,, 4 wiwfzxiyxy xy z (1) Where f is a complex valued function on B. [10] The Bitsadze equation arises in many areas including structural mechanics, electrostatics, magneto statics, po- wer electromagnetic, conductive media, heat transfer and diffusion ([11-13]). In [1,2], Begehr introduced some boundary value problems for Bitsadze equation under some solvability conditions and presented their solutions as results for applying the Dirichlet and Neumann boun- dary value problems all those solutions have singular in- tegrals in their context. For that, we will consider one of these problems to apply our numerical method for eva- luating the singular integrals. Problem (1.1): zz wf in B, 0,w 1 zz zw on B, 0 z wc , Where 101 ;, ,; and fLBCB c . ![]() D. MASHAT ET AL. Copyright © 2011 SciRes. AM 119 Its unique solution is given by Equation (1.2) (Below) Let us rewrite it in the form ,wzczuzvzGf z (1.3) Where 0 1 1, 2 d uz iz 2 1 1 1 1log 1, 2 zd vz z iz and 22 1 1 . () z Gf zfdd z (1.4) Our method is basically a recursive routine in Fourier space that divides the interior of the unit disk into a col- lection of annular regions and expands the integral in Fourier series in angular direction with radius dependent Fourier coefficients. A set of exact recursive relations are derived which are used to produce the Fourier coeffi- cients of singular. These recursive relations involve ap- propriate scaling of one-dimensional integrals in annular regions. The integrals in (1.4) at all grid points are then easily obtained from the Fourier coefficients by the FFT. The rest of the paper is structured as follows. Section 2 presents the solution of the linear integrals u and v. Sec- tion 3 develops the mathematical foundation of the effi- cient algorithm to evaluate (1.4) within the unit disk. The fast algorithms for solving problem (1.1) is discussed in Section 4. We carry out numerical results with this me- thod in section 5. Finally, we summarize and conclude in Section 6. 2. Evaluating the Integrals u and v 1) 0 1 1 2 d uz iz Let i e and i zre , where ,0r then 2 0 0 1, 2 i ii ii ied ure e iere Since the integral is on the unit disk then 1 , 20 0 2 0 00 1 ,21 1 2 i i in in n e ur d re ere d Let 0iin n n eae , 2 00 0 1 ,2 , nin inin n nn nin n n urareeed are Then we can write ,in n n ur ue (2.1) Where if 0, 0 if 0. n n n ar n un 2) 2 1 1 1 1log 1, 2 zd vz z iz 22 1 0 2 2 1 0 2 2 1 10 11 ,log1, 2 1 log1, 2 1 . 2 i iii ii ii i n iin i n ried vrere e ire e rered re rr eed n re Let 1iin n n ebe , 2 2 10 11 1 1 11 ,, 2 . nin inin n i nn nnin n n br r vreee d n re brre n put n = m+1 2 1 01., mmim m m b vrrr e m Then we can write ,, im m m vr ve (2.3) Where 2 1 if 0, 1 0 if 0. mm m m brr m vmm 222 01 11 1 1 11 1 log 1. 22 () zz dd wz czzfdd iziz z (1.2) ![]() D. MASHAT ET AL. Copyright © 2011 SciRes. AM 120 3. Mathematical Foundation of the Algorithms In this section, we develop the theory n eed e d to construct an efficient algorithm for evaluation the singular inte- grals (1.4). The following theorem is crucial for later development of the algorithm. Theorem 3.1. The value of the integral (1.4) with i zre , 0r can be written as in n n Gfzgr e (3.1) Where 22 2 0;10; 2 2 2 0; ; 0 1 ; 1 nn n BBr nn n Br rr fddn gr rr fddn (3.2) Proof. If we denote 22 2 0 1 ,. 2() in z Qre d z (3.3) Then it follows from (1.4) and (3.1) that (0;1) 1, . nB g rfQrdd (3.4) The integral in (3.3) can be evaluated by first expand- ing 22 () z z in power of z and z to get 22 22 2 0 2 2 2 1 ; , ; . n in n n n in n n rr er z zrr er By comparing this result with the Fourier series coef- ficients of 22 () z z , we get 22 2 2 2 2 0; 0, , ; 0, , , ; 1, , 0; 1, . nn n nn n nr rr nr Qr rr nr nr (3.5) Substitution of (3.5) into (3.4) yields the desired result. Corollary 3.1. Suppose that i e and f has Fourier coefficient n f ; then the coefficients n g r in Equation (3.2) can be written as: 122 2 1 22 2 1 0 –; 0, =2 ; 1. nn n n r nrnn n n rr fdn gr rr fdn (3.6) Corollary 3.2. It follows directly from Equation (3.6) that 10 n g for 0n, 00 n g for 1n . Corollary 3.3. Let ij rr . Define 2 1 , 2 1 ; 0, ; 1. j i j i r n n r n ij r n n r fdn Cfdn (3.7) and 2 1 , 2 1 ; 0, ; 1. j i j i r n n r n ij r n n r fdn Bfdn (3.8) After some algebraic manipulation it follows from Equations (3 .7) and (3.8) that . nini ni g rCrBr (3.9) Where , 2; 0, n nn i nii ijn j j r CrrCCrn r (3.10) 2 2, 2; 1, n nn i njnij ij j r CrCrrCn r (3.11) 2 2, 2; 0, n nn i niiijn j j r Brr BBrn r (3.12) and , 2; 1. n nn i njni jij j r BrBrrB n r (3.13) Corollary 3.4. Let 01 2 01 M rrr r . It follows from recursive applications of (3.10)-(3.13) and from using Corollary 3.2 that 12 ,1 ,1 21, 1, 1 2; 0, 2; 1. Mnnnn liil ii il nl lnn nn liilii i rCrBn gr rC rBn (3.14) ![]() D. MASHAT ET AL. Copyright © 2011 SciRes. AM 121 for 1, 2,3,,1lM. Corollary 3.5. It follows directly from Equations (3.6) and (3.9) that 110; 0, nn CB n (3.15) 000; 1. nn CB n (3.16) 4. The Fast Algorithm We construct the fast algorithm based on the theory of section 3. The unit disk is discredited using M N lat- tice points with M equidistant points in the radial direc- tion and N equidistant points in the circular direction. The following is a formal description of the fast algo- rithm useful for pr ogramming pur p oses. Algorithm 4.1. (The fast algorithm for evaluating the singular integral (1.4)) Input: M, N and 2,1,1, 1, ik N l f rel MkN Output: 2,1,1,1, ik N l Gf relMkN . Step 1. Set 8 K N, 00r and 1 M r. Step 2. Compute the Fourier coefficients nl f r, 0, 1lM and ,nKK from known values of 2,1,2,, ik N l f re kN using the FFT. Step 3. Compute ,1 1, 1 n ii CiM and 2,1[0,2] nKK using Equation (3.7). Step 4. Compute ,1 1, 1 n ii BiM and 2, 1[0,2]nK K using Equation (3.8). Step 5. Compute nl g r, 2, 2nKK , 1, 1lM using relations (3.1 4). set 0,0,0, 2 nMnM CrBrn K do 0,1, ,2nK do 1, ,1lM ,1 1 1 2, n nn l nll llnl l r Cr rCCr r 2 2,1 1 1 2, n nn l nll llnl l r Brr BBr r . nlnl nl g rCrBr enddo enddo set 00 0,0,2, 1 nn CrBrn K 2 110,1 2, nn n Crr C 110,1 2, nn n Br rB 111 . nnn g rCrBr do 2,,1nK do 2, ,1lM 2 2 111, 2, n nn l nlnll ll l r CrCrr C r 111, 2, n nn l nlnll ll l r BrBr rB r . nlnl nl g rCrBr enddo enddo Step 6. Finally, compute 2 22 2; 1,1 1,, . K ik Nik N lnl nK Gfzregr e lM kN Algorithm 4.2 (The fast algorithm for solving the problem (1.1)): Input: M, N , 2 0ik N e , 2 1ikN e and 2ik N l fre , 1,1 ,1,lM kN . Output: 2,1, 1,1,. ik N l wrel Mk N Step 1. Set 8 K N , 00r and 1 M r. Step 2. Compute 2ik N l Gf zre , 1, 1lM, 1,kN using algorithm 4.1. Step 3. Compute the Fourier coefficients , n an KK from known values of 2 0ik N e , 1, 2,,kN using the FFT. Step 4. Compute the Fourier coefficients 1, 1 n bnK K from known values of 2 1ikN e , 1, 2,,kN using the FFT. Step 5. Compute 2 (),1,1,1, ik N l urel MkN using the relation (2.1). Step 6. Compute 2 (),1,1,1, ik N l vrel MkN using the relation (2.3). Step 7. Compute 2 (),1,1,1, ik N l wrelMk N . 222 22 () ik Nik Nik N ll l ik Nik N ll wrecre ure vre Gfre 5. Numerical Results In this section we solve a boundary value problem for the inhomogeneous Bitsadze equation in the unit disk by using the algorithms that presented in section 4. Example Consider the problem 2 zz wz in B,,wz 2, zz zw ,zB 00 z w , The exact solution for this problem is given by 2,wzzz zB By using algorithm 4.2 we have the max error as illu- strate in the following Table 1. ![]() D. MASHAT ET AL. Copyright © 2011 SciRes. AM 122 Table 1. Maximum relative error. MAX ERROR M = 10 M = 50 M = 100 M = 200 N=64 3.371768E-07 2.980596E-07 2.588641E-07 2.245232E-07 N=128 3.371753E-07 2.980553E-07 2.588640E-07 2.245231E-07 N= 256 3.371734E -07 2.980548E-07 2.588639E-07 2.245196E-07 N= 512 3.371718E -07 2.980526E-07 2.588628E-07 2.245153E-07 N= 1024 3.371717E-07 2.980501E-07 2.588627E-07 2.245142E-07 6. Conclusions We presented a fast algorithm to solve the Bitsadze equ- ation in the unit disk under special boundary conditions in the complex plane, by constructed the fast algorithm to evaluate the singular integral transform (1.4). The method divides the interior of the unit diskB :1zz into a collection of annular regions. The in- tegrals and the function f (z) are expanded in terms of Fourier series with radius dependent Fourier coefficients. The good performance of the algorithm is due to the use of scaling one-dimensional integral in the radial direction to produce the value of the singular integral over the en- tire domain. Specifically, scaling factors are used to de- fine exact recursive relations which evaluate the radius dependent Fourier coefficients of the singular integral (1.4). The inverse Fourier transform are applied on each circle to obtain the value of the singular integrals on all circles. 7. References [1] H. Begehr, “Boundary Value Problems in Complex Analysis I,” Boles’ de la Association’s Mathematical Ve- nezuelan, Vol. 12, No. 1, 2005, pp. 65-85. [2] H. Begehr, “Boundary Value Problems in Complex Analysis II,” Boles’ de la Association’ Mathematical Ve- nezuelan, Vol. 12, No. 2, 2005, pp. 217-250. [3] P. Daripa, “A Fast Algorithm to Solve Nonhomogeneous Cauchy–Riemann Equations in the Complex Plane,” SIAM Journal on Scientific and Statistical Computing, Vol. 13, No. 6, 1992, pp. 1418-1432. doi:10.1137/0913080 [4] P. Daripa and D. Mashat, “An Efficient and Novel Nu- merical Method for Quasiconformal Mappings of Doubly Connected Domains,” Numerical Algorithms, Vol. 18, No. 2, 1998, pp. 159-175. doi:10.1023/A:1019169431757 [5] P. Daripa and D. Mashat, “Singular Integral Transforms and Fast Numerical Algorithms,” Numerical Algorithms, Vol. 18, No. 2, 1998, pp. 133-157. doi:10.1023/A: 1019117414918 [6] P. Daripa and L. Borges, “A Fast Parallel Algorithm for the Poisson Equation on a Disk,” Journal of Computa- tional Physics, Vol. 169, No. 1, 2001, pp. 151-192. doi: 10.1006/jcph.2001.6720 [7] P. Daripa and L. Borges, “A Parallel Version of a Fast Algorithm for Singular Integral Transforms,” Numerical Algorithms, Vol. 23, No. 1, 2000, pp. 71-96. doi:10.1023/ A:1019143832124 [8] P. Daripa, “A Fast Algorithm to Solve the Beltrami Equ- ation with Applications to Quasiconformal Mappings,” Journal of Computational Physics, Vol. 106, No. 2, 1993, pp. 355-365. [9] P. Daripa, “On a Numerical Method for Quasiconformal Grid Generation,” Journal of Computational Physics, Vol. 96, No. 2, 1991, pp. 229-236. doi:10.1016/0021-9991(91) 90274-O [10] A. H. Babayan, “A Boundary Value Problem for Bitsadze Equation in the Unit Disc,” Journal of Contemporary Mathematica Analysis, Vol. 42, No. 4, 2007, pp. 177-183. doi:10.3103/S1068362307040012 [11] A. V. Bitsadze, “Boundary Value Problems of Second Order Elliptic Equations,” North-Holland Publishing Company, Amsterdam, 1968. [12] C. Miranda, “Partial Differential of Elliptic Type,” Springer, New York, 1970. [13] M. Schechter, L. Bers and F. John, “Partial Differential Equations,” Interscience, New York, 1964. |