×

Error analysis of a randomized numerical method. (English) Zbl 0817.65058

The paper analyzes the performances of a family of randomized numerical methods for solving the purely deterministic initial value problem for the finite-dimensional system \(dy/dz= f(t, y)\); \(y(t_ 0)= y_ 0\), on a finite interval under the hypothesis that \(f\) is smooth in \(y\) but no more than bounded and measurable in \(t\). A probability model of a representative member of this family is studied: this is a random single- step method which generates a sequence \(Y_ k\) by \[ Y_{k+ 1}= Y_ k+ {h\over p} \sum^ p_{j= 1} \left\{{1\over 2}f(U_{jk}, Y_ k+ hf(u_{jk}, Y_ k))+ {1\over 2} f(u_{jk}, Y_ k)\right\}, \] \(U_{jk}= \max(T_{1jk}, T_{2jk})\), \(u_{jk}= \min(T_{1jk}, T_{2jk})\), where for each step \(\{T_{1jk}\}\) and \(\{T_{2jk}\}\) are fresh \(p\)-fold random samples of the uniform distribution on the numerical grid interval \([t_ k, t_ k+ h]\). The main results describe the asymptotic form of the error and give a weak law which with probability \(1- \beta\) bounds the error in terms of \(\beta\), \(h\) and \(p\):
Let \(t_ k= kh\), \(y_ k= y(t_ k)\), \(E_ k\) denote the expectation with respect to the uniform distribution on \([t_ k, t_{k+ 1}]\times [t_ k, t_{k+ 1}]\), and \[ F(t, s, u)= \textstyle{{1\over 2}} \{f(\max [t, s], u+ hf(\min[t, s], u)+ f(\min[t, s], u)\}, \]
\[ \sigma^ 2_{k+1} (h, u)= E_ k E_ k \{\| F(s_ 1, t_ 1, u)- F(s_ 2, t_ 2, u)\|^ 2\}, \]
\[ s^ 2_ k(h)= \sup_{| u- y_{k-1}|\leq d} \{\sigma^ 2_{k(h, u)}\},\;S^ 2(t, h)= h \sum_{t_ k\leq t} s^ 2_ k(h). \] Suppose there is an open neighborhood \(U\) in \(\mathbb{R}^{N+ 1}\) of the graph of the solution \(y(t)\) on which \(f\) and its \(y\)-partial derivatives up to order two are bounded and \(t\)-Borel measurable. Then there are positive constants \(L\) and \(h_ 0\) such that, given a level \(\beta> 0\), if \(\max[h, (h/p\beta)^{{1\over 2}} S(1, h)]< h_ 0\), then with probability not less than \(1-\beta\), \[ \| Y_ k- y(t_ k)\|< L\{h^ 2+(h/\beta p)^{{1\over 2}} S(t_ k, h)\}. \] {}.

MSC:

65L05 Numerical methods for initial value problems involving ordinary differential equations
65L06 Multistep, Runge-Kutta and extrapolation methods for ordinary differential equations
34A34 Nonlinear ordinary differential equations and systems
PDFBibTeX XMLCite
Full Text: DOI