数值计算方法总结ppt课件.ppt

《数值计算方法总结ppt课件.ppt》由会员分享，可在线阅读，更多相关《数值计算方法总结ppt课件.ppt（71页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、数值计算方法总结数值计算方法总结 数值计算方法的一般概念数值计算方法的一般概念 解线性代数方程组的直接法解线性代数方程组的直接法 插值法与最小二乘法插值法与最小二乘法 数值微积分数值微积分 方程与方程组的迭代解法方程与方程组的迭代解法第第1章章 数值计算方法的一般数值计算方法的一般概念概念n定义定义 算法是指由基本算术运算及运算顺序的规定构成算法是指由基本算术运算及运算顺序的规定构成的完整的解题步骤的完整的解题步骤. .1.1 1.1 算法算法n描述描述 算法可以使用框图、算法语言、数学语言、自然算法可以使用框图、算法语言、数学语言、自然语言来进行描述。语言来进行描述。n具有的特征具有的特征

2、正确性、有穷性、适用范围广、运算工作量少、正确性、有穷性、适用范围广、运算工作量少、 使用资源少、逻辑结构简单、便于实现使用资源少、逻辑结构简单、便于实现 计算结果可靠计算结果可靠第第1章章 数值计算方法的一般数值计算方法的一般概念概念l 稳定性稳定性 计算过程中的误差能得到控制，各步误差对计算计算过程中的误差能得到控制，各步误差对计算结果不致产生过大的影响结果不致产生过大的影响1.1 1.1 算法算法 计算机的计算结果通常是近似的，因此算法必有误差，并且计算机的计算结果通常是近似的，因此算法必有误差，并且应能估计误差。应能估计误差。l 收敛性收敛性 通过增加计算量，能使近似计算解充分接近理论

3、通过增加计算量，能使近似计算解充分接近理论解解第第1章章 数值计算方法的一般数值计算方法的一般概念概念1.2 1.2 误差误差n定义定义 误差是指近似值与真正值之差误差是指近似值与真正值之差 误差分类误差分类模型误差模型误差在建立数学模型时，忽略次要因素而造成的在建立数学模型时，忽略次要因素而造成的数据误差数据误差由于问题中的值通过观察得到的，从而产生误差由于问题中的值通过观察得到的，从而产生误差截断误差截断误差通过近似替代，简化为较易求解的问题通过近似替代，简化为较易求解的问题计算误差计算误差由于计算机中数的位数限制而造成的由于计算机中数的位数限制而造成的第第1章章 数值计算方法的一般数值计

4、算方法的一般概念概念1.2 1.2 误差误差n绝对误差绝对误差 绝对误差：是指近似值与真正值之差或差的绝对绝对误差：是指近似值与真正值之差或差的绝对值，即值，即x设设x为真值为真值, ,为真值的近似值为真值的近似值xx xx ,或 绝对误差界：用一个满足绝对误差界：用一个满足 的数的数 , ,来表示来表示绝对误差的大小，并记为绝对误差的大小，并记为 第第1章章 数值计算方法的一般数值计算方法的一般概念概念1.2 1.2 误差误差n相对误差相对误差 相对误差：是指近似值与真正值之比或比的绝对相对误差：是指近似值与真正值之比或比的绝对值，即值，即 相对误差界：用一个满足相对误差界：用一个满足 的数

5、的数 , ,来表示来表示相对误差的大小，并记为相对误差的大小，并记为 相对误差界常用百分数表示相对误差界常用百分数表示第第1章章 数值计算方法的一般数值计算方法的一般概念概念1.2 1.2 误差误差n准确数字准确数字 各位数字皆准确的近似数称为有效数.此时各准确数字也称为有效数字第第1章章 数值计算方法的一般数值计算方法的一般概念概念1.2.3 1.2.3 数据误差影响的估计数据误差影响的估计第第1章章 数值计算方法的一般数值计算方法的一般概念概念1.2.3 1.2.3 数据误差影响的估计数据误差影响的估计12n12n (xxx (xxxy iiiiiiiiixxxxxxxxxni=1ni=1

6、在误差估计式(1-1),(1-2)中,.,) y ,.,) 或表示解的误差相对参量 的误差的放大或缩小倍数 这些系数的绝对值称为求y问题的条件数条件数，其值很大时的问题称为坏条件问题坏条件问题或病态问题病态问题 凡是计算结果接近于零的问题往往是病态问题。凡是计算结果接近于零的问题往往是病态问题。 应避免相近数相减应避免相近数相减, ,小除数和大乘数小除数和大乘数第第1章章 数值计算方法的一般数值计算方法的一般概念概念1.2.3 1.2.3 数据误差影响的估计数据误差影响的估计212212122212122222(1 1)xxxxxxxxxxxxxxxxx112112112112112112由误

7、差估计式可知(xxx(xxx(xxx(xxxxx(xx(xx 1)21)2xxx(x(x第第2章章 解线性代数方程的直接法解线性代数方程的直接法求解求解n n阶线性代数方程组阶线性代数方程组11 11221121 1222221 122 (2-1)nnnnnnnnnna xa xa xba xa xa xba xa xa xb写成矩阵形式为写成矩阵形式为 (0)AxbA111212122212 nnnnnnaaaaaaAaaa其中12 nxxxx12 nbbbb直接法指的是不计舍入误差时直接法指的是不计舍入误差时, ,通过有限次算术运算能求得准确解的方法通过有限次算术运算能求得准确解的方法 第

8、第2章章 解线性代数方程的直接法解线性代数方程的直接法2.1 2.1 高斯消去法高斯消去法2.1.1 2.1.1 基本步骤基本步骤高斯消去法步骤高斯消去法步骤1.1.消去消去 经过经过n-1n-1步将方程组化为同解的上三角形方程组步将方程组化为同解的上三角形方程组11221,1 nnaaa第一步消去下方元素,第二步消去下方元素,.,第n-1步消去下方元素2.2.回代回代 按相反顺序求解上三角形方程组按相反顺序求解上三角形方程组, ,得到方程组的解得到方程组的解11 nnxxx第一步得到 ,第二步得到,.,第n步得到将方程组写成增广矩阵的形式将方程组写成增广矩阵的形式, ,将有利于计算机实现将有

9、利于计算机实现 AA b第第2章章 解线性代数方程的直接法解线性代数方程的直接法2.1 2.1 高斯消去法高斯消去法2.1.2 2.1.2 运算量估计运算量估计高斯消去法运算量估计高斯消去法运算量估计1.1.消去算法运算量消去算法运算量3211 -1,-:,1-,5()(11)326nknkn knkknnnNnk nk 分为步 第 步变换行 求倍数 再从个元素中减去第 行对应列的倍数 因此所需乘除次数: 2.2.回代运算量回代运算量-112 1,11,.,-11,(1)12.2nnxxxnn nNn 求 需做 次除法 求需做 次乘法和 次除法求 需次乘法和 次除法 因此所需乘除次数: 321

10、2 33nnNNNn因此,3 ()o n即,运算量为第第2章章 解线性代数方程的直接法解线性代数方程的直接法2.1 2.1 高斯消去法高斯消去法2.1.3 2.1.3 选主元技术选主元技术1,.,kkkknkpkkkaaaapk 为避免出现小主元 在第 步的第 列的元素中选出绝对值最大的元素然后交换第 行和第 行 继续进行消去过程 这种消去法称为列主元消去法 选主元方法分为行主元法与全主元法第第2章章 解线性代数方程的直接法解线性代数方程的直接法2.2 2.2 三角分解法三角分解法2.2.1 2.2.1 杜里特尔分解法杜里特尔分解法 高斯消去法的消去过程高斯消去法的消去过程, ,实质上是把系数

11、矩阵实质上是把系数矩阵A A分解为单位下三角矩分解为单位下三角矩阵阵L L与上三角矩阵与上三角矩阵R R的乘积的乘积, ,并且求解方程组并且求解方程组Ly=bLy=b的过程的过程, ,回代过程是求解回代过程是求解上三角形方程组上三角形方程组Rx=yRx=y11,1,.,1iijijikkjkral rji jn11()/,1,.,ijijijk kiiiklal rrjin 111112121313111121212212232322223131323233333333112233,()()()()( )()()()()()()()()()() ()()()()()nnnnnnnnnnnnnn

12、nnnnLRArarararay blarararay blalararay blalalaray b实际计算时 可以将 和 共同存放到增广矩阵 的位置上第第2章章 解线性代数方程的直接法解线性代数方程的直接法2.2 2.2 三角分解法三角分解法2.2.1 2.2.1 杜里特尔分解法杜里特尔分解法 分解分解A=LR,A=LR,且且L L为单位下三角阵为单位下三角阵,R,R为上三角阵为上三角阵, ,称为杜里特尔称为杜里特尔(Dollittlse)(Dollittlse)分解分解. . 使用杜里特尔分解求解方程组使用杜里特尔分解求解方程组Ax=bAx=b或或L(Rx)=b,L(Rx)=b,相当于求

13、两个方程组相当于求两个方程组 Ly=b, Rx=yLy=b, Rx=y运算量运算量3232211 (),(),321(),233ALRnnLybnnnnRxynnNn分解需次 解需次解需次 共第第2章章 解线性代数方程的直接法解线性代数方程的直接法2.2 2.2 三角分解法三角分解法2.2.2 2.2.2 克洛特分解法克洛特分解法此分解称为克洛特此分解称为克洛特(Crout)(Crout)分解分解 AAR,RL对 进行杜里特尔分解时, =L为单位下三角阵, 为上三角阵1122 DR(,.,)nnDdiag rrr令 为 的对角元所构成的对角阵 -1 ()()ALRLD D R11111122

14、(,.,)nnDdiag rrr则 计算公式计算公式1111 ,1,., ()/ 1,2,.,1ijijijk kikiijijikkjiiklal rji inral rljiin 第第2章章 解线性代数方程的直接法解线性代数方程的直接法2.2 2.2 三角分解法三角分解法2.2.3 2.2.3 追赶法追赶法111122223331111 nnnnnnnbcdabcdabcdAA babcdabd11122223333111111111nnnnnnnlryalryalryAalryaly 作克洛特分解第第2章章 解线性代数方程的直接法解线性代数方程的直接法2.2 2.2 三角分解法三角分解法

15、2.2.3 2.2.3 追赶法追赶法1111 ,/b ydl1因此,可得 l11111/, ()/ , 2,3,.,iiiiii iiiiiircllba ryda ylin1 ,1,.,1nniiiixyxyrxin回代得到, ,iiir l y 按以上公式求解Ax=b的方法称为追赶法其中计算的过程称为追 回代和过程称为赶 计算量估计:共需要的乘除法次数为5n-4.第第2章章 解线性代数方程的直接法解线性代数方程的直接法2.2 2.2 三角分解法三角分解法2.2.4 2.2.4 平方根法平方根法 AAxb对于求解 为正定矩阵的方程组121/2111() ()/, 1,., ,1,.,iiii

16、iikkijijijk ikiiklallal iljin in 计算公式A即 可分解为下三角阵及其转置矩阵的乘积()TALD L则由于A的各阶顺序主子式大于0,则A可作克洛特分解 且L的对角元全为正数121211112222(,.,)()()()nTTTDdiagdddALD DLLDLDLL令则 第第2章章 解线性代数方程的直接法解线性代数方程的直接法2.3 2.3 舍入误差对解的影响舍入误差对解的影响2.3.1 2.3.1 向量和矩阵的范数向量和矩阵的范数121222 1/21221 () maxnnii nxxxxxxxxxx 常用的向量的范数有三种:1212 ( ,.,) ,( )(

17、 ,.,)Tnnxx xxxxxx xx对向量具有如下类似性质的函数 向量 的范数或 称为模或长度 (1) =0, ,0 (2) , (3) : xxxxxyxy 性质: 非负性:齐次性:对任意实数三角不等式第第2章章 解线性代数方程的直接法解线性代数方程的直接法2.3 2.3 舍入误差对解的影响舍入误差对解的影响2.3.1 2.3.1 向量和矩阵的范数向量和矩阵的范数 ( )AA对n阶矩阵A,具有如下4种性质的函数 称为矩阵A的范数 (1) 0 =0, 0,0 (2) , (3) : (4) AAAAABABABA B 性质: 非负性:齐次性:对任意实数三角不等式111112 max,1 m

18、ax, (),nijjninijinjTAaAaAA A 常 用 矩 阵 范 数 :称 为 范 数称 为 无 穷 大 范 数称 为 谱 范 数第第2章章 解线性代数方程的直接法解线性代数方程的直接法2.3 2.3 舍入误差对解的影响舍入误差对解的影响2.3.1 2.3.1 向量和矩阵的范数向量和矩阵的范数21/ 211 ()nnijFijAa 矩 阵 的 F范 数 (Frobenius):1 (1) (2) I11 (3) 1, ()1AxA xIBIBIBB矩阵范数还具有以下性质: 单位矩阵 的范数当时可逆 且第第2章章 解线性代数方程的直接法解线性代数方程的直接法2.3 2.3 舍入误差对

19、解的影响舍入误差对解的影响2.3.2 2.3.2 舍入误差对解的影响舍入误差对解的影响,Axbxxb 直 接 法 解 线 性 方 程 组由 于 舍 入 误 差 的 存 在 ,只 能得 到 近 似 解,或 者 是 A的 精 确 解1-, 1(),AbAAAbbbxbAkAxbAkAkcond AAAAxb近 似 矩 阵和 近 似 向 量的 误 差 为 则 可 以 得 到其 中称 为 方 程 组的 条 件 数k条 件 数很 大 的 方 程 称 为 病 态 方 程 组k值 比 较 小 的 方 程 组 称 为 良 态 方 程 组第第3章章 插值法与最小二乘法插值法与最小二乘法( ) 0,1,.,iiy

20、f xin数个点处数 已知函y =f(x)在n+1互不相同的的函值3.1 3.1 拉格朗日插值法拉格朗日插值法3.1.1 3.1.1 插值多项式的概念插值多项式的概念2012( ) ( ) (3-2)nnnyf xpxaa xa xa x为数选项求函的近似值,用n次多式( ) ( ) 0,1,., (3-3)nniipxpxyin满条使足件 使用以上方法求函数近似式的方法称为使用以上方法求函数近似式的方法称为插值法插值法 满足条件满足条件(3-3)(3-3)的插值多项式是存在且唯一的的插值多项式是存在且唯一的第第3章章 插值法与最小二乘法插值法与最小二乘法01(1)( ),.,1,( )( )

21、( ) ( )( )( )( )(1)!nnnnnyf xx xxa bna bxf xpxfR xf xpxxn 如果被插函数在包含节点的区间上存在阶导数,则在区间上的任意点 处,被插函数与插值多项式的误差3.1 3.1 拉格朗日插值法拉格朗日插值法3.1.2 3.1.2 插值多项式的截断误差插值多项式的截断误差0101 ( )()()() ,.,nnxxxxxxxxx xx 其中为介于 与节点之间 这种误差不考虑舍入误差，称为这种误差不考虑舍入误差，称为截断误差截断误差第第3章章 插值法与最小二乘法插值法与最小二乘法3.1 3.1 拉格朗日插值法拉格朗日插值法3.1.3 3.1.3 拉格朗

22、日插值多项式拉格朗日插值多项式000( )( )nnnjniiiiijijj ixxL xl x yyxx ( ),( ) ( )( -)( )iiiinl xxl xx xx 这里 次式称为拉格朗日插值基函数 简写为01011( )()()(), ( )()()()()niiiiiiinxxxxxxxxxxxxxxxx其中第第3章章 插值法与最小二乘法插值法与最小二乘法3.1 3.1 拉格朗日插值法拉格朗日插值法3.1.3 3.1.3 拉格朗日插值多项式拉格朗日插值多项式0110101101,-( )( )nx xx xf xL xyyxxxx特例 当时 有 1011( )( )( -)(

23、-)2R xfx xx x 02122010102101201220212,( -)( -)( -)( -)( )( )()()()()( -)( -) +()()nx xx xx xx xf xL xyyxxxxxxxxx xx xyxxxx 当时 有 20121( )( )( -)( -)( -)6R xfx xx xx x 第第3章章 插值法与最小二乘法插值法与最小二乘法3.1 3.1 拉格朗日插值法拉格朗日插值法3.1.3 3.1.3 拉格朗日插值多项式拉格朗日插值多项式计算插值多项式的值计算插值多项式的值 若计算的插值点在节点之外若计算的插值点在节点之外, ,则称为则称为外推或外插外

24、推或外插 若计算的插值点在节点之间若计算的插值点在节点之间, ,则称为则称为内插内插内插的误差较小内插的误差较小, ,外插的误差较大外插的误差较大, ,误差公式由误差公式由R(x)R(x)得到得到第第3章章 插值法与最小二乘法插值法与最小二乘法3.2 3.2 添节点与导数的插值法添节点与导数的插值法3.2.1 3.2.1 牛顿插值多项式牛顿插值多项式为使其满足插值条件为使其满足插值条件(3-3),(3-3),只需满足方程组只需满足方程组00011011022012022021010201011()()(-)()(-)(-)(-)()(-)(-)(-) (-)(-)(-)nnnnnnnnnnnn

25、nnyNxcyNxcc xxyNxcc xxc xxxxyNxcc xxc xxxxcxxxxxx因此因此, ,可得可得000()cyf x 第第3章章 插值法与最小二乘法插值法与最小二乘法3.2 3.2 添节点与导数的插值法添节点与导数的插值法3.2.1 3.2.1 牛顿插值多项式牛顿插值多项式012120110012012(,.,)( ,.,)(,.,) (,.,)( ),.,iiiiiiicf x x xxf x xxf x xxxxf x x xxyf xx x xxi 同理可得 称为在处的 阶差商001010120101011( )()(,)()(,)()() (,.,)()()()

26、nnnNxf xf x xxxf x x xxxxxf x xxxxxxxx 于是得到 称为牛顿(Newton)插值多项式第第3章章 插值法与最小二乘法插值法与最小二乘法3.2 3.2 添节点与导数的插值法添节点与导数的插值法3.2.1 3.2.1 牛顿插值多项式牛顿插值多项式01( )( )( ) (,., ) ( )nnnR xf xNxf x xxxx 011(,.,) ( ) nnf x xxxx01011(,., )(,.,)nnnf x xxxf x xxx假定1( )( )nnNxNx1( )1( )nnNxnNx 因此,牛顿插值多项式的截断误差约等于牛顿插值次式增加的项0011

27、01221201233231230123()()(,)()( ,)(,)()(,)( ,)(,)xf xxf xf x xxf xf x xf x x xxf xf x xf x x xf x x x x差商表差商表第第3章章 插值法与最小二乘法插值法与最小二乘法3.2 3.2 添节点与导数的插值法添节点与导数的插值法3.2.2 3.2.2 逐次线性插值法逐次线性插值法(1)( )( )( ) ( )( )( )( )(1)!nnnxf xfR xf xpxxnn 多项式插值式项式p与被插函数的误差为0,1*121,( ),.,( ),.,nnnnpxx xxpxx xx假设是以为节点的插值多

28、项式 是以为节点的插值多项式*001*110( )( ) ( )( )()( )( ) ( )( )() (3-5)nnnnnnnnnpxpxf xpxxxxxpxpxf xpxxxxx因此得到估计式*001( )( )( ) ( )( )() nnnnpxpxf xf xpxxxxx因此得到更好的近似式第第3章章 插值法与最小二乘法插值法与最小二乘法3.2 3.2 添节点与导数的插值法添节点与导数的插值法3.2.2 3.2.2 逐次线性插值法逐次线性插值法111-1-1-1,.,( ),( )( ) ( )( )()iiiikkiiiikkkkikikixxxNxNxNxNxNxxxxx 假

29、设节点为的插值多项式为则此方法称为列维尔(Neville)逐次线性插值法0000101011210202123210303123( )( )( )( )( )( )( )( )( )( )xNxyxNxyNxxNxyNxNxxNxyNxNxNx列维尔算法表列维尔算法表第第3章章 插值法与最小二乘法插值法与最小二乘法3.2 3.2 添节点与导数的插值法添节点与导数的插值法3.2.3 3.2.3 带导数的插值多项式带导数的插值多项式( )1,( ),( )()nyf xnnHxf xHermite 如果已知被插函数在节点处的函数值和导数值共个值则在这些节点处函数值和导数值等于已知值的 次多项式称为

30、的带导数插值多项式或埃尔米特插值多项式()( )1),.,1,.,.()1(,.,)!iriiiiiiiiiiikiiiixyyyyxrxxxxfxkkf xxxk求解方法有两种( 已知节点 处函数值与导数值时 把视为重节 点直接应用牛顿插值法 此时个重节点的 阶差商应为(2)仿效拉格朗插值多项式的导出法第第3章章 插值法与最小二乘法插值法与最小二乘法3.3 3.3 分段插值与样条函数插值法分段插值与样条函数插值法3.3.1 3.3.1 高次插值多项式的缺陷高次插值多项式的缺陷(1)( ) ( )( )( )( )(1)!nnnfR xf xpxxn 插值多项式的误差公式(1)( )( ),n

31、fx由于与与有关 因此,其绝对值不一定随次数n的增大而减小插值多项式的与原函数在插值点处误差较小,但在其它点处误差很大,出现龙格现象第第3章章 插值法与最小二乘法插值法与最小二乘法3.3 3.3 分段插值与样条函数插值法分段插值与样条函数插值法3.3.2 3.3.2 分段低次插值法分段低次插值法012-1*11-1-11., , ,( )( )( -)niiiiiiiiaxxxxba bnxixxyyf xp xyx xxx 设则节点把分成 个小区间当插值点在第 个小区间上时 采用一次插值分式 此方法称为分段线性插值法*1-11( )( )( )( -)( -)2iif xp xfx xx x

32、其截断误差为 22-1-1*21( )11( -)( -)(-)441( )( )8iiiiiixx xx xxxhf xp xh2i-1i设a,b上 fM ,则在x,x 上 则 *11max0,( )( )ii nhhp xf x 当收敛于被插函数第第3章章 插值法与最小二乘法插值法与最小二乘法3.3 3.3 分段插值与样条函数插值法分段插值与样条函数插值法3.3.3 3.3.3 三次样条函数插值法三次样条函数插值法 为保证插值函数及其导数在插值区间内处处充分接近被插函数,需要使用样条函数作插值函数01-1( ),(.), , -1iniimS xx axxxbxxma bm 次样条函数是一

33、种分段函数 在节点分成的每个小区间上是 次多项式 而在整个区间上为阶导数连续-1,iixx 常用的样条函数为三次样条函数,在区间上是3次多项式m (1) 表达式12211122111( ),( ),( )(12)()(12)() ()()()()iiiiiiiiiiiiiiiiiiiiiiiiS xy S xm hxxxxxxxxxxS xyyhhhhxxxxxxmxxmhh设则有第第3章章 插值法与最小二乘法插值法与最小二乘法3.3 3.3 分段插值与样条函数插值法分段插值与样条函数插值法3.3.3 3.3.3 三次样条函数插值法三次样条函数插值法 (2)M表达式33112211111 (

34、)()()6 ()() ,66iiiiiiiiiiiiiiiiiS xxx MxxMhhxxhxxyMyMxxxhh1( ),( ),iiiiiiS xy SxM hxx 设( )iS xM 利用的导数的连续性推出满足的方程11111111162iiiiiiiiiiiiiiiiihhyyyyMMMhhhhhhhh1111111116,1,6 (,)iiiiiiiiiiiiiiiiiiihhyyyydf xx xhhhhhhhh ii记 11-1 2 1,., -1iiiiiiMnMMMdini则满足个方程 此方程组称为三弯矩方程组第第3章章 插值法与最小二乘法插值法与最小二乘法3.3 3.3

35、分段插值与样条函数插值法分段插值与样条函数插值法3.3.3 3.3.3 三次样条函数插值法三次样条函数插值法样条插值函数样条插值函数优点优点: :在节点加密时在节点加密时, ,它和它的导函数能在整个插值区间上它和它的导函数能在整个插值区间上 充分靠近被插函数充分靠近被插函数缺点缺点: :为求为求M M或或m m表达式表达式, ,需形成方程组并进行求解需形成方程组并进行求解第第3章章 插值法与最小二乘法插值法与最小二乘法3.4 3.4 最小二乘法最小二乘法2211( )( ),1,2,.,( )( ),( )( ),1,2,.,( )iiiiiimmiiiiiyf xmyf ximf xp xp

36、 xyp xy imSp xy 假定观测得到的函数的 个函数值 求的简单近似式使与 的差的平方和最小 即 使最小( ) ( ), ( )p xmyp xxyf x 称为 个数据的最小二乘拟合函数近似反映变量 与 之间的关系 称为经验公式称为被拟合的函数001122( )( )( )( )( )( ),( )nniip xp xcxcxcxcx nmxcS 最小二乘拟合函数可写为 其中 应适当选取且线性无关在此表示式中,求系数 使残差平方和 最小第第3章章 插值法与最小二乘法插值法与最小二乘法3.4 3.4 最小二乘法最小二乘法01111102122201()()()()()(),()()(),

37、 nnmmnmnTTTTxxxyxxxyyxxxyAbycy 若记 由于则正规方程组可写为 说明A为对称阵,且为正定阵,正规方程组必有唯一解01021112( )(0,., ),( )., iiiiiiiiijnjnniniinnnnnixxjnp xcc xc xmxxycxxxx yccxxxx y 当最小二乘拟合函数称为最小二乘拟合多项式 正规方程组为第第3章章 插值法与最小二乘法插值法与最小二乘法拉格朗日插值多式项牛顿插值多项式高次多项式插值逐次线性插值多项式拟合法埃尔米特插值多项式插值法 三次样条函数插值法低次多项式插值B样条函数插值法逼近法 最小二乘法第第4章章 数值微积分数值微积

38、分( )( ) ( ):( )( ) , ,( ),( )0,( )1( ),baI fx f x dxxf xa bxxxf x 讨论以下积分的方法 其中和是区间上的已知函数 称为权函数通常 积分被积函数 假定充分可导4.1 4.1 数值积分法数值积分法第第4章章 数值微积分数值微积分4.1 4.1 数值积分法数值积分法4.1.1 4.1.1 近似函数积分法近似函数积分法1 ( )( )( )()( ),nniiif xLxl x f xx 由拉格朗日插值法两边同乘然后积分 得到插值型求积公式1()( )( )() (4-2),( ) ( )nbiiaiiibiiaIfx f x dxA f

39、 xQ fxAAx lx dx 其中称求积节点称为求积系数 (1)(4 - 2) -( )( ) -( )1 ( )( )( )(1)!bnabnaR fI fQ fxf xLxdxxfx dxn 求积公式的截断误差第第4章章 数值微积分数值微积分4.1 4.1 数值积分法数值积分法4.1.1 4.1.1 近似函数积分法近似函数积分法( )1,x 常用数值积分公式是权函数等矩节点时的求积公式-,0,1,., ,ibaxaih in hhn 称为步长301(1)1,-()(),( )212nhbahhI ff xf xR ff 梯形求积公式 公式(4-2)称为牛顿-柯特斯(Newton-cote

40、s)求积公式0125(4)(2)2,(-) / 2()4()()3 ( )90nhbahI ffxfxfxhR ff 辛浦生(Simpson)或抛物线求积公式 第第4章章 数值微积分数值微积分4.1 4.1 数值积分法数值积分法4.1.1 4.1.1 近似函数积分法近似函数积分法01235(4)(3)3,(-) / 33()3()3()()83 ( )80nhbahI ff xf xf xf xhR ff 牛顿求积公式 012347(6)(4)4,(-) / 427()32()12()32()7()458 ( )945nhbahI ff xf xf xf xf xhR ff 柯特斯求积公式 第

41、第4章章 数值微积分数值微积分4.1 4.1 数值积分法数值积分法1212114(4)( ) ( )4()2()( )3 ( ) ()( )180nniiiiI fS hhf af xf xf bR fI fS hhba f 复化复辛浦生求积公式 以上方法是取定步长以上方法是取定步长h h算积分的方法算积分的方法, ,称为定步长积分法称为定步长积分法4.1.2 4.1.2 复化求积公式复化求积公式第第4章章 数值微积分数值微积分4.1 4.1 数值积分法数值积分法4.1.3 4.1.3 变步长积分法变步长积分法*,.hh 为使计算精度增高,可知当h充分小时,必会使误差满足要求. 因此 先任取步

42、长为 进行计算 然后取较小步长进行计算如果两次计算结果相差较大 则取更小步长进行计算 如此继续下去 直到相邻两次计算结果相差不大为止 取最小步长算出的结果作为积分值 此方法称为变步长积分法.* ,2hh 在进行实际计算时 一般可取进行计算第第4章章 数值微积分数值微积分4.1 4.1 数值积分法数值积分法4.1.4 4.1.4 龙贝格积分法龙贝格积分法( )(2 )( )( )3T hThS hT h23( )(2 )( )( ) 41( )(2 )( )( ) 41S hShC hS hC hChR hC h 复化柯特斯求积公式 龙贝格积分法011222333301()()()()()()(

43、)()()(),/ 2,1,2.iiT hT hS hT hS hC hT hS hC hR hhba hhi龙贝格积分法计算过程 其中第第4章章 数值微积分数值微积分4.1 4.1 数值积分法数值积分法4.1.5 4.1.5 待定系数法与高斯型求积公式待定系数法与高斯型求积公式1 ()( )( )() (4-2),( ) ( )nbiiaiiibiiaIfxfx dxA fxQfxAAx lx dx 在 以 下 的 插 值 型 求 积 公 式 中 其 中称 求 积 节 点称 为 求 积 系 数 (1) -()() -()1 ()()()(1)!bnabnaRfIfQfxfxLxdxxfx d

44、xn 其 截 断 误 差(1)(1),(),0,0;1,(1)!, ()()0,(4 - 2)nnbafxrrnfRfrnfnRfxx dxcn因 此 若是次 多 项 式 则则 必 有而 当时则 有所 以 称 插 值 型 求 积 公 式的 代 数 精 度 为第第4章章 数值微积分数值微积分4.1 4.1 数值积分法数值积分法4.1.5 4.1.5 待定系数法与高斯型求积公式待定系数法与高斯型求积公式121211221122,1( )( ) ( )0,( )1,0,R ffccmfxfxR c fc fc R fc R fmf xR ff xmR fm 假定某个近似公式两边之差是 的线性式 即对

45、任意常数和对任意两个阶导数存在的函数和满足条件如果对任意次数不超过次的多项式有但当是某个次的多项式时则称该近似式代数精度的为定义定义第第4章章 数值微积分数值微积分4.1 4.1 数值积分法数值积分法4.1.5 4.1.5 待定系数法与高斯型求积公式待定系数法与高斯型求积公式(1)010101 , 1,( ) ( )( )( )( ,.,)( )( )(1)! ( )()()(),., , 1,.,mmmmR fa bmmR f xR e xfe xf x xxxxxmxxxxxxxa bmx xxxx01m 设近似式两边之差是区间上阶导数连续的线性表示式 且代数精度为则其中 xxx而是区间上

46、的个任意点是在之间且与01,.,mxxx 有关的数广义皮亚诺定理广义皮亚诺定理01:( )( ),.,( )( )( ), mp xf xxxxf xp xe xR fR peR pR eR e证明 设是以为节点的插值多项式 则则有 第第4章章 数值微积分数值微积分4.2 4.2 数值微分法数值微分法4.2.1 4.2.1 近似函数求导法近似函数求导法()()()0( )( ),( )( )( )()nnkkkniiif xLxfxLxlx f x 函数的拉格朗日插值多项式既是其近似式 其导数也可以用来近似求其导数 即有 ()(1)()011 ( )( )(1)!,.,knkndR ffxdx

47、nx xxx 其截断误差为 其中 与有关(2)*(1)11 ()( )( )( )(2)!(1)!nnR ffxfxnn 因此第第4章章 数值微积分数值微积分4.2 4.2 数值微分法数值微分法4.2.1 4.2.1 近似函数求导法近似函数求导法0101102001221201()(),()21()(),()21()( 34),()231()(),26hfxyyR ffhhfxyyR ffhhfxyyyR ffhhfxyyR fh 常 用 的 数 值 微 分 公 式 是 公 式 (4-23)中 节 点 等 矩 且 x为节 点 的 特 殊 情 形(1)两 点 数 值 微 分 公 式 (2)三 点

48、 数 值 微 分 公 式 22012()1()(43),()23fhfxyyyR ffh 第第4章章 数值微积分数值微积分4.2 4.2 数值微分法数值微分法4.2.1 4.2.1 近似函数求导法近似函数求导法*21*22*2*21*22*2()( )( )() ()( )(/)1()( )()( ) ()()(/)1T hT hT hT hfxT hhhhhhT hT hT hT hfxT hhhhh h 实用的截断误差估计式为第第5章章 方程和方程组的迭代解法方程和方程组的迭代解法( )0(5-1)f x 讨论以下方程的根 5.1 5.1 方程求根法方程求根法5.1.1 5.1.1 试探法

49、与二分法试探法与二分法( ) , ,( ) ( )0,( , ),( )0.( )( )0yf xa bf a f ba bff xf x 如果函数在区间上连续 且那么在区间内必定存在使 称为函数的零零点定理点或方程的根第第5章章 方程和方程组的迭代解法方程和方程组的迭代解法 (1)试探法5.1 5.1 方程求根法方程求根法5.1.1 5.1.1 试探法与二分法试探法与二分法01-1-1-,(0,1,. ), (),(),.,()()0,;() ()0,.2.inkkkkkkb anhxaih innf xf xf xf xxxxf xf xh 任取正整数令顺次计算 若发现则取 为 若发现则取

50、为在此方法中所得的根的误差不超过第第5章章 方程和方程组的迭代解法方程和方程组的迭代解法 (2)二分法5.1 5.1 方程求根法方程求根法5.1.1 5.1.1 试探法与二分法试探法与二分法1,( ),( )0,2,2( )( )0,( )( )0,3-,abcf cf ccf a f cbcf c f bachb a步骤 取区间中点计算若发现则取 为结束 若则令 若则令 若区间长度充分小 则取中点为结束 否则,转(1) 此方法的近似值误差不超过h/2第第5章章 方程和方程组的迭代解法方程和方程组的迭代解法5.1 5.1 方程求根法方程求根法5.1.2 5.1.2 简单迭代法简单迭代法0121