College of Science, China Agricultural University, Beijing 100083, China
Received August 22, 2013; Accepted September 23, 2013; Published September 27, 2013
Citation: Chen J, Xu C (2013) The Five-Point Difference Method Based on the K-Modes Cluster for Two-Dimensional Poisson Equations. J Appl Computat Math 2: 139. doi: 10.4172/2168-9679.1000139
Copyright: © 2013 Chen J, et al. This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited.
Visit for more related articles at Journal of Applied & Computational Mathematics
In this paper, we proposed a new method for the numerical solutions of a two-dimensional Poisson equation, where we used k-modes clustering algorithm to improve the standard five-point difference scheme. Numerical experiments have shown that the five-point difference method based on k-modes cluster is effective and efficient. The proposed new method not only reduces computing time remarkably, but also shows better performance in data storage and stability than the standard five-point difference scheme.
K-modes cluster; Five-point difference scheme; Twodimensional Poisson equations
Scientific computation plays an important role in natural sciences, engineering and technology. It has become an indispensable tool in many areas. The Poisson equation is an essential partial differential equation in fluid dynamics and electromagnetic. Due to its analytical solution of a Poisson equation is difficult to obtain, an alternative method is to find its numerical solution. A classical method to get the numerical solution of the Poisson equation is the standard five-point or nine-point difference scheme, which is simple to use and secondorder accurate [1-3]. In order to enhance the accuracy of the difference scheme, it is often required to have finer mesh split or to use more complex difference scheme, which will result in much more computing time and larger amount of data storage. Moreover, as the scale of data increases, the dimension of the coefficient matrix of the linear equations will increase and the numerical solutions will become less stable. To acquire good experimental data usually need a compromise between the calculation efficiency and data storage capacity. In the numerical solution of the two-dimensional Poisson equation, the function value often fluctuates considerably. In areas with a higher absolute value of the derivative (if it exists), the mesh accuracy needs to be higher. In doing so, we need to apply to the whole domain, leading to the data storage and computation time doubled. In fact, in some parts of the domain, even if the division accuracy increases, the accuracy of the numerical solution may stay the same. Therefore, it is of importance to simplify the calculation and to reduce data storage while ensuring sufficient accuracy of numerical solutions.
The proposed new k-modes method is an extension of the k-means algorithm [4] for processing large data in data mining. In 2003, Hu and Chen proposed an effective method based on mesh grid for highdimensional data and large data sets [5]. In 2009, an algorithm based on mesh grid and module indicator optimization hierarchical clustering was also proposed [6]. Recent research on the difference scheme for differential equations has mainly applied new results of other research areas to the classical numerical algorithms. For instance, the doublegrid [7] finite difference method for nonlinear elliptic and parabolic equations was given in 2004. Another method of second order elliptic equation with variable coefficients [8] for solving initial boundary problems was developed in 2010. They provided a difference scheme and proved its existence, uniqueness, convergence and stability using energy method. Recent research on the numerical solution of differential equations is mainly focused on applying data processing algorithms to the problem-solving process, such as the Radial Basis Function (RBF) neural network for solving differential equations [9,10]. Another approach is to construct an effective difference scheme for new forms of differential equations obtained from the engineering field or theoretical deduction. For example, in computational fluid dynamics (CFD) field, building an effective calculation method to capture shock is a key part of the study.
To our knowledge, there are not research publications to use k-modes cluster to construct five-point difference scheme for solving a two-dimensional Poisson equation. In this paper, based on the development of new algorithms in data mining, we applied k-modes cluster to the standard five-point difference scheme and proposed a new method for solving two-dimensional Poisson equation where we constructed the five-point difference scheme based on k-modes cluster algorithm. The proposed new method not only ensures the stabilization of solutions of the fully discrete two-dimensional (2-D) Poisson system, but also reduces the computational load and avoids time-consuming calculations, while guaranteeing the sufficient accuracy of its numerical solution. This new method also enhances calculation efficiency.
In the next section, the k-modes cluster algorithm is given and the new five-point difference scheme based on k-modes clustering for 2-dimentional Poisson equations are developed. Given below, some numerical examples are presented to illustrate the errors between the solutions of the proposed and the standard five-point difference scheme, and below section provides conclusions and future research topics.
K-modes method and the new five-point difference scheme based on k-modes cluster for two-dimensional Poisson equations
We consider the Dirichlet boundary problem of two-dimensional Poisson equation
(1)
(2)
Where are constants, are constants, φ(x, y), are the given functions, u (x, y) is the unknown function.
K-modes algorithm: The k-means clustering algorithm is widely used in data mining. Compared with k-means algorithm, the k-modes algorithm can handle classified attribute-type data where the k-means algorithm cannot [11,12].
The k-modes algorithm uses modes instead of the means in clustering. It is similar to k-means, which renews alternately the cluster center and divides the matrix, till the value of the cost function remains unchanged. The k-modes algorithm takes the dissimilarity measure
Where,
are two objects, there are s character properties, , instead of the distance in the k-means algorithm.
In the k-modes algorithm, the smaller the dissimilarity measure, the smaller the distance. The dissimilarity measure between a sample and a cluster center is the number of their different properties. The sample belongs to the cluster center that has the minimum dissimilarity measure.
Use the following function is minimized as the clustering criterion function:
Where, Δ_{n×m} is the membership matrix, represents the set of objects contains the number of elements and corresponding to the membership of the row vectors of the matrix. k represents the number of the divided sub-class, which corresponds to the case reported in the column vector matrix.
The new five-point difference scheme based on k-modes cluster for two-dimensional Poisson equations: In the following, we will present how to construct a five-point difference scheme based on grid function and error function k-modes clustering for solving twodimensional Poisson problems:
a) Divide the given solution domain. For the convenience of explanation, we choose to divide the domain evenly in this paper. The initial division can be given at a moderate division step. To ensure that the numerical fluctuations of the solutions can be reflected as much as possible, we choose the initial division by comparing different step sizes.
b) Divide the grid nodes. Discretize the 2-D Poisson problem by using a five-point difference scheme and solve the discrete linear equations to obtain a rough numerical solution.
c) Store the grid nodes and the corresponding numerical solution. The corresponding relationship should be guaranteed. Consequently, the grid function and the error function can be obtained. Then, begin to cluster with two forms (see Step 4) and Step 5)).
d) Cluster based on grid function Define the Euclidean distance between two vectors. We cluster each pretreated fragment based on k-modes algorithm of 2.1:
o Select k objects random according to the given value of k, the vector Z_{i} is an initial representative of the center of a cluster. The vector is an initial representative of the mean.
o For each of the remaining objects, calculate the dissimilarity measure for each data point with k classes between the centers using Euclidean distance. And through different values to calculate the membership matrix where
o Recalculate the center of each cluster Z^{(t)} and the mean of each cluster M^{(t)}. Define Z^{(t+1)} that is the minimum data error between the mean and the center of the family.
o Calculate matrix P(U, Z), if the algorithm ends. Otherwise, set t=t+1, then go to step b.
o The value of k is determined by the function image of the numerical solution of two-dimensional Poisson equations through several tests
e) Cluster based on error function . Use ε_{ij} is instead of u_{ij} in the dissimilarity measure, select the same clustering algorithm as in Step 4).
f) Apply different grid division strategies to the corresponding regions of each clustered class. We finer the mesh in places with large fluctuations, and maintain the original grid in places with small fluctuations.
g) Linking all classes after the data processing in accordance with the original order to form a new subdivision. In the new mesh, using a five-point difference scheme, apply different discretization methods at inner points and junction points of the mesh in order to get the new discrete equation and solve it again.
In this section, numerical experiments are conducted in the twodimensional Poisson equations with Dirichlet boundary value problem, giving
(3)
The exact solution of problem (3) is . In the following, we apply the five-point difference scheme based on k-modes cluster (see Section 2.2) to solve problem (3).
In the interval [0, 2]×[0,1] the problem (3) is given a suitable mesh. As the internal [0, 2] will be divided into 32 equal portions, and [0,1] will be divided into 16 equal parts, which will be .
The mesh directly leads to the five-point difference results, namely the linear equations:
(4)
The value of the nodes are substituted into (4), obtaining
(5)
Solve the linear equations (5) by Gauss-Seidel iteration.
The results obtained in Step 3, such as the exact solutions of the nodes, the difference function values and the absolute values of the error, are shown in Table 1 (the total number of internal nodes are 464).
Nodes | Grid Function Values | True value of the nodes | Absolute values of the error |
---|---|---|---|
(x_{i},y_{j}) | u_{ij} | u(x_{i},y_{j}) | |
(0.063,0.25) | 0.750371 | 0.752711 | 0.002 |
(0.125, 0.5) | 1.126169 | 1.133148 | 0.007 |
(0.25, 0.5) | 1.27037 | 1.28402 | 0.014 |
(0.5, 0.5) | 1.623932 | 1.648121 | 0.025 |
(0.75, 0.5) | 2.08566 | 2.117 | 0.031 |
(1.0, 0.5) | 2.68624 | 2.71828 | 0.032 |
(1.25 , 0.5) | 3.463609 | 3.490342 | 0.027 |
(1.5, 0.5) | 4.464887 | 4.48169 | 0.017 |
(1.7, 0.5) | 5.74887 | 5.7546 | 0.005 |
Table 1: Results of the five-point difference scheme for the two-dimensional Poisson equation.
Cluster based on the coarse grid function . After repeated trials and approbations, we finally select the class k=2, which indicate the class C_{1} and he class C_{2} respectively. We can obtain the clustering results as follows:
a) The class C1 consists of the following regions:
[0, 0.375]×[0, 1), (0.375, 0.563)×(0, 0.313], (0.438, 0.563)×[0.813, 1], (0.563, 0.628)×(0, 0.25), (0.563, 0.625)×[0.875, 1], (0.625, 0.813)× (0, 0.188), (0.813, 0.875)×(0, 0.125);
b) The class C_{2} includes the remaining regions in the original solving domain after removing the regions of the class C_{1}.
Cluster based on the error functions . We still select the clustering class k=2, which indicate the class C_{1}* and the class C_{2}* respectively. Then, the clustering results are given as follows:
a) The class C_{1}* consists of the following regions:
(0, 0.25]×(0, 0.75], (0.25, 0.313)×(0, 0.625], (0.313, 0.375)×(0, 0.563], (0.375, 0.563)×(0, 0.438), (0.563, 0.688)×(0, 0.313], (0.688, 0.813)×(0, 0.188);
b) The class C_{2}* includes the remaining regions in the original given area after removing the regions of the class C_{1}*.
In order to obtain a more exact solution, we divide the mesh in a finer way. The class of clustering will be handled as following:
a) For the regions corresponding to the class C_{1} and C_{1}*, maintain the original division fineness unchanged.
b) For the regions corresponding to the class C_{2} and C_{2}*, maintain the original division fineness unchanged on the abscissa axis, while reducing the division step size to a half on the vertical axis. It means that there are 814 internal nodes in step 5) and 856 internal nodes in step 6) in total.
After the difference subdivision, we still use the five-point difference scheme for internal nodes. At the junction points of two types, is calculated using the difference schemes of . The equations obtained above are solved by Gauss-Seidel iterative method.
As a result, comparing the numerical solutions of two-dimensional Poisson problems that are calculated by the five-point difference schemes based on grid functions k-modes clustering and error functions k-modes clustering process, we can give the error curves graph of the numerical solution with five-point difference processing based on grid function k-modes clustering, which is shown in Figure 1 (The unit of error shaft: ×10^{-1}).
From Figure 1 and Figure 2, we notice that the error between the numerical solutions calculated by the grid function k-modes clustering and analytical solution is slightly larger than the error between the numerical solutions calculated by the error function k-modes clustering and analytical solution. Therefore, we can conclude that the five-point difference schemes based on the error function for k-modes clustering for solving two-dimensional Poisson problems is a method even better than the five-point difference schemes based on the grid function for k-modes clustering for solving two-dimensional Poisson problems.
The proposed methods are a brand-new method that has never been applied to solving two-dimensional Poisson equations. From Figure 1 and Figure 2, we get the results of the k-modes clustering algorithm based on the processing of the grid function and error function . Although the power exponent of their absolute errors is an order lower than the direct difference method in magnitude, but we can save nearly half of the data storage capacity, and the number of iterations can be reduced from 191 times to 151 times, improving the solving speed of numerical solution. Furthermore, during the process of obtaining the numerical solution through these methods, the geometric properties of the two-dimensional Poisson equations do not need to be considered again, and the fivepoint difference schemes based on k-modes clustering are also more stable. An order of magnitude error is within the allowable range for the majority of problems and does not have a direct influence on the accuracy of the results. In this paper, the numerical experiments have shown that we proposed five-point difference schemes based on the grid functions k-modes clustering and the error functions k-modes clustering are effective and efficient, they will have extensive applications.