2.6 条件数与病态方程组

病态方程（ill-conditioned equation）是指一个数学方程在求解过程中，由于其系数矩阵的条件数非常大，导致求解过程不稳定，解的结果也容易受到误差的影响。

在Python中，可以使用NumPy库中的`cond()`函数来计算一个矩阵的条件数。

条件数的计算公式为：cond(A) = ||A|| * ||A^(-1)||，其中A是一个矩阵，A^(-1)是A的逆矩阵，||A||表示矩阵A 的范数。

以下是一个Python代码示例，演示如何计算一个矩阵的条件数：
```python
import numpy as np
# 定义一个矩阵A
A = np.array([[1, 2], [3, 4]])
# 计算矩阵A的条件数
cond_value = np.linalg.cond(A)
print("The condition number of matrix A is:", cond_value)
```
在这个例子中，我们定义了一个2x2的矩阵A，并使用`np.linalg.cond()`函数计算了矩阵A的条件数。

如果条件数非常大，说明这个方程是病态的。

对病态方程组的处理方法研究蓝醒龙（广西民族大学数学与计算机科学学院03数本2班，530006）摘 要： 对病态线性方程组解法研究是数值计算方法的一个重要研究课题。

本文分析了病态方程组的特点，介绍了几种有效的解法。

关键词： 病态线性方程组；条件数；预处理；迭代Studying The Algorithm For Solving Ill-conditionedSystem Of EquationsAbstract ： Studying the algorithm for solving ill-conditioned system of equations is an important issue. This paper analyses the equations characteristic, and introduces several effective algorithms.Key words ：ill-conditioned system of equations; condition number; pretreatment; iteration1 问题的提出一个线性方程组 A X b =，若右端向量b 或系数矩阵A 的微小变化就会引起方程组的解发生很大的变化，则称A X b =为病态方程组。

方程组的系数矩阵A 的条件数()1C o n d A AA -=刻画了方程组的性态，若()1C ond A ≥，则称A X b =为“病态”方程组；若()Cond A 相对较小，则称A X b =为“良态”方程组。

良态方程组用GAUSS 消去法和JACOBI 等简单的迭代法就可以得到比较好的计算解，而对于病态方程组，一般的直接法和迭代法会有较大的误差，甚至严重失真。

所以，在解方程组时，有必要先对方程组的性态进行研究，采用相应的算法，才能得到比较精确的计算解。

利用方程组的条件数来判断就是一个很好的办法。

病态线性代数方程组的求解理论的分析表明，求解病态的线性代数方程组是困难的。

考虑方程组Hx = b 的求解，其中H 为Hilbert 矩阵，n n ij h H ⨯=)(，11-+=j i h ij ，n j i ,...,2,1,=1. 估计Hilbert 矩阵2-条件数与阶数的关系；2. 选择问题的不同维数，分别用Gauss 消去法，Jacobi 迭代，GS 迭代和SOR 迭代求解，比较结果；3. 讨论病态问题求解的算法。

解： 1、取Hilbert 矩阵阶数最高分别为n=20和n=100。

采用Hilbert 矩阵的2-条件数作为实验的比较对象，画出的曲线如下图所示：lg(())n cond H n从图中可以看出，在n ≤13之前，图像接近直线，在n ＞13之后，图像趋于平缓，在一定的范围内上下波动。

为了比较图像的线性部分，作出一条直线与已知曲线进行比较。

比较直线的关系式为：833.1519.1))(lg(-=n H cond n ，结果下图所示。

nl g (c o n d (H n ))lg(cond(Hn))~n 关系图从图2中可以看出，当n 较小时，n H cond n ~))(lg(之间近似满足线性关系。

当n 继续增大到100时，n H cond n ~))(lg(关系图下图所示：从图中可以看出，图像的走势符合在n=20时的猜想，在n 大于一定的值之后，图像趋于平缓，且在一定范围内震荡，同时又有一定上升趋势，但上升速度很慢。

2、选择不同的阶数n ，设方程组的精确解为xz=(1,1,…,1)T进行计算，用四种方法解x_Guass1、x_Jacobi1、x_GS1、x_SOR1对比表如下nl g (c o n d (H n ))lg(cond(Hn))~n关系图nl g (c o n d (H n ))lg(cond(Hn))~n 关系图表所示。

Gauss 消去法求解：选择问题的阶数为3~8时，用Gauss 消去法求得的解与精确解一致，当阶数为9~14时，解开始出现偏差，而且n 越大，偏差越大。

第２章 线性代数方程组数值解法I ：直接法考虑方程组 b Ax = （n n R A ⨯∈非奇异,n R b ∈ 且0≠b ） (2．6.1) 设A 有误差 b A ,δ有误差b δ,则因此引起解x 有误差,即有扰动方程组 b b x x A A δδδ+=++))((现在来研究如何通过A δ和b δ对x δ的影响作出估计。

定理2．6.1 设 方程组(2.6．１)中b A ,分别有扰动A δ，b δ,因而解向量有误差x δ；又A δ足够小,使得 11<-A A ，则有误差估计式 )(111bbAAAAA A xxδδδδ+-≤--证明由 b x A x A x A δδδδδ=++))(()( ))(()(111x A A x A A b A x δδδδδ-----= 两边取范数有x A A x A A b A x δδδδδ111---++≤得到x A A b A x A A x δδδδδ111---+≤- )()1(11x A b A x A A δδδδ+≤--- 得到 )(111x A b AAA x δδδδ+-≤--又注意到b Ax =有 b x A ≥ 从而得到bA x ≤1，故上述不等式左边乘以x 1,右边圆括号第一项乘以x 1，第二项乘以bA ,并从括号中提出A ，则得（2.6．3) 定理的结果实际包含两种特殊情形: (1)A 精确，即 0=A δ,b 有扰动b δ，从而b b x x A δδ+=+)(bbAA xxδδ1-≤(2) A 有扰动A δ，b 精确，即0=b δ,这时b x x A A =++))((δδAAA AA A xxδδδ111---≤当A A δ1-很小时，上式可近似表示为AAAA xxδδ1-≈2.条件数与病态方程组定义 2．6.1 设A 为非奇异矩阵，称数A A 1- 即 A A A cond 1)(-= 为矩阵A 的条件数。

矩阵A 的条件数的一些基本性质: (1) 任何非奇异矩阵A ,对任一算子范数均有1)(≥A cond )()(1-=A cond A cond )()(A cond A cond =α(2) 根据定义 )(max 2A A A T λ= ，可得 )()()(min max 2212A A A A A AA cond T T λλ==-(3) 若 U 为正交阵,即I UU T =，则 1)(2=U cond又A 非奇异，则222)()()(UA cond AU cond A cond == (4）设 1λ与n λ为A 按模最大和最小的特征值，则nA cond λλ1)(≥特别地，若T A A =(即A 对称)，则nA cond λλ1)(=若A 对称正定，则 nA cond λλ12)(=证明 略定理 ２.6．2 (事后误差估计）设方程组 b Ax =,A 非奇异，0≠b ，x 是精确解,-x 是近似解,剩余向量 --=x A b r ，则有估计式 br A cond xx x b r A cond )()(1≤-≤-证明：因b Ax =，得 )(----=-=-=x x A x A Ax x A b r ，从而r A x x 1--=-,于是r A x x 1--≤-，又由bA x ≤1,于是得估计式右端br A cond bA rA xxx )(1=≤---类似地,由上述 )(--=x x A r ,得--≤x x A r ，或--≤x x Ar ，由 b A x 1-=得b A x 1-≤,综合两式得估计式两端xx x bA A r b r A cond ---≤≤1)(1例 2.６.1３．事后误差估计定理 2.6.2 设方程组b≠b,x是精确解,-xAx=,A非奇异,A非奇异，0是近似解,剩余向量-br,则有估计式=xA-例题讲解2例题２.1 对方程组Ａx ＝b, Ａ非奇异不一定能作顺序G ａuss 消去过程,或者说，A 非奇异不一定有LU 分解。

第16讲 追赶法、误差分析在实际应用问题中，经常会遇到解三对角线方程组。

例如：用三次样条函数的插值问题中得到的三转弯及三弯矩方程组，当时说可用追赶法来求解。

还有用差分法解二阶线性常微分方程边值问题，若用三点插值格式也得到解三对角线方程组，本节介绍该类方程组中的特例及该种方程组的解法：追赶法。

优点：1.计算量小。

2.方法简单，存贮量小。

3.数值稳定的（对舍入误差来说）。

1 追赶法三对角线方程组的一般表示方法：可见，对A 的分解只需求i i u l ,且按n n n l u l u l u l −→−−→−−→−−→−−→−−→−−→−--112211.....的递推过程进行，形象地称为“追”的过程⎩⎨⎧=-==-),....2(/)(/1111n i l y a f y l f y i i i i ⎩⎨⎧-=-==+)1,2,.....1(1n i x u y x y x i i i inn 形象地称回代求解过程为“赶”的过程追赶法的计算量为5n-4次乘除法，可用4个 一 维数组存放{}{}{}{}i i i i f c b a ,,,。

共占用4n-2个单元，在计算过程中{}{}{}i i i y u l ,,依次覆盖掉{}{}{}i i i f c b ,,最后，{}i x 覆盖掉{}i y ，所以，追赶法具有计算量小，占用内存单元少的特点。

2、误差分析⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=-n n l u u u U 121....111⎪⎪⎪⎪⎪⎪⎪⎪⎭⎫⎝⎛=n nl a l a l a l L ....33221)1,...,3,2,1(-=n i ⎪⎩⎪⎨⎧+===+++11111i i i i ii i lu a b u l c l b ⎪⎩⎪⎨⎧-===+++i i i i ii i ua b l l c u b l 11111/)1,...,3,2,1(-=n i病态方程组与条件数一个线性方程组Ax=b 是由它的系数矩阵A 和它的右端项b 所确定，在实际问题中，由于各种原因，A 或b 往往有误差，从而使得解也产生误差。

安徽工业大学数理科学与工程学院病态线性方程组的求解专业数学与应用数学班级数***班学号*******姓名 ***指导教师***二○一五年五月一、设计目的：为了更加透彻的熟悉数值分析课程，学习各种数学软件的使用，锻炼自己对知识的实际运用能力。

二、引言：用直接法求解AX=F 线性方程组,对于系数矩阵A 对角占优是很有效的。

方程阶数不高时,人们经常使用;而当方程组阶数大时,由于积累误差,导致结果失真。

为了克服误差积累问题,通常用迭代法。

它具有可达到所要求的精度和对计算内存要求不大的优点,对求解大型线性方程组,迭代法计算时间远比直接法少,所以在实际计算中,迭代法也被人们广泛使用。

然而迭代法要研究迭代格式的收敛性,如Jacobi 迭代对系数矩阵为病态矩阵不收敛,为此我们提供一种修改的Jacobi 迭代,并给出一些数值例子来说明有较好的效果。

三、解线性方程组迭代法的描述设线性方程组AX=P ，这里A:{a ij },X:{x i },F:{f i },1≤i,j ≤n,为了更广泛地应用，对A 只限制实的非奇异矩阵，那么，若给定初值x )0(,我们熟知的有: Jacobi 迭代:x )1(+k i=(f i -∑njk j ij x a )()/a ii j i ≠, 1≤i ≤n四、求解病态线性方程组的另一种迭代解法设线性方程BX=F, 这里系数矩阵B 是病态的，指的是矩阵条件数是较大的。

条件数越大，就越难求得准确解，为此，我们将方程的两端同加DX 项，那 么相应的Jacobi 迭代有：X ])([)()(1)1(k k X H D F A D -++=-+ (1)这里，A 为B 的对角阵，即A: {b ii },H:{b ij } j i ≠ 1≤i,j ≤n,记M= )()(1H D A D -+-，)()1()(k k k X X X -=∆+,那么有：)0()1()(X M X M X k k k ∆==∆=∆-Λ由此可见（1）式收敛，迭代矩阵M 的谱半径应满足p(M )<1，谱半径若用M 的特征值判断，则较为繁锁；若B 不可约，根据线性代数对角占优简单迭代必收敛的性质，为简单起见，我们取D 为对角线阵，即D: {d i },为保证收敛就得取d i =Sign{∑jii ij b b |,|}，符号Sign{a,b}的含义是与b 同号，数值取a,这是充分条件，实际计算中有时可放宽处理，比如可取d i =Sign{ii ij ijb b Max |,|}或者d i =Sign{ii ij jb b Max |,|} j i ≠，因而相应的Jacobi 迭代修改为：x )1(+k i =(f i -∑≠+ij k i i k j ij x d x b )()()/(b ii +d i ) （2）下面列举普通Jacobi 迭代不收敛，解不出正确结果，而用修改的Jacobi 迭代可求出满意结果的例子：例 1：A=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--211111112 F=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡--032 精确解为X=[]T 111---，普通Jacobi 迭代不收敛，取d i =Sign{ii ij ja a Max |,|} j i ≠， 1≤i,j ≤3用（2）式迭代40步，X=[]T000003.1000053.1000035.1---例 2：方程系数为Hilbert 阵H:{)1/(1-+=j i h ij } F:{∑=jij i h f } 1≤i,j ≤n精确解X=[]T 111Λ，普通Jacobi 迭代发散，取d i =Sign{∑jii ij h h |,|}用修改的（2）式迭代，n=1200时迭代10870步结果摘录如下：五、结论与问题以上数值试验表明该迭代算法对求解病态线性方程组是有效的，其优点是可达到预定的精度。

《数值计算方法》课程教学大纲一、课程基本信息二、课程教学目标数值计算方法是大规模科学模拟计算领域的一门重要的基础课，具有很强的应用性。

通过对本课程的学习及上机实习，使学生掌握掌握数值计算的基本概念、基本方法及其原理，培养应用计算机从事科学与工程计算的能力。

具体能力目标如下：具有应用计算机进行科学与工程计算的能力；具有算法设计和理论分析能力；熟练掌握并使用数学软件，处理海量数据，进行大型数值计算的能力。

三、教学学时分配《数值计算方法》课程理论教学学时分配表《数值计算方法》课程实验内容设置与教学要求一览表四、教学内容和教学要求第一章数值分析与科学计算引论（4学时）（一）教学要求1.了解误差的来源以及舍入误差、截断误差的定义；2.理解并掌握绝对误差、相对误差、误差限和有效数字的定义和相互关系；3.了解函数计算的误差估计，误差传播、积累带来的危害和提高计算稳定性的一般规律。

（二）教学重点与难点教学重点：误差理论的基本概念教学难点：误差限和有效数字的相互关系，误差在近似值运算中的传播（三）教学内容第一节数值分析的对象、作用与特点1．数学科学与数值分析2．计算数学与科学计算3. 计算方法与计算机4. 数值问题与算法第二节数值计算的误差1．误差的来源与分类2．误差与有效数字3. 数值运算的误差估计第三节误差定性分析与避免误差危害1．算法的数值稳定2．病态问题与条件数3. 避免误差危害第四节数值计算中算法设计的技术1．多项式求值的秦九韶算法2．迭代法与开方求值本章习题要点：要求学生完成作业10-15题。

其中概念题15%，证明题5%，计算题60%，上机题20%第二章插值法（12学时）（一）教学要求1.掌握插值多项式存在唯一性条件；2.熟练掌握Lagrange插值多项式及其余项表达式，掌握基函数及其性质；3.能熟练使用均差表和差分表构造Newton插值公式；4.能理解高次插值的不稳定性并熟练掌握各种分段插值中插值点和分段的对应关系；5.熟练掌握三次样条插值的条件并能构造第一和第二边界条件下的三次样条插值。