线性方程组数值解法

第二章 线性方程组的数值解法在科技、工程技术、社会经济等各个领域中很多问题常常归结到求解线性方程组。

例如电学中的网络问题，样条函数问题，构造求解微分方程的差分格式和工程力学中用有限元方法解连续介质力学问题，以及经济学中求解投入产出模型等都导致求解线性方程组。

n 阶线性方程组的一般形式为⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++nn nn n n n n n n b x a x a x a b x a x a x a b x a x a x a L K K K K L L 22112222212********* （1.1） 其矩阵形式为b Ax = （1.2） 其中⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=n n nn n n n n b b b b x x x x a a a a a a a a a A M M L K K K K L L 2121212222111211),,2,1,(n j i a ij L =，),,2,1(n i b i L =均为实数，i b 不全为0，且A 为非奇异。

关于线性方程组的数值解法一般分为两类：1．直接法 就是不考虑计算机过程中的舍入误差时，经有限次的四则运算得到方程组准确解的方法。

而实际中由于计算机字长的限制，舍入误差的存在和影响，这种算法也只能求得线性方程组的近似解。

本章将阐述这类算法中最基本的消去法及其某些变形。

这些方法主要用于求解低阶稠密系数矩阵方程组。

2．迭代法 从某个解的近似值出发，通过构造一个无穷序列，用某种极限过程去逐步逼近线性方程组的精确解的方法。

本章主要介绍迭代法与迭代法。

迭代法是解大型稀疏矩阵（矩阵阶数高而且零元素较多）的线性方程组的重要方法。

§1 高斯)(Gauss 消去法1.1 Gauss 消去法Gauss 消去法是将线性方程组化成等价的三角形方程组求解。

首先举例说明Gauss消去法的基本思想和过程。

1大学数学实验 实验报告 | 2014/4/5一、 实验目的1、学习用Matlab 软件数值求解线性代数方程组，对迭代法的收敛性和解的稳定性作初步分析；2、通过实例学习用线性代数方程组解决简化问题。

二、 实验内容项目一：种群的繁殖与稳定收获：种群的数量因繁殖而增加，因自然死亡而减少，对于人工饲养的种群（比如家畜）而言，为了保证稳定的收获，各个年龄的种群数量应维持不变。

种群因雌性个体的繁殖而改变，为方便起见以下种群数量均指其中的雌性。

种群年龄记作k=1,2,…,n ,当年年龄k 的种群数量记作x k ，繁殖率记作b k （每个雌性个体1年的繁殖的数量），自然存活率记作s k （s k =1−d k ，d k 为1年的死亡率），收获量记作ℎk ，则来年年龄k 的种群数量x ̌k 应该为x ̌k =∑b k n k=1x k , x ̌k+1=s k x k −ℎk , (k=1,2,…,n -1)。

要求各个年龄的种群数量每年维持不变就是要求使得x ̌k =x k , (k=1,2,…,n -1).(1) 如果b k , s k 已知，给定收获量ℎk ，建立求各个年龄的稳定种群数量x k 的模型（用矩阵、向量表示）.(2) 设n =5,b 1=b 2=b 5=0,b 3=5,b 4=3,s 1=s 4=0.4,s 2=s 3=0.6,如要求ℎ1~ℎ5为500,400,200,100,100，求x 1~x 5.(3) 要使ℎ1~ℎ5均为500，如何达到？问题分析：该问题属于简单的种群数量增长模型，在一定的条件（存活率，繁殖率等）下为使各年龄阶段的种群数量保持不变，各个年龄段的种群数量将会满足一定的要求，只要找到种群数量与各个参量之间的关系，建立起种群数量恒定的方程就可以求解出各年龄阶段的种群数量。

模型建立：根据题目中的信息，令x ̌k =x k ，得到方程组如下：{x ̌1=∑b k nk=1x k =x 1x ̌k+1=s k x k −ℎk =x k+1整理得到：{−x 1∑b k nk=1x k =0−x k+1+s k x k =ℎk2 大学数学实验 实验报告 | 2014/4/52写成系数矩阵的形式如下：A =[b 1−1b 2b 3s 1−100s 2−1…b n−1b n0000⋮⋱⋮000000000⋯00−10s n−1−1]令h =[0, ℎ1,ℎ2,ℎ3,…,ℎn−2,ℎn−1]Tx =[x n , x n−1,…,x 1]T则方程组化为矩阵形式：Ax =h ，即为所求模型。

第2章 线性方程组的数值解法2.1 引言在自然科学研究和工程技术的应用中，许多问题的解决，诸如非线性问题线性化、求微分方程的数值解最终都归结为线性方程组的求解问题. 我们在后面章节中的样条插值、曲线拟合、数值代数等，也需要求解线性方程组。

一般地，设n 阶线性方程组(linear system of equations of order n )为11112211211222221122,,,n n n n n n nn n n a x a x a x b a x a x a x b a x a x a x b +++=⎧⎪+++=⎪⎨⎪⎪+++=⎩ (2.1.1) 表示成矩阵形式=Ax b , (2.1.2)其中()111212122212n n ij n nn n nn a a a a a a a a a a ⨯⎡⎤⎢⎥⎢⎥==⎢⎥⎢⎥⎣⎦ A ，12n x x x ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦ x ，12n b b b ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦b , (2.1.3) A 为系数矩阵(coefficient matrix).目前在计算机上经常使用的、简单有效的线性方程组的数值解法大致分为两类：直接法(direct method)和迭代法(iterative method). 其中直接法适用于以稠密矩阵为系数矩阵的中低阶线性方程组，而迭代法主要用于求解以稀疏矩阵为系数矩阵的高阶线性方程组。

本章首先介绍解线性方程组的两种常用的直接法：Gauss 消去法与矩阵三角分解法；然后介绍解线性方程组的三种常用的迭代法：Jacobi 迭代法、Gauss-Seidel 迭代法、超松弛法(SOR 法)，并讨论它们的收敛性。

最后，讨论了线性方程组的性态。

2.2 Gauss 消去法Gauss 消去法（Gaussian elimination method ）的基本思想是使用初等行变换将方程组转化为一个同解的上三角形方程组，再通过回代，求出该三角形方程组的解.2.2.1 Gauss 消去法Gauss 消去法包括消元和回代两个过程. 下面先举例说明Gauss 消去法求解线性方程组的主要过程.例2.2.1 求解线性方程组123123123471,2581,3611 1.x x x x x x x x x ++=⎧⎪++=⎨⎪++=⎩ 解 将该线性方程组写成增广矩阵(augmented matrix)的形式1471258136111⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦用Gauss 消去法求解过程如下：1．消元过程12213323323214711471147125810361036136111061020020r r r r r r r r r -+→-+→-+→⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥−−−−→---−−−−→---⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥---⎣⎦⎣⎦⎣⎦,从而原方程组等价地变为上三角形方程组123233471,361,20.x x x x x x ++=⎧⎪--=-⎨⎪=⎩2．回代过程从第3 个方程解出30x =，将其代入第2 个方程得()2216/31/3x x =--+=，再将30x =及21/3x =回代到第1个方程，解出1231471/3x x x =--=-. 从而得到原方程组的解123113,0.x x x =-==对于一般线性方程组(2.1.1)，使用Gauss 消去法求解分为以下两步：1．消元过程为方便起见，记()(0)(0),ijn na ⨯==A A ()T(0)(0)(0)(0)1,12,1,1,,,n n n n a a a +++== b b ，则方程组(2.1.1)为()()()()()()()()()()()()000011112211,1000021122222,100001122,1,,.n n n n n n n n nn n n n a x a x a x a a x a x a x a a x a x a x a +++⎧+++=⎪+++=⎪⎨⎪⎪+++=⎩ (2.2.1) 第1次消元：若()0110a ≠，对方程组(2.2.1) 执行初等行变换11i i i r l r r -→, 2,3,,i n = ,得第1个导出方程组——————————————————————————高斯 (Carl Friedrich Gauss 1777年4月30 日 – 1855年2月23 ) 是德国数学家、天文学家，在许多科学领域都做出了杰出的贡献，他为现代数论、微分几何(曲面论)、误差理论等许多数学分支奠定了基础. 他的数学研究以简明、严谨、完美而著称于世. 他在数学上与阿基米德、牛顿和欧拉齐名，被称为“数学王子”，被公认为有史以来最伟大的数学家之一.()()()()()()()()()()000011112211,111122222,111122,1,,,n nn n n n n nn n n n a x a x a x a a x a x a a x a x a +++⎧+++=⎪⎪++=⎨⎪⎪++=⎩(2.2.2)其中()()1111/i i l a a =，()()()10011,2,3,,;2,3,, 1.ij ij i j a a l a i n j n =-==+第2次消元：若()1220a ≠，对方程组(2.2.2)执行初等行变换22,i i i r l r r -→ 3,4,,i n = ,得第2个导出方程组()()()()()()()()()()()()()()()0000011112213311,1111122223322,122233333,122233,1,,,,n nn n n n n nn n nn nn n a x a x a x a x a a x a x a x a a x a x a a x a x a ++++⎧++++=⎪⎪+++=⎪⎪++=⎨⎪⎪⎪++=⎪⎩(2.2.3)其中()()112222/i i l a a =，()()()21122,3,4,,;3,4,, 1.ij ij i j a a l a i n j n =-==+第k 次消元：若()10k kka -≠，对第1k -个导出方程组执行初等行变换i ik k i r l r r -→，1,2,,i k k n =++ , 得第k 个导出方程组()()()()()()()()()()()()()()()000001111221,1111,110112221,1122,11,111,1,1,11,1,,,,k k n nn k k n n n k k k k k k k n nk n k k k n k k nn n n n a x a x a x a x a a x a x a x a a x a x a a x a x a +++++++++++++++⎧+++++=⎪⎪++++=⎪⎪⎨++=⎪⎪⎪⎪++=⎩(2.2.4)其中()()11k k ik ikkkl a a --=，()()()11,k k k ij ij ik kj a a l a --=- 1,,;1,, 1.i k n j k n =+=++ 重复上述过程1n -次，得到第1n -个导出方程组()()()()()()()()()()()()()()0000011112213311,1111122223322,122233333,111,1,,,.n n n n n n n nn n n nn nn n a x a x a x a x a a x a x a x a a x a x a a x a +++--+⎧++++=⎪⎪+++=⎪⎪++=⎨⎪⎪⎪=⎪⎩(2.2.5)其中()()()()()1111,,1,2,,1;1,,;1,, 1.k k kk k ik ikkkij ijik kjl a a a a l a k n i k n j k n ----==-=-=+=++ (2.2.6)这样，通过消元过程就将方程组(2.1.1)化成了等价的上三角形方程组(2.2.5).2．回代过程回代过程就是求上三角形方程组(2.2.5)的解. 若()10n nna -≠，则从最后一个方程开始，先求出()()11,1,/n n n n n n n x a a --+=，再由第1n -个方程解出1n x -，依此类推可解出221,,,n x x x - . 一般(2.2.7)定义 2.2.1 由式(2.2.2)-(2.2.7)确定的求解线性方程组的算法称为Gauss 消去法(Gaussian elimination method)，包括消元(elimination)和回代(backward substitution)两个过程。

线性方程组的四种数值解法(电子科技大学物理电子学院，四川 成都 610054)摘要：本文介绍了四种求解线性方程组的数值解法: 雅克比迭代法、高斯赛德尔迭代法、高斯消去法和改进的平方根法的基本原理和算法流程，通过求解具体方程，对四种求解方法进行了对比。

对于雅克比迭代法和高斯赛德尔迭代法，研究了两种算法对求解同一方程组的迭代效率差异，结果表明高斯赛德尔迭代法达到同样精度所需迭代次数较少。

对于高斯消去法，通过选择列主元的方法提高算法的准确度，计算结果表明高斯消去法计算精确，且运算复杂度也不是很高。

对于改进的平方根法，其运算复杂度低，但对于给定的方程组有着严苛的要求。

关键词：雅克比迭代法；高斯赛德尔迭代法；高斯消去法；改进的平方根法；线性方程组引言线性方程组的求解在日常生活和科研中有着极其重要的应用，但在实际运算中，当矩阵的维数较高时，用初等方法求解的计算复杂度随维数的增长非常快，因此，用数值方法求解线性方程组的重要性便显现出来。

经典的求解线性方程组的方法一般分为两类：直接法和迭代法。

前者例如高斯消去法,改进的平方根法等，后者的例子包括雅克比迭代法，高斯赛德尔迭代法等。

这些方法的计算复杂度在可以接受的范围内，因此被广泛采用。

一般来说，直接法对于阶数比较低的方程组比较有效；而后者对于比较大的方程组更有效。

在实际计算中，几十万甚至几百万个未知数的方程组并不少见。

在这些情况下，迭代法有无可比拟的优势。

另外，使用迭代法可以根据不同的精度要求选择终止时间，因此比较灵活。

在问题特别大的时候，计算机内存可能无法容纳被操作的矩阵，这给直接法带来很大的挑战。

而对于迭代法，则可以将矩阵的某一部分读入内存进行操作，然后再操作另外部分。

本文使用上述四种算法求解对应的方程组，验证各种算法的精确度和计算速度。

1 算法介绍1.1 雅克比迭代法 1.1.1 算法理论设线性方程组(1)b Ax的系数矩阵A 可逆且主对角元素 均不为零,令并将A 分解成(2)从而(1)可写成令其中. (3)以B 1为迭代矩阵的迭代法(公式)(4)称为雅克比(Jacobi)迭代法(公式),用向量的分量来表示,(4)为(5)其中为初始向量.1.1.2 算法描述 1给定迭代初始向量X 0以及误差要求delta 2根据雅克比迭代公式计算出下一组向量3判断X 是否满足误差要求，即||X k+1 – X k || < delta4若误差满足要求，则停止迭代返回结果；若否，则返回第二步进行下一轮迭代1.2 高斯赛德尔迭代法nna ,...,a ,a 2211()nna ,...,a ,a diag D 2211=()D D A A +-=()b x A D Dx +-=11f x B x +=b D f ,A D I B 1111--=-=()()111f x B x k k +=+⎩⎨⎧[],...,,k ,n ,...,i x a ba xnij j )k (j j i iii)k (i21021111==∑-=≠=+()()()()()Tn x ,...x ,x x 002010=1.2.1 算法理论由雅克比迭代公式可知,在迭代的每一步计算过程中是用的全部分量来计算的所有分量,显然在计算第i 个分量时,已经计算出的最新分量没有被利用，从直观上看,最新计算出的分量可能比旧的分量要好些.因此，对这些最新计算出来的第次近似的分量加以利用,就得到所谓解方程组的高斯—塞德尔（Gauss-Seidel ）迭代法.把矩阵A 分解成(6)其中,分别为的主对角元除外的下三角和上三角部分,于是,方程组(1)便可以写成即其中(7)以为迭代矩阵构成的迭代法(公式)(8)称为高斯—塞德尔迭代法(公式),用变量表示的形式为(9)1.2.2 算法描述 1给定迭代初始向量X 0以及误差要求delta2根据高斯赛德尔迭代公式计算出下一组向量()k x ()1+k x ()1+k ix ()()1111+-+k i k x ,...,x 1+k()1+k x()1+k jx U L D A --=()nna ,...,a ,a diag D 2211=U ,L --A ()b Ux x L D +=-22f x B x +=()()b L D f ,U L D B 1212---=-=2B ()()221f x B x k k +=+⎩⎨⎧[],...,,k ,n ,,i x a x a b a xi j n i j )k (j ij )k (j ij i ii)k (i21021111111==∑∑--=-=+=++3判断X是否满足误差要求，即||X k+1– X k|| < delta4若误差满足要求，则停止迭代返回结果；若否，则返回第二步进行下一轮迭代1.3 高斯消去法1.3.1 算法理论下面三种变换称为初等行变换：1.对调两行；2.以数k≠0乘某一行中的所有元素；3.把某一行所有元素的k倍加到另一行对应的元素上去。

线性代数方程组的数值解法【实验目的】1. 学会用MATLAB 软件数值求解线性代数方程组，对迭代法的收敛性和解的稳定性作初步分析；2. 通过实例学习用线性代数方程组解决简化的实际问题。

【实验内容】【题目1】通过求解线性方程组A1x=b1和A2x=b2，理解条件数的意义和方程组的性态对解的影响。

其中A1是n阶范德蒙矩阵，即⎡1x0⎢1x1⎢A1=⎢⎢⎢⎣1xn-12x0x12 2xn-1n-1⎤ x0⎥ x1n-1⎥1,...,n-1 ，xk=1+0.1k，k=0,⎥ n-1⎥ xn-1⎥⎦A2是n阶希尔伯特矩阵，b1，b2分别是A1，A2的行和。

（1）编程构造A1（A2可直接用命令产生）和b1，b2；你能预先知道方程组A1x=和A2x=。

b2的解吗？令n=5，用左除命令求解（用预先知道的解可检验程序）b1（2）令n=5,7,9,…，计算A1，A2的条件数。

为观察它们是否病态，做以下试验：b1，b2不变，A1和A2的元素A1(n,n)，A2(n,n)分别加扰动ε后求解；A1和A2不变，b1，b2的分量b1(n)，分析A和b的微小扰动对解的影响。

b2(n)分别加扰动ε求解。

ε取10-1010，-8，10-6。

（3）经扰动得到的解记做x~，计算误差-x~x，与用条件数估计的误差相比较。

1.1构造A1，A2和b1，b2首先令n=5，构造出A1，A2和b1，b2。

首先运行以下程序，输出A1。

运行以下程序对A1,A2求行和：由于b1，b2分别是A1，A2的行和，所以可以预知x1=运行下列程序，用左除命令对b1，b2进行求解：得到以下结果： T。

x2=(1,1, ,1)1.2 计算条件数并观察是否为病态1.不加扰动，计算条件数。

运行以下程序：由此可知，A1，A2的条件数分别是3.574∗10, 4,766∗10。

2.b1，b2不变，A1(n,n)，A2(n,n)分别加扰动（1）n=5时设x11,x12,x13分别为A1添加扰动10−10，10−8,10−6后的解。