∣ x k + 1 − x k ∣ ∣ < ε 1 或者 ∣ f ( x ) ∣ < ε 2 \begin{vmatrix}f(x)\end{vmatrix}<\varepsilon_2 ∣ ∣ f ( x ) ∣ ∣ < ε 2 来作为迭代的终止条件,一般我们选择前者,因为后者可能会有梯度非常小的情况简单迭代法及其收敛性 把 f ( x ) = 0 f(x)=0 f ( x ) = 0 转化为等价的方程
x = φ ( x ) (4.2) x=\varphi(x) \tag{4.2} x = φ ( x ) ( 4.2 )
从而 f ( s ) = 0 f( s) = 0 f ( s ) = 0 等价于 s = φ ( s ) s= \varphi ( s) s = φ ( s ) 。s s s 叫 φ ( x ) \varphi(x) φ ( x ) 的不动点。
选定s s s 的初始近似值x 0 x_0 x 0 ,用递推公式
x k + 1 = φ ( x k ) ( k = 0 , 1 , ⋅ ⋅ ⋅ ) (4.3) x_{k+1}=\varphi(x_k)\quad(k=0,1,\cdotp\cdotp\cdotp)\tag{4.3} x k + 1 = φ ( x k ) ( k = 0 , 1 ,⋅⋅⋅ ) ( 4.3 )
产生序列 { x k } \left\{x_k\right\} { x k } ,在一定条件下,序列 { x k } \left\{x_k\right\} { x k } 收敛于 s s s 。在 { x k } \left\{x_k\right\} { x k } 收敛的情况下,当 k k k 足够大时就可取 x k x_k x k 作为方程(4.1)的近似根。迭代公式(4.3)被称为求解方程(4.1)的简单迭代法,其中 φ ( x ) \varphi(x) φ ( x ) 称为迭代函数。
对于任意的式(4.1)可构成多种简单选代法,它们的迭代函数各不相同。为求同一个根,它们所产生的序列{ x k } \left\{x_k\right\} { x k } ,有的可能收敛,有的可能不收敛;有的会收敛得快,有的会收敛得慢。这一切都取决于送代函数 φ ( x ) \varphi(x) φ ( x ) 在有根区间内的性态。
大范围收敛性定理 设函数 φ ( x ) ∈ C [ a , b ] \varphi(x)\in C[a,b] φ ( x ) ∈ C [ a , b ] ,在(a , b ) a,b) a , b ) 内可导,且满足两个条件:
当x ∈ [ a , b ] x\in[a,b] x ∈ [ a , b ] 时,φ ( x ) ∈ [ a , b ] ; \varphi(x)\in[a,b]; φ ( x ) ∈ [ a , b ] ; 当 x ∈ ( a , b ) x\in(a,b) x ∈ ( a , b ) 时,∣ φ ′ ( x ) ∣ ⩽ L < 1 |\varphi^\prime(x)|\leqslant L<1 ∣ φ ′ ( x ) ∣ ⩽ L < 1 ,其中L L L 为一常数。 则有如下结论:
方程(4.2)在区间[a,b]上有唯一的根 s s s ; 对任取的 x 0 ∈ [ a , b ] x_0\in[a,b] x 0 ∈ [ a , b ] ,简单迭代法(4. 3)产生的序列 { x k } ⊂ [ a , b ] \{x_k\}\subset[a,b] { x k } ⊂ [ a , b ] 且收敛于 s s s ; 成立误差估计式 ∣ s − x k ∣ ⩽ L k 1 − L ∣ x 1 − x 0 ∣ (4.4) \mid s-x_k\mid\leqslant\frac{L^k}{1-L}\mid x_1-x_0\mid \tag{4.4} ∣ s − x k ∣ ⩽ 1 − L L k ∣ x 1 − x 0 ∣ ( 4.4 )
∣ s − x k ∣ ⩽ L 1 − L ∣ x k − x k − 1 ∣ (4.5) \mid s-x_k\mid\leqslant\frac L{1-L}\mid x_k-x_{k-1}\mid \tag{4.5} ∣ s − x k ∣ ⩽ 1 − L L ∣ x k − x k − 1 ∣ ( 4.5 )
1)令 F ( x ) = x − φ ( x ) F(x)=x-\varphi(x) F ( x ) = x − φ ( x ) ,则 F ( x ) ∈ C [ a , b ] F(x)\in C[a,b] F ( x ) ∈ C [ a , b ] ,并由条件(1)可知
F ( a ) = a − φ ( a ) ⩽ 0 , F ( b ) = b − φ ( b ) ⩾ 0 F(a)=a-\varphi(a)\leqslant0,\quad F(b)=b-\varphi(b)\geqslant0 F ( a ) = a − φ ( a ) ⩽ 0 , F ( b ) = b − φ ( b ) ⩾ 0
若上面两个不等式中有一个等号成立,则方程(4.2)有根 s = a s=a s = a 或s = b s=b s = b 。若两个都是严格不等式,则根据连续函数的介值定理,必存在 s ∈ ( a , b ) s\in(a,b) s ∈ ( a , b ) ,使 F ( s ) = s − φ ( s ) = 0 F(s)=s-\varphi(s)=0 F ( s ) = s − φ ( s ) = 0 ,即方程(4.2)有根s ∈ ( a , b ) s\in(a,b) s ∈ ( a , b ) 。今设有两个不同的 s 1 , s 2 ∈ [ a , b ] s_1,s_2\in[a,b] s 1 , s 2 ∈ [ a , b ] 使 s 1 = φ ( s 1 ) , s 2 = φ ( s 2 ) s_1=\varphi(s_1),s_2=\varphi(s_2) s 1 = φ ( s 1 ) , s 2 = φ ( s 2 ) ,则由微分中值定理以及条件(2),有
∣ s 1 − s 2 ∣ = ∣ φ ( s 1 ) − φ ( s 2 ) ∣ = ∣ φ ′ ( ξ ) ∣ ∣ s 1 − s 2 ∣ ⩽ L ∣ s 1 − s 2 ∣ < ∣ s 1 − s 2 ∣ \mid s_1-s_2\mid=\mid\varphi(s_1)-\varphi(s_2)\mid=\mid\varphi^{\prime}(\xi)\mid\mid s_1-s_2\mid\leqslant L\mid s_1-s_2\mid<\mid s_1-s_2\mid ∣ s 1 − s 2 ∣=∣ φ ( s 1 ) − φ ( s 2 ) ∣=∣ φ ′ ( ξ ) ∣∣ s 1 − s 2 ∣ ⩽ L ∣ s 1 − s 2 ∣<∣ s 1 − s 2 ∣
其中 ξ \xi ξ 在 s 1 s_1 s 1 与 s 2 s_2 s 2 之间,因而 ξ ∈ ( a , b ) \xi\in(a,b) ξ ∈ ( a , b ) 。上式出现的矛盾证实s 1 = s 2 s_1=s_2 s 1 = s 2 。
2)因 x 0 ∈ [ a , b ] x_0\in[a,b] x 0 ∈ [ a , b ] ,由条件(1)可知,{ x k } ⊂ [ a , b ] \{x_k\}\subset[a,b] { x k } ⊂ [ a , b ] 。又由条件(2),得
∣ x k − s ∣ = ∣ φ ( x k − 1 ) − φ ( s ) ∣ = ∣ φ ′ ( ξ k ) ∣ ⋅ ∣ x k − 1 − s ∣ ⩽ L ∣ x k − 1 − s ∣ ⩽ ⋅ ⋅ ⋅ ⩽ L k ∣ x 0 − s ∣ \mid x_k-s\mid=\mid\varphi(x_{k-1})-\varphi(s)\mid=\mid\varphi^{\prime}(\xi_k)\mid\cdot\mid x_{k-1}-s\mid\leqslant L\mid x_{k-1}-s\mid\leqslant\cdotp\cdotp\cdotp\leqslant L^k\mid x_0-s\mid ∣ x k − s ∣=∣ φ ( x k − 1 ) − φ ( s ) ∣=∣ φ ′ ( ξ k ) ∣ ⋅ ∣ x k − 1 − s ∣ ⩽ L ∣ x k − 1 − s ∣ ⩽ ⋅⋅⋅ ⩽ L k ∣ x 0 − s ∣
其中 ξ k \xi_k ξ k 在 x k − 1 x_k-1 x k − 1 与 s s s 之间,因而 ξ k ∈ ( a , b ) \xi_k\in(a,b) ξ k ∈ ( a , b ) 。因 0⩽ L < 1 \leqslant L<1 ⩽ L < 1 ,故有 lim k → ∞ x k = s \lim_{k\to\infty} x_k=s lim k → ∞ x k = s 。
3)设 m > k m>k m > k ,则有
x m − x k = ∑ i = k m − 1 ( x i + 1 − x i ) x_m-x_k=\sum_{i=k}^{m-1}(x_{i+1}-x_i) x m − x k = i = k ∑ m − 1 ( x i + 1 − x i )
而
∣ x i + 1 − x i ∣ = ∣ φ ( x i ) − φ ( x i − 1 ) ∣ ⩽ L ∣ x i − x i − 1 ∣ ⩽ … ⩽ L i ∣ x 1 − x 0 ∣ \begin{aligned}\mid x_{i+1}-x_i\mid&=\mid\varphi(x_i)-\varphi(x_{i-1})\mid\leqslant\\&L\mid x_i-x_{i-1}\mid\leqslant\ldots\leqslant L^i\mid x_1-x_0\mid\end{aligned} ∣ x i + 1 − x i ∣ =∣ φ ( x i ) − φ ( x i − 1 ) ∣ ⩽ L ∣ x i − x i − 1 ∣ ⩽ … ⩽ L i ∣ x 1 − x 0 ∣
于是有:
∣ x m − x k ∣ ⩽ ∑ i = k m − 1 ∣ x i + 1 − x i ∣ ⩽ ∑ i = k m − 1 L i ∣ x 1 − x 0 ∣ = L k 1 − L m − k 1 − L ∣ x 1 − x 0 ∣ \mid x_m-x_k\mid\leqslant\sum_{i=k}^{m-1}\mid x_{i+1}-x_i\mid\leqslant\sum_{i=k}^{m-1}L^i\mid x_1-x_0\mid=L^k\frac{1-L^{m-k}}{1-L}\mid x_1-x_0\mid ∣ x m − x k ∣ ⩽ i = k ∑ m − 1 ∣ x i + 1 − x i ∣ ⩽ i = k ∑ m − 1 L i ∣ x 1 − x 0 ∣= L k 1 − L 1 − L m − k ∣ x 1 − x 0 ∣
x m − x k = x m − x m − 1 + x m − 1 ⋯ − x k x_m-x_k=x_m-x_{m-1}+x_{m-1}\cdots-x_k x m − x k = x m − x m − 1 + x m − 1 ⋯ − x k
然后使用绝对值不等式
令 m → ∞ m\to\infty m → ∞ ,由于 0⩽ L < 1 \leqslant L<1 ⩽ L < 1 ,故由上式得到式(4.4)。
又由
∣ x i + 1 − x i ∣ ⩽ L ∣ x i − x i − 1 ∣ ⩽ ⋯ ⩽ L i − k + 1 ∣ x k − x k − 1 ∣ \mid x_{i+1}-x_i\mid\leqslant L\mid x_i-x_{i-1}\mid\leqslant\cdots\leqslant L^{i-k+1}\mid x_k-x_{k-1}\mid ∣ x i + 1 − x i ∣ ⩽ L ∣ x i − x i − 1 ∣ ⩽ ⋯ ⩽ L i − k + 1 ∣ x k − x k − 1 ∣
得
∣ x m − x k ∣ ⩽ ∑ i = k m − 1 ∣ x i + 1 − x i ∣ ⩽ ∑ i = k m − 1 L i − k + 1 ∣ x k − x k − 1 ∣ = L 1 − L m − k 1 − L ∣ x k − x k − 1 ∣ \mid x_m-x_k\mid\leqslant\sum_{i=k}^{m-1}\mid x_{i+1}-x_i\mid\leqslant\sum_{i=k}^{m-1}L^{i-k+1}\mid x_k-x_{k-1}\mid=L\frac{1-L^{m-k}}{1-L}\mid x_k-x_{k-1}\mid ∣ x m − x k ∣ ⩽ i = k ∑ m − 1 ∣ x i + 1 − x i ∣ ⩽ i = k ∑ m − 1 L i − k + 1 ∣ x k − x k − 1 ∣= L 1 − L 1 − L m − k ∣ x k − x k − 1 ∣
令m → ∞ m\to\infty m → ∞ ,由上式得到式(4.5)。证毕。
局部收敛性定理
注:定理4.2并没有给出邻域 δ \delta δ 具体是什么,怎么计算,仅仅要求该邻域存在,也即迭代的起始点 x 0 x_0 x 0 足够接近 s s s 时 。总能得到收敛于 s s s 的迭代序列。
简单迭代法收敛速度
这里 θ \theta θ 相当于一个仿射变换,此外证明得到的 lim k → ∞ ∣ φ ′ ( s − θ e k ) ∣ = ∣ φ ′ ( s ) ∣ \lim_{k\to\infty}\mid\varphi^{\prime}(s-\theta e_{k})\mid=\mid\varphi^{\prime}(s)\mid lim k → ∞ ∣ φ ′ ( s − θ e k ) ∣=∣ φ ′ ( s ) ∣ ,也就是说常数 c = ∣ φ ′ ( s ) ∣ c=\mid\varphi^{\prime}(s)\mid c =∣ φ ′ ( s ) ∣
证明中一个非常关键的点是连续性
牛顿法 用简单送代法求方程(4.1)的根 s s s ,十分重要的问题是构造迭代函数 φ ( x ) \varphi(x) φ ( x ) 。为了使收敛速度的阶高一些,应尽可能使 φ ( x ) \varphi(x) φ ( x ) 在 x = s x=s x = s 处有更多阶导数等于零。
现在令 φ ( x ) = x + h ( x ) f ( x ) \varphi(x)=x+h(x)f(x) φ ( x ) = x + h ( x ) f ( x ) ,h ( x ) h(x) h ( x ) 为待定函数,但 h ( s ) ≠ 0 h(s)\neq0 h ( s ) = 0 ,代入简单迭代法 φ ( x ) = x \varphi(x)=x φ ( x ) = x ,则方程(4.1)与方程
x = x + h ( x ) f ( x ) x=x+h(x)f(x) x = x + h ( x ) f ( x )
有共同的根 s s s 。现用条件 φ ′ ( s ) = 0 \varphi^{\prime}(s)=0 φ ′ ( s ) = 0 确定 h ( x ) h(x) h ( x ) 。由 f ( s ) = 0 f(s)=0 f ( s ) = 0 ,则:
φ ′ ( s ) = 1 + h ′ ( s ) f ( s ) + h ( s ) f ′ ( s ) = 1 + h ( s ) f ′ ( s ) = 0 \varphi^\prime(s)=1+h^\prime(s)f(s)+h(s)f^\prime(s)=1+h(s)f^\prime(s)=0 φ ′ ( s ) = 1 + h ′ ( s ) f ( s ) + h ( s ) f ′ ( s ) = 1 + h ( s ) f ′ ( s ) = 0
知 h ( x ) h(x) h ( x ) 必须满足 h ( s ) = − 1 f ′ ( s ) h(s)=\frac{-1}{f^{\prime}(s)} h ( s ) = f ′ ( s ) − 1 。显然,取 h ( x ) = − 1 f ′ ( x ) h(x)=-\frac1{f^{\prime}(x)} h ( x ) = − f ′ ( x ) 1 就具备这个条件,并且也满反 h ( s ) ≠ 0 h(s)\neq0 h ( s ) = 0 。于是,φ ( x ) \varphi(x) φ ( x ) 被确定为
φ ( x ) = x − f ( x ) f ′ ( x ) \varphi(x)=x-\frac{f(x)}{f^{\prime}(x)} φ ( x ) = x − f ′ ( x ) f ( x )
它满足 φ ′ ( s ) = 0 \varphi^\prime(s)=0 φ ′ ( s ) = 0 。由此得出下面的特殊的简单迭代法
x k + 1 = x k − f ( x k ) f ′ ( x k ) ( k = 0 , 1 , ⋅ ⋅ ⋅ ) (4.7) x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime}(x_k)}\quad(k=0,1,\cdotp\cdotp\cdotp)\tag{4.7} x k + 1 = x k − f ′ ( x k ) f ( x k ) ( k = 0 , 1 ,⋅⋅⋅ ) ( 4.7 )
式(4.7)所表示的迭代法称为 Newton(牛顿)法。
Newton 法可求方程(4.1)的实数根和复数根。当求实数根时,Newton 法有明显的几何意义。当获得 x k x_k x k 之后,过曲线 y= f ( x ) =f(x) = f ( x ) 上的点( x k , f ( x k ) ) (x_k,f(x_k)) ( x k , f ( x k )) 作该曲线的切线,此切线与 x x x 轴相交的交点横坐标就是 Newton 法迭代序列的第k + 1 k+1 k + 1 个元素x k − 1 x_{k-1} x k − 1 。因此 Newton 法(4.7)又称为切线法。
局部收敛性 定理 4.6 设 s s s 是方程(4.1)的根,在包含 s 的某个开区间内 f ′ ( x ) f^\prime(x) f ′ ( x ) 连续且 f ′ ( x ) ≠ 0 f^{\prime}(x)\neq0 f ′ ( x ) = 0 ,则存在 δ > 0 \delta{>}0 δ > 0 ,当 x 0 ∈ [ s − δ , s + δ ] x_0\in[s-\delta,s+\delta] x 0 ∈ [ s − δ , s + δ ] 时,由 Newton 法(4.7)产生的序列 { x k } \{x_k\} { x k } 收敛于 s s s ;若 f ′ ( s ) ≠ 0 f^\prime(s)\neq0 f ′ ( s ) = 0 且 x 0 ≠ s x_0\neq s x 0 = s ,则序列 { x k } \left\{x_k\right\} { x k } 是平方收敛的。
Newton 法(4.7)的迭代函数 φ ( x ) \varphi(x) φ ( x ) 为
φ ( x ) = x − f ( x ) f ′ ( x ) , φ ′ ( x ) = f ( x ) f ′ ′ ( x ) [ f ′ ( x ) ] 2 \varphi(x)=x-\frac{f(x)}{f^{'}(x)},\quad\varphi^{'}(x)=\frac{f(x)f^{''}(x)}{[f^{'}(x)]^2} φ ( x ) = x − f ′ ( x ) f ( x ) , φ ′ ( x ) = [ f ′ ( x ) ] 2 f ( x ) f ′′ ( x )
因 f ′ ( x ) f^\prime(x) f ′ ( x ) 连续且 f ′ ( x ) ≠ 0 f^\prime(x)\neq0 f ′ ( x ) = 0 ,故 φ ′ ( x ) \varphi^{\prime}(x) φ ′ ( x ) 在包含 s s s 的某个开区间内连续,并且有
φ ( s ) = s , φ ′ ( s ) = 0 \varphi(s)=s,\varphi^\prime(s)=0 φ ( s ) = s , φ ′ ( s ) = 0
根据定理 4.2,必存在 δ > 0 \delta>0 δ > 0 ,当 x 0 ∈ [ s − δ , s + δ ] x_0\in[s-\delta,s+\delta] x 0 ∈ [ s − δ , s + δ ] 时,由送代法(4.7)产生的序列 { x k } ⊂ [ s − δ , s + δ ] \{x_k\}\subset[s-\delta,s+\delta] { x k } ⊂ [ s − δ , s + δ ] ,且收敛于 s s s 。
由 Taylor 公式以及 f ( s ) = 0 f(s)=0 f ( s ) = 0 ,有
f ( s ) = f ( x k ) + f ′ ( x k ) ( s − x k ) + f ′ ′ ( ξ k ) 2 ! ( s − x k ) 2 = 0 f(s)=f(x_k)+f^{\prime}(x_k)(s-x_k)+\frac{f^{\prime\prime}(\xi_k)}{2!}(s-x_k)^2=0 f ( s ) = f ( x k ) + f ′ ( x k ) ( s − x k ) + 2 ! f ′′ ( ξ k ) ( s − x k ) 2 = 0
x k + 1 − s = x k − f ( x k ) f ′ ( x k ) − s = f ′ ′ ( ξ k ) 2 f ′ ( x k ) ( s − x k ) 2 x_{k+1}-s=x_k-\frac{f(x_k)}{f^{\prime}(x_k)}-s=\frac{f^{\prime\prime}(\xi_k)}{2f^{\prime}(x_k)}(s-x_k)^2 x k + 1 − s = x k − f ′ ( x k ) f ( x k ) − s = 2 f ′ ( x k ) f ′′ ( ξ k ) ( s − x k ) 2
其中 ξ k \xi_k ξ k 在 x k x_k x k 与 s s s 之间。因 f ′ ( s ) ≠ 0 f^\prime(s)\neq0 f ′ ( s ) = 0 以及 f ′ ( x ) f^{\prime}(x) f ′ ( x ) 的连续性,故可设当 x ∈ [ s − δ , s + δ ] x\in[s-\delta,s+\delta] x ∈ [ s − δ , s + δ ] 时 f ′ ′ ( x ) ≠ 0 f^{\prime\prime}(x)\neq0 f ′′ ( x ) = 0 。因而当 x 0 ∈ [ s − δ , s + δ ] x_0\in[s-\delta,s+\delta] x 0 ∈ [ s − δ , s + δ ] 且 x 0 ≠ s x_0\neq s x 0 = s 时, x k ≠ s ( k = 1 , 2 , . . . ) ,x_k\neq s(k=1,2,...) , x k = s ( k = 1 , 2 , ... ) 。于是有
lim k → ∞ ∣ x k + 1 − s ∣ ∣ x k − s ∣ 2 = ∣ f ′ ′ ( s ) 2 f ′ ( s ) ∣ > 0 \lim_{k\to\infty}\frac{\mid x_{k+1}-s\mid}{\mid x_k-s\mid^2}=\left|\frac{f^{\prime\prime}(s)}{2f^{\prime}(s)}\right|>0 k → ∞ lim ∣ x k − s ∣ 2 ∣ x k + 1 − s ∣ = ∣ ∣ 2 f ′ ( s ) f ′′ ( s ) ∣ ∣ > 0
故序列 { x k } \left\{x_k\right\} { x k } 是平方收敛的。
证毕。
定理 4.6 是 Newton 法的局部收敛性定理。如果 f ( x ) f(x) f ( x ) 只满足此定理的条件,则在一般情况下,初值 x 0 x_{0} x 0 要比较靠近所要求的根 s s s ,Newton 法才能收敛,也就是定理结论中的 δ \delta δ 要比较小。
大范围收敛性(收敛的充分条件 定理 4.7 设函数 f ( x ) f(x) f ( x ) 在区间 [ a , b ] [a,b] [ a , b ] 上存在二阶连续导数,且满足条件:
f ( a ) f ( b ) < 0 f( a) f( b) {< }0 f ( a ) f ( b ) < 0 ;(根存在)
f ′ ′ ( x ) f^{\prime\prime}(x) f ′′ ( x ) 在区间 [ a , b ] [a,b] [ a , b ] 上不变号;(根唯一)
当 x ∈ [ a , b ] x\in[a,b] x ∈ [ a , b ] 时,f ′ ( x ) ≠ 0 ; f^\prime(x)\neq0; f ′ ( x ) = 0 ; (f ′ ( x ) ≠ 0 f^\prime(x)\neq0 f ′ ( x ) = 0 ,根唯一)
x 0 ∈ [ a , b ] , f ( x 0 ) f ′ ′ ( x 0 ) > 0 x_{0}\in [ a, b] , f( x_{0}) f^{\prime \prime }( x_{0}) > 0 x 0 ∈ [ a , b ] , f ( x 0 ) f ′′ ( x 0 ) > 0 。
则由 Newton 法(4.7)产生的序列{ x k } \{ x_k \} { x k } 单调收敛 于方程(4.1) 在 [ a , b ] [a, b] [ a , b ] 内唯一的根 s s s ,并且至少是平方收敛的。
插值与逼近 代数插值 给定 n + 1 n+1 n + 1 个互异的实数 x 0 , x 1 , ⋯ , x n x_0, x_1, \cdots , x_n x 0 , x 1 , ⋯ , x n ,实值函数 f ( x ) f( x) f ( x ) 在包含 x 0 , x 1 , ⋯ , x n x_0,x_1,\cdots,x_n x 0 , x 1 , ⋯ , x n 的某个区间 [ a , b ] [a,b] [ a , b ] 内有定义。设函数组
{ φ k ( x ) ( k = 0 , 1 , ⋯ , n ) } \{\varphi_k(x)(k=0,1,\cdots,n)\} { φ k ( x ) ( k = 0 , 1 , ⋯ , n )}
是次数不高于 n n n 的多项式组,且在点集 { x 0 , x 1 , ⋯ , x n } \left\{x_0,x_1,\cdots,x_n\right\} { x 0 , x 1 , ⋯ , x n } 上线性无关。
现在提出如下的问题:在次数不高于 n n n 的多项式集合
D n = S p a n { φ 0 , φ 1 , ⋯ , φ n } \mathscr{D}_n=\mathrm{Span}\{\varphi_0,\varphi_1,\cdots,\varphi_n\} D n = Span { φ 0 , φ 1 , ⋯ , φ n }
中寻求多项式
p n ( x ) = ∑ k = 0 n c k φ k ( x ) (5.1) p_n(x)=\sum_{k=0}^nc_k\varphi_k(x)\tag{5.1} p n ( x ) = k = 0 ∑ n c k φ k ( x ) ( 5.1 )
使其满足条件
p n ( x i ) = f ( x i ) ( i = 0 , 1 , ⋯ , n ) (5.2) p_n(x_i)=f(x_i)\quad(i=0,1,\cdots,n)\tag{5.2} p n ( x i ) = f ( x i ) ( i = 0 , 1 , ⋯ , n ) ( 5.2 )
此问题称为一元函数的代数插值问题。x 0 , x 1 , ⋅ ⋅ ⋅ , x n x_0,x_1,\cdotp\cdotp\cdotp,x_n x 0 , x 1 ,⋅⋅⋅, x n 称为插值节点;f ( x ) f(x) f ( x ) 称为被插值函数; φ k ( x ) ( k = 0 , 1 , ⋯ , n ) \varphi_k(x)(k=0,1,\cdots,n) φ k ( x ) ( k = 0 , 1 , ⋯ , n ) 称为插值基函数;条件(5.2)称为插值条件;满足插值条件(5.2)的多项式(5.1)称为 n 次插值多项式。
由于插值基函数组 { φ k ( x ) ( k = 0 , 1 , ⋯ , n ) } \{\varphi_k(x)(k=0,1,\cdots,n)\} { φ k ( x ) ( k = 0 , 1 , ⋯ , n )} 在点集 { x 0 , x 1 , ⋯ , x n } \left\{x_0,x_1,\cdots,x_n\right\} { x 0 , x 1 , ⋯ , x n } 上线性无关,所以满足插值条件(5.2)的 n n n 次插值多项式 p n ( x ) p_n(x) p n ( x ) 是存在且唯一的。
又由于插值基函数组限定为次数不高于n n n 的多项式组,所以对于不同的插值基函数组,只要满足同一插值条件(5.2),则所得的n n n 次插值多项式也是唯一的。
对于 n + 1 n+1 n + 1 个插值点, p n ( x i ) = f ( x i ) p_n(x_i)=f(x_i) p n ( x i ) = f ( x i ) 有 n + 1 n+1 n + 1 个方程:p ( x i ) = ∑ j = 0 n a j x i j = f ( x i ) p(x_i)=\sum^n_{j=0}a_jx_i^j=f(x_i) p ( x i ) = ∑ j = 0 n a j x i j = f ( x i )
最后可以化为矩阵 X ⋅ A = F X\cdot A=F X ⋅ A = F (分别是 列向量 x i x_i x i ,值 a i , f ( x i ) a_i,f(x_i) a i , f ( x i ) 构成的矩阵)
拉格朗日插值 取插值基函数
l k ( x ) = ∏ j = 0 n x − x j x k − x j ( k = 0 , 1 , ⋅ ⋅ ⋅ , n ) (5.3) l_k(x)=\prod_{j=0}^n\frac{x-x_j}{x_k-x_j}\quad(k=0,1,\cdotp\cdotp\cdotp,n) \tag{5.3} l k ( x ) = j = 0 ∏ n x k − x j x − x j ( k = 0 , 1 ,⋅⋅⋅, n ) ( 5.3 )
显然,l k ( x ) ( k = 0 , 1 , . . . , n ) l_k(x)(k=0,1,...,n) l k ( x ) ( k = 0 , 1 , ... , n ) 都是 n n n 次多项式,且具有下列性质
l k ( x i ) = { 1 , i = k 0 , i ≠ k l_k(x_i)=\begin{cases}1,&i=k\\0,&i\neq k\end{cases} l k ( x i ) = { 1 , 0 , i = k i = k
显然,通过这种方式得到的 l k ( x i ) l_k(x_i) l k ( x i ) 仅第 i i i 个分量为1,所以彼此一定会线性无关
因此,函数组 { l k ( x ) ( k = 0 , 1 , ⋅ ⋅ ⋅ , n ) } \left\{l_k(x)(k=0,1,\cdotp\cdotp\cdotp,n)\right\} { l k ( x ) ( k = 0 , 1 ,⋅⋅⋅, n ) } 必在点集 { x 0 , x 1 , ⋅ ⋅ ⋅ , x n } \left\{x_0,x_1,\cdotp\cdotp\cdotp,x_n\right\} { x 0 , x 1 ,⋅⋅⋅, x n } 上线性无关,并且
p n ( x ) = ∑ k = 0 n l k ( x ) f ( x k ) (5.4) p_n(x)=\sum_{k=0}^nl_k(x)f(x_k)\tag{5.4} p n ( x ) = k = 0 ∑ n l k ( x ) f ( x k ) ( 5.4 )
由 c k l ( x k ) = 0 , k ≠ j c_kl(x_k)=0,k\neq j c k l ( x k ) = 0 , k = j
p n ( x j ) = ∑ c i l ( x i ) = c j l ( x j ) = c j = f ( x j ) p_n(x_j)=\sum c_i l(x_i)=c_jl(x_j)=c_j=f(x_j) p n ( x j ) = ∑ c i l ( x i ) = c j l ( x j ) = c j = f ( x j )
或
p n ( x ) = ∑ k = 0 n ( ∏ j = 0 n x − x j x k − x j ) f ( x k ) (5.5) p_n(x)=\sum_{k=0}^n\Big(\prod_{j=0}^n\frac{x-x_j}{x_k-x_j}\Big)f(x_k)\tag{5.5} p n ( x ) = k = 0 ∑ n ( j = 0 ∏ n x k − x j x − x j ) f ( x k ) ( 5.5 )
就是满足插值条件(5.2)的 n n n 次插值多项式。
牛顿插值 拉格朗日插值在计算过程中若需要改变节点或增加节点时, 全部基函数 l k ( x ) l_k(x) l k ( x ) 都需要重新计算 ,这在实际计算中很不方便
目标是寻找新的基函数,使得每加一个节点时,只附加一项 上去 ,而不必重新计算全部基函数
Newton 插值多项式的构造 基函数如下:
{ φ k ( x ) } = { 1 , x − x 0 , ( x − x 0 ) ( x − x 1 ) , … , ( x − x 0 ) ( x − x 1 ) … ( x − x n − 1 ) } \{\varphi_k(x)\}=\{1,x-x_0,(x-x_0)(x-x_1),\ldots,(x-x_0)(x-x_1)\ldots(x-x_{n-1})\} { φ k ( x )} = { 1 , x − x 0 , ( x − x 0 ) ( x − x 1 ) , … , ( x − x 0 ) ( x − x 1 ) … ( x − x n − 1 )}
( φ 0 ( x 0 ) , φ 1 ( x 0 ) , … , φ n ( x 0 ) φ 0 ( x 1 ) , φ 1 ( x 1 ) , … , φ n ( x 1 ) ⋮ ⋮ ⋮ φ 0 ( x n ) , φ 1 ( x n ) , … , φ n ( x n ) ) = ( 1 0 0 0 1 x 1 − x 0 0 0 1 x 2 − x 0 ( x 2 − x 0 ) ( x 2 − x 1 ) ⋮ ⋮ ⋮ ⋮ 0 1 x n − x 0 ( x n − x 0 ) ( x n − x 1 ) ∏ j = 0 n − 1 ( x n − x j ) ) \begin{pmatrix}\varphi_0(x_0),\varphi_1(x_0),\ldots,\varphi_n(x_0)\\\varphi_0(x_1),\varphi_1(x_1),\ldots,\varphi_n(x_1)\\\vdots&\vdots&\vdots\\\varphi_0(x_n),\varphi_1(x_n),\ldots,\varphi_n(x_n)\end{pmatrix}=\begin{pmatrix}1&0&0&0\\1&x_1-x_0&0&0\\1&x_2-x_0&(x_2-x_0)(x_2-x_1)&\vdots\\\vdots&\vdots&\vdots&0\\\\1&x_n-x_0&(x_n-x_0)(x_n-x_1)&\prod_{j=0}^{n-1}(x_n-x_j)\end{pmatrix} ⎝ ⎛ φ 0 ( x 0 ) , φ 1 ( x 0 ) , … , φ n ( x 0 ) φ 0 ( x 1 ) , φ 1 ( x 1 ) , … , φ n ( x 1 ) ⋮ φ 0 ( x n ) , φ 1 ( x n ) , … , φ n ( x n ) ⋮ ⋮ ⎠ ⎞ = ⎝ ⎛ 1 1 1 ⋮ 1 0 x 1 − x 0 x 2 − x 0 ⋮ x n − x 0 0 0 ( x 2 − x 0 ) ( x 2 − x 1 ) ⋮ ( x n − x 0 ) ( x n − x 1 ) 0 0 ⋮ 0 ∏ j = 0 n − 1 ( x n − x j ) ⎠ ⎞
所以这组函数线性无关,故插值函数为:
p n ( x ) = c 0 + c 1 ( x − x 0 ) + c 2 ( x − x 0 ) ( x − x 1 ) + ⋯ + c n ( x − x 0 ) ( x − x 1 ) ⋯ ( x − x n − 1 ) \begin{aligned}p_{n}(x)&=c_0+c_1(x-x_0)+c_2(x-x_0)(x-x_1)\\&+\cdots+c_n(x-x_0)(x-x_1)\cdots(x-x_{n-1})\end{aligned} p n ( x ) = c 0 + c 1 ( x − x 0 ) + c 2 ( x − x 0 ) ( x − x 1 ) + ⋯ + c n ( x − x 0 ) ( x − x 1 ) ⋯ ( x − x n − 1 )
由p n ( x i ) = f ( x i ) ( i = 0 , 1 , ⋯ , n ) p_n(x_i)=f(x_i)\quad(i=0,1,\cdots,n) p n ( x i ) = f ( x i ) ( i = 0 , 1 , ⋯ , n ) :
{ f ( x 0 ) = p n ( x 0 ) = c 0 f ( x 1 ) = p n ( x 1 ) = c 0 + c 1 ( x 1 − x 0 ) f ( x 2 ) = p n ( x 2 ) = c 0 + c 1 ( x 2 − x 0 ) + c 2 ( x 2 − x 0 ) ( x 2 − x 1 ) f ( x 3 ) = p n ( x 3 ) = c 0 + c 1 ( x 3 − x 0 ) + c 2 ( x 3 − x 0 ) ( x 3 − x 1 ) f ( x n ) = p n ( x n ) = c 0 + c 1 ( x n − x 0 ) + c 2 ( x n − x 0 ) ( x n − x 1 ) + ⋯ + c n ( x n − x 0 ) ⋯ ( x n − x n − 1 ) \begin{cases}&f(x_0)=p_n(x_0)=c_0\\&f(x_1)=p_n(x_1)=c_0+c_1(x_1-x_0)\\&f(x_2)=p_n(x_2)=c_0+c_1(x_2-x_0)+c_2(x_2-x_0)(x_2-x_1)\\&f(x_3)=p_n(x_3)=c_0+c_1(x_3-x_0)+c_2(x_3-x_0)(x_3-x_1)\\&f(x_n)=p_n(x_n)=c_0+c_1(x_n-x_0)+c_2(x_n-x_0)(x_n-x_1)+\cdots+c_n(x_n-x_0)\cdots(x_n-x_{n-1})\end{cases} ⎩ ⎨ ⎧ f ( x 0 ) = p n ( x 0 ) = c 0 f ( x 1 ) = p n ( x 1 ) = c 0 + c 1 ( x 1 − x 0 ) f ( x 2 ) = p n ( x 2 ) = c 0 + c 1 ( x 2 − x 0 ) + c 2 ( x 2 − x 0 ) ( x 2 − x 1 ) f ( x 3 ) = p n ( x 3 ) = c 0 + c 1 ( x 3 − x 0 ) + c 2 ( x 3 − x 0 ) ( x 3 − x 1 ) f ( x n ) = p n ( x n ) = c 0 + c 1 ( x n − x 0 ) + c 2 ( x n − x 0 ) ( x n − x 1 ) + ⋯ + c n ( x n − x 0 ) ⋯ ( x n − x n − 1 )
可得 c k = f [ x 0 , x 1 , ⋯ , x k ] c_k=f[x_0,x_1,\cdots,x_k] c k = f [ x 0 , x 1 , ⋯ , x k ]
k 阶差商 一阶差商:f [ x 0 , x 1 ] = f ( x 1 ) − f ( x 0 ) x 1 − x 0 f[x_0,x_1]=\frac{f(x_1)-f(x_0)}{x_1-x_0} f [ x 0 , x 1 ] = x 1 − x 0 f ( x 1 ) − f ( x 0 )
二阶差商:f [ x 0 , x 1 , x 2 ] = f [ x 0 , x 2 ] − f [ x 0 , x 1 ] x 2 − x 1 f[x_0,x_1,x_2]=\frac{f[x_0,x_2]-f[x_0,x_1]}{x_2-x_1} f [ x 0 , x 1 , x 2 ] = x 2 − x 1 f [ x 0 , x 2 ] − f [ x 0 , x 1 ]
k阶插商:
f [ x 0 , x 1 , ⋯ , x k ] = f [ x 0 , x 1 , ⋯ , x k − 2 , x k ] − f [ x 0 , x 1 , ⋯ , x k − 1 ] x k − x k − 1 f[x_0,x_1,\cdots,x_k]=\frac{f[x_0,x_1,\cdots,x_{k-2},x_k]-f[x_0,x_1,\cdots,x_{k-1}]}{x_k-x_{k-1}} f [ x 0 , x 1 , ⋯ , x k ] = x k − x k − 1 f [ x 0 , x 1 , ⋯ , x k − 2 , x k ] − f [ x 0 , x 1 , ⋯ , x k − 1 ]
牛顿插值公式利用差商可简单地表为
N 0 ( x ) = f ( x 0 ) N 1 ( x ) = f ( x 0 ) + f [ x 0 , x 1 ] ( x − x 0 ) = N 0 ( x ) + f [ x 0 , x 1 ] ( x − x 0 ) N 2 ( x ) = N 1 ( x ) + f [ x 0 , x 1 , x 2 ] ( x − x 0 ) ( x − x 1 ) . . . . . . N k + 1 ( x ) = N k ( x ) + f [ x 0 , ⋯ , x k + 1 ] ( x − x 0 ) ( x − x 1 ) ⋯ ( x − x k ) ⏟ \begin{aligned} &N_0(x)=f(x_0) \\ &N_1(x)=f(x_0)+f[x_0,x_1](x-x_0) \\ & \quad \quad \quad =N_0(x)+f[x_0,x_1](x-x_0) \\ &N_2(x)=N_1(x)+f[x_0,x_1,x_2](x-x_0)(x-x_1) \\ &...... \\ &N_{k+1}(x)=N_k(x)+\underbrace{f[x_0,\cdots,x_{k+1}](x-x_0)(x-x_1)\cdots(x-x_k)} \end{aligned} N 0 ( x ) = f ( x 0 ) N 1 ( x ) = f ( x 0 ) + f [ x 0 , x 1 ] ( x − x 0 ) = N 0 ( x ) + f [ x 0 , x 1 ] ( x − x 0 ) N 2 ( x ) = N 1 ( x ) + f [ x 0 , x 1 , x 2 ] ( x − x 0 ) ( x − x 1 ) ...... N k + 1 ( x ) = N k ( x ) + f [ x 0 , ⋯ , x k + 1 ] ( x − x 0 ) ( x − x 1 ) ⋯ ( x − x k )
因此, 每增加一个结点, Newton 插值多项式只增加一项(即括号标注的一项)
插值余项 设 x 0 , x 1 , ⋯ , x n x_0, x_1, \cdots , x_n x 0 , x 1 , ⋯ , x n 是互异实数,对给定的实数x x x ,实值函数f ( x ) f( x) f ( x ) 在区间 I x I_x I x 上有 n + 1 n+ 1 n + 1 阶导数,则拉格朗日插值多项式与牛顿插值多项式有相同的插值余项:
R n ( x ) = f ( x ) − p n ( x ) = f ( n + 1 ) ( ξ ) ( n + 1 ) ! ∏ i = 0 n ( x − x i ) . R_n(x)=f(x)-p_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x-x_i). R n ( x ) = f ( x ) − p n ( x ) = ( n + 1 )! f ( n + 1 ) ( ξ ) i = 0 ∏ n ( x − x i ) .
罗尔定理的推论:若 φ ( x ) \varphi ( x) φ ( x ) 充分光滑,且 ϕ ( x 1 ) = ⋯ = ϕ ( x n ) = 0 ⇒ \phi ( x_1) = \cdots = \phi ( x_n) = 0\Rightarrow ϕ ( x 1 ) = ⋯ = ϕ ( x n ) = 0 ⇒ 存在 n − l n-l n − l 个 ξ ∈ I ~ \xi \in \tilde{I} ξ ∈ I ~ 使得 φ ( l ) ( ξ ) = 0 \varphi ^{( l) }( \xi ) = 0 φ ( l ) ( ξ ) = 0
此外,过 n + 1 n +1 n + 1 个点的 n n n 次多项式是唯一的:N n ( x ) ≡ L n ( x ) N_n(x)\equiv L_n(x) N n ( x ) ≡ L n ( x )
R n ( x ) R_n(x) R n ( x ) 有 n + 1 n+1 n + 1 个根 x 0 x_0 x 0 ~x n x_n x n
证明:
由于 R n ( x i ) = 0 R_n( x_i) = 0 R n ( x i ) = 0 , i = 0 , 1 , . . . , n \boldsymbol{i}= 0, 1, . . . , n i = 0 , 1 , ... , n ⇒ \Rightarrow ⇒ R n ( x ) = u ( x ) ∏ i = 0 ( x − x i ) = f ( x ) − p n ( x ) R_{n}(x)=u(x)\prod_{i=0}(x-x_{i})=f(x)-p_{n}(x) R n ( x ) = u ( x ) ∏ i = 0 ( x − x i ) = f ( x ) − p n ( x )
任意固定x ≠ x i x\neq x_i x = x i ( i = 0 , . . . , n ) ( i= 0, . . . , n) ( i = 0 , ... , n ) ,构造辅助函数
g ( t ) = R n ( t ) − u ( x ) ∏ i = 0 n ( t − x i ) = f ( t ) − p n ( t ) − u ( x ) ∏ i = 0 n ( t − x i ) (1) g(t)=R_n(t)-u(x)\prod_{i=0}^n(t-x_i)=f(t)-p_n(t)-u(x)\prod_{i=0}^n(t-x_i)\tag{1} g ( t ) = R n ( t ) − u ( x ) i = 0 ∏ n ( t − x i ) = f ( t ) − p n ( t ) − u ( x ) i = 0 ∏ n ( t − x i ) ( 1 )
则 g ( t ) g( t) g ( t ) 有 n + 2 n+ 2 n + 2 个不同的根 x , x 0 , … , x n x, x_0, \ldots , x_n x , x 0 , … , x n 反复使用Rolle定理,可得存在 ξ ∈ I ~ x \xi\in\tilde{I}_x ξ ∈ I ~ x ,使得:
g ( n + 1 ) ( ξ ) = 0 , ξ ∈ I ~ x g^{(n+1)}(\xi)=0,\xi\in\tilde{I}_{x} g ( n + 1 ) ( ξ ) = 0 , ξ ∈ I ~ x
⇒ u ( x ) = f ( n + 1 ) ( ξ ) ( n + 1 ) ! ⇒ R n ( x ) = f ( n + 1 ) ( ξ ) ( n + 1 ) ! ∏ i = 0 n ( x − x i ) . (2) \Rightarrow u(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\Rightarrow R_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{i=0}^n(x-x_i).\tag{2} ⇒ u ( x ) = ( n + 1 )! f ( n + 1 ) ( ξ ) ⇒ R n ( x ) = ( n + 1 )! f ( n + 1 ) ( ξ ) i = 0 ∏ n ( x − x i ) . ( 2 )
显然 ξ \xi ξ 和 x x x 有关
对 (1) 式求导,由于 p n ( t ) p_n(t) p n ( t ) 为 n n n 次多项式,所以 p n ( n + 1 ) ( t ) = 0 p_n^{(n+1)}(t)=0 p n ( n + 1 ) ( t ) = 0 ,[ u ( x ) ∏ i = 0 n ( t − x i ) ] ( n + 1 ) = u ( x ) ( n + 1 ) ! [u(x)\prod_{i=0}^n(t-x_i)]^{(n+1)}=u(x)(n+1)! [ u ( x ) ∏ i = 0 n ( t − x i ) ] ( n + 1 ) = u ( x ) ( n + 1 )! ,所以:
g ( n + 1 ) ( t ) = f ( n + 1 ) ( t ) − u ( x ) ( n + 1 ) ! g^{(n+1)}(t)=f^{(n+1)}(t)-u(x)(n+1)! g ( n + 1 ) ( t ) = f ( n + 1 ) ( t ) − u ( x ) ( n + 1 )!
即可得到 (2) 式
正交多项式 权函数 定义 权函数 在区间(a , b ) a,b) a , b ) 上,若非负函数ρ ( x ) \rho ( x) ρ ( x ) 满足
对一切整数n ≥ 0 , ∫ a b x n ρ ( x ) d x n\geq0,\int_a^bx^n\rho(x)dx n ≥ 0 , ∫ a b x n ρ ( x ) d x 存在;
对 ( a , b ) ( a, b) ( a , b ) 上的非负连续函数 f ( x ) f( x) f ( x ) ,若 ∫ a b ρ ( x ) f ( x ) d x = 0 \int _{a}^{b}\rho ( x) f( x) dx= 0 ∫ a b ρ ( x ) f ( x ) d x = 0 ,则在区间 ( a , b ) ( a, b) ( a , b ) 上 f ( x ) ≡ 0. f( x) \equiv 0. f ( x ) ≡ 0.
那么,称 ρ ( x ) \rho(x) ρ ( x ) 为 ( a , b ) (a,b) ( a , b ) 上的权函数。
常见的权函数:ρ ( x ) ≡ 1 , a ≤ x ≤ b ; \rho ( x) \equiv 1, a\leq x\leq b; ρ ( x ) ≡ 1 , a ≤ x ≤ b ;
内积 给定 f ( x ) , g ( x ) ∈ C [ a , b ] , ρ ( x ) f( x) , g( x) \in C[ a, b] , \rho ( x) f ( x ) , g ( x ) ∈ C [ a , b ] , ρ ( x ) 是 ( a , b ) (a,b) ( a , b ) 上的权函数,称
( f , g ) = ∫ a b ρ ( x ) f ( x ) g ( x ) d x (f,g)=\int_a^b\rho(x)f(x)g(x)dx ( f , g ) = ∫ a b ρ ( x ) f ( x ) g ( x ) d x
为 f f f ,g g g 在 [ a , b ] [a,b] [ a , b ] 上的内积.
内积的性质 ( f , g ) = ( g , f ) ; \left(f,\:g\right)=\left(\:g,\:f\right); ( f , g ) = ( g , f ) ;
( k f , g ) = ( f , k g ) = k ( f , g ) , k (kf,g)=(f,kg)=k(f,g),k ( k f , g ) = ( f , k g ) = k ( f , g ) , k 为常数,k ∈ R ; k\in R; k ∈ R ;
( f 1 + f 2 , g ) = ( f 1 , g ) + ( f 2 , g ) ; \left(f_{1}+f_{2},\:g\right)=\left(f_{1},g\:\right)+\left(f_{2},g\:\right); ( f 1 + f 2 , g ) = ( f 1 , g ) + ( f 2 , g ) ;
若在 [ a , b ] [a,b] [ a , b ] 上 f ( x ) ≢ 0 f(x)\not\equiv0 f ( x ) ≡ 0 ,则 ( f , f ) > 0. (f,f)>0. ( f , f ) > 0.
正交与正交函数系 若内积
( f , g ) = ∫ a b ρ ( x ) f ( x ) g ( x ) d x = 0 (f,g)=\int_a^b\rho(x)f(x)g(x)dx=0 ( f , g ) = ∫ a b ρ ( x ) f ( x ) g ( x ) d x = 0
则称 f f f , g 在 [ a , b ] [a,b] [ a , b ] 上带权 ρ ( x ) \rho(x) ρ ( x ) 正交.
正交函数系 定义 若函数系 { φ 0 ( x ) , φ 1 ( x ) , . . . , φ n ( x ) , . . . } \{\varphi_0(x),\varphi_1(x),...,\varphi_n(x),...\} { φ 0 ( x ) , φ 1 ( x ) , ... , φ n ( x ) , ... } 满足
( φ i , φ j ) = ∫ a b ρ ( x ) φ i ( x ) φ j ( x ) d x = { 0 , i ≠ j a i > 0 , i = j (\varphi_i,\varphi_j)=\int\limits_a^b\rho(x)\varphi_i(x)\varphi_j(x)dx=\begin{cases}0, i\neq j\\a_i>0,i=j\end{cases} ( φ i , φ j ) = a ∫ b ρ ( x ) φ i ( x ) φ j ( x ) d x = { 0 , i = j a i > 0 , i = j
则称 { φ n ( x ) } \{\varphi_n(x)\} { φ n ( x )} 是 [ a , b ] [a,b] [ a , b ] 上带权 ρ ( x ) \rho(x) ρ ( x ) 的正交函数系.
[ a , b ] [a,b] [ a , b ] 上带权 ρ ( x ) \rho(x) ρ ( x ) 的正交函数系必是线性无关的函数系,而不论 ρ ( x ) \rho(x) ρ ( x ) 是什么函数.
这里函数系线性无关与前面插值里的线性无关不是一个概念 设 φ k ( x ) \varphi_k(x) φ k ( x ) 是最高项系数不为零的 k k k 次多项式,k = 0 , 1 , 2 , … ; k=0,1,2,\ldots; k = 0 , 1 , 2 , … ; 则 { φ k ( x ) } \{\boldsymbol{\varphi}_k(x)\} { φ k ( x )} 是 [ a , b ] [a,b] [ a , b ] 上带权 ρ ( x ) \rho(x) ρ ( x ) 的正交多项式系
⇔ \Leftrightarrow ⇔ (充分必要条件)
对任何次数不高于 k − 1 k-1 k − 1 的多项式 q ( x ) q(x) q ( x ) ,总有
( q , φ k ) = ∫ a ρ ( x ) q ( x ) φ k ( x ) d x = 0 , k = 1 , 2 , ⋯ . (q,\varphi_k)=\int_a\rho(x)q(x)\varphi_k(x)dx=0,k=1,2,\cdots. ( q , φ k ) = ∫ a ρ ( x ) q ( x ) φ k ( x ) d x = 0 , k = 1 , 2 , ⋯ .
性质 (结构)设 { φ k ( x ) } \{\varphi_k(x)\} { φ k ( x )} 是 [ a , b ] [a,b] [ a , b ] 上带权 ρ ( x ) \rho(x) ρ ( x ) 的正交多项式系,则{ c k φ k ( x ) } \left\{c_k\varphi_k(x)\right\} { c k φ k ( x ) } 也是[ a , b ] [a,b] [ a , b ] 上带权 ρ ( x ) \rho(x) ρ ( x ) 的正交多项式系。其中,c k c_k c k 是非零常数.
(唯一性){φ k ( x ) } \varphi_k(x)\} φ k ( x )} 是区间[ a , b ] [a,b] [ a , b ] 上带权 ρ ( x ) \rho(x) ρ ( x ) 的正交多项式系,若各个φ k ( x ) \varphi_k(x) φ k ( x ) 的最高次项系数是1,则这样的{ φ k ( x ) } \{\varphi_k(x)\} { φ k ( x )} 是唯一的. 证 设 { φ k ( x ) } , { g k ( x ) } \{\varphi_k(x)\},\{g_k(x)\} { φ k ( x )} , { g k ( x )} 为性质2中要求正交多项式系,k = 0 k=0 k = 0 时,φ 0 ( x ) ≡ 1 ≡ g 0 ( x ) . \varphi_0(x)\equiv1\equiv g_0(x). φ 0 ( x ) ≡ 1 ≡ g 0 ( x ) . k ≥ 1 k\geq 1 k ≥ 1 时,g k − φ k g_k- \varphi _k g k − φ k 是次数不高于 k − 1 k- 1 k − 1 的多项式,由定理5.6知,
( g k − φ k , φ k ) = ( g k − φ k , g k ) = 0 ⇔ ( g k − φ k , g k − φ k ) = 0 , ⇔ g k − φ k ≡ 0 , g k ( x ) ≡ φ k ( x ) , a ≤ x ≤ b \begin{aligned}&(\:g_k-\varphi_k,\:\varphi_k\:)=(\:g_k-\varphi_k,\:g_k\:)=0\\&\Leftrightarrow(g_k-\varphi_k,g_k-\varphi_k)=0,\\&\Leftrightarrow g_k-\varphi_k\equiv0,\quad g_k(x)\equiv\varphi_k(x)_,a\leq x\leq b\end{aligned} ( g k − φ k , φ k ) = ( g k − φ k , g k ) = 0 ⇔ ( g k − φ k , g k − φ k ) = 0 , ⇔ g k − φ k ≡ 0 , g k ( x ) ≡ φ k ( x ) , a ≤ x ≤ b
(正交多项式的根)若 φ k ( x ) {\varphi_k(x)} φ k ( x ) 是 [ a , b ] [a,b] [ a , b ] 上带权 ρ ( x ) \rho(x) ρ ( x ) 的 正交多项式系,则 k ≥ 1 k\geq1 k ≥ 1 时,k k k 次正交多项式 φ k ( x ) \varphi_k(x) φ k ( x ) 在 ( a , b ) (a,b) ( a , b ) 内有 k k k 个互异的实根.
事实上,可以证明 k k k 次正交多项式有k k k 个单根.
设{φ k ( x ) } \varphi_k(x)\} φ k ( x )} 是区间[ a , b ] [a,b] [ a , b ] 上带权 ρ ( x ) \rho(x) ρ ( x ) 的正交多项式系,则 k ≥ 1 k\geq1 k ≥ 1 时,有如下的递推关系式:
ϕ k + 1 ( x ) = a k + 1 a k ( x − β k ) ϕ k ( x ) − a k + 1 a k − 1 a k 2 λ k − 1 ϕ k − 1 ( x ) \phi_{k+1}(x)=\frac{a_{k+1}}{a_k}(x-\beta_k)\phi_k(x)-\frac{a_{k+1}a_{k-1}}{a_k^2}\lambda_{k-1}\phi_{k-1}(x) ϕ k + 1 ( x ) = a k a k + 1 ( x − β k ) ϕ k ( x ) − a k 2 a k + 1 a k − 1 λ k − 1 ϕ k − 1 ( x )
其中,a k a_k a k 是 φ k ( x ) \varphi_k(x) φ k ( x ) 的最高次项系数,且
β k = ( x φ k , φ k ) ( φ k , φ k ) , λ k − 1 = ( φ k , φ k ) ( φ k − 1 , φ k − 1 ) . \beta_{k}=\frac{(x\varphi_{k},\varphi_{k})}{(\varphi_{k},\varphi_{k})},\quad\lambda_{k-1}=\frac{(\varphi_{k},\varphi_{k})}{(\varphi_{k-1},\varphi_{k-1})}. β k = ( φ k , φ k ) ( x φ k , φ k ) , λ k − 1 = ( φ k − 1 , φ k − 1 ) ( φ k , φ k ) .
函数的最佳平方逼近 函数的最佳逼近问题:对函数类 A A A 中给定的函数 f ( x ) f( x) f ( x ) ,需要在另一类较简单的便于计算的函数类 B B B ( B ∈ A ) ( B\in A) ( B ∈ A ) 中,找一个函数P ( x ) P( x) P ( x ) ,使 P ( x ) P(x) P ( x ) 与 f ( x ) f (x) f ( x ) 之差在某种度量意义下达到最小。
函数f ( x ) f(x) f ( x ) 称为被逼近函数;P ( x ) P( x) P ( x ) 称为逼近函数,两者之差称为逼近误差。
函数类 A A A 通常是区间 [ a , b ] [a,b] [ a , b ] 上的连续函数,记作 C [ a , b ] C[a,b] C [ a , b ] ;函数类 B B B 通常是代数多项式,有理多项式 ,三角多项式,分段多项式等容易计算的函数。
常用度量标准 一致逼近(均匀逼近)以 max a ≤ x ≤ b ∣ f ( x ) − p ( x ) ∣ \max _a\leq x\leq b| f( x) - p( x) | max a ≤ x ≤ b ∣ f ( x ) − p ( x ) ∣ 作为度量误差 f ( x ) − P ( x ) f(x)-P( x) f ( x ) − P ( x ) 的“大小” 标准
平方逼近(均方逼近)以 以 ∫ a b [ f ( x ) − p ( x ) ] 2 d x \int_a^b[f(x)-p(x)]^2dx ∫ a b [ f ( x ) − p ( x ) ] 2 d x 作为度量误差 f ( x ) − P ( x ) f(x)-P( x) f ( x ) − P ( x ) 的“大小” 标准
最佳平方逼近的概念与解法
H n = Span { φ 0 ( x ) , φ 1 ( x ) , . . . , φ n ( x ) } H_n= \operatorname { Span} \{ \varphi _0( x) , \varphi _1( x) , . . . , \varphi _n( x) \} H n = Span { φ 0 ( x ) , φ 1 ( x ) , ... , φ n ( x )} 是 φ i ( x ) \varphi_i(x) φ i ( x ) 张成的线性空间
定理5.7 设f ( x ) ∈ C [ a , b ] , p ∗ ( x ) ∈ H n f(x)\in C[a,b],p^*(x)\in H_n f ( x ) ∈ C [ a , b ] , p ∗ ( x ) ∈ H n ,在 H n H_n H n 中,p ∗ ( x ) p^* ( x) p ∗ ( x ) 是 f ( x ) f( x) f ( x ) 最佳平方逼近的函数⇔ ( f − p ∗ , φ j ) = 0 , j = 0 , 1 , . . . , n \Leftrightarrow(f-p^*,\varphi_j)=0,j=0,1,...,n ⇔ ( f − p ∗ , φ j ) = 0 , j = 0 , 1 , ... , n 其中,{ φ 0 ( x ) , φ 1 ( x ) , . . . , φ n ( x ) } \{ \varphi _0( x) , \varphi _1( x) , . . . , \varphi _n( x) \} { φ 0 ( x ) , φ 1 ( x ) , ... , φ n ( x )} 为子空间 H n H_n H n 的一组基
( ⇒ ) ( \Rightarrow ) ( ⇒ ) p ∗ ( x ) = ∑ c i ∗ φ i ( x ) p^*(x)=\sum c_i^*\varphi _i(x) p ∗ ( x ) = ∑ c i ∗ φ i ( x ) 代入 ( f − p ∗ , φ j ) = 0 (f-p^*,\varphi_j)=0 ( f − p ∗ , φ j ) = 0 得 ( f − ∑ c i ∗ φ i , φ j ) = 0 (f-\sum c_i^*\varphi _i,\varphi_j)=0 ( f − ∑ c i ∗ φ i , φ j ) = 0
则 ( f , φ j ) = ( ∑ c i ∗ φ i , φ j ) = ∑ c i ∗ ( φ i , φ j ) (f,\varphi_j)=(\sum c_i^*\varphi _i,\varphi_j)=\sum c_i^*(\varphi_i,\varphi_j) ( f , φ j ) = ( ∑ c i ∗ φ i , φ j ) = ∑ c i ∗ ( φ i , φ j )
即:
[ ( φ 0 , φ 0 ) ( φ 0 , φ 1 ) ⋯ ( φ 0 , φ n ) ( φ 1 , φ 0 ) ( φ 1 , φ 1 ) ⋯ ( φ 1 , φ n ) ⋮ ⋮ ⋯ ⋮ ( φ n , φ 0 ) ( φ n , φ 1 ) ⋯ ( φ n , φ n ) ] [ c 0 ∗ c 1 ∗ ⋮ c n ∗ ] = [ ( f , φ 0 ) ( f , φ 1 ) ⋮ ( f , φ n ) ] \begin{bmatrix}(\varphi_0,\varphi_0)&(\varphi_0,\varphi_1)&\cdots&(\varphi_0,\varphi_n)\\(\varphi_1,\varphi_0)&(\varphi_1,\varphi_1)&\cdots&(\varphi_1,\varphi_n)\\\vdots&\vdots&\cdots&\vdots\\(\varphi_n,\varphi_0)&(\varphi_n,\varphi_1)&\cdots&(\varphi_n,\varphi_n)\end{bmatrix}\begin{bmatrix}c_0^*\\c_1^*\\\vdots\\c_n^*\end{bmatrix}=\begin{bmatrix}(f,\varphi_0)\\(f,\varphi_1)\\\vdots\\(f,\varphi_n)\end{bmatrix} ⎣ ⎡ ( φ 0 , φ 0 ) ( φ 1 , φ 0 ) ⋮ ( φ n , φ 0 ) ( φ 0 , φ 1 ) ( φ 1 , φ 1 ) ⋮ ( φ n , φ 1 ) ⋯ ⋯ ⋯ ⋯ ( φ 0 , φ n ) ( φ 1 , φ n ) ⋮ ( φ n , φ n ) ⎦ ⎤ ⎣ ⎡ c 0 ∗ c 1 ∗ ⋮ c n ∗ ⎦ ⎤ = ⎣ ⎡ ( f , φ 0 ) ( f , φ 1 ) ⋮ ( f , φ n ) ⎦ ⎤
从而求解系数 c i ∗ c_i^* c i ∗
( ⇐ ) ( \Leftarrow ) ( ⇐ ) 若( f − p ∗ , φ j ) = 0 , j = 0 , 1 , . . . , n ( f- p^*, \varphi _j) = 0, j= 0, 1, . . . , n ( f − p ∗ , φ j ) = 0 , j = 0 , 1 , ... , n 成立,对任意的 p ( x ) ∈ H n p( x) \in H_n p ( x ) ∈ H n ,有
( f − p , f − p ) = ( f − p ∗ + p ∗ − p , f − p ∗ + p ∗ − p ) = ( f − p ∗ , f − p ∗ ) + 2 ( f − p ∗ , p ∗ − p ) + ( p ∗ − p , p ∗ − p ) \begin{aligned}(f-p,f-p)&=(f-p^*+p^*-p,f-p^*+p^*-p)\\&=(f-p^*,f-p^*)+2(f-p^*,p^*-p)+(p^*-p,p^*-p)\end{aligned} ( f − p , f − p ) = ( f − p ∗ + p ∗ − p , f − p ∗ + p ∗ − p ) = ( f − p ∗ , f − p ∗ ) + 2 ( f − p ∗ , p ∗ − p ) + ( p ∗ − p , p ∗ − p )
由于 ( f − p ∗ , p ∗ − p ) = ∑ j = 0 n ( c j ∗ − c j ) ( f − p ∗ , φ j ) = 0 \left ( f- p^* , p^* - p\right ) = \sum _{j= 0}^n\left ( c_j^* - c_j\right ) \left ( f- p^* , \varphi _j\right ) = 0 ( f − p ∗ , p ∗ − p ) = ∑ j = 0 n ( c j ∗ − c j ) ( f − p ∗ , φ j ) = 0 及 ( p ∗ − p , p ∗ − p ) ≥ 0 ( p^* - p, p^* - p) \geq 0 ( p ∗ − p , p ∗ − p ) ≥ 0 ,故 ( f − p , f − p ) ≥ ( f − p ∗ , f − p ∗ ) . (f-p,f-p)\geq(f-p^*,f-p^*). ( f − p , f − p ) ≥ ( f − p ∗ , f − p ∗ ) .
p ∗ p^* p ∗ 在 H n H_n H n 中是对 f f f 的最佳平方逼近函数
即设 f ( x ) ∈ C [ a , b ] , p ∗ ( x ) ∈ H n f(x)\in C[a,b],p^*(x)\in H_n f ( x ) ∈ C [ a , b ] , p ∗ ( x ) ∈ H n ,在 H n H_n H n 中,p ∗ ( x ) p^* ( x) p ∗ ( x ) 是对 f ( x ) f( x) f ( x ) 最佳平方逼近的函数⇔ \Leftrightarrow ⇔ 对任意的 p ( x ) ∈ H n p( x) \in H_n p ( x ) ∈ H n 均有
( f − p ∗ , p ) = 0 (f-p^*,p)=0 ( f − p ∗ , p ) = 0
定理5.8 设 f ( x ) ∈ C [ a , b ] f( x) \in C[ a, b] f ( x ) ∈ C [ a , b ] 在子空间 H n H_n H n 中,对 f ( x ) f( x) f ( x ) 最佳平方逼近的函数是唯一的
正交函数系在最佳平方逼近中的应用 对于正交函数系,( φ k , φ j ) = ∫ ρ ( x ) φ k ( x ) φ j ( x ) d x = 0 , k ≠ j (\varphi_{k},\varphi_{j})=\int\rho(x)\varphi_{k}(x)\varphi_{j}(x)dx=0,k\neq j ( φ k , φ j ) = ∫ ρ ( x ) φ k ( x ) φ j ( x ) d x = 0 , k = j
[ ( φ 0 , φ 0 ) ( φ 0 , φ 1 ) ⋯ ( φ 0 , φ n ) ( φ 1 , φ 0 ) ( φ 1 , φ 1 ) ⋯ ( φ 1 , φ n ) ⋮ ⋮ ⋯ ⋮ ( φ n , φ 0 ) ( φ n , φ 1 ) ⋯ ( φ n , φ n ) ] [ c 0 c 1 ⋮ c n ] = [ ( f , φ 0 ) ( f , φ 1 ) ⋮ ( f , φ n ) ] \begin{bmatrix}(\varphi_0,\varphi_0)&(\varphi_0,\varphi_1)&\cdots&(\varphi_0,\varphi_n)\\(\varphi_1,\varphi_0)&(\varphi_1,\varphi_1)&\cdots&(\varphi_1,\varphi_n)\\\vdots&\vdots&\cdots&\vdots\\(\varphi_n,\varphi_0)&(\varphi_n,\varphi_1)&\cdots&(\varphi_n,\varphi_n)\end{bmatrix}\begin{bmatrix}c_0\\c_1\\\vdots\\c_n\end{bmatrix}=\begin{bmatrix}(f,\varphi_0)\\(f,\varphi_1)\\\vdots\\(f,\varphi_n)\end{bmatrix} ⎣ ⎡ ( φ 0 , φ 0 ) ( φ 1 , φ 0 ) ⋮ ( φ n , φ 0 ) ( φ 0 , φ 1 ) ( φ 1 , φ 1 ) ⋮ ( φ n , φ 1 ) ⋯ ⋯ ⋯ ⋯ ( φ 0 , φ n ) ( φ 1 , φ n ) ⋮ ( φ n , φ n ) ⎦ ⎤ ⎣ ⎡ c 0 c 1 ⋮ c n ⎦ ⎤ = ⎣ ⎡ ( f , φ 0 ) ( f , φ 1 ) ⋮ ( f , φ n ) ⎦ ⎤
⇒ [ ( φ 0 , φ 0 ) ( φ 1 , φ 1 ) ⋱ ( φ n , φ n ) ] [ c 0 c 1 ⋮ c n ] = [ ( f , φ 0 ) ( f , φ 1 ) ⋮ ( f , φ n ) ] \Rightarrow\begin{bmatrix}(\varphi_0,\varphi_0)\\&(\varphi_1,\varphi_1)\\&&\ddots\\&&&(\varphi_n,\varphi_n)\end{bmatrix}\begin{bmatrix}c_0\\c_1\\\vdots\\c_n\end{bmatrix}=\begin{bmatrix}(f,\varphi_0)\\(f,\varphi_1)\\\vdots\\(f,\varphi_n)\end{bmatrix} ⇒ ⎣ ⎡ ( φ 0 , φ 0 ) ( φ 1 , φ 1 ) ⋱ ( φ n , φ n ) ⎦ ⎤ ⎣ ⎡ c 0 c 1 ⋮ c n ⎦ ⎤ = ⎣ ⎡ ( f , φ 0 ) ( f , φ 1 ) ⋮ ( f , φ n ) ⎦ ⎤
⇒ c k = ( f , φ k ) ( φ k , φ k ) , k = 0 , 1 , 2 , . . . , n \Rightarrow c_k=\frac{(f,\varphi_k)}{(\varphi_k,\varphi_k)},\quad k=0,1,2,...,n ⇒ c k = ( φ k , φ k ) ( f , φ k ) , k = 0 , 1 , 2 , ... , n
曲线拟合 与插值的一个非常大的区别就是曲线拟合的函数 y ∗ ( x ) y^*(x) y ∗ ( x ) 不要求经过所有数据点。
最小二乘问题 最小二乘问题的矩阵表示 最小二乘解的特征 最小二乘法的精度 正交多项式用于曲线拟合 数值积分 目的是求一些牛顿-莱布尼茨积分公式无法求解的积分函数
求积公式及其代数精度 一求积公式的一般形式:
∫ a b f ( x ) d x ≈ ∑ k = 0 n λ k f ( x k ) (6.1) \int_a^bf(x)dx\approx\sum_{k=0}^n\lambda_kf(x_k)\tag{6.1} ∫ a b f ( x ) d x ≈ k = 0 ∑ n λ k f ( x k ) ( 6.1 )
式中 x k ( k = 0 , 1 , ⋯ , n ) x_k( k= 0, 1, \cdots , n) x k ( k = 0 , 1 , ⋯ , n ) 称为求积节点,它们满足 :
a ≤ x 0 < x 1 < … < x n ≤ b a\leq x_0<x_1<\ldots<x_n\leq b a ≤ x 0 < x 1 < … < x n ≤ b
λ k ( k = 0 , 1 , ⋯ , n ) \lambda _{k}( k= 0, 1, \cdots , n) λ k ( k = 0 , 1 , ⋯ , n ) 称为求积系数,与被积函数无关 。
当求积节点与求积系数确定了以后,求积公式就确定了,因此任务是确定求积节点和求积系数。
截断误差或余项:
R n = ∫ a b f ( x ) d x − ∑ k = 0 n λ k f ( x k ) R_n=\int_a^bf(x)dx-\sum_{k=0}^n\lambda_kf(x_k) R n = ∫ a b f ( x ) d x − k = 0 ∑ n λ k f ( x k )
代数精度 对求积公式(6.1),当 f ( x ) f(x) f ( x ) 为任何次数不高于 m m m 的多项式时都成立,而当 f ( x ) f(x) f ( x ) 为某个 m + 1 m+1 m + 1 次多项式时不成立,则称它具有 m m m 次代
数精度。
如何求解代数精度:对求积公式(6.1),当 f ( x ) f(x) f ( x ) 为 1 , x , x 2 , ⋯ , x n 1,x,x^2,\cdots,x^n 1 , x , x 2 , ⋯ , x n 时,求积公式均成立,则对于任何次数不高于 m m m 的多项式求积公式也必然成立。
差值型求积公式 利用插值多项式 p n ( x ) p_n(x) p n ( x ) 逼近代替 f ( x ) f(x) f ( x ) 计算积分
在[ a , b ] \left [ a, b\right ] [ a , b ] 上取 a ≤ x 0 < x 1 < … < x m ≤ b a\leq x_0< x_1< \ldots < x_m\leq b a ≤ x 0 < x 1 < … < x m ≤ b 。构 造 f f f 的 n n n 次Lagrange插值基函数
p n ( x ) = ∑ k = 0 n l k ( x ) f ( x k ) , l k ( x ) = ∏ i = 0 n x − x i x k − x i , k = 0 , 1 , ⋯ , n p_n(x)=\sum_{k=0}^nl_k(x)f(x_k),l_k(x)=\prod_{i=0}^n\frac{x-x_i}{x_k-x_i},k=0,1,\cdots,n p n ( x ) = k = 0 ∑ n l k ( x ) f ( x k ) , l k ( x ) = i = 0 ∏ n x k − x i x − x i , k = 0 , 1 , ⋯ , n
∫ a b f ( x ) d x ≈ ∑ k = 0 n ( ∫ a b l k ( x ) d x ) f ( x k ) (6.1.1) \int_a^bf(x)dx\approx\sum_{k=0}^n\left(\int_a^bl_k(x)\mathrm{d}x\right)f(x_k)\tag{6.1.1} ∫ a b f ( x ) d x ≈ k = 0 ∑ n ( ∫ a b l k ( x ) d x ) f ( x k ) ( 6.1.1 )
λ k ( n ) = ∫ a b l k ( x ) d x = ∫ a b ∏ i = 0 i ≠ k n x − x i x k − x i d x , k = 0 , 1 , ⋯ , n (6.2) \lambda_k^{(n)}=\int_a^bl_k(x)\mathrm{d}x=\int_a^b\prod_{i=0\atop i\neq k}^n\frac{x-x_i}{x_k-x_i}\mathrm{d}x,k=0,1,\cdots,n\tag{6.2} λ k ( n ) = ∫ a b l k ( x ) d x = ∫ a b i = k i = 0 ∏ n x k − x i x − x i d x , k = 0 , 1 , ⋯ , n ( 6.2 )
其中,λ k ( n ) \lambda_k^{(n)} λ k ( n ) 由节点决定与 f ( x ) f(x) f ( x ) 无关。
设函数 f ( x ) f(x) f ( x ) 在区间 [ a , b ] [a,b] [ a , b ] 上足够光滑,则由定理5.1得
f ( x ) = ∑ k = 0 n l k ( x ) f ( x k ) + f ( n + 1 ) ( ξ ) ( n + 1 ) ! ∏ j = 0 n ( x − x j ) f(x)=\sum_{k=0}^nl_k\left(x\right)f(x_k)+\frac{f^{(n+1)}\left(\xi\right)}{\left(n+1\right)!}\prod_{j=0}^n\left(x-x_j\right) f ( x ) = k = 0 ∑ n l k ( x ) f ( x k ) + ( n + 1 ) ! f ( n + 1 ) ( ξ ) j = 0 ∏ n ( x − x j )
其中 x ∈ [ a , b ] , ξ = ξ ( x ) ∈ ( a , b ) x\in[a,b],\xi=\xi(x)\in(a,b) x ∈ [ a , b ] , ξ = ξ ( x ) ∈ ( a , b ) 因此,可得
R n = ∫ a b f ( x ) d x − ∑ k = 0 n λ k ( n ) f ( x k ) = ∫ a b [ f ( x ) − L n ( x ) ] d x = ∑ k = 0 n ( ∫ a b l k ( x ) d x ) f ( x k ) + ∫ a b f ( n + 1 ) ( ξ ) ( n + 1 ) ! ∏ j = 0 n ( x − x j ) d x − ∑ k = 0 n ( ∫ a b l k ′ ( x ) d x ) f ( x k ) = ∫ a b f ( n + 1 ) ( ξ ) ( n + 1 ) ! ∏ j = 0 n ( x − x j ) d x R_n=\int_a^bf(x)\mathrm{d}x-\sum_{k=0}^n\lambda_k^{(n)}f(x_k)=\int_a^b[f(x)-L_n(x)]\mathrm{d}x\\=\sum_{k=0}^n\left(\int_a^bl_k\left(x\right)dx\right)f(x_k)+\int_a^b\frac{f^{(n+1)}\left(\xi\right)}{\left(n+1\right)!}\prod_{j=0}^n\left(x-x_j\right)dx-\sum_{k=0}^n\left(\int_a^bl_k^{\prime}(x)\mathrm{d}x\right)f(x_k)\\=\int_a^b \frac{f^{(n+1)}(\xi)}{(n+1)!}\prod_{j=0}^n\left(x-x_j\right)dx R n = ∫ a b f ( x ) d x − k = 0 ∑ n λ k ( n ) f ( x k ) = ∫ a b [ f ( x ) − L n ( x )] d x = k = 0 ∑ n ( ∫ a b l k ( x ) d x ) f ( x k ) + ∫ a b ( n + 1 ) ! f ( n + 1 ) ( ξ ) j = 0 ∏ n ( x − x j ) d x − k = 0 ∑ n ( ∫ a b l k ′ ( x ) d x ) f ( x k ) = ∫ a b ( n + 1 )! f ( n + 1 ) ( ξ ) j = 0 ∏ n ( x − x j ) d x
定理与相关推论 ∑ k = 0 n λ k ( n ) = b − a \sum_{k=0}^n\lambda_k^{(n)}=b-a k = 0 ∑ n λ k ( n ) = b − a
其中,a , b a,b a , b 为积分下上限
定理6.2 n + 1 n+1 n + 1 个节点的求积公式 (6.1)至少有 n n n 次代数精度则它一定是插值型求积公式。 Newton-Cotes 求积公式 等距节点插值积分 将积分区间 [ a , b ] [a,b] [ a , b ] 划分为 n n n 等份,步长为 h = b − a n h=\frac{b-a}n h = n b − a ,节点等距为 x k = a + k h x_k=a+kh x k = a + kh 构造出的插值求积公式
∫ a b f ( x ) d x ≈ ∑ k = 0 n ( ∫ a b l k ( x ) d x ) f ( x k ) \int_a^bf(x)dx\approx\sum_{k=0}^n\left(\int_a^bl_k(x)\mathrm{d}x\right)f(x_k) ∫ a b f ( x ) d x ≈ k = 0 ∑ n ( ∫ a b l k ( x ) d x ) f ( x k )
λ k ( n ) = ∫ a b l k ( x ) d x = ∫ a b ∏ i = 0 i ≠ k n x − x i x k − x i d x , k = 0 , 1 , ⋯ , n \lambda_k^{(n)}=\int_a^bl_k(x)\mathrm{d}x=\int_a^b\prod_{i=0\atop i\neq k}^n\frac{x-x_i}{x_k-x_i}\mathrm{d}x,k=0,1,\cdots,n λ k ( n ) = ∫ a b l k ( x ) d x = ∫ a b i = k i = 0 ∏ n x k − x i x − x i d x , k = 0 , 1 , ⋯ , n
Newton-Cotes求积公式,式中 λ k ( n ) \lambda_{k}^{(n)} λ k ( n ) 称为Newton-Cotes求积系数
定理6.3 当 n n n 为偶数时,n + 1 n+1 n + 1 个节点的 n n n 阶Newton-Cotes 求积公式的代数精度至少是n + 1 n+1 n + 1 次。 收敛性 考察是否对任何在[ a , b ] [ a, b] [ a , b ] 上 可 积 的 函 数 f ( x ) f( x) f ( x ) 都有
lim n → ∞ [ ∑ k = 0 n λ k ( n ) f ( a + k b − a n ) ] = ∫ a b f ( x ) d x . \lim_{n\to\infty}\biggl[\sum_{k=0}^n\lambda_k^{(n)}f\biggl(a+k\frac{b-a}n\biggr)\biggr]=\int_a^bf(x)\mathrm{d}x. n → ∞ lim [ k = 0 ∑ n λ k ( n ) f ( a + k n b − a ) ] = ∫ a b f ( x ) d x .
其中,λ k ( n ) \lambda _k^{( n) } λ k ( n ) 是 Newton-Cotes 求积系数。答案是否定的
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 ZWN's blog !