Elements of the General Theory of Optimal Algorithms

Preface
Introduction
	References
Contents
List of Symbols and Abbreviations
Chapter 1: Elements of the Computing Theory
	1.1 Theory of Error Computations
	1.2 Problem Statement of Optimization of Computation
	1.3 Identification and Clarification of A Priori Information
	1.4 Accuracy Optimal Computational Algorithms
	1.5 Time Optimal Computational Algorithms
	1.6 Improvement of the Lower Estimate of the Accuracy of the Approximate Solving Problem by the Choice of Informational Operat...
	1.7 Basic Approaches to Constructing the Accuracy Optimal and Close to Them Quadrature and Cubature Formulae of Integrals Comp...
Chapter 2: Theories of Computational Complexity
	2.1 General Provisions. Statement of the Problem
	2.2 Algebraic Computing Complexity
		2.2.1 Formal Computational Models
		2.2.2 Asymptotic Qualities of ``Fast´´ Algorithms
	2.3 Analytic Computational Complexity
		2.3.1 Accuracy and Complexity of Computations
		2.3.2 Input Information, Algorithms, and Complexity of Computations
		2.3.3 Computer Architecture and the Complexity of Computation
	2.4 Complexity of Real Computation Processes
		2.4.1 On the Computer Constructing Technology of T-Efficient Computing Processes
		2.4.2 Specificity of Using Characteristic Estimates
	2.5 Examples of Using the Theory of Computational Complexity
		2.5.1 Classes of Computational Problems, Informational Operators, and Algorithms
			2.5.1.1 Approximation and Recovery of Functions and Functionals
			2.5.1.2 Digital Signal Processing
		2.5.2 Estimates of the Computational Complexity of Approximate Solutions of Certain Classes of Problems Constructing
			2.5.2.1 Approximation and Recovery of Functions and Functionals
			2.5.2.2 Digital Signal Processing
		2.5.3 T-Efficient Algorithms for Different Computing Models
			2.5.3.1 For Sequential Computational Models
				Approximation and Recovery of Functions and Functionalities
				Digital Signal Processing
			2.5.3.2 For Models of Parallel Computing
				Approximation and Recovery of Functions and Functionalities
				Digital Signal Processing
			2.5.3.3 For a Quantum Model Computation
Chapter 3: Interlineation of Functions
	3.1 Definition of Interlineation and Interflatation. Examples of Engineering Problems That Lead to Interlineation and Interfla...
		3.1.1 Examples of Engineering Problems That Lead to Interlineation and Interflatation
	3.2 Interlineation of Functions of Two Variables on M (M  2) Straight Lines with a Support of a Class CR (R2)
		3.2.1 Generalized d´Alembert´s Formula
		3.2.2 Lagrange´s and Hermite´s Interpolation Operators
		3.2.3 Interlineation of Functions on M (M  2) of Parallel Straight Lines in R2 with the Support of a Class Cr (R2)
		3.2.4 Rational Interlineation f(x,y) on a System of the Straight Lines with Support of a Class Cr (R2)
		3.2.5 A Generalized d´Alembert´s Formula for Functions of Three Variables
	3.3 Interlineation of the Functions of Two Variables on M (M  2) of the Straight Lines Without the Support of a Class CR (R2)
		3.3.1 Rational Interlineation on M Concurrent Straight Lines Without the Support of a Class CR (R2)
		3.3.2 Polynomial Interlineation on a System of Mutually Perpendicular Straight Lines
		3.3.3 The Best Lagrange´s Polynomial Interlineation in L1[-1;1]2 on the System of Mutually Perpendicular Straight Lines
		3.3.4 Polynomial Interlineation on Concurrence Without Supporting the Class CR (R2)
	3.4 Piecewise-Polynomial Interlineation
		3.4.1 Piecewise-Constant Splines
		3.4.2 Polynomial Splines of Orders r, r  1
		3.4.3 Spline-Interlineation. General Statements
		3.4.4 Spline-Interlination on the Lines of Rectangulation
	3.5 Trigonometric Interlineation
		3.5.1 Operators of Trigonometric Interlineation
		3.5.2 Periodic Spline-Interlineation
Chapter 4: Interflatation of Functions
	4.1 Rational Interflatation on M Planes in RN, N  3
		4.1.1 Interflatation of Functions. Definition
		4.1.2 Rational Interflatation on M Planes without Support of the Class Cr (Rn), N  3
	4.2 Polynomial Interflatation of Functions N, N  3 Variables with the Traces on the System of Planes that Are Parallel to the ...
		4.2.1 Interflatation on the System of Planes that Are Parallel to the Coordinates
		4.2.2 Lagrange´s Interflatation on the System of Planes xi = xi, j,
		4.2.3 Hermite´s Interflatation on the System of Planes xi = xi, j,
	4.3 Operators of the Spline Interflatation of the Functions N, N  3 Variables with the Traces on the System of the Planes that...
		4.3.1 Hermite´s Spline-Interflatation on the System of Planes xi = xi, j,
		4.3.2 Spline-Interflatation of Defect 1
	4.4 Operators of Polynomial Interflatation of the Functions of Three Variables with Traces in the System of Intersected Planes
	4.5 Trigonometric Interflatation of Functions N, N  3 of Variables with the Traces on the System of Planes that Are Parallel t...
	4.6 Economical Schemes of Spline-Interpolation of Functions of Three Variables that Are Constructed with Interflatation
	4.7 Generalized Lanczos Cubature Formula
		4.7.1 Generalized Green´s Formula
		4.7.2 Cubature Formula. Examples
	4.8 Interlination of Functions and Rvachov Structural Method
		4.8.1 Problems that cannot be Solved by Staying Only within the Structural Method and Method of R-Function
		4.8.2 Basic Principles of the Structural Method of Solving Mathematical Physics Problems
		4.8.3 Method of R-Function and Structural Method
		4.8.4 Interlineation on the Straight Lines that Are Parallel to the Coordinate Axes and at the Boundary of Arbitrary Domain G ...
		4.8.5 Interflatation on the System of Planes that Are Parallel to the Coordinate and on the Boundary of a Domain G  3
Chapter 5: Cubature Formulae Using Interlineation of Functions
	5.1 Formula of Rectangles for Functions of Two Variables
	5.2 Mixed Cubature Formula of Rectangles of r Order
	5.3 Cubature Formula of Central Rectangles
	5.4 Mixed Cubature Formula of Central Rectangles
	5.5 Cubature Formulae on the Basis of Spline-Interlination
		5.5.1 Cubature Formulae on the Basis of Product of Operators of Spline-Interpolation Functions
		5.5.2 Cubature Formulae for Composed Domains
	5.6 Quadrature and Cubature Formulae for the Fourier Coefficients Using the Interlineation of Functions
		5.6.1 Quadrature Formulae for Fourier Coefficients
		5.6.2 Cubature Formulae for the Fourier Coefficients on the Basis of the Spline-Interlineation Operators
	5.7 Smoliak Cubature Formulae
Chapter 6: Testing the Quality of Algorithm Programs
	6.1 Theoretical Bases of Quality Testing of Algorithm Programs
		6.1.1 On Systematization of Classes of Problems of Computational Mathematics
		6.1.2 Numerical Methods and Their Classification
		6.1.3 A Priori Information and Problem Characteristics
		6.1.4 Computational Algorithms and Their Classification
	6.2 Practical Aspects of Quality Testing of Algorithm Programs
		6.2.1 Subject and Objectives of Testing
		6.2.2 Testing Method
		6.2.3 Classification of Problems and Creation of Testing Sets
		6.2.4 Conducting of a Computational Experiment
		6.2.5 About the Use of Testing Results
	6.3 Examples of Use of Theory of Quality Testing of Algorithm Programs
Chapter 7: Computer Technologies of Solving Problems of Computational and Applied Mathematics with Fixed Values of Quality Cha...
	7.1 Computer Model of Computations. Problem Statement
	7.2 Conditions of Existence of ε-Solution of the Problem
	7.3 Reserves of Improving of Quality Characteristics of Solution and Computing Process
	7.4 Elements of the Technology of Solving Problem with Given Values of Characteristics of Quality
	7.5 Examples of Technology Use of the Problem Solution with Given Values of Characteristics of Quality to the Problem of Integ...
	7.6 Examples of the Problems Necessitating the Computation of Integrals from Fast-Oscillating Functions
About the Authors
Epilogue
Bibliography
Index