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,记11niixx221niixx1maxiinxx则1,2和都是向量范数。定理1.2设和是nR上的任意两种向量范数,则存在与向量x无关的常数m和M(0mM),使下列关系式成立,nmxxMxxR1.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,则3111maxnijjniAamax2()TAAA11maxnijinjAa其中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)...kkkkkkaaDknaa2.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.................................................1srnsnnnrsnsnrnnrnnaaaAaaauuululll1,.....nnnnuu为节省空间,用C(m,n)存储A的带内元素,其中m=r+s+1,并且1,ijijsjac。2.2.5拟三对角线性方程组的求解方法1112221111112222221111221..................11...........................1...1nnnnnnnnnnnnnnacddacAdaccdapqsdpqsqsdpsrrrrr2.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||||kkkkkGxxxxGGxxxxG2.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,...)TnkkrjjnkkkrkkTkknkkkrruhhuhhyuhuAyhhhhkk作为1的近似值,-1ky作为A的属于1的特征向量。3.1.2反幂法第一种反幂法迭代格式:0011111111&0/(1,2,...)nTkkkkkkkkTkkkuRuuuyuAuyyuk1k作为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(