《2022年计算方法总结》由会员分享,可在线阅读,更多相关《2022年计算方法总结(11页珍藏版)》请在金锄头文库上搜索。
1、第一章:基本概念1. 12.12.1.mmmmnmnxx xx xxxx12.12.mmmmnxx xx xxx若1102nxx,称x准确到 n 位小数,mnx及其以前的非零数字称为准确数字。各位数字都准确的近似数称为有效数,各位准确数字称为有效数字。2. 12.( )0.ltf xxx xx进制:,字长:t,阶码:l,可表示的总数:12(1)(1)1tUL3.计算机数字表达式误差来源实数到浮点数的转换,十进制到二进制的转换,结算结果溢出,大数吃小数。4. 数据误差影响的估计:121(,.)nniix xxyyxx121( ,.)nniiiyyx xxxxyxy,小条件数。解接近于零的都是病态
2、问题,避免相近数相减。避免小除数大乘数。5.算法的稳定性若一个算法在计算过程中舍入误差能得到控制,或者舍入误差的积累不影响产生可靠的计算结果,称算法数值稳定。第二章:解线性代数方程组的直接法1.高斯消去法步骤:消元过程与回代过程。顺利进行的条件:系数矩阵A 不为零; A 是对称正定矩阵,A 是严格对角占优矩阵。2.列主元高斯消去法失真:小主元出现,出现小除数,转化为大系数,引起较大误差。解决:在消去过程的第K步,交换主元。还有行主元法,全主元法。3.三角分解法杜立特尔分解即LU分解。用于解方程LYbAXbLUXbUXY;用于求1122.nnALUL UUu uu。克罗特分解:11()()ALU
3、LDDULDD U,下三角阵和单位上三角阵的乘积。将杜立特尔分解或克罗特分解应用于三对角方程,即为追赶法。对称正定矩阵的乔列斯基分解,TAGG,下三角阵及其转置矩阵的乘积;用于求解AXb的平方根法。改进平方根法:利用矩阵的TALDL分解。4.舍入误差对解的影响精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 1 页,共 11 页向量范数定义:常用的向量范数:矩阵的范数:常用的矩阵范数:矩阵范数与向量范数的相容性:影响:()1xbAkAxbAkA,其中1( )cond AkA A,k 值大, 病态问题。第三章:插值法1.定义给定 n+1 个互不相同的点
4、,xi 及在 xi 处的函数值yi(i=0 n),构造一个次数不超过n 次的多项式:20111( ).nnPxaa xa xa x,使满足( )niiP xy。取( )( )nf xP x。称( )nP x为插值多项式,ix为插值节点,( )f x为被插函数。插值问题具有唯一性。2.Lagrange插值多项式表达式:误差估计式:3.Newton插值多项式差商:表达式:误差表达式:差商的性质:1)差商与节点的次序无关;2)K 阶差商对应K阶导数;3) 4) 5) 4.埃尔米特(带导数)插值多项式1)Newton 法,给定f 及 f(k)为数字;2)Lagrange 法,给定f 及 f(k)为表达
5、式。5.三次样条插值函数分段三次插值多项式的定义:S(x)在子区间 xi-1,xi上是三次多项式,S(xi)=yi,s(x)在a,b上连续。三次样条插值函数的导出:精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页,共 11 页第四章:函数最优逼近法1.最优平方逼近对于广义多项式:001122( )( )( )( ).( )nnP xcxcxcxcx,其中( )ix线性无关。要求:若 f(x)是表格函数, 确定 P(x)称为最小二乘拟合函数,当( )iixx,P(x)为最小二乘多项式;若 f(x)是连续函数,称P(x)为最优平方逼近函数。2.函
6、数的内积,范数定义及其性质内积的定义:性质:范数的定义:范数的性质:正规方程组或法方程组:3.正交多项式正交函数系的定义:代入正规方程组的系数矩阵,则:几个正交多项式举例:1)勒让德多项式2)拉盖尔多项式3)埃尔米特多项式4)切比雪夫多项式四种正交多项式均可用于高斯型求积公式;P 多项式用于最优平方逼近,T多项式用于最优一致逼近。正交多项式的性质:1)正交多项式( )kg x线性无关,推论:( )()kP x kn与( )ng x正交。2)在区间 a,b或min(xi),max(xi) 上, n 次正交多项式gn(x)有 n 个不同的零点。3)设( )kg x是最高次项系数为1 的正交多项式,
7、则:4.最优一致逼近法(1)切比雪夫多项式的性质精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页,共 11 页性质 1:( )kT x是-1,1上关于21( )1xx的正交多项式,00(,),(,)/ 2kkT TT T;性质 2:11( )2( )( )kkkTxxT xTx;性质 3:( )kT x是最高次项为12kkx的 k 次多项式,2( )kTx只含 x 的偶次项,21( )kTx只含x 的奇次项;性质 4:( )kT x有 k 个不同的零点,21cos,0,1.12iixikk;性质 5:在 -1,1上,( )1kTx,且在 k+
8、1 个极值点cos,0,1.iixikk处( )kTx依次取得最大值 1 和-1;性质 6:设 Pn(x)是任意一个最高次项系数为1 的 n 次多项式,则:11111111max( )max( )22nnnnxxPxTx(2)最优一致逼近法的定义设函数 f(x)在区间 a,b连续, 若 n次多项式001122( )( )( )( ).( )nnnP xcxcxcxcx使max( )( )nnax bPfP xf x达到最小,则称( )nPx为( )f x在a,b上的最优一致逼近函数。切比雪夫定理: n 次多项式P(x)成为函数y=f(x)在区间 a,b上最优一致逼近多项式的充要条件是 误 差(
9、)()()R xfxP x在 区 间 a,b 上 以 正 负 或 负 正 交 替 的 符 号 依 次 取 得max( )a x bER x的点(偏差点)的个数不少于n+2。采用如下方程组进行求解:(3)近似最优一致逼近多项式思路:使用 T 多项式性质6 若区间是 -1,1,取 xi(i=0 n)为 Tn+1的零点,则21cos(),02(1)iixinn,以此构造插值多项式Pn(x);若区间是 a,b,通过转换,-1,122abbaxt t;方法 1:由21cos(),02(1)iitinn,构造 Pn(t),然后将2xabtba代入 Pn(t),可精选学习资料 - - - - - - - -
10、 - 名师归纳总结 - - - - - - -第 4 页,共 11 页得 Pn(x)。方法 2:取21cos22222(1)iiabbaabbaixtn,i=0n;构造 Pn(x)。例:(4)截断切比雪夫级数法设 f(x)在-1,1 上连续,0( )( )nkkkS xC Tx,其中(,)(,)kkkTk fCT T;记0( )( )nnkkkS xC Tx;应用切比雪夫定理及性质5,取0( )( )( )nnkkkfxS xC Tx。(5)缩短幂级数法方法 1:方法 2:第五章:数值微积分第一节 牛顿柯特斯公式( ) 1()( ) ( )( )( )( )bbxaaI fx f x dxf
11、x dxF bF a一数值算法1.数值积分算法对于复杂函数f(x),考虑用其近似函数P(x)去逼近,用P(x)的积分值近似代替f(x)积分值。2.插值型数值积分方法对于拉格朗日插值多项式,广义积分中值定理:若f(x)在a,b上连续, g(x)在a,b上部变号,则,a b,使( ) ( )( )( )bbaaf x g x dxfg x dx3.牛顿柯特斯公式梯形公式:辛普森公式:二复化求积公式精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页,共 11 页1. ( )( )baI ff x dx,把a,b分成若干等长的小区间,在每个小区间用简单
12、低次数值积分公式,在将其得到的结果相加。2.复化梯形公式3.复化辛普森公式三变步长的积分公式1.先取一步长h 进行计算, 再取较小步长h*计算, 若两次结果相差很大,则在取更小步长进行计算,依次进行,直到相邻两次计算结果相差很大,则取较小步长的结果为积分近似值。2.变步长复化梯形公式3.变步长复化辛普森公式四龙贝格积分法第二节 待定系数法1.代数精度定义对于近似公式( )( )IfQ f,如果f(x)是任意不超过m 次的多项式,( )()I fQ f成立,而对于某个m+1 多项式,( )()I fQ f,称代数精度为m 次。2.判定方法近似式的代数精度为m 次对( )1, ,.,mf xxx,
13、 近 似 式 精 确 成 立 ,()( )I fQ f,1( )mf xx时 不 成 立 ,()()I fQ f。梯形公式m=1,辛普森公式m=3。3.Peano 定理精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页,共 11 页第三节 高斯型积分公式一定义节点个数一定,具有最高阶代数精度公式的插值型积分公式称为Guass型求积公式。插值型积分公式定义:定理:数值积分公式()( )I fQ f至少有 n 次代数精度近似式是插值型积分公式。对于牛顿科特斯公式,若采用等距节点,n 分别为奇数和偶数时,代数精度分别为n 和 n+1。二最高代数精度定
14、理:21mnSo,给定 n+1 个节点, 具有 2n+1 次代数精度的插值型数值积分公式称为Gauss型求积公式。三 Gauss型积分公式的构造方法方法 1:代数精度为2n+1,则( )1, ,.,mfxxx时成立,可解出iA和ix。方法 2:定理:代数精度21mnix是a,b上关于( )x的正交多项式1( )ngx的零点 (高斯点 ),其中( ) ( )biiaAx l x dx。四高斯型求积公式的误差五常用的高斯型求积公式1.Gauss-Legendre求积公式101( )( )( )niiif x dxA f xQ f,ix是1( )nPx的 n+1 个零点。n=0 n=1 2.Gaus
15、s-Laguerre求积公式00( )( )( )nxiiief x dxA f xQ f000( )( )( )xxxf x dxee f x dxe F x dx精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 7 页,共 11 页()00( )()( )xa tataef x dxef at dxee F t dt3.Gauss-Hermite 求积公式20( )( )( )nxiiief x dxA f xQ f4.Gauss-Chebyshev求积公式1201( )21(cos)1221nif xidxfnnx第四节 数值微分0()( )(
16、 )limhf xhf xfxh,h 大,不精确,h 小,由于小除数引入大误差。近似函数法取等节距节点,0,0,1,.ixxih in(1)一阶导数, n=1,两个节点0x1x(2)一阶导数, n=2,三个节点0x1x2x(3)二阶导数, n=2,三个节点0x1x2x实用误差估计例:精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页,共 11 页第六章 非线性方程的迭代解法第一节 方程求根法根的定义:对于非线性方程组f(x)=0,若存在数使 f()=0,称是非线性方程组f(x)=0的根。零点存在定理: 若 f(x)是闭区间 a,b上的连续函数,
17、若 f(a)f(b)0,则必然存在 , a b,使f()=0。试探法,二分法。一简单迭代法初值0x,1()kkxx,产生迭代序列kx。简单迭代收敛定理(压缩映像原理)对于迭代函数( ) x, 若满足 (1)若 , ,( ) , xa bxa b; (2)存在正数0L1,超线性收敛;P=2,平方收敛。定理:设是方程( )xx的根,如果迭代函数( ) x满足(1)()()( ).()0,()0PP1()kkxx产生的迭代序列kx是 P阶收敛。二牛顿迭代法1()()kkkkf xxxfx收敛性分析:牛顿迭代法具有局部收敛性,初值0xx,产生迭代序列收敛。收敛定理:设f(x)在a,b上二阶导数存在,若
18、( ) ( )0f a f b,( )f x在a,b上单调,( )f x在a,b上凹向不变 (即( )fx在区间上不变号) ,初值0x满足00()()0f xfx,则任意初值0 , xa b,有牛顿迭代法产生的kx收敛于方精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页,共 11 页程的唯一根。简化牛顿法:1110()()()()()kkkkkkkkkkf xf xf xxxxxxxfxfxC三弦割法或割线法用差商代替导数111()()()kkkkkkkf xxxf xf xxx第二节 线性代数方程组迭代解法Jacobi迭代法, Gauss-
19、Seidel迭代法SOR迭代法(11(1)kkkiiGSxxx)2211()optjB迭代法的收敛性:将迭代法用矩阵表示:ADEF,1kkxBxgJacobi迭代法:G-S迭代法:SOR迭代法:定理:1kkxBxg,对0x产生的迭代序列kx收敛的充要条件是:lim0kkB或()1B。推论 1:若1B,则收敛;推论 2: SOR方法收敛的必要条件是02;推论 3:设 A 是严格对角占优矩阵,则Jacobi,G-S,01的 SOR方法收敛;推论 4: 1)设 A 是对称正定矩阵,则G-S方法收敛; 2) 设 A 是对称正定矩阵,若2D-A 也对称正定,则Jacobi方法收敛;若2D-A 不对称正定
20、,则Jacobi方法不收敛; 3) 设 A 是对称正定矩阵,02,则 SOR方法收敛。第三节 非线性方程组的迭代解法11()()kkkkxxfxf x第七章 矩阵特征值和特征向量矩阵 A 主特征值模最大的特征值取为主特征值。对 n 个互不相同的特征值123.n,对应特征向量123n;任意向量01 122.nnzccc0kkzA Z精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页,共 11 页111klimkkzc,kz是对应 A 的1的特征向量,11()()kikizz规范乘幂法1kkyAz,ky按模取最大分量maxkkym,kkkyzm。
21、01limkkz,01是1的规范化向量;1limkkm。加速法(原点位移法)1kkyApI z第八章 常微分方程数值解法的导出0( )( , ( )( )y xfx y xy ay一数值微分法欧拉公式:1(,)iiiiyyhf xy后退欧拉公式:111(,)iiiiyyhfxy终点法:112(,)iiiiyyhfx y局部截断误差:21()( )2iihy xyy二数值积分法111(,)(,)2iiiiiihyyf x yf xy预估1( ,)iiiiyyhf x y,校正111(,)(,)2iiiiiihyyf x yf xy三泰勒展示法四线性多步法精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页,共 11 页