共查询到20条相似文献,搜索用时 62 毫秒
1.
We extend the applicability of the Gauss–Newton method for solving singular systems of equations under the notions of average
Lipschitz–type conditions introduced recently in Li et al. (J Complex 26(3):268–295, 2010). Using our idea of recurrent functions, we provide a tighter local as well as semilocal convergence analysis for the Gauss–Newton
method than in Li et al. (J Complex 26(3):268–295, 2010) who recently extended and improved earlier results (Hu et al. J Comput Appl Math 219:110–122, 2008; Li et al. Comput Math Appl 47:1057–1067, 2004; Wang Math Comput 68(255):169–186, 1999). We also note that our results are obtained under weaker or the same hypotheses as in Li et al. (J Complex 26(3):268–295,
2010). Applications to some special cases of Kantorovich–type conditions are also provided in this study. 相似文献
2.
Alicia Cordero José L. Hueso Eulalia Martínez Juan R. Torregrosa 《Numerical Algorithms》2010,53(4):485-495
In this paper, we present two new three-step iterative methods for solving nonlinear equations with sixth convergence order.
The new methods are obtained by composing known methods of third order of convergence with Newton’s method and using an adequate
approximation for the derivative, that provides high order of convergence and reduces the required number of functional evaluations
per step. The first method is obtained from Potra-Pták’s method and the second one, from Homeier’s method, both reaching an
efficiency index of 1.5651. Our methods are comparable with the method of Parhi and Gupta (Appl Math Comput 203:50–55, 2008). Methods proposed by Kou and Li (Appl Math Comput 189:1816–1821, 2007), Wang et al. (Appl Math Comput 204:14–19, 2008) and Chun (Appl Math Comput 190:1432–1437, 2007) reach the same efficiency index, although they start from a fourth order method while we use third order methods and simpler
arithmetics. We prove the convergence results and check them with several numerical tests that allow us to compare the convergence
order, the computational cost and the efficiency order of our methods with those of the original methods. 相似文献
3.
P. Wojtaszczyk 《Foundations of Computational Mathematics》2010,10(1):1-13
In compressed sensing, we seek to gain information about a vector x∈ℝ
N
from d
≪
N nonadaptive linear measurements. Candes, Donoho, Tao et al. (see, e.g., Candes, Proc. Intl. Congress Math., Madrid, 2006; Candes et al., Commun. Pure Appl. Math. 59:1207–1223, 2006; Donoho, IEEE Trans. Inf. Theory 52:1289–1306, 2006) proposed to seek a good approximation to x via ℓ
1 minimization. In this paper, we show that in the case of Gaussian measurements, ℓ
1 minimization recovers the signal well from inaccurate measurements, thus improving the result from Candes et al. (Commun.
Pure Appl. Math. 59:1207–1223, 2006). We also show that this numerically friendly algorithm (see Candes et al., Commun. Pure Appl. Math. 59:1207–1223, 2006) with overwhelming probability recovers the signal with accuracy, comparable to the accuracy of the best k-term approximation in the Euclidean norm when k∼d/ln N. 相似文献
4.
John A. Ford Yasushi Narushima Hiroshi Yabe 《Computational Optimization and Applications》2008,40(2):191-216
Conjugate gradient methods are appealing for large scale nonlinear optimization problems, because they avoid the storage of
matrices. Recently, seeking fast convergence of these methods, Dai and Liao (Appl. Math. Optim. 43:87–101, 2001) proposed a conjugate gradient method based on the secant condition of quasi-Newton methods, and later Yabe and Takano (Comput.
Optim. Appl. 28:203–225, 2004) proposed another conjugate gradient method based on the modified secant condition. In this paper, we make use of a multi-step
secant condition given by Ford and Moghrabi (Optim. Methods Softw. 2:357–370, 1993; J. Comput. Appl. Math. 50:305–323, 1994) and propose two new conjugate gradient methods based on this condition. The methods are shown to be globally convergent
under certain assumptions. Numerical results are reported. 相似文献
5.
Recently, Li et al. (Comput. Optim. Appl. 26:131–147, 2004) proposed a regularized Newton method for convex minimization problems. The method retains local quadratic convergence property
without requirement of the singularity of the Hessian. In this paper, we develop a truncated regularized Newton method and
show its global convergence. We also establish a local quadratic convergence theorem for the truncated method under the same
conditions as those in Li et al. (Comput. Optim. Appl. 26:131–147, 2004). At last, we test the proposed method through numerical experiments and compare its performance with the regularized Newton
method. The results show that the truncated method outperforms the regularized Newton method.
The work was supported by the 973 project granted 2004CB719402 and the NSF project of China granted 10471036. 相似文献
6.
We introduce a new iterative method in order to approximate a locally unique solution of variational inclusions in Banach
spaces. The method uses only divided differences operators of order one. An existence–convergence theorem and a radius of
convergence are given under some conditions on divided difference operator and Lipschitz-like continuity property of set-valued
mappings. Our method extends the recent work related to the resolution of nonlinear equation in Argyros (J Math Anal Appl
332:97–108, 2007) and has the following advantages: faster convergence to the solution than all the previous known ones in Argyros and Hilout
(Appl Math Comput, 2008 in press), Hilout (J Math Anal Appl 339:53–761, 2008, Positivity 10:673–700, 2006), and we do not need to evaluate any Fréchet derivative. We provide also an improvement of the ratio of our algorithm under
some center-conditions and less computational cost. Numerical examples are also provided.
相似文献
7.
A derivative free iterative method for approximating a solution of nonlinear least squares problems is studied first in Shakhno
and Gnatyshyn (Appl Math Comput 161:253–264, 2005). The radius of convergence is determined as well as usable error estimates. We show that this method is faster than its
Secant analogue examined in Shakhno and Gnatyshyn (Appl Math Comput 161:253–264, 2005). Numerical example is also provided in this paper. 相似文献
8.
Complex B-splines as introduced in Forster et al. (Appl. Comput. Harmon. Anal. 20:281–282, 2006) are an extension of Schoenberg’s cardinal splines to include complex orders. We exhibit relationships between these complex
B-splines and the complex analogues of the classical difference and divided difference operators and prove a generalization
of the Hermite–Genocchi formula. This generalized Hermite–Genocchi formula then gives rise to a more general class of complex
B-splines that allows for some interesting stochastic interpretations.
相似文献
9.
We introduce the new idea of recurrent functions to provide a new semilocal convergence analysis for Newton-type methods,
under mild differentiability conditions. It turns out that our sufficient convergence conditions are weaker, and the error
bounds are tighter than in earlier studies in some interesting cases (Chen, Ann Inst Stat Math 42:387–401, 1990; Chen, Numer Funct Anal Optim 10:37–48, 1989; Cianciaruso, Numer Funct Anal Optim 24:713–723, 2003; Cianciaruso, Nonlinear Funct Anal Appl 2009; Dennis 1971; Deuflhard 2004; Deuflhard, SIAM J Numer Anal 16:1–10, 1979; Gutiérrez, J Comput Appl Math 79:131–145, 1997; Hernández, J Optim Theory Appl 109:631–648, 2001; Hernández, J Comput Appl Math 115:245–254, 2000; Huang, J Comput Appl Math 47:211–217, 1993; Kantorovich 1982; Miel, Numer Math 33:391–396, 1979; Miel, Math Comput 34:185–202, 1980; Moret, Computing 33:65–73, 1984; Potra, Libertas Mathematica 5:71–84, 1985; Rheinboldt, SIAM J Numer Anal 5:42–63, 1968; Yamamoto, Numer Math 51: 545–557, 1987; Zabrejko, Numer Funct Anal Optim 9:671–684, 1987; Zinc̆ko 1963). Applications and numerical examples, involving a nonlinear integral equation of Chandrasekhar-type, and a differential
equation are also provided in this study. 相似文献
10.
In this paper we provide a Heine–Borel type characterization for 0-compactness in approach spaces (Lowen 1997). Since this requires making use of the so-called regular function frame the most natural setting to develop this in is approach
frames (Banaschewski 1999; Banaschewski et al., Acta Math Hung 115(3):183–196, 2007, Topology Appl 153:3059–3070, 2006). We then go on to characterize Hausdorffness for approach frames which allows us to study some fundamental properties of
compact Hausdorff approach frames. 相似文献
11.
P. M. Kleniati P. Parpas B. Rustem 《Journal of Optimization Theory and Applications》2010,145(2):289-310
We consider polynomial optimization problems pervaded by a sparsity pattern. It has been shown in Lasserre (SIAM J. Optim.
17(3):822–843, 2006) and Waki et al. (SIAM J. Optim. 17(1):218–248, 2006) that the optimal solution of a polynomial programming problem with structured sparsity can be computed by solving a series
of semidefinite relaxations that possess the same kind of sparsity. We aim at solving the former relaxations with a decomposition-based
method, which partitions the relaxations according to their sparsity pattern. The decomposition-based method that we propose
is an extension to semidefinite programming of the Benders decomposition for linear programs (Benders, Comput. Manag. Sci.
2(1):3–19, 2005). 相似文献
12.
In Han and Shen (SIAM J. Math. Anal. 38:530–556, 2006), a family of univariate short support Riesz wavelets was constructed from uniform B-splines. A bivariate spline Riesz wavelet
basis from the Loop scheme was derived in Han and Shen (J. Fourier Anal. Appl. 11:615–637, 2005). Motivated by these two papers, we develop in this article a general theory and a construction method to derive small support
Riesz wavelets in low dimensions from refinable functions. In particular, we obtain small support spline Riesz wavelets from
bivariate and trivariate box splines. Small support Riesz wavelets are desirable for developing efficient algorithms in various
applications. For example, the short support Riesz wavelets from Han and Shen (SIAM J. Math. Anal. 38:530–556, 2006) were used in a surface fitting algorithm of Johnson et al. (J. Approx. Theory 159:197–223, 2009), and the Riesz wavelet basis from the Loop scheme was used in a very efficient geometric mesh compression algorithm in Khodakovsky
et al. (Proceedings of SIGGRAPH, 2000). 相似文献
13.
The existence and construction of symplectic 2s-stage variable coefficients Runge-Kutta (RK) methods that integrate exactly IVPs whose solution is a trigonometrical polynomial
of order s with a given frequency ω is considered. The resulting methods, that can be considered as trigonometrical collocation methods, are fully implicit,
symmetric and symplectic RK methods with variable nodes and coefficients that are even functions of ν=ω
h (h is the step size), and for ω→0 they tend to the conventional RK Gauss methods. The present analysis extends previous results on two-stage symplectic exponentially
fitted integrators of Van de Vyver (Comput. Phys. Commun. 174: 255–262, 2006) and Calvo et al. (J. Comput. Appl. Math. 218: 421–434, 2008) to symmetric and symplectic trigonometrically fitted methods of high order. The algebraic order of the trigonometrically
fitted symmetric and symplectic 2s-stage methods is shown to be 4s like in conventional RK Gauss methods. Finally, some numerical experiments with oscillatory Hamiltonian systems are presented. 相似文献
14.
This paper is devoted to the convergence and stability analysis of a class of nonlinear subdivision schemes and associated
multiresolution transforms. As soon as a nonlinear scheme can be written as a specific perturbation of a linear and convergent
subdivision scheme, we show that if some contractivity properties are satisfied, then stability and convergence can be achieved.
This approach is applied to various schemes, which give different new results. More precisely, we study uncentered Lagrange
interpolatory linear schemes, WENO scheme (Liu et al., J Comput Phys 115:200–212, 1994), PPH and Power-P schemes (Amat and Liandrat, Appl Comput Harmon Anal 18(2):198–206, 2005; Serna and Marquina, J Comput Phys 194:632–658, 2004) and a nonlinear scheme using local spherical coordinates (Aspert et al., Comput Aided Geom Des 20:165–187, 2003). Finally, a stability proof is given for the multiresolution transform associated to a nonlinear scheme of Marinov et al.
(2005). 相似文献
15.
Most standard textbooks about asymptotic approximations of integrals do not give explicit formulas for the coefficients of
the asymptotic methods of Laplace and saddle point. In these techniques, those coefficients arise as the Taylor coefficients
of a function defined in an implicit form, and the coefficients are not given by a closed algebraic formula. Despite this
fact, we can extract from the literature some formulas of varying degrees of explicitness for those coefficients: Perron’s
method (in Sitzungsber. Bayr. Akad. Wissensch. (Münch. Ber.), 191–219, 1917) offers an explicit computation in terms of the derivatives of an explicit function; in (de Bruijn, Asymptotic Methods in
Analysis. Dover, New York, 1950) we can find a similar formula for the Laplace method which uses derivatives of an explicit function. Dingle (in Asymptotic
Expansions: Their Derivation and Interpretation, Academic Press, New York, 1973) gives the coefficients of the saddle point method in terms of a contour integral. Perron’s method is rediscovered in (Campbell
et al., Stud. Appl. Math. 77:151–172, 1987), but they also go farther and compute the above mentioned derivatives by means of a recurrence. The most recent contribution
is (Wojdylo, SIAM Rev. 48(1):76–96, 2006), which rediscovers the Campbell, Fr?man and Walles’ formula and rewrites it in terms of Bell polynomials (in the Laplace
method) using new ideas of combinatorial analysis which efficiently simplify and systematize the computations. In this paper
we continue the research line of these authors. We combine the more systematic version of the saddle point method introduced
in (López et al., J. Math. Anal. Appl. 354(1):347–359, 2009) with Wojdylo’s idea to derive a new and more explicit formula for the coefficients of the saddle point method, similar to
Wojdylo’s formula for the coefficients of the Laplace method. As an example, we show the application of this formula to the
Bessel function. 相似文献
16.
For finding a root of an equation f(x) = 0 on an interval (a, b), we develop an iterative method using the signum function and the trapezoidal rule for numerical integrations based on the
recent work (Yun, Appl Math Comput 198:691–699, 2008). This method, so-called signum iteration method, depends only on the signum function sgn(f(x)){\rm{sgn}}\left(f(x)\right) independently of the behavior of f(x), and the error bound of the kth approximation is (b − a)/(2N
k
), where N is the number of integration points for the trapezoidal rule in each iteration. In addition we suggest hybrid methods which
combine the signum iteration method with usual methods such as Newton, Ostrowski and secant methods. In particular the hybrid
method combined with the signum iteration and the secant method is a predictor-corrector type method (Noor and Ahmad, Appl
Math Comput 180:167–172, 2006). The proposed methods result in the rapidly convergent approximations, without worry about choosing a proper initial guess.
By some numerical examples we show the superiority of the presented methods over the existing iterative methods. 相似文献
17.
In this paper we investigate POD discretizations of abstract linear–quadratic optimal control problems with control constraints.
We apply the discrete technique developed by Hinze (Comput. Optim. Appl. 30:45–61, 2005) and prove error estimates for the corresponding discrete controls, where we combine error estimates for the state and the
adjoint system from Kunisch and Volkwein (Numer. Math. 90:117–148, 2001; SIAM J. Numer. Anal. 40:492–515, 2002). Finally, we present numerical examples that illustrate the theoretical results. 相似文献
18.
We continue the discussion of error estimates for the numerical analysis of Neumann boundary control problems we started in
Casas et al. (Comput. Optim. Appl. 31:193–219, 2005). In that paper piecewise constant functions were used to approximate the control and a convergence of order O(h) was obtained. Here, we use continuous piecewise linear functions to discretize the control and obtain the rates of convergence
in L
2(Γ). Error estimates in the uniform norm are also obtained. We also discuss the approach suggested by Hinze (Comput. Optim.
Appl. 30:45–61, 2005) as well as the improvement of the error estimates by making an extra assumption over the set of points corresponding to
the active control constraints. Finally, numerical evidence of our estimates is provided.
The authors were supported by Ministerio de Ciencia y Tecnología (Spain). 相似文献
19.
A refinable spline in ℝ
d
is a compactly supported refinable function whose support can be decomposed into simplices such that the function is a polynomial
on each simplex. The best-known refinable splines in ℝ
d
are the box splines. Refinable splines play a key role in many applications, such as numerical computation, approximation
theory and computer-aided geometric design. Such functions have been classified in one dimension in Dai et al. (Appl. Comput.
Harmon. Anal. 22(3), 374–381, 2007), Lawton et al. (Comput. Math. 3, 137–145, 1995). In higher dimensions Sun (J. Approx. Theory 86, 240–252, 1996) characterized those splines when the dilation matrices are of the form A=mI, where m∈ℤ and I is the identity matrix. For more general dilation matrices the problem becomes more complex. In this paper we give a complete
classification of refinable splines in ℝ
d
for arbitrary dilation matrices A∈M
d
(ℤ). 相似文献
20.
Endre Boros Khaled Elbassioni Vladimir Gurvich Hans Raj Tiwary 《Annals of Operations Research》2011,188(1):63-76
Given a graph G=(V,E) and a weight function on the edges w:E→ℝ, we consider the polyhedron P(G,w) of negative-weight flows on G, and get a complete characterization of the vertices and extreme directions of P(G,w). Based on this characterization, and using a construction developed in Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190,
2008), we show that, unless P=NP, there is no output polynomial-time algorithm to generate all the vertices of a 0/1-polyhedron. This strengthens the NP-hardness
result of Khachiyan et al. (Discrete Comput. Geom. 39(1–3):174–190, 2008) for non 0/1-polyhedra, and comes in contrast with the polynomiality of vertex enumeration for 0/1-polytopes (Bussiech and
Lübbecke in Comput. Geom., Theory Appl. 11(2):103–109, 1998). As further applications, we show that it is NP-hard to check if a given integral polyhedron is 0/1, or if a given polyhedron
is half-integral. Finally, we also show that it is NP-hard to approximate the maximum support of a vertex of a polyhedron
in ℝ
n
within a factor of 12/n. 相似文献