Lavrentiev regularization + Ritz approximation = uniform finite element error estimates for differential equations with rough coefficients
Authors:
Andrew Knyazev and Olof Widlund
Journal:
Math. Comp. 72 (2003), 1740
MSC (2000):
Primary 65N30, 35R05; Secondary 35J25, 35J70
Published electronically:
July 13, 2001
MathSciNet review:
1933812
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: We consider a parametric family of boundary value problems for a diffusion equation with a diffusion coefficient equal to a small constant in a subdomain. Such problems are not uniformly wellposed when the constant gets small. However, in a series of papers, Bakhvalov and Knyazev have suggested a natural splitting of the problem into two wellposed problems. Using this idea, we prove a uniform finite element error estimate for our model problem in the standard parameterindependent Sobolev norm. We also study uniform regularity of the transmission problem, needed for approximation. A traditional finite element method with only one additional assumption, namely, that the boundary of the subdomain with the small coefficient does not cut any finite element, is considered. One interpretation of our main theorem is in terms of regularization. Our FEM problem can be viewed as resulting from a Lavrentiev regularization and a RitzGalerkin approximation of a symmetric illposed problem. Our error estimate can then be used to find an optimal regularization parameter together with the optimal dimension of the approximation subspace.
 1.
G. P. Astrakhantsev, Method of fictitious domains for a secondorder elliptic equation with natural boundary conditions, U.S.S.R. Computational Math. and Math. Phys. 18 (1978), 114121.
 2.
N.
S. Bakhvalov and A.
V. Knyazev, Effective computation of averaged characteristics of
composites of periodic structure that consist of essentially different
materials, Dokl. Akad. Nauk SSSR 313 (1990),
no. 4, 777–781 (Russian); English transl., Soviet Math. Dokl.
42 (1991), no. 1, 57–62. MR 1080629
(92m:73007)
 3.
N.
S. Bakhvalov and A.
V. Knyazev, Fictitious domain methods and computation of
homogenized properties of composites with a periodic structure of
essentially different components, Numerical methods and applications,
CRC, Boca Raton, FL, 1994, pp. 221–266. MR 1282311
(95e:65113)
 4.
Nikolai
S. Bakhvalov and Andrew
V. Knyazev, Preconditioned iterative methods in a subspace for
linear algebraic equations with large jumps in the coefficients,
(University Park, PA, 1993) Contemp. Math., vol. 180, Amer. Math.
Soc., Providence, RI, 1994, pp. 157–162. MR 1312389
(95j:65042), http://dx.doi.org/10.1090/conm/180/01968
 5.
N. S. Bakhvalov, A. V. Knyazev, and G. M. Kobel'kov, Iterative methods for solving equations with highly varying coefficients, Fourth International Symposium on Domain Decomposition Methods for Partial Differential Equations (Philadelphia, PA) (Roland Glowinski, Yuri A. Kuznetsov, Gérard A. Meurant, Jacques Périaux, and Olof Widlund, eds.), SIAM, 1991, pp. 197205. CMP 91:12
 6.
N. S. Bakhvalov, A. V. Knyazev, and R. R. Parashkevov, Extension theorems for Stokes and Lamé equations for nearly incompressible media and their applications to numerical solution of problems with highly discontinuous coefficients, Numerical Linear Algebra with Applications. Accepted, May 2001.
 7.
N.
Bakhvalov and G.
Panasenko, Homogenisation: averaging processes in periodic
media, Mathematics and its Applications (Soviet Series), vol. 36,
Kluwer Academic Publishers Group, Dordrecht, 1989. Mathematical problems in
the mechanics of composite materials; Translated from the Russian by D.
Leĭtes. MR 1112788
(92d:73002)
 8.
A.
Bakushinsky and A.
Goncharsky, Illposed problems: theory and applications,
Mathematics and its Applications, vol. 301, Kluwer Academic Publishers
Group, Dordrecht, 1994. Translated from the Russian by I. V. Kochikov. MR 1325921
(96d:65101)
 9.
Alain
Bensoussan, JacquesLouis
Lions, and George
Papanicolaou, Asymptotic analysis for periodic structures,
Studies in Mathematics and its Applications, vol. 5, NorthHolland
Publishing Co., Amsterdam, 1978. MR 503330
(82h:35001)
 10.
Oleg
V. Besov, Valentin
P. Il′in, and Sergey
M. Nikol′skiĭ, Integral representations of functions
and imbedding theorems. Vol. I, V. H. Winston & Sons, Washington,
D.C., 1978. Translated from the Russian; Scripta Series in Mathematics;
Edited by Mitchell H. Taibleson. MR 519341
(80f:46030a)
Oleg
V. Besov, Valentin
P. Il′in, and Sergey
M. Nikol′skiĭ, Integral representations of functions
and imbedding theorems. Vol. II, V. H. Winston & Sons, Washington,
D.C., 1979. Scripta Series in Mathematics; Edited by Mitchell H. Taibleson.
MR 521808
(80f:46030b)
 11.
Christoph
Börgers and Olof
B. Widlund, On finite element domain imbedding methods, SIAM
J. Numer. Anal. 27 (1990), no. 4, 963–978. MR 1051116
(91g:65235), http://dx.doi.org/10.1137/0727055
 12.
B.
L. Buzbee, F.
W. Dorr, J.
A. George, and G.
H. Golub, The direct solution of the discrete Poisson equation on
irregular regions, SIAM J. Numer. Anal. 8 (1971),
722–736. MR 0292316
(45 #1403)
 13.
Philippe
G. Ciarlet, The finite element method for elliptic problems,
NorthHolland Publishing Co., Amsterdam, 1978. Studies in Mathematics and
its Applications, Vol. 4. MR 0520174
(58 #25001)
 14.
Martin
Costabel, Boundary integral operators on Lipschitz domains:
elementary results, SIAM J. Math. Anal. 19 (1988),
no. 3, 613–626. MR 937473
(89h:35090), http://dx.doi.org/10.1137/0519043
 15.
G. R. Cowper, Gaussian quadrature formulas for triangles, Int. J. Num. Meth. Eng. 7 (1973), 405408.
 16.
G. C. A. DeRose and A. R. Diaz, Single scale wavelet approximations in layout optimization, Struct. Optimization 18 (1999), no. 1, 111.
 17.
, Solving threedimensional layout optimization problems using fixed scale wavelets, Comput. Mech. 25 (2000), no. 23, 274285.
 18.
Alejandro
R. Díaz, A waveletGalerkin scheme for analysis of
largescale problems on simple domains, Internat. J. Numer. Methods
Engrg. 44 (1999), no. 11, 1599–1616. MR 1680220
(99m:80002), http://dx.doi.org/10.1002/(SICI)10970207(19990420)44:11<1599::AIDNME556>3.3.CO;2G
 19.
L.
Escauriaza, E.
B. Fabes, and G.
Verchota, On a regularity theorem for weak
solutions to transmission problems with internal Lipschitz
boundaries, Proc. Amer. Math. Soc.
115 (1992), no. 4,
1069–1076. MR 1092919
(92j:35020), http://dx.doi.org/10.1090/S00029939199210929191
 20.
Richard
S. Falk and John
E. Osborn, Remarks on mixed finite element
methods for problems with rough coefficients, Math. Comp. 62 (1994), no. 205, 1–19. MR 1203735
(94c:65136), http://dx.doi.org/10.1090/S00255718199412037351
 21.
P.
Grisvard, Elliptic problems in nonsmooth domains, Monographs
and Studies in Mathematics, vol. 24, Pitman (Advanced Publishing
Program), Boston, MA, 1985. MR 775683
(86m:35044)
 22.
P.
Grisvard, Singularities in boundary value problems, Recherches
en Mathématiques Appliquées [Research in Applied
Mathematics], vol. 22, Masson, Paris, 1992. MR 1173209
(93h:35004)
 23.
N.
Heuer and E.
P. Stephan, The PoincaréSteklov operator within countably
normed spaces, Mathematical aspects of boundary element methods
(Palaiseau, 1998), Chapman & Hall/CRC Res. Notes Math., vol. 414,
Chapman & Hall/CRC, Boca Raton, FL, 2000, pp. 152–164. MR 1719852
(2000j:65123)
 24.
V.
V. Jikov, S.
M. Kozlov, and O.
A. Oleĭnik, Homogenization of differential operators and
integral functionals, SpringerVerlag, Berlin, 1994. Translated from
the Russian by G. A. Yosifian [G. A. Iosif′yan]. MR 1329546
(96h:35003b)
 25.
R.
Bruce Kellogg, On the Poisson equation with intersecting
interfaces, Applicable Anal. 4 (1974/75),
101–129. Collection of articles dedicated to Nikolai Ivanovich
Muskhelishvili. MR 0393815
(52 #14623)
 26.
Carlos
E. Kenig, Harmonic analysis techniques for second order elliptic
boundary value problems, CBMS Regional Conference Series in
Mathematics, vol. 83, Published for the Conference Board of the
Mathematical Sciences, Washington, DC, 1994. MR 1282720
(96a:35040)
 27.
A. V. Knyazev, Iterative solution of PDE with strongly varying coefficients: algebraic version, Iterative Methods in Linear Algebra (Amsterdam) (R. Beauwens and P. de Groen, eds.), Elsevier, 1992, Proceedings IMACS Symp. Iterative Methods in Linear Algebra, Brussels, 1991, pp. 8589. CMP 92:11
 28.
Serge
Levendorskii, Degenerate elliptic equations, Mathematics and
its Applications, vol. 258, Kluwer Academic Publishers Group,
Dordrecht, 1993. MR 1247957
(95b:35079)
 29.
J.L.
Lions, Perturbations singulières dans les problèmes
aux limites et en contrôle optimal, Lecture Notes in
Mathematics, Vol. 323, SpringerVerlag, Berlin, 1973 (French). MR 0600331
(58 #29078)
 30.
T.A. Manteuffel, S. McCormick, and G. Starke, Firstorder systems leastsquares for secondorder elliptic problems with discontinuous coefficients, Proceedings of the Seventh Copper Mountain Conference on Multigrid Methods, Copper Mountain, CO, April 37, 1995, NASA Conference Publication 3339, Part 2, 1995, p. 551.
 31.
G. I. Marchuk, Yu. A. Kuznetsov, and A. M. Matsokin, Fictitious domain and domain decomposition methods, Soviet J. Numerical Analysis and Math. Modelling 1 (1986), 182.
 32.
William
McLean, Strongly elliptic systems and boundary integral
equations, Cambridge University Press, Cambridge, 2000. MR 1742312
(2001a:35051)
 33.
Serge
Nicaise and AnnaMargarete
Sändig, Transmission problems for the Laplace and elasticity
operators: regularity and boundary integral formulation, Math. Models
Methods Appl. Sci. 9 (1999), no. 6, 855–898. MR 1702865
(2000i:35022), http://dx.doi.org/10.1142/S0218202599000403
 34.
O.
A. Oleĭnik, A.
S. Shamaev, and G.
A. Yosifian, Mathematical problems in elasticity and
homogenization, Studies in Mathematics and its Applications,
vol. 26, NorthHolland Publishing Co., Amsterdam, 1992. MR 1195131
(93k:35025)
 35.
R.
Plato and G.
Vainikko, On the regularization of projection methods for solving
illposed problems, Numer. Math. 57 (1990),
no. 1, 63–79. MR 1043802
(91h:65097), http://dx.doi.org/10.1007/BF01386397
 36.
W. Proskurowski and O. Widlund, A finite element  capacitance matrix method for the Neumann problem for Laplace's equation, SIAM Stat. and Sci. Comput. 1 (1980), 410425.
 37.
Włodzimierz
Proskurowski and Olof
Widlund, A finite elementcapacitance matrix method for the Neumann
problem for Laplace’s equation, SIAM J. Sci. Statist. Comput.
1 (1980), no. 4, 410–425. MR 610753
(83e:65164), http://dx.doi.org/10.1137/0901029
 38.
Enrique
SánchezPalencia, Nonhomogeneous media and vibration
theory, Lecture Notes in Physics, vol. 127, SpringerVerlag,
Berlin, 1980. MR
578345 (82j:35010)
 39.
V. K. Saul'ev, On solving boundary value problems with high performance computers by a fictitious domain method, Siberian Math. J. 4 (1963), no. 4, 912, (In Russian).
 40.
Giuseppe
Savaré, Regularity results for elliptic equations in
Lipschitz domains, J. Funct. Anal. 152 (1998),
no. 1, 176–201. MR 1600081
(2000d:35046), http://dx.doi.org/10.1006/jfan.1997.3158
 41.
V.
V. Vasin and A.
L. Ageev, Illposed problems with a priori information,
Inverse and Illposed Problems Series, VSP, Utrecht, 1995. MR 1374573
(97j:65100)
 42.
Olof B. Widlund, An extension theorem for finite element spaces with three applications, Numerical Techniques in Continuum Mechanics (Braunschweig/Wiesbaden) (Wolfgang Hackbusch and Kristian Witsch, eds.), Notes on Numerical Fluid Mechanics, v. 16, Friedr. Vieweg und Sohn, 1987, Proceedings of the Second GAMMSeminar, Kiel, January, 1986, pp. 110122.
 1.
 G. P. Astrakhantsev, Method of fictitious domains for a secondorder elliptic equation with natural boundary conditions, U.S.S.R. Computational Math. and Math. Phys. 18 (1978), 114121.
 2.
 N. S. Bakhvalov and A. V. Knyazev, Efficient computation of averaged characteristics of composites of a periodic structure of essentially different materials, Soviet Math. Doklady 42 (1991), no. 1, 5762. MR 92m:73007
 3.
 , Fictitious domain methods and computation of homogenized properties of composites with a periodic structure of essentially different components, Numerical Methods and Applications (Gury I. Marchuk, ed.), CRC Press, Boca Raton, 1994, pp. 221276. MR 95e:65113
 4.
 , Preconditioned iterative methods in a subspace for linear algebraic equations with large jumps in the coefficients, Domain Decomposition Methods in Science and Engineering (D. Keyes and J. Xu, eds.), Contemporary Mathematics, vol. 180, American Mathematical Society, Providence, 1994, Proceedings of the Seventh International Conference on Domain Decomposition, October 2730, 1993, held at the Pennsylvania State University, pp. 157162. MR 95j:65042
 5.
 N. S. Bakhvalov, A. V. Knyazev, and G. M. Kobel'kov, Iterative methods for solving equations with highly varying coefficients, Fourth International Symposium on Domain Decomposition Methods for Partial Differential Equations (Philadelphia, PA) (Roland Glowinski, Yuri A. Kuznetsov, Gérard A. Meurant, Jacques Périaux, and Olof Widlund, eds.), SIAM, 1991, pp. 197205. CMP 91:12
 6.
 N. S. Bakhvalov, A. V. Knyazev, and R. R. Parashkevov, Extension theorems for Stokes and Lamé equations for nearly incompressible media and their applications to numerical solution of problems with highly discontinuous coefficients, Numerical Linear Algebra with Applications. Accepted, May 2001.
 7.
 N. S. Bakhvalov and G. P. Panasenko, Homogenization: Averaging of processes in periodic media. Mathematical problems in the mechanics of composite materials, Mathematics and Its Applications. Soviet Series, vol. 36, Kluwer Academic Publishers, Dordrecht/Boston/London, 1989. MR 92d:73002
 8.
 A. Bakushinsky and A. Goncharsky, Illposed problems: Theory and applications, Mathematics and Its Applications, vol. 301, Kluwer Academic Publishers, Dordrecht/Boston/London, 1994. MR 96d:65101
 9.
 Alain Bensoussan, JacquesLouis Lions, and George Papanicolaou, Asymptotic analysis for periodic structures, Studies in Mathematics and its Applications, vol. 5, NorthHolland Publishing Co., Amsterdam, 1978. MR 82h:35001
 10.
 O. V. Besov, V. P. Il'in, and S. M. Nikol'skii, Integral representations of functions and imbedding theorems, vols. 1, 2, Wiley, New York, 1979. MR 80f:46030a; MR 80f:46030b
 11.
 Ch. Börgers and O. Widlund, On finite element domain imbedding methods, SIAM J. Numer. Anal. 27 (1990), no. 4, 963978. MR 91g:65235
 12.
 B. L. Buzbee, F. W. Dorr, J. A. George, and G. Golub, The direct solution of the discrete Poisson equation on irregular regions, SIAM J. Numer. Anal. 8 (1971), 722736. MR 45:1403
 13.
 Philippe G. Ciarlet, The finite element method for elliptic problems, NorthHolland Publishing Co., Amsterdam, 1978, Studies in Mathematics and its Applications, Vol. 4. MR 58:25001
 14.
 Martin Costabel, Boundary integral operators on Lipschitz domains: elementary results, SIAM J. Math. Anal. 19 (1988), no. 3, 613626. MR 89h:35090
 15.
 G. R. Cowper, Gaussian quadrature formulas for triangles, Int. J. Num. Meth. Eng. 7 (1973), 405408.
 16.
 G. C. A. DeRose and A. R. Diaz, Single scale wavelet approximations in layout optimization, Struct. Optimization 18 (1999), no. 1, 111.
 17.
 , Solving threedimensional layout optimization problems using fixed scale wavelets, Comput. Mech. 25 (2000), no. 23, 274285.
 18.
 A. R. Diaz, A waveletGalerkin scheme for analysis of largescale problems on simple domains, International Journal for Numerical Methods in Engineering 44 (1999), no. 11, 15991616. MR 99m:80002
 19.
 L. Escauriaza, E. B. Fabes, and G. Verchota, On a regularity theorem for weak solutions to transmission problems with internal Lipschitz boundaries, Proc. Amer. Math. Soc. 115 (1992), no. 4, 10691076. MR 92j:35020
 20.
 Richard S. Falk and John E. Osborn, Remarks on mixed finite element methods for problems with rough coefficients, Math. Comp. 62 (1994), no. 205, 119. MR 94c:65136
 21.
 P. Grisvard, Elliptic problems in nonsmooth domains, Pitman (Advanced Publishing Program), Boston, Mass., 1985. MR 86m:35044
 22.
 , Singularities in boundary value problems, Masson, Paris, 1992. MR 93h:35004
 23.
 N. Heuer and E. P. Stephan, The PoincaréSteklov operator within countably normed spaces, Mathematical aspects of boundary element methods (Palaiseau, 1998), Chapman & Hall/CRC, Boca Raton, FL, 2000, pp. 152164. MR 2000j:65123
 24.
 V. V. Jikov, S. M. Kozlov, and O. A. Olenik, Homogenization of differential operators and integral functionals, SpringerVerlag, Berlin, 1994, Translated from the Russian by G. A. Yosifian [G. A. Iosifyan]. MR 96h:35003b
 25.
 R. Bruce Kellogg, On the Poisson equation with intersecting interfaces, Applicable Anal. 4 (1974/75), 101129, Collection of articles dedicated to Nikolai Ivanovich Muskhelishvili. MR 52:14623
 26.
 Carlos E. Kenig, Harmonic analysis techniques for second order elliptic boundary value problems, Published for the Conference Board of the Mathematical Sciences, Washington, DC, 1994. MR 96a:35040
 27.
 A. V. Knyazev, Iterative solution of PDE with strongly varying coefficients: algebraic version, Iterative Methods in Linear Algebra (Amsterdam) (R. Beauwens and P. de Groen, eds.), Elsevier, 1992, Proceedings IMACS Symp. Iterative Methods in Linear Algebra, Brussels, 1991, pp. 8589. CMP 92:11
 28.
 Serge Levendorskii, Degenerate elliptic equations, Mathematics and its Applications, vol. 258, Kluwer Academic Publishers Group, Dordrecht, 1993. MR 95b:35079
 29.
 J. L. Lions, Perturbations singuliéres dans les problémes aux limites et en contrôle optimal, Lecture Notes in Mathematics, vol. 323, SpringerVerlag, New York, 1973. MR 58:29078
 30.
 T.A. Manteuffel, S. McCormick, and G. Starke, Firstorder systems leastsquares for secondorder elliptic problems with discontinuous coefficients, Proceedings of the Seventh Copper Mountain Conference on Multigrid Methods, Copper Mountain, CO, April 37, 1995, NASA Conference Publication 3339, Part 2, 1995, p. 551.
 31.
 G. I. Marchuk, Yu. A. Kuznetsov, and A. M. Matsokin, Fictitious domain and domain decomposition methods, Soviet J. Numerical Analysis and Math. Modelling 1 (1986), 182.
 32.
 William McLean, Strongly elliptic systems and boundary integral equations, Cambridge University Press, Cambridge, 2000. MR 2001a:35051
 33.
 Serge Nicaise and AnnaMargarete Sändig, Transmission problems for the Laplace and elasticity operators: regularity and boundary integral formulation, Math. Models Methods Appl. Sci. 9 (1999), no. 6, 855898. MR 2000i:35022
 34.
 O. A. Olenik, A. S. Shamaev, and G. A. Yosifian, Mathematical problems in elasticity and homogenization, Studies in Mathematics and its Applications, vol. 26, NorthHolland Publishing Co., Amsterdam, 1992. MR 93k:35025
 35.
 R. Plato and Vainikko G., On the regularization of projection methods for solving illposed problems, Numerische Mathematik 57 (1990), 6379. MR 91h:65097
 36.
 W. Proskurowski and O. Widlund, A finite element  capacitance matrix method for the Neumann problem for Laplace's equation, SIAM Stat. and Sci. Comput. 1 (1980), 410425.
 37.
 Alfio Quarteroni and Alberto Valli, Domain decomposition methods for partial differential equations, Oxford University Press, Oxford, 1999. MR 83e:65164
 38.
 Enrique SánchezPalencia, Nonhomogeneous media and vibration theory, Lecture Notes in Physics, vol. 127, SpringerVerlag, Berlin, 1980. MR 82j:35010
 39.
 V. K. Saul'ev, On solving boundary value problems with high performance computers by a fictitious domain method, Siberian Math. J. 4 (1963), no. 4, 912, (In Russian).
 40.
 Giuseppe Savaré, Regularity results for elliptic equations in Lipschitz domains, J. Funct. Anal. 152 (1998), no. 1, 176201. MR 2000d:35046
 41.
 V. V. Vasin and A. L. Ageev, Illposed problems with a priori information, Inverse and Illposed problems series, VSP, Utrecht, The Netherlands, 1995. MR 97j:65100
 42.
 Olof B. Widlund, An extension theorem for finite element spaces with three applications, Numerical Techniques in Continuum Mechanics (Braunschweig/Wiesbaden) (Wolfgang Hackbusch and Kristian Witsch, eds.), Notes on Numerical Fluid Mechanics, v. 16, Friedr. Vieweg und Sohn, 1987, Proceedings of the Second GAMMSeminar, Kiel, January, 1986, pp. 110122.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2000):
65N30,
35R05,
35J25,
35J70
Retrieve articles in all journals
with MSC (2000):
65N30,
35R05,
35J25,
35J70
Additional Information
Andrew Knyazev
Affiliation:
Department of Mathematics, University of Colorado at Denver P.O. Box 173364, Campus Box 170, Denver, Colorado 802173364
Email:
knyazev@nanet.ornl.gov
Olof Widlund
Affiliation:
Courant Institute of Mathematical Sciences, 251 Mercer Street, New York, New York 10012
Email:
widlund@cs.nyu.edu
DOI:
http://dx.doi.org/10.1090/S0025571801013783
PII:
S 00255718(01)013783
Keywords:
Galerkin,
Lavrentiev,
Ritz,
Tikhonov,
discontinuous coefficients,
error estimate,
finite elements,
regularization,
regularity,
transmission problem,
fictitious domain,
embedding
Received by editor(s):
May 19, 1998
Received by editor(s) in revised form:
December 28, 2000
Published electronically:
July 13, 2001
Additional Notes:
The first author was supported by NSF Grant DMS9501507
The second author was supported in part by NSF Grant CCR9732208 and in part by the U.S. Department of Energy under contract DEFG0292ER25127
Article copyright:
© Copyright 2001 American Mathematical Society
