数值计算方法总复习.

第二章非线性方程的数值解法常用方法1二分法2一般迭代法3牛顿迭代法4弦截法根的隔离；误差估计；迭代收敛阶2一般迭代法)1(0)(xf对(1)迭代法(1)把（1）等价变换为如下形式)2()(xgx(2)建立迭代格式)3()(1kkxgx(3)适当选取初始值x0，递推计算出所需的解。定理2.2（非局部收敛定理）如果在上连续可微且以下条件满足：)(xg],[ba],[)(,],[)1(baxgbax则若1)(,],[)2(Lxgbax对.}{)(,],[,*1xxxgxbaxkkk收敛于的解序列对那么命题2.2若在区间内，则对任何，迭代格式不收敛。],[ba1][xg)(1kkxgx],[0bax推论设x*=g(x*)，若g(x)在x*附近连续可微且，则迭代格式xk+1=g(xk)在x*附近局部收敛。1|)(|*xg(2)迭代法的收敛性简单地代之以||1kkxx(3)迭代法的误差估计3牛顿迭代法)122()()(1kkkkxfxfxx其迭代函数为)132()()()(xfxfxxg牛顿迭代法4弦截法,1,0,)()()()(10111kxxxxxfxfxfxxkkkkkkk弦截法第三章线性代数方程组的数值解法1解线性方程组的消去法1解线性方程组的矩阵分解法3解线性方程组的迭代法给定一个线性方程组)13(bAxnnnnnnnnnnijbbbbxxxxaaaaaaaaaaA2121212222111211,,)(这里求解向量x。)13(bAx)0(24)0(4)0(42)0(41)0(13)0(3)0(32)0(31)0(12)0(2)0(22)0(21)0(11)0(1)0(12)0(110)0()0(1,)0()0(,,nnnnnnnnniiiijijaaaaaaaaaaaaaaaabAabbaa）（则增广矩阵为：记）（(1)高斯消去法1.解线性方程组的消去法1）消元过程：对k=1,2,…,n依次计算)43()1,,1;,,2,1()1;,2,1(/)()1()1()()1()1()(nkjnkkiaaaankkjaaakjkkkikjikjikkkkjkkjk2)回代过程：)53()1,,1,(1)()(1)(1nnkxaaxaxnkjjkjkknkknnnnxIbA行初等变换这一无回代的消去法称为高斯-若当（Jordan）消去法(2)高斯-若当（Jordan）消去法高斯-若当（Jordan）消去法一般公式：)1,,1;,,1,1,,1()1;,2,1(/)()1()1()()1()1()(nkjnkkiaaaankkjaaakjkkkikjikjikkkkjkkjk定理3.1如果的各阶顺序主子式均不为零，即有),3,2(0,01111111nkaaaaDaDkkkkk即消去法可行。推论若系数矩阵严格对角占优，即有),2,1(1niaanjijijii),,3,2(/,1)1(1)0(11nkDDaDakkkkk则消去法可行，且(3)选主元素的消去法主元素的选取通常采用两种方法：一种是全主元消去法；另一种是列主元消去法。2解线性方程组的矩阵分解法一、非对称矩阵的三角分解法矩阵分解法的基本思想是：nnnnllllllL21222111nnnnuuuuuuU22211211可逆下三角矩阵可逆上三角矩阵)0(AbAx对于给定的线性方程组LUA（1）分解bLyyUxbLUxbAx)2(——解两个三角形方程组。分解。—为单位上三角为下三角，分解。—为上三角为单位下三角，CroutULDoolittleUL.2.1矩阵的Crout分解的计算公式010k规定),,1;1,,2,1(/)(),,2,1;,,2,1(1111nijnilulauijniulalikiikjikijijjkkjikijij(3-12)nnnnnnaaaaaaaaa212222111211nnnnllllll212221111112112nnuuu4444434342424141343433333232313124242323222221211414131312121111)()()()()()()()()()()()()()()()(lalalalaualalalauaualalauauaualajilaujialiiijijijij/)]([)(.2一个内积一个内积行第列第行第列第行第列第332211.1注：3.3.3对称正定矩阵的三角分解定义3.1若n阶方矩阵A具有性质且对任何n维向量成立，则称A为对称正定矩阵。TAA0x0AxxT定理3.4若A为对称正定矩阵，则(1)A的k阶顺序主子式(2)有且仅有一个单位下三角矩阵L和对角矩阵D使得（3-16）这称为矩阵的乔里斯基（Cholesky）分解。(3)有且仅有一个下三角矩阵，使（3-17）这称为分解矩阵的平方根法。),,2,1(0nkDkTLDLAL~TLLA~~3解线性方程组的迭代法nnnnnnnnnijffffmmmmmmmmmmM21212222111211)(，其中迭代法思想:(1)Ax=b(3-1))23(fxMx格式递推求解。，用迭代选取初始向量Tnxxxx],,,[)3()0()0(1)0(0)0((2)建立迭代格式)263()()1(fxMxkk这称为一阶定常迭代格式，M称为迭代矩阵。bAx约化便得),2,1()(11nixabaxnjijjijiiii从而可建立迭代格式对（3-23）以分量表示即)233(),2,1(1njijijnibxa(1)、Jacob迭代法雅可比（Jacobi）迭代)243()2,1,0;,2,1()(11)()1(knixabaxnjijkjijiiiki0000,000121121121nnnnnnnaaaaUaaaL可逆这里记nnaaaDULDA2211,则雅可比迭代格式（3-24）可用矩阵表示为MJfJbDxULDxkk1)(1)1()()253()2,1,0;,2,1()(1111)()1()1(knixaxabaxijnijkjijkjijiiiki用矩阵表示为bLDxULDxkk1)(1)1()()(对雅可比迭代格式修改得高斯-塞德尔（Gauss-Seidel）迭代fG-SMG-S(2)Gauss-Seidel迭代法例3.10分别用雅可比迭代法和高斯-塞德尔迭代法求解线性方程组1015352111021210321xxx解相应的迭代公式为)(2)(1)1(3)(3)(1)1(2)(3)(2)1(14.02.021.02.05.11.02.03.0kkkkkkkkkxxxxxxxxx雅可比迭代高斯-塞德尔迭代)1(2)1(1)1(3)(3)1(1)1(2)(3)(2)1(14.02.021.02.05.11.02.03.0kkkkkkkkkxxxxxxxxx令取四位小数迭代计算,0)0(3)0(2)0(1xxx由雅可比迭代得000.3,000.2,000.1)11(3)11(2)11(1xxx由高斯-塞德尔迭代得000.3,000.2,000.1)6(3)6(2)6(1xxx定理3.5若一阶定常迭代格式（3-26）的迭代矩阵满足条件nnijmM)()283(1max11njijnim则该迭代格式对任何初始向量均收敛。)0(x则该迭代格式对任何初始向量均收敛。)0(x)293(1max11niijnjm定理3.6若一阶定常迭代格式（3-26）的迭代矩阵满足条件nnijmM)(迭代法的收敛性推论如果线性代数方程组Ax=b的系数矩阵A为严格对角占优矩阵，即)303(),2,1(1njijijiiniaa则相应的雅可比迭代法与高斯-塞德尔迭代法对任何初始向量均收敛。)0(x定理3.8一阶定常迭代格式对任何初始向量均收敛的充分必要条件为其迭代矩阵的谱半径小于1，即fMxxkk)()1(这里为M的特征值n,,1)313(1max)(1iniM第四章函数的插值与拟合法1插值多项式的构造2最小二乘法定义4.1设y=f(x)在区间[a,b]上连续，在[a,b]内n+1个互不相同的点上取值.求一代数多项式P(x)，使得)(,,010bxxaxxxnnnyyy,,10)14(),1,0()(niyxPii则称P(x)为f(x)的插值函数1插值多项式定理4.1在n+1个互异点上满足插值条件(4-1)的次数不超过n次的插值多项式存在且惟一。nxxx,,,10)(xPn两种插值多项式形式(1)拉格朗日插值多项式下列列表函数的多项式Ln(x)xx0x1---xi-1xixi+1---xnyy0y1---yi-1yiyi+1---yn)54()()(000ninjijjijiniiinxxxxyxlyxL)())(()())(()())(()())(()(1210120102010210nnnnnxxxxxxxxxxxxyxxxxxxxxxxxxyxL)'54()())(()())((110110nnnnnnxxxxxxxxxxxxy010110101)(xxxxyxxxxyxL线性插值(n=1)，抛物插值(n=2)))(())(())(())(())(())(()(1202102210120120102102xxxxxxxxyxxxxxxxxyxxxxxxxxyxL(2)牛顿均差插值多项式)())()(](,,[))(](,,[)](,[)()(110010102100100nnxxxxxxxxxxxfxxxxxxxfxxxxfxfxNnkkkxxxxfxf1100)(],,[)(Ln(x)和N(x)插值多项式的余项),()()74(],[),()!1()()(1)1(baxbaxxnfxRnnn)64()()(01njjnxxx)()()()()(xNxfxLxfxRnn)())()(](,,,[)(10010nnnxxxxxxxxxxxxfxR)204()(],,,,[110xxxxxfnn例：已知列表函数,并计算f(0.5)的计算值。)()(33xNxL和作)()()()()(332211003xlyxlyxl