郑州大学数值分析考试知识点

题目类型：填空〔15个共30分，计算，证明综合题第一章根底 重点考察根本概念〔填空题〕把握：误差的种类，截断误差，舍入误差的来源，有效数字的推断和定义。了解：误差限，算法及要留意的问题。习题：误差分类：模型误差:从实际问题中抽象出数学模型时产生的误差。观测误差:通过测量得到模型中参数的值导致输入数据的误差。舍入误差:由于计算机字长有限而在数值运算的每一步所产生的误差。截断误差/方法误差:近似求解时产生的误差。模型误差：建立模型是由于做抱负化假设，无视次要因素而导致的误差，是四种误差中最大者。观测误差：由于仪器、试验手段、环境、人员等因素导致原始数据与真实值存在的误差。截断误差：用实际计算中有限次计算的近似结果代替需要无限次运算的准确值而产生的误差。舍入误差：计算机浮点数系近似表示实数系带来的误差。Taylor截断误差/方法误差。有效数字定义:设实数x的近似值为x10kaa12

a 其中每个am

是0,1,2,3. 9中的一个数字，且ai 1

0假设x确实定误差满足|e(x)|xx110kn就称用x近似x时具有n位有效数字，或者说x准确到了n位。2例题：0.24991/40.2499 0.2499 10 0,即m 0，|1 0.2499 | 0.0001 0.5 10 03 0.5 10 mn,即n 343例题：设x 1.7320508.......x=1.73,x=1.7321,x=1.7320是其近似值,问它们分别有几位有效数字?31 2 313解：e 31

x|0.00211

1013 32313e 2e 3

x |0.00005 1015 512 213x |0.000051 1014 433 2衡量算法优劣的指标有_时间简单度_, 空间简单度_.n3,空间简单度是指：算法需占用存储空间的量度。时间简单度是指：n3,两个n

则称两个n阶矩阵相乘这一问题的时间简单度为O(n3)把握：差商计算，插值误差估量,Hermite插值了解：Lagrange设函数f设函数f(x)在互异的节点x处有定义，称if(x)关于点x,x的一阶差商。0 1f(x)关于点x,xx的二阶差商。0 1,2k定义为：f(x)关于点x0：i11k阶差商可表成节点上函数值的线性组合，即2各阶差商具有对称性,即转变差商中节点的次序不会转变差商的值。设0,1,2,3……k的任一排列,则3f(xn次多项式，则一阶差商n-14f(x)在区间[a,bn+1,固定n+1在如下关系：主对角都是下减上再除以x-x剩下的都是下层减上层i 0牛顿差值：二次Newton插值公式为:nNewton二次Newton插值公式为:nNewton:简洁验证，NewtonP(x)=f(x),i=0,1,2,…,n.n i i拉格朗日插值和牛顿插值:插值函数与被插值函数在节点上的函数值相等Hermite插值:插值函数与被插值函数在节点上的函数值相等、某阶导数值相等。1.牛顿插值的误差不要求函数的高阶导数存在，所以更具有一般性f(x)是由离散点给出的函数f(x)的导数不存在的情形均适用。2.Newton插值公式的计算量为：n(n+1)/24.Hermitef(xx

上的函数值和导数值,即(x,f(x)),(x,f”(x)),i=0,1,2…,ni假设存在2n+1次多项式H(x)满足

i i i i则称H2n+1

2n+1(x)f(x)关于节点{x}(i=0,1,2,…,n)Hermite。i记f(x)=y,f”(x)=m,i=0,1,2,…,ni i i i由于每个节点对应两个插值条件，因此每个节点对应两个插值基函数:0 0 0111故三次Hermite插值函数的的形式:111故三次Hermite插值函数的的形式:构造差值基函数：三次Hermite插值误差定理：差值误差定理〔拉格朗日：

,…,x

0 1 n nn i i,习题：LagrangeNewton插值多项式，并写出误差估量式，以及验证插值多项式的唯一性。x014f(x)1932.函数f(0)=1,f(1)=3,f(2)=7,则f[0,1]= 2 ,f[0,1,2]= 1 。 f[x,x]f”(x)0 0 00,1两节点构造三次Hermite:f(0)=1,f’(0)=0,f(1)=2,f’(1)=1设x 0,x 1,则f(x )1，f(x)2，f”(x )0, f”(x)1设0 1 0 1 0 1插商表：xif(xi)一二三0101 012 1112 10-1因此,所求插值多项式为：第三章数据拟合把握：给出几个点求线性拟合曲线〔计算题〕了解：最小二乘原理如下数据表求拟合函数:(xabx习题：数据拟合与插值的区分是什么？插值法要求近似函数〔曲线或曲面〕经过的全部数据点。数据拟合主要依靠观测或试验得到数据，这些数据往往有肯定的随机误差，不要求近似函数的曲线或曲面通过全部点。最小二乘原理是使偏差

的 平方和 到达最小。i3.3.求过点2,0,1〔3,〕的线性拟合函数。Simpson〔填空Gauss〔推导题Gauss〔计算。了解：数值微分，积分余项1.梯形求积公式2.Simpson梯形公式和Simpson1，31.梯形求积公式2.SimpsonnGauss2n-12Gauss3n个节点Gauss2n+1n个节点插值型求积公式的代数精度为nnnn+1n个点插值型求积公式的代数精度为nnnn-1〔Simpson积分公式，对全部的子区间求和即得整个区间[,]上的积分公式，这种方法称为复化求积法。4.nf(x)在[a,b]上有连续的二阶导数，试推导定积分ba

f(x)dx在[a,b]上的复化梯形公式。对区间[a,bnxi

aih, hban

,n可得其子区间[xi,xi1](i0,1,2n1)上的梯形公式及其余项为：假设求积公式具有2n+1次代数精度，则称该公式为Guass型求积公式。假设求积公式具有2n+1次代数精度，则称该公式为Guass型求积公式。相应的积分点Gauss由代数精度的定义知，要使求积公式具有2n+1次代数精度，只要取时准确成立正交多项式系定义：一个正交多项式系：勒让德正交多项式：X是[a,bp(xnGaussk取勒让德(Legendre)正交多项式的零点作为高斯点，就可以得到高斯-勒让德积分公式：例题：n=0[-1,1Gauss公式11

f(x)dxc0

f(x)0[-1,1]上的一次正交多项式设p(x)xa|1p(x)01p1 1

dx11

(xa)1dx0a0p(x)x1

px)0求Gauss零点得x1

0 则10

f(x)dxc0

f(x0

)c0

f(0)Gauss10fx)x01所以1f(x)dx11

1dx2c0

f(x0

)c0

f(0)c20Gauss积分公式为11

f(x)dx2f(0)例题：n=1[-1,1Gauss公式11

f(x)dxc0

f(x0

)c1

f(x)1[-1,1]上的二次正交多项式设px)x2axb|2p(x0121

p(x)1dx0 a0 1 1p(x)xdx0 b31 2 33因此可得p(x)x21 令p(x)0求Gauss零点得x ,x 332 3 2 0 3 1 3则

f(x)dxc

3)cf( 3)1

3 1 3Gauss20/1fx)x01fx)x1x代入1f(x)dx

3)cf( 3)中可得c 1,c11

3 1 3 0 1故两节点的Gauss公式1f(x)dxf( 3)f( 3)1 3 3例题：n=2[-1,1Gauss公式

f(x)dxc

f(x

f(x)c

f(x)1〕先求[-1,1]上的二次正交多项式

1 0 0 1 1 2 2设p(x)x3ax2bxc|335可得：p(x)1(5x33x)令p(x)0求Gauss零点得x 3,x0,x 353 2 3 0 5 1 25 8 52〕令f(x)1，f(x)x，f(x)x2，可得c ,c ,c 0 9 1 9 2 9Gauss公式1

f(x)dx5

f(

3)8

f(0)5f( 3)1一般积分区间上的变量替换：

9 5 9 9 5例题：求带权函数的Gauss求积公式的推导：1f例题：求带权函数的Gauss求积公式的推导：1f(x)dxAf(x)Af(x).00011(1)先求积分区间[0，1]上带权函数的正交多项式的零点。fx)x2axb|，由正交多项式性质：xx1x0x

f(x)dx0xx1 f(x)xdx00解之得：a=-10/9 b=5/21，f(x)的零点为：x0=,x1=〔2〕再求积分系数。12次多项式准确成立，令f(x)=1,x1 xdx2AA0 3 0 1 21

xxdx

Ax0

5 00

11，解之得：A0，A1x1x0

f(x)dxA0

f(x0

)A1

f(x)1习题：确定以下求积公式中的待定系统，使得求积公式的代数精度尽量的高，并指明代数精度(1)

1f(x)dx1[f(1)2f(x)3f(x)]1 3 1 2分别用梯形公式、SimpsonGauss11

exdx，并估量各种方法的误差。4.推导复化梯形公式，并用复化梯形公式计算以下积分.〔未做〕4.推导复化梯形公式，并用复化梯形公式计算以下积分.〔未做〕1x04xdx,(n8)LU分解法求解线性方程组〔计算题，求Gauss消去法、平方根法、追赶法等运算量多大？〔填空了解：GaussLDL，追赶法1.高斯消去法总的乘除运算量为：平方根法的乘除运算量为：n36O(n2)1.高斯消去法总的乘除运算量为：4.4.LU平方根法和LDL求解的线性方程组为正定对称的线性方程组，追赶法求的是严格对角占优的线性方程组。三角分解法〔LU分解〕A=LUAx=bLUx=bUx=y，则Ly=b。Ly=b解出yUx=y解出x。假设A的各阶主子式不为零，则可以实现：多利特尔(Doolittle)分解：假设L为单位下三角矩阵，U为上三角矩阵；多利特尔(Doolittle)分解：a a11 12

a a 13 14 l

0 0 0u u11 12

u u 13 14a a21 22

a23 a2421 1

0 00

u u u 22 23 24 a a a a l l 1 00 0 u u u 31 u a a41

a33 a3443 44

31 l l41

l 10

33 340 044u u u 11 12 13

u 14 l21u11

l u u2112

l u u2113

l u u 2114 24 l31u11

l u l u3112 32

l u l u u3113 32 23

l u l u u3114 32 24 34 l u4111

l u l u4112 42

l u l u l u4113 42 23 43

l u l u l u u4114 42 24 43 34 44

u a ,u11 11

a ,u12

a ,u13

a ,. ,u14

a ,nj

l a u21 21

a a ,l21 11

a a ,l31 11

a a41

,. ,li1

a ai1

,i1,2 ,nu2行

u a22

l u ,u2112

a 23

u ,u2113

a 24

u2114

,. ,u2j

a j

u

,j2,3,. ,nl2列

l 32

l u3112

u ,l22

42

l u4112

u , ,l22

i2

lui112

u ,i3,4,. ,n223×3ULa11UU的其次行为该元素减去与其同行的同列的第i个L和U乘积的和。u a22l u,u a22 2112 23l u23 2113L的其次列为该元素减去与其同行的同列的第iL的其次列为该元素减去与其同行的同列的第i个L和U乘积的和，再除以该列的对角线元素Uu

a lu

l

(该元素减去对角线元素乘积的和)33 33

3113

3223由上式的关系可求得u和lij iju a1j

n lij

aijuij

i1,2,. ,nk=2,3,4,…,n的计算为：u akj k1l ukm m1

jk,k1,.....,n lik

a

k1limm1

u umk

,n习题：2 13x 64 57x111 32853

2 1Doolittle100 213

L210 U031 131 00131 005 再用前推和回代解出x1,x2,x3把握：Jacobi,Gauss-Seidel迭代格式构造，敛散性分析，向量、矩阵的范数、谱半径了解：SOR要求：给个方程组能写出Jacobi,Gauss-Seidel的迭代格式和迭代矩阵；由迭代矩阵的谱半径来推断敛散性；写出迭代格式，证明其敛散性〔计算+证明题〕向量和矩阵的范数计算〔填空和计算〕谱半径是如何定义的，谱半径与范数的关系是什么?(填空)题型：具体题＋证明，误差分析，三个主要迭代法，条件误差估量，范数的小证明线性方程组的数值解法有：直接法和迭代法。向量范数矩阵范数：雅可比(Jacobi)迭代格式：高斯-塞德尔〔Gauss-Seidel〕迭代法高斯-塞德尔〔Gauss-Seidel〕迭代法迭代法的收敛性及误差估量：判别收敛的几个常用条件：习题：1.x(3,2,1,7)T，计算||x||1

，||x||2

，||x||.3 1 22.A=0 1

，计算||A||

，||A|| . 1 2 62 0

1 2 A ,分别计算A的谱半径A,条件数condA)||A||0 3 14.4.矩阵A谱半径小于范数。求解AX=b的迭代格式x(k1)Bx(k)g收敛的充分必要条件 谱半径小于1_。SOR迭代法收敛的一个必要条件是松驰因子_ 0<ω