For linear system Ax = b, the traditional condition number is the worst case for all b¡¦s and often overestimated in many problems. For a specific b, the effective condition number is a better upper bound for the relative error of x. But, it is also possible that this effective condition number is overestimated. In this thesis, we study the true ratio of the relative error of x to the relative perturbation of b, called the true condition number. We obtain several new upper bounds and estimates for true condition number. We also explore to change the system to an equivalent one by shifting b to minimize its effective condition number. Finally we apply all our results to functional approximation.

This thesis consists of two parts. In the first part, to solve the boundary value problems of homogeneous equations, the fundamental solutions (FS) satisfying the homogeneous equations are chosen, and their linear combination is forced to satisfy the exterior and the interior boundary conditions. To avoid the logarithmic singularity, the source points of FS are located outside of the solution domain S. This method is called the method of fundamental solutions (MFS). The MFS was first used in Kupradze in 1963. Since then, there have appeared numerous reports of MFS for computation, but only a few for analysis. The part one of this thesis is to derive the eigenvalues for the Neumann and the Robin boundary conditions in the simple case, and to estimate the bounds of condition number for the mixed boundary conditions in some non-disk domains. The same exponential rates of Cond are obtained. And to report numerical results for two kinds of cases. (I) MFS for Motz's problem by adding singular functions. (II) MFS for Motz's problem by local refinements of collocation nodes. The values of traditional condition number are huge, and those of effective condition number are moderately large. However, the expansion coefficients obtained by MFS are scillatingly large, to cause another kind of instability: subtraction cancellation errors in the final harmonic solutions. Hence, for practical applications, the errors and the ill-conditioning must be balanced each other. To mitigate the ill-conditioning, it is suggested that the number of FS should not be large, and the distance between the source circle and the partial S should not be far, either. In the second part, to reduce the severe instability of MFS, the truncated singular value decomposition(TSVD) and Tikhonov regularization(TR) are employed. The computational formulas of the condition number and the effective condition number are derived, and their analysis is explored in detail. Besides, the error analysis of TSVD and TR is also made. Moreover, the combination of TSVD and TR is proposed and called the truncated Tikhonov regularization in this thesis, to better remove some effects of infinitesimal sigma_{min} and high frequency eigenvectors.

In this thesis, for the under-determined system Fx = b with the matrix F ∈m¡Ñn (m ≤ n), new error bounds involving the traditional condition number and the effective condition number are established. Such error bounds are simple than those of over-determined system. The errors results implies that for stability, the condition number and the effective condition numbers are important if the perturbation of matrix F and vector b are dominant, respectively. This thesis is also devoted to the application of Neumann problems, where the consistent condition holds to guarantee the existence of multiple solutions. For the traditional Neumann conditions, the discrete consistent condition has to be satisfied to guarantee the existence of numerical solutions. Such a discrete consistent condition can be removed, to greatly simplify the numerical algorithms, and to retain the same convergence rates. For Neumann Problems, we may solve its ordinal discrete linear equations, or the underdetermined systems by ignoring some dependent equations, or the fixed variables methods. Moreover, we may choose different equations to be ignored, and different variables to be fixed. The comparisons of these different methods and choices are important in applications. In this thesis, the new comparisons and relations of stability and accuracy are first explored, and some interesting results and new discoveries are found. Numerical examples of Neumann problem in 1D are carried out, to support the analysis made. However, the algorithms and stability analysis can be applied to the complicated Nuemann problems in 2D and 3D, such as the traction problems in linear elastic problems.

No description available.

The growing interest in computing structured matrix functions stems from the fact that preserving and exploiting the structure of matrices can help us gain physically meaningful solutions with less computational cost and memory requirement. The work presented here is divided into two parts. The first part deals with the computation of functions of structured matrices. The second part is concerned with the structured error analysis in the computation of matrix functions. We present algorithms applying the inverse scaling and squaring method and using the Schur-like form of the symplectic matrices as an alternative to the algorithms using the Schur decomposition to compute the logarithm of symplectic matrices. There are two main calculations in the inverse scaling and squaring method: taking a square root and evaluating the Padé approximants. Numerical experiments suggest that using the Schur-like form with the structure preserving iterations for the square root helps us to exploit the Hamiltonian structure of the logarithm of symplectic matrices. Some type of matrices are nearly structured. We discuss the conditions for using the nearest structured matrix to the nearly structured one by analysing the forward error bounds. Since the structure preserving algorithms for computing the functions of matrices provide advantages in terms of accuracy and data storage we suggest to compute the function of the nearest structured matrix. The analysis is applied to the nearly unitary, nearly Hermitian and nearly positive semi-definite matrices for the matrix logarithm, square root, exponential, cosine and sine functions. It is significant to investigate the effect of the structured perturbations in the sensitivity analysis of matrix functions. We study the structured condition number of matrix functions defined between smooth square matrix manifolds. We develop algorithms computing and estimating the structured condition number. We also present the lower and upper bounds on the structured condition number, which are cheaper to compute than the "exact" structured condition number. We observe that the lower bounds give a good estimation for the structured condition numbers. Comparing the structured and unstructured condition number reveals that they can differ by several orders of magnitude. Having discussed how to compute the structured condition number of matrix functions defined between smooth square matrix manifolds we apply the theory of structured condition numbers to the structured matrix factorizations. We measure the sensitivity of matrix factors to the structured perturbations for the structured polar decomposition, structured sign factorization and the generalized polar decomposition. Finally, we consider the unstructured perturbation analysis for the canonical generalized polar decomposition by using three different methods. Apart from theoretical aspect of the perturbation analysis, perturbation bounds obtained from these methods are compared numerically and our findings show an improvement on the sharpness of the perturbation bounds in the literature.

給定一個設計矩陣X,當從X刪去一列或數列以後,X的特徵結構可能產生很 大的改變。在本文中,計算帽子矩陣H的高槓桿值,刪去如此有影響力的觀 察值後,X的特徵結構是否有改變,以及探討它的條件數。舉一些特殊的定 理, 討論從X刪去一列或數列之後的條件數。因此,我們也探討近似的條件 數,考慮兩者之間有何關係。 我們計算設計矩陣X的條件數與設計矩陣X 刪去一列或數列後的條件數,及診斷刪去有影響力的列對共線性之影響。 舉二個實例,使用 Matlab軟體計算條件數,分析它們的共線性性質, 以及 討論隱藏共線性與創造共線性的強度何者為強。

In spectral analysis of high dimensional multivariate time series, it is crucial to obtain an estimate of the spectrum that is both numerically well conditioned and precise. The conventional approach is to construct a nonparametric estimator by smoothing locally over the periodogram matrices at neighboring Fourier frequencies. Despite being consistent and asymptotically unbiased, these estimators are often ill-conditioned. This is because a kernel smoothed periodogram is a weighted sum over the local neighborhood of periodogram matrices, which are each of rank one. When treating high dimensional time series, the result is a bad ratio between the smoothing span, which is the effective local sample size of the estimator, and dimension. In classification, clustering and discrimination, and in the analysis of non-stationary time series, this is a severe problem, because inverting an estimate of the spectrum is unavoidable in these contexts. Areas of application like neuropsychology, seismology and econometrics are affected by this theoretical problem. We propose a new class of nonparametric estimators that have the appealing properties of simultaneously having smaller L2-risk than the smoothed periodogram and being numerically more stable due to a smaller condition number. These estimators are obtained as convex combinations of the averaged periodogram and a shrinkage target. The choice of shrinkage target depends on the availability of prior knowledge on the cross dimensional structure of the data. In the absence of any information, we show that a multiple of the identity matrix is the best choice. By shrinking towards identity, we trade the asymptotic unbiasedness of the averaged periodogram for a smaller mean-squared error. Moreover, the eigenvalues of this shrinkage estimator are closer to the eigenvalues of the real spectrum, rendering it numerically more stable and thus more appropriate for use in classification. These results are derived under a rigorous general asymptotic framework that allows for the dimension p to grow with the length of the time series T. Under this framework, the averaged periodogram even ceases to be consistent and has asymptotically almost surely higher L2-risk than our shrinkage estimator. Moreover, we show that it is possible to incorporate background knowledge on the cross dimensional structure of the data in the shrinkage targets. We derive an exemplary instance of a custom-tailored shrinkage target in the form of a one factor model. This offers a new answer to problems of model choice: instead of relying on information criteria such as AIC or BIC for choosing the order of a model, the minimum order model can be used as a shrinkage target and combined with a non-parametric estimator of the spectrum, in our case the averaged periodogram. Comprehensive Monte Carlo studies we perform show the overwhelming gain in terms of L2-risk of our shrinkage estimators, even for very small sample size. We also give an overview of regularization techniques that have been designed for iid data, such as ridge regression or sparse pca, and show the interconnections between them.

The purpose of this paper is to extend, as much as possible, the modern theory of condition numbers for conic convex optimization: z* := minz ctx s.t. Ax - b Cy C Cx , to the more general non-conic format: z* := minx ctx (GPd) s.t. Ax-b E Cy X P, where P is any closed convex set, not necessarily a cone, which we call the groundset. Although any convex problem can be transformed to conic form, such transformations are neither unique nor natural given the natural description of many problems, thereby diminishing the relevance of data-based condition number theory. Herein we extend the modern theory of condition numbers to the problem format (GPd). As a byproduct, we are able to state and prove natural extensions of many theorems from the conic-based theory of condition numbers to this broader problem format.

abstract: Power flow calculation plays a significant role in power system studies and operation. To ensure the reliable prediction of system states during planning studies and in the operating environment, a reliable power flow algorithm is desired. However, the traditional power flow methods (such as the Gauss Seidel method and the Newton-Raphson method) are not guaranteed to obtain a converged solution when the system is heavily loaded. This thesis describes a novel non-iterative holomorphic embedding (HE) method to solve the power flow problem that eliminates the convergence issues and the uncertainty of the existence of the solution. It is guaranteed to find a converged solution if the solution exists, and will signal by an oscillation of the result if there is no solution exists. Furthermore, it does not require a guess of the initial voltage solution. By embedding the complex-valued parameter α into the voltage function, the power balance equations become holomorphic functions. Then the embedded voltage functions are expanded as a Maclaurin power series, V(α). The diagonal Padé approximant calculated from V(α) gives the maximal analytic continuation of V(α), and produces a reliable solution of voltages. The connection between mathematical theory and its application to power flow calculation is described in detail. With the existing bus-type-switching routine, the models of phase shifters and three-winding transformers are proposed to enable the HE algorithm to solve practical large-scale systems. Additionally, sparsity techniques are used to store the sparse bus admittance matrix. The modified HE algorithm is programmed in MATLAB. A study parameter β is introduced in the embedding formula βα + (1- β)α^2. By varying the value of β, numerical tests of different embedding formulae are conducted on the three-bus, IEEE 14-bus, 118-bus, 300-bus, and the ERCOT systems, and the numerical performance as a function of β is analyzed to determine the “best” embedding formula. The obtained power-flow solutions are validated using MATPOWER. / Dissertation/Thesis / Flow chart of the HE algorithm / Presentation for mater's thesis defense / Masters Thesis Electrical Engineering 2015

原著論文リスト[A1]: “The final publication is available at Springer via http://dx.doi.org/10.1007/s11075-012-9607-5.”. [A2]: “The final publication is available at Springer via http://dx.doi.org/10.1007/s10092-013-0085-5.”, [A3]: DOI“10.1016/j.camwa.2015.11.022” / 京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19859号 / 情博第610号 / 新制||情||106(附属図書館) / 32895 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 中村 佳正, 教授 矢ｹ崎 一幸, 教授 山下 信雄 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM