数值分析笔记整理

2023-12-27 19:28:12

数值分析笔记整理(上)

?

第一章 计算误差评估算法稳定性

1、计算误差限

做题步骤:
  • 求初值误差限 ∣ ε 0 ∣ |\varepsilon_{0}| ε0?
  • 用题中所给条件推出n=1,2,3……的误差限,直到找到规律
  • 用误差限通项公式求得目标项误差限

2、有效数字

∣ 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??x21?m?n+1

  • 这里m是将数值变成标准形式(x.xxxx)小数点移动的位数,右移为负,左移为正,n为数值的有效数字
  • 例:0.314 化为标准形式,小数点需右移一位,m=-1;有效数字为3位,n=3; 此时m-n+1=-3 ; ∣ 0.314 ? x ∣ ≤ 1 2 ? 1 0 ? 3 |0.314-x|\le \frac{1}{2}*10^{-3} ∣0.314?x21??10?3

3、评估算法稳定性

  • 首先正推计算误差限

卷面要体现如 ∣ 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?=aEN?=?=anEn?

  • { a < 1 误差减小;算法稳定 a > 1 误差增大;算法不稳定 \begin{cases} a<1 误差减小;算法稳定\\ a>1 误差增大;算法不稳定 \end{cases} {a<1误差减小;算法稳定a>1误差增大;算法不稳定?

  • 若算法不稳定,选取一个较大的N,逆推回第一项

第二章插值法

1、拉格朗日插值法

  • 拉格朗日插值基函数

    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=0n?yk??lk(x)?

2、牛顿插值法

  • 差商

    一阶差商: 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??

第三章函数逼近

1、最佳平方逼近

做题步骤
  • 一般题中会给出f(x);要求f(x)在某一区间上 ρ ( x ) = 1 , Ψ = s p a n { 1 x x 2 ? } \displaystyle \rho(x)=1,\varPsi=span\begin{Bmatrix} 1 & x & x^2 \cdots\end{Bmatrix} ρ(x)=1,Ψ=span{1?x?x2??} ,要求最佳平方逼近多项式
  • 根据 Ψ = s p a n { 1 x x 2 ? } \displaystyle \varPsi=span\begin{Bmatrix} 1 & x & x^2 \cdots\end{Bmatrix} Ψ=span{1?x?x2??}设出 ? 0 = 1 , ? 1 = x , ? 2 = x 2 ? \displaystyle \phi_0=1,\phi_1=x,\phi_2=x^2 \cdots ?0?=1,?1?=x,?2?=x2?
  • 求法方程元素:

( ? 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?)? ?

  • 解方程得 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_2x^2+a_1x+a_0 s?=a2?x2+a1?x+a0?

2、勒让德多项式

  • 若题中要求[-1,1]区间则可以用勒让德多项式求解
  • 记住勒让德多项式前三项

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 n ? = 2 n + 1 2 ∫ a b f ( x ) P n ( x ) d x \displaystyle a_n^* = \frac{2n+1}{2}\int_{a}^{b}f(x) P_n(x)dx an??=22n+1?ab?f(x)Pn?(x)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=xarctanxab??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=xarcsinxab?+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=xarccosxab??1?x2 ?ab?

第四章 数值积分与数值微分

1、 依据求积公式求代数精度与待定参数

  • 代数精度:如果某个求积公式对于次数不超过m的多项式能准确成立,但对于m+1次多项式就不准确成立,则称该求积公式具有m次代数精度

做题步骤

  • 若求积公式中存在n个未知参数,则直接将 f ( x ) = 1 ; x ; x 2 ? x n f(x)=1;x;x^2\cdots x^n f(x)=1;x;x2?xn分别带入公式中,令两端相等求得未知参数
  • 若求积公式中无未知参数,则将 f ( x ) = 1 ; x ; x 2 ? x n f(x)=1;x;x^2\cdots x^n f(x)=1;x;x2?xn分别带入求积公式,验证两端是否相等
  • 若在第k次公式左边≠右边,则该求积公式具有k-1次代数精度

2、(复合)梯形公式与(复合)辛普森公式

  • 梯形公式

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=1n?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=0n?1?f(xk+21??)k=1n?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?h2axbmax?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?h4axbmax?f(x)(4)

3、做题技巧

  • 开始可以直接根据题目列出 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列表

  • 对应求和,带入公式求解

  • 最后根据对应余项算截断误差

第五章求解线性方程组的直接方法

1、高斯消去法

  • 消元法求解矩阵方程,写出消元过程

2、直接三角法分解(杜利特尔Doolittle分解)求线性方程

  • 将系数矩阵A分解成上、下三角矩阵 A=LU

[ 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?

  • 解方程 { L y = b U x = y \large \begin{cases}Ly=b \\ Ux=y\end{cases} ? ? ??Ly=bUx=y?求出x

2、追赶法求解三对角方程组

  • 例:

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?? ?

  • 求解公式 { q 1 = a 1 p i = a i q i ? 1 q i = a i ? p i c i ? 1 \large \begin{cases} q_1=a_1 \\ p_i=\frac{a_i}{q_{i-1}} \\ q_i = a_i-p_ic_{i-1} \end{cases} ? ? ??q1?=a1?pi?=qi?1?ai??qi?=ai??pi?ci?1??
  • 快捷记忆法: { q 1 = a 1 我 = 原我 现上 我 = 原我 ? 现左 ? 现上 \large \begin{cases} q_1=a_1 \\ 我=\frac{原我}{现上} \\ 我 = 原我-现左*现上 \end{cases} ? ? ??q1?=a1?=现上原我?=原我?现左?现上?
  • 求得p,q,c,还原LU,解出方程组

3、(改进)平方根法求解线性方程组

平方根法: 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} ?原我现上原我?最上原我??原我?现左?现上?相交现上原我?现左?最上?相交??原我?现最左?现最上?相交?现左?现上?相交 ?? ?

文章来源:https://blog.csdn.net/weixin_63087177/article/details/135230999
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。