Author | Laasonen, Pentti |
Source | ACM Digital Library |
Content type | Text |
Publisher | Association for Computing Machinery (ACM) |
File Format | |
Copyright Year | ©1958 |
Language | English |
Subject Domain (in DDC) | Computer science, information & general works ♦ Data processing & computer science |
Abstract | The solution for a Dirichlet problem on a given plane domain and with given boundary values is usually approximated in numerical computation by its discrete analog defined and determined on an approximating set of net points. It can be proved that the approximation thus obtained converges to the exact solution, when the net becomes denser indefinitely, independently of the domain and the boundary values subject to rather weak conditions. Nevertheless, the irregularity of the boundary curve and of the boundary values affects strongly the convergence rate. For instance, if both are analytic and if a proper boundary interpolation scheme is used, then the simplest net analog leads to an error which decreases asymptotically at least proportional to the square of the mesh constant $\textit{h},$ as proved by Gerschgorin [2] and Collatz [1]: $δ\textit{h}$ = $\textit{O}(\textit{h2}).$ In introducing the convergence exponent (1) $\textit{&kgr;}$ = $lim\textit{h}→0$ inf $max\textit{PhCDh}$ log | $δ\textit{h}(\textit{Ph})$ |/log $\textit{h},$ $\textit{Dh}$ being the approximating net domain with the mesh constant $\textit{h}$ and $\textit{Ph}$ its node, this result can be expressed also by the inequality $\textit{&kgr;}$ ≧ 2. On the other hand, the author of this paper has shown in [4] that if the boundary of the domain is piecewise analytic, i.e., composed of a finite number of analytic arcs, and the boundary values are analytic on each closed arc, but jump discontinuities at the join of two arcs are permitted, then the convergence exponent depends on the angles at those corners where two adjacent arcs are connected. (Of course, the analytic character of the prescribed boundary values may alter at a finite number of interior points of an analytic boundary arc; it is sufficient to partition this arc at these points into different arcs with angles π at the related corners.) Actually, if απ is the largest of these angles, then, by using, for instance, the extrapolation scheme proposed by Collatz in [1] in order to determine the boundary values for the approximating net domain, one obtains the inequality (2) $\textit{&kgr;}$ ≧ min (2, 1/α).In the paper [4] it has been proved, moreover, that if the boundary values are not only piecewise analytic but also continuous, then for α < 1 the relation $δ\textit{h}$ = $\textit{O}$ $(\textit{h2})$ holds. This implies that (3) $\textit{&kgr;}$ ≧ 2, (α < 1). However, no information is given in the case where α ≧ 1, i.e., if either the domain has corners where two different analytic arcs are connected to form an angle greater than or equal to π, or at some interior point of an analytic boundary are the analytic character of the prescribed boundary values changes. The result (2) is valid, of course; however, since (3) is an essentially better result than (2) for 1/2 < α < 1, one could expect that some improvement is possible also in the cases α ≧ 1, if the prescribed values are continuos. The results obtained theoretically in the paper [4] may be summarized as follows. If the domain has a piecewise analytic boundary and the boundary values are also piecewise analytic, both in the sense described above, then (2) $\textit{&kgr;}$ ≧ min (2, 1/α), (α > 0), where the boundary values may be discontinuous. However, if the boundary values are continuous, then (3) $\textit{&kgr;}$ ≧ 2, (0 < α < 1).The purpose of the present paper is to develop further the considerations in [4] and to demonstrate those theoretical results by some experimental ones. These seem to indicate that in the two inequalities above, at least in some cases, the equality sign holds, and, moreover, that the latter theoretical rule is just a part of a more general hypothetical rule, namely (4) $\textit{&kgr;}$ ≧ min (2, 2/α), (α > 0).Table I presents the results of some experiments with discontinuous but piecewise analytic boundary values. In each case the domain $\textit{D}$ is a polygon such that its boundary $\textit{B}$ contains the boundary nodes set of the approximating square net domain $\textit{Dh}.$ Moreover, the boundary values are assumed to vanish, except at those corner points with the greatest angle απ, and, hence, the asymptotic solution for $\textit{h}$ → 0 is known to be identically zero. It is true that the boundary values thus defined do not fall strictly under the definition of piecewise analytic boundary functions, given above, but they can be interpreted as the difference of two such admissible functions. If $\textit{uh}$ and $\textit{uh}$ are the discrete solutions of the related problems, then it is obvious that $\textit{uh}$ is their difference, and its rate of convergence, as $\textit{h}$ → 0, is at least the smaller of those for $\textit{uh}$ and $\textit{uh}.$ Accordingly, the rate of convergence obtained by using such degenerate boundary functions is now an upper bound for the rate originally investigated.Now, if the truncation error were exactly $δ\textit{h}$ = $\textit{uh}$ - $\textit{u}$ = $\textit{Ch&kgr;},$ with some $\textit{C}$ independent of $\textit{h},$ then for two different values $\textit{h}$ with the ratio 2 (for instance $\textit{h}$ = 2 and $\textit{h}$ = 1) the corresponding approximations $\textit{u}2$ and $\textit{u}1$ would have the ratio $\textit{u}2:\textit{u}1$ = $2\textit{&kgr;},$ since $\textit{u}$ is identically zero. Accordingly, the expression (5) $\textit{&kgr;}$ = (log $\textit{u}2:\textit{u}1)/log$ 2 gives an approximation for the asymptotic convergence exponent. In table I, α is the magnitude of the greatest angle divided by π ; $\textit{n}$ is the number of the interior points at which the values $\textit{u}1$ and $\textit{u}2$ are determined and then used to compute $\textit{&kgr;}$ from (5); $\textit{&kgr;m}$ is the arithmetic mean of these $\textit{n}$ values and $\textit{s}$ the related quartile deviation; finally, $\textit{&kgr;}$ in the last column is the theoretical lower bound (6) $\textit{&kgr}$ = min (2, 1/&agr;α).In the investigation of problems with continuous and piecewise analytic boundary values the domains are similar to those previously described. Now, however, the limit solution for $\textit{h}$ → 0 is not known, and, therefore, the approximate values $\textit{&kgr;}$ are based on three consecutive approximations to the solution at the same point, with three different values of $\textit{h}$ which are chosen so that they are in the proportion 4:2:1. If these are denoted by $\textit{u}4,$ $\textit{u}2,$ and $\textit{u}1,$ and if the truncation error were $δ\textit{h}$ = $\textit{uh}$ - $\textit{u}$ = $\textit{Ch&kgr;},$ with $\textit{C}$ independent of $\textit{h},$ then $\textit{&kgr;}$ could be computed from (7) $\textit{&kgr;}$ = (log $\textit{u}4$ - $\textit{u}2/\textit{u}2$ - $\textit{u}1)/log$ 2. This is now the formula from which the approximate values $\textit{&kgr;}$ are computed at $\textit{n}$ (quite uniformly distributed) interior points. $\textit{&kgr;m}$ is the arithmetic mean and $\textit{s}$ the quartile deviation. In addition to these values, table II gives also $\textit{&kgr;},$ which is defined by (8) $\textit{&kgr;}$ = min (2, 2/α).The remarkably good coincidence between the corresponding values $\textit{&kgr;m}$ and $\textit{&kgr;}$ is also indicated in figure 1; it contains, in addition to the experimental values $\textit{&kgr;m},$ also the graphs of the analytic expressions for $\textit{&kgr;}$ and $\textit{&kgr;},$ from (6) and (8), respectively, with respect to 1/α. Those values which are theoretically proved to be lower bounds for the convergence exponent are represented as a solid line and those values in the hypothetical case as a broken one.In trying to prove theoretically the hypothesis that, for continuous boundary values, the relation $\textit{&kgr;}$ ≧ $\textit{&kgr;}$ is true, the decisive difficulty lies in finding proper estimates for the variation of the discrete solution function $\textit{uh}$ in the vicinity of a corner. As long as the angle of this corner is less than π, i.e., α < 1, then the variation of $\textit{uh}$ is of the order $\textit{O}(\textit{r}),$ as shown in [4], $\textit{r}$ being the distance from the corner point. This agrees with the variation $\textit{O}(\textit{r})$ of the solution function $\textit{u}$ of Laplace's differential equation. Now, for α > 1, the variation of $\textit{u}$ can be proved to be of the order $\textit{O}(\textit{r}1/α).1$ In order to obtain some experimental knowledge about the variation of $\textit{uh},$ the following numerical experiments were made. First, suppose that the corner point $\textit{P}(0)$ is a node for the nets considered. Take a direction from the corner such that two points $\textit{Ph}(1)$ and $\textit{Ph}(2)$ of the net domain are located on the line in this direction. Moreover, suppose that the $\textit{Ph}(1)$ is the closest node on this line and $\textit{Ph}(2)$ the second closet, so that their distances have the ratio 1:2. Let $\textit{uh}(1)$ and $\textit{uh}(2)$ be the values of $\textit{uh}$ at $\textit{Ph}(1)$ and $\textit{Ph}(2),$ respectively, and $\textit{u}(0)$ the prescribed boundary value at $\textit{P}(0).$ Then, for indefinitely decreasing $\textit{h},$ the expression (9) $λ\textit{h}$ = (log $\textit{uh}(2)$ - $\textit{u}(0)/\textit{uh}(1)$ - $\textit{u}(0))/log$ 2 will converge to the limit $λ\textit{0},$ provided the asymptotic behavior of $\textit{uh}$ in the vicinity of $\textit{P}(0)$ is characterized by an expression (10) $\textit{uh}$ ∼ $\textit{u}(0)$ + $\textit{Cr}λ0,$ where $\textit{C}$ is independent of $\textit{h}$ but dependent on the direction of approach. Of course, the converse is not in general true. The statement that the expressions (9) tend to a definite limit does not justify the conclusion that $\textit{uh}$ behaves asymptotically like (10). Nevertheless it is interesting to find the values of (9) for various directions and for decreasing mesh constants $\textit{h}.$ Table III again gives in its first column the value α of the domain, i.e., the greatest angle divided by π, in the second column the number of those directions in which the expressions $λ\textit{h}$ were determined. The three following columns contain the mean values of these $λ\textit{h}'s$ determined for three different mesh constants which are proportional to 4:2:1. Finally, the last column gives the expected lower bound for λ0: λ = min (1, 1/α). These results seem to indicate that if there exists a limit λ0 for indefinitely decreasing $\textit{h},$ then this limit cannot be less than λ. (The values λ4, λ2, and λ1 for α = 1, seemingly not supporting this conjecture, are not yet near enough to their limit value, which for α = 1 - ε has been proved to be greater than or equal to 1.) Furthermore, this statement makes the estimate $\textit{uh}$ - $\textit{u}(0)$ = $\textit{O}(\textit{r}λ)$ plausible, which has been proved for α < 1, as has been already mentioned. If it is true also for α > 1, i.e., if $\textit{uh}$ - $\textit{u}(0)$ = $\textit{O}(\textit{r}1/α),$ (α > 1) then it follows, from the similar estimate for the solution of the differential equation, that (11) $δ\textit{h}$ = $\textit{O}(\textit{r}1/α).But$ now, this estimate can be used to find an estimate for $δ\textit{h}$ in terms of $\textit{h}.$ In reference [4], it is shown that $δ\textit{h}$ = $\textit{O}(\textit{h}(2))$ follows from α < 1 and $δ\textit{h}$ = $\textit{O}(\textit{r}).$ Without going into details it may be remarked that a similar reasoning leads to the assertion that α > 1 and (11) imply the estimate $δ\textit{h}$ = $\textit{O}(\textit{h}(1/α)+\textit{&kgr;}1),$ where $\textit{&kgr;}1$ is any number less than 1/α. Accordingly, this estimate yields $δ\textit{h}$ = $\textit{O}(\textit{h}(2/α)-ε)$ where ε is any positive quantity: that is, the convergence exponent defined in (1) is at least 2/α.Briefly, the results are as follows:Let $\textit{D}$ be a plane domain those boundary $\textit{B}$ is composed of a finite number of regular analytic arcs, απ being the greatest angle at the corner Let $\textit{u}$ be the solution of a Dirichlet problem with prescribed, piecewise analytic boundary by using the interpolation scheme from [1] in order to assign the values at the boundary nodes of $\textit{Dh}.$ Let $\textit{uh}$ be the solution of the corresponding discrete problem and $δ\textit{h}$ = $\textit{uh}$ - $\textit{u}$ the truncation error. Specifically, this truncation error for an indefinitely decreasing mesh constant $\textit{h}$ is examined by introducing the convergence exponent $\textit{&kgr;}$ = $lim\textit{h}→0$ inf $max\textit{Ph(Dh}$ log $δ\textit{h}$ $(\textit{Ph})/log\textit{h}.For$ boundary values which may be discontinuous, the rate of convergence is determined by an exponent, whose lower bound has been proved in [4] to be $\textit{&kgr;}$ ≧ min (2, 1/α).For continuous boundary values, the hypothesis $\textit{&kgr;}$ &gE min (2, 2/&agr;α) s introduced. It has been shown in [4] that it holds for α < 1; for various values $\textit{&kgr;}$ &gE 1, experimental results seem to be in good agreement with this law. Moreover, it has been remarked that another hypothetical law,uh |
ISSN | 00045411 |
Age Range | 18 to 22 years ♦ above 22 year |
Educational Use | Research |
Education Level | UG and PG |
Learning Resource Type | Article |
Publisher Date | 1958-01-01 |
Publisher Place | New York |
e-ISSN | 1557735X |
Journal | Journal of the ACM (JACM) |
Volume Number | 5 |
Issue Number | 1 |
Page Count | 7 |
Starting Page | 32 |
Ending Page | 38 |
Ministry of Human Resource Development (MHRD) under its National Mission on Education through Information and Communication Technology (NMEICT) has initiated the National Digital Library of India (NDLI) project to develop a framework of virtual repository of learning resources with a single-window search facility. Filtered and federated searching is employed to facilitate focused searching so that learners can find out the right resource with least effort and in minimum time. NDLI is designed to hold content of any language and provides interface support for leading vernacular languages, (currently Hindi, Bengali and several other languages are available). It is designed to provide support for all academic levels including researchers and life-long learners, all disciplines, all popular forms of access devices and differently-abled learners. It is being developed to help students to prepare for entrance and competitive examinations, to enable people to learn and prepare from best practices from all over the world and to facilitate researchers to perform inter-linked exploration from multiple sources. It is being developed at Indian Institute of Technology Kharagpur.
NDLI is a conglomeration of freely available or institutionally contributed or donated or publisher managed contents. Almost all these contents are hosted and accessed from respective sources. The responsibility for authenticity, relevance, completeness, accuracy, reliability and suitability of these contents rests with the respective organization and NDLI has no responsibility or liability for these. Every effort is made to keep the NDLI portal up and running smoothly unless there are some unavoidable technical issues.
Ministry of Human Resource Development (MHRD), through its National Mission on Education through Information and Communication Technology (NMEICT), has sponsored and funded the National Digital Library of India (NDLI) project.
Phone: +91-3222-282435
For any issue or feedback, please write to ndl-support@iitkgp.ac.in