Search

Abstract We deal with the approximate solution of initial value problems in infinite-dimensional Banach spaces with a Schauder basis. We only allow finite-dimensional algorithms acting in the spaces R N , with varying N. The error of such algorithms depends on two parameters: the truncation parameters N and a discretization parameter n. For a class of C r right-hand side functions, we define an algorithm with varying N , based on possibly non-uniform mesh, and we analyze its error and cost. For constant N , we show a matching (up to a constant) lower bound on the error of any algorithm in terms of N and n , as N , n → ∞. We stress that in the standard error analysis the dimension N is fixed, and the dependence on N is usually hidden in error coefficient. For a certain model of cost, for many cases of interest, we show tight (up to a constant) upper and lower bounds on the minimal cost of computing an ε -approximation to the solution (the ε -complexity of the problem). The results are illustrated by an example of the initial value problem in the weighted ℓ p space (1 ≤ p < ∞). [ABSTRACT FROM AUTHOR]

We study potential advantages of adaptive mesh point selection for the solution of systems of initial value problems. For an optimal order discretization method, we propose an algorithm for successive selection of the mesh points, which only requires evaluations of the right-hand side function. The selection (asymptotically) guarantees that the maximum local error of the method does not exceed a prescribed level. The usage of the algorithm is not restricted to the chosen method; it can also be applied with any method from a general class. We provide a rigorous analysis of the cost of the proposed algorithm. It is shown that the cost is almost minimal, up to absolute constants, among all mesh selection algorithms. For illustration, we specify the advantage of the adaptive mesh over the uniform one. Efficiency of the adaptive algorithm results from automatic adjustment of the successive mesh points to the local behavior of the solution. Some numerical results illustrating theoretical findings are reported. [ABSTRACT FROM AUTHOR]

Abstract It is known that, for systems of initial-value problems, algorithms using adaptive information perform much better in the worst case setting than the algorithms using nonadaptive information. In the latter case, lower and upper complexity bounds significantly depend on the number of equations. However, in contrast with adaptive information, existing lower and upper complexity bounds for nonadaptive information are not asymptotically tight. In this paper, we close the gap in the complexity exponents, showing asymptotically matching bounds for nonadaptive standard information, as well as for a more general class of nonadaptive linear information. [ABSTRACT FROM AUTHOR]

We discuss adaptive mesh point selection for the solution of scalar initial value problems. We consider a method that is optimal in the sense of the speed of convergence, and we aim at minimizing the local errors. Although the speed of convergence cannot be improved by using the adaptive mesh points compared to the equidistant points, we show that the factor in the error expression can be significantly reduced. We obtain formulas specifying the gain achieved in terms of the number of discretization subintervals, as well as in terms of the prescribed level of the local error. Both nonconstructive and constructive versions of the adaptive mesh selection are shown, and a numerical example is given. [ABSTRACT FROM AUTHOR]

We study the solution of two-point boundary-value problems for second order ODEs with boundary conditions imposed on the first derivative of the solution. The right-hand side function g is assumed to be r times ( r ≥ 1 ) continuously differentiable with the r th derivative being a Hölder function with exponent ϱ ∈ ( 0 , 1 ] . The boundary conditions are defined through a continuously differentiable function f . We define an algorithm for solving the problem with error of order m − ( r + ϱ ) and cost of order m log m evaluations of g and f and arithmetic operations, where m ∈ N . We prove that this algorithm is optimal up to the logarithmic factor in the cost. This yields that the worst-case ε -complexity of the problem (i.e., the minimal cost of solving the problem with the worst-case error at most ε > 0 ) is essentially Θ ( ( 1 / ε ) 1 / ( r + ϱ ) ) , up to a log 1 / ε factor in the upper bound. The same bounds hold for r + ϱ ≥ 2 even if we additionally assume convexity of g . For r = 1 , ϱ ∈ ( 0 , 1 ] and convex functions g , the information ε -complexity is shown to be Θ ( ( 1 / ε ) 1 / 2 ) . [ABSTRACT FROM AUTHOR]

We investigate the optimal solution of systems of initial-value problems with smooth right-hand side functions f from a Hölder class $F^{r,\varrho }_{\text {reg}}$, where r ≥ 0 is the number of continuous derivatives of f, and ϱ ∈ (0, 1] is the Hölder exponent of rth partial derivatives. We consider algorithms that use n evaluations of f, the ith evaluation being corrupted by a noise δ of deterministic or random nature. For δ ≥ 0, in the deterministic case the noise δ is a bounded vector, ∥ δ∥≤ δ. In the random case, it is a vector-valued random variable bounded in average, ( E(∥ δ∥)) ≤ δ, q ∈ [1, + ∞). We point out an algorithm whose L error ( p ∈ [0, + ∞]) is O( n + δ), independently of the noise distribution. We observe that the level n + δ cannot be improved in a class of information evaluations and algorithms. For ε > 0, and a certain model of δ-dependent cost, we establish optimal values of n( ε) and δ( ε) that should be used in order to get the error at most ε with minimal cost. [ABSTRACT FROM AUTHOR]

The paper deals with the solution of systems of IVPs with discontinuous right-hand side functions f . In our previous work we considered IVPs with continuous f  ’s having discontinuous derivatives. We assumed the global Lipschitz continuity of f , and the analysis was heavily based on that assumption. In the present paper we skip the continuity assumption. We assume that f is a piecewise regular function that satisfies the Lipschitz condition only in some regions of the domain. (By the regular function we mean a function belonging to a Hölder class.) A hypersurface where the regularity of f breaks down is not known. We define an algorithm DISC-IVP for solving such problems, and analyze its error and cost. The error analysis in the presence of discontinuities of f is essentially different than that in the continuous case. We show in a subclass of f  ’s that the worst-case error of the algorithm (measured in the conservative supremum norm over the interval of integration) is of the same order as for globally regular functions. The algorithm and the analysis do not use heuristic arguments. In particular, we are able to bound the cost of the algorithm, which leads to the bound on the ε-complexity of the problem (the minimal cost of computing an ε-approximation to the solution). The ε-complexity in the discontinuous case described above turns out to be of the same order as that in the globally regular case. In the other words, the solution of discontinuous problems is no more difficult than the solution of globally regular ones. Furthermore, the algorithm DISC-IVP is error and cost optimal. [ABSTRACT FROM AUTHOR]

It is well-known that classical integration schemes designed for regular systems of IVPs become inefficient for piecewise regular problems. To avoid a significant increase of the cost of obtaining an ε-approximation for piecewise regular problems, special adaptive algorithms are usually designed. Constructing such algorithms is often based on the knowledge of a 'switching function' whose zeros define the singularity hypersurface, or it relies on certain heuristic arguments. In this paper we analyze the worst-case ε-complexity of globally continuous and piecewise regular problems with unknown smooth switching function. We consider problems with right-hand side functions from the class Fr,ϱ which consists of piecewise r-smooth functions with Hölder r-th partial derivatives with the exponent ϱ∈(0,1]. In contrast to our previous work, we restrict ourselves to information defined only by values of the right-hand side function (computation of partial derivatives is not allowed). We design an algorithm that is based on the computation of Lagrange interpolation polynomials to locate singularity points and to approximate a function of a single variable at intermediate stages. A rigorous analysis (independent of heuristic arguments) of its error and cost is given. It turns out that both the error and the cost of the algorithm are of the same order as for regular problems. That is, no reduction of the order is observed when passing through singularities, and the cost of the algorithm remains at the same level as for regular problems. In the class Fr,ϱ the algorithm has the worst-case error O(m-(r+ϱ)) (in the Chebyshev norm) and the total cost O(m), where m is the number of discretization points. This leads to the conclusion that the worst-case ε-complexity of the considered problem in Fr,ϱ is Θ(ε-1/(r+ϱ)), and the minimal cost is achieved by the defined algorithm that only needs function evaluations. The auxiliary algorithm that locates singularities and approximates a piecewise regular function of a single variable is also original, and it may be of interest per se. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we are interested in a rigorous analysis of the solution of a class of initial-value problems with singularities. We consider scalar non-autonomous IVPs with separated variables and one unknown singularity in each variable (which leads to four unknown ‘events’ in the two-dimensional space). Many algorithms proposed in the literature for singular IVPs are practically oriented. They do not avoid heuristic arguments, and are often checked for efficiency by numerical experiments. We design an adaptive algorithm with no heuristic steps for solving the considered problems, and provide rigorous bounds on the error. We show that in spite of the presence of singularities the algorithm preserves the (optimal) error known for the regular case. Lower bounds on the error of any algorithm in the case of a larger number of singularities are also discussed. [Copyright &y& Elsevier]

Abstract: We study the solution of piecewise regular systems of IVPs with a switching hypersurface defined by an unknown event function. Our aim is to design an algorithm that is not based on heuristic steps, it does not use information on the event function and preserves the order known for regular systems. The algorithm is based on the adaptive mesh which differs from the equidistant mesh only by a single point. We provide a rigorous (that is, independent of heuristic arguments) analysis of its error and cost. [Copyright &y& Elsevier]

Abstract: We consider the root finding of a real-valued function defined on the -dimensional unit cube. We assume that has continuous partial derivatives, with all partial derivatives of order being Hölder functions with the exponent . We study the -complexity of this problem in three settings: deterministic, randomized and quantum. It is known that with the root error criterion the deterministic -complexity is infinite, i.e., the problem is unsolvable. We show that the same holds in the randomized and quantum settings. Under the residual error criterion, we show that the deterministic and randomized ε-complexity is of order . In the quantum setting, the -complexity is shown to be of order . This means that a quadratic speed-up is achieved on a quantum computer. [Copyright &y& Elsevier]

We deal with quantum and randomized algorithms for approximating a class of linear continuous functionals. The functionals are defined on a Hölder space of functions f of d variables with r continuous partial derivatives, the rth derivative being a Hölder function with exponent ρ. For a certain class of such linear problems (which includes the integration problem), we define algorithms based on partitioning the domain of f into a large number of small subdomains, and making use of the well-known quantum or randomized algorithms for summation of real numbers. For N information evaluations (quantum queries in the quantum setting), we show upper bounds on the error of order N in the quantum setting, and N in the randomized setting, where γ = ( r + ρ)/ d is the regularity parameter. Hence, we obtain for a wider class of linear problems the same upper bounds as those known for the integration problem. We give examples of functionals satisfying the assumptions, among which we discuss functionals defined on the solution of Fredholm integral equations of the second kind, with complete information about the kernel. We also provide lower bounds, showing in some cases sharpness of the obtained results, and compare the power of quantum, randomized and deterministic algorithms for the exemplary problems. [ABSTRACT FROM AUTHOR]

Abstract: The optimal solution of initial-value problems in ODEs is well studied for smooth right-hand side functions. Much less is known about the optimality of algorithms for singular problems. In this paper, we study the (worst case) solution of scalar problems with a right-hand side function having r continuous bounded derivatives in , except for an unknown singular point. We establish the minimal worst case error for such problems (which depends on r similarly as in the smooth case), and define optimal adaptive algorithms. The crucial point is locating an unknown singularity of the solution by properly adapting the grid. We also study lower bounds on the error of an algorithm for classes of singular problems. In the case of a single singularity with nonadaptive information, or in the case of two or more singularities, the error of any algorithm is shown to be independent of r. [Copyright &y& Elsevier]

Abstract: We establish essentially optimal bounds on the complexity of initial-value problems in the randomized and quantum settings. For this purpose we define a sequence of new algorithms whose error/cost properties improve from step to step. These algorithms yield new upper complexity bounds, which differ from known lower bounds by only an arbitrarily small positive parameter in the exponent, and a logarithmic factor. In both the randomized and quantum settings, initial-value problems turn out to be essentially as difficult as scalar integration. [Copyright &y& Elsevier]

Abstract: We study the problem, initiated by Kacewicz [Randomized and quantum algorithms yield a speed-up for initial-value problems, J. Complexity 20 (2004) 821–834; see also http://arXiv.org/abs/quant-ph/0311148], of finding randomized and quantum complexity of initial-value problems. We showed in Kacewicz (2004) that a speed-up in both settings over the worst-case deterministic complexity is possible. In the present paper we prove, by defining new algorithms, that further improvement in upper bounds on the randomized and quantum complexity can be achieved. In the Hölder class of right-hand side functions with r continuous bounded partial derivatives, with rth derivative being a Hölder function with exponent , the -complexity is shown to be in the randomized setting, and on a quantum computer (up to logarithmic factors). This is an improvement for the general problem over the results from Kacewicz (2004). The gap still remaining between upper and lower bounds on the complexity is further discussed for a special problem. We consider scalar autonomous problems, with the aim of computing the solution at the end point of the interval of integration. For this problem, we fill up the gap by establishing (essentially) matching upper and lower complexity bounds. We show that the complexity in this case is in the randomized setting, and in the quantum setting (again up to logarithmic factors). Hence, this problem is essentially as hard as the integration problem. [Copyright &y& Elsevier]

We discuss in this paper optimality properties of identification algorithms in a set membership framework. We deal with restricted-complexity (conditional) identification, where approximations (models) to a possibly complex system are selected from a low dimensional space. We discuss the worst- and average-case settings. In the worst-case setting, we present results on optimality, or suboptimality, of algorithms based on computing the unconditional or conditional Chebyshev centres of an uncertainty set. In the average-case setting, we show that the optimal algorithm is given by the projection of the unconditional Chebyshev centre. We show explicit formulas for its average errors, allowing us to see the contribution of all problem parameters to the minimal error. We discuss the case of weighted average errors corresponding to non-uniform distributions over uncertainty sets, and show how the weights influence the minimal identification error. [ABSTRACT FROM AUTHOR]