计算机算法复习题及答案(前三章).pdf

该【计算机算法复习题及答案(前三章) 】是由【小屁孩】上传分享，文档一共【9】页，该文档可以免费在线阅读，需要了解更多关于【计算机算法复习题及答案(前三章) 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。:..计算机算法复****题及答案(前三章)第一章1、什么是绝对误差?什么是相对误差?答:绝对误差等于准确值与近似值差的绝对值。相对误差是近似数的误差与准确值的比值。2、什么是绝对误差限?什么是相对误差限?答:绝对误差限为绝对误差的“上界”相对误差限为相对误差绝对值的“上界”3、有效数字与绝对误差限有何关系?有效数字与相对误差限有何关系?答:(绝对)若近似值的绝对误差限是某一位上的半个单位,且该位直到的第一位非零数字一共有几位。则称近似值有n位有效数字。(相对)设近似值=±0.···×有n位有效数字,≠0,则真相对误差限为×设近似值=±0.···×的相对误差限为×,≠0,则它有n位有效数字。4、、、、=,那么取2位,=,有效数字为2位取3位,=,有效数字为3位取4位,=,有效数字为4位取5位,=,,若=,则误差限是|-x|≤×=×若=,则误差限是|-x|≤×≤×,若=,则相对误差限是=×=×%,要取几位有效数字?,≤×.由于=···,已知=4,故只要取n=4,就有≤×=%只要对的近似值取4位有效数字,%。此时由开方表得≈、课本13~14页****题1、2、3、:下列各数都是经过四舍五入得到的近似数,试指出它们是具有几位有效数字的近似数,并确定++和的误差限答:=,5位,=,2位,=,4位|++|-|++|≤|-|+|-|+|-|:..=×+×+×=()≈||η()+|η()|=××+××=+=()≈||η()+||η()=+==110m,宽d的值为=80m,已知|L-|≤,|d-|≤,试求面积S=Ld的绝对误差限和相对误差限。解:绝对误差限:S=η(Ld)≈||η(d)+||η(L)=110×+80×=相对误差限:S=(Ld)≈d㏑L+d㏑d=+=+=%=,b=,问a+b,a×b有几位有效数字。解:a+b≈+≈×b≈×≈、设x=,求x的具有i位有效数字的近似值,其中i=2、3、4、5、。X*解:i=2,1=*i=3,2=*i=4,3==5,X*=、判断下列哪个数精度高:x=1000±、y=100±:X*=1000y*=100,?=,?=∵?=?∴y*与X*的误差限相等xy??但是y=%,x=%∴X的精度高y*x*7、已知x1=,(x1是?的近似值〕且│?-x1│≤1/2*10-5哪么x1有几位有效数字?1解:∵|π-x|≤×10?5,m=||-6=-512∴x有6位有效数字1:..?答:数据拟合只要所构造的近似函数g(X)与被逼近函数f(X)在区间[a,b]上的偏差满足某种要求就行了。插值多项式所构造的函数y=f(x)的近似函数g(x)必须精确地通过由已知离散数据所确定的离散点。?答:①已给出函数是否肯定②查找函数是否唯一③如何表达查找函数④:基于准则(3)使残差的平方和为最小,即=min来选取拟合曲线的方法为曲线拟合的最小二乘法4、、、=f(x)的函数求其近似值插值表达式x13y12x?xx?x解:将x=1,y=1,x=3,y=2代入式P(x)=1y+0y,00111x?x0x?x10110x?3x?111得P(x)=×1+×2=(x+1)∴f(x)≈(x+1)11?33?=,=,lg==,;解:这里x=,x=,x==,y=,y=(x)=yl(x)+yl(x)+yl(x)2001122(x-)(x-)P(X)=×(-)(-)(x-)(x-)+×(-)(-)(x-)(x-)+×(-)(-)=13038x2-+()=:..,要举起W公斤的重物需要用F公斤的力,实验所得的数据如下表。W/kg20406080100F/。解:首先,将这些数据画在直角坐标系中,从图形上看,数据点的分布大致呈一条直线,所以所求的拟合直线为y=a+bx,则由公式?NNNa?b?x??y?ii?得关于a和b的线性方程组?i?1i?1NNN?a?x?b?x2??xy?iiii?i?1i?1i?1?5a?300b??解得a=,b=?300a?22000b?37972004000247623x∴近似公式为y=+20040005、课本50页****题:1、2、3、,求X=??x?xx?xPX?1y?0y解:将x=3,x=4,y=,y=?x0x?x10101110x?4x?3???(x)=3?44?3=+∴P()=,求二次lagrange插值多项式P(x)2X314Y425解:(x-1)(x-4)(x-3)(x-4)(x-3)(x-1)P(X)=×4+×2+×5=2(3-1)(3-4)(1-3)(1-4)(4-3)(4-1)=X+1****题3、已知函数表如下,试不用开方的办法而用抛物插值法计算115的值X100121144Y101112解:(x-121)(x-144)(x-100)(x-144)(x-100)(x-121)P(X)=×10+×11+×122(100-121)(100-144)(121-100)(121-144)(144-100)(144-121)10x2-2650x+17424011x2-2684x+15840012x2-2652x+145200=++9244831012P(115)≈:..,求Newton插值多项式X01436Y0-78514解:X1Y1一阶二阶三阶四阶42300-73?39011-75-154830353614Nn(x)=f(Xo)+f[Xo,X1](X-Xo)+f[Xo,X1,X2](X-Xo)(X-X1)+f[Xo,X1,X2,X3](X-Xo)(X-X1)(X-X2)+f[Xo,X1,X2,X3,X4](X-Xo)(X-X1)(X-X2)(X-X3)28X4?259X3+402X2?346X=151515156、已知列表函数值如下,构造牛顿二次插值公式。X314Y425解:XY一阶二阶N(X)=4+(X?3)=X+1n3410121457、由课本24页:、、三阶Newton插值公式。二阶:N(X)=f(x)+f[x,x](x?x)+f[x,x,x](x?x)(x?x)n001001201三阶:N(X)=f(x)+f[x,x](x?x)+f[x,x,x](x?x)(x?x)+n001001201f[x,x,x,x](x?x)(x?x)(x?x)0123012第三章:1、复化求积法的基本思想是什么?答:为了改善求积公式的精度,把积分区间分成若干个小区间,在每个小区间上采用次数不高的插值多项式,构造出相应的低阶求积公式,然后再把他们加起来作为整个积分区间上的求积公式。2、求积公式的代数精度有什么作用?梯形公式的代数是多少?答:作用:衡量一个求积公式的精确程度梯形公式具有一次代数精度3、复化求积法与变步长求积的区别?答:复化求积法计算积分时,要事先给出一个合适的步长。而变步长求积是在步长逐次二分的过程中,反复利用复化求积公式进行计算,直到所求的积分值满足精度要求为止。4、用复化的辛浦生公式和复化的梯形公式计算下列列表函数的积分值。X-4-2024Y1/171/511/51/17:..4+4解:复化辛浦生:h==242**********I=S=×[++4×(+)+2×1]=×=≈:21111214248I=T=×[++2×(+1+)]=+=≈、,88页****题6、,复化simpson公式和n=6的Newton-Cotes公式计算积分下表中给出了sinX在7个点上的值.----------------------------------------------------------------------------------------------------------------------------------------------------------------------解:用复化梯形公式I≈Tn=[f(a)+2f()(k)+f(b)]取a=0,b=π/2,n=π/12,n=6,则I≈Tn=1/2×1/12×π[sin(0)+sin()+sin]≈099429用复化Simpson公式I≈Sn=[f(a)+f(b)+4f()+2f()]≈=6的Newton-Cotes公式I≈Xsin+Xsin+Xsin+Xsin+Xsin+Xsin+Xsin≈,复化梯形公式的误差为-,复化Simpson公式的误差为+,用牛的Newton-Cotes公式的误差为+,Simpson公式计算定积分dX:..解:梯形公式:dX≈(1-0)[+]=+=Simpson公式:dX≈×(1-0)×[+4×+]=.(1)dX(取n=8)复化梯形公式=n==dX≈×[+2×[++++++]+]=:dX≈×[++4×(+++)+2×(++)]=(2)dX(取n=6)复化梯形公式:n==:..dX≈×[+2×(++++)+]=:dX≈×[++4×(++)×2×(+)]=:1、什么是绝对误差?什么是相对误差?准确值x与其近似值x*之差称为近似数x*的绝对误差相对误差:近似数的误差与准确值的比值2、什么是绝对误差限?什么是相对误差限?在数值计算中,记为e(x*)=x*-x,简记为。但一般来说,不能准确知道的大小,可以通过测量或计算|e(x*)|=|x*-x|≤估计其绝对值的上界,那么叫做近似数x*的绝对误差限,简称误差限相对误差限:绝对误差跟近似值的比值3、有效数字与绝对误错限有何关系?有效数字与相对误错限有何关系?若已知近似值的误差限,可以判断出有效数字的位数,若已知有效数字的位数,:1数据拟合与插值多项式有什么不同?数据拟合是求一个简单的函数,不要求通过已知的这些点,而是要求在整体上‘尽量好‘的逼近原函数而插值多项式则要求必须找到一个恰好通过这些数据点的多项式2构造插值多项式应注意事项有几点?在n+1个互异的插值节点x0,x1,....xn上满足条件式Pn(xi)=yi的次数不高于n的代数多项式存在且唯一3曲线拟合的最小二乘法的基本思想?找到一条曲线,既能反映给定数据的一般趋势,又不至于出现局部较大波动,所构造的近似函数g(x)与被逼近函数f(x)在区间[a,b]上的偏差满足某种要求第三章:1、复化求积法的基本思想是什么?:..把积分区间分成若干个小区间,在每个小区间上采用次数不高的插值多项式,构造出响应的地界求积公式,然后再吧它们加起来作为整个积分区间上的求积公式2、求积公式的代数精度有什么作用?梯形公式的代数是多少?衡量一个求积公式的精确程度梯形公式具有一次代数精度3、复化求积法与变步长求积的区别?复化求积法对于提高精度是有效的,但步长取得太大则精度难以保证变步长求积法可以通过在步长逐次二分的过程中,反复利用复化求积法进行计算,知道所求得的积分值满足精度要求第五章:1、代数方程求根的二分法的基本思想?用二分法求实根X的近似值的基本思路,就是逐步将含有X的区间二分,通过判断函数值的符号,逐步对半缩小有根区间,直到区间缩小到容许误差范围之内,然后取区间中点为根X的近似值。2、代数方程求根的简单迭代法基本步骤?1确定迭代变量2建立迭代关系式3对迭代过程进行控制3、牛顿迭代法的收敛条件是什么?设α是方程的根,φ'(a)绝对值≤L<1第六章:列主元消元法与全主元消元法有何区别?全主元消去法与列主元消去法基本相同,只是在消元过程的第k步中(k=1,2,…,n),把对第k列选主元的步骤改成对所剩第k,k+1,…,n行和列进行,从这(n-k+1)2个数中选取绝对值最大的元素,称为主元。求解线性方程组有哪二大类方法?消去法与平方根法