Complexity of Nonlinear Two-Point Boundary-Value Problems

✍ Scribed by Bolesław Kacewicz

• Publisher: Elsevier Science
• Year: 2002
• Tongue: English
• Weight: 282 KB
• Volume: 18
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1006/jcom.2002.0643

✦ Synopsis

We study upper and lower bounds on the worst-case e-complexity of nonlinear two-point boundary-value problems. We deal with general systems of equations with general nonlinear boundary conditions, as well as with second-order scalar problems. Two types of information are considered: standard information defined by the values or partial derivatives of the right-hand-side function, and linear information defined by arbitrary linear functionals. The complexity depends significantly on the problem being solved and on the type of information allowed. We define algorithms based on standard or linear information, using perturbed Newton's iteration, which provide upper bounds on the e-complexity. The upper and lower bounds obtained differ by a factor of log log 1=e: Neglecting this factor, for general problems the e-complexity for the right-hand-side functions having r ðr52Þ continuous bounded partial derivatives turns out to be of order ð1=eÞ 1=r for standard information, and ð1=eÞ 1=ðrþ1Þ for linear information. For second-order scalar problems, linear information is even more powerful. The e-complexity in this case is shown to be of order ð1=eÞ 1=ðrþ2Þ ; while for standard information it remains at the same level as in the general case. # 2002 Elsevier Science (USA)