北京航空航天大学数值分析课程知识点总结

11.2误差知识与算法知识1.2.2绝对误差、相对误差与有效数字设a是准确值x的一个近似值，记exa，称e为近似值a的绝对误差，简称误差。如果||e的一个上界已知，记为，即||e，则称为近似值a的绝对误差限或绝对误差界，简称误差限或误差界。记rexaexx，称re为近似值a的相对误差。由于x未知，实际上总把ea作为a的相对误差，并且也记为rexaeaa，相对误差一般用百分比表示。re的上界，即||ra称为近似值a的相对误差限或相对误差界。定义设数a是数x的近似值。如果a的绝对误差限时它的某一位的半个单位，并且从该位到它的第一位非零数字共有n位，则称用a近似x时具有n位有效数字。1.2.3函数求值的误差估计设()ufx存在足够高阶的导数，a是x的近似值，则~()ufa是()ufx的近似值。若'()0fa且|''()|/|'()|fafa不很大，则有误差估计~~()'()()()'()()eufaeaufaa。若(1)()'()''()...()0,()0kkfafafafa，且比值(1)()()/()kkfafa不很大，则有误差估计()~()~()()()!()()()!kkkkfaeueakfauak。对于n元函数，有误差估计~121~121(,,...,)()()(,,...,)()()nniiinniiifaaaeueaxfaaauax；若一阶偏导全为零或很小，则要使用高阶项。1.2.4算法及其计算复杂性（1）要有数值稳定性，即能控制舍入误差的传播。（2）两数相加要防止较小的数加不到较大的数中所引起的严重后果。（3）要尽量避免两个相近的近似值相减，以免严重损失有效数字。（4）除法运算中，要尽量避免除数的绝对值远远小于被除数的绝对值。1.3向量范数与矩阵范数1.3.1向量范数定义定义在nR上的实值函数称为向量范数，如果对于nR中的任意向量x和y满足：（1）正定性：0x，当且仅当0x时，0x；2（2）齐次性：对任一数kR，有kxkx；（3）成立三角不等式：xyxy。定理1.1对nR中的任一向量12(,,...,)Tnxxxx，记11niixx221niixx1maxiinxx则1，2和都是向量范数。定理1.2设和是nR上的任意两种向量范数，则存在与向量x无关的常数m和M(0mM)，使下列关系式成立,nmxxMxxR1.3.2矩阵范数定义定义在nnR上的实值函数称为矩阵范数，如果对于nnR中的任意矩阵A和B满足：（1）0A，当且仅当0A时，0A；（2）对任一数kR，有kAkA；（3）ABAB；（4）ABAB。定义对于给定的向量范数和矩阵范数，如果对于任一个nxR和任一个nnAR满足AxAx，则称所给的矩阵范数与向量范数是相容的。定理1.3设在nR种给定了一种向量范数，对任一矩阵nnAR，令1=maxxAAx，则由此定义的是一种矩阵范数，并且它与所给定的向量范数相容。定理1.4设[]nnijAaR，则3111maxnijjniAamax2()TAAA11maxnijinjAa其中max()TAA表示矩阵TAA的最大特征值（TAA是正定或半正定矩阵，它的全部特征值非负）。还有一种常见的矩阵范数2,1nijFijAa，且与向量范数2相容，但是不从属于任何向量范数。单位矩阵I的任何一种算子范数1=max1xIIx。定理1.5设矩阵nnAR的某种范数1A，则IA为非奇异矩阵，并且当该范数为算子范数时，还有111IAA成立。2.1Gauss消去法2.1.1顺序Gauss消去法定理2.1顺序Gauss消去法的前n-1个主元素()(1,2,...,1)kkkakn均不为零的充分必要条件是方程组的系数矩阵A的前n-1个顺序主子式(1)(1)111(1)()1.........0,(1,2,...,1)...kkkkkkaaDknaa2.1.2列主元素Gauss消去法定理2.2设方程组的系数矩阵A非奇异，则用列主元素Gauss消去法求解方程组时，各个列主元素()(1,2,...,1)kkikakn均不为零。2.2直接三角分解法2.2.1Doolittle分解法(单位下三角+上三角)与Crout分解法(下三角+单位上三角)定理2.3矩阵[](2)ijnnAan有唯一的Doolittle分解的充分必要条件是A的前n-1个顺序主子式0,(1,2,...,1)kDkn。推论矩阵[](2)ijnnAan有唯一的Crout分解的充分必要条件是A的前n-1个顺序主子式0,(1,2,...,1)kDkn。2.2.2选主元的Doolittle分解法4定理2.4若矩阵nnAR非奇异，则存在置换矩阵Q，使QA可做Doolittle分解。2.2.3三角分解法解带状线性方程组定理2.5(保带状结构的三角分解)设[]ijnnAa是上半带宽为s、下半带宽为r的带状矩阵，且A的前n-1个顺序主子式均不为零，则A有唯一的Doolittle分解111,11,1,,11121,12,1,1,1,,1.................................1...1.................................................1srnsnnnrsnsnrnnrnnaaaAaaauuululll1,.....nnnnuu为节省空间，用C(m,n)存储A的带内元素，其中m=r+s+1，并且1,ijijsjac。2.2.5拟三对角线性方程组的求解方法1112221111112222221111221..................11...........................1...1nnnnnnnnnnnnnnacddacAdaccdapqsdpqsqsdpsrrrrr2.3矩阵的条件数与病态线性方程组2.3.1矩阵的条件数与线性方程组的性态定义对非奇异矩阵A，称量1||||||||AA为矩阵A的条件数，记作1cond()||||||||AAA。矩阵A的条件数与所取的矩阵范数有关，常用的条件数是51cond()||||||||AAA，1222cond()||||||||AAA性质1对任何非奇异矩阵A，cond()1A。性质2设A是非奇异矩阵，0k是常数，则有cond()cond()kAA。性质3设A是非奇异的是对称矩阵，则有12cond()nA，其中1和n分别是矩阵A的模为最大和模为最小的特征值。性质4设A是正交矩阵，则有2cond()1A。2.3.2关于病态线性方程组的求解问题（1）采用高精度的算术运算。（2）平衡方法（行平衡，取每行绝对值最大数的倒数组成对角阵，乘在原方程左右两边）。（3）残差校正。2.4迭代法2.4.1迭代法的一般形式及其收敛性(1)()(0,1,...)kkxGxdk定义设nn矩阵G的特征值是12,,...,n，称1()max||iinG为矩阵G的谱半径。定理2.9对任意的向量d，迭代法收敛的充分必要条件是()1G。定理2.9如果矩阵G的某种范数||G||1，则（1）方程组的解*x存在且唯一；（2）对于迭代公式，有()*(0)lim,kkxxxR，且下列两式成立()*(1)(0)()*()(1)||||||||||||1||||||||||||||||1||||kkkkkGxxxxGGxxxxG2.4.2Jacobi迭代法(1)1()11()(0,1,...)()kkJADLUxDLUxDbkGDLU定理2.10Jacobi迭代法收敛的充分必要条件是()1JG。定理2.11如果||||1JG，则Jacobi迭代法收敛。引理2.1若矩阵nnAR是主对角线按行(或按列)严格占优阵，则A是非奇异矩阵。6定理2.12如果方程组的系数矩阵式主对角线按行(或按列)严格占优阵，则用Jacobi迭代法求解必收敛。2.4.3Gauss-Seidel迭代法(1)1()11()()(0,1,...)()kkGADLUxDLUxDLbkGDLU定理2.13GS迭代法收敛的充分必要条件是()1GG。定理2.14如果||||1GG，则Jacobi迭代法收敛。定理2.15如果方程组的系数矩阵式主对角线按行(或按列)严格占优阵，则用GS法求解必收敛。定理2.16如果方程组的系数矩阵A是正定矩阵，则用GS法求解必收敛。2.4.4逐次超松弛迭代法(1)1()1111(1)111()[(1)]()(0,1,...)11()[(1)]kkSADLDUxDLDUxDLbkGDLDU实际使用的形式(1)1(1)1()11{[(1)]}(0,1,...)kkkxDLxIDUxDbk它的分量形式是1(1)(1)()()111{(1)}(0,1,...)inijijkkkkiijijjjiiiiiiiaabxxxxkaaa定理2.17SOR方法收敛的充分必要条件是()1SG。定理2.18如果||||1SG，则SOR方法收敛。定理2.19SOR方法收敛的必要条件是02。定理2.20如果方程组的系数矩阵A是主对角线按行(或按列)严格占优阵，则用01的SOR方法求解必收敛。定理2.21如果方程组的系数矩阵A是正定矩阵，则用02的SOR方法求解必收敛。***实系数二次方程20xpxq的两个根之模均小于1的充要条件是：||1,10,10qpqpq***A为正定矩阵A的各阶顺序主子式全大于零。3.1幂法和反幂法3.1.1幂法（用于计算矩阵的按模为最大的特征值和相应的特征向量）第一种幂法迭代格式：70011111111&0/(1,2,...)nTkkkkkkkkTkkkuRuuuyuuAyyuk第二种幂法迭代格式：(0)(0)010(1)(1)1(1)11()()111()=(,...,)&0||max||/||(,...,)sgn()(1,2,...)TnkkrjjnkkkrkkTkknkkkrruhhuhhyuhuAyhhhhkk作为1的近似值，-1ky作为A的属于1的特征向量。3.1.2反幂法第一种反幂法迭代格式：0011111111&0/(1,2,...)nTkkkkkkkkTkkkuRuuuyuAuyyuk1k作为n的近似值，-1ky作为A的属于n的特征向量。还可以用带原点平移的反幂法求矩阵A的某个特征值s。3.3QR方法3.3.1矩阵的QR分解设nvR是单位向量，令2THIvv，则H是对称正交矩阵，称为Householder矩阵。引理3.1设有非零向量nsR和单位向量neR，必存在Householder矩阵H，使得Hse，其中是实数，并且||Tss。(可取()()Tsevsese)8定理3.2任何nn实矩阵A总可以分解为一个正交矩阵Q与一个上三角矩阵R的乘积。设1(