数值分析笔记

第一章绪论1、设x是精确值x*的一个近似值，近似值x的绝对误差e=x*-x绝对误差限|e|≤有关系式x-≤x*≤x+或x*=x±相对误差er（x*未知，用x代替）相对误差限r=/|x||er|≤r有效数字n从x左起第一个非零数字到该数位共有n位凡是由精确值经过四舍五入得到的近似值,其绝对误差限等于该近似值末位的半个单位。2.设近似值x的相对误差限位10-5，则x至少具有（5）为有效数字。第二章解线性方程组的直接法1、Gauss消去法是一种规则化的加减消元法，通过逐次消元计算，转化为等价的上三角形方程组。顺序Gauss消去法(简称为Gauss消去法):为主元素前提条件：主元素都不为零矩阵A的各阶顺序主子式都不为零。主元Gauss消去法:前提条件：矩阵A的行列式不为零。分为列主元消去法和全主元消去法，常用的方法为列主元消去法。列主元Gauss消去法是在每一步消元前,在主元所在的一列选取绝对值最大的元素作为主元素。2、直接三角分解法（1）Doolittle分解(LU)前提条件：A的各阶顺序主子式不为零。则存在唯一单位下三角矩阵L和上三角矩阵U使A=LUDoolittle分解(LU)法：Ax=b且A=LU，则先用Ly=b求y，再用Ux=y求x。三阶的LU计算公式（2）平方根法LDM分解和Cholesky分解(GGT)A=LU=LDM=LDLT=GGT（平方根法：Ax=b且A=GGT，则先用Gy=b求y，再用GTx=y求x）紧凑格式三阶公式全公式：若记G=(gij),则有:对k=1,2,…,n（3）追赶法Crout分解(TM)A=LU=LDM=TM三对角矩阵A的各阶顺序主子式都不为零的一个充分条件是:|a1||c1|0;|an||dn|0;|ai||ci|+|di|,cidi0,i=2,3,…,n-1.3、向量和矩阵的范数（1）向量的范数‖x‖为向量x的范数①非负性：‖x‖0,且‖x‖=0当且仅当x=0；②齐次性：实数,‖x‖=||‖x‖；③三角不等式:‖x+y‖‖x‖+‖y‖。x=(x1,x2,…,xn)T向量的1-范数:向量的2-范数:向量的-范数:范数的等价性m‖x‖‖x‖M‖x‖,xRn常用的三种向量范数等价关系‖x‖‖x‖1n‖x‖,xRn若则向量序列{x(k)}收敛于向量x*,记作***xxxxeerxxxxeer*),...,2,1()(nkakkk1111321323121nnnllllllL1/)(/1/12212313211311121uulauauaL2332133133132123122122131211ululaulaulaaaaUnnnnuuuuuu22211211......Unnnnnnaaaaaaaaa.........212222111211332211uuuD1/1//1222311131112uuuuuuM2322313322213132113122122112111333231222111333231222111/)(//ggagggagagagaaggggggaaaaaankigggaggagkmkkkmimikikkmkmkkkk,,1,)()(1111221nnnnnadcadcadca11122211nnnnT112211,,3,2,,,3,2,,,3,2,,,111111nicnidanidcaiiiiiiiii1111121nM222212nxxxx||max1inixxnxxxx211nRnxxxx,2nRnxxxx,2120lim*)(xxkk*)(*)(,limxxxxkkk或nixxikik,,2,1,*)(*)(xx4、矩阵的范数①非负性②齐次性③三角不等式‖A+B‖‖A‖+‖B‖和‖AB‖‖A‖‖B‖‖A‖为矩阵A的范数，为矩阵的特征值常用的矩阵范数矩阵的1-范数:,也称矩阵的列范数.矩阵的2-范数:,也称为谱范数.矩阵的-范数:,也称为行范数.矩阵的F-范数:1,2,…,n为矩阵A的n个特征值,则为矩阵A的谱半径。Cond(A)=‖A‖‖A-1‖,称为方程组Ax=b或矩阵A的条件数。第三章解线性方程组的迭代法x(k+1)=Mx(k)+g,k=0,1,2,…其中M称为迭代矩阵。1、Jacobi迭代法和Gauss-Seidel迭代法Jacobi迭代法（J迭代法）迭代矩阵若记则x(k+1)=Bx(k)+gk=0,1,2,…2、Gauss-Seidel迭代法（G-S迭代法）（了解）收敛比J迭代法快3、逐次超松弛迭代法---SOR方法（了解）称为松弛因子,当1时称为超松弛迭代,当1时称为欠松弛迭代。SOR方法收敛的快慢与松弛因子的选择有密切关系。经验上可取1.41.6。4、迭代法的收敛性迭代法收敛迭代矩阵谱半径小于1。若‖M‖1,则对任意x(0),迭代法收敛（充分非必要条件）。且若使‖x(k)–x*‖,只需即若n阶矩阵A=(aij)满足:则A是严格对角占优矩阵。若A严格对角占优,则J法,GS法,SOR法(01)收敛若A是对称正定矩阵,则解方程组Ax=b的①J迭代法收敛2D-A也正定；②G-S迭代法必收敛；③SOR法(02)收敛。0EAniijnjaA111max)(max2AATAnjijniaA11maxnjiijFaA1,2ini1max)(A,2,1,0,,2,1,)(11)(11)()1(knixaxabaxnijkijijkijiiikjji0002122222211111112nnnnnnnnaaaaaaaaaaaaBTnnnababab),,,(222111g,2,1,0,,2,1,)(11)(11)1()1(knixaxabaxnijkijijkijiiikjji1)(A)1()(*)(1kkkxxMMxx(0)(1)k*(k)xxM1Mxx)0()1(1xxMMkM(0)(1)xx)M(1ln/)ln(εkniaaiinijjij,,2,1,1,2,1,0,,2,1,)()(11)1()()1(knixaxabaxxnijkijijkijiiikikjji第四章解非线性方程的迭代法1、简单迭代法（逐次逼近法）方程(x)=0改写x=(x)，取合适的初始值x0，然后作迭代xk+1=(xk),k=0,1,2,…(x)称为迭代函数（1）整体收敛：若①a(x)b;②|(x)|L1,x[a,b].则xk+1=(xk),x0[a,b]都收敛于方程的唯一根。（2）局部收敛：若|()|1,则对充分接近的初值x0,迭代法xk+1=(xk)收敛。（3）xkp阶收敛于是指:p=1称为线性收敛;p=2称平方收敛;p1称超线性收敛。（4）若()=()=…=(m-1)()=0,但(m)()0，则迭代法m阶收敛。2、Newton迭代法（了解）3、二分法（了解）误差估计式|xk-|2-(k+1)(b-a).方程f(x)=0在区间[a,b]内有唯一根,f(a)f(b)0,f′(x)0。第六章插值与逼近1、Lagrange插值多项式定义：lk(x)(k=0,1,…,n)是关于节点xk(k=0,1,…,n)的n次Lagrange插值基函数。称为n次Lagrange插值多项式。公式：若记n+1(x)=(x-x0)(x-x1)…(x-xn),则n次Lagrange插值余项若|(n+1)(x)|在[a,b]有上界Mn+1，则2、Newton插值多项式定义：(xj)-(xi)与xj-xi(ij)的比值为(x)关于点xi,xj的一阶差商[xi,xj]称为(x)关于点xi,xj的一阶差商称为(x)关于点xi,xj,xk的二阶差商称为(x)关于点x0,x1,…,xk的k阶差商差商性质:①k阶差商（线性组合）②差商对节点具有对称性；③n次多项式(x)的k阶差商,当kn时是一个n-k次多项式;当kn时恒等于0。④若(x)具有k阶连续导数,则(即为xk系数)。n次Newton插值多项式(x)=Nn(x)+Rn(x)Nn(x)=(x0)+(x-x0)[x0,x1]+(x-x0)(x-x1)[x0,x1,x2]+…+(x-x0)(x-x1)…(x-xn-1)[x0,x1,…,xn]n次Newton插值余项Rn(x)=(x-x0)(x-x1)…(x-xn)[x0,x1,…,xn,x]3、分段插值多项式（略）4、三次样条插值（略）Cxxpkkk1lim,2,1,0,)()(1kxfxfxxkkkknkkkyx0nn1100n)((x)yl(x)yl(x)yl(x)Llnkjjjkjnkkkkkkknkkkxxxxxxxxxxxxxxxxxxxxxxxxx011101110)())(())(()())(())(()(l)()()()(11knknkxxxxxl))()!1()()()()(1)1(xnfxLxfxRnxnnn)()!1()(11xnMxRnnnijijjixxxfxfxxf)()(],[ikjikjkjixxxxfxxfxxxf],[],[],,[01102110],,,[],,,[],,,[xxxxxfxxxfxxxfkkkkkjjjkkxfxxxxf0110)()(1],,,[,!)(],,,[)(10kfxxxfkk)!1()(],,,,[)1(10nfxxxxfxnnLxxLkln)1(ln016、正交多项式(x)与g(x)的内积Schemite正交化(x)是非负连续函数,称为[a,b]上的权函数区间[-1,1]上权函数对应的二次正交多项式Pn上由线性无关函数1,x,x2,…,xn经过Schemite正交化过程得到的多项式p0(x),p1(x),…,pn(x)称为[a,b]上的正交多项式.（即f0(x)=1,f1(x)=x,f2(x)=x2,…,fn(x)=xn）7、数据拟合的最小二乘法(x)=a00(x)+a11(x)+…+ann(x)常用的函数系有幂函数系xj,三角函数系sinjx,cosjx,指数函数系正交函数系等.最常用的是幂函数系xj,即取=Pn=Span1,x,x2,…,xn,这时求得的拟合曲线称为多项式拟合曲线.（即0(x)=1,1(x)=x,2(x)=x2,…,n(x)=xn）引进向量j=(j(x0),j(x1),…,j(xm))T,j=0,1,2,…,n=(y0,y1,…,ym)T且记向量内积正则方程组badxxgxfxgf)()()(),(badxxffff)(),(22badxxfxf)()(22