求解线性方程组的LA = U分解法
作者：Ababu T. Tiruneh; Tesfamariam Y. Debessai; Gabriel C. Bwembya; Stanley J. Nkambule
国籍：斯威士兰王国
出处：Journal of Applied Mathematics and Physics, 2019, 7, 2031-2051
中文译文：
摘要：利用形式对系数矩阵进行直接分解，给出了求解线性方程组的一种方法。降阶下三角矩阵的元素可以用行或列运算确定，并证明是高斯主元乘子的排列积之和。这些排列积之和可以用易于记忆的树结构来构造，也可以用矩阵乘积来替代计算。与分解中元素的存储相比，该方法只需要存储一半大小的矩阵。本文还证明了该方法与Gauss消去法和LU分解法的等价性。
关键词：线性方程组，Gauss消去法，分解法，线性方程，逆矩阵，决定因子
- 引言
线性方程组或方程组线性化迭代求解在许多科学和工程问题中出现[ 1 ]，线性方程组的实际应用很多，例如在数字信号处理、线性规划问题、非线性问题的数值分析和最小二乘曲线拟合等方面的应用[ 2 ]，历史上也曾报道为数字电脑的发展提方程组的求解方法供了动力[ 3 ]。
高斯消元法是通过加入独立的方程组将线性方程组化为三角矩阵的一种系统化方法19世纪著名数学家卡尔·弗雷德里希·高斯( Carl Fredrich Gauss )提出了消元法，作为他对某一定理证明的一部分[ 5 ]，当消元过程中，当系数矩阵对角线上某一行出现零点时，由下面的行进行行交换。高斯消元法需要对n阶方程组进行次运算[ 6 ] [ 7 ]。
分解是由Alan Turing将系数矩阵分解为上三角矩阵和下三角矩阵的乘积，即 [ 8 ]发展而来的一种高斯消元方法，该方法利用方程 和 [ 9 ]分两步求解；Doolittle方法是分解的一种替代方法，下三角矩阵L的对角元素均设为一个[ 7 ]，Doolittle方法需要次运算[ 10 ]；Crout方法是由美国数学家Prescott Crout发展而来的。在Crout方法中，上三角矩阵U将其对角元素均设为1 [ 11 ]，Crout方法同样需要次运算。
Cholesky分解对对称正定矩阵起作用。将方程组中的系数矩阵分解为，其中为下三角矩阵，其转置为上三角矩阵。解涉及和 [ 12 ]的逐次求解，Cholesky分解可作为LU分解的一个特例，其中系数矩阵为对称正定非奇异矩阵。对称正定矩阵的高斯消去不需要支点，占用LU分解方法一半的工作和存储需求[ 13 ] [ 14 ]，Cholesky方法需要次运算[ 10 ]。
QR分解将方程的系统转化为三角系统其中。矩阵Q是正交的( )，R是上三角矩阵[ 15 ] [ 16 ]。
- 方法建立
本文提出的方法是将线性方程组中的系数矩阵A用一个单下三角约化矩阵进行约化，将原系数矩阵转化为一个上三角矩阵，利用分解和Gauss消去的方法，通过回代求解。对于n阶线性方程组给出为:
方程组 ( 1 )的矩阵表示形式为：
其中，是含有原方程元素的系数矩阵，B是包含元素的右边列向量。
该方法将系数矩阵A和右手边列向量B同时转换为如下解：
换句话说，系数矩阵和右手边列向量B通过方程变换：
因此，该过程实质上是以确定下三角矩阵为中心，将系数矩阵降为上三角矩阵，设此矩阵由元素组成：
运算LA = U将系数矩阵A中的系数降为如下的上三角矩阵U：
但是，该方法不需要存储矩阵U，因为只需要确定矩阵L就可以减少矩阵A和右边列向量B。显然，通过只涉及减少矩阵L的矩阵运算看出，
在该方法中，元素将用Gauss消元的Gauss主元行乘子来写，不久将显示，元素是乘子组装成树状结构便于记忆的排列积之和。在降阶过程中，元素不会像通常的Gauss消去或LU分解那样保持不变，而是随着A到U矩阵的降阶过程逐列或逐行进行，当在元素中加入新的Gauss主元行乘子时，元素会发生变化。
与限于列向运算的Gauss方法不同，在该方法中也有可能进行行向运算。实际上，将遵循行智慧过程派生元素。
从下三角L矩阵的第2行开始，唯一未知的是，并就Gauss消元主元行乘子，给出将归零,有如下运算：
|
|
对于第3行，通过支点元素确定，这样：
|
|
对于第3行，剩余元素是通过支点元素确定的，根据第2行之前的操作，支点元素由原值修改而来。因此，我们给出了的约化.
整理合并行乘子m, 对系数矩阵A的元素，即 ，方程（10）变为：
同理可得，第4行的元素确定如下：
对于,
对于,
对于,
对于4x4的矩阵L，归纳元素，可以表示为上面的高斯枢纽乘子m,可以得到矩阵L的等式（15）：
|
|
很容易证明式( 15 )中L矩阵中的m项构成排列积，其中按项数对应二项级数展开的系数。对于L矩阵的任意元素，m-乘积项的个数由下式给出：
二项式展开的幂由下式给出
例如，对于:
这对应于幂的二项式展开，即{1,2,1}
矩阵L中元素的排列积是
|
|
对于，类似地有：
这对应于幂的二项式展开，即{1,3,3,1}
因此，矩阵L中元素的排列积m是
|
|
2.1．m-排列积的树状结构
很容易列举 的 m 排列积，且这些积可以排列成树状结构。 以元素为例，形成如图1所示的树状结构。
图1 形成矩阵L所使用的排列积的树结构。
对于下三角矩阵L的元素，当幂的二项式系数对应的m个乘积时，给出了二项式系数:
例如，对于，,{0,1,2}；
因此，
类似地，对于，,{0,1,2,3}；
一旦确定的值对应于二项式系数，可以按如下步骤计算排列积之和：
以K = { 0，1，2，3 }的为例，取包含3项的K=2,排列积之和由下面的式子给出：
一般来说，对于任意元素，排列积之和可以用如下公式计算：
最后，将和求和得到元素如下
2.3计算下三角矩阵 L 的元素的矩阵形式解
使用矩阵乘法可以很容易地计算下三角矩阵 L 的元素。 对于任意元素 ，矩阵乘法采用以下形式：
|
|
式（26）表明，可以由已经确定的的值确定，其中,排列积为
式 26 可以概括为如下的一般矩阵乘积形式。 再次考虑方程(5)的下三角矩阵L；
由矩阵形式给出现阶段已经确定的相应Gauss行主元乘子的负值:
|
|
矩阵的LU分解后是矩阵L,证明如下：
为了避免混淆，因为传统的LU分解方法有其L矩阵，重新记为，使其与提出的直接分解过程中的L矩阵不同。
从和的关系中可以看出：
那么，
|
or |
|
其中I是单位矩阵。因此L矩阵只是LU分解方法的L矩阵的逆。
如式( 15 )所示的L矩阵元素可以从矩阵方程中重现：
|
|
下面以求解4x4的线性方程组的为例，对方程5所示的4x4矩阵L进行说明。从元素开始，方程( 30 )的矩阵将取如下表示形式：
对于元素：
对于元素：
对于元素：
对于元素：
对于元素：
这就完成了式( 15 )所示的4x4矩阵L，即
|
|
2.4所需的运算次数
所需的运算次数仅与矩阵L元素的确定有关。显然，与LU分解类似，运算的阶数为幂2，即对于n个矩阵，所需的运算次数与成正比增长. 这显可以被看作是一个等差数列1,2,3，hellip;,n-1的行中的的数量， 其总和为：
以4x4矩阵L为例：
方程( 5 )所示矩阵L的元素表示要确定待定的六个元素。与LU分解相比，该方法的运算量只需要LU分解所需运算量的一半。其原因是，与LU方法不同，方法不需要存储U元素，即只需要求解线性方程组的L 矩阵
2.5. 确定矩阵 L元素的过程
下三角矩阵L的元素的计算或多或少可以采用与下面步骤中概述的相同的程序进行行或列的计算。
步骤 1：将元素的所有高斯主元行乘数的初始值设置为零。在计算特定的 值时，将使用其他主元行乘数的最新值。 换句话说，一旦由于逐行计算或逐列计算而改变了 的值，它们的值就会被更新。
步骤2：从第一列和第二行开始，依次按行或按列进行计算和时的值。例如，对于元素，需要计算的m值是，在时，需要计算的。计算m值的矩阵方程为LA = U，其中对于元素，方程采用以下形式：
<t
剩余内容已隐藏，支付完成后下载完整资料</t
英语原文共 21 页，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[595880]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
