A fast nonlocal algorithm for solving Neumann-Dirichlet boundary value problems with error control


  • B.V. Semisalov Novosibirsk State University




boundary value problem, fast algorithm, estimation of error, collocation method, relaxation method, nonlocal algorithm without saturation


A method for searching numerical solutions to Neumann-Dirichlet boundary value problems for differential equations of elliptic type is proposed. This method allows reaching a desired accuracy with low consumption of memory and computer time. The method adapts the properties of best polynomial approximations for construction of algorithms without saturation on the basis of nonlocal Chebyshev approximations. A new approach to the approximation of differential operators and to solving the resulting problems of linear algebra is also proposed. Estimates of numerical errors are given. A high convergence rate of the proposed method is substantiated theoretically and is shown numerically in the case of problems with Cr-smooth and C∞-smooth solutions. Expressions for arrays approximating the differential operators in problems with various types of boundary conditions are obtained. These expressions allow the reader to quickly implement the method «from scratch».

Author Biography

B.V. Semisalov


  1. A. M. Blokhin and R. D. Alaev, Energy Integrals and Their Applications in the Stability Analysis of Difference Schemes (Novosibirsk, Novosibirsk Univ., 1993) [in Russian].
  2. K. I. Babenko, Fundamentals of Numerical Analysis (Nauka, Moscow, 1986) [in Russian].
  3. K. I. Babenko, “On the Saturation Phenomenon in Numerical Analysis,” Dokl. Akad. Nauk SSSR 241 (3), 505-508 (1978) [Sov. Math. Dokl. 19, 859-863 (1978)].
  4. B. V. Semisalov, “Non-Local Algorithm of Finding Solution to the Poisson Equation and Its Applications,” Zh. Vychisl. Mat. Mat. Fiz. 54 (7), 1110-1135 (2014).
  5. S. D. Algazin, Numerical Algorithms without Saturation in the Classical Problems of Mathematical Physics (Nauchnyi Mir, Moscow, 2002) [in Russian].
  6. V. N. Belykh, “Superconvergent Unsaturated Algorithms for the Numerical Solution of the Laplace Equation,” Sib. Zh. Ind. Mat. 5 (2), 36-52 (2002).
  7. V. N. Belykh, “On the Best Approximation Properties of 𝒞-Smooth Functions on an Interval of the Real Axis (to the Phenomenon of Unsaturated Numerical Methods),” Sib. Mat. Zh. 46 (3), 483-499 (2005) [Sib. Math. J. 46 (3), 373-385 (2005)].
  8. V. N. Belykh, “Particular Features of Implementation of an Unsaturated Numerical Method for the Exterior Axisymmetric Neumann Problem,” Sib. Mat. Zh. 54 (6), 1237-1249 (2013) [Sib. Math. J. 54 (6), 984-993 (2013)].
  9. D. Jackson, “On Approximation by Trigonometric Sums and Polynomials,” Trans. Amer. Math. Soc. 13, 491-515 (1912).
  10. S. N. Bernstein, “On the Best Approximation of Continuous Functions by Polynomials of a Given Degree,” Soobshch. Khar’kov Mat. Obshch. 13, 49-144 (1912).
  11. V. K. Dzyadyk, Introduction to the Theory of Uniform Approximation by Polynomials (Nauka, Moscow, 1977) [in Russian].
  12. N. S. Bakhvalov, N. P. Zhidkov, and G. M. Kobel’kov, Numerical Methods (Binom, Moscow, 2008) [in Russian].
  13. M. A. Lavrent’ev and B. V. Shabat, Methods of Theory of Functions of Complex Variable (Nauka, Moscow, 1973) [in Russian].
  14. H. Lebesgue, “Sur l’Approximation des Fonctions,” Bull. Sci. Math. Ser. 2 22, 278-287 (1898).
  15. V. K. Dzjadyk and V. V. Ivanov, “On Asymptotics and Estimates for the Uniform Norms of the Lagrange Interpolation Polynomials Corresponding to the Chebyshev Nodal Points,” Anal. Math. 9 (2), 85-97 (1983).
  16. S. K. Godunov and G. P. Prokopov, “On the Computation of Conformal Transformations and the Construction of Difference Meshes,” Zh. Vychisl. Mat. Mat. Fiz. 7 (5), 1031-1059 (1967) [USSR Comput. Math. Math. Phys. 7 (5), 89-124 (1967)].
  17. V. D. Liseikin, Yu. I. Shokin, I. A. Vaseva, and Yu. V. Likhanova, Grid Generation Technology (Nauka, Novosibirsk, 2009) [in Russian].
  18. A. M. Blokhin, A. S. Ibragimova, and B. V. Semisalov, “Designing of Computational Algorithm for System of Moment Equations which Describe Charge Transport in Semiconductors,” Mat. Mod. 21 (4), 15-34 (2009).
  19. V. A. Trenogin, Functional Analysis (Nauka, Moscow, 1980) [in Russian].
  20. A. A. Belov and N. N. Kalitkin, “Evolutionary Factorization and Superfast Relaxation Count,” Mat. Model. 26 (9), 47-64 (2014) [Math. Models Comput. Simul. 7 (2), 103-116 (2015)].
  21. A. N. Konovalov, Introduction to Computational Methods of Linear Algebra (Nauka, Novosibirsk, 1993) [in Russian].
  22. J. W. Demmel, Applied Numerical Linear Algebra (SIAM, Philadelphia, 1997; Mir, Moscow, 2001).
  23. R. D. Russell and L. F. Shampine, “A Collocation Method for Boundary Value Problems,” Numer. Math. 19, 1-28 (1972).



How to Cite

Семисалов Б.В. A Fast Nonlocal Algorithm for Solving Neumann-Dirichlet Boundary Value Problems With Error Control // Numerical Methods and Programming (Vychislitel’nye Metody i Programmirovanie). 2016. 17. 500-522. doi 10.26089/NumMet.v17r446



Section 1. Numerical methods and applications