1-14hit |
Akira INOUE Masahide KASHIWAGI Shin'ichi OISHI Mitsunori MAKINO
In this paper, we are concerned with a problem of obtaining an approximate solution of a finite-dimensional nonlinear equation with guaranteed accuracy. Assuming that an approximate solution of a nonlinear equation is already calculated by a certain numerical method, we present computable conditions to validate whether there exists an exact solution in a neighborhood of this approximate solution or not. In order to check such conditions by computers, we present a method using rational arithmetic. In this method, both the effects of the truncation errors and the rounding errors of numerical computation are taken into consideration. Moreover, based on rational arithmetic we propose a new modified Newton interation to obtain an improved approximate solution with desired accuracy.
Masahide KASHIWAGI Shin'ichi OISHI Mitsunori MAKINO Kazuo HORIUCHI
In this letter, a constructive simplified Newton method is presented for calculating solutions of infinite dimensional nonlinear equations, which uses a projection scheme from an infinite dimensional space to finite dimensional subspaces. A convergence theorem of the method is shown based on Urabe's theorem.
Mitsunori MAKINO Shin'ichi OISHI
A homotopy method is proposed for numerically solving an infinite dimensional convex optimization problem (COP). In this method, in the first place, by introducing an auxiliary COP, which is easy to solve, the original COP is imbedded into a parametric COP. Then, the Kuhn-Tucker (K-T) equation is derived which is equivalent to the parametric COP. It is shown that this K-T equation belongs to a class of Approximation proper homotopy equations. Using this, a sequence of finite dimensional approximate equations are derived for the K-T equation. It is shown that under certain mild conditions these approximate equations can be always solved by finite dimensional homotopy method and numerical solutions for them can be identified. Moreover, using the Approximation properness of the K-T equation, it is shown that from such a sequence a subsequence can always be derived which is convergent to a solution of the K-T equation. In this paper, two types of auxiliary COP's are introduced and two types of K-T equations are considered, a fixed point homotopy type and a Newton homotopy type. Since applicability is slightly different, comparison of applicability is also discussed between them.
Mitsunori MAKINO Shin'ichi OISHI Kazuo HORIUCHI
A numerical method is proposed for identifying bifurcating solution of infinite dimensional nonlinear equations by making use of the infinite dimensional homotopy method. In this paper in the first place, in order to show the existence of bifurcating solutions for a certain class of the Fredholm operators, a mapping degree is defined which has the similar properties as in a finite dimensional space. Using this, under certain conditions a primary bifurcation point exists for a certain type of infinite dimensional nonlinear equations. Furthermore, in case of the Leray-Schauder operator, it is shown that a certain bifurcating solution of the Leray-Schauder operator equation can be identified by making use of the infinite dimensional homotopy method.
Mitsunori MAKINO Masahide KASHIWAGI Shin'ichi OISHI Kazuo HORIUCHI
An estimation method of region is presented, in which a solution path of the so-called Newton type homotopy equation in guaranteed to exist, it is applied to a certain class of uniquely solvable nonlinear equations. The region can be estimated a posteriori, and its upper bound also can be estimated a priori.
Mitsunori MAKINO Masahide KASHIWAGI Shin'ichi OISHI Kazuo HORIUCHI
A priori estimation is presented for a computational complexity of the homotopy method applying to a certain class of strongly monotone nonlinear equations. In the present papers, a condition is presented for a certain class of uniquely solvable equations, under which an upper bound of a computational complexity of the Newton type homotopy method can be a priori estimated. In this paper, a condition is considered in a case of linear homotopy equations including the Newton type homotopy equations. In the first place, the homotopy algorithm based on the simplified Newton method is introduced. Then by using Urabe type theorem, which gives a sufficient condition guaranteeing the convergence of the simplified Newton method, a condition is presented under which an upper bound of a computational complexity of the algorithm can be a priori estimated, when it is applied to a certain class of strongly monotone nonlinear equations. The presented condition is demonstrated by numerical experiments.
Mitsunori MAKINO Shin'ichi OISHI Masahide KASHIWAGI Kazuo HORIUCHI
A priori estimation is presented for a computational complexity of the homotopy method applying to a certain class of uniquely solvable nonlinear equations. In the first place, the reason is explained why a computational complexity of the homotopy method can not be a priori estimated in general. In this paper, the homotopy algorithm is considered in which a numerical path following algorithm is executed based on the simplified Newton method. Then by introducing Urabe's theorem, which gives a sufficient condition guaranteeing the convergence of the simplified Newton method, it is shown that a computational complexity of the algorithm can be a priori estimated, when it is applied to a certain class of uniquely solvable nonlinear equation. In this paper, two types of path following algorithms are considered, one with a numerical error estimation in the domain of a nonlinear operator and another with one in the range of the operator.
Mitsunori MAKINO Shin'ichi OISHI Masahide KASHIWAGI Kazuo HORIUCHI
In this paper, in the first place, a slightly version upped Urabe type theorem of convergence criterion is presented for the modified Newton method. Then, based on this theorem, a posteriori stopping criterion is presented for a class of numerical methods of calculating solutions including the simplicial approximate homotopy method for nonlinear equations. By this criterion it is estimated whether an approximate solution satisfies the conditions of the Urabe theorem or not. Finally, it is shown that under a certain mild condition a class of simplicial approximate homotopy methods such as Merrill's method generate an approximate solution which satisfies our stopping criterion in restarting finite steps.
In the field of computer graphics (CG), some adaptive methods have been proposed in order to make CG images more real in relatively low computational cost. As one of such adaptive methods, in this paper, an adaptive method will be proposed for detection of edges and approximation of surfaces in the use of the so-called automatic differentiation. In the proposed method a CG image with high quality can be generated in suitable computational cost. In this paper, three cases will be considered. The first is an adaptive distributed ray tracing which can adaptively generate anti-aliased CG images in suitable computational cost. The second is a high quality triangular meshing, which guarantees accuracy of the generated meshes according to shape of given surface in suitable computational cost. The last case is used in the so-called radiosity method.
In this paper a priori estimation method is presented for calculating solution of convex optimization problems (COP) with some equality and/or inequality constraints by so-called Newton type homotopy method. The homotopy method is known as an efficient algorithm which can always calculate solution of nonlinear equations under a certain mild condition. Although, in general, it is difficult to estimate a priori computational complexity of calculating solution by the homotopy method. In the presented papers, a sufficient condition is considered for linear homotopy, under which an upper bound of the complexity can be estimated a priori. For the condition it is seen that Urabe type convergence theorem plays an important role. In this paper, by introducing the results, it is shown that under a certain condition a global minimum of COP can be always calculated, and that computational complexity of the calculation can be a priori estimated. Suitability of the estimation for analysing COP is also discussed.
Masahide KASHIWAGI Mitsunori MAKINO Toshimichi SAITO
Mitsunori MAKINO Shin'ichi OISHI Masahide KASHIWAGI Kazuo HORIUCHI
A type of infinite dimensional homotopy method is considered for numerically calculating a solution curve of a nonlinear functional equation being a Fredholm operator with index 1 and an A-proper operator. In this method, a property of so-called A-proper homotopy plays an important role.
Related with accuracy, computational complexity and so on, quality of computing for the so-called homotopy method has been discussed recently. In this paper, we shall propose an estimation method with interval analysis of region in which unique solution path of the homotopy equation is guaranteed to exist, when it is applied to a certain class of uniquely solvable nonlinear equations. By the estimation, we can estimate the region a posteriori, and estimate a priori an upper bound of the region.