河海大学研究生数值分析课件

数值分析

编者李庆扬等

课件董祖引

Ch1绪论1.1数值分析研究对象与特点

科学技术领域的三大环节：（1）实验；（2）科学计算；（3）理论。

所谓的科学计算是指使用计算机进行数值计算的工作，它可以部分地替代科学实验。科学计算的主要过程：实际问题数学模型数值计算方法程序设计上机计算求出结果

其中数值计算方法是数值分析研究的对象。主要包括：（1）函数的数值逼近（包括插值法）；

（2）数值微分和数值积分；

（3）非线性方程（组）数值解；

（4）数值线性代数（如线性方程组数值解、矩阵特征值特征向量的计算）；

（5）（偏）微分方程数值解。数值分析的主要特点：（1）可行性；（2）时效性；（3）可靠性；（4）实验性。1.2数值计算的误差

误差的来源与分类：（1）模型误差；（2）观察误差；（3）截断误差（也称方法误差）；例如：其截断误差：

（4）舍入误差（包括由十进制转换为二进制引起的误差）。例如：其舍入误差：绝对误差：其中是的一个近似值。（绝对）误差限：并记：相对误差：实际计算中通常用相对误差限：

若近似值的误差限是某一位的半个单位，就说“精确”到这一位。

若该位到的第一位非零数字共有n位，就说有n位有效数字。

它可表示为：

例1

按四舍五入原则下列各数：187.9325，0.03785551，8.000033，2.7182818，2/3具有5位有效数字的近似值分别为：187.93，0.037856，8.0000，2.7183，0.66667定理1

设近似数表示为：若具有n位有效数字，则相对误差限至少具有n位有效数字。反之，若的相对误差限，则（证明见黑板）

例2

要使的近似值的相对误差限小于0.1%，要取几位有效数字。（见黑板）

以、记、的绝对误差限，则一般的，利用Taylor展式，有

例3

测量得某场地长l的值为m，宽d

的值为m，试求面积s=ld的绝对误差限与相对误差限。（见黑板）1.3误差定性分析与避免误差危害

一般的，误差的定量分析是困难的，我们考虑下列三各方面的定性分析。（1）病态问题与条件数。

若输入数据有微小扰动（即误差），引起输出数据（即问题的解）相对误差很大，则称为病态问题。

病态程度可用相对误差比值来描述，如：并称为计算函数值问题的条件数。

例如，，则。它表示相对误差大约放大n倍。(2)算法的数值稳定性。

一个算法如果输入数据有误差，而在计算过程中舍入误差不增长，则称此算法是数值稳定的。比如，page9例5的A算法是数值不稳定的，B算法是稳定的。(3)避免误差危害的若干原则。1.避免小数作除数。2.避免两相近数相减。

例4

利用中心差商公式计算在处的导数值。（详见黑板）3.防止大数“吃”小数。4.简化计算步骤，减少运算次数。

例5

计算多项式的值。

直接计算共需要做次乘法和n次加法。若用秦九韶算法只要n次乘法和n次加法即可。Ch2插值法2.1引言

设在区间上有意义，且已知在点上的值若存在简单函数，使得

插值区间。则称是的插值函数。点称为

插值节点。其他点称为插值点。称为

若是次数不超过n的多项式，即则称为插值多项式。相应的方法称为多项式插值。

若是分段多项式，则称分段多项式插值。

常用的有拉格朗日插值、牛顿插值、埃尔米特插值、埃特金插值、三次样条插值等。2.2拉格朗日插值定义1

若n次多项式在n+1个节点上满足则称为节点上的n次（拉格朗日）插值基函数。

注意：它与无关。

事实上，拉格朗日插值基函数令则满足：称为拉格朗日插值多项式。

特别的，当n=1，称线性插值。当n=2，称抛物插值二次插值。

若引入记号则拉格朗日插值多项式可写成如下的紧凑形式：例1

已知的观察值数据x01320-4求的二次插值。（见黑板）

定理1

满足插值条件的n次插值多项式是存在唯一的。

证明只要证明唯一性。

假设还有次数不超过n的多项式满足则这与代数基本定理（n次多项式至多有n个零点）矛盾。特别的，若令则得又若则

关于截断误差，也称拉格朗日插值余项，我们有

定理2

设在上连续，在内存在，则，有（证明见黑板）若，则截断误差限

例2

已给sin0.32=0.314567，sin0.34=0.333487，sin0.36=0.352274，试用抛物插值计算sin0.3367，并估计截断误差。（见黑板）

一般说来，不易求得，可用下述的误差的事后估计法。（详见黑板）

最后，关于插值多项式的数值计算的稳定性，我们有结论：

（1）线性插值数值计算是稳定的；（2）高次（非线性）插值数值计算是不稳定的。（详见黑板）2.3均差与牛顿插值公式

牛顿插值法的思想是将插值多项式表写成

其中为待定系数，

可由插值条件确定。它们正好是下述定义的均差。

定义2

称为关于点的一阶均差；称为的二阶均差；一般的，称为的k阶均差。

利用归纳法可以证明：均差具有如下基本性质：

（1）（对称性）均差与节点的排序无关，即（2）

（3）若在上存在n阶导数，则（证明略）

具体计算时可列均差表（详见黑板）。

根据均差的定义，并把x看作上一点，则将后式代入前式，即得其中显然满足插值条件，称为牛顿（均差）插值多项式。插值余项

注意：根据插值多项式的存在唯一性定理，牛顿插值与拉格朗日插值结果（包括余项）是一致的，只是形式不同而已。

与拉格朗日插值比较，牛顿插值计算量省，且便于程序设计。在增加节点时牛顿插值是很方便的。（算例见page34，略）2.5埃尔米特插值

埃尔米特插值不仅要求节点处函数值相等，且对应的导数（甚至高阶导数）值也相等。具体地，设

要求次数不超过2n+1的插值多项式，使得

仿照拉格朗日插值，令

其中，是量组基函数，为2n+1次，且满足

利用拉格朗日插值基函数可求出。（详见黑板）

容易证明，埃尔米特插值多项式是唯一的，且余项为

实际常用两点三次埃尔米特插值（即n=1），用矩阵表示为其中，，。

对于节点比较多时，可分段三次埃尔米特插值。（略，详见50）例3

求满足的插值多项式，及余项表达式。（见黑板）

例4

设是Hermite插值基函数，证明：（见黑板）2.6分段低次插值

高次插值有时会发生所谓的龙格(Runge)现象。例如在上解析。在[-5,5]上取n+1个等距节点作Lagrange插值龙格证明了，当时，只在时，当时，发散。（如图，见黑板）

鉴于此，实际上很少使用6、7次以上插值。可用分段低次插值。下面只介绍最简单的分段线性插值，和分段Hermite插值。

从几何上看，分段线性插值就是依次连接节点的折线。

设节点上的函数值为。记，求折线函数：在每个小区间上是线性函数则称是分段线性插值函数。易知且有误差估计其中，（由Lagrange插值余项可得）以及其中，（由page59习题5的结果可得）

可以证明，当时，在上一致收敛到。（详见page48）

如果还知道节点处的导数值可构造一个导数连续的分段插值函数，满足在每个小区间上是次数不超过三次的多项式。

上述称为分段三次Hermite多项式。它的具体表达式为（由5.10，5.8，5.9）可以证明，从而有

定理3

设，则当时，在上一致收敛到。2.7三次样条插值（简介）

工程制图中，把富有弹性的细木条（样条）用压铁固定在样点上，在其他地方让它自由弯曲，所成曲线称为样条曲线。数学上，定义如下：

定义4

若函数，且在每个小区间上是次数不超过三次的多项式，其中，是给定节点，则称是以为节点的三次样条函数。若在节点上还满足则称是的三次样条插值函数。例4

判断下列函数是否为三次样条函数：

注意，要确定定义4中的三次样条插值函数，还需要加上边界条件，如：或：等。

要求出，在每个小区间上的要确定4个待定系数，共4n个参数。

在节点处还要满足连续性（光滑性）条件：共有3(n-1)个条件。再满足共有4n-2个条件。还需要2个条件，通常在区间端点上各加一个（边界）条件，常见的有3种：特别的，（自然边界条件）

（3）当是以为周期的周期函数时，要求也是周期函数。边界满足：但此时，，并称此时的为周期样条函数。

根据上述条件，利用分段三次Hermite插值(此处假定)可得关于的一个三对角线性方程组（具体过程略，见54）。转化为(7.8)式。可用追赶法解之。

关于它的误差界与收敛性，见定理4（page57），效果极佳。Ch3函数逼近与快速傅里叶变换3.1基本概念及预备知识线性空间，基，维数。如（n维向量空间）（次数不超过n的多项式空间，n+1维）（区间[a，b]上连续函数空间，无限维）定理1

（Weierstrass定理）设，则即在[a，b]上一致成立。伯恩斯坦多项式（1912年给出）

其中满足Weierstrass定理要求，但收敛很慢。此外，以及

定义2

设S线性空间，，定义一实值函数，它满足：等号成立当且仅当则称是S上的范数。S与称赋范线性空间。中常用范数

（-范数，最大范数）

（1-范数）

（2-范数）中常用范数

定义3

设X是数域K（R或C）上的线性空间，，定义内积满足：等号成立当且仅当X连同称为内积空间。若，称u，v正交。定理2

（Cauchy-Schwarz定理）

定理3

设（内积空间），则Gram矩阵非奇异的充要条件是线性无关。（证明见黑板）由内积可诱导出一个范数：

例1

的内积诱导出2-范数加权内积对应导出范数中的内积

定义4

设[a，b]（可以是无限）上的非负函数满足：（1）存在有限；（2）对[a，b]上的非负连续函数，若有则称为[a，b]上的一个权函数。例2C[a，b]上内积

导出范数当，则3.2正交多项式

定义5

若

则称在[a，b]上带权正交。若函数族满足：

则称是[a，b]上带权的正交函数族。又若，则称为标准正交函数族。三角函数族：1，cosx，sinx，cos2x，sin2x，……是上的正交函数族。

特别的，当是n次多项式时，则称是[a，b]上带权的n次正交多项式。对于利用Schmidt正交化构造正交多项式这里的满足：（1）是首一的n次多项式。（2）任一n次多项式均可表为

（3）当时，，且与任一次数小于k的多项式正交。（4）递推公式其中（证明略）

（5）[a，b]上带权正交多项式在（a，b）内恰有n个不同实根。（证明略）

特别的，取[a，b]=[-1，1]，，则上述称勒让德多项式，记，用导数可表示为（1814年由罗德利克给出）注意，它不是首一的，首一的Legendre多项式~Legendre多项式具有下列性质：（1）正交性：

（证明见page72）（2）奇偶性：（3）递推关系：（证明见黑板）（4）在[-1，1]内有n个不同实零点。利用递推关系可得：

取，此时正交化得到的称为切比雪夫（Chebyshev）多项式。切比雪夫多项式用三角函数表为（不是首一的）：切比雪夫多项式满足：（5）递推关系：事实上，

由此可得，（6）在[-1，1]上带权正交，且事实上，令

（7）只含x的偶次幂，只含x的奇次幂。

（8）在[-1，1]上的n个零点为实用上，可用表示为还有其他正交多项式：1、第二类切比雪夫多项式取令第二类切比雪夫多项式具有递推公式：2、拉盖尔多项式取区间，权函数。递推公式：3、埃尔米特多项式取区间，权函数。递推公式：3.3最佳一致逼近多项式设，求s.t.这就是最佳一致逼近或切比雪夫逼近问题。

定义7

设称为与在[a，b]上的偏差。称为在[a，b]上的最小偏差。

定义8

设，若存在s.t.，则称是在[a，b]上的最佳一致逼近多项式（最小偏差逼近多项式），简称最佳逼近多项式。最佳逼近多项式总是存在的，即

定理4

设，则存在s.t.（证明略）

定义9

设，若在处有则称是的偏差点。

当时，称“正”偏差点。

当时，称“负”偏差点。介值定理保证偏差点总是存在的。

定理5

是的最佳逼近多项式的充分必要条件是：在[a，b]上至少有n+2个轮流为“正”，“负”的偏差点。即有n+2个点使得并称为切比雪夫交错点组。（只证充分性，见黑板）

推论若，则在中存在唯一的最佳逼近多项式。（证明略）

定理6

在[-1，1]上所有最高次系数为1的n次多项式中，与零的偏差最小。（证明见黑板）

例3

求在[-1，1]上的最佳2次逼近多项式。（见黑板）

一般来说，要求最佳逼近多项式是困难的，但在一定条件下的最佳1次逼近多项式是容易的。（详见黑板）

例4

求在[0，1]上最佳1次逼近多项式。（见黑板）

例5

求在[0，1]上1次最佳平方逼近多项式。解法方程得故平方误差最大误差用正交函数族作最佳平方逼近。为正交函数族，则故均方误差

定理9

在[-1，1]上所有最高次系数为1的n次多项式中，首一的Legendre多项式与零的偏差最小。（证明见黑板）

例5

求在[-1，1]上的三次最佳平方逼近多项式。（见黑板）当区间为[a，b]时，可作变换将区间化为[-1，1]，用Legendre多项式逼近。3.5曲线拟合的最小二乘法

给定的一组值要求使得误差平方和这里的也可以加权平方和记令记则称法方程，记注意，可能是奇异的。

定义10

设的任意线性组合在点集上至多只有n个不同的零点，则称在点集上满足哈尔（Haar）条件。

显然，在任意个点上满足哈尔条件。

可以证明，当在满足哈尔条件时，法方程唯一解。

当时，称线性拟合，当时，是病态的。

某些拟合可通过适当变换化为线性的，如取对数得具体算例见page94例7、例8。（略）

注：曲线拟合的最小二乘法即为超定线性方程的最小二乘解（取）。（ch5中介绍）

结束Ch4数值积分与数值微分4.1引言

积分的计算，有著名的Newton-Leibniz公式：本公式在理论上有重大意义，但在实际使用中往往是困难的。因为的原函数通常不易得到，甚至只是一张数表。为此，我们有必要研究积分的数值计算问题，比如：梯形公式：（中）矩形公式：

一般的，数值积分具有下列形式：其中，称为求积节点，称为求积系数（也称为节点的权），它仅与有关，而与无关。

关于数值积分的精度问题我们引入：

定义1

如果某个求积公式对所有不高于m次的多项式准确成立，而对某个m+1次多项式不准确成立，则称该公式具有m次代数精度。

事实上，只要对准确成立，而对不准确成立即可。

不难验证，T及R都为一次代数精度。例1

确定，使得的代数精度尽可能高。（见黑板）

构造求积公式的最基本方法是所谓插值型的求积公式。设给定节点

以插值函数近似代替，则

记，则称为插值型求积公式。插值型求积公式的余项

定理1求积公式至少具有n次代数精度的充分必要条件它是插值型求积公式。（证明见黑板）

定理2若求积公式中系数，则此公式是稳定的。（证明是简单的，略，见page122）4.2牛顿-柯特斯公式

牛顿-柯特斯求积公式是将积分区间[a，b]n等分。（具体推导见黑板）则这就是Newton-Cotes公式。其中，称为柯特斯系数，它只与n有关，与[a，b]及无关。特别地，当n=1，即梯形公式。当n=2，，即Simpson公式，也称抛物线公式。当n=4，并称为柯特斯公式。

书中表4-1（page124）给出了n=1~8的柯特斯系数。

注意，当时，出现负值，此时不能保证求积公式的稳定性。

定理3当n为偶数时，牛顿-柯特斯求积公式至少具有n+1次代数精度。

（证明见黑板）

特别地，Simpson公式具有三次代数精度。

利用积分中值定理，我们可得到（过程略）梯形公式的余项Simpson公式的余项Cotes公式的余项4.3复化求积公式（1）复化梯形公式。

将[a，b]n等分，分点在每个小区间上采用梯形公式，则记并称为复化梯形公式。

不难证明，其余项为由此可知，

由于的求积系数为正，故数值计算稳定。（2）复化Simpson公式。将[a，b]n等分，在每个小区间上采用Simpson公式，记，则记并称为复化Simpson公式。

其余项为显然，且数值计算稳定。（具体算例见page130例1，略）类似可得：(3)复化Cotes公式。4.4龙贝格求积公式由假定，则有于是，（误差的事后估计）令可以期望其结果更好。事实上，类似的，

进一步，并称为Romberg公式。一般的，也称为Romberg公式。

注意，当时，Romberg公式已不属于Newton-Cotes公式的范畴。逐步二分的Romberg算法可列表（见黑板）。

例2

用Romberg算法计算（二分4次）。（见黑板）4.5高斯求积公式

在求积公式中，适当选择节点有望提高其代数精度。更一般的，考虑带权函数的插值型求积公式

例3带权的插值型求积公式，其代数精度最高不超过2n+1次。（见黑板）

定义4如果求积公式具有2n+1次代数精度，则称节点为高斯点，相应的公式称为高斯公式。

例4

构造下列的高斯求积公式：（见黑板）

定理5插值型求积公式的节点是高斯点的充分必要条件是与任何次数不超过n次的多项式带权正交，即（证明见黑板）高斯求积公式的余项为

定理5等价于：

插值型求积公式的节点是高斯点的充分必要条件是它是积分区间上带权的n+1次的正交多项式的零点。

高斯求积公式是稳定的（定理6及其推论），也是收敛的（定理7）。

对于，积分区间[-1，1]，由于勒让德多项式在[-1，1]上正交，故的零点即为高斯点。比如（两点高斯-勒让德求积公式）

注意，对于一般的积分区间[a，b]，可作变换而将积分区间化为[-1，1]。（三点高斯-勒让德求积公式）（四、五点的见page145表4-7）高斯-勒让德求积公式的余项为当n=1时，

对于，积分区间[-1，1]，由于切比雪夫多项式在[-1，1]上带权正交，故的零点即为高斯点。进一步可算得

为方便计，用n个节点写出高斯-切比雪夫求积公式：其余项

例5

用三点高斯-切比雪夫公式计算：（见黑板）4.6数值微分（简介）

最简单的数值微分是用差商近似代替微商，如（中点公式）

中点公式误差阶为，即对二次多项式精确成立。记由得

从截断误差看，h越小越好，但从舍入误差看，h太小，有效数字严重损失。

若令与的舍入误差为，，则计算的舍入误差限从而计算的误差限：取为最优步长。

完Ch5线性方程组的直接解法5.1引言与预备知识（略）5.2高斯消去法

高斯消去法是解线性方程组的古老而有效的方法之一。这里只是将这一方法公式化，程序化罢了。（具体略）

下面我们用高斯消去法的矩阵表写来给出矩阵的三角分解。

设系数矩阵A的各顺序主子式都不为零（这是高斯消去法能进行的充分条件）。原方程经过第一次消元得，相当于左乘矩阵即

一般的，经第k次消元得相当于左乘矩阵即依次下去，最后得到记上三角矩阵，则其中为单位下三角矩阵。

定理7

（矩阵的LU分解）设A为n阶矩阵，如果A的直到n-1阶顺序主子式不为零，则A可分解为一个单位下三角矩阵L和一个上三角矩阵U的乘积，且分解法唯一。

（只要证明唯一性，见黑板）5.3高斯主元素消去法（简介）

通过一个算例说明高斯列主元素消去法。例1

用高斯列主元素消去法解线性方程组（见黑板）

再通过一个算例说明高斯-约当消去法。例2

用高斯-约当消去法解线性方程组（见黑板）

当然，在高斯-约当消元之前也可以先选列主元。5.4矩阵三角分解法

主要介绍直接三角分解法（杜利特尔分解法），对称正定方程组的乔累斯基分解法，三对角线方程组的追赶法。1、直接三角分解法

若有A=LU，则方程组Ax=b化为LUx=b。令LUx=b。由Ly=b

解出y。再由Ux=y解出x。其中

从A的元素可直接给出计算L，U的元素的递推公式。（详细见黑板）

上述的三角分解称为杜利特尔（Doolittle）分解法。

如果取L为下三角矩阵，U为单位上三角矩阵，则类似可得A的三角分解A=LU，并称为克鲁特（Crout）分解法。例3

用Doolittle分解法求解（见黑板）2、乔累斯基分解法

当方程组Ax=b的系数矩阵为正定矩阵时，则A的三角分解可以进一步简化。

定理10

（对称矩阵的三角分解）设A为n阶对称矩阵，且A的各顺序主子式都不为零，则A可唯一分解为其中L为单位下三角矩阵，D为对角阵。（证明见黑板）

定理11

（对称正定矩阵的Cholesky分解）

设A为n阶对称正定矩阵，则存在一个实的非奇异下三角矩阵L，使得当限定L的对角元为正时，分解是唯一的。（证明见黑板）

下面给出L的元素的计算递推公式。（详细见黑板）3、追赶法设三对角线方程组简记为Ax=f。

当其系数矩阵满足所谓的“对角占优”条件时，即则用高斯消去法或杜利特尔（克鲁特）分解法求解此方程组时，可略去许多的中间步骤（但计算机不会！）。

为此，直接给出“化简后的克鲁特分解法”——追赶法。

设A=LU，即令

比较即得容易验证，在对角占优条件下，故有递推公式

求解Ax=f等价于求解Ly=f及Ux=y。解Ly=f得解Ux=y得

这就是追赶法。其中称计算及的过程为“追”。称计算的过程为“赶”。

追赶法的计算量很小，大约为8n次乘除法，而且数值是稳定的。5.5向量和矩阵范数

定义2

如果向量的某个实值函数

满足：

则称是上的一个向量范数。等号成立当且仅当中常用范数

（-范数，最大范数）

（1-范数）

（2-范数）

（p-范数）

其中三角不等式称Minkowski不等式。

容易证明，范数N(x)是向量x的连续函数。

向量序列的收敛性等价于（定理16）（定理14）任意两种范数是所谓等价的，即存在常数，使得对一切，有（定理15）

定义4

如果矩阵的某个实值函数

满足：等号成立当且仅当则称是上的一个矩阵范数。

定义5

设，，给定向量范数，相应地定义一个矩阵的实函数（可以验证它满足定义4），则是上的矩阵范数，并称为的算子范数（从属范数）。

定理17

上述定义的确实是上的矩阵范数，且满足下列的相容条件：（证明见黑板）

对应于向量x的、1、2-范数，我们有常用的矩阵范数（定理18）：

（1）行范数（2）列范数（3）2-范数其中表示的最大的特征值。此外还有

（4）F-范数例4

设4阶阿达玛（Hadamard）矩阵求：，，，。（见黑板）例5

设A为n阶实矩阵，证明：（证明见黑板）

定义6

设的特征值为，称为的A的谱半径。

定理19（特征值上界）谱半径不超过A的任一算子范数，即。（对也成立）（证明见黑板）

定理20如果A是实对称矩阵，则（证明见黑板）

例6

设A，B是n阶实对称矩阵，证明：

定理20如果，则非奇异，且（为算子范数）（证明见黑板）5.6误差分析

线性方程组Ax=b中A或b通常带有观察误差以及（计算过程中产生的）舍入误差。下面来分析这些微小误差对解的影响。引例7

设方程组

记为Ax=b，其精确解

现常数项带有微小变化，考察方程组

可记为，其中其精确解为。

比较原方程组的解，变化很大。这样的方程组称为病态的，要引起特别注意。

定义7

如果矩阵A或常数项b的微小变化，引起方程组Ax=b解的巨大变化，则称此方程组（或矩阵A）是病态的，否则是良态的。

下面我们来寻找病态的原因以及刻画病态的度量。

设方程组Ax=b的精确解为x，先讨论A是精确的，b有误差。即方程组其解为，则故而故于是，（定理22）

这说明常数项的相对误差在解中可能放大倍。

对于b是精确的，A有误差，类似的有由此可见，刻画病态的程度。

定义8

设A是非奇异矩阵，称为矩阵A的条件数。常用的条件数：当A为对称矩阵时，条件数具有下列性质：（3）若A为正交矩阵，则例8

求三阶Hilbert矩阵的条件数：解：类似可得可见高阶Hilbert矩阵是严重病态的。

对于病态方程组可采用高精度，或用同解变换以减少系数矩阵的条件数，也可用“迭代改善法”。

一般的，当（1）A的三角约化时出现小主元；（2）A的行列式值很小或某些行近似线性相关；（3）A的元素差异很大且无规则时，通常A是病态的。

例9

方程组系数矩阵A的条件数

用列主元素消去法（计算到三位数字）得很坏的结果其同解方程组系数矩阵B的条件数

也用列主元素消去法（计算到三位数字）得很好的结果迭代改善法简介：先从解得近似解，记。再解得近似解。最后改善。可重复进行。当是精确解时，则由知道是的精确解。

注意：严重病态时，迭代法可能不收敛。5.7矩阵的正交三角化及应用1、初等反射阵其中，也称Householder矩阵（变换）。H是对称正交矩阵。（定理25）Householder变换的几何意义（见黑板）。2、平面旋转矩阵（变换）也称Givens变换。显然，P是正交矩阵。3、矩阵的QR分解

定理30（矩阵的QR分解）

（1）设，且列满秩，则其中R为非奇异上三角阵。

（2）设，且满秩，则有。其中Q为正交矩阵，R为上三角阵。当R具有正对角元时，分解法唯一。

定理31（Givens变换的QR分解）设为非奇异，则（1）R为上三角阵。（2）Q为正交矩阵。当R具有正对角元时，分解法唯一。4、求解超定线性方程组

设超定线性方程组令

为残差向量，求使得即关于x求导，并令其为零，得即（称为法方程组）

容易证明，为对称正定矩阵。

法方程组有唯一解这就是超定线性方程组的最小二乘解。

例10

求超定线性方程组的最小二乘解。其中（见黑板）

值得注意的是，法方程组往往是病态的。可利用矩阵的QR分解直接从原超定方程组解得最小二乘解。

利用正交约化定理，选择初等反射阵同时令，为正交阵，则且故当为的解时，有此时，由得（算例见page227例12，略）

结束Ch6线性方程组的迭代法6.1引言

设线性方程组，是其精确解，所谓迭代法是构造序列并按某种精度要求取k，以近似代替。

常见的有雅可比迭代法、高斯-塞德尔迭代法、超松弛迭代法。引例1

设线性方程组其精确解为。将原方程组改写为建立迭代格式取初值，可计算得已很接近精确解。一般的，迭代格式用矩阵可表示为并赋予初值。

称为迭代矩阵，为常向量（它们与k无关，称为定常迭代）。

迭代法中需要考虑的问题是：

（1）什么样的迭代格式及初值保证。

（2）精度如何说明。

（3）收敛时，收敛速度的快慢。6.2基本迭代法

设，其中为非奇异矩阵，令，其中非奇异，得或于是，由此构造一阶定常迭代格式：令，则

这就是Jacobi迭代法。其中。若引进记号则Jacobi迭代格式可写为具体的，Jacobi迭代格式为引例1的迭代法是Jacobi迭代。

在Jacobi迭代格式中，将用来代替，可得这就是Gauss-Seidel迭代法。（也称异步迭代）

下面给出Gauss-Seidel迭代法的矩阵表示。

设，代入得即得迭代格式或由得

例2

用Gauss-Seidel迭代法求解解：迭代公式取初值，可计算得

比较即知，G-S迭代比J-迭代收敛更快。注意：此结论一般不成立。

下面给出逐次超松弛迭代法（S.O.R）。

作为G-S迭代的一种加速法，它由S.P.Frankel及D.Young于五十年代提出。

由G-S迭代引入加速迭代公式（加权平均）代入即得这就是逐次超松弛迭代法。（其中称为松弛因子）

当时，S.O.R即为G-S迭代。取时，称为超松弛。取时，称为亚（低）松弛。统称超松弛。

下面给出S.O.R迭代的矩阵表示。即得故

关于松弛因子的确定无一般方法，可以试验，如等。6.3迭代法的收敛性

向量序列的收敛是指按分量收敛，同样，矩阵序列的收敛是指按元素收敛。例4矩阵序列当时，定理1（证明是简单的，略）定理2对任意向量，有（证明见黑板）定理3设，则（证明要用到Jardon标准形，参见p245，略）

定理4（迭代法基本定理）一阶线性定常迭代对于任意初始向量迭代收敛的充分必要条件是（证明见黑板）

推论J-迭代、G-S迭代、SOR迭代收敛的充分必要条件是它们的迭代矩阵的谱半径小于1。例5讨论方程组的J-迭代、G-S迭代的收敛性。（见黑板）

一般的，求谱半径是困难的，由于，只要某一个算子范数，则迭代收敛，具体地我们有下述定理。

定理5设方程组及一阶线性定常迭代。若的某种算子范数，则（1）迭代法收敛，即对任给初始向量，有且（2）

（3）

（4）（证明见黑板）

定理5的结论(3)说明用描述迭代精度是合理的。可以用来控制迭代次数。结论(4)可预计所需要迭代次数。

当方程组的系数矩阵为对角占优或对称正定时，我们可直接从知道常用迭代的收敛性。定义3（1）若矩阵的元素满足则称严格对角占优；

（2）若矩阵的元素满足且至少有一个不等式严格成立，则称弱对角占优；

定义4若矩阵的元素经若干次行列重排可化为，则称是可约矩阵，否则称不可约的。

定理6若是严格对角占优，或不可约弱对角占优，则非奇异。（证明，略）

定理7若是严格对角占优，或不可约弱对角占优，则解方程组的J-迭代与G-S迭代均收敛。（证明略）

定理8

（SOR迭代收敛的必要条件）设方程组的SOR迭代收敛，则。（证明见黑板）

定理10若是严格对角占优，或不可约弱对角占优，则当时，解方程组的SOR迭代收敛。

定理9若是对称正定方程组，则SOR迭代收敛。（证明略）（证明略）

例6

若是n阶非奇异矩阵，则通过同解变换总可以用G-S方法求解。（见黑板）Ch7非线性方程求根7.1方程求根与二分法（略）7.2迭代法及其收敛性

将方程改写为等价形式，若，则称为函数的一个不动点。

建立迭代公式，并选择初值，若，则称迭代公式收敛，即为函数的一个不动点。故也称不动点迭代法。例1

方程改写成建立迭代公式取，计算到可作为方程的近似根。

但若改写成，建立迭代公式取，迭代显然发散。

定理1

设满足：（映内性）（压缩性）则在上存在唯一的不动点。（证明见黑板）

定理2

在定理1的条件下，，有并有误差估计（证明见黑板）

此外，还有

一般的，L不易知道，条件（2）常用

代替。

定义1

设是的不动点，若迭代序列，且收敛到，则称迭代法局部收敛。

定理3

设是的不动点，在的某领域连续，且,则迭代局部收敛。

（证明是简单的）

例2

方程，其根为，构造下列迭代法：（1），则（事实上，此迭代发散）

（2），则

（此迭代也发散）

（3），则（4），则（3），（4）均收敛，但（4）更快（结果见page271）

定义2

设迭代收敛到的不动点，记迭代误差，如果

则称迭代是p阶收敛的。p=1时，称线性收敛；p>1时，称超线性收敛；特别当p=2时，称平方收敛。

定理4

设迭代，如果在的某领域连续，且

则迭代在附近是p阶收敛的。（证明见黑板）

例3迭代法收敛于，问迭代是几阶收敛的。（见黑板）7.3迭代收敛的加速方法

（1）埃特金加速方法设，由中值定理假设（变化不大），则相除得得记称埃特金加速方法。可以证明的收敛速度比更快。

（2）斯蒂文森加速方法

把埃特金加速方法用到不动点迭代：这便是Steffensen迭代。

它只是“二合一”的不动点迭代。Steffensen迭代也可写为其中

定理5

若是的不动点，则也是的不动点。反之，若是的不动点，又存在，且，则是的不动点，且Steffensen迭代是二阶的。（证明，略）

例1中迭代公式是发散的。但用Steffensen迭代是收敛的。（计算结果见page275）。

更进一步，若原迭代是p阶收敛的，则Steffensen迭代是p+1阶收敛的。（证略）7.4牛顿法

对于方程，若，构造迭代这就是牛顿迭代法（也称切线法）。（见黑板图）牛顿法的迭代函数

设是的单根，即从而，故牛顿法至少是平方收敛的。且由得例4用牛顿法解二次方程得迭代公式对于任意，可证明（page278)如求，取，可计算得（具有精度）从，得，建立迭代公式迭代函数为若，即，则迭代法局部收敛。取，得称简化的牛顿法（也称平行弦法）。（见黑板图）

注意，牛顿法或简化牛顿法对某些初值可能发散。为此，附加条件：满足此单调性条件的算法称下山法。对于Newton迭代作加权平均（，称下山因子），代入即得Newton下山法：

对于的选择可以从逐次减半试算直到满足单调性要求。Newton法也适用重根情形。（详见黑板）7.5弦截法与抛物线法

在Newton法中，以差商代替微商，即得弦截法：此方法需要给出双初值，。定理6说明，弦截法是超线性收敛的，（抛物线法略）7.6解非线性方程组的Newton迭代法设非线性方程组记则方程组简记为。

利用多元函数的泰勒展开（取线性部分），有由得构造迭代公式：这也是Newton迭代法。并称为Jacobi矩阵。结束Ch8矩阵特征值问题计算8.1引言

如果矩阵A有一个重数为k的特征值而对应的特征向量线性无关的个数少于k，则称A是亏损矩阵。此时A不可对角化。亏损矩阵的理论和计算都是困难的。关于特征值界的估计有下列的

Gerschgorin圆盘定理（1）A的每一个特征值必属于下述某个圆盘之中（复平面中）

（2）如果A有m个圆盘组成一个连通的并集S，且S与余下的n-m个圆盘是分离的，则S内恰好包含A的m个特征值。特别的，如果某个Di

与其他圆盘是分离，则Di中恰好包含A的一个特征值。例1

估计矩阵的特征值范围。（见黑板）

矩阵经过相似变换特征值不变。Schur定理设，则存在酉矩阵U，使得其中为A的特征值（可能是复数）。酉矩阵U满足：

实Schur分解定理设，则存在正交矩阵Q，使得其中为一阶或二阶方阵，且每个一阶是A的实特征值，二阶的两个特征值是A的两个共轭复特征值。

对于实对称矩阵，有下列结果：

定理11

设为实对称矩阵，则（1）

（2）

（3）其中称为对应于向量的瑞利商。8.2幂法及反幂法

幂法是用于计算矩阵主特征值及对应的特征向量的迭代方法。

设具有完全的特征向量组，记及分别为的特征值及对应的特征向量，且的主特征值是实根，满足构造迭代向量序列设则由于故从而故当k充分大时，有

作为的特征向量的近似值（除一个因子外）。以表示的第i个分量，则