太湖网站建设推荐秒搜科技,wordpress 文件加载顺序,网站建设实训,北京app开发外包文章目录 Richardson外推Romberg#xff08;龙贝格#xff09;算法 本篇文章适合个人复习翻阅#xff0c;不建议新手入门使用 本专栏#xff1a;数值分析复习 的前置知识主要有#xff1a;数学分析、高等代数、泛函分析 本节继续考虑数值积分问题
Richardson外推
命题龙贝格算法 本篇文章适合个人复习翻阅不建议新手入门使用 本专栏数值分析复习 的前置知识主要有数学分析、高等代数、泛函分析 本节继续考虑数值积分问题
Richardson外推
命题复合梯形公式的另一形式 设 f ∈ C ∞ [ a , b ] f\in C^{\infty}[a,b] f∈C∞[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_{i0}^{n-1}[f(x_i)f(x_{i1})] T(h)2hi0∑n−1[f(xi)f(xi1)]
则 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(l1,2,\dots) αl(l1,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_ix_{i1}}{2},i0,1,\dots,n-1 xi212xixi1,i0,1,…,n−1
考虑 f ( x ) f(x) f(x) 在 x x i 1 2 xx_{i\frac{1}{2}} xxi21 处的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(xi21)f′(xi21)(x−xi21)2!f′′(xi21)(x−xi21)2⋯
若对上述 Taylor 公式代入 x x i , x x i 1 xx_{i},xx_{i1} xxi,xxi1则得 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_{i1})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(xi1)f(xi21)f′(xi21)2h2!f′′(xi21)(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(xi21)f′(xi21)(−2h)2!f′′(xi21)(−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_{i1})}{2}f(x_{i\frac{1}{2}})\frac{h^2}{8}f(x_{i\frac{1}{2}})\cdots 2f(xi)f(xi1)f(xi21)8h2f′′(xi21)⋯
等式两端求和乘以 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_{i0}^{n-1}f(x_{i\frac{1}{2}})\frac{h^3}{8}\sum\limits_{i0}^{n-1}f(x_{i\frac{1}{2}})\cdots\tag 1 T(h)hi0∑n−1f(xi21)8h3i0∑n−1f′′(xi21)⋯(1)
另一方面对Taylor公式从 x i x_i xi 到 x i 1 x_{i1} xi1 进行积分得到 ∫ 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_{i1}}f(x)\mathrm{d}xh\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 ∫xixi1f(x)dxh⋅f(xi21)2f′(xi21)[(2h)2−(−2h)2]6f′′(xi21)[(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_{i0}^{n-1}\int_{x_i}^{x_{i1}}f(x)\mathrm{d}xh\sum\limits_{i0}^{n-1}f(x_{i\frac{1}{2}}) \frac{h^3}{24}\sum\limits_{i0}^{n-1}f(x_{i\frac{1}{2}}) \cdots\tag 2 Ii0∑n−1∫xixi1f(x)dxhi0∑n−1f(xi21)24h3i0∑n−1f′′(xi21)⋯(2)
结合12式可得 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_{i0}^{n-1}f(x_{i\frac{1}{2}})\cdots\tag 3 T(h)I12h3i0∑n−1f′′(xi21)⋯(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}xh\sum\limits_{i0}^{n-1}f(x_{i\frac{1}{2}})\frac{h^3}{24}\sum\limits_{i0}^{n-1}f^{(4)}(x_{i\frac{1}{2}})\cdots ∫abf′′(x)dxhi0∑n−1f′′(xi21)24h3i0∑n−1f(4)(xi21)⋯
结合 ∫ a b f ′ ′ ( x ) d x f ′ ( b ) − f ′ ( a ) \int_a^bf(x)\mathrm{d}xf(b)-f(a) ∫abf′′(x)dxf′(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^2h^5c_4\sum\limits_{i0}^{n-1}f^{(4)}(x_{i\frac{1}{2}})\cdots T(h)Iα1h2h5c4i0∑n−1f(4)(xi21)⋯
重复上述操作考虑 ∫ 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)I−41α2h4⋯3αl(22l1−1)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_{i0}^{n-1}[f(x_i)f(x_{i1})] T0(h)T(h)2hi0∑n−1[f(xi)f(xi1)]
加速一次即进行一次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)4n−14nTn−1(2h)−4n−11Tn−1(h)
若记 T m ( k ) T m ( h 2 k ) , k 0 , 1 , 2 , … T_m^{(k)}T_m(\frac{h}{2^k}),k0,1,2,\dots Tm(k)Tm(2kh),k0,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}^{(k1)}-\frac{1}{4^n-1}T_{n-1}^{(k)} Tn(k)4n−14nTn−1(k1)−4n−11Tn−1(k)
定理 设被积函数 f ( x ) f(x) f(x) 充分光滑 lim k → ∞ T m ( k ) I \lim\limits_{k\to\infty}T_m^{(k)}I k→∞limTm(k)I lim m → ∞ T m ( k ) I \lim\limits_{m\to\infty}T_m^{(k)}I m→∞limTm(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 k0,m0,hb-a k0,m0,hb−a
代入梯形公式求 T 0 ( k ) ( k 0 , 1 , 2 , … ) T_0^{(k)}(k0,1,2,\dots) T0(k)(k0,1,2,…)加速一次由递推公式求 T 1 ( k ) T_1^{(k)} T1(k)直至 ∣ T k ( 0 ) − T k − 1 ( 0 ) ∣ ε |T_k^{(0)}-T_{k-1}^{(0)}|\varepsilon ∣Tk(0)−Tk−1(0)∣ε则取 T k ( 0 ) ≈ I T_{k}^{(0)}\approx I Tk(0)≈I
注具体求解顺序如下表 参考书籍《数值分析》李庆扬 王能超 易大义 编
