一 、 向量、矩阵范数

为了讨论线性方程组近似解的误差估计与研究解方程组迭代法的收敛性，需要在中引进向量序列(或矩阵序列)极限概念。为此，这就需要对量空间(或矩阵空间)元素的“大小”引进某种度量即向量范数(或矩阵范数)即距离的概念。

(一)向量范数：向量范数是中向量长度概念的推广。

定义8 (1)称为n维复向量空间。

称为复矩阵空间。

(2)设,称为x的共轭转置，称为A共轭转置矩阵。

在许多应用中，对向量的范数(对向量的“大小”的度量)都要求满足正定条件，齐次条件和三角不等式，下面给出向量范数的抽象定义。

定义9(向量范数)关于向量(或)的某个实值非负函数，如果满足下述条件

(1)正定性

(2)齐次性其中(或)

(3)三角不等式，称是上(或)一个向量范数(或为模)。

由三角不等式可推出不等式   (4) 

下面给出矩阵计算中一些常用向量范数。

定义10 设

(1)向量的“”范数

(2)向量的“1”范数  

(3)向量的“2”范数  

(4)向量的能量范数   设为对称正定阵

  称为向量的能量范数。

定理19 设(或)，则是上(或)的向量范数。

证明 只验证三角不等式：对任意，则

利用哥西不等式：，则有

定理20 (范数的等价性) 对任何则

(1) 

(2) 

(3) 

证 只证(1)。记

于是有(a) 

(b) 

(二)向量序列的极限

定义11 (向量序列的极限)设有向量序列及向量且记

如果个数列收敛，即

则称收敛于，记，

或说向量序列的收敛是分量收敛到对应分量。

例 设有向量序列

   显然，有

定义12 (距离)

设，称非负实数为之间距离，其中为向量的任何一种意义下范数。

定理21 设为中一向量序列，且，则

是(当)

其中为向量的任一范数。

证明 只对证明。显然有

又由范数的等价性定理有：

于是

(三)矩阵的范数

一个矩阵A可看作维向量空间中一个向量，于是由上向量“2”范数，可以引进中矩阵的一种范数。

称为A的 Frobenius范数。

定义13 (矩阵范数)关于矩阵的某个非负实值函数，如果满足下述条件：

(1)正定性： 

(2)齐次性： 

(3)三角不等式： 

则称是上的一个矩阵范数(或模)。

由于在许多应用问题中，矩阵和向量是相联系的，现引进一种矩阵的算子范数。它是由向量范数诱导出来的并且这种矩阵范数和向量范数是相容的，即不等式成立。

定义14 (矩阵的算子范数)设且设有一种向量范数相应的定义一个矩阵的非负函数

(最大比值),称为矩阵A的算子范数。

定理22 设是上的向量范数，则是上一个范数且满足相容条件：

(1) 

(2) 

证明 由定义,可知有

  或

下面验证三角不等式： 

由定义

由于

或

故

定理23 (矩阵范数公式)设，则

(1) (称为A的行范数)

(2) (称为A的列范数)

(3) (称为A的“2”范数)

其中为最大特征值。

证明 证(1)：记,

于是

说明，对任何向量，则有                      (a)

如果能找到一向量且使那末，定理得证。

下面来寻求使比值等于，记且使

于是， 

且由(a)式有

由此，应选取为： 

则及或

故

证(3)：由于为对称半正定矩阵，则特征值为非负，即记特征值为，则有

且有满足,

考查比值：且，于是

说明，对任何非零向量，则有

另一方面，取则有

故

定理24 (矩阵范数等价性)设，则

(1);(2) 

定义25 (矩阵的谱半径)设的特征值为，称

为A的谱半径。

定理25 (特征值界)

(1)设，则，其中为满足矩阵，向量相容性条件的矩阵范数。

(2)设为对称矩阵，则。

证明 只证(1)。

设为A的任一特征值，于是，存在使

且

即  

定理26 设为矩阵的算子范数，且，则为非奇异矩阵，且有估计

证明 1)反证法。

设为奇异阵，则有非零解记为，即

于是，由此，有，这与假设矛盾。

2)由

即得

从而

二 、 矩阵的条件数、病态方程组

直接法的误差原因：1．算法及舍入原因

2．方程组本身固有的问题

要分析方程组的状态并估计算法的误差（原始数据扰动对解的影响）——量度：矩阵的条件数

【引例】设方程组,精确解为.

a=[1 1;1 1.0001];b=[2,2]';a\\b  

对右端项作微小变化(小扰动)：

  其中

a=[1 1;1 1.0001];b=[2,2.0001]';a\\b  

显然有, 

【说明】右端常数项的相对误差

而引起解的相对误差

常数项的微小误差引起解的相对误差较大,扩大了倍,也就是说,此方程组解对方程组的数据A,b非常敏感,这样的方程组就是病态方程组.

设线性方程组为

Ax=b                     …………………（1）

其中A∈Rn×n,x,b∈Rn且A非奇异。x*：准确解，δx：解的误差，即

                              …………………（2）

δA--A的误差，δb--b的误差。讨论δx与δA，δb的关系

(一) b有误差而A无误差情形

将带有误差的右端项和带误差的解向量代入方程组，则

              …………………（3）

由于，而得到  ,    从而

另一方面，由(1)式取范数，有

可得

【定理27】设A是非奇异矩阵，Ax=b≠0,且A（x*+δx）=b+δb则有误差估计式

                    …………………（4）

其中称为方阵A的条件数。

说明：1、解的相对误差是右端项b的相对误差的cond(A)倍

2、如果条件数很大，则解的误差将成倍增长。

【定义】称条件数很大的矩阵为“病态”矩阵；称病态矩阵对应的方程组为病态方程组。反之，则称A为良态矩阵。

(二) A及b都有误差的情形

【定理28】   

设在方程组Ax=b中，A及b都有误差，且，则有

证：带有误差的方程组为

            …………………（5）

由于，因而

                …………………（6）

为从（6）式中解出δx，必须限定（A+δA）-1存在。从而

                 …………………（7）

利用，得到

      …………………（8）

又由定理26知，当时

     …………………（9）

对（7）式取范数，并由（8）、（9）式得到

………………（10）

从而由及（10）式，有

            ……………（11）

【注】仅A或b有误差是（11）式中δb=0或δA=0的特例。

(三) 常用的条件数及其性质

1.当A=AT时，;

2.当A对称正定时， 

3.对非奇异矩阵A,cond(A)≥1,

cond(A)=cond(A-1),cond(cA)=cond(A)(c≠0,c∈R)

4.若U为正交矩阵，即UTU=I，则   cond(U)2=1

对非奇异矩阵A,cond(A)2=cond(UA)2=cond(AU)2

(四) 病态方程组

病态方程组的判别设Ax=b，A∈Rn×n,且A非奇异

当cond(A)>>1,则Ax=b是病态方程组（坏条件的，A是病态的）

当cond(A)相对较小时,则Ax=b是良态方程组（好条件的，A是良态的）

【例】在引例方程组中，b有扰动=(0，0.0001)T ，试计算 cond(A)∞，并说明对解向量x的影响。

a=[1 1;1 1.0001];b=[2;2];

norm_b=norm(b,inf);

detb=[0;0.0001];norm_detb=norm(detb,inf);

err_b=norm_detb/norm_b

cond_a=cond(a,inf)

err_x=err_b*cond_a  

【例】希尔伯特矩阵的条件数:

cond(hilb(2)),cond(hilb(3)),cond(hilb(5)),cond(hilb(8))  

a=hilb(3),b=ones(3,1);a\\b  

a =[1.0000    0.5000    0.3333;

    0.5000    0.3333    0.2500;

    0.3333    0.2500    0.2000+0.000001];b=ones(3,1);a\\b  

【注】(1)由矩阵条件数性质可知，正交矩阵的线性方程组是好条件的;

(2)条件数性质4指出，正交变换保持条件数不变，这说明在很多方法中使用正交矩阵约化矩阵的合理性。

设有方程组，其中为非奇异，为精确解，又设为计算解。一般，计算剩余向量，用大小来检验计算解的精度，是否很小，就是一个较好的近似解呢？

【定理29】 (事后误差估计)

(1)设A为非奇异矩阵，x是精确解，即。

(2)设是方程组一个近似解，，则近似解的相对误差有估计式

证明     由

所以                              ……………(12)

另一方面，由，有

    即                    ……………(13)

由(12)及(13)式，则  

说明  近似解精度(误差界)不仅依赖于剩余“大小”，而且依赖于A的条件数，当A是病态时，即使有很小的剩余，也不能保证是高精度的近似解。

三、 关于病态方程组的解法,非奇异矩阵

(一) 判断是病态方程组

(1) 当A的行列式相对来说很小,或A某些行(或列)近似线性相关,方程组可能病态.

(2) 如果用选主元消去法求解,在A约化中出现小主元,方程组可能病态.

(3) 当系数矩阵A元素数量级相差很大,并且无一定规则时,方程组可能病态.

(4) 估计条件数.由于,所以发现病态的可靠方法是计算A的条件数,若直接计算再计算,那末求大约需要次乘法运算,为求解(用直接法)计算量的3倍,代价太高.

一个矩阵条件数的估计方法:由于

(令,由解求)

因此

选择向量且求解使产生大的解.于是

【注】方法成功的关键在于怎样使比值接近它的极大值

(二) 病态方程组的解法

对于病态方程组,当我们用一般方法求解时,仅由舍入而产生的误差也会使我们算不出比较满意的解,此时可采用下述方法求解.

1  采用高精度的算术运算

例如,采用双倍字长进行运算,或用双字长求内积等,以此改善和减轻矩阵病态的影响,其缺点是计算时间将大为增加.

2  采用预处理方法

求解求解:寻求非异矩阵P,Q使

或其中且改善A的条件数,

于是,可用数值稳定方法求解,再求,当A为对称正定阵时,一般选择P,Q为对角阵或三角矩阵.

3  平衡方法

当系数矩阵A元素数量级差别很大,威尔金森提出采用行均衡方法,这时矩阵A条件数可能得到改善.

行(或列)均衡: 就是解方程组之前首先将A的行(或列)大体均衡一下,即对每一行(或每一列)乘以适当的数,使所有行(列)按照某种范数大体上有相同的长度.

设,其中为非奇异阵.计算

令

于是求解求解或.

这时条件数可能得到改善,再用列主元消去法或部分选主元三角分解法求解.

例 设有方程组

或,计算.

解  计算

于是

行平衡:

对A每一行计算.

即,求解.记

或且

所以,说明为良态方程组.

用列主元消去法求解(且3位浮点数进行计算)可得计算解(是较好的近似解).

4  迭代改善法

设,其中为非奇异矩阵且为病态.如果其中为机器基数, 计算机字长,就说A对于机器的精度来说是病态的,现假设.

首先用选主元三角分解法实现分解

其中P为置换阵,L为单位下三角阵,U为上三角阵且得到计算解,将按下述方法改善近似解的精度.

(1)  计算剩余向量                   ……………(14)

(2)  求解记解为                     ……………(15)

(3)  改善                           ……………(16)

如果(14),(15),(16)计算没有误差,则就是的精确解.

可验证,即

但是,在实际计算中,由于有舍入误差,只是近似解,重复(14)～(16)过程,就得到一近似解序列.下载本文