Main Page: Difference between revisions

From formulasearchengine
Jump to navigation Jump to search
← Older editNewer edit →
No edit summary
No edit summary
Line 1: Line 1:
In [[mathematics]], a '''Dirichlet problem''' is the problem of finding a [[function (mathematics)|function]] which solves a specified [[partial differential equation]] (PDE) in the interior of a given region that takes prescribed values on the boundary of the region.
In [[mathematics]], '''directed-complete partial orders''' (abbreviated to '''dcpo''' or sometimes just '''cpo''') are special classes of [[partially ordered set]]s, characterized by particular [[completeness (order theory)|completeness properties]]. Complete partial orders play a central role in [[theoretical computer science]], in [[denotational semantics]] and [[domain theory]].


The Dirichlet problem can be solved for many PDEs, although originally it was posed for [[Laplace's equation]].  In that case the problem can be stated as follows:
== Definitions ==


:Given a function ''f'' that has values everywhere on the boundary of a region in '''R'''<sup>''n''</sup>, is there a unique [[continuous function]] ''u'' twice continuously differentiable in the interior and continuous on the boundary, such that ''u'' is [[harmonic function|harmonic]] in the interior and ''u''&nbsp;=&nbsp;''f'' on the boundary?
A partially ordered set is a '''directed-complete partial order''' ('''dcpo''') if each of its [[directed set|directed subsets]] has a [[supremum]]. Recall that a subset of a partial order is directed if it is non-empty and every pair of elements has an upper bound in the set. In the literature, dcpos sometimes also appear under the label '''up-complete poset''' or simply '''cpo'''.


This requirement is called the [[Dirichlet boundary condition]].  The main issue is to prove the existence of a solution; uniqueness can be proved using the [[maximum principle]].
In some contexts, the phrase [[chain complete|ω-cpo]] (or just '''cpo''') is used to describe a poset in which every ω-chain (''x''<sub>1</sub>≤''x''<sub>2</sub>≤''x''<sub>3</sub>≤''x''<sub>4</sub>≤...) has a supremum. Every dcpo is an ω-cpo.


==History==
An important role is played by dcpo's with a least element. They are sometimes called '''pointed dcpo'''s, or '''cppo'''s, or just '''cpo'''s.
The '''Dirichlet problem''' is named after [[Johann Peter Gustav Lejeune Dirichlet|Lejeune Dirichlet]], who proposed a solution by a variational method which became known as [[Dirichlet's principle]]. The existence of a unique solution is very plausible by the 'physical argument': any charge distribution on the boundary should, by the laws of [[electrostatics]], determine an [[electrical potential]] as solution.


However, [[Weierstrass]] found a flaw in Dirichlet's argument, and a rigorous proof of existence was found only in 1900 by [[David Hilbert|Hilbert]]. It turns out that the existence of a solution depends delicately on the smoothness of the boundary and the prescribed data.
Requiring the existence of directed suprema can be motivated by viewing directed sets as generalized approximation sequences and suprema as ''limits'' of the respective (approximative) computations. This intuition, in the context of denotational semantics, was the motivation behind the development of [[domain theory]].


== General solution ==
The [[duality (order theory)|dual]] notion of a directed complete poset is called a '''filtered complete partial order'''. However, this concept occurs far less frequently in practice, since one usually can work on the dual order explicitly.
For a domain <math>D</math> having a sufficiently smooth boundary <math>\partial D</math>, the general solution to the Dirichlet problem is given by 


:<math>u(x)=\int_{\partial D} \nu(s) \frac{\partial G(x,s)}{\partial n} ds</math>
== Examples ==


where <math>G(x,y)</math> is the [[Green's function]] for the partial differential equation, and
* Every finite poset is directed complete.
* All [[complete lattice]]s are also directed complete.
* For any poset, the set of all [[non-empty]] [[filter (mathematics)|filters]], ordered by subset inclusion, is a dcpo. Together with the empty filter it is also pointed. If the order has binary [[join and meet|meets]], then this construction (including the empty filter) actually yields a [[complete lattice]].
* The set of all [[partial function]]s on some given set ''S'' can be ordered by defining ''f''&nbsp;≤&nbsp;''g'' for functions ''f'' and ''g'' if and only if ''g'' extends ''f'', i.e. if the domain of ''f'' is a subset of the domain of ''g'' and the values of ''f'' and ''g'' agree on all inputs for which both functions are defined. (Equivalently, ''f''&nbsp;≤&nbsp;''g'' if and only if ''f''&nbsp;⊆&nbsp;''g'' where ''f'' and ''g'' are identified with their respective [[graph of a function|graphs]].) This order is a pointed dcpo, where the least element is the nowhere defined function (with empty domain). In fact, ≤ is also [[bounded complete]]. This example also demonstrates why it is not always natural to have a greatest element.
* The [[specialization order]] of any [[sober space]] is a dcpo.
* Let us use the term “[[deductive system]]” as a set of sentences closed under consequence (for defining notion of consequence, let us use e.g. Tarski's algebraic approach<ref name=Tar-BizIg>Tarski, Alfred: Bizonyítás és igazság / Válogatott tanulmányok. Gondolat, Budapest, 1990. (Title means: Proof and truth / Selected papers.)</ref><ref name=BurSan-UnivAlg>[http://www.math.uwaterloo.ca/~snburris/index.html Stanley N. Burris] and H.P. Sankappanavar: [http://www.math.uwaterloo.ca/~snburris/htdocs/ualg.html A Course in Universal Algebra]</ref>). There are interesting theorems which concern a set of deductive systems being a directed complete partial ordering.<ref name=seqdcpo>See online in p. 24 exercises 5–6 of §5 in [[#_note-BurSan-UnivAlg|BurSan:UnivAlg]]. Or, on paper, see [[#_note-Tar-BizIg|Tar:BizIg]].</ref> Also, a set of deductive systems can be chosen to have a least element in a natural way (so that it can be also a complete partial ordering), because the set of all consequences of the empty set (i.e. “the set of the logically provable / logically valid sentences”) is (1) a deductive system (2) contained by all deductive systems.


:<math>\frac{\partial G(x,s)}{\partial n} = \widehat{n} \cdot \nabla_s G (x,s) = \sum_i n_i \frac{\partial G(x,s)}{\partial s_i}</math>
== Properties ==


is the derivative of the Green's function along the inward-pointing unit normal vector <math>\widehat{n}</math>.  The integration is performed on the boundary, with [[Measure (mathematics)|measure]] <math>ds</math>. The function <math>\nu(s)</math> is given by the unique solution to the [[Fredholm integral equation]] of the second kind,
An ordered set ''P'' is a pointed dcpo if and only if every [[chain (order theory)|chain]] has a supremum in ''P''. Alternatively, an ordered set ''P'' is a pointed dcpo if and only if every [[order-preserving]] self-map of ''P'' has a least [[fixpoint]]. Every set ''S'' can be turned into a pointed dcpo by adding a least element ⊥ and introducing a flat order with ⊥&nbsp;≤&nbsp;''s'' and s&nbsp;≤&nbsp;''s'' for every ''s''&nbsp;∈&nbsp;''S'' and no other order relations.


:<math>f(x) = -\frac{\nu(x)}{2} + \int_{\partial D} \nu(s) \frac{\partial G(x,s)}{\partial n} ds.</math>
== Continuous functions and fixpoints ==


The Green's function to be used in the above integral is one which vanishes on the boundary:
A function ''f'' between two dcpos ''P'' and ''Q'' is called [[Scott continuity|'''(Scott) continuous''']] if it maps directed sets to directed sets while preserving their suprema:
* <math>f(D) \subseteq Q</math> is directed for every directed <math>D \subseteq P</math>.
* <math>f(\sup D) = \sup f(D)</math> for every directed <math>D \subseteq P</math>.
Note that every continuous function between dcpos is a [[monotone|monotone function]].
This notion of continuity is equivalent to the topological continuity induced by the [[Scott topology]].


:<math>G(x,s)=0</math>
The set of all continuous functions between two dcpos ''P'' and ''Q'' is denoted <nowiki>[</nowiki>''P''&nbsp;→&nbsp;''Q''<nowiki>]</nowiki>. Equipped with the pointwise order, this is again a dcpo, and a cpo whenever ''Q'' is a cpo.
Thus the complete partial orders with Scott continuous maps form a [[cartesian closed category]].<ref name="barendregt1984">[[Henk Barendregt|Barendregt, Henk]], [http://www.elsevier.com/wps/find/bookdescription.cws_home/501727/description#description ''The lambda calculus, its syntax and semantics''], [[North-Holland]] (1984)</ref>


for <math>s\in \partial D</math> and <math>x\in D</math>. Such a Green's function is usually a sum of the free-field Green's function and a harmonic solution to the differential equation.
Every order-preserving self-map ''f'' of a cpo (''P'', ⊥) has a least fixpoint.<ref>See [[Knaster–Tarski theorem]]; The foundations of program verification, 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, ISBN 0-471-91282-4, Chapter 4; the Knaster-Tarski theorem, formulated over cpo's, is given to prove as exercise 4.3-5 on page 90.</ref> If ''f'' is continuous then this fixpoint is equal to the supremum of the [[Iterated function|iterates]] (⊥, ''f''(⊥), ''f''(''f''(⊥)), … ''f''<sup>''n''</sup>(⊥), …) of ⊥ (see also the [[Kleene fixpoint theorem]]).


===Existence===
== See also ==
The Dirichlet problem for harmonic functions always has a solution, and that solution is unique, when the boundary is sufficiently smooth and <math>f(s)</math> is continuous. More precisely, it has a solution when


:<math>\partial D \in C^{(1,\alpha)}</math>
Directed completeness relates in various ways to other [[completeness (order theory)|completeness]] notions. Directed completeness alone is quite a basic property that occurs often in other order theoretic investigations, using for instance [[algebraic poset]]s and the [[Scott topology]].


for <math>0<\alpha</math>, where <math>C^{(1,\alpha)}</math> denotes the [[Hölder condition]].
== Notes ==


== Example: the unit disk in two dimensions ==
<references/>
In some simple cases the Dirichlet problem can be solved explicitly.  For example, the solution to the Dirichlet problem for the unit disk in '''R'''<sup>2</sup> is given by the [[Poisson integral formula]].


If <math>f</math> is a continuous function on the boundary <math>\partial D</math> of the open unit disk <math>D</math>, then the solution to the Dirichlet problem is <math>u(z)</math> given by
== References ==
* {{cite book
| author = Davey, B.A., and Priestley, H. A.
| year = 2002
| title = '''Introduction to Lattices and Order'''
| edition = Second
| publisher = Cambridge University Press
| isbn = 0-521-78451-4
}}


:<math>u(z) = \begin{cases} \frac{1}{2\pi}\int_0^{2\pi} f(e^{i\psi})
{{DEFAULTSORT:Complete Partial Order}}
\frac {1-\vert z \vert ^2}{\vert 1-ze^{-i\psi}\vert ^2} d \psi & \mbox{if }z \in D \\
[[Category:Order theory]]
f(z) & \mbox{if }z \in \partial D. \end{cases}</math>


The solution <math>u</math> is continuous on the closed unit disk <math>\bar{D}</math> and harmonic on <math>D.</math>
[[fr:Ordre partiel complet (informatique)]]
 
[[pl:Porządek zupełny]]
The integrand is known as the [[Poisson kernel]]; this solution follows from the Green's function in two dimensions:
[[ru:Частично упорядоченное множество#Полное частично упорядоченное множество]]
 
[[zh:完全偏序]]
:<math>G(z,x) = -\frac{1}{2\pi} \log \vert z-x\vert + \gamma(z,x)</math>
 
where <math>\gamma(z,x)</math> is harmonic
 
:<math>\Delta_x \gamma(z,x)=0</math>
 
and chosen such that <math>G(z,x)=0</math> for <math>x\in \partial D</math>.
==Methods of solution==
For bounded domains, the Dirichlet problem can be solved using the [[Perron method]], which relies on the [[maximum principle]] for [[subharmonic function]]s. This approach is described in many text books.<ref> See for example:
*{{harvnb|John|1982}}
*{{harvnb|Bers|John|Schechter|1979}}
*{{harvnb|Greene|Krantz|2006}}
</ref> It is not well-suited to describing smoothness of solutions when the boundary is smooth. Another classical [[Hilbert space]] approach through [[Sobolev space]]s does yield such information.<ref> See for example:
*{{harvnb|Bers|John|Schechter|1979}}
*{{harvnb|Chazarain|Piriou|1982}}
*{{harvnb|Taylor|2011}}
</ref> The solution of the Dirichlet problem using [[Sobolev spaces for planar domains]] can be used to prove the smooth version of the [[Riemann mapping theorem]]. {{harvtxt|Bell|1992}} has outlined a different approach for establishing the smooth Riemann mapping theorem, based on the [[reproducing kernel]]s of Szegő and Bergman, and in turn used it to solve the Dirichlet problem. The classical methods of [[potential theory]] allow the Dirichlet problem to be solved directly in terms of [[integral operator]]s, for which the standard theory of [[compact operator|compact]] and [[Fredholm operator]]s is applicable. The same methods work equally for the [[Neumann problem]].
<ref>See:
*{{harvnb|Folland|1995}}
*{{harvnb|Bers|John|Schechter|1979}}</ref>
 
==Generalizations==
Dirichlet problems are typical of [[elliptic partial differential equation]]s, and [[potential theory]], and the [[Laplace equation]] in particular. Other examples include the [[biharmonic equation]] and related equations in [[elasticity theory]].
 
They are one of several types of classes of PDE problems defined by the information given at the boundary, including [[Neumann problem]]s and [[Cauchy problem]]s.
 
==Notes==
{{reflist|2}}
 
==References==
* {{springer|author=A. Yanushauskas|id=d/d032910|title=Dirichlet problem}}
* S. G. Krantz, ''The Dirichlet Problem.''  §7.3.3 in ''Handbook of Complex Variables''. Boston, MA: Birkhäuser, p. 93, 1999. ISBN 0-8176-4011-8.
* S. Axler, P. Gorkin, K. Voss, ''[http://www.ams.org/mcom/2004-73-246/S0025-5718-03-01574-6/home.html The Dirichlet problem on quadratic surfaces]'' Mathematics of Computation '''73''' (2004), 637-651.
*{{Citation | last1=Gilbarg | first1=David | last2=Trudinger | first2=Neil S. | author2-link=Neil Trudinger | title=Elliptic partial differential equations of second order | publisher=[[Springer-Verlag]] | location=Berlin, New York | edition=2nd | isbn=978-3-540-41160-4 | year=2001}}
*Gérard, Patrick; [[Eric Leichtnam|Leichtnam, Éric]]: Ergodic properties of eigenfunctions for the Dirichlet problem. Duke Math. J. 71 (1993), no. 2, 559-607.
*{{citation|last=John|first= Fritz|title=Partial differential equations|edition=4th|series= Applied Mathematical Sciences|volume= 1|publisher= Springer-Verlag|year= 1982|id= ISBN 0-387-90609-6}}
*{{citation|last=Bers|first=Lipman|last2=John|first2=Fritz|last3= Schechter|first3= Martin|title=Partial differential equations, with supplements by Lars Gȧrding and A. N. Milgram|series= Lectures in Applied Mathematics|volume= 3A|publisher= American Mathematical Society|year=1979|id=ISBN 0-8218-0049-3}}
*{{citation|title=Lectures on Elliptic Boundary Value Problems|first=Shmuel|last= Agmon|authorlink=Shmuel Agmon|year=2010|publisher=American Mathematical Society|id=ISBN 0-8218-4910-7}}
* {{citation|first=Elias M.|last= Stein|authorlink=Elias Stein|year=1970|title=Singular Integrals and Differentiability Properties of Functions|publisher=Princeton University Press}}
*{{citation|last=Greene|first= Robert E.|last2= Krantz|first2= Steven G.|title= Function theory of one complex variable|edition=3rd|series= Graduate Studies in Mathematics|volume= 40|publisher= American Mathematical Society|year= 2006|id= ISBN 0-8218-3962-4}}
*{{citation| last=Taylor|first= Michael E.|title= Partial differential equations I. Basic theory|edition=2nd |series= Applied Mathematical Sciences|volume= 115|publisher=Springer|year=2011|id= ISBN 978-1-4419-70}}
*{{citation|last=Zimmer|first= Robert J.|title= Essential results of functional analysis|series= Chicago Lectures in Mathematics|publisher= University of Chicago Press|year= 1990|id= ISBN 0-226-98337-4}}
*{{citation|last=Folland|first= Gerald B.|title= Introduction to partial differential equations|edition=2nd|publisher=Princeton University Press|year=1995|id= ISBN 0-691-04361-2}}
*{{citation|title=Introduction to the Theory of Linear Partial Differential Equations|volume=14|series= Studies in Mathematics and Its Applications|first=Jacques|last= Chazarain|first2= Alain|last2= Piriou|publisher=Elsevier|year= 1982|id=ISBN 0444864520}}
*{{citation|last=Bell|first=Steven R.|title= The Cauchy transform, potential theory, and conformal mapping|series= Studies in Advanced Mathematics|publisher= CRC Press|year= 1992|id=ISBN 0-8493-8270-X}}
*{{citation|title=Foundations of Differentiable Manifolds and Lie Groups|series=Graduate Texts in Mathematics|volume= 94|year=1983|
first=Frank W.|last= Warner|id=ISBN 0387908943|publisher=Springer}}
*{{citation|title=Principles of Algebraic Geometry|first=Phillip |last=Griffiths|first2= Joseph|last2= Harris|publisher= Wiley Interscience| year=1994|id=ISBN  0471050598}}
*{{citation|last=Courant|first= R.|title=Dirichlet's Principle, Conformal Mapping, and Minimal Surfaces|
publisher=Interscience|year= 1950}}
*{{citation|last=Schiffer|first= M.|last2=Hawley|first2= N. S.|title=Connections and conformal mapping|journal=
Acta Math.|volume= 107|year= 1962|pages= 175–274}}
 
== External links ==
* {{MathWorld | urlname=DirichletProblem | title=Dirichlet Problem}}
* [http://math.fullerton.edu/mathews/c2003/DirichletProblemMod.html Dirichlet Problem Module by John H. Mathews]
 
[[Category:Potential theory]]
[[Category:Partial differential equations]]
[[Category:Fourier analysis]]
[[Category:Mathematical problems]]
 
[[ca:Problema de Dirichlet]]
[[es:Problema de Dirichlet]]
[[fr:Problème de Dirichlet]]
[[ko:디리클레 문제]]
[[ja:ディリクレ問題]]
[[pms:Problema ëd Dirichlet]]
[[pl:Problem Dirichleta]]
[[pt:Problema de Dirichlet]]
[[ru:Задача Дирихле]]
[[tr:Dirichlet problemi]]
[[zh:狄利克雷问题]]

Revision as of 08:38, 12 August 2014

In mathematics, directed-complete partial orders (abbreviated to dcpo or sometimes just cpo) are special classes of partially ordered sets, characterized by particular completeness properties. Complete partial orders play a central role in theoretical computer science, in denotational semantics and domain theory.

Definitions

A partially ordered set is a directed-complete partial order (dcpo) if each of its directed subsets has a supremum. Recall that a subset of a partial order is directed if it is non-empty and every pair of elements has an upper bound in the set. In the literature, dcpos sometimes also appear under the label up-complete poset or simply cpo.

In some contexts, the phrase ω-cpo (or just cpo) is used to describe a poset in which every ω-chain (x1≤x2≤x3≤x4≤...) has a supremum. Every dcpo is an ω-cpo.

An important role is played by dcpo's with a least element. They are sometimes called pointed dcpos, or cppos, or just cpos.

Requiring the existence of directed suprema can be motivated by viewing directed sets as generalized approximation sequences and suprema as limits of the respective (approximative) computations. This intuition, in the context of denotational semantics, was the motivation behind the development of domain theory.

The dual notion of a directed complete poset is called a filtered complete partial order. However, this concept occurs far less frequently in practice, since one usually can work on the dual order explicitly.

Examples

  • Every finite poset is directed complete.
  • All complete lattices are also directed complete.
  • For any poset, the set of all non-empty filters, ordered by subset inclusion, is a dcpo. Together with the empty filter it is also pointed. If the order has binary meets, then this construction (including the empty filter) actually yields a complete lattice.
  • The set of all partial functions on some given set S can be ordered by defining f ≤ g for functions f and g if and only if g extends f, i.e. if the domain of f is a subset of the domain of g and the values of f and g agree on all inputs for which both functions are defined. (Equivalently, f ≤ g if and only if f ⊆ g where f and g are identified with their respective graphs.) This order is a pointed dcpo, where the least element is the nowhere defined function (with empty domain). In fact, ≤ is also bounded complete. This example also demonstrates why it is not always natural to have a greatest element.
  • The specialization order of any sober space is a dcpo.
  • Let us use the term “deductive system” as a set of sentences closed under consequence (for defining notion of consequence, let us use e.g. Tarski's algebraic approach[1][2]). There are interesting theorems which concern a set of deductive systems being a directed complete partial ordering.[3] Also, a set of deductive systems can be chosen to have a least element in a natural way (so that it can be also a complete partial ordering), because the set of all consequences of the empty set (i.e. “the set of the logically provable / logically valid sentences”) is (1) a deductive system (2) contained by all deductive systems.

Properties

An ordered set P is a pointed dcpo if and only if every chain has a supremum in P. Alternatively, an ordered set P is a pointed dcpo if and only if every order-preserving self-map of P has a least fixpoint. Every set S can be turned into a pointed dcpo by adding a least element ⊥ and introducing a flat order with ⊥ ≤ s and s ≤ s for every s ∈ S and no other order relations.

Continuous functions and fixpoints

A function f between two dcpos P and Q is called (Scott) continuous if it maps directed sets to directed sets while preserving their suprema:

Note that every continuous function between dcpos is a monotone function. This notion of continuity is equivalent to the topological continuity induced by the Scott topology.

The set of all continuous functions between two dcpos P and Q is denoted [P → Q]. Equipped with the pointwise order, this is again a dcpo, and a cpo whenever Q is a cpo. Thus the complete partial orders with Scott continuous maps form a cartesian closed category.[4]

Every order-preserving self-map f of a cpo (P, ⊥) has a least fixpoint.[5] If f is continuous then this fixpoint is equal to the supremum of the iterates (⊥, f(⊥), f(f(⊥)), … fn(⊥), …) of ⊥ (see also the Kleene fixpoint theorem).

See also

Directed completeness relates in various ways to other completeness notions. Directed completeness alone is quite a basic property that occurs often in other order theoretic investigations, using for instance algebraic posets and the Scott topology.

Notes

  1. ↑ Tarski, Alfred: Bizonyítás és igazság / Válogatott tanulmányok. Gondolat, Budapest, 1990. (Title means: Proof and truth / Selected papers.)
  2. ↑ Stanley N. Burris and H.P. Sankappanavar: A Course in Universal Algebra
  3. ↑ See online in p. 24 exercises 5–6 of §5 in BurSan:UnivAlg. Or, on paper, see Tar:BizIg.
  4. ↑ Barendregt, Henk, The lambda calculus, its syntax and semantics, North-Holland (1984)
  5. ↑ See Knaster–Tarski theorem; The foundations of program verification, 2nd edition, Jacques Loeckx and Kurt Sieber, John Wiley & Sons, ISBN 0-471-91282-4, Chapter 4; the Knaster-Tarski theorem, formulated over cpo's, is given to prove as exercise 4.3-5 on page 90.

References

  • 20 year-old Real Estate Agent Rusty from Saint-Paul, has hobbies and interests which includes monopoly, property developers in singapore and poker. Will soon undertake a contiki trip that may include going to the Lower Valley of the Omo.

    My blog: http://www.primaboinca.com/view_profile.php?userid=5889534

fr:Ordre partiel complet (informatique) pl:Porządek zupełny ru:Частично упорядоченное множество#Полное частично упорядоченное множество zh:完全偏序

Retrieved from "https://en.formulasearchengine.com/index.php?title=Main_Page&oldid=44958"