共查询到20条相似文献,搜索用时 31 毫秒
1.
J. -P. Berrut 《Computing》1990,44(1):69-82
We want to approximate the valueLf of some bounded linear functionalL (e.g., an integral or a function evaluation) forf∈H 2 by a linear combination Σ j=0 j=0 a j f j , wheref j:=f(z j) for some pointsz j in the unit disk and the numbersa j are to be chosen independent off j. Using ideas of Sard, Larkin has shown that, for the errorLf?Σ j=0 j=0 a j f j to be minimal,a j must be chosen such that Σ j=0 j=0 a j f j =Lf ⊥ for the rational function \(f^ \bot (z) = \sum\nolimits_{j = 0}^n {\{ \prod\nolimits_{k = 0}^n {(1 - \bar z_k z_j )/\prod\nolimits_{k = 0}^n {(1 - \bar z_k z)} } \} l_j } (z)f_j \) , in whichl j (z) are the Lagrange polynomials. Evaluatingf ⊥ as given above requriesO(n 2) operations for everyz. We give here formulae, patterned after the barycentric formulae for polynomial, trigonometric and rational interpolation, which permit the evaluation off ⊥ inO(n) operations for everyz, once some weights (that are independent ofz) have been computed. Moreover, we show that certain rational approximants introduced by F. Stenger (Math. Comp., 1986) can be interpreted as special cases of Larkin's interpolants, and are therefore optimal in the sense of Sard for the corresponding points. 相似文献
2.
CAO FeiLong ZHANG YongQuan & XU ZongBen College of Science China Jiliang University Hangzhou China Institute of Information System Sciences Xi’an Jiaotong University Xi’an 《中国科学F辑(英文版)》2009,52(8):1321-1327
Let SFd and Πψ,n,d = { nj=1bjψ(ωj·x+θj) :bj,θj∈R,ωj∈Rd} be the set of periodic and Lebesgue’s square-integrable functions and the set of feedforward neural network (FNN) functions, respectively. Denote by dist (SF d, Πψ,n,d) the deviation of the set SF d from the set Πψ,n,d. A main purpose of this paper is to estimate the deviation. In particular, based on the Fourier transforms and the theory of approximation, a lower estimation for dist (SFd, Πψ,n,d) is proved. That is, dist(SF d, Πψ,n,d) (nlogC2n)1/2 . T... 相似文献
3.
M. M. Cecchi 《Calcolo》1967,4(3):363-368
The numerical integration of integrals of the type
dx is carried out through an approximate quadrature formula of the Gauss type
where the abscissasx
i and the weighting coefficientsA
i
are evaluated with the requirement that the above formula be exact when thef(x) are polynomials of the highest possible degree.
相似文献
4.
We present results of computational experiments with an extension of the Perceptron algorithm by a special type of simulated annealing. The simulated annealing procedure employs a logarithmic cooling schedule
, where
is a parameter that depends on the underlying configuration space. For sample sets S of n-dimensional vectors generated by randomly chosen polynomials
, we try to approximate the positive and negative examples by linear threshold functions. The approximations are computed by both the classical Perceptron algorithm and our extension with logarithmic cooling schedules. For
and
, the extension outperforms the classical Perceptron algorithm by about 15% when the sample size is sufficiently large. The parameter was chosen according to estimations of the maximum escape depth from local minima of the associated energy landscape.
相似文献
5.
Battle and Lemarie derived independently wavelets by orthonormalizing B-splines. The scaling function
m
(t) corresponding to Battle–Lemarie's wavelet
m
(t) is given by
, where B
m(t) is the mth-order central B-spline and the coefficients
m, k
satisfy
. In this paper, we propose an FFT-based algorithm for computing the expansion coefficients
m, k
and the two-scale relations of the scaling functions and wavelets. The algorithm is very simple and it can be easily implemented. Moreover, the expansion coefficients can be efficiently and accurately obtained via multiple sets of FFT computations. The computational approach presented in this paper here is noniterative and is more efficient than the matrix approach recently proposed in the literature. 相似文献
6.
We prove that the concept class of disjunctions cannot be pointwise approximated by linear combinations of any small set of
arbitrary real-valued functions. That is, suppose that there exist functions f1, ?, fr\phi_{1}, \ldots , \phi_{r} : {− 1, 1}n →
\mathbbR{\mathbb{R}} with the property that every disjunction f on n variables has $\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi
_{i}\|_{\infty}\leq 1/3$\|f - \sum\nolimits_{i=1}^{r} \alpha_{i}\phi
_{i}\|_{\infty}\leq 1/3 for some reals a1, ?, ar\alpha_{1}, \ldots , \alpha_{r}. We prove that then $r \geq
exp \{\Omega(\sqrt{n})\}$r \geq
exp \{\Omega(\sqrt{n})\}, which is tight. We prove an incomparable lower bound for the concept class of decision lists. For the concept class of majority
functions, we obtain a lower bound of W(2n/n)\Omega(2^{n}/n) , which almost meets the trivial upper bound of 2n for any concept class. These lower bounds substantially strengthen and generalize the polynomial approximation lower bounds of Paturi
(1992) and show that the regression-based agnostic learning algorithm of Kalai et al. (2005) is optimal. 相似文献
7.
We present an approximation algorithm for solving graph problems in which a low-cost set of edges must be selected that has
certain vertex-connectivity properties. In the survivable network design problem, a valuer
ij
for each pair of verticesi andj is given, and a minimum-cost set of edges such that there arer
ij
vertex-disjoint paths between verticesi andj must be found. In the case for whichr
ij
∈{0, 1, 2} for alli, j, we can find a solution of cost no more than three times the optimal cost in polynomial time. In the case in whichr
ij
=k for alli, j, we can find a solution of cost no more than 2H(k) times optimal, where
. No approximation algorithms were previously known for these problems. Our algorithms rely on a primal-dual approach which
has recently led to approximation algorithms for many edge-connectivity problems.
This research was supported by NSF Grant CCR-91-03937 and a DIMACS postdoctoral fellowship, and was conducted in part while
the author was visiting MIT.
This research was supported by an NSF Graduate Fellowship and an NSF Postdoctoral Fellowship, and was conducted in part while
the author was a graduate student at MIT and in part while a postdoc at Cornell. 相似文献
8.
Paul E. Dunne 《Acta Informatica》1985,22(2):229-240
Summary The k-th threshold function, T
k
n
, is defined as:
where x
i{0,1} and the summation is arithmetic. We prove that any monotone network computing T
3/n(x
1,...,x
n) contains at least 2.5n-5.5 gates.This research was supported by the Science and Engineering Research Council of Great Britain, UK 相似文献
9.
E. A. Timofeev 《Automatic Control and Computer Sciences》2017,51(7):586-591
Let Ω = AN be a space of right-sided infinite sequences drawn from a finite alphabet A = {0,1}, N = {1,2,…}. Let ρ(x, y)Σk=1∞|x k ? y k |2?k be a metric on Ω = AN, and μ the Bernoulli measure on Ω with probabilities p0, p1 > 0, p0 + p1 = 1. Denote by B(x,ω) an open ball of radius r centered at ω. The main result of this paper \(\mu (B(\omega ,r))r + \sum\nolimits_{n = 0}^\infty {\sum\nolimits_{j = 0}^{{2^n} - 1} {{\mu _{n,j}}} } (\omega )\tau ({2^n}r - j)\), where τ(x) = 2min {x,1 ? x}, 0 ≤ x ≤ 1, (τ(x) = 0, if x < 0 or x > 1 ), \({\mu _{n,j}}(\omega ) = (1 - {p_{{\omega _{n + 1}}}})\prod _{k = 1}^n{p_{{\omega _k}}} \oplus {j_k}\), \(j = {j_1}{2^{n - 1}} + {j_2}{2^{n - 2}} + ... + {j_n}\). The family of functions 1, x, τ(2 n r ? j), j = 0,1,…, 2 n ? 1, n = 0,1,…, is the Faber–Schauder system for the space C([0,1]) of continuous functions on [0, 1]. We also obtain the Faber–Schauder expansion for Lebesgue’s singular function, Cezaro curves, and Koch–Peano curves. Article is published in the author’s wording. 相似文献
10.
Given a “black box” function to evaluate an unknown rational polynomial
f ? \mathbbQ[x]f \in {\mathbb{Q}}[x] at points modulo a prime p, we exhibit algorithms to compute the representation of the polynomial in the sparsest shifted power basis. That is, we determine
the sparsity $t \in {\mathbb{Z}}_{>0}$t \in {\mathbb{Z}}_{>0}, the shift
a ? \mathbbQ\alpha \in {\mathbb{Q}}, the exponents 0 £ e1 < e2 < ? < et{0 \leq e_{1} < e_{2} < \cdots < e_{t}}, and the coefficients
c1, ?, ct ? \mathbbQ \{0}c_{1}, \ldots , c_{t} \in {\mathbb{Q}} \setminus \{0\} such that
f(x) = c1(x-a)e1+c2(x-a)e2+ ?+ct(x-a)etf(x) = c_{1}(x-\alpha)^{e_{1}}+c_{2}(x-\alpha)^{e_{2}}+ \cdots +c_{t}(x-\alpha)^{e_{t}} 相似文献
11.
In this paper, a class of two-dimensional shunting inhibitory cellular neural networks with time-varying delays and variable coefficients as following system
12.
In this paper we construct an interpolatory quadrature formula of the type $$\mathop {\rlap{--} \smallint }\limits_{ - 1}^1 \frac{{f'(x)}}{{y - x}}dx \approx \sum\limits_{i = 1}^n {w_{ni} (y)f(x_{ni} )} ,$$ wheref(x)=(1?x)α(1+x)β f o(x), α, β>0, and {x ni} are then zeros of then-th degree Chebyshev polynomial of the first kind,T n (x). We also give a convergence result and examine the behavior of the quantity \( \sum\limits_{i = 1}^n {|w_{ni} (y)|} \) asn→∞. 相似文献
13.
Algebraic immunity is a new cryptographic criterion proposed against algebraic attacks. In order to resist algebraic attacks,
Boolean functions used in many stream ciphers should possess high algebraic immunity. This paper presents two main results
to find balanced Boolean functions with maximum algebraic immunity. Through swapping the values of two bits, and then generalizing
the result to swap some pairs of bits of the symmetric Boolean function constructed by Dalai, a new class of Boolean functions
with maximum algebraic immunity are constructed. Enumeration of such functions is also given. For a given function p(x) with deg(p(x)) < , we give a method to construct functions in the form p(x)+q(x) which achieve the maximum algebraic immunity, where every term with nonzero coefficient in the ANF of q(x) has degree no less than .
Supported by the National Natural Science Foundation of China (Grant No. 60673068), and the Natural Science Foundation of
Shandong Province (Grant Nos. Y2007G16, Y2008G01) 相似文献
14.
Tools for computational differentiation transform a program that computes a numerical function F(x) into a related program that computes F(x) (the derivative of F). This paper describes how techniques similar to those used in computational-differentiation tools can be used to implement other program transformations—in particular, a variety of transformations for computational divided differencing. The specific technical contributions of the paper are as follows:– It presents a program transformation that, given a numerical function F(x) defined by a program, creates a program that computes F[x
0, x
1], the first divided difference of F(x), where
– It shows how computational first divided differencing generalizes computational differentiation.– It presents a second program transformation that permits the creation of higher-order divided differences of a numerical function defined by a program.– It shows how to extend these techniques to handle functions of several variables.The paper also discusses how computational divided-differencing techniques could lead to faster and/or more robust programs in scientific and graphics applications.Finally, the paper describes how computational divided differencing relates to the numerical-finite-differencing techniques that motivated Robert Paige's work on finite differencing of set-valued expressions in SETL programs. 相似文献
15.
V. R. Fatalov 《Problems of Information Transmission》2010,46(2):160-183
Let {ξ
k
}
k=0∞ be a sequence of i.i.d. real-valued random variables, and let g(x) be a continuous positive function. Under rather general conditions, we prove results on sharp asymptotics of the probabilities
$
P\left\{ {\frac{1}
{n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\}
$
P\left\{ {\frac{1}
{n}\sum\limits_{k = 0}^{n - 1} {g\left( {\xi _k } \right) < d} } \right\}
, n → ∞, and also of their conditional versions. The results are obtained using a new method developed in the paper, namely,
the Laplace method for sojourn times of discrete-time Markov chains. We consider two examples: standard Gaussian random variables
with g(x) = |x|
p
, p > 0, and exponential random variables with g(x) = x for x ≥ 0. 相似文献
16.
John P. Boyd 《Journal of scientific computing》2006,29(1):1-24
In constructing local Fourier bases and in solving differential equations with nonperiodic solutions through Fourier spectral algorithms, it is necessary to solve the Fourier Extension Problem. This is the task of extending a nonperiodic function, defined on an interval
, to a function
which is periodic on the larger interval
. We derive the asymptotic Fourier coefficients for an infinitely differentiable function which is one on an interval
, identically zero for
, and varies smoothly in between. Such smoothed “top-hat” functions are “bells” in wavelet theory. Our bell is (for x ≥ 0)
where
where
. By applying steepest descents to approximate the coefficient integrals in the limit of large degree j, we show that when the width L is fixed, the Fourier cosine coefficients a
j
of
on
are proportional to
where Λ(j) is an oscillatory factor of degree given in the text. We also show that to minimize error in a Fourier series truncated after the Nth term, the width should be chosen to increase with N as
. We derive similar asymptotics for the function f(x)=x as extended by a more sophisticated scheme with overlapping bells; this gives an even faster rate of Fourier convergence 相似文献
17.
Given a nonempty set of functions
18.
19.
D. Gangopadhyay 《Gravitation and Cosmology》2010,16(3):231-238
A lagrangian for a k-essence field is constructed for a constant scalar potential, and its form is determined when the scale factor is very small
as compared to the present epoch but very large as compared to the inflationary epoch. This means that one is already in an
expanding and flat universe. The form is similar to that of an oscillator with time-dependent frequency. Expansion is naturally
built into the theory with the existence of growing classical solutions of the scale factor. The formalism allows one to estimate
the temperature fluctuations of the background radiation at these early stages (as compared to the present epoch) of the Universe.
If the temperature is T
a
at time t
a
and T
b
at time t
b
(t
b
> t
a
), then, for small times, the probability evolution for the logarithm of the inverse temperature can be estimated as
|
设为首页 | 免责声明 | 关于勤云 | 加入收藏 |
Copyright©北京勤云科技发展有限公司 京ICP备09084417号 |