?
∣ x ? ? x ∣ ≤ ε ? |x^*-x|\le \varepsilon^* ∣x??x∣≤ε?
∣ x ? ? x ∣ ≤ 1 2 m ? n + 1 |x^*-x|\le \frac{1}{2}^{m-n+1} ∣x??x∣≤21?m?n+1
卷面要体现如 ∣ E n ∣ = ∣ y n ? ? y n ∣ = a ∣ E N ∣ = ? = a n ∣ E n ∣ |E_{n}|=|y^*_n-y_{n}|=a|E_{N}|=\cdots=a^{n}|E_{n}| ∣En?∣=∣yn???yn?∣=a∣EN?∣=?=an∣En?∣
{ a < 1 误差减小；算法稳定 a > 1 误差增大；算法不稳定 \begin{cases} a<1 误差减小；算法稳定\\ a>1 误差增大；算法不稳定 \end{cases} {a<1误差减小；算法稳定a>1误差增大；算法不稳定?
若算法不稳定，选取一个较大的N，逆推回第一项
拉格朗日插值基函数
l k ( x ) = ( x ? x 0 ) ? ( x ? x k ? 1 ) ( x ? x k + 1 ) ? ( x ? x n ) ) ( x k ? x 0 ) ? ( x k ? x k ? 1 ) ( x k ? x k + 1 ) ? ( x k ? x n ) ( k = 0 , 1 , 2 , 3 ? n ) l_{k(x)}=\displaystyle\frac{(x-x_0)\cdots(x-x_{k-1})(x-x_{k+1})\cdots(x-x_n))}{(x_k-x_0)\cdots(x_k-x_{k-1})(x_k-x_{k+1})\cdots(x_k-x_n)} (k=0,1,2,3\cdots n) lk(x)?=(xk??x0?)?(xk??xk?1?)(xk??xk+1?)?(xk??xn?)(x?x0?)?(x?xk?1?)(x?xk+1?)?(x?xn?))?(k=0,1,2,3?n)
题中给出几个点，就有几个插值基函数
插值多项式
L n ( X ) = ∑ k = 0 n y k ? l k ( x ) L_{n(X)} = \displaystyle \sum^{n}_{k=0}y_k*l_{k(x)} Ln(X)?=k=0∑n?yk??lk(x)?
差商
一阶差商： f [ x i , x j ] = f ( x i ) ? f ( x j ) x i ? x j \displaystyle f[x_i,x_j]=\frac{f(x_i)-f(x_j)}{x_i-x_j} f[xi?,xj?]=xi??xj?f(xi?)?f(xj?)?
二阶差商： f [ x i , x j , x k ] = f [ x i , x j ] ? f [ x j , x k ] x i ? x k \displaystyle f[x_i,x_j,x_k]=\frac{f[x_i,x_j]-f[x_j,x_k]}{x_i-x_k} f[xi?,xj?,xk?]=xi??xk?f[xi?,xj?]?f[xj?,xk?]? 前两项 ? 后两项 头 ? 尾 \displaystyle \frac{前两项-后两项}{头-尾} 头?尾前两项?后两项?
? 三阶差商： f [ x i , x j , x k , x m ] = f [ x i , x j , x k ] ? f [ x j , x k , x m ] x i ? x m \displaystyle f[x_i,x_j,x_k,x_m]=\frac{f[x_i,x_j,x_k]-f[x_j,x_k,x_m]}{x_i-x_m} f[xi?,xj?,xk?,xm?]=xi??xm?f[xi?,xj?,xk?]?f[xj?,xk?,xm?]? 前三项 ? 后三项 头 ? 尾 \displaystyle \frac{前三项-后三项}{头-尾} 头?尾前三项?后三项?
N ( X ) = f ( x 0 ) + f [ x 0 , x 1 ] ( x ? x 0 ) + f [ x 0 , x 1 , x 2 ] ( x ? x 0 ) ( x ? x 1 ) + f [ x 0 , x 1 , x 2 , ? ? , x n ] ( x ? x 0 ) ? ( x ? x n ? 1 ) \displaystyle N_{(X)}=f(x_0)+f[x_0,x_1](x-x_0)+f[x_0,x_1,x_2](x-x_0)(x-x_1)+f[x_0,x_1,x_2,\cdots ,x_n](x-x_0)\cdots(x-x_{n-1}) N(X)?=f(x0?)+f[x0?,x1?](x?x0?)+f[x0?,x1?,x2?](x?x0?)(x?x1?)+f[x0?,x1?,x2?,?,xn?](x?x0?)?(x?xn?1?)
| x i x_i xi? | f ( x i ) f(x_i) f(xi?) | 一阶差商 | 二阶差商 | 三阶差商 | ? \cdots ? | n阶差商 |
|---|---|---|---|---|---|---|
| x 0 x_0 x0? | f ( x 0 ) f(x_0) f(x0?) | |||||
| x 1 x_1 x1? | f ( x 1 ) f(x_1) f(x1?) | a 1 a_1 a1? | ||||
| x 2 x_2 x2? | f ( x 2 ) f(x_2) f(x2?) | a 2 a_2 a2? | b 1 b_1 b1? | |||
| ? \vdots ? | ? \vdots ? | ? \vdots ? | ? \vdots ? | ? \vdots ? | ? \vdots ? | |
| x n x_n xn? | f ( x n ) f(x_n) f(xn?) | a n a_n an? | b n b_n bn? | c n c_n cn? |
一阶差商： a 1 = f ( x 0 ) ? f ( x 1 ) x 0 ? x 1 \displaystyle a_1=\frac{f(x_0)-f(x_1)}{x_0-x_1} a1?=x0??x1?f(x0?)?f(x1?)?
二阶差商： b 1 = a 1 ? a 2 x 0 ? x 1 \displaystyle b_1=\frac{a_1-a_2}{x_0-x_1} b1?=x0??x1?a1??a2??
三阶差商： a 1 = b 1 ? b 2 x 0 ? x 1 \displaystyle a_1=\frac{b_1-b_2}{x_0-x_1} a1?=x0??x1?b1??b2??
( ? 0 , ? 0 ) = ∫ a b x 0 + 0 d x \displaystyle (\phi_0,\phi_0)=\int_{a}^{b}x^{0+0}dx (?0?,?0?)=∫ab?x0+0dx
( ? i , ? j ) = ∫ a b x i + j d x \displaystyle (\phi_i,\phi_j)=\int_{a}^{b}x^{i+j}dx (?i?,?j?)=∫ab?xi+jdx
( f , ? i ) = ∫ a b f ( x ) x i d x \displaystyle (f,\phi_i)=\int_{a}^{b}f(x)x^{i}dx (f,?i?)=∫ab?f(x)xidx
[ ( ? 0 , ? 0 ) ( ? 0 , ? 1 ) ( ? 0 , ? 2 ) ( ? 1 , ? 0 ) ( ? 1 , ? 1 ) ( ? 1 , ? 2 ) ( ? 2 , ? 0 ) ( ? 2 , ? 1 ) ( ? 2 , ? 2 ) ] [ a 0 a 1 a 2 ] = [ ( f , ? 0 ) ( f , ? 1 ) ( f , ? 2 ) ] \displaystyle \begin{bmatrix}(\phi_0,\phi_0) & (\phi_0,\phi_1) & (\phi_0,\phi_2)\\(\phi_1,\phi_0) & (\phi_1,\phi_1) & (\phi_1,\phi_2)\\(\phi_2,\phi_0) & (\phi_2,\phi_1) & (\phi_2,\phi_2)\end{bmatrix} \begin{bmatrix}a_0\\a_1\\a_2\end{bmatrix} = \begin{bmatrix}(f,\phi_0)\\(f,\phi_1)\\(f,\phi_2)\end{bmatrix} ?(?0?,?0?)(?1?,?0?)(?2?,?0?)?(?0?,?1?)(?1?,?1?)(?2?,?1?)?(?0?,?2?)(?1?,?2?)(?2?,?2?)? ? ?a0?a1?a2?? ?= ?(f,?0?)(f,?1?)(f,?2?)? ?
P 0 = 1 ; P 1 = x ; P 2 = 3 x 2 ? 1 2 ; P 3 = x ( 5 x 2 ? 3 ) 2 \displaystyle P_0=1; P_1=x ;P_2=\frac{3x^2-1}{2};P_3=\frac{x(5x^2-3)}{2} P0?=1;P1?=x;P2?=23x2?1?;P3?=2x(5x2?3)?
( f , P 0 ) = ∫ a b f ( x ) d x \displaystyle (f,P_0)=\int_{a}^{b}f(x)dx (f,P0?)=∫ab?f(x)dx
( f , P 1 ) = ∫ a b f ( x ) x d x \displaystyle (f,P_1)=\int_{a}^{b}f(x)xdx (f,P1?)=∫ab?f(x)xdx
( f , P 2 ) = ∫ a b f ( x ) 3 x 2 ? 1 2 d x \displaystyle (f,P_2)=\int_{a}^{b}f(x)\frac{3x^2-1}{2}dx (f,P2?)=∫ab?f(x)23x2?1?dx
( f , P 3 ) = ∫ a b f ( x ) x ( 5 x 2 ? 3 ) 2 d x \displaystyle (f,P_3)=\int_{a}^{b}f(x)\frac{x(5x^2-3)}{2}dx (f,P3?)=∫ab?f(x)2x(5x2?3)?dx
得 a 0 ? , a 1 ? , a 2 ? a_0^*,a_1^*,a_2^* a0??,a1??,a2??得到多项式 s ? = a 2 ? x 2 + a 1 ? x + a 0 ? \displaystyle s^*=a_2^*x^2+a_1^*x+a_0^* s?=a2??x2+a1??x+a0??
本章会考一个反三角函数的分部积分法
( a r c t a n x ) ′ = 1 1 + x 2 \displaystyle (arctanx)' = \frac{1}{1+x^2} (arctanx)′=1+x21?
( a r c c o s ) ′ = ? 1 1 ? x 2 \displaystyle (arccos)' = -\frac{1}{\sqrt{1-x^2}} (arccos)′=?1?x2?1?
( a r c c o s ) ′ = ? 1 1 + x 2 \displaystyle (arccos)' = -\frac{1}{\sqrt{1+x^2}} (arccos)′=?1+x2?1?
∫ a b a r c t a n x d x = x a r c t a n x ∣ a b ? 1 2 l n ( 1 + x 2 ) ∣ a b \displaystyle \int_{a}^{b}arctanxdx=xarctanx|_a^b-\frac{1}{2}ln(1+x^2)|_a^b ∫ab?arctanxdx=xarctanx∣ab??21?ln(1+x2)∣ab?
∫ a b a r c s i n x d x = x a r c s i n x ∣ a b + 1 ? x 2 ∣ a b \displaystyle \int_{a}^{b}arcsinxdx=xarcsinx|_a^b+\sqrt{1-x^2}|_a^b ∫ab?arcsinxdx=xarcsinx∣ab?+1?x2?∣ab?
∫ a b a r c c o s x d x = x a r c c o s x ∣ a b ? 1 ? x 2 ∣ a b \displaystyle \int_{a}^{b}arccosxdx=xarccosx|_a^b-\sqrt{1-x^2}|_a^b ∫ab?arccosxdx=xarccosx∣ab??1?x2?∣ab?
T n ≈ h 2 [ f ( a ) + f ( b ) ] \displaystyle T_n \approx \frac{h}{2}[f(a)+f(b)] Tn?≈2h?[f(a)+f(b)] h = b ? a n \displaystyle h=\frac{b-a}{n} h=nb?a?
S n ≈ b ? a 6 [ f ( a ) + 4 f ( b ? a 2 ) + f ( b ) ] \displaystyle S_n \approx \frac{b-a}{6}[f(a)+4f(\frac{b-a}{2})+f(b)] Sn?≈6b?a?[f(a)+4f(2b?a?)+f(b)]
T n ≈ h 2 [ f ( a ) + 2 ∑ k = 1 n ? 1 f ( x k ) + f ( b ) ] \displaystyle T_n \approx \frac{h}{2}[f(a)+2\sum_{k=1}^{n-1}f(x_k)+f(b)] Tn?≈2h?[f(a)+2k=1∑n?1?f(xk?)+f(b)] h = b ? a n \displaystyle h=\frac{b-a}{n} h=nb?a?
S n ≈ h 2 [ f ( a ) + 4 ∑ k = 0 n ? 1 f ( x k + 1 2 ) ∑ k = 1 n ? 1 f ( x k ) + f ( b ) ] \displaystyle S_n \approx \frac{h}{2}[f(a)+4\sum_{k=0}^{n-1}f(x_{k+\frac{1}{2}})\sum_{k=1}^{n-1}f(x_k)+f(b)] Sn?≈2h?[f(a)+4k=0∑n?1?f(xk+21??)k=1∑n?1?f(xk?)+f(b)] h = b ? a n \displaystyle h=\frac{b-a}{n} h=nb?a?
∣ R ( f ) ∣ = b ? a 12 h 2 max ? a ≤ x ≤ b ∣ f ( x ) ′ ′ ∣ \displaystyle |R(f)|=\frac{b-a}{12}h^2\max_{a\le x\le b}|f(x)''| ∣R(f)∣=12b?a?h2a≤x≤bmax?∣f(x)′′∣
∣ R ( f ) ∣ = b ? a 2880 h 4 max ? a ≤ x ≤ b ∣ f ( x ) ( 4 ) ∣ \displaystyle |R(f)|=\frac{b-a}{2880}h^4\max_{a\le x\le b}|f(x)^{(4)}| ∣R(f)∣=2880b?a?h4a≤x≤bmax?∣f(x)(4)∣
开始可以直接根据题目列出 h h h ; f ( x ) f(x) f(x) ; x k = h k x_k=hk xk?=hk ; x k + h 2 = x k + h 2 x_{k+\frac{h}{2}}=x_k+\frac{h}{2} xk+2h??=xk?+2h?
按步长h列表
对应求和，带入公式求解
最后根据对应余项算截断误差
[ a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33 ] = [ 1 0 0 l 21 1 0 l 31 l 32 1 ] [ u 11 u 12 u 13 0 u 22 u 23 0 0 u 33 ] \large \begin{bmatrix}a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\a_{31} & a_{32} & a_{33}\end{bmatrix}=\begin{bmatrix}1 & 0 & 0 \\ l_{21} & 1 & 0 \\l_{31} & l_{32} & 1\end{bmatrix} \begin{bmatrix}u_{11} & u_{12} & u_{13} \\ 0 & u_{22} & u_{23} \\0 & 0 & u_{33} \end{bmatrix} ?a11?a21?a31??a12?a22?a32??a13?a23?a33?? ?= ?1l21?l31??01l32??001? ? ?u11?00?u12?u22?0?u13?u23?u33?? ?
解出 l i j 与 u i j \large l_{ij}与u_{ij} lij?与uij?
A = [ 2 ? 1 0 0 0 ? 1 2 ? 1 0 0 0 ? 1 2 ? 1 0 0 0 ? 1 2 ? 1 0 0 0 ? 1 2 ] \large A = \begin{bmatrix}2 & -1 & 0 & 0 & 0 \\ -1 & 2 & -1 & 0 & 0\\0 & -1 & 2 & -1 & 0\\0 & 0 & -1 & 2 & -1\\ 0 & 0 & 0 & -1 & 2\end{bmatrix} A= ?2?1000??12?100?0?12?10?00?12?1?000?12? ?
分解 A = L U = [ 1 0 0 0 0 p 1 1 0 0 0 0 p 2 1 0 0 0 0 p 3 1 0 0 0 0 p 4 1 ] [ q 1 c 1 0 0 0 0 q 2 c 2 0 0 0 0 q 3 c 3 0 0 0 0 q 4 c 4 0 0 0 0 q 5 ] \large A=LU= \begin{bmatrix}1 & 0 & 0 & 0 & 0 \\ p_1 & 1 & 0 & 0 & 0\\0 & p_2 & 1 & 0 & 0\\0 & 0 & p_3 & 1 & 0\\ 0 & 0 & 0 & p_4 & 1\end{bmatrix} \begin{bmatrix}q_1 & c_1 & 0 & 0 & 0 \\ 0 & q_2 & c_2 & 0 & 0\\0 & 0 & q_3 & c_3 & 0\\0 & 0 & 0 & q_4 & c_4\\ 0 & 0 & 0 & 0 & q_5\end{bmatrix} A=LU= ?1p1?000?01p2?00?001p3?0?0001p4??00001? ? ?q1?0000?c1?q2?000?0c2?q3?00?00c3?q4?0?000c4?q5?? ? 其中c已知常数，为原矩阵对应位置元素
将LU组合一下
[ q 1 c 1 0 0 0 p 1 q 2 c 2 0 0 0 p 2 q 3 c 3 0 0 0 p 3 q 4 c 4 0 0 0 p 4 q 5 ] \large \begin{bmatrix}q_1 & c_1 & 0 & 0 & 0 \\ p_1 & q_2 & c_2 & 0 & 0\\0 & p_2 & q_3 & c_3 & 0\\0 & 0 & p_3 & q_4 & c_4\\ 0 & 0 & 0 & p_4 & q_5\end{bmatrix} ?q1?p1?000?c1?q2?p2?00?0c2?q3?p3?0?00c3?q4?p4??000c4?q5?? ?
平方根法： A = L L T A = LL^T A=LLT
[ 原我 原我 最上 原我 ? 现左 ? 现上 原我 最上 原我 ? 现左 ? 最上 现上 原我 ? 现最左 ? 现最上 ? 现左 ? 现上 ] \large \begin{bmatrix}\sqrt{原我}\\ \frac{原我}{最上} & \sqrt{原我-现左*现上}\\ \frac{原我}{最上} & \frac{原我-现左*最上}{现上} & \sqrt{原我-现最左*现最上-现左*现上}\end{bmatrix} ?原我?最上原我?最上原我??原我?现左?现上?现上原我?现左?最上??原我?现最左?现最上?现左?现上?? ?
改进平方根法： A = L D L T A = LDL^T A=LDLT
[ 原我 原我 现上 原我 ? 现左 ? 现上 ? 相交 原我 最上 原我 ? 现左 ? 最上 ? 相交 现上 原我 ? 现最左 ? 现最上 ? 相交 ? 现左 ? 现上 ? 相交 ] \large \begin{bmatrix}原我\\ \frac{原我}{现上} & 原我-现左*现上*相交\\ \frac{原我}{最上} & \frac{原我-现左*最上*相交}{现上} & \sqrt{原我-现最左*现最上*相交-现左*现上*相交}\end{bmatrix} ?原我现上原我?最上原我??原我?现左?现上?相交现上原我?现左?最上?相交??原我?现最左?现最上?相交?现左?现上?相交?? ?