数值分析复习:Richardson外推和Romberg算法

这篇具有很好参考价值的文章主要介绍了数值分析复习:Richardson外推和Romberg算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

本篇文章适合个人复习翻阅,不建议新手入门使用
本专栏:数值分析复习 的前置知识主要有:数学分析、高等代数、泛函分析

本节继续考虑数值积分问题

Richardson外推

命题:复合梯形公式的另一形式
f ∈ C ∞ [ a , b ] f\in C^{\infty}[a,b] fC[a,b],记 I = ∫ a b f ( x ) d x I=\int_a^bf(x)\mathrm{d}x I=abf(x)dx ,将复合梯形公式记为
T ( h ) = h 2 ∑ i = 0 n − 1 [ f ( x i ) + f ( x i + 1 ) ] T(h)=\frac{h}{2}\sum\limits_{i=0}^{n-1}[f(x_i)+f(x_{i+1})] T(h)=2hi=0n1[f(xi)+f(xi+1)]

T ( h ) = I + α 1 h 2 + α 2 h 4 + ⋯ + α l h 2 l + ⋯ T(h)=I+\alpha_1h^2+\alpha_2h^4+\cdots+\alpha_lh^{2l}+\cdots T(h)=I+α1h2+α2h4++αlh2l+

其中 α l ( l = 1 , 2 , …   ) \alpha_l(l=1,2,\dots) αl(l=1,2,) h h h 无关

证明
x i + 1 2 = x i + x i + 1 2 , i = 0 , 1 , … , n − 1 x_{i+\frac{1}{2}}=\frac{x_i+x_{i+1}}{2},i=0,1,\dots,n-1 xi+21=2xi+xi+1,i=0,1,,n1

考虑 f ( x ) f(x) f(x) x = x i + 1 2 x=x_{i+\frac{1}{2}} x=xi+21 处的Taylor展开公式
f ( x ) = f ( x i + 1 2 ) + f ′ ( x i + 1 2 ) ( x − x i + 1 2 ) + f ′ ′ ( x i + 1 2 ) 2 ! ( x − x i + 1 2 ) 2 + ⋯ f(x)=f(x_{i+\frac{1}{2}})+f'(x_{i+\frac{1}{2}})(x-x_{i+\frac{1}{2}})+\frac{f''(x_{i+\frac{1}{2}})}{2!}(x-x_{i+\frac{1}{2}})^2+\cdots f(x)=f(xi+21)+f(xi+21)(xxi+21)+2!f′′(xi+21)(xxi+21)2+

若对上述 Taylor 公式代入 x = x i , x = x i + 1 x=x_{i},x=x_{i+1} x=xi,x=xi+1,则得
f ( x i + 1 ) = f ( x i + 1 2 ) + f ′ ( x i + 1 2 ) h 2 + f ′ ′ ( x i + 1 2 ) 2 ! ( h 2 ) 2 + ⋯ f(x_{i+1})=f(x_{i+\frac{1}{2}})+f'(x_{i+\frac{1}{2}})\frac{h}{2}+\frac{f''(x_{i+\frac{1}{2}})}{2!}(\frac{h}{2})^2+\cdots f(xi+1)=f(xi+21)+f(xi+21)2h+2!f′′(xi+21)(2h)2+ f ( x i ) = f ( x i + 1 2 ) + f ′ ( x i + 1 2 ) ( − h 2 ) + f ′ ′ ( x i + 1 2 ) 2 ! ( − h 2 ) 2 + ⋯ f(x_i)=f(x_{i+\frac{1}{2}})+f'(x_{i+\frac{1}{2}})(-\frac{h}{2})+\frac{f''(x_{i+\frac{1}{2}})}{2!}(-\frac{h}{2})^2+\cdots f(xi)=f(xi+21)+f(xi+21)(2h)+2!f′′(xi+21)(2h)2+

两式加和,得到
f ( x i ) + f ( x i + 1 ) 2 = f ( x i + 1 2 ) + h 2 8 f ′ ′ ( x i + 1 2 ) + ⋯ \frac{f(x_i)+f(x_{i+1})}{2}=f(x_{i+\frac{1}{2}})+\frac{h^2}{8}f''(x_{i+\frac{1}{2}})+\cdots 2f(xi)+f(xi+1)=f(xi+21)+8h2f′′(xi+21)+

等式两端求和,乘以 h h h 得到
T ( h ) = h ∑ i = 0 n − 1 f ( x i + 1 2 ) + h 3 8 ∑ i = 0 n − 1 f ′ ′ ( x i + 1 2 ) + ⋯ (1) T(h)=h\sum\limits_{i=0}^{n-1}f(x_{i+\frac{1}{2}})+\frac{h^3}{8}\sum\limits_{i=0}^{n-1}f''(x_{i+\frac{1}{2}})+\cdots\tag 1 T(h)=hi=0n1f(xi+21)+8h3i=0n1f′′(xi+21)+(1)

另一方面,对Taylor公式从 x i x_i xi x i + 1 x_{i+1} xi+1 进行积分,得到
∫ x i x i + 1 f ( x ) d x = h ⋅ f ( x i + 1 2 ) + f ′ ( x i + 1 2 ) 2 [ ( h 2 ) 2 − ( − h 2 ) 2 ] + f ′ ′ ( x i + 1 2 ) 6 [ ( h 2 ) 3 − ( − h 2 ) 3 ] + ⋯ \int_{x_i}^{x_{i+1}}f(x)\mathrm{d}x=h\cdot f(x_{i+\frac{1}{2}})+\frac{f'(x_{i+\frac{1}{2}})}{2}[(\frac{h}{2})^2-(-\frac{h}{2})^2]+\frac{f''(x_{i+\frac{1}{2}})}{6}[(\frac{h}{2})^3-(-\frac{h}{2})^3]+\cdots xixi+1f(x)dx=hf(xi+21)+2f(xi+21)[(2h)2(2h)2]+6f′′(xi+21)[(2h)3(2h)3]+

等式两端求和得

I = ∑ i = 0 n − 1 ∫ x i x i + 1 f ( x ) d x = h ∑ i = 0 n − 1 f ( x i + 1 2 ) + h 3 24 ∑ i = 0 n − 1 f ′ ′ ( x i + 1 2 ) + ⋯ (2) I=\sum\limits_{i=0}^{n-1}\int_{x_i}^{x_{i+1}}f(x)\mathrm{d}x=h\sum\limits_{i=0}^{n-1}f(x_{i+\frac{1}{2}}) +\frac{h^3}{24}\sum\limits_{i=0}^{n-1}f''(x_{i+\frac{1}{2}}) +\cdots\tag 2 I=i=0n1xixi+1f(x)dx=hi=0n1f(xi+21)+24h3i=0n1f′′(xi+21)+(2)

结合(1)(2)式,可得
T ( h ) = I + h 3 12 ∑ i = 0 n − 1 f ′ ′ ( x i + 1 2 ) + ⋯ (3) T(h)=I+\frac{h^3}{12}\sum\limits_{i=0}^{n-1}f''(x_{i+\frac{1}{2}})+\cdots\tag 3 T(h)=I+12h3i=0n1f′′(xi+21)+(3)

类似(2)式的推导,可得
∫ a b f ′ ′ ( x ) d x = h ∑ i = 0 n − 1 f ′ ′ ( x i + 1 2 ) + h 3 24 ∑ i = 0 n − 1 f ( 4 ) ( x i + 1 2 ) + ⋯ \int_a^bf''(x)\mathrm{d}x=h\sum\limits_{i=0}^{n-1}f''(x_{i+\frac{1}{2}})+\frac{h^3}{24}\sum\limits_{i=0}^{n-1}f^{(4)}(x_{i+\frac{1}{2}})+\cdots abf′′(x)dx=hi=0n1f′′(xi+21)+24h3i=0n1f(4)(xi+21)+

结合 ∫ a b f ′ ′ ( x ) d x = f ′ ( b ) − f ′ ( a ) \int_a^bf''(x)\mathrm{d}x=f'(b)-f'(a) abf′′(x)dx=f(b)f(a),可将(3)式化为
T ( h ) = I + α 1 h 2 + h 5 c 4 ∑ i = 0 n − 1 f ( 4 ) ( x i + 1 2 ) + ⋯ T(h)=I+\alpha_1h^2+h^5c_4\sum\limits_{i=0}^{n-1}f^{(4)}(x_{i+\frac{1}{2}})+\cdots T(h)=I+α1h2+h5c4i=0n1f(4)(xi+21)+

重复上述操作,考虑 ∫ a b f ( 4 ) ( x ) d x \int_a^bf^{(4)}(x)\mathrm{d}x abf(4)(x)dx,消去 h 5 h^5 h5 的项,得到 h 4 h^4 h4 的项,继续重复操作,可得
T ( h ) = I + α 1 h 2 + α 2 h 4 + ⋯ + α l h 2 l + ⋯ T(h)=I+\alpha_1h^2+\alpha_2h^4+\cdots+\alpha_lh^{2l}+\cdots T(h)=I+α1h2+α2h4++αlh2l+

定义:Richardson外推
从低阶精度格式的截断误差的渐近展开式出发,做简单线性计算从而得到高阶精度格式的方法称为Richardson外推

例:
考虑复合梯形公式 T ( h ) T(h) T(h) 满足的式子
T ( h ) = I + α 1 h 2 + α 2 h 4 + ⋯ + α l h 2 l + ⋯ T(h)=I+\alpha_1h^2+\alpha_2h^4+\cdots+\alpha_lh^{2l}+\cdots T(h)=I+α1h2+α2h4++αlh2l+

此时截断误差量级为 O ( h 2 ) O(h^{2}) O(h2)

取步长为 h 2 \frac{h}{2} 2h,则有
T ( h 2 ) = I + α 1 h 2 4 + α 2 h 4 16 + ⋯ + α l h 2 l 2 2 l + ⋯ T(\frac{h}{2})=I+\alpha_1\frac{h^2}{4}+\alpha_2\frac{h^4}{16}+\cdots+\alpha_l\frac{h^{2l}}{2^{2l}}+\cdots T(2h)=I+α14h2+α216h4++αl22lh2l+

结合这两个式子,消去 h 2 h^{2} h2项,得
4 T ( h 2 ) − T ( h ) 3 = I − 1 4 α 2 h 4 + ⋯ + α l 3 ( 1 2 2 l − 1 ) h 2 l + ⋯ \frac{4T(\frac{h}{2})-T(h)}{3}=I-\frac{1}{4}\alpha_2h^4+\cdots+\frac{\alpha_l}{3}(\frac{1}{2^{2l}}-1)h^{2l}+\cdots 34T(2h)T(h)=I41α2h4++3αl(22l11)h2l+
T 1 ( h ) = 4 T ( h 2 ) − T ( h ) 3 T_1(h)=\frac{4T(\frac{h}{2})-T(h)}{3} T1(h)=34T(2h)T(h),且
T 1 ( h ) = I + β 2 h 4 + β 3 h 6 + ⋯ + β l h 2 l + ⋯ T_1(h)=I+\beta_2h^4+\beta_3h^6+\cdots+\beta^lh^{2l}+\cdots T1(h)=I+β2h4+β3h6++βlh2l+
若用 T 1 ( h ) T_1(h) T1(h) 估计 I I I ,则截断误差量级提高到 O ( h 4 ) O(h^{4}) O(h4)
类似地,可继续做……

注:只要截断误差可表示为 h h h 的幂级数,均可使用 Richardson外推提高精度

Romberg(龙贝格)算法

在上述对复合梯形公式的截断误差进行Richardson外推的过程中,记复合梯形公式 T 0 ( h ) = T ( h ) = h 2 ∑ i = 0 n − 1 [ f ( x i ) + f ( x i + 1 ) ] T_0(h)=T(h)=\frac{h}{2}\sum\limits_{i=0}^{n-1}[f(x_i)+f(x_{i+1})] T0(h)=T(h)=2hi=0n1[f(xi)+f(xi+1)]

加速一次(即进行一次Richardson外推)后的估计式记为
T 1 ( h ) = 4 T ( h 2 ) − T ( h ) 3 T_1(h)=\frac{4T(\frac{h}{2})-T(h)}{3} T1(h)=34T(2h)T(h)

记加速 n n n 次的估计式为 T n ( h ) T_n(h) Tn(h),则有递推式
T n ( h ) = 4 n 4 n − 1 T n − 1 ( h 2 ) − 1 4 n − 1 T n − 1 ( h ) T_n(h)=\frac{4^n}{4^n-1}T_{n-1}(\frac{h}{2})-\frac{1}{4^n-1}T_{n-1}(h) Tn(h)=4n14nTn1(2h)4n11Tn1(h)

若记 T m ( k ) = T m ( h 2 k ) , k = 0 , 1 , 2 , … T_m^{(k)}=T_m(\frac{h}{2^k}),k=0,1,2,\dots Tm(k)=Tm(2kh),k=0,1,2,,则有递推式
T n ( k ) = 4 n 4 n − 1 T n − 1 ( k + 1 ) − 1 4 n − 1 T n − 1 ( k ) T_n^{(k)}=\frac{4^n}{4^n-1}T_{n-1}^{(k+1)}-\frac{1}{4^n-1}T_{n-1}^{(k)} Tn(k)=4n14nTn1(k+1)4n11Tn1(k)

定理:
设被积函数 f ( x ) f(x) f(x) 充分光滑

  1. lim ⁡ k → ∞ T m ( k ) = I \lim\limits_{k\to\infty}T_m^{(k)}=I klimTm(k)=I
  2. lim ⁡ m → ∞ T m ( k ) = I \lim\limits_{m\to\infty}T_m^{(k)}=I mlimTm(k)=I

注:证明略去,第一个结论说明当节点数目无穷多时, T m ( k ) T_m^{(k)} Tm(k) 收敛于准确的积分值;第二个结论说明随着Richardson外推的进行, T m ( k ) T_m^{(k)} Tm(k) 也收敛于准确的积分值

上述递推式和收敛定理给出了如下的Romberg算法

定义:Romberg算法
对预先给定的精度 ε \varepsilon ε,求 I = ∫ a b f ( x ) d x I=\int_a^bf(x)\mathrm{d}x I=abf(x)dx 的近似值,算法如下:

初始取 k = 0 , m = 0 , h = b − a k=0,m=0,h=b-a k=0,m=0,h=ba

  1. 代入梯形公式,求 T 0 ( k ) ( k = 0 , 1 , 2 , …   ) T_0^{(k)}(k=0,1,2,\dots) T0(k)(k=0,1,2,)
  2. 加速一次,由递推公式求 T 1 ( k ) T_1^{(k)} T1(k)
  3. 直至 ∣ T k ( 0 ) − T k − 1 ( 0 ) ∣ < ε |T_k^{(0)}-T_{k-1}^{(0)}|<\varepsilon Tk(0)Tk1(0)<ε,则取 T k ( 0 ) ≈ I T_{k}^{(0)}\approx I Tk(0)I

注:具体求解顺序如下表

数值分析复习:Richardson外推和Romberg算法,数值分析,笔记,数值分析

参考书籍:《数值分析》李庆扬 王能超 易大义 编文章来源地址https://www.toymoban.com/news/detail-856337.html

到了这里,关于数值分析复习:Richardson外推和Romberg算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法设计与分析-期末复习经典例题

    算法设计应满足的目标:正确性,可使用,可读,健壮,高效率,低存储 算法的5个重要特征:有限、确定、可行、输入、输出 通常用 函数的返回值 表示算法能否正确执行,如果某个形参需要将执行结果回传给实参,需要将该形参设计为 引用型参数 算法分析是分析算法 占

    2024年02月03日
    浏览(51)
  • 算法设计与分析期末复习题

    1.应用Johnson法则的流水作业调度采用的算法是(D) A. 贪心算法 B. 分支限界法 C.分治法 D. 动态规划算法 2.Hanoi塔问题如下图所示。现要求将塔座A上的的所有圆盘移到塔座B上,并仍按同样顺序叠置。移动圆盘时遵守Hanoi塔问题的移动规则。由此设计出解Hanoi塔问题的递归算法正

    2024年02月09日
    浏览(38)
  • 【期末复习】计算机算法设计与分析

    小编相信大家都很急切,要如何短时间学会算法通过考试呢?下面就让楼主带大家一起了解吧。 算法期末考试,其实就是算法期末考试了。那么小编为什么会算法期末考试,相信大家都很好奇是怎么回事。大家可能会感到很惊讶,小编怎么会算法期末考试呢?但事实就是这样

    2024年02月03日
    浏览(43)
  • 算法设计与分析 期末复习 北邮BUPT

    以下内容以“算法设计与分析-2022”王晓茹老师的ppt为大纲 问题、要求 也均为老师课堂上的口述要求和ppt上的要求 渐进上界、渐进下界 证明 O ( f ( n ) ) + O ( g ( n ) ) = O ( m a x { f ( n ) , g ( n ) } ) O(f(n))+O(g(n)) = O(max{f(n),g(n)}) O ( f ( n )) + O ( g ( n )) = O ( ma x { f ( n ) , g ( n )}) (最后一

    2024年01月16日
    浏览(55)
  • 计算机算法设计与分析期末复习

    以下是我的部分算法笔记,希望可以给复习的小伙伴们参考一下: 题目: 一切合法的输入数据都能得出满足要求的结果,包括典型的、苛刻的输入数据也能够得出满足要求的结果。这个含义对应算法的(正确性) 算法要对异常情况进行适当的处理,就是算法的(健壮性)

    2024年02月13日
    浏览(41)
  • 【算法分析与设计】【期中(末)复习题】【2022秋】

    1.按照渐近阶从低到高的顺序排列下列表达式: 30n,2logn,4,n! A. 430n2lognn! B. 30n42lognn! C. n!42logn30n D. `42logn30nn! O(1) O(logn) O(n) O(nlogn) O(n 2 ) O(n 3 ) O(n k ) O(2 n ) O(n!) O(n n ) (常数阶 对数阶 线性阶 线性对数阶 平方阶 立方阶 K次方阶 指数阶 阶乘阶 n的n次方) 2.二维空间中有n个点,

    2024年02月08日
    浏览(39)
  • 算法设计与分析期末复习题(史上最详细)

    算法设计与分析期末复习题(一) 1、二分搜索算法是利用( A )实现的算法。 A、分治策略 B、动态规划法 C、贪心法 D、回溯法 2、下列不是动态规划算法基本步骤的是( A )。 A、找出最优解的性质 B、构造最优解 C、算出最优解 D、定义最优解 3、最大效益优先是( A )的一

    2023年04月09日
    浏览(51)
  • 算法设计与分析复习笔记第六章分支限界法

    分支限界法的基本思想 分支限界法类似于回溯法,也是一种在问题的解空间树T中搜索问题解的算法。 但在一般情况下,分枝限界法与回溯法的求解目标不同。回溯法的求解目标是找出解空间树中满足约束条件的所有解,而分枝限界法的求解目标则是找出满足约束条件的一个

    2024年02月03日
    浏览(49)
  • 【华为OD机试真题】1194 - Excel单元格数值统计(JAVA C++ Python JS) | 机试题+算法思路+考点+代码分析

    🍂个人博客首页: KJ.JK   🍂专栏介绍: 华为OD机试真题汇总,定期更新华为OD各个时间阶段的机试真题,每日定时更新,本专栏将使用Python语言进行更新解答,包含真题,思路分析,代码参考,欢迎大家订阅学习 🎃题目描述

    2024年02月06日
    浏览(50)
  • 最优化理论笔记及期末复习(《数值最优化》——高立)

    8.3.1实验内容 利用Matlab编程,实现采用简单Armijo非精确线搜索求步长的三种方法:负梯度法、BFGS法及FR共轭梯度法,并求解如下无约束优化问题: m i n f ( x ) = 10 ( x 1 3 − x 2 ) 2 + ( x 1 − 1 ) 2 min f(x) =10(x_1^3-x_2)^2+(x_1-1)^2 m i n f ( x ) = 1 0 ( x 1 3 ​ − x 2 ​ ) 2 + ( x 1 ​ − 1 ) 2 通过

    2024年02月02日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包