大规模线性方程组

2024-05-01

大规模线性方程组（精选八篇）

大规模线性方程组篇1

解大规模线性方程组是数值计算的基本任务之一, 被广泛应用于天气预报、结构分析、热传导、电力网格分析、生产规划、回归分析等诸多领域。目前, 线性方程组解法通常分为两类:直接求解法和迭代求解法。由于直接求解法时间复杂度较高, 在求解大规模线性方程组, 特别是系数矩阵为稀疏矩阵的方程组时, 通常采用迭代法。Jacobi迭代法, Gauss-Seidel迭代法, 逐次超松弛 (SOR) 迭代法, Krylov子空间方法已被许多人研究和应用过[1,2]。文章利用Mann迭代的思想, 提出的求解线性方程组的新方法——Mann迭代并行算法, 具有广泛的应用范围:当系数矩阵的主对角元素不为零时, 在实数范围内对任意初值收敛。

1预备知识

1953年Mann[3]证明了如下定理:

定理1 设T是一个实数集R中的紧区间[a, b]上的连续自映射, 则由下式定义的[a, b]中的序列{xn}

$x \in [a, b] x_{n + 1} = Τ x_{n} x_{n} = \sum_{k = 1}^{n} \frac{x_{k}}{k} n \geq 0$ (1)

收敛于T的不动点。

1991年, David Borwein等人建立了实函数不动点迭代的如下结果:

定理2[4] 设[a, b]为实数集R上的有界闭区间, 映射f:[a, b]→[a, b]连续, {αn}满足:

(i) 0≤αn≤1 n≥0

(ii) $\sum_{n = 0}^{\infty} α_{n} = \infty$

则由下式定义的Mann迭代序列{xn}

${\begin{cases} x_{1} \in [a, b] \\ x_{n + 1} = (1 - α_{n}) x_{n} + α_{n} f (x_{n}) \end{cases}$

(2)

收敛于f的不动点。

现利用实函数不动点的Mann迭代算法, 给出求解线性方程组的Mann迭代并行算法。

2算法描述

设有线性方程组

$\sum_{j = 1}^{n} a_{i, j} x_{j} = b_{i} i = 1, 2, \dots, n$ . (3)

其含有n个未知数x1, x2, …, xn, 其中主对角线元素不为0。

将式 (3) 改写为未知量x的分量的形式为:

$x_{i} = \frac{(b_{i} - \sum_{j = 1}^{n} a_{i j} x_{j} + a_{i j} x_{i})}{a_{i i}}$ (4)

设算子

$Τ x_{i} = \frac{(b_{i} - \sum_{j = 1}^{n} a_{i j} x_{j} + a_{i j} x_{i})}{a_{i i}}$ (5)

定理2已指出Mann迭代对实函数的收敛性, 现对线性方程组式 (3) 进行Mann迭代, 利用第k步所计算的变量xik来计算第k+1步的xik+1的值:

x $_{i}^{k + 1}$ = (1-αn) x $_{i}^{k}$ +αnTx $_{i}^{k}$ (6)

设xik为xi经过k次迭代后的结果, 若对于所有的i=1, 2, …, n, 都有 (xik+1- xik) 小于允许的差值E, 即

${Μ A X}_{i = 1}^{n} | x_{i}^{k + 1} - x_{i}^{k} | < E$ (7)

则表示结果已收敛至允许的误差范围内, 迭代结束。

具体算法如下:

(1) 给定初始解X0, 矩阵[A|B]

(2) 进行迭代, k=1, 2, …, n, 直至收敛

(2.1) 并行求解x $_{i}^{k + 1}$ = (1-αn) x $_{i}^{k}$ +αnTx $_{i}^{k}$

(2.2) 并行求解x $_{i}^{k + 1}$ -x $_{i}^{k}$

(2.3) 判断 ${Μ A X}_{i = 1}^{n} | x_{i}^{k + 1} - x_{i}^{k} |$ 是否满足解误差要求, 如果满足则停止迭代, 输出结果;反之则继续 (2.1)

3并行性分析

3.1串行执行时间

我们首先讨论算法的串行执行时间。

算法的第1步是准备阶段, 第2步是解的循环迭代过程, 我们将计算这一部分的串行计算时间。

设算子Txi的时间复杂度为L (n) , 由式 (5) 可知

L (n) =2n+4 (8)

在一次迭代过程中, 对每一个i, 由式 (6) 可知, 计算xi复杂度 $L^{'} (n)$ 为

L′ (n) =4+L (n) =2n+8 (9)

共有n个xi, 需计算N次才能求解出所有xi, 故串行计算算法第2.1步的复杂度L″ (n) 为

L″ (n) =n×L′ (n) =2n2+8n (10)

串行计算算法第2.2步复杂度为n。算法第2.3步采用顺序查找, 其复杂度为n。设浮点数的乘法和加法的计算时间为Tfc, 则在一次迭代过程中, 即从xik到xik+1的时间复杂度Ts为

Ts= (L″ (n) +n+n) ×Tfc= (2n2+10n) Tfc (11)

3.2并行执行时间

由算法描述可知, 只有第2.3 步规约差值的最大值不能完全并行执行, 其余计算都可以完全并行执行。实际上, 得到最大差值的计算并不占算法的主导地位, 在并行环境下, 可以在O (lgn) 时间内完成[5]。所以, 并行算法的加速比应该接近于处理器的台数p, 现具体证明如下。

若使用p台处理器处理含n个方程的线性方程组, 不妨设n是p的整数倍, 则每个处理器处理q个方程, 其中n=pq。由式 (10) 可知, 第2.1步的时间复杂度为

P (n) =q×L′ (n) =2nq+8q (12)

设n个数规约出最大值的时间复杂度为S (n) , 其中S (n) = O (lgn) , 则第2.3 步的时间复杂度为 (S (n/q) +q) 。若通讯耗时Ttrans, 则在一次迭代中, 并行算法的计算时间Tp为

Tp=[P (n) +q+ (S (n/q) +q) ]Tfc+Ttrans (13)

化简后, 得

$Τ_{p} = (\frac{2}{p} n^{2} + \frac{10}{p} n + S (p)) Τ_{f c} + Τ_{t r a n s}$ (14)

由式 (11) 和式 (14) 得到算法的加速比为

$\frac{Τ_{s}}{Τ_{p}} = p (\frac{2 n^{2} + 10 n}{2 n^{2} + 10 n + p S (p) + ε})$ (15)

由于算法在一次迭代中, 只有同步计算进度和传递最大的误差值时需要通信, 因此, 由ε的定义知n>>ε。而S (p) 为O (lgp) , 故算法的加速比

$\frac{Τ_{s}}{Τ_{p}} \approx p$ (16)

4并行实现

本文算法实验平台为曙光2000集群。

算法第1步为准备阶段, 只计算一次, 在主节点上完成, 主要为读入待计算的方程组并初始化系数矩阵[A|B]和初始向量X0;同时将系数矩阵分为p块, 每块q组, 分别发送给p个处理器;另外将初始向量X0传播到各个节点。

算法第2步为循环迭代过程, 各计算节点用Mann迭代计算q组xik+1, 并计算出xik+1- xik, 此时系统做一次同步, 更新Xk, 并判断两次迭代最大差值是否在允许差值E范围内, 如果是, 则结束计算、输出结果, 否则继续迭代。计算流程图如图1所示。

5数值结果

本节将通过对阶数分别为1000, 2000, 5000, 8000, 10000的五个线性方程组[6]的求解, 来实验算法的加速比和效率。取可接受的差值E=0.0001。

Mann迭代参数αn取

$α_{n} = {\frac{1}{1^{\frac{1}{10}}}, \frac{1}{2^{\frac{1}{10}}}, \dots, \frac{1}{n^{\frac{1}{10}}}, \dots}$

从表1中我们可以看出, 对阶 n=2000, 5000, 8000, 10000的线性方程组, 当p=2、 p=4时, 加速比都接近p, 这与式 (16) 的分析结果是基本相符的;当p=8时, 加速比小于p, 这是由于通信时间随着处理器个数的增加而增大, 使得效率变低。

对于相同的p, 当n=1000, 2000时, 其效率明显低于n=5000, 8000, 10000的情况, 其加速比也小于p, 这是由于当方程组阶数较低时, 每次计算时间较短, 而通信和同步的时间与计算阶数较高方程组时差别不大, 因此, 效率降低。对相同的n值, 随着p的增加, 效率也在降低, 这同样是因为每个处理器的计算时间在减少, 通信和同步时间所占比例相对增加所致。

6结论

本文讨论了在基于消息传递的并行环境下, 将Mann迭代用于解大规模线性方程组的算法。该算法应用范围广, 并行设计简单、有效。理论分析表明, 当同步时间不占主导地位时, 算法的加速比接近处理机台数p, 即接近理想加速比。

摘要：利用实函数不动点的Mann迭代算法, 提出了一种求解大规模线性方程组新的并行算法, 分析了算法的并行加速比, 讨论了算法在基于消息传递机制的MPI并行环境下的实现流程, 给出了并行环境上的实验。该算法适用范围广, 数值计算结果表明理论分析与实际计算相符合, 算法在并行环境下具有较好的并行度, 可适合大规模科学与工程的高性能计算。

关键词：Mann迭代,大规模线性方程组,并行算法

参考文献

[1]Dongarra J, Foster I, Fox G, et al.The Sourcebook of Parallel Compu-ting[M].San Francisco:Morgan Kaufmann, 2002.

[2]Saad Y, van der Vorst H A.Iterative solution of linear systems in the20th century[J].Journal of Computational and Applied Mathematics, 2000, 123:133.

[3]Mann WR.Mean value methods in iteration[J].Proceedings of the A-merican Mathematical Society, 1953, 4 (3) :506510.

[4]Borwein D, Borwein J.Fixed point iterations for real functions[J].Journal of Mathematical Analysis and Applications, 1991, 157 (1) :112126.

[5]Xavier C, Iyengar S S.Introduction to Parallel Algorithms[M].New York:Wiley-IEEE, 1998.

线性方程组教案篇2

章节题目： §3.1 线性方程组的消元解法；§3.2 向量与向量组的线性组合； §3.3 向量的线性相关性；§3.4向量组的秩；§3.5线性方程组解的结构；习题课学时分配：共12学时。

§3.1 线性方程组的消元解法；

3学时 §3.2 向量与向量组的线性组合 1.5学时 §3.3 向量的线性相关性

1.5学时； §3.4向量组的秩；

3学时 §3.5线性方程组解的结构；习题课

3学时本章教学目的与要求：：

目的：使学生掌握线性方程组的初等变换和系数矩阵的初等行变换的关系及线性方程组的求解方法。

要求

1）．理解线性方程组的消元解法与系数矩阵的初等变换的关系； 2）．熟练运用矩阵的初等变换解线性方程组；

3）．理解并掌握矩阵秩的概念，学会用矩阵的初等变换求矩阵秩的方法； 4）．掌握线性方程组有解的判定定理及应用； 5）．掌握齐次线性方程组有非零解的充分必要条件；

课堂教学方案

课程名称：§3.1 线性方程组的消元解法

授课时数：3学时授课类型：理论课教学方法与手段：讲授法

教学目的与要求：使学生掌握线性方程组的初等变换和系数矩阵的初等行变换的关系，熟练运用矩阵的初等变换解线性方程组；

教学重点、难点：线性方程组的初等变换，矩阵的初等变换，消元法解线性方程组的具体做法，教学内容

§3.1 线性方程组的消元解法

现在讨论一般线性方程组.所谓一般线性方程组是指形式为

a11x1a12x2axax211222am1x1am2x2a1nxnb1,a2nxnb2,amnxnbm

(3.1)的方程组，aij(i1,2，m;j1,2，n)称为线性方程组的系数，bj(j1,2，m)称为常数项.系数aij的第一个指标i表示它在第i个方程，第二个指标j表示它是xj的系数.其中x1,x2,,xn代表n个未知量，m是方程的个数，方程组中未知量的个数n与方程的个数m不一定相等.若记：

a11a12a21a22Aam1am2a1nx1b1a2nxb22

X

b

xamnbsna1na2namnb1b2

（3.2）bm而系数和常数项又可以排成下表：

a11a12a21a22Aam1am2显然AXb，实际上，有了(3.2)之后，除去代表未知量的文字外线性方程组(3.1)就确定了，方程解的情况与采用什么文字来代表未知量没有关系.这里矩阵A称为线性方程组的系数矩阵，A 称为增广矩阵。

在中学所学代数里学过用加减消元法和代入消元法。解二元、三元线性方程组.实际上，这个方法比用行列式解线性方程组更有普遍性.下面就来介绍如何用一般消元法解一般线性方程组.例1，解方程组

2x12x2x36,x12x24x33, 5x7xx28.231不难看出，在消去未知量的过程中，它实际上是反复地对方程组进行变换，而所用的变换也只是由以下三种基本的变换所构成：

1.互换两个方程的位置，2.用一非零数乘某一方程； 3.把一个方程的倍数加到另一个方程。

以上三种变换1，2，3称为线性方程组的初等变换.所谓方程组(3.1)的一个解就是指由n个数k1,k2,,kn组成的有序数组(k1,k2,,kn)，当x1,x2,,xn分别用k1,k2,,kn代入后，(3.1)中每个等式都变成恒等式.方程组(3.1)的解的全体称为它的解集合.解方程组实际上就是找出它全部的解，或者说，求出它的解集合.如果两个方程组有相同的解集合，它们就称为同解的.显然初等变换把一个线性方程组变成一个与它同解的线性方程组

线性方程组有没有解完全取决于（3.1）的系数和常数项，如果知道了一个线性方程组的全部系数和常数项，那么这个线性方程组的解就基本上确定了.显然，消元法求方程组解的过程就是相当于对线性方程组的增广矩阵反复施行初等变换的过程.线性方程组的初等变换对应于矩阵的初等行变换，因此，以下从矩阵的初等变换入手讨论方程的解。

定理3.1 线性方程组(3.1)的增广矩阵总可以通过矩阵的初等行变换和第一种列变换化为以下形式：

c11c120c210000c1rc2rcr,r1c1nc2ncrn0d1d2dr（3.3）dr10相应地，线性方程组(3.1)化为

c11x1c12x2c1rxrc1nxnd1,c22x2c2rxrc2nxnd2,crrxrcrnxndr,

（3.4）0d,r100,00.因此线性方程组（3.1）有解的充要条件是rA,brA，并且当rA,bn时方程组有唯一解，当rA,bn时有无穷多解。简要证明：对于方程组(3.1)，首先检查x1的系数.如果x1的系数a11,a21,,as1全为零，那么方程组(3.1)对x1没有任何限制，x1就可以取任何值，而方程组(3.1)可以看作x2,,xn的方程组来解.如果x1的系数不全为零，那么利用初等变换1，不妨设a110.利用初等变换3，分别把第一个方程的(i2,,n).于是方程组(3.1)就变成

a11x1a12x2a1nxnb1,x2a2nxnb2,a22

as2x2asnxnbs,ai1倍加到第i个方程a11其中

aijaijai1a1j,i2,,s,j2,,n a11相应的，增广矩阵的第一列除a110外，其余元素全变为0 这样，解方程组(3.1)的问题就归结为解方程组

x2a2nxnb2,a22

axaxbsnnns22的问题.这样一步步作下去，最后就得到一个阶梯形方程组.为了讨论起来方便，不妨设所得的方程组为

c11x1c12x2c1rxrc1nxnd1,c22x2c2rxrc2nxnd2,crrxrcrnxndr,

(3.5)0d,r100,00.相应的矩阵为 c11c120c21 0000c1rc2rcr,r1c1nc2ncrn0d1d2dr(3.6)dr10其中cii0,i1,2,,r.方程组(3.5)中的“0=0”这样一些恒等式可能不出现，也可能出现，这时去掉它们也不影响(3.11)的解.而且(3.1)与(3.5)是同解的.现在考虑的解的情况.如(3.5)中有方程0dr1，而dr10.这时不管x1,x2,,xn取什么值都不能使它成为等式.故(3.5)无解，因而(1)无解.当dr1是零或(3.5)中根本没有“0=0”的方程时，分两种情况： 1）rn.这时阶梯形方程组为

c11x1c12x2c1nxnd1,c22x2c2nxnd2,

（3.7）cnnxndn,其中cii0,i1,2,,n.由最后一个方程开始，xn,xn1,,x1的值就可以逐个地唯一决定了.在这个情形，方程组(3.7)的解也就是方程组(1)有唯一的解.2）rn.这时阶梯形方程组为

c11x1c12x2c1rxrc1,r1xr1c1nxnd1,c22x2c2rxrc2,r1xr1c2nxnd2, crrxrcr,r1xr1crnxndr,其中cii0,i1,2,,r.把它改写成

c11x1c12x2c1rxrd1c1,r1xr1c1nxn,c22x2c2rxrd2c2,r1xr1c2nxn,

(3.8)crrxrdrcr,r1xr1crnxn.由此可见，任给xr1,,xn一组值，就唯一地定出x1,x2,,xr的值，也就是定出方程组(3.8)的一个解.一般地，由(3.8)我们可以把x1,x2,,xr通过xr1,,xn表示出来，这样一组表达式称为方程组(3.1)的一般解，而xr1,,xn称为一组自由未知量.从这个例子看出，对线性方程组的增广矩阵实施初等变换，有时不一定是（3.5）的样子，但总可以适当调换矩阵的列，相当于同时交换方程组中某两个未知量的位置，这并不影响方程的解。以上就是用消元法解线性方程组的整个过程.总起来说就是，首先用初等变换化线性方程组为阶梯形方程组，把最后的一些恒等式“0=0”(如果出现的话)去掉.如果剩下的方程当中最后的一个等式是零等于一非零的数，那么方程组无解，否则有解.在有解的情况下，如果阶梯形方程组中方程的个数r等于未知量的个数，那么方程组有唯一的解；如果阶梯形方程组中方程的个数r小于未知量的个数，那么方程组就有无穷多个解.例2 解线性方程组

x15x2x3x41,x2xx3x3,1234 3x18x2x3x41,x19x23x37x47.例3 解线性方程组

x12x23x3x45,2x4xx3,124 x12x23x32x48,x12x29x35x421.课后作业：P152 1，3

课堂教学方案

课程名称： §3.2向量与向量组的线性相关性授课时数：1.5学时授课类型:理论课

教学方法与手段：讲授法

教学目的与要求：掌握向量组的线性相关、无关的定义，掌握有关定理及推论教学重点、难点：重点是判别向量组的线性相关性；难点是定理的证明教学内容

§3.2 向量与向量组的线性组合

（一）向量及其线性运算

定义3.1 所谓数域P上一个n维向量就是由数域P中n个数组成的有序数组

(a1,a2,,an)

(1)ai称为向量(1)的第i分量.用小写希腊字母,,,来代表向量.向量通常是写成一行：

(a1,a2,,an).有时也可以写成一列：

b1b2.bn为了区别，前者称为行向量，后者称为列向量。它们的区别只是写法上的不同.如果n维向量

(a1,a2,,an),(b1,b2,,bn)的对应分量都相等，即

aibi(i1,2,,n).就称这两个向量是相等的，记作.分量全为零的向量(0,0,,0)称为零向量，记为0;向量(a1,a2,,an)称为向量(a1,a2,,an)的负向量，记为.定义3.2 向量

(a1b1,a2b2,,anbn)

称为向量

(a1,a2,,an),(b1,b2,,bn)的和，记为

定义3.3 设k为数域P中的数，向量(ka1,ka2,,kan)称为向量(a1,a2,,an)与数k的数量乘积，记为k

定义3.4 所有n维实向量的集合记为Rn，Rn的n维向量的全体，同时考虑到定义在它们上面的加法和数量乘法，称为实n维向量空间.显然线性空间中元素满足以下规律：

交换律：

.(2)结合律：

()().(3)

0.(4)

()0.(5)k()kk，(6)(kl)kl，(7)k(l)(kl)，(8)

1.(9)(6)—(9)是关于数量乘法的四条基本运算规则.由(6)—(9)或由定义不难推出：

00，(10)

(1)，(11)

k00.(12)如果k0,0，那么

k0.(13)例1．计算

11（i）（2，0，-1）+（-1，-1，2）+（0，1，-1）；

321（ii）5（0，1，-1）-3（1，2）+（1，-3，1）．

3例2．证明：如果

a（2，1，3）+ b（0,1,2）+ c（1，-1，4）=（0，0，0），那么a = b = c = 0．

（二）向量组的线性组合

两个向量之间最简单的关系是成比例.所谓向量与成比例就是说有一数k使

k.定义3.5 向量称为向量组1,2,的数k1,k2,,ks，使

k11k22如果有数域P中,s的一个线性组合，kss, ,s其中k1,k2,,ks叫做这个线性组合的系数.当向量是向量组1,2,的一个线性组合时，也说可以经向量组1,2，s线性表出.例如，任一个n维向量(a1,a2,,an)都是下面向量组的一个线性组合.1(1,0,,0),(0,1,,0),2 

n(0,0,,1)向量1,2,,n称为n维单位向量.零向量是任意向量组的线性组合.a1jb1a2jb2定理3.3设，向量i（j1,2,abmmj组1,2，n），则向量可由向量,n线性表示的充要条件是：以1,2，n为列向量的矩阵与以1,2，n，为列向量的矩阵有相同的秩

若向量组1,2，s的中每一个向量i(i1,2,s,都)可以经向量组1,2，t线性表出，那么向量组1,2，s就称为可以经向量组1,2，t线性表出.定理3.4如果向量组1,2,组1,2，s可以经向量组1,2，t线性表出，向量,s可以,t可以经向量组1,2,,p线性表出，那么向量组1,2,经向量组1,2,,p线性表出.定义3.5如果两个向量组互相可以线性表出，它们就称为等价.向量组之间等价具有以下性质：

1）反身性：每一个向量组都与它自身等价.2）对称性：如果向量组1,2,,s与1,2,,t等价，那么向量组1,2,,t与1,2,,s等价.3）传递性：如果向量组1,2,,s与1,2,,t等价，1,2,,t与1,2,,p等价，那么向量组1,2,,s与1,2,,p等价.课后作业：P159 4，6（1），8

课堂教学方案

课程名称： §3.3向量组的线性相关性授课时数：1.5学时授课类型:理论课

教学方法与手段：讲授法

§3.3向量组的线性相关性

定义3.7向量组1,2,,s(s1)称为线性相关的，如果有数域P中不全为零的数k1,k2,,ks，使

k11k22kss0

如果当且仅当k1k2线性无关。

从定义可以看出，单独一个零向量线性相关，单独一个非零向量线性无关.任意一个包含零向量的向量组一定是线性相关的.向量组1,2线性相关就表示

ks0上式成立，则称向量组,,,(s1)12s1k2或者2k1(这两个式子不一定能同时成立).在P为实数域，并且是三维时，就表示向量1与2共线.三个向量1,2,3线性相关的几何意义就是它们共面.并且如果一向量组线性无关，那么它的任何一个非空的部分组也线性无关.特别地，由于两个成比例的向量是线性相关的，所以，线性无关的向量组中一定不能包含两个成比例的向量.不难看出，由n维单位向量1,2,,n组成的向量组是线性无关的.定理3.5 向量组1,2，n，其中

a1ja2jij1,2,amj,n，则1,2，n线性相关的充要条件是：以1,2，n为列向量的矩阵的秩小于向量的个数n。

具体判断一个向量组是线性相关还是线性无关的问题可以归结为解方程组的问题.向量组1,2，n线性相关齐次线性方程组x11x22xnn0有非零,n线,n解。或者说齐次线性方程组x11x22性无关。

推论1 设n个向量ia1j,a2j,线性相关的充要条件是：

a11a21an1a12a22an2xnn0只有零解1,2,，向量组1,2，n）,anj（j1,2,a1na2nann0

注：这里把1,2，n应理解为列向量。

也可以说向量组1,2，m线性相关A(12m)的秩小于向量个数m；向量组线性无关A(12m)的秩为m.从而，如果向量组(2)线性无关，那么在每一个向量上添一个分量所得到的n1维的向量组

i(ai1,ai2,,ain,ai,n1),i1,2,,s(5)也线性无关.例1 判断P3的向量

1(1,2,3),2(2,1,0),3(1,7,9)

是否线性相关。

例2 若向量组1,2,3线性无关，则向量组212,253,4331也线性无关.例3若向量1,2，m的部分组1,2，s(sm)线性相关,s线性无关。1,2，m线性相关。反之，1,2，m线性无关1,2,证：因为1,2，s线性相关，则存在不全为零的k1,k2,kss0s1,ks，使

k11k22则1,2,（2）记 kss0k110m0 ,m线性相关。

a1ja1j,(j1,j,jarjarjar1j,m)

若1,2，m线性无关1,2，m线性相关。,m线性无关。反之，若1,2，m线性相关1,2,证：1°记A(1,2,,m),B(1,2,m,，)显然r(A)r(B)，因为1,2，m线性无关，知r(A)m，因而r(B)m.2°因为B只有m列，所以r(B)m.由1°和2°知r(B)m，知1,2，m线性无关。,m，当nm时1,2，m线（3）m个n维向量组成的向量组1,2,性相关。

证：记Anm(1,相关。

（4）设向量组1,2，m)，因为nmr(Anm)nm，则1,2，m线性,m线性无关，1,2，m,线性相关可由1,2，m表示，且表示法唯一。

证：记A(1,2,1°因为1,2,2°因为1,2，m),B(1,2，m,)，显然r(A)r(B).,m线性无关，知r(A)m ,m,线性相关，知r(B)m1 ,m)xb有解且唯一。可由因此r(B)m，知，Ax(1,2,1,2，m表示，且表示法唯一。□

推论1 当向量组中所含向量的个数大于向量的维数时，此向量组线性相关。定理3.6 如果一向量组的一部分线性相关，那么这个向量组就线性相关.（二）关于线性组合与线性相关的定理

定理3.7 向量组1,2,,s(s2)，线性相关向量组1,2,,s中至少存在一个向量能由其余s1个向量线性表示。

定理3.8 设1,2,以由1,2,而向量1,2，s线性相关，则可,s线性无关，,s线性表示，且表示法唯一。,s与1,2，t是两个向量组.如果向量组定理3.9 设1,2,1,2，t可以经1,2，s线性表出，且ts，那么向量组1,2，t必线性相关.反之如果向量组1,2，t可以经向量组1,2，s线性表出，且1,2，t线性无关，那么ts.推论两个线性无关的等价的向量组，必含有相同个数的向量.例4（1）设1,2,3线性无关，证明1,12,123也线性无关；对n个线性无关向量组1,2,,n，以上命题是否成立？

（2）当1,2,3线性无关，证明112,223,313也线性无关，当1,2,,n线性无关时，12,23,,n1n,n1是否也线性无关？

解：令x11x22x330，代入整理得：.因为1,2,3线性无关，则应有

x30x10x1x2x2x30

（﹡）

(x1x3)1(x1x2)2(x2x3)30 101101A110011B011001

r(A)r(B)3，所以（﹡）式只有零解，由定理5推论1知1,2,3线性无关。

例5 设在向量组1,2,,n中，10且每个i都不能表成它的前i1个向量1,2,,i1的线性组合，证明1,2,,n线性无关.例6 研究下面向量组的线性相关性

10112,2,230352

解：解法1.令k11k22k330，整理得 k3k12k12k23k15k22k3因为线性方程组的系数行列式

000

101002

所以方程组必有非零解，知1,2,3线性相关。

（2）解法2.由

101101行220022B352000 2235知1,2,3线性相关。□

小结：(1)若所给的向量为行向量，转置成列向量，再用上面的方法求解即可。（2）解法2一般说来比较好，今后尽可能用解法2.例7已知1,2,3线性无关，112，223，331，证明向量组1,2,3线性无关。

课后作业P160

11，13，15，16（1）

课堂教学方案

课程名称： §3.4 向量组的秩授课时数：3学时授课类型:理论课

教学方法与手段：讲授法

教学目的与要求：掌握向量组的秩的定义，掌握有关定理及推论教学重点、难点：向量组的秩的定义、有关定理及推论教学内容

（一）向量组的极大线性无关组

定义3.8 n维向量组1,2,,s的一个部分组称为一个极大线性无关组，如果这个部分组本身是线性无关的，并且从这个向量组中任意添一个向量(如果还有的话)，所得的部分向量组都线性相关.一个线性无关向量组的极大线性无关组就是这个向量组本身.极大线性无关组的一个基本性质是，任意一个极大线性无关组都与向量组本身等价.比如看R3的向量组

1(1,0,0),2(0,1,0),3(1,1,0)

在这里｛1,2｝线性无关，而312，所以｛1,2｝是一个极大线性无关组.另一方面，｛1,3｝，｛2,3｝也都是向量组｛1,2,3｝的极大线性无关组.定理3.10如果 j1,j2，jr是1,2,,s的线性无关部分组，它是极大,jr线性表示。无关组的充要条件是1,2,,s中每一个向量都可由j1,j2,上面的例子可以看出，向量组的极大线性无关组不是唯一的.但是每一个极大线性无关组都与向量组本身等价，因而，一向量组的任意两个极大线性无关组都是等价的.（二）向量组的秩

一向量组的极大线性无关组都含有相同个数的向量.因此，极大线性无关组所含向量的个数与极大线性无关组的选择无关，它直接反映了向量组本身的性质.因此有

定义3.9 向量组1,2,,s的极大线性无关组所含向量的个数称为这个向量组的秩.一向量组线性无关的充要条件是它的秩与它所含向量的个数相同.每一向量组都与它的极大线性无关组等价.由等价的传递性可知，任意两个等价向量组的极大线性无关组也等价.所以，等价的向量组必有相同的秩.含有非零向量的向量组一定有极大线性无关组，且任一个线性无关的部分向量都能扩充成一极大线性无关组.全部由零向量组成的向量组没有极大线性无关组.规定这样的向量组的秩为零.例如，矩阵

10A00的行向量组是

1321000014 501(1,1,3,1),2(0,2,1,4),3(0,0,0,5),4(0,0,0,0)

它的秩是3.它的列向量组是

1(1,0,0,0),2(1,2,0,0),3(3,1,0,0),4(1,4,5,0)

它的秩也是3.矩阵A的行秩等于列秩，这点不是偶然的.定理3.11 A为mn矩阵，rAr的充要条件是A的列（行）秩为r。推论：A的列秩与行秩相等。（因为行秩等于列秩，所以下面就统称为矩阵的秩.）

例1求向量组1(2,4,2),2(1,1,0),3(2,3,1),4(3,5,2)的一个极大无关组，并把其余向量用该极大无关组线性表示。

例2设1,2,以经1,2，s与1,2，t是两个向量组.如果向量组1,2，s可,t线性表出，r1,2，sr1,2，t

定理3.11 设向量组1,2，s与1,2，t等价，则：

r1,2，sr1,2，t

例3 设A是数域F上mn矩阵，B是数域F上ns矩阵，于是

r(AB)min[r(A),r(B)]，即乘积的秩不超过各因子的秩.特别地，当有一个因子是可逆矩阵时，乘积的秩等于另一个因子的秩。

课后作业P161

17，18，19

课堂教学方案

课程名称： §3.5 线性方程组解的结构授课时数：3学时授课类型:理论课

教学方法与手段：讲授法

教学目的与要求：理解基础解系的概念，掌握线性方程组解的结构教学重点、难点：线性方程组解的结构教学内容

§3.5 线性方程组解的结构

设线性方程组为

a11x1a12x2axax211222am1x1am2x2a1nxnb1,a2nxnb2,amnxnbm

当用初等行变换把增广矩阵A化成如下阶梯形

其中cii0,i1,2,c1100000c12c1r0000crr000c1nc2ncrn000c22c2rd1d2dr 000,r时方程组有解.以下讨论线性方程组解的结构。所谓解的结构问题就是解与解之间的关系问题.首先讨论齐次线性方程组。

一、齐次线性方程组的解的结构设

a11x1a12x2axax211222 am1x1am2x2a1nxn0,a2nxn0,amnxn0(1)是一齐次线性方程组，它的解所成的集合具有下面两个重要性质： 1.两个解的和还是方程组的解.2.一个解的倍数还是方程组的解.对于齐次线性方程组，综合以上两点即得，解的线性组合还是方程组的解.这个性质说明了，如果方程组有几个解，那么这些解的所有可能的线性组合就给出了很多的解.基于这个事实，我们要问：齐次线性方程组的全部解是否能够通过它的有限的几个解的线性组合给出？

定义3.10 齐次线性方程组(1)的一组解1,2,,t称为(1)的一个基础解系，如果

1）(1)的任一个解都能表成1,2,,t的线性组合； 2）1,2,,t线性无关.应该注意，定义中的条件2)是为了保证基础解系中没有多余的解.由定义容易看出，任何一个线性无关的与某一个基础解系等价的向量组都是基础解系.定理3.13在齐次线性方程组有非零解的情况下，它有基础解系，并且基础解系所含解的个数等于nr，这里r表示系数矩阵的秩(nr是自由未知量的个数).设齐次线性方程组经过初等变换化为

x1k1,r1xr1xkx22,r1r1xrkr,r1xr1knx1x1k1r,x1r1n，xkxkx,2r,1r1n2n,2k1,nxn,k2,nxn,xr1krnx

即

xrkr,r1,n，xxr1r1kr,nxn.xr2xr2xnxn用矩阵表示即为：

k1,r1k1,r2x1kk2,r12,r2x2kkr,r1xr,r2xxrr1r201xr101xn00k1,nk2,nkr,nxn0

01k1,r1k1,r2kk2,r12,r2kkr,r1r,r2，记12100100x1x2则xnkk1122k1,nk2,nkr,n,r0称作原方程组的一个基础解系

01krr 二、一般线性方程组的解的结构如果把一般线性方程组

a11x1a12x2a1nxnb1,axaxaxb,2112222nn2(2)as1x1as2x2asnxnbs的常数项换成0，就得到齐次线性方程组(1).齐次线性方程组(1)称为方程组(2)的导出组.方程组(2)的解与它的导出组(1)的之间有密切的关系：

1.线性方程组(2)的两个解的差是它的导出组(1)的解.2.线性方程组(2)的一个解与它的导出组(1)的一个解之和还是这个线性方程组的一个解.定理3.14 如果是线性方程组(2)的一个特解，是其导出组的全部解，那么即为线性方程组(2)的全部解。

定理说明了，为了找出一线性方程组的全部解，只要找出它的一个特殊的解以及它的导出组的全部解就行了.导出组是一个齐次线性方程组，在上面已经看到，一个齐次线性方程组的解的全体可以用基础解系来表示.因此，根据定理我们可以用导出组的基础解系来表出一般线性方程组的一般解；如果0是线性方程组(2)的一个特解，1,2,,nr是其导出组的一个基础解系，那么(2)的任一个解都可以表成

0k11k22knrnr

大规模线性方程组篇3

1.相关概念

定义1设V, W是数域F上的两个向量空间, 如果映射:τ:V→W满足

τ (aα+bβ) =aτ (α) +br (β) , α, β∈V, a, b∈F, 则称τ是V到W的一个线性映射.

定义2向量空间V在τ之下的象集是W的一个子集, 叫作τ的象, 记作Im (τ) , 即Im (τ) ={τ (α) |α∈V}.

定义3把W的零子空间{0}在τ之下的原象的集合, 叫作τ的核, 记作核 (τ) , 即核 (τ) ={α|α∈V, 且τ (α) =0}.

2.基本性质

设τ是数域F上向量空间V到向量空间W的一个线性映射.

性质1 Im (τ) 是V的一个子空间, 核 (τ) 是W的一个子空间.

性质2设α1, α2, …, αn是向量空间V的一个基,

则Im (τ) ={a1τ (α1) +a2τ (α2) +…+anτ (αn) |ai∈F, i=1, 2, …, n}=L (τ (α1) , τ (α2) , …, τ (αn) ) .

性质3设dim V=n, 则dim Im (τ) +dim核 (τ) =n.

以上性质在一般的高等代数教材中均有证明, 在此不予证明.

二、线性方程组理论

一般线性方程组的基本问题有三个:解的存在性、解的数量、解的结构.下面我们用线性映射的性质来解决这些问题.

设数域F上的n元线性方程组为

简记为AX=B, 其中A为 (1) 的系数矩阵, B= (b1, b2, …, bm) T, X= (X1, X2, …, Xn) T.

定义τ:α|→Aα, α= (a1, a2, …, an) T∈Fn.

由定义1容易得τ是向量空间Fn到Fm上的一个线性映射, 并且

τ (α) =Aα, α∈Fn;Im (τ) =L (A1, A2, …, An) ;dim Im (τ) =秩 (A) .其中, Ai= (a1i, a2i, …, ami) T∈Fm, (i=1, 2, …, n) , A= (A1, A2, …, An) .

1.齐次线性方程组AX=0的解及结构

由上述向量空间Fn到Fm上的一个线性映射τ的定义可知:对于α∈Fn, α是AX=0的解当且仅当α是核 (τ) 中的元素, 因此, AX=0的解集就是核 (τ) .于是, 我们有

当AX=0有非零解时, 设γ1, γ2, …, γs是向量空间核 (τ) 的一个基, 那么AX=0的全部解构成的集合为{a1γ1+a2γ2+…+asγs|ai∈F, i=1, 2, …, s}.

2.线性方程组AX=B的解及结构

AX=B有解, 则存在α∈Fn, 使得τ (α) =Aα=B∈Fm, 所以

设α0是AX=B的一个固定解, 对AX=B的任意解γ, 令α0-γ=β, 则β是AX=0的解, 所以, AX=B的解的集合是{α0+β|β∈核 (τ) }.于是

因此, 当线性方程组AX=B有无穷多个解时, 它有解集为:

大规模线性方程组篇4

关键词：线性代数方程组,块状五对角矩阵,线性插值方法

在计算数学中,有相当一部分问题都归结为线性代数方程组的求解问题,尤其是特殊结构的大型分块带状线性代数方程组,在工程领域,如:流体力学、天体预测和系统控制等方面会经常遇到。采用迭代方法[1,2,3]求解这类问题时,需要讨论算法的收敛性,这是一个难度相当大的问题;而采用直接方法[2]求解时,需要设计一种可行方案,使解法的运算量不随方程组阶数的增大而过分增加。本文针对特殊结构的大型线性代数方程组,即块状五对角线性代数方程组建立了一种线性插值求解方法,该方法所需要的乘除法运算量随着子方程的个数呈线性增长,而通常的Gauss消去法所需要的乘除法运算量随着子方程的个数呈立方增长。

1 线性插值方法

考虑线性代数方程组Ax=f,其中

undefined

系数矩阵A为可逆方阵,Ai,Bi,Ci,Di是r阶方阵,Fi是r阶可逆方阵,xi和fi为r维列向量。方程组Ax=f的m个子方程为

undefined

则方程组undefined等价于

任意给定x1,x2,由(2)式的第(1)个子方程解出x3,由第(2)个子方程解出x4,再由第(i)个子方程解出xi+2(i=3,…,m-2),可得方程组undefined的一组解.分别取

可求得方程组undefined的2r+1组解

令y(k)=x(k)-x(0),即yundefined=xundefined-xundefined(i=1,…,m),则有undefined。任意选取参数t1,t2,…,t2r,构造向量

undefined

易见undefined。要求x*满足(1)式的第(m-1)个子方程,可得

undefined

整理得

undefined

又要求x*满足(1)式的第(m)各子方程,可得

undefined

整理得

undefined

若(4)式和(5)式组成的2r阶方程组有唯一解t1,t2,…,t2r则由(3)式确定的x*是方程组Ax=f的唯一解。称这种方法为解块状五对角方程组的线性插值法。

2 插值解的存在性与运算量分析

首先证明由(4)式和(5)式组成的2r阶方程组有唯一解t1,t2,…,t2r。

因为由xundefined,xundefined,…,xundefined和xundefined,xundefined,…,xundefined构成的2r维向量组线性无关,所以mr维向量组x(1),x(2),…,x(2r)线性无关,从而mr维向量组y(1),y(2),…,y(2r)线性无关。有因为矩阵A可逆,所以mr×2r矩阵A(y(1),y(2),…,y(2r))列满秩。注意到

undefined

故2r阶方阵

undefined

列满秩,从而为可逆矩阵,因此由(4)式和(5)式组成的方程组有唯一解t1,t2,…,t2r。

再来分析线性插值法的运算量。

给定x1,x2,求解一个子方程(Gauss消去法)约需undefined次乘除法运算(其中形成子方程需要4r2次乘法运算),求得方程组undefined的一组解约需undefined次乘除法运算,求得方程组的2r+1组解约需undefined次乘除法运算,求解(4)式和(5)式组成的2r阶方程组(Gauss消去法)约需undefined次乘除法运算(其中形成(4)式约需8r3+4r2次乘除法运算,形成(5)式约需6r3+3r2次乘除法运算),由(3)式计算x*约需2mr2次乘法运算.总的乘除法运算次数大约为undefined

也就是undefined。

直接求解方程组Ax=f(Gauss消去法)约需undefined次乘除法运算。

当r=3,4,6,9时,分别取m=100和m=1000,线性插值法与直接法所需的乘除法运算次数对比见表1和表2。

易见,当时m=100,直接法所需的乘除法运算量是线性插值法的200倍,当m=1000时,直接法所需的乘除法运算量是线性插值法的20000倍,即当子方程组的个数增大10倍时,线性插值法的乘除法运算也增大10倍,而直接法的乘除法运算量增大1000倍。

3 算例

例1 设线性代数方程组Ax=f系数矩阵的子矩阵分别为

undefined

分别对m=1000,5000,10000,50000使用线性插值方法求解方程组Ax=f,各子方程的误差为

δ1=‖C1x1+D1x2+F1x3-f1‖2

δ2=‖B2x1+C2x2+D2x3+F2x4-f2‖2

δi=‖Aixi-2+Bixi-1+Cixi+Dixi+1+Fixi+2-fi‖2(i=3,…,m-2)

δm-1=‖Am-1xm-3+Bm-1xm-2+Cm-1xm-1+Dm-1xm-fm-1‖2

δm=‖Amxm-2+Bmxm-1+Cmxm-fm‖2

求解的时间与子方程的误差见表3。

例2 设线性代数方程组Ax=f系数矩阵的子矩阵分别为

undefined

分别对m=1000,5000,10000,50000使用线性插值方法求解方程组Ax=f,求解的时间与子方程的误差见表4。

参考文献

[1]颜庆津.数值分析.北京:北京航空航天大学出版社,2000

[2]张凯院,徐仲.数值代数.西安:西北工业大学出版社,2000

大规模线性方程组篇5

在《线性代数的教学思路 (I) 》[4]给出的教学思路基础上, 本文给出非数学专业线性代数克莱姆规则的教学思路。并且应用关系映射反演思想方法简要论述克莱姆规则。教学实验证实, 这一教学思路具有可行性和可操作性, 并且是适宜的和有效的。更一般的理论研究和具体教学实验, 请参看有关文献[1,5]。

定义1给定一个含有n个未知量n个方程的线性方程组 (1)

它的系数构成一个行列式D

D称为这个线性方程组的系数行列式。

定理5.5.1 (克莱姆 (Cramer) 规则) :一个含有n个未知量n个方程的线性方程组 (1)

当它的系数行列式D≠0时, 有且仅有一个解

此处Dj是把系数行列式D的第j列换成方程组的常数列b1, b2, …, bn得到的n阶行列式。

证明令j是整数1, 2, …, n中的任意一个。分别以A1j, A2j, …, Anj乘方程组 (1) 的第一, 第二, …, 第n个方程, 然后相加, 得

由定理3.4.2和定理3.4.3, xj的系数等于D而xi (i≠j) 的系数都是零;因此等式左端等于Dxj, 而等式右端刚好是n阶行列式Dj, 此处Dj是把系数行列式D的第j列换成方程组的常数列b1, b2, …, bn得到的n阶行列式。

这样, 我们得到Dxj=Dj

令j=1, 2, …, n, 我们得到方程组

方程组 (1) 的每一个解都是方程组 (3) 的解.事实上, 设c1, c2, …, cn是方程组 (1) 的一个解.那么在 (1) 中把xi代以ci (i=1, 2, …, n) , 就得到一组等式.对于这一组等式施以由方程组 (1) 到方程组 (3) 的变换, 显然得到下面的一组等式:

这就是说, c1, c2, …, cn也是方程组 (3) 的一个解。

当D≠0时, 方程组 (3) 有唯一解, 就是 (2) , 因此方程组 (1) 也最多有这一个解。

我们证明 (2) 是 (1) 的解.为此, 把 (2) 代入方程组 (1) , 那么 (1) 的第i (i=1, 2, …, n) 个方程的左端变为

计算出来, 我们得到

这里我们应用了定理3.4.2和定理3.4.3.这就是说, (2) 是方程组 (1) 的解。

因此, 当D≠0时, 方程组 (1) 有且仅有一个解, 这个解由公式

(2) 给出。

克莱姆 (Cramer) 规则的RMI方法的框图如图1 (为节省篇幅采用矩阵形式) 。

注:本文是2008年度甘肃省教育厅第二批科研项目计划项目 (序号0805B-08) 的研究成果之一。

参考文献

【1】窦永平.数学教育整体思路导言【J】.兰州商学院学报, 2002, (4) :127-128.

【2】平云.高等学校数学教学中的德育教育初探【J】.兰州商学院学报, 1993, 增刊 (1) :51-52.

【3】窦永平.线性规划模型建立的教学思路【J】.兰州商学院学报, 1990, (2) :66-70.

【4】窦永平线性代数的教学思路 (I) 【J】.高等理科教育, 2004, 教育教学研究专辑 (二) :8-10.

【5】平耘.教学组织论的研究与建立【J】.社科纵横, 1992, (5) :47-49.

【6】张禾瑞.郝新.高等代数【M】.北京:人民教育出版社, 1979.

【7】窦永平.行列式的教学思路【J】.甘肃科技纵横, 2006, (1) :162.184.

【8】窦永平.行列式展开理论的教学思路【J】.甘肃科技纵横, 2006, (4) :161.

线性方程组的求解及其应用篇6

线性方程组的解法，早在中国古代的数学著作《九章算术》方程章中已做了比较完整的论述.其中所述方法实质上相当于现代的对方程组的增广矩阵施行初等行变换，从而消去未知量的方法，即高斯消元法.在西方，线性方程组的研究是在17世纪后期由莱布尼茨开创的.他曾研究含两个未知量的三个线性方程组组成的方程组.麦克劳林在18世纪上半叶研究了具有二、三、四个未知量的线性方程组，得到了现在称为克莱姆法则的结果.克莱姆不久也发表了这个法则.18世纪下半叶，法国数学家贝祖对线性方程组理论进行了一系列研究，证明了一元齐次线性方程组有非零解的条件是系数行列式等于零.

2. 线性方程组解的结构

n元线性方程组的一个解(c1, c2，…cn)是一个n维向量，当方程组有无穷多个解时，需要研究这些解向量之间的关系，以便更透彻地把握住它们.

关于齐次线性方程组的解的结构有以下结论：

1)定义1齐次线性方程组的一组解η1，η2，…ηt称为该方程组的一个基础解系，如果

a)该方程组的任一解都能表成η1，η2，…ηt的线性组合.

b)η1η2…ηt线性无关.

2)齐次线性方程组的两个解的和还是解，一个解的倍数还是解.

3)齐次线性方程组有非零解时必定存在基础解系，并且一个基础解系里有n-r个解，其中n是未知量的个数，r是系数矩阵的秩.如果系数在数域P中的齐次线性方程组 (1) 的一个基础解系是：η1，η2…ηn-r，则 (1) 的全部解为

其中k1, k2，…kn-r取遍数域P中的全部数.

3. 线性方程组的求解方法

3.1 消元法

解线性方程组的最基本最有效的方法是消元法.它的做法是：先把线性方程组的增广矩阵经过矩阵的初等行变换化成阶梯形，然后去解相应的阶梯形方程组.或者把线性方程组的增广矩阵经过初等行变换化成行简化阶梯形，从而可立即求出方程组的解.

消元法是求解低阶多元线性方程组的方法，此时线性方程组必须是适定方程组，一般是用于二元一次或三元一次方程组，当未知元增多时，计算效率低甚至无法求解.

3.2 克拉默法则

当系数行列式小为零时，适定方程组有唯一解，其解为：

其中D是系数行列式，D是在系数行列式基础之上结合方程组右边常数形成的新行列式.在此法则中，行列式的计算显得非常重要.利用行列式的性质计算行列式最为有效，对于二、三阶行列式可以利用对角线法则计算.

克拉默法则克服了消元法计算效率低甚至无法计算多元一次方程组的缺点，但是对于系数行列式等于零及欠定或者超定方程组的情况，它是无能为力的.事实上，当未知元数过多时，克拉默法则的计算效率就很低.

4. 线性方程组的解法在MATLAB中的实践

MATLAB语言是一种以矩阵运算为基础的计算语言，对于实现线性方程组的求解非常方便、对一个四元一次方程组的求解，可以用克拉默法则和逆阵乘积法来实现，程序如下：

其中克拉默法则用行列式除法Xi=det (Di)/det (D)来实现;逆阵乘积法用X=inv (D)*b来实现;det (D)是系数矩阵D的行列式运算;inv (D)是D的逆阵运算.

上例中，系数矩阵D不为零，可以用克拉默法则和逆阵乘积法来求解.当系数行列式为零时，只能用初等变换来求解.对于初等变换，利用阶梯生成函数命令rref也可以轻松地实现.

可见，MATLAB语言实现线性方程组的求解具有程序简单、直观的特点，同时还具有计算效率高的优点，在实际计算中摆脱了系数矩阵阶数未知元数等的限制.

5. 结语

本文首先介绍了一些线性组解法的历史，然后主要介绍了线性方程组的几种解法：消元法和克拉默法则.线性方程组是线性代数中一个最重要的内容，它除了本文介绍的几种解题的方法及应用外，还有很多其他的解题方法及更多广泛的应用.它是数学及其他理工科解题时必不可少的知识之一对线性方程组的解题方法及它的应用，也会一直不断地研究下去.

参考文献

[1]李尚志.线性代数[M].高等教育出版社.

[2]李排昌.矩阵与解线性方程组[J].中国人民公安大学学报, 2011.

[3]李桂荣, 韩忠月, 梁超.线性方程组的简便解法[J].德州学院学报, 2007.8, 第23卷 (第4期) .

[4]姬五胜.线性方程组解法及其MATLAB实践[J].天水师范学院学报, 2009.3, 第29卷 (第2期) .

病态线性方程组的粒子群算法篇7

关键词：粒子群算法,病态线性方程组,最优化

粒子群优化算法 (Particle Swarm Optimization, PSO) 最初是由Kennedy和Eberhart于1995年提出的一类基于智能的随机优化算法[1], 其思想来源于对鸟群捕食行为的研究, POS算法有着算法简单、容易实现, 并且可调参数等特点, 适用于求解大量非线性、不可微和多峰值的复杂优化问题。由于PSO算法的程序实现起来异常简洁, 需要调整的参数也少, 因而已应用于多个学科和工程领域[2]。

在图像恢复、带限信号外推、解卷积、模型参数估计、Fredholm第一类积分方程求解、地震勘探等许多领域, 都需要求解病态线性方程组。由于病态方程组的条件数很大, 数据误差和计算过程中引入的舍入误差使解不稳定, 即不管原始数据的误差多么小, 都可能造成解的很大变化, 使所得解严重失真;同时, 也使这类方程的求解变得相当困难[3]。

1 粒子群算法

粒子群优化算法 (Particle Swarm Optimization, PSO) 最初Ke nnedy和Eberhart[1]提出的, 源自于对鸟群捕食行为研究, 是一种迭代的优化算法。

粒子群优化算法 (POS) 首先在可行解空间中随机初始化m个粒子, 每一个粒子都对应着优化问题的一个解, 并且由目标函数确定一个适应值 (Fitness Value) 。每个粒子都在解空间中运动, 通常粒子将追随当前最优粒子而动, 并经过迭代逐步搜索, 最后得到最优解。在整个迭代搜索过程中, 粒子始终跟踪两个最优值, 一个是粒子本身迄今找到的最优解;另外一个为全体粒子迄今找到的最优解。在n维搜索空间中, 记第i个粒子当前的位置为xi= (xi1, xi2, L, xin) , 其速度为vi= (vi1, vi2, L, vin) , 粒子找到的个体历史最优位置为pi= (pi1, pi2, L, pin) , 全局最优位置为pg= (pg1, pg2, L, pgn) 。

个体历史最优位置ip是粒子本身的经验, 全局最优位置pg是粒子群的经验, 每个粒子位置就是按照这两个经验值更新。对于t+1次迭代, 每一个粒子按照下面两式进行更新变化:

d=, 12, L, D, D为解空间的维数, 即自变量的个数。加速常数c1, c2分别调节向pbest和gbest方向飞行的最大步长, 合适的c1, c2可以提升算法的寻优能力。但是各学者对c1, c2的确切取值观点还不尽一致, 一般情况下取c1=c2=.20。r1, r2是在范围[0, 1]内取值的随机实数。

个体最优位置pi是个体所搜寻到的最好的解, 每迭代一次之后, 粒子都会向新位置运动, 实现位置更新。这里需要有一个判定的过程, 也就是个体最优位置的更新过程:

在每一次迭代过程中, 由 (2) 产生一个新的解向量xi (t+) 1, 对该解向量进行评价, 并与个体最优位置的适应值进行比较, 如果当前的解向量较优, 则保存其为个体最优位置;如不是, 则个体最优位置保持不变。

有些时候可能会对粒子群优化算法的速度加以限制, 这样一定程度保证粒子不容易跳出解空间。vmax是常数, 限制了速度的最大值。粒子的速度被限制在一个范围内[-vmax, vmax]内, 即在速度更新后, 对粒子速度作以下限制:

通过这种速度的限制, 使速度保持在一个适中的水平, 有利于粒子群算法的局部搜索。

2 病态线性方程组的粒子群算法

考虑线性方程组:

即

其中, 矩阵A= (aij) n×n∈Rn×n, 向量x= (x1, x2, L, xn) T, 向量b= (b1, b2, L, nb) T。

设x、b和A的绝对误差分别为δx、δb和δA, 则x的相对误差估计如下[4]:

其中, cond (A) =Av⋅Av-1。表明若条件数cond (A) 很大时, A和b的微小变化都能引起解的巨大变化, 称其为病态线性方程组。

为了用粒子群优化算法求解线性方程组 (1) , 必须将方程组 (1) 的求解转化为一个优化问题来解决。通过变分原理, 方程组 (1) 的最优解问题等价于求解无约束优化问题:

下面给出粒子群算法求解线性方程组的步骤:

Step1:初始化粒子群 (速度和位置) 、惯性因子、加速常数、最大迭代次数和算法终止的最小允许误差。

Step2:利用适应度函数 (2) 评价每个粒子的初始适应值。

Step3:将初始适应值作为当前每个粒子的局部最优值, 并将各适应值对应的位置作为每个粒子的局部最优值所在的位置。

Step4:将最佳初始值作为当前全局最优值, 并将最优适应值对应的位置作为全局最优值所在的位置。

Step5:依据 (1) 更新每个粒子当前的飞行速度。

Step6:对每个粒子的飞行速度进行幅度处理, 使之不能超过设定的最大飞行速度。

Step7:依据 (2) 更新每个粒子当前所在的位置。

Step8:比较当前每个粒子的适应值是否比历史局部最优值好, 如果好, 则将当前粒子适应值作为粒子的局部最优值, 其对应的位置作为每个粒子的局部最优值所在位置。

Step9:在当前群中找出全局最优值, 并将当前全局最优值对应的位置作为粒子群全局最优值所在的位置。

Step10:重复 (step5) ～ (step9) , 直到满足设定的最小误差或者达到最大迭代次数。

Step11:输出粒子群全局最优值和其对应的位置以及每个粒子的局部最优值和其对应的位置。

3 数值试验

为了验证PSO算法求解病态线性方程的有效性, 本文以Hilber矩阵为系数矩阵的严重病态方程组为例, 考虑方程组:

其中H是n维Hilbert矩阵, 其元素满足, 从而病态方程组的精确解为

为了和文献[5]中提出的蚁群算法求解病态线性方程组的结果作对比, 本文取n=7。则方程组 (1) 的系数矩阵H的范数条件数为, 为严重病态问题。通过变分原理得到与 (1) 等价的最优问题:

选取粒子数60, c1=c2=20., ω=.0 6, 最大迭代次数为100000, 得到了满意的结果, 见表1, 表1还列出了文献[5]提出的蚁群算法及其他算法求得的结果, 比较发现, 本文提出的POS算法求解病态线性方程组, 方法稳定, 结果满意。

参考文献

[1]J.Kermedy, R.Eberhart.Partiele Swarm Optimization[A].In:Proeeedings of IEEE Iniernational Confereneeon Neural etworks[C].Piseataway:NJ:IEEECS, 1995:1942～1984.

[2]谢晓峰, 张文俊, 杨之廉, 等.粒子群算法综述[J].控制与决策, 2003, 18 (2) :129～134.

[3]殷福亮, 殷福新, 林淑云.解病态线性方程组的遗传算法[J].大连理工大学学报, 1994, 34 (6) :732～737.

[4]李庆扬, 关治, 白峰杉.数值计算原理[M].北京:清华大学出版社, 2000, 165～171.

[5]Duan Haibin, Wang Daobo, Zhu Jianqiang.Nobel method basedon ant colony optimization for soving ill-conditioned linearsystems of equations[J].Journal of Systems Engineering andElectronics, 2005, 16 (3) :606～610.

[6]郑洲顺, 黄光辉, 杨晓辉.求解病态线性方程组的混合算法[J].贵州工业大学学报, 2008, 37 (3) :12～15.

解析线性方程组中的若干问题篇8

关键词：列向量,行向量,线性相关,线性无关

线性代数是大学理、工、经济管理、医药、农业等学科必修的一门数学基础课, 是除算术外, 应用最为广泛的数学方法, 它是从初等数学到高等数学学习的桥梁, 对学生数学的学习起重要作用。线性代数在工农业生产实践中也有广泛应用, 如钢板受力后的变形, 大气的流场, 都可以用若干个微分方程来描述。通常对微分方程进行离散, 得到线性方程组, 再用数值方法求解。在试验数据处理和曲线拟合问题中, 在无法完全满足给定条件的情况下, 求一个比较接近的解, 最常用的方法是最小二乘法。然而对于一些比较小的线性方程组, 也可以通过MATLAB等数学软件求解。

一般线性方程表达为:

矩阵设为A

(*) 有零解⇔r (A) =r=n (未知量个数) 。

(*) 非零解⇔r (A) =r

特别地, 当s=n (即方程个数与未知量个数相等) 时, (*) 只有零解⇔|A|=|aij|n≠0, 即为Gramer法则的加强。

Gramer法则给出了一个用行列式解n×n线性方程组唯一解的方法。行列式的计算是在解线形方程组的基础上发展起来的。在实际计算过程中, 随着矩阵维数的升高, 行列式的计算是十分复杂的, 因此Gramer法则往往不被使用。然而Gramer法则却给出了求数值解的重要方法。

以上是大多教材给出的结论, 笔者可以继续探寻:设A是s×n的非零矩阵, 由Ax=0只有零解, 得a11x1+a12x2+...+a1nxn=0且x1=x2……=xn=0, 因此可以得到更进一步的结论:只有零解的充要条件是A的列向量线性无关。

进一步探究方程组有解与向量组之间的线性关系, 可通过举例来说明。

A是一个方阵, 有|A|=|aij|n=0, 方程组有非零解。

设α1= (1, 1, 3) Tα2= (1, -1, 1) Tα3= (-1, 1, -1) T为对应的列向量,

η1= (1, 1, -1) η2= (1, -1, 1) η3= (3, 1, -1) 为对应的行向量。

不难看出α2+α3=0, 2η1+η2=η3, 既列相关, 也行相关。即方程组有非零解且存在非独立的方程。