几个问题在最近的博客文章评论促使我讨论矩阵的条件数。

在评论我的帖子对希尔伯特矩阵,一个名叫米歇尔读者问道:

在评论我的帖子大约四倍精度,马克问道:

简短的回答是错误估计是很少紧张,但这是不可能找到一个更好的,这需要相同的时间解决坏心肠的线性方程是解决状态良好的系统。

内容

条件数的反演

我应该首先指出数字,有许多不同的条件,尽管提问者可能没有意识到,他们询问只是其中之一——反转的条件数。一般来说,条件数不仅适用于一个特定的矩阵,但也要解决的问题。我们是反相矩阵,找到其特征值,或计算指数吗?的例子不胜枚举。一个矩阵可以为反演条件差而特征值问题是条件。或者,反之亦然。

一个矩阵的条件数和计算任务答案是衡量敏感扰动输入数据和解决方案过程中舍入错误了。

当我们只是说一个矩阵是“坏脾气的”,我们通常只是考虑它的逆矩阵的敏感性,而不是所有的其他条件。

规范

为了使这些概念更精确,让我们先从一个向量规范。具体来说,欧几里得范数或2 -规范。

$ $ x \ | \ = \ \ | (\ sum_i x_i ^ 2) ^ {5} $ $

这是“笔直地”的距离n维空间。

一个矩阵的相应规范措施多少美元美元的映射矩阵可以拉伸引起的向量。

$ $ M \ = \ \ | \ | \ = \{\马克斯{{\ | Ax \ |} \ / {x \ \ | |}}} $ $

有时也很重要考虑向量矩阵能缩小多少。

$ $ m \ = \{\分钟{{\ | Ax \ |} \ / {x \ \ | |}}} $ $

最低的倒数逆的伸展是常态,因为

$ $ m \ = \{\分钟{{\ | Ax \ |} \ / {x \ \ | |}}} \ = \{\分钟{{y \ \ | |} \ / {\ | ^ y \ |}{1}}} \ = \ 1 /{\马克斯{{\ | ^ y \ |}{1}在{\ \ | | y}} \} \ = \ 1 / \ | ^ {1} \ | $ $

一个单数矩阵是一个非零向量映射到零向量。对于一个奇异矩阵

$ $ $ $ m \ = \ 0

和逆不存在。

的比例最大,最小拉伸是反转的条件数。

$ $ \卡帕(A) \ = \ {{M} \ / {M}} $ $

一个等价的定义是

$ $ \卡帕(A) \ = \ \ | \ \ | | ^ {1} \ | $ $

如果一个矩阵是奇异的,那么其条件数是无限的。

线性方程

条件数\卡帕(A)美元是参与这个问题的答案:多少可以改变系统的右手边的线性方程组影响解决方案?考虑一个方程组

$ $ $ $ x \ = \ b

和第二个系统通过改变右边

$ $ (x + \δx) = b + \δb $ $

认为\δb美元是b和美元的误差\δx美元作为x美元产生的错误,虽然我们不需要做任何假设的错误很小。因为美元(\δx) = \δb美元,M和M美元美元的定义立即导致

$ $ \ b \ | | \ leq M \ \ | $ $ | x

和

$ $ \ | \δb \ \ | | \组米\δx \ | $ $

因此,如果m \ neq 0美元,

$ ${\ | \δx \ | \ / \ \ | | x} \ leq \卡帕(A)δb {\ | \ \ | \ \ | b \ |} $ $

量δb美元\ | \ \ | / \ \ | | b是一美元相对右边的变化,和数量\ | \ \ |δx美元/ x \ \ | | $是结果相对变化的解决方案。使用相对变化是他们的优势无量纲的推荐- - - - - -他们不受总体规模的影响因素。

这个不等式条件表明,数量是一个相对误差放大倍数。右边的变化会引起变化\卡帕(A)倍美元的解决方案。

例子

让我们调查一个线性方程组

左($ $ = \ \{数组}{cc}开始4.1 & 2.8 \ \ 9.7 & 6.6 \结束数组{}\右)$ $

把b美元美元美元的第一列,所以解决Ax = b是美元

开始左($ $ x = \ \{数组}{c} 1 \ \ 0 \结束数组{}\右)$ $

切换到MATLAB

= (4.1 - 2.8;9.7 - 6.6]b = (: 1) x = A \ b

A = 4.1000 2.8000 9.7000 6.6000 = 4.1000 9.7000 x = 1.0000 - -0.0000

现在添加0.01第一个组成部分b。

b2 = (4.11;9.7)

b2 = 4.1100 - 9.7000

解决方案变化显著。

x2 = \ b2

x2 = 0.3400 - 0.9700

这个解决方案的敏感性x右手边的变化b是一种条件反射。

kappa =电导率(A)

k = 1.6230 e + 03

的上限可能的变化x显示所有的有效数字的变化。

kappa *规范(b-b2) /规范(b)

ans = 1.5412

实际的变化x这个扰动是造成

规范(x x2) /规范(x)

ans = 1.1732

所以这个特殊的改变在右手边生成几乎最大的可能变化的解决方案。

接近奇异

大条件数意味着矩阵接近奇异。让我们做一个小改变的第二行一个。

A2 = [4.1 - 2.8;9.676 - 6.608)

一个= 4.1000 = 4.1000 2.8000 9.6760 6.6080 2.8000 9.7000 6.6000 A2

由此产生的矩阵是奇异。如果我们试图计算它的逆矩阵,我们得到一个警告消息。

A2inv =发票(A2)

警告:矩阵接近奇异或严重了。结果可能是不准确的。RCOND = 1.988677 e-17。A2inv = 1.0 e + 15 * -1.4812 0.6276 2.1689 -0.9190

的数量RCOND警告是估计的条件数的倒数。使用互惠是遗留下来的前几天,我们有IEEE浮点运算正代表溢出和无穷。对于这个示例RCOND的顺序每股收益(1)和比例因子A2inv意味着它的元素是无用的。这是不可能的计算不存在的东西。

一个相当最近除了MATLAB函数气孔导度估计\卡帕(A)美元。现在康德(A)比1 / rcond (A)。

逆

条件数\卡帕(A)也出现在美元开往多少改变E矩阵一美元美元可以影响它的逆矩阵。

$ $ {{\ | (A + E) ^ {1} - ^ {1} \ |} \ / {\ | ^ {1} \ |}} \ \ le \ \卡帕(A) {{\ \ | | E}在{\ | \ |}}\ $ $

吉姆·威尔金森的工作对高斯消去法表明,舍入误差计算逆矩阵的每一列一列的逆矩阵在给定矩阵的舍入误差。让我们回避这一点,说发票(一个)计算的确切逆+ E,美元\ \ | | E是美元的舍入误差相对于美元\ \ | $ |。

我们不知道E美元,但对于一个n——- - - - - -n矩阵的估计

规范(E)美元$ \大约\空间n * eps(规范(A))

我们有一个简单的估计误差计算逆,相对于未知的完全相反。

X =\空间的逆美元一个

Z =发票(A)

规范(Z - X) /规范(X)$ \大约$n * eps *电导率(一个)

为我们2×2例估计的相对误差计算逆

2 * eps * conde(一个)

ans = 9.9893 e-13

这表示我们可以期待12或13(16)有效数字。

威尔金森不得不假设每个浮点算术运算带来最大的舍入误差。但是只有一小部分的操作有舍入误差,甚至对于那些错误小于最大可能。这估计会高估。但没有严格估计是可能的。

对于我们的示例,计算逆

格式长Z =发票(A)

Z = -66.000000000000057 28.000000000000025 97.000000000000085 -41.000000000000036

事实证明完全相反的由整数条目

X =圆(Z)

X = -66 28 97 -41

我们可以比较实际的相对误差的估计。

格式短规范(Z - X) /规范(X)

ans = 8.7342 e-16

所以我们有超过15个有效数字的准确性。

速度

在简化的轮廓,计算$ n的逆的算法——- n矩阵美元,美元或求解n美元线性方程组,包括循环长度n嵌套三美元。每个访问元素n ^ 2美元美元$ n倍。因此,计算复杂度成正比n ^ 3美元。很多事情可以做,影响比例系数,但它仍然是n ^ 3美元。

实际的数字矩阵(通常)不影响执行时间。近奇异矩阵可以作为一个状态良好的倒也一样快。答案可能不是非常准确的,如果条件数很大,但\卡帕(A)美元并不发挥作用的速度。

得到了MATLAB代码

发表与MATLAB®R2017a