求矩阵A^＋的初等变换法

求矩阵Ａ~＋的初等变换法赵昌成（湖北郧阳师专４４１９００）设Ａ是复ｍ×ｎ矩阵，如果ｎ×ｍ矩阵Ｘ满足（１）ＡＸＡ＝Ａ（２）ＸＡＸ＝Ｘ；（３）（ＡＸ）＝ＡＸ；（４）（ＸＡ）＝ＸＡ．则称Ｘ为Ａ的Ｍｏｒｅ－Ｐｅｎｒｏｓｅ广义逆（号表示对矩阵取共轭转置运算）．...     

非退化扩散过程的极性的必要性

设Ｘ（ｔ）是一Ｎ维非退化扩散过程．设 Ｅ（０，∞）和 Ｆ ＲＮ都为紧集．本文给出了：Ｐ（Ｘ－１（Ｆ）∩Ｅ≠φ）＞０，Ｐ（Ｘ－１（Ｆ）≠φ）＞０和Ｐ（Ｘ（Ｅ）≠φ）＞０的充分条件．证明了：ｉ）设 Ｎ≥ ３，ａ）若 ｄｉｍ（Ｆ）＜Ｎ－２，则 Ｐ（Ｘ－１（Ｆ）＝φ）＝１； ｂ）若ｄｉｍ（Ｆ）＞Ｎ－２，则 Ｐ（Ｘ－１（Ｆ）≠φ）＞０； ｃ）存在 Ｆ１ ＲＮ，Ｆ２ ＲＮ，ｄｉｍ（Ｆ１）＝ｄｉｍ（Ｆ２）＝Ｎ－２，但有Ｐ（Ｘ－１（Ｆ１）＝φ）＝１，Ｐ（Ｘ－１（Ｆ２）≠φ）＞０．ｉｉ）设Ｎ＝１，ａ）若ｄｉｍ（Ｅ）＞１／２，则ｘ∈Ｒ１，Ｐ（Ｘ－１（ｘ）∩Ｅ≠φ）＞０；ｂ）存在Ｅ（０，∞），ｄｉｍ（Ｅ）＝１／２，使得ｘ∈Ｒ１，Ｐ（Ｘ－１（ｘ）∩Ｅ≠φ）＞０．以上这些结果，不仅仅是Ｂｒｏｗｎ运动的推广，即使就Ｂｒｏｗｎ运动的情形而言，其中有些结果也是新的．     

任意体上的矩阵方程［X_（nn）A_（ns），X_（nn）B_（nt）］＝［A_

本文研究了任意体上的矩阵方程［Ｘ（ｎｎ）Ａ（ｎｓ），Ｘ（ｎｎ）Ｂ（ｎｔ）］＝［Ａ（ｎｓ），０］（１）给出了（１）相容的充要条件、通解的表达式、解的性质及其实用解法．     

奇异M─矩阵的图相容弱正则分裂

设Ａ是奇异Ｍ－矩阵，Ａ＝Ｍ－Ｎ是Ａ的图相容弱正则分裂．本文研究迭代矩阵Ｍ－１Ｎ的谱性质，得到与迭代矩阵的指数有关的一个定理：ｉｎｄ０（Ａ）＝ｉｎｄ１（Ｍ－１Ｎ）．它推广了Ｈ．Ｓｃｈｎｅｉｄｅｒ和作者的结果．     

矩阵方程AX + XB=0求解初探

一、矩阵方程ＡＸ＋ＸＢ＝０解的判定命题＝设Ａ、Ｂ均为ｎ阶方阵,则矩阵方程ＡＸ＋ＸＢ＝０（＊）与矩阵方程Ｑ·Ｙ＝０等价;其中ＹＴ＝（ｘ１１,ｘ１２,…,ｘ１ｎ,ｘ２１,…,ｘ２ｎ,,ｘｎ１,ｘｎｎ）证明设Ａ＝（ａｉｊ）,Ｂ＝（ｂｉｊ）,Ｘ＝（ｘｉｊ）均为ｎ阶方务,则（＊）式等价于由矩阵相等关系知（＊＊）等价于下列ｎ组线性方程组现在就第（１’）式进行讨论,将（１’）展开为用矩阵表示为（ａ１１Ｅ＋ＢＴａ１２Ｅａ１３Ｅ…ａ１ｎＥ）Ｙ＝０（１’）其中ＹＴ＝（ｘ１１ｘ１２…ｘ１ｎ,ｘ２１…ｘ２ｎ…ｘｎ１…ｘ…     

自反算子代数的环自同构

设Ａ是Ｂａｎａｃｈ空间Ｘ上的自反算子代数，并且Ａ的不变子空间格ＬａｔＡ满足 ０＋≠０和Ｘ_≠Ｘ，ａ：Ａ→Ａ是环自同构．如果Ｘ是实空间，并且ｄｉｍ　Ｘ　＞１；则存在Ｘ上的线性有界可逆算子Ａ，使得ａ（Ｔ）＝ＡＴＡ～（－１）；Ｔ∈Ａ：如果Ｘ是复空间，并且ｄｉｍ Ｘ　＝∞，则ａ（Ｔ）＝ＡＴＡ～（－１），Ｔ∈Ａ．其中Ａ：Ｘ→Ｘ是线性、或者共轭线性有界可逆算子．     

一类矩阵方程的简便解法

一类矩阵方程的简便解法胡安民（连云港职业大学）对于系数矩阵可逆的矩阵方程ＡＸ＝Ｂ，ＸＡ＝Ｂ及ＡＸＢ＝Ｃ，一般线性代数教材中讲述求解方法时通常分两步进行：首先求系数矩阵Ａ的逆阵Ａ－１，再用Ａ－１与Ｂ相采得解（对于解ＡＸＢ＝Ｃ则需先求出Ａ－１，Ｂ－１，再...     

按环路α-连对角占优阵及应用

１．引言与记号 利用矩阵的对角占优性研究矩阵的特征值分布和非奇Ｈ矩阵的判定,是数值代数的重要课题．［１］－［４］给出了利用 Ｏｓｔｒｏｗｓｋｉ定理及连对角占优性判定非奇 Ｈ－矩阵的最新成果．本文引入按环路α－连对角占优概念,给出了非奇Ｈ－矩阵的判定条件及等价表征,简化了计算,改进与推广了［１］－［９］的相应结果． 设Ａ＝．Γ（Ａ）表 Ａ的方向图,其顶点集及弧集分别记作 Ｖ（Ａ）及 Ｅ（Ａ）,ｅｉｊ表从顶点ｉ到顶点 ｊ的弧, Ｃ（Ａ）表 Γ（Ａ）中非平凡环路集合．对任意固定 α Ｅ［０,１］还记＊ｋ伪行、列足…     

奇异M—矩阵的图相容弱正则分裂

设Ａ是奇异Ｍ－矩阵，Ａ＝Ｍ－Ｎ是Ａ的图相容弱正则分裂。本文研究迭代矩阵Ｍ＾－１Ｎ的谱性质，得到与迭代矩阵的指数有关的一个定理：ｉｎｄ０（Ａ）＝ｉｎｄ１（Ｍ＾－１Ｎ）．它推广了Ｈ．Ｓｃｈｎｅｉｄｅｒ和作者的结果。     

矩阵损失下均值向量的线性可容许估计

设Ｙ＝（Ｙ１，…，Ｙｎ）′相互独立，ＥＹ＝Ｘβ，ＣｏｖＹ＝Ｘｄｉａｇ（β１，…，βｎ）Ｘ′，β＝（β１，…，βｎ）′∈Ｒ＋ｎ为参数，Ｒ＋＝（０，＋∞），Ｘ为已知的元素非负且对角线元素为正的ｎ阶满秩矩阵，估计均值Ｘβ，选取损失函数为矩阵损失，估计类为Ｄ＝｛ＡＹ：Ａ为元素非负的ｎ阶矩阵｝．本文研究ＡＹ在Ｄ中的容许性，获得了ＡＹ在Ｄ中是Ｘβ的容许估计的充要条件．     

Some fundamental issues of basic line search algorithm for linear programming problems

In this article we present the fundamental idea, concepts and theorems of a basic line search algorithm for solving linear programming problems which can be regarded as an extension of the simplex method. However, unlike the iteration of the simplex method from a basic point to an improved adjacent basic point via pivot operation, the basic line search algorithm, also by pivot operation, moves from a basic line which contains two basic feasible points to an improved basic line which also contains two basic feasible points whose objective values are no worse than that of the two basic feasible points on the previous basic line. The basic line search algorithm may skip some adjacent vertices so that it converges to an optimal solution faster than the simplex method. For example, for a 2-dimensional problem, the basic line search algorithm can find an optimal solution with only one iteration.     

线性规划的最钝角松弛算法

本文提出一个基于最钝角原理的松弛算法求解线性规划问题。该算法依据最钝角原理略去部分约束得到一个规模较小的子问题,用原始单纯形算法解之;再添加所略去的约束恢复原问题,若此时全部约束条件均满足则已获得一个基本最优解,否则用对偶单纯形算法继续求解。初步的数值试验表明,新算法比传统两阶段单纯形算法快得多。     

New efficient shortest path simplex algorithm: pseudo permanent labels instead of permanent labels

We introduce a new network simplex pivot rule for the shortest path simplex algorithm. This new pivot rule chooses a subset of non-basic arcs to simultaneously enter into the basis. We call this operation a multiple pivot. We show that a shortest path simplex algorithm with this pivot rule performs O(n) multiple pivots and runs in O(nm) time. Our pivot rule is based on the new concept of a pseudo permanently labeled node, and it can be adapted to design a new label-correcting algorithm that runs in O(nm). Moreover, this concept lets us introduce new rules to identify negative cycles. Finally, we compare the network simplex algorithm with multiple pivots with other previously proposed efficient network simplex algorithm in a computational experiment.     

Parallel search paths for the simplex algorithm

It is well known that the simplex method is inherently a sequential algorithm with little scope for parallelization. Even so, during the last decades several attempts were made to parallelize it since it is one of the most important algorithms for solving linear optimization problems. Such parallelization ideas mostly rely on iteration parallelism and overlapping. Since the simplex method goes through a series of basic solutions until it finds an optimal solution, each of them must be available before performing the next basis change. This phenomenon imposes a limit on the performance of the parallelized version of the simplex method which uses overlapping iterations. Another approach can be considered if we think about alternative paths on the n-dimensional simplex polyhedron. As the simplex method goes through the edges of this polyhedron it is generally true that the speed of convergence of the algorithm is not smooth. It depends on the actual part of the surface. If a parallel version of the simplex algorithm simultaneously goes on different paths on this surface a highly reliable algorithm can be constructed. There is no known dominating strategy for pivot selection. Therefore, one can try different pivot selection methods in parallel in order to guide the algorithm on different pathways. This approach can be used effectively with periodic synchronization on shared memory multi-core computing environments to speed up the solution algorithm and get around numerically and/or algorithmically difficult situations throughout the computations.     

线性规划的对偶基线算法

In this paper,we studied the dual form of the basic line algorthm for linear programs.It can be easily implemented in tableau that similar to the primal/dual simplex method.Different from primal simplex method or dual simplex method,the dual basic line algorithm can keep primal feasibility and dual feasibility at the same time in a tableau,which makes it more efficient than the former ones.Principles and convergence of dual basic line algorthm were discussed.Some examplex and computational experience were given to illustrate the efficiency of our method.     

Criss-cross methods: A fresh view on pivot algorithms

Criss-cross methods are pivot algorithms that solve linear programming problems in one phase starting with any basic solution. The first finite criss-cross method was invented by Chang, Terlaky and Wang independently. Unlike the simplex method that follows a monotonic edge path on the feasible region, the trace of a criss-cross method is neither monotonic (with respect to the objective function) nor feasibility preserving. The main purpose of this paper is to present mathematical ideas and proof techniques behind finite criss-cross pivot methods. A recent result on the existence of a short admissible pivot path to an optimal basis is given, indicating shortest pivot paths from any basis might be indeed short for criss-cross type algorithms. The origins and the history of criss-cross methods are also touched upon.     

A Simplex-Type Algorithm for General Transportation Problems: An Alternative to Stepping-Stone

This paper re-examines use of the linear programming (LP) formulation to solve the transportation problem (TP). The proposed method is a general-purpose algorithm which uses only one operation, the Gauss Jordan pivoting used in the simplex method. The final tableau can be used for post-optimality analysis of TP. This algorithm appears to be faster than simplex, more general than stepping-stone and simpler than both in solving general TP. A numerical example illustrates the methodology. It is assumed the reader is familiar with simplex terminology.     

The double pivot simplex method

The simplex method, created by George Dantzig, optimally solves a linear program by pivoting. Dantzig’s pivots move from a basic feasible solution to a different basic feasible solution by exchanging exactly one basic variable with a nonbasic variable. This paper introduces the double pivot simplex method, which can transition between basic feasible solutions using two variables instead of one. Double pivots are performed by identifying the optimal basis in a two variable linear program using a new method called the slope algorithm. The slope algorithm is fast and allows an iteration of DPSM to have the same theoretical running time as an iteration of the simplex method. Computational experiments demonstrate that DPSM decreases the average number of pivots by approximately 41% on a small set of benchmark instances.     

A practical anti-degeneracy row selection technique in network linear programming

A characteristic feature of the primal network simplex algorithm (NSA) is that it usually makes a large number of degenerate iterations. Though cycling and even stalling can be avoided by recently introduced pivot rules for NSA, the practical efficiency of these rules is not known yet. For the case when the simplex algorithm is used to solve the continuous linear programming (LP) problem there exists a practical anti-cycling procedure that proved to be efficient. It is based on an expanding relaxation of the individual bound on the variables. In this paper we discuss the adaptation of this method to NSA, taking advantage of the special integer nature of network problems. We also give an account of our experience with these ideas as they are experimentally implemented in the MINET network LP solver. Reductions of CPU time have been achieved on a smaller set of specially structured real-life problems.This research was supported in part by Hungarian Research Fund OTKA 2587, and by DAAD 314 108 060 0 while the author was at Universität Heidelberg, Germany, October, 1990.     

An Integral Simplex Algorithm for Solving Combinatorial Optimization Problems

In this paper a local integral simplex algorithm will be described which, starting with the initial tableau of a set partitioning problem, makes pivots using the pivot on one rule until no more such pivots are possible because a local optimum has been found. If the local optimum is also a global optimum the process stops. Otherwise, a global integral simplex algorithm creates and solves the problems in a search tree consisting of a polynomial number of subproblems, subproblems of subproblems, etc. The solution to at least one of these subproblems is guaranteed to be an optimal solution to the original problem. If that solution has a bounded objective then it is an optimal set partitioning solution of the original problem, but if it has an unbounded objective then the original problem has no feasible solution. It will be shown that the total number of pivots required for the global integral simplex method to solve a set partitioning problem having m rows, where m is an arbitrary but fixed positive integer, is bounded by a polynomial function of n.A method for programming the algorithms in this paper to run on parallel computers is discussed briefly.