数值计算方法总结

数值计算方法总结数值计算方法的一般概念解线性代数方程组的直接法插值法与最小二乘法数值微积分方程与方程组的迭代解法第1章数值计算方法的一般概念定义算法是指由基本算术运算及运算顺序的规定构成的完整的解题步骤.1.1算法描述算法可以使用框图、算法语言、数学语言、自然语言来进行描述。具有的特征正确性、有穷性、适用范围广、运算工作量少、使用资源少、逻辑结构简单、便于实现计算结果可靠第1章数值计算方法的一般概念稳定性计算过程中的误差能得到控制，各步误差对计算结果不致产生过大的影响1.1算法计算机的计算结果通常是近似的，因此算法必有误差，并且应能估计误差。收敛性通过增加计算量，能使近似计算解充分接近理论解第1章数值计算方法的一般概念1.2误差定义误差是指近似值与真正值之差误差分类模型误差在建立数学模型时，忽略次要因素而造成的数据误差由于问题中的值通过观察得到的，从而产生误差截断误差通过近似替代，简化为较易求解的问题计算误差由于计算机中数的位数限制而造成的第1章数值计算方法的一般概念1.2误差绝对误差绝对误差：是指近似值与真正值之差或差的绝对值，即~x设x为真值,为真值的近似值xxxx,或绝对误差界：用一个满足的数,来表示绝对误差的大小，并记为第1章数值计算方法的一般概念1.2误差相对误差相对误差：是指近似值与真正值之比或比的绝对值，即相对误差界：用一个满足的数,来表示相对误差的大小，并记为相对误差界常用百分数表示第1章数值计算方法的一般概念1.2误差准确数字各位数字皆准确的近似数称为有效数.此时各准确数字也称为有效数字第1章数值计算方法的一般概念1.2.3数据误差影响的估计第1章数值计算方法的一般概念1.2.3数据误差影响的估计12n12n(xxx(xxxyiiiiiiiiixxxxxxxxxni=1ni=1在误差估计式(1-1),(1-2)中,,...,)y,,...,)或表示解的误差相对参量的误差的放大或缩小倍数这些系数的绝对值称为求y问题的条件数，其值很大时的问题称为坏条件问题或病态问题凡是计算结果接近于零的问题往往是病态问题。应避免相近数相减,小除数和大乘数第1章数值计算方法的一般概念1.2.3数据误差影响的估计212212122212122222(11)))))))xxxxxxxxxxxxxxxxx112112112112112112由误差估计式可知(xxx(xxx(xxx(xxxxx(xx(xx1)21)2xxx(x(x第2章解线性代数方程的直接法求解n阶线性代数方程组11112211211222221122(2-1)nnnnnnnnnnaxaxaxbaxaxaxbaxaxaxb写成矩阵形式为(0)AxbA111212122212nnnnnnaaaaaaAaaa其中12nxxxx12nbbbb直接法指的是不计舍入误差时,通过有限次算术运算能求得准确解的方法第2章解线性代数方程的直接法2.1高斯消去法2.1.1基本步骤高斯消去法步骤1.[消去]经过n-1步将方程组化为同解的上三角形方程组11221,1nnaaa第一步消去下方元素,第二步消去下方元素,...,第n-1步消去下方元素2.[回代]按相反顺序求解上三角形方程组,得到方程组的解11nnxxx第一步得到,第二步得到,...,第n步得到将方程组写成增广矩阵的形式,将有利于计算机实现AAb第2章解线性代数方程的直接法2.1高斯消去法2.1.2运算量估计高斯消去法运算量估计1.消去算法运算量3211-1,-:,1-,5()(11)326nknknknkknnnNnknk分为步第步变换行求倍数再从个元素中减去第行对应列的倍数因此所需乘除次数:2.回代运算量-1121,11,...,-11,(1)12...2nnxxxnnnNn求需做次除法求需做次乘法和次除法求需次乘法和次除法因此所需乘除次数:321233nnNNNn因此,3()on即,运算量为第2章解线性代数方程的直接法2.1高斯消去法2.1.3选主元技术1,,,,...,,,,kkkknkpkkkaaaapk为避免出现小主元在第步的第列的元素中选出绝对值最大的元素然后交换第行和第行继续进行消去过程这种消去法称为列主元消去法选主元方法分为行主元法与全主元法第2章解线性代数方程的直接法2.2三角分解法2.2.1杜里特尔分解法高斯消去法的消去过程,实质上是把系数矩阵A分解为单位下三角矩阵L与上三角矩阵R的乘积,并且求解方程组Ly=b的过程,回代过程是求解上三角形方程组Rx=y11,,1,...,1iijijikkjkralrjijn11()/,1,..,ijijijkkiiiklalrrjin111112121313111121212212232322223131323233333333112233,()()()()()()()()()()()()()()()()()()()()nnnnnnnnnnnnnnnnnnLRArarararayblarararayblalararayblalalarayb实际计算时可以将和共同存放到增广矩阵的位置上第2章解线性代数方程的直接法2.2三角分解法2.2.1杜里特尔分解法分解A=LR,且L为单位下三角阵,R为上三角阵,称为杜里特尔(Dollittlse)分解.使用杜里特尔分解求解方程组Ax=b或L(Rx)=b,相当于求两个方程组Ly=b,Rx=y运算量3232211(),(),321(),233ALRnnLybnnnnRxynnNn分解需次解需次解需次共第2章解线性代数方程的直接法2.2三角分解法2.2.2克洛特分解法此分解称为克洛特(Crout)分解AAR,RL对进行杜里特尔分解时,=L为单位下三角阵,为上三角阵1122DR(,,...,)nnDdiagrrr令为的对角元所构成的对角阵-1()()ALRLDDR11111122(,,...,)nnDdiagrrr则计算公式1111,1,...,()/1,2,...,1ijijijkkikiijijikkjiiklalrjiinralrljiin第2章解线性代数方程的直接法2.2三角分解法2.2.3追赶法111122223331111nnnnnnnbcdabcdabcdAAbabcdabd11122223333111111111nnnnnnnlryalryalryAalryaly作克洛特分解第2章解线性代数方程的直接法2.2三角分解法2.2.3追赶法1111,/bydl1因此,可得l11111/,()/,2,3,...,iiiiiiiiiiiircllbarydaylin1,,1,...,1nniiiixyxyrxin回代得到,,iiirly按以上公式求解Ax=b的方法称为追赶法其中计算的过程称为追回代和过程称为赶计算量估计:共需要的乘除法次数为5n-4.第2章解线性代数方程的直接法2.2三角分解法2.2.4平方根法AAxb对于求解为正定矩阵的方程组121/2111()()/,1,...,,1,...,iiiiiikkijijijkikiiklallaliljinin计算公式A即可分解为下三角阵及其转置矩阵的乘积()TALDL则由于A的各阶顺序主子式大于0,则A可作克洛特分解且L的对角元全为正数121211112222(,,...,)()()()nTTTDdiagdddALDDLLDLDLL令则第2章解线性代数方程的直接法2.3舍入误差对解的影响2.3.1向量和矩阵的范数1212221/21221()maxnniinxxxxxxxxxx常用的向量的范数有三种:1212(,,...,),()(,,...,)Tnnxxxxxxxxxx对向量具有如下类似性质的函数向量的范数或称为模或长度(1)=0,,0(2),(3):xxxxxyxy性质:非负性:齐次性:对任意实数三角不等式第2章解线性代数方程的直接法2.3舍入误差对解的影响2.3.1向量和矩阵的范数()AA对n阶矩阵A,具有如下4种性质的函数称为矩阵A的范数(1)0=0,0,0(2),(3):(4)AAAAABABABAB性质:非负性:齐次性:对任意实数三角不等式111112max,1max,(),nijjninijinjTAaAaAAA常用矩阵范数:称为范数称为无穷大范数称为谱范数第2章解线性代数方程的直接法2.3舍入误差对解的影响2.3.1向量和矩阵的范数21/211()nnijFijAa矩阵的F范数(Frobenius):1(1)(2)I11(3)1,,()1AxAxIBIBIBB矩阵范数还具有以下性质:单位矩阵的范数当时可逆且第2章解线性代数方程的直接法2.3舍入误差对解的影响2.3.2舍入误差对解的影响~,Axbxxb~直接法解线性方程组由于舍入误差的存在,只能得到近似解,或者是A的精确解~~~~1-,1(),AbAAAbbbxbAkAxbAkAkcondAAAAxb近似矩阵和近似向量的误差为则可以得到其中称为方程组的条件数k条件数很大的方程称为病态方程组k值比较小的方程组称为良态方程组第3章插值法与最小二乘法()0,1,..,iiyfxin数个点处数已知函y=f(x)在n+1互不相同的的函值3.1拉格朗日插值法3.1.1插值多项式的概念2012()()(3-2)nnnyfxpxaaxaxax为数选项求函的近似值,用n次多式()()0,1,..,(3-3)nniipxpxyin满条使足件使用以上方法求函数近似式的方法称为插值法满足条件(3-3)的插值多项式是存在且唯一的第3章插值法与最小二乘法01(1)(),,...,,1,()()()()()()()(1)!nnnnnyfxxxxabnabxfxpxfRxfxpxxn如果被插函数在包含节点的区间上存在阶导数,则在区间上的任意点处,被插函数与插值多项式的误差3.1拉格朗日插值法3.1.2插值多项式的截断误差0101()()()(),,...,nnxxxxxxxxxxx其中为介于与节点之间这种误差不考虑舍入误差，称为截断误差第3章插值法与最小二乘法3.1拉格朗日插值法3.1.3拉格朗日插值多项式000()()nnnjniiiiijijjixxLxlxyyxx(),()()(-)()iiiinlxxlxxxx这里次式称为拉格朗日插值基函数简写为01011()()()(),()()()()()niiiiiiinxxxxxxxxxxxxxxxx其中第3章插值法与最小二乘法3.1拉格朗日插值法3.1.3拉格朗日插值多项式0110101101,--()()nxxxxfxLxyyxxxx特例当时有1011()()(-)(-)2Rxfxxxx02122010102101201220212,(-)(-)(-)(-)()()()()()()(-)(-)+()()nxxxxxxxxfxLxy