数值分析(计算方法)总结

第一章绪论误差来源：模型误差、观测误差、截断误差（方法误差）、舍入误差ε(x)=|x−x∗|是x∗的绝对误差，e=x∗−x是x∗的误差，ε(x)=|x−x∗|≤ε，ε为x∗的绝对误差限（或误差限）er=ex=x∗−xx为x∗的相对误差，当|er|较小时，令er=ex∗=x∗−xx∗相对误差绝对值得上限称为相对误差限记为：εr即：|er|=|x∗−x||x∗|≤ε|x∗|=εr绝对误差有量纲，而相对误差无量纲若近似值x∗的绝对误差限为某一位上的半个单位，且该位直到x∗的第一位非零数字共有n位，则称近似值x∗有n位有效数字，或说x∗精确到该位。例：设x=π=3.1415926…那么x∗=3,ε1(x)=0.1415926…≤0.5×100,则x∗有效数字为1位，即个位上的3，或说x∗精确到个位。科学计数法：记x∗=±0.a1a2⋯an×10m(其中a1≠0),若|x−x∗|≤0.5×10m−n，则x∗有n位有效数字，精确到10m−n。由有效数字求相对误差限：设近似值x∗=±0.a1a2⋯an×10m（a1≠0）有n位有效数字，则其相对误差限为12a1×101−n由相对误差限求有效数字：设近似值x∗=±0.a1a2⋯an×10m（a1≠0）的相对误差限为为12（a1+1）×101−n则它有n位有效数字令x∗、y∗是x、y的近似值，且|x∗−x|≤η(x)、|y∗−y|≤η(y)1.x+y近似值为x∗+y∗,且η(x+y)=η(x)+η（y）和的误差（限）等于误差（限）的和2.x-y近似值为x∗−y∗,且η(x+y)=η(x)+η（y）3.xy近似值为x∗y∗,η(xy)≈|x∗|∗η(y)+|y∗|∗η(x)4.η(xy)≈|x∗|∗η(y)+|y∗|∗η(x)|y∗|21．避免两相近数相减2．避免用绝对值很小的数作除数3．避免大数吃小数4．尽量减少计算工作量第二章非线性方程求根1.逐步搜索法设f(a)0,f(b)0，有根区间为(a,b)，从x0=a出发，按某个预定步长(例如h=(b-a)/N)一步一步向右跨，每跨一步进行一次根的搜索，即判别f(xk)=f(a+kh)的符号，若f(xk)0(而f(xk-1)0),则有根区间缩小为[xk-1,xk](若f(xk)=0，xk即为所求根),然后从xk-1出发，把搜索步长再缩小，重复上面步骤，直到满足精度：|xk-xk-1|E为止，此时取x*≈(xk+xk-1)/2作为近似根。2.二分法设f(x)的有根区间为[a,b]=[a0,b0],f(a)0,f(b)0.将[a0,b0]对分，中点x0=((a0+b0)/2),计算f(x0)。对于给定精度ε，即b−a2k𝜀，可得所需步数k，k[ln(b−a)−ln(ε)ln23.比例法一般地，设[ak,bk]为有根区间，过(ak,f(ak))、(bk,f(bk))作直线，与x轴交于一点xk,则：x=a−f(a)f(b)−f(a)∗(b−a)1.试位法每次迭代比二分法多算一次乘法，而且不保证收敛。2.比例法不是通过使求根区间缩小到0来求根，而是在一定条件下直接构造出一个点列（递推公式），使该点列收敛到方程的根。——这正是迭代法的基本思想。事先估计:|x∗−xk|≤L1−L|x1−x0|事后估计|x∗−xk|≤11−L|xk+1−xk|局部收敛性判定定理：设x∗为方程x=φ(x)的根，φ(x)′在x∗的某一邻域内连续，且|φ(x∗)′|1，则该迭代局部收敛局部收敛性定理对迭代函数的要求较弱，但对初始点要求较高，即初始点必须选在精确解的附近Steffensen迭代格式：x̃k+1=φ(xk)x⃗k+1=φ(x̃k+1)xk+1=xk−(x̃k+1−xk)2x⃗k+1−2x̃k+1+xkNewton法：xk+1=xk−f(xk)f′(xk)Newton下山法：xk+1=xk−λf(xk)f′(xk),λ是下山因子弦割法：xk+1=xk−f(xk)∗(xk−xk−1)f(xk)−f(xk−1)抛物线法：令t=x−xk,h0=xk−2−xk,h1=xk−1−xk,可化为y(t)=at2+bt+c其中：a=(f(xk−2)−c)∗h1−(f(xk−1)−c)∗h0h1∗h02−h0∗h12b=(f(xk−1)−c)∗h02−(f(xk−2)−c)∗h12h1∗h02−h0∗h12c=f(xk)则：xk+1={xk+−2cb+√b2−4ac,b0xk+2cb+√b2−4ac,b≤0设迭代xk+1=g(xk)收敛到g(x)的不动点（根）x*设ek=xkx*若limk→∞|ek+1||ek|p=C，则称该迭代为p（不小于1）阶收敛，其中C(不为0)称为渐进误差常数第三章解线性方程组直接法列主元LU分解法：计算主元Si=aik−∑lirurk，i=k,k+1…nk−1r=1选主元|Sik|=maxk≤i≤n{|Si|}{u1j=a1j，（j=1,2…n)li1=ai1u11，（i=2,3…n){ukj=akj−∑lkmumj，(j=k,k+1,…n)，即为上式主元k−1m=1lik=1ukk(aik−∑limumkk−1m=1)，(i=k+1,k+2,…n)对于Ax=b，三角分解A=LU，Doolittle分解：L为单位下三角矩阵，U为上三角矩阵；Crout分解：L为下三角矩阵，U为单位上矩阵。可分解为：{Ly=b，下三角方程组Ux=y，上三角方程组若利用紧凑格式可化为：Ux=y{y1=b1yk=bk−∑lkmym，（k=2,3…n）k−1m=1Cholesky平方根法：系数矩阵A必须对称正定AX=b⇔{Ly=bLTx=y(其中A=LLT){l11=√a11，li1=ai1l11(i=2,3…n)lkk=√akk−∑lkm2k−1m=1，lik=1lkk(aik−∑limlkm)(i=k+1,k+2…n，k=2,3…n)k−1m=1改进Cholesky分解法：A=LDLTL=[1l211l31l321………⋱ln1ln2…ln(n−1)1]，D=[d1d2⋱⋱dn]。由A=L(DLT)A=[1l211l31l321………⋱ln1ln2…ln(n−1)1]，D=[d1d1l21d1l31…d1ln1d2d2l32…d2ln2⋱…d3ln3⋱⋮dn]，逐行相乘{lij=1dj(aij−∑likdkljk)，（j=1,2…i−1)j−1k=1di=aii−∑lik2j−1k=1dk，（i=1,2…n)为减少计算量，令cij=lijdj，可改为：{cij=aij−∑cikljkj−1k=1lij=cijdjdj=aii−∑cikliki−1k=1(i=2,3…n，j=1,2…i−1)，等价于{Ly=bLTx=D−1y其中：D−1=[1d11d2⋱1dn]追赶法：Ax=d(A=LU),可化为Ly=d,Ux=yA=[a1c1b1a2c2⋱⋱⋱an−1bn−1cn−1anbn]=[1l21⋱⋱ln−11ln1][u1c1u2c2⋱⋱un−1cn−1un]{u1=b1li=aiui−1ui=bi−lici−1，（i=2,3…n)向量范数：：{‖A‖1=∑|xi|ni=1，1−范数‖A‖2=√∑xi2ni=1，2−范数或欧氏范数‖A‖∞=limp→+∞‖x‖p=max1≤i≤n{|xi|}，∞−范数矩阵范数：{‖A‖1=max1≤j≤n∑|aij|ni=1，列范数‖A‖2=√λmax(ATA)，谱范数‖A‖∞=max1≤i≤n∑|aij|nj=1，行范数谱半径:ρ(A)=max1≤i≤n{|λi|}λ为特征值,且ρ(A)≤‖A‖,若A为对称阵则：ρ(A)=‖A‖2收敛条件：谱半径小于1条件数：Cond=‖A−1‖∗‖A‖，Cond2(A)=|λmax||λmin|第四章解线性方程组的迭代法Jacobi迭代：xi(k+1)=1aii(bi−∑aijxj(k)−∑aijxj(k))nj=i+1i−1j=1,(i=1,2…n;k=0,1,2…)基于Jacobi迭代的Gauss-Seidel迭代:xi(k+1)=1aii(bi−∑aijxj(k+1)−∑aijxj(k))nj=i+1i−1j=1,(i=1,2…n;k=0,1,2…)迭代收敛：谱半径小于1，范数小于1能推出收敛但不能反推逐次超松弛迭代（SOR）:xi(k+1)=xi(k)−ϖaii(bi−∑aijxj(k+1)−∑aijxj(k))nj=i+1i−1j=1,(i=1,2…n;k=0,1,2…)或：xi(k+1)=(1−ϖ)xi(k)+ϖaii(bi−∑aijxj(k+1)−∑aijxj(k))nj=i+1i−1j=1,(i=1,2…n;k=0,1,2…)当ϖ=1时，就是基于Jacobi迭代的Gauss-Seidel迭代（加权平均）。第五章插值法Lagrange插值法：lj(xi)={0，i≠j1，i=j，则lj(x)=∏x−xixj−xini=0构造插值函数：Ln(xi)=f(xi)=yi，(i=0,1…n)，令L(x)=l0(x)y0+l1(x)y1+⋯+ln(x)yn则：y=Ln(x)=∑lj(x)yj=∑[∏(x−xi)(xj−xi)ni=0i≠j]nj=0nj=0yj若记：𝓌(x)=(x−x0)(x−x1)…(x−xn)=∏（x−xi）ni=0则可改为：lj(x)=𝓌n+1(x)(x−xj)𝓌′n+1(xj)，则Ln(x)=∑∏(x−xi)(xj−xi)ni=0i≠jnj=0yj=∑𝓌(x)(x−xj)𝓌′(xj)nj=0yj则插值余项：Rn(x)=f(x)−Ln(x)=fn+1(ξ)(n+1)!𝓌n+1(x)逐次线性插值法Aitken（埃特金法）：𝐋𝟎,𝟏…𝐤,𝐥(𝐱)=𝐋𝟎,𝟏…𝐤(𝐱)+𝐋𝟎,𝟏…𝐤−𝟏(𝐱)−𝐋𝟎,𝟏…𝐤(𝐱)𝐱𝐥−𝐱𝐤(𝐱−𝐱𝐤)=𝟏𝐱𝐥−𝐱𝐤|𝐟(𝐱𝐥)𝐱−𝐱𝐥𝐟(𝐱𝐤)𝐱−𝐱𝐤|Newton插值法：N(x)=a0+a1(x-x0)+a2(x-x0)(x-x1)+…+an(x-x0)(x-x1)…(x-xn)并满足N(x)=f(x)差商的函数值表示：f[x0,x1…xk]=∑f(xi)𝓌k+1(xi)ki=0差商与导数的关系：f[x0,x1…xk]=f(n)(ξ)n!则：f(x)=f(x0)+f[x0,x1]𝓌1(x)+⋯+f[x0,x1…xn]𝓌n(x)+f[x,x0,x1…xn+1]𝓌n+1(x)等距节点Newton插值公式：Newton向前插值：Nn(a+th)=f(x)+∑∆knk=1y0(tk)，其中(tk)=t(t−1)…(t−k+1)k!余项：Rn(x)=fn+1(ξ)hn+1(tn+1)，t=x−x0hNewton向后插值：Nn(xn+th)=f(xn)+∑∇knk=1yn(t+k−1k)余项：Rn(x)=fn+1(ξ)hn+1(t+nn+1)Hermite插值：H(x)=∑αj(x)yj+∑βj(x)y′jnj=0nj=0αj(x)=(Ax+B)lj2(x)，βj(x)=(Cx+D)lj2(x)可得：{αi(x)=[1−2(x−xi)∑1xi−xknk=0k≠i]li2(x)βi(x)=(x−xi)li2(x)插值余项：R2n+1(x)=f(x)−H2n+1(x)=f(2n+2)(ξ)(2n+2)!𝓌n+12(x)待定系数：H(x)=L0,1…n(Aitken)+(x−x1∗)(x−x2∗)…(x−xn∗)(Ax+B)三次样条插值：（三弯矩构造法）记s′′(xi)=Mi对s积分两次并满足插值条件，hi=xi−xi−1，λi=hihi+hi+1，μi=hi+1hi+hi+1对于附加弯矩约束条件：[2μ1λ22μ2λ32⋱⋱⋱μn−2λn−12][M1M2M3⋮Mn−1]=[6f[x0,x1,x2]−λ1M06f[x1,x2，x3]6f[x2,x3，x4]⋮6f[xn−2,xn−1,xn]−μn−1Mn]λiMi−1+2Mi+μiM