数值分析复习资料

存在性：Lagrange 插值 \(L_n\) 已构造（定义 1.2），基函数 \(\ell_i\) 均为 \(n\) 次多项式且 \(\ell_i(x_j)=\delta_{ij}\)，故 \(L_n(x_i)=y_i\)。

唯一性：设 \(P,Q\) 均为满足条件的 \(\le n\) 次多项式，则 \(R=P-Q\) 有 \(n+1\) 个互异零点 \(x_0,\dots,x_n\) 而次数 \(\le n\)，故 \(R\equiv0\)。

固定 \(x\ne x_i\)，作辅助函数 \(\varphi(t)=f(t)-L_n(t)-K\omega(t)\)，其中 \(K=\frac{f(x)-L_n(x)}{\omega(x)}\)。则 \(\varphi\) 在 \(x,x_0,\dots,x_n\) 共 \(n+2\) 个互异点处取 0。由 Rolle 定理，\(\varphi'\) 在这些点之间至少有 \(n+1\) 个零点；再 Rolle，\(\varphi''\) 至少有 \(n\) 个零点……递推至 \(\varphi^{(n+1)}\) 在 \((a,b)\) 内至少有一个零点 \(\xi\)：

\(0=\varphi^{(n+1)}(\xi)=f^{(n+1)}(\xi)-K(n+1)!\)，故 \(K=\frac{f^{(n+1)}(\xi)}{(n+1)!}\)，即 \(f(x)-L_n(x)=\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega(x)\)。

(2) 由插值多项式唯一性：Newton 与 Lagrange 是同一多项式，比较 \(x^{n}\) 的系数——Lagrange 形式中 \(x^n\) 的系数正是 \(\sum_i\frac{f(x_i)}{\prod_{j\ne i}(x_i-x_j)}\)，而 Newton 形式的首项系数是 \(f[x_0,\dots,x_n]\)。

(3) 由插值余项公式对 \(x=x_n\) 处求 \(n\) 阶导（\(\omega^{(n)}=n!\)）或直接取重节点极限可得；这也是 (4) 的解析来源。

设 \(\Phi_n=\mathrm{span}\{\varphi_j\}\)。若残差 \(r=f-S^*\) 与所有 \(\varphi_j\) 正交，则对任意 \(S=S^*+h\in\Phi_n\)：

\(\|f-S\|^2=\|r-h\|^2=\|r\|^2-2(r,h)+\|h\|^2=\|r\|^2+\|h\|^2\ge\|r\|^2\)，等号仅当 \(h=0\)，故 \(S^*\) 最优（勾股定理：误差分解为两正交部分）。

反之若某 \((r,\varphi_j)\ne0\)，取 \(h=-\frac{(r,\varphi_j)}{(\varphi_j,\varphi_j)}\varphi_j\in\Phi_n\)，则 \(\|r-h\|^2=\|r\|^2-\frac{(r,\varphi_j)^2}{(\varphi_j,\varphi_j)}<\|r\|^2\)，\(S^*\) 非最优。

法方程即把正交条件展开。Gram 矩阵正定：\(c^TGc=\|\sum c_k\varphi_k\|^2\ge0\)，\(\varphi_j\) 线性无关时仅 \(c=0\) 取 0。

把 \(xp_n(x)\) 对 \(\{p_0,\dots,p_{n+1}\}\) 展开（它们是 \(n+1\) 次多项式空间的基）：\(xp_n=\sum_{k=0}^{n+1}\alpha_kp_k\)。由正交性，\((xp_n,p_k)=(p_n,xp_k)\)：当 \(k

利用二项分布的期望：\(\sum_{k}\binom{n}{k}x^k(1-x)^{n-k}=1\)，\(\sum k\binom{n}{k}x^k(1-x)^{n-k}=nx\)，\(\sum k^2\cdots=nx(1-x)+n^2x^2\)。于是

\(B_n(f,x)-f(x)=\sum_k(f(\tfrac{k}{n})-f(x))\binom{n}{k}x^k(1-x)^{n-k}\)。

由一致连续性，把 \(k\) 分成"\(|k/n-x|\) 小"与"大"两类：前者被 \(\varepsilon\) 控制（\(\sum\) 权重 = 1），后者用 Chebyshev 不等式型估计 \(\sum_{|k/n-x|\ge\delta}\binom{n}{k}x^k(1-x)^{n-k}\le\frac{x(1-x)}{n\delta^2}\to0\)。两段都小，故一致收敛。

\(\int_a^b f=\int_a^b L_n+\int_a^b R_n\)，其中 \(R_n=\frac{f^{(n+1)}(\xi)}{(n+1)!}\omega(x)\)。当 \(f\) 为 \(\le n\) 次多项式时 \(R_n=0\)，故公式精确——代数精度 \(\ge n\)。节点固定（非 Gauss）时，误差项 \(\int_a^b\omega\) 一般非零，故典型公式（梯形、Simpson）的代数精度恰为 \(n\)（Simpson 因对称性额外高一阶）。

梯形：插值余项 \(R_1(x)=\frac{f''(\xi_x)}{2}(x-a)(x-b)\)。因 \((x-a)(x-b)\le0\) 不变号，由积分中值定理（推广形式，被积函数含不变号因子）：

\(\int_a^b R_1=\frac{f''(\eta)}{2}\int_a^b(x-a)(x-b)\,\mathrm{d}x=\frac{f''(\eta)}{2}\cdot\frac{-(b-a)^3}{6}=-\frac{(b-a)^3}{12}f''(\eta)\)。

Simpson：用三次插值 \(H_3\)（含中点，Hermite 型）或对 \(\omega(x)=(x-a)(x-b)(x-c)\)（\(c\) 为中点，奇函数关于 \(c\)）积分消去，得余项含 \(f^{(4)}\) 且系数 \(-1/2880\)。

复化梯形：每个小区间用梯形余项 \(-\frac{h^3}{12}f''(\eta_k)\)，相加得 \(-\frac{h^3}{12}\sum_{k=1}^{n}f''(\eta_k)\)。由"连续函数在稠密点集的取值平均"性质（加权中值），存在 \(\eta\) 使 \(\frac1n\sum f''(\eta_k)=f''(\eta)\)，故误差 \(=-\frac{b-a}{12}h^2f''(\eta)\)。复化 Simpson 同理：每区间余项 \(-\frac{h^5}{2880}f^{(4)}(\eta_k)\)，\(n\) 个相加得 \(-\frac{b-a}{180}h^4f^{(4)}(\eta)\)。

对任意 \(\le 2n+1\) 次多项式 \(f\)，带余除法：\(f=q\cdot p_{n+1}+r\)，\(\deg q\le n\)，\(\deg r\le n\)，其中 \(p_{n+1}\) 为 \(n+1\) 次 Legendre 多项式。因节点 \(x_k\) 是 \(p_{n+1}\) 的零点：\(f(x_k)=r(x_k)\)；又 \(\int_{-1}^1 q\,p_{n+1}=0\)（正交性），故 \(\int f=\int r=\sum A_k r(x_k)=\sum A_k f(x_k)\)——精确。不可能达到 \(2n+2\)：取 \(f=p_{n+1}^2\)（\(\ge0\)），\(\int f>0\) 而 \(\sum A_k f(x_k)=0\)。

设 \(I(h)=I+c_1h^p+c_2h^{2p}+\cdots\)，\(I(h/2)=I+c_1(h/2)^p+c_2(h/2)^{2p}+\cdots\)。作组合 \(\frac{2^p I(h/2)-I(h)}{2^p-1}\)：

\(=\frac{(2^p-1)I+(2^p\cdot c_1(h/2)^p-c_1h^p)+\cdots}{2^p-1}=I+\frac{c_2(2^{p-p}-1)h^{2p}+\cdots}{2^p-1}=I+O(h^{2p})\)——\(h^p\) 项被精确消去，主误差阶升为 \(2p\)。

消元第 \(k\) 步用初等下三角阵 \(L_k=I-l_k e_k^T\)（\(l_k=(0,\dots,0,l_{k+1,k},\dots,l_{nk})^T\)，\(l_{ik}=a_{ik}^{(k-1)}/a_{kk}^{(k-1)}\)）左乘，把第 \(k\) 列主元以下消为 0。顺序主子式非零保证 \(a_{kk}^{(k-1)}\ne0\)（消元可进行到底）。

最后 \(L_{n-1}\cdots L_1A=U\)，故 \(A=L_1^{-1}\cdots L_{n-1}^{-1}U=LU\)，且下三角矩阵之逆仍为下三角、乘积仍单位下三角——存在性。唯一性：设 \(LU=L'U'\)，则 \(L'^{-1}L=U'U^{-1}\) 同时是下三角与上三角，必为对角阵；对角线为 1（单位三角），故恒等，\(L=L',\ U=U'\)。

Cholesky：由对称性 \(LL^T\) 的正定性与 LU 唯一性推导，或直接按列递推 \(l_{ii}=\sqrt{a_{ii}-\sum l_{ik}^2}\)。

\(\delta x=\tilde x-x=A^{-1}\delta b\)，故 \(\|\delta x\|\le\|A^{-1}\|\|\delta b\|\)。又 \(\|b\|=\|Ax\|\le\|A\|\|x\|\)，即 \(\frac1{\|x\|}\le\frac{\|A\|}{\|b\|}\)。相乘：

\(\frac{\|\delta x\|}{\|x\|}\le\|A^{-1}\|\|\delta b\|\cdot\frac{\|A\|}{\|b\|}=\mathrm{cond}(A)\frac{\|\delta b\|}{\|b\|}\)。

系数扰动 \((A+E)\tilde x=b\)：\((I+A^{-1}E)\tilde x=x\)，当 \(\|A^{-1}E\|<1\) 时 \(I+A^{-1}E\) 可逆且 \(\|(I+A^{-1}E)^{-1}\|\le\frac1{1-\|A^{-1}E\|}\)，代入即得上界。

\(x-\tilde x=A^{-1}r\)：\(\|x-\tilde x\|\le\|A^{-1}\|\|r\|\)，除以 \(\|x\|\ge\frac{\|b\|}{\|A\|}\) 得上界。

下界：\(\|r\|=\|A(x-\tilde x)\|\le\|A\|\|x-\tilde x\|\)，且 \(\|x-\tilde x\|/\|x\|\ge\frac{\|r\|}{\|A\|\|x\|}\ge\frac{\|r\|}{\|A\|}\cdot\frac{\|A\|}{\|b\|}\cdot\frac1{\mathrm{cond}(A)}\)（用 \(\|x\|\le\|A^{-1}\|\|b\|\) 与 \(1/\|A^{-1}\|\le\|A\|/\mathrm{cond}(A)\)）。整理即得。

误差向量 \(e^{(k)}=x^{(k)}-x^*\) 满足 \(e^{(k)}=B^k e^{(0)}\)。若对任意初值收敛，则 \(B^k e\to0\) 对一切 \(e\)，故 \(B^k\to0\)。由 Jordan 标准形，\(B^k\to0\iff\) 每个特征值满足 \(|\lambda|<1\)（Jordan 块 \(J_k(\lambda)^m\) 的范数 \(\sim m^{k-1}|\lambda|^{k-m+1}\to0\iff|\lambda|<1\)），即 \(\rho(B)<1\)。

⟸：由 \(\rho(B)<1\) 可取范数 \(\|B\|\le\rho(B)+\varepsilon<1\)（谱半径公式 \(\rho=\lim\|B^k\|^{1/k}\)），则 \(\|e^{(k)}\|\le\|B\|^k\|e^{(0)}\|\to0\)。

Jacobi：\(\|B_J\|_\infty=\max_i\sum_{j\ne i}\frac{|a_{ij}|}{|a_{ii}|}=\max_i\frac{\sum_{j\ne i}|a_{ij}|}{|a_{ii}|}<1\)（严格对角占优 ⟹ 每行比值 <1）。由定理 5.2 的范数充分条件收敛。

Gauss-Seidel：设 \(\rho(B_{GS})\ge1\)，取特征值 \(\lambda\)、\(|\lambda|\ge1\) 与特征向量 \(x\)：\((\lambda D-L)x=Ux\)（\(B_{GS}=(D-L)^{-1}U\) ⟹ \(\lambda(D-L)x=Ux\)）。取 \(|x_m|=\max|x_i|\)：

\(|\lambda||a_{mm}||x_m|\le|a_{mm}||x_m|\le\sum_{j>m}|a_{mj}||x_j|+|\lambda|\sum_{j

由 \(\det B_\omega=\det((D-\omega L)^{-1})\det((1-\omega)D+\omega U)\)，因 \((D-\omega L)^{-1}\) 下三角对角 1，\(\det B_\omega=\det((1-\omega)D+\omega U)=(1-\omega)^n\det D\cdot\det D^{-1}=(1-\omega)^n\)（三角阵行列式 = 对角元乘积）。故 \(\prod\lambda_i=(1-\omega)^n\)，若 \(|\lambda_i|<1\) 则 \(|1-\omega|=\prod|\lambda_i|^{1/n}<1\)，即 \(0<\omega<2\)。

唯一性：若 \(x^*,y^*\) 均为不动点，\(|x^*-y^*|=|\varphi(x^*)-\varphi(y^*)|\le q|x^*-y^*|\)，\(q<1\) 迫使相等。

收敛：\(|x_{k+1}-x_k|=|\varphi(x_k)-\varphi(x_{k-1})|\le q|x_k-x_{k-1}|\le q^k|x_1-x_0|\)，故 \(\{x_k\}\) 是 Cauchy 列（\(q<1\)），收敛于 \(\bar x\in[a,b]\)（闭区间）；由连续性 \(\bar x=\varphi(\bar x)\)。误差：\(|x_k-x^*|\le\sum_{j=k}^{\infty}|x_{j+1}-x_j|\le\sum_{j=k}^{\infty}q^j|x_1-x_0|=\frac{q^k}{1-q}|x_1-x_0|\)。

收敛阶：Taylor \(\varphi(x_k)-\varphi(x^*)=\varphi'(x^*)(x_k-x^*)+O((x_k-x^*)^2)\)。

在 \(x_k\) 处展开：\(0=f(x^*)=f(x_k)+f'(x_k)(x^*-x_k)+\frac{f''(\xi_k)}{2}(x^*-x_k)^2\)。两边除以 \(f'(x_k)\) 并移项：

\(x^*-\big(x_k-\frac{f(x_k)}{f'(x_k)}\big)=\frac{f''(\xi_k)}{2f'(x_k)}(x^*-x_k)^2\)，即 \(x^*-x_{k+1}=\frac{f''(\xi_k)}{2f'(x_k)}(x_k-x^*)^2\)。

因 \(f'(x^*)\ne0\) 且连续，邻域内 \(|f'|\ge m>0\)、\(|f''|\le M\)，故 \(|x_{k+1}-x^*|\le\frac{M}{2m}|x_k-x^*|^2\)。若初值满足 \(\frac{M}{2m}|x_0-x^*|<1\)，递推得二次收敛。

由差商性质 \(f[x_k,x_{k-1}]=f'(\eta_k)\)（\(\eta_k\) 在两点间），割线格式写为 \(e_{k+1}=e_k-\frac{f(x_k)}{f[x_k,x_{k-1}]}\)。用 Taylor 展开 \(f(x_k)=f'x^*e_k+\frac{f''}{2}e_k^2+O(e_k^3)\) 与 \(f[x_k,x_{k-1}]=f'+O(e_{k-1})\)，得

\(e_{k+1}\approx\frac{f''}{2f'}(e_k^2-e_ke_{k-1})=\frac{f''}{2f'}e_ke_{k-1}\)。设 \(|e_k|\approx C|e_{k-1}|^p\)，代入 \(e_{k+1}=C e_ke_{k-1}\) 比较指数得 \(p^2=p+1\)，\(p=\frac{1+\sqrt5}{2}\)。

\(A^k v_0=\sum c_i\lambda_i^k u_i=\lambda_1^k\big(c_1u_1+\sum_{i\ge2}c_i(\tfrac{\lambda_i}{\lambda_1})^k u_i\big)\)。因 \(|\lambda_i/\lambda_1|<1\)，括号内第二项 \(\to0\)，故 \(A^k v_0/\lambda_1^k\to c_1u_1\)；归一化后方向趋于 \(u_1\)。Rayleigh 商收敛：\(\frac{v_k^TAv_k}{v_k^Tv_k}\to\lambda_1\)（\(v_k\to u_1\) 时商 \(\to u_1^TAu_1=\lambda_1\)）。

设 \(\lambda\) 为特征值、\(x\) 为对应特征向量，取 \(|x_m|=\max_j|x_j|\ne0\)。由 \(Ax=\lambda x\) 的第 \(m\) 行：\((\lambda-a_{mm})x_m=\sum_{j\ne m}a_{mj}x_j\)，故

\(|\lambda-a_{mm}||x_m|\le\sum_{j\ne m}|a_{mj}||x_j|\le|x_m|\sum_{j\ne m}|a_{mj}|\)，即 \(|\lambda-a_{mm}|\le\sum_{j\ne m}|a_{mj}|\)——\(\lambda\) 属于第 \(m\) 个圆盘。

全局误差 \(E_{n+1}=|y(x_{n+1})-y_{n+1}|\le|y(x_{n+1})-\big(y(x_n)+h\Phi(x_n,y(x_n),h)\big)|+|h\Phi(x_n,y(x_n),h)-h\Phi(x_n,y_n,h)|\)

\(\le T_{n+1}+hL|y(x_n)-y_n|\)（Lipschitz：\(|\Phi(x,y)-\Phi(x,z)|\le L|y-z|\)）。于是 \(E_{n+1}\le(1+hL)E_n+Ch^{p+1}\)，递推（用 \(1+hL\le e^{hL}\) 与几何级数）：

\(E_n\le e^{n hL}E_0+\frac{e^{nhL}-1}{hL}\cdot Ch^{p+1}=O(h^p)\)（\(nh\le b-a\) 固定，\(E_0=0\)）。

显式 Euler 代入 \(y'=\lambda y\)：\(y_{n+1}=(1+h\lambda)y_n\)，误差按 \(|1+h\lambda|\) 缩放。要求 \(|1+h\lambda|<1\) 即 \(h\in(0,-2\mathrm{Re}\,\lambda/|\lambda|^2)\)。

隐式 Euler：\(y_{n+1}=y_n+h\lambda y_{n+1}\Rightarrow y_{n+1}=\frac{1}{1-h\lambda}y_n\)。当 \(\mathrm{Re}\,\lambda<0\) 时 \(1-h\lambda\) 在右半平面，模 >1，故因子模 <1——无条件稳定，步长只受精度限制。