计算方法B.裴玉茹.05.最小二乘(3)

Posted on Edited on In Views:
最小二乘、法线方程、离散最小二乘、连续最小二乘、多项式模型、正交条件（简化最小二乘）
  • 数值分析课本第 4 章（最小二乘） + PPT（最小二乘法）

最小二乘

  • PPT 补充

1. 拟合与插值

拟合 插值
参数 \(a_1,\cdots,a_n(n<m)\) 参数 \(a_1,\cdots,a_m\)
\(y_k(x_k)\approx y_k\) \(y_k(x_k)=y_k\)
近似关系 精确通过
简单函数 复杂函数

过拟合

  • 将具有 \(n\) 个自由度的函数拟合到 \(n\) 个数据点上，不会留下数据点上的误差

2. 最小二乘

  • 有解 or 无解

  • 超定方程
    • 可能是不相容的线性方程组

法线方程

  • 余项范数 \(\Vert{b-Ax}\Vert_2\) 的极小值满足法线方程 \(A^{T}Ax=A^{T}b\)

\[ \Vert{b-Ax}\Vert_2^{2}=(b-Ax)^{T}(b-Ax)=b^{T}b-2x^{T}A^{T}b+x^{T}A^{T}Ax \]

  • 极小值满足偏导数为 0

\[ -2A^{T}b+2A^{T}Ax=0 \]

  • 法线方程

\[ A^{T}Ax=A^{T}b \]

矩阵求导

  • \(\dfrac{\partial{Ax}}{\partial{x}}=A\)

\[ \dfrac{\partial{y}}{\partial{x}}=\begin{pmatrix} \dfrac{\partial{y_1}}{\partial{x_1}}&\cdots&\dfrac{\partial{y_1}}{\partial{x_n}}\\ \vdots&&\vdots\\ \dfrac{\partial{y_n}}{\partial{x_1}}&\cdots&\dfrac{\partial{y_n}}{\partial{x_n}}\\ \end{pmatrix} \]

  • \(\dfrac{\partial{x^{T}A}}{\partial{x}}=A^{T}\)
  • \(\dfrac{\partial{x^{T}b}}{\partial{x}}=\dfrac{\partial{b^{T}x}}{\partial{x}}=b\)
  • \(\dfrac{\partial{x^{T}Ax}}{\partial{x}}=(A+A^{T})x\)

\[ x^{T}Ax=\sum_{j=1}^{n}x_j\sum_{i=1}^{n}x_ia_{ij}=\sum_{j=1}^{n}\sum_{i=1}^{n}a_{ij}x_ix_j \]

\[ \dfrac{\partial{y_i}}{\partial{x_j}}=(a_{ij}+a_{ji})x_i \]

3. 离散最小二乘近似

  • 拟合数据点

不同误差度量

  • 最小最大：对最差的点给了最大的权重

\[ \max_{1\le i\le m}\vert{P(x_i)-y_i}\vert \]

  • 绝对偏差：没有给直线外点足够的权重

\[ \sum_{i=1}^{m}\vert{P(x_i)-y_i}\vert \]

  • 最小二乘

\[ \sum_{i=1}^{m}\Vert{P(x_i)-y_i}\Vert^{2} \]

直线拟合

  • 最小二乘

\[ E=\sum_{i=1}^{m}({y_i-(a_0+a_1x_i)})^{2} \]

  • 极值定理，可以求得 \(a_0,a_1\)

\[ \dfrac{\partial{E}}{\partial{a_0}}=0,\dfrac{\partial{E}}{\partial{a_1}}=0 \]

  • 解得

\[ a_0=\dfrac {\left(\sum_{i=1}^{m}x_i^2\right)\left(\sum_{i=1}^{m}y_i\right)-\left(\sum_{i=1}^{m}x_i\right)\left(\sum_{i=1}^{m}x_iy_i\right)} {m\left(\sum_{i=1}^{m}x_i^2\right)-\left(\sum_{i=1}^{m}x_i\right)\left(\sum_{i=1}^{m}x_i\right)} \]

\[ a_1=\dfrac {m\left(\sum_{i=1}^{m}x_iy_i\right)-\left(\sum_{i=1}^{m}x_i\right)\left(\sum_{i=1}^{m}y_i\right)} {m\left(\sum_{i=1}^{m}x_i^2\right)-\left(\sum_{i=1}^{m}x_i\right)\left(\sum_{i=1}^{m}x_i\right)} \]

多项式拟合

\[ p_n(x)=a_nx^n+\cdots+a_1x+a_0 \]

  • 最小二乘

\[ E=\sum_{i=1}^{m}({y_i-p_n(x)})^{2} \]

  • 极值定理

\[ \dfrac{\partial{E}}{\partial{a_j}}=-2\sum_{i=1}^{m}(y_i-p_n(x_i))x_i^j=-2\sum_{i=1}^{m}y_ix_i^{j}+2\sum_{k=0}^{n}a_k\sum_{i=1}^{m}x_i^{k+j} \]

\[ \sum_{k=0}^{n}a_k\sum_{i=1}^{m}x_{i}^{k+j}=\sum_{i=1}^{m}y_ix_{i}^{j},j=0,\cdots,n \]

  • 得到一组方程组，当 \(x_i\) 都不相同，方程组具有唯一解

\[ \begin{align} a_0\sum_{i=1}^{m}x_{i}^{1}+a_1\sum_{i=1}^{m}x_{i}^{1}+\cdots+a_n\sum_{i=1}^{m}x_{i}^{n}&=\sum_{i=1}^{m}y_ix_{i}^{0}\\ &\cdots\\ a_0\sum_{i=1}^{m}x_{i}^{n}+a_1\sum_{i=1}^{m}x_{i}^{n+1}+\cdots+a_n\sum_{i=1}^{m}x_{i}^{2n}&=\sum_{i=1}^{m}y_ix_{i}^{n}\\ \end{align} \]

唯一解证明

  • 构造 \((n+1)\times(n+1)\) 阶矩阵 \(A=(a_{ij})\)，\(m>n+1\)
    • 下标 1 开始

\[ a_{ij}=\sum_{k=1}^{m}x_{k}^{i+j-2} \]

  • 构造 \((n+1)\) 维向量 \(a\) 如下

\[ x=(a_0,\cdots,a_n)^{T} \]

  • 构造 \((n+1)\) 维向量 \(b\) 如下

\[ y=\left(\sum_{i=1}^{m}y_ix_i^0,\cdots,\sum_{i=1}^{m}y_ix_i^n\right)^{T} \]

  • 法线方程转化为

\[ Ax=y \]

  • 相当于已知 \(A,y\) 求解 \(x\)，唯一解等价于证明 \(A\) 是非奇异矩阵
  • 假设 \(A\) 是奇异矩阵，则存在向量 \(c\ne0\) 使得 \(c^{T}A{c}=0\)（\(A\) 中向量不能张成 \(n+1\) 维空间 ）
  • 我们对 \(A\) 做分解，令 \(m\times(n+1)\) 阶 \(B=(b_{ij})\)

\[ b_{ij}=x_{i}^{j-1} \]

  • 我们可以得到 \(A=B^{T}B\)
  • \(c^{T}Ac=c^{T}B^{T}Bc=(Bc)^T(Bc)=0\)
  • 我们设 \(f(x)=c_0+c_1x+\cdots+c_nx^{n}\)

\[ Bc=\Big(f(x_1),\cdots,f(x_m)\Big)^{T} \]

\[ (Bc)^{t}(BC)=f^2(x_1)+\cdots+f^2(x_m)=0 \]

  • 于是我们得到 \(f(x)=0\) 有 \(m\) 个解 \(x_1,\cdots,x_m\)
  • 而 \(f(x)\) 的阶数为 \(n\)，最多有 \(n\) 个解，而 \(m>n+1>n\)，推出矛盾
  • 因此 \(A\) 是非奇异矩阵，法线方程具有唯一解

非线性模型

  • 指数模型：线性化
    • 两个模型求解一般不同：误差 / 损失函数不同
  • 模型函数、损失函数

4. 连续最小二乘

多项式模型

  • \(n\) 阶多项式近似

\[ p_n(x)=a_nx^n+\cdots+a_1x+a_0 \]

  • 误差

\[ E=\int_{a}^{b}(f(x)-p_n(x))^2\;\mathrm{d}x \]

  • 极值定理

\[ \dfrac{\partial{E}}{\partial{a_j}}=-2\int_{a}^{b}(f(x)-p_n(x))x^j\;\mathrm{d}x=-2\int_{a}^{b}f(x)x^{j}\;\mathrm{d}x+2\sum_{k=0}^{n}a_k\int_{a}^{b}x^{k+j}\;\mathrm{d}x=0 \]

\[ \sum_{k=0}^{n}a_k{\color{red}\int_{a}^{b}x^{k+j}\;\mathrm{d}x}=\int_{a}^{b}f(x)x^{j}\;\mathrm{d}x \]

  • 其中红色部分

\[ \int_{a}^{b}x^{k+j}\;\mathrm{d}x=\dfrac{b^{j+k+1}-a^{j+k+1}}{j+k+1} \]

  • 求解 \(n+1\) 个未知数 \(a_j\)
  • 系数矩阵的条件数很大，病态矩阵
  • 希尔伯特矩阵（Hilbert 矩阵）
    • \(H=(h_{ij})=(\dfrac{1}{i+j-2})\)
    • 条件数 \(cond(H_n)_{\infty}\to\infty\)

线性无关

  • 如果 \(c_0\phi_0+\cdots+c_n\phi_n=0\) 在 \([a,b]\) 上恒成立能够推出 \(c_j=0,\forall j\)，则函数 \(\phi_0,\cdots,\phi_n\) 在区间 \([a,b]\) 上线性无关

多项式

  • 如果 \(\phi_j\) 是 \(j\) 阶多项式，那么多项式 \(\{\phi_0,\cdots,\phi_n\}\) 在区间 \([a,b]\) 上线性无关
  • 证明
    • 从 \(\phi_n\) 开始，因为只有这一个多项式含有 \(n\) 次方项，于是 \(c_n=0\)
    • 逐步向低阶，此时只有 \(\phi_{n-1}\) 有 \(n-1\) 次方项，于是 \(c_{n-1}=0\)
    • 类似的，证明 \(c_j=0,\forall j\)
  • \(\prod_n\)：至多 \(n\) 阶多项式集合
    • \(\{\phi_0,\cdots,\phi_n\}\) 是 \(\prod_n\) 中的线性无关多项式集合，则 \(\prod_n\) 中的任意多项式可以唯一写作 \(\{\phi_0,\cdots,\phi_n\}\) 的线性组合

权函数

  • \(w(x)\)：在区间 \(I\) 中，\(w(x)\ge0\)，在 \(I\) 的任意子区间中 \(w(x)\ne0\)

多项式基函数组合模型

  • 修改 \(p_n(x)\) 如下

\[ p_n(x)=\sum_{k=0}^{n}a_k\phi_k(x) \]

  • 误差

\[ E=\int_{a}^{b}w(x)(f(x)-p_n(x))^2\;\mathrm{d}x \]

  • 类似的，使用极值定理求解系数

\[ \dfrac{\partial{E}}{\partial{a_j}} =\int_{a}^{b}w(x)[f(x)-\sum_{k=0}^{n}a_k\phi_k(x)]\phi_j(x)\;\mathrm{d}x =0 \]

\[ \int_{a}^{b}w(x)f(x)\phi_j(x)\;\mathrm{d}x=\sum_{k=0}^{n}a_k\int_{a}^{b}w(x)\phi_k(x)\phi_j(x)\;\mathrm{d}x \]

正交条件

  • 关于权函数 \(w\) 的正交函数集合\(\{\phi_0,\cdots,\phi_n\}\) 满足

\[ \int_a^bw(x)\phi_i(x)\phi_j(x)=\left\{\begin{array}{rr} 0,&j\ne i\\ \alpha_i,&j=i \end{array}\right. \]

  • 单位正交集合：\(\alpha_i=0\)
  • 最小二乘近似被简化

\[ \int_{a}^{b}w(x)f(x)\phi_j(x)\;\mathrm{d}x=\sum_{k=0}^{n}a_k\int_{a}^{b}w(x)\phi_k(x)\phi_j(x)\;\mathrm{d}x=a_j\alpha_j \]

\[ a_j=\dfrac{\int_{a}^{b}w(x)f(x)\phi_j(x)\;\mathrm{d}x}{\alpha_j} =\dfrac{\int_{a}^{b}w(x)f(x)\phi_j(x)\;\mathrm{d}x}{\int_{a}^{b}w(x)\phi_j^2(x)\;\mathrm{d}x} \]