文档
计算机科学
数值分析
方程的迭代解法

方程的迭代解法

  • 确定初值
    • 画图法
    • 扫描法
      • 在有根区间中，选定一个步长 hh，用零点定理确定当前区间 [x0,x0+h][x_0,x_0 + h] 内是否有根，并令 x0⟵x0+hx_0 \longleftarrow x_0 + h，判断下一个区间。
      • 如果 hh 过大可能漏掉根，如果过小则计算量大。
    • 二分法
      • 不断切分当前区间 [a,b][a,b]，进入有根的子区间，并继续寻找。
      • 切分 nn 次后，最终子区间长度为 b−a2n\dfrac{b - a}{2^n}，方法误差 ∣Δxn∣≤b−a2n|\Delta x_n| \le \dfrac{b - a}{2^n}。
      • 如果要求 ∣Δxn∣≤ε|\Delta x_n| \le \varepsilon，则 n≥log⁡2b−aε=ln⁡(b−a)−ln⁡εln⁡2n \ge \log_2\dfrac{b - a}{\varepsilon} = \dfrac{\ln(b - a) - \ln \varepsilon}{\ln 2}。
      • 二分法无法求复根以及偶重根。
  • 迭代方法
    • 迭代计算
      • 已知方程 f(x)=0f(x) = 0，则将其变换为 x=φ(x)x = \varphi(x)，则 xn+1=φ(xn)x_{n + 1} = \varphi(x_n) 是迭代公式。
      • 从初值 x0x_0 开始，得到 x1=φ(x0),x2=φ(x1),…x_1 = \varphi(x_0),x_2 = \varphi(x_1),\dots，则 x0,x1,x2,…x_0,x_1,x_2,\dots 是迭代序列。
      • 如果 lim⁡n→+∞xn=α\lim\limits_{n \to +\infty} x_n = \alpha 存在，则 α\alpha 就是方程的根。如果发散，则这种迭代法失效。
    • 收敛性
      • 类型
        • 大范围收敛：任意位置都可以收敛。
        • 局部收敛：收敛速度更块，但需要初值接近根。
      • 收敛的充分条件
        • 如果在 [a,b][a, b] 上 φ(x)\varphi(x) 可导，且满足 ∣φ′(x)∣≤q<1|\varphi'(x)| \le q < 1，则迭代过程收敛。
        • qq 在此处保证 ∣φ′(x)∣|\varphi'(x)| 不是收敛于 11。
        • qq 越小则收敛越快。
        • 实际应用中，[a,b][a,b] 长度较小，∣φ′(x)∣|\varphi'(x)| 变化较小，所以只判断 ∣φ(x0)∣<1|\varphi(x_0)|<1。
      • 收敛速度
        • 如果存在正数 r,cr,c 满足 lim⁡n→+∞∣xn+1−a∣∣xn−a∣r=c\lim\limits_{n \to +\infty} \dfrac{|x_{n+1} - a|}{|x_n - a|^r} = c，则其 rr 阶收敛。
    • 终止条件
      • 迭代终止条件为 ∣xn−α∣<ε|x_n - \alpha| < \varepsilon，但需要估计一个 ∣xn−α∣|x_n - \alpha| 的上界来解决 α\alpha 未知的问题。
      • 常用上界公式：
        • ∣xn−α∣≤q1−q∣xn−xn−1∣|x_n - \alpha| \le \dfrac{q}{1 - q}|x_n - x_{n - 1}|，对于 q≤0.5q\le 0.5 时，可以用 ∣xn−α∣≤∣xn−xn−1∣|x_n - \alpha| \le |x_n - x_{n - 1}| 替代。
        • ∣xn−α∣≤qn1−q∣x1−x0∣|x_n - \alpha| \le \dfrac{q^n}{1 - q}|x_1 - x_0|，该公式可以估计 nn。
        • ∣xn−α∣≤∣φ(xn)∣m,m≤∣φ′(x)∣|x_n - \alpha| \le \dfrac{|\varphi(x_n)|}{m},m \le |\varphi'(x)|。
    • 误差分析
  • 常用迭代公式
    • 构造迭代公式
      • 构造法 1
        • 已知方程 x=φ(x)x = \varphi(x)，引入参数 θ\theta 并变换得到 x−θx=φ(x)−θxx - \theta x = \varphi(x) - \theta x。
        • 整理并构造一个迭代公式 xn+1=11−θ(φ(x)−θx)=ψ(x)x_{n + 1} = \dfrac{1}{1 - \theta}(\varphi(x) - \theta x) = \psi(x)。
        • 通过选取 θ≈ψ′(x)\theta \approx \psi'(x)，可以使该迭代公式的 ∣q∣|q| 较小。
      • 构造法 2
        • 已知方程 f(x)=0f(x) = 0，构造迭代公式 xn+1=xn−λf(xn)x_{n + 1} = x_n - \lambda f(x_n) 。
      • 反函数法
        • 如果 ∣φ′(x)∣>1|\varphi'(x)|>1，则可以构造 φ(x)\varphi(x) 的反函数 ψ(x)\psi(x)，变换迭代公式为 x=ψ(x)x = \psi(x)，并且满足收敛条件。
    • 经典公式
      • 埃特金法
        • 埃特金法基于构造法 1。
        • 对于方程 x=φ(x)x = \varphi(x)，首先选定初值 x0x_0，按照以下方式迭代：
          • 已知当前为 xnx_n，计算 yn+1=φ(xn)y_{n + 1} = \varphi(x_n) 和 zn+1=φ(yn+1)=φ(φ(xn))z_{n + 1} = \varphi(y_{n + 1}) = \varphi(\varphi(x_n))。
          • 计算 θn=zn+1−yn+1yn+1−xn\theta_n = \dfrac{z_{n + 1} - y_{n + 1}}{y_{n + 1} - x_n}。
          • 得出 xn+1=11−θn(φ(xn)−θnxn)=xnzn+1−yn+12xn−2yn+1+zn+1x_{n + 1} = \dfrac{1}{1 - \theta_n}\left(\varphi(x_n) - \theta_n x_n\right) = \dfrac{x_n z_{n + 1} - y_{n + 1}^2}{x_n - 2y_{n + 1} + z_{n + 1}}。
        • 整理后的迭代公式：xn+1=xnφ(φ(xn))−(φ(xn))2xn−2φ(xn)+φ(φ(xn))x_{n + 1} = \dfrac{x_n \varphi(\varphi(x_n)) - (\varphi(x_n))^2}{x_n - 2\varphi(x_n) + \varphi(\varphi(x_n))}。
        • 埃特金法的几何意义是用割线代替曲线 y=φ(x)y = \varphi(x) 求与 y=xy = x 的交点。
        • 收敛阶为 22。
      • 牛顿法
        • 牛顿法基于构造法 2，选取 λ=1f′(xn)\lambda = \dfrac{1}{f'(x_n)}，迭代公式为 xn+1=xn−f(xn)f′(xn)x_{n + 1} = x_n - \dfrac{f(x_n)}{f'(x_n)}。
        • 牛顿法的几何意义是用切线代替曲线求与 xx 轴交点，又叫切线法。
        • 牛顿法在 [a,b][a,b] 内的收敛条件：
          • f(x)f(x) 在 [a,b][a,b] 内二阶可导；
          • f(a)f(b)<0f(a)f(b) < 0；
          • f′(x)≠0f'(x) \ne 0，f′′(x)f''(x) 不变号；
          • f(x0)f′′(x0)>0f(x_0)f''(x_0) > 0。
        • 牛顿法对初值敏感，如果初值靠近根，则求解快速，否则不容易收敛。
        • 收敛阶为 22。
      • 简化切线法
        • 基于构造法 2，选取 λ=1f′(x0)\lambda = \dfrac{1}{f'(x_0)}，迭代公式为 xn+1=xn−f(xn)f′(x0)x_{n + 1} = x_n - \dfrac{f(x_n)}{f'(x_0)}。
        • 切线固定为初值处的切线。
      • 修正切线法
        • 基于构造法 2 和简化切线法，每迭代 mm 次，重新选取当前 xnx_n 处的切线斜率作为 λ\lambda。
      • 牛顿下山法
        • 定义下山条件为 ∣f(x)∣>∣f(x1)∣>∣f(x2)∣>⋯|f(x)| > |f(x_1)| > |f(x_2)| > \cdots，牛顿下山法要求迭代的 xx 需要满足下山条件以保证收敛。
        • 引入下山因子 λ~\tilde\lambda，迭代公式改为 xn+1=xn−λ~f(xn)f′(xn)x_{n + 1} = x_n - \tilde\lambda\dfrac{f(x_n)}{f'(x_n)}。
        • 对于某个 λ~\tilde\lambda，如果迭代出的下一个 xx 不满足下山条件，则不断缩小 λ~\tilde\lambda（一般除以 22），直到满足。
        • 每一次迭代， λ~\tilde\lambda 继承上一次的。
        • 通常为 λ~\tilde\lambda 设置一个最小值，如果减小过了最小值，则需要重新选取初值计算。
      • 单点弦截法
        • 基于构造法 2，λ\lambda 的计算中，用割线的斜率代替导数，即 λ=1ΔyΔx=xn−x0f(xn)−f(x0)\lambda = \dfrac{1}{\frac{\Delta y}{\Delta x}} = \dfrac{x_n - x_0}{f(x_n) - f(x_0)}。
        • 迭代过程中，割线只有一个点变化，所以是单点弦截法。
        • 迭代公式为 xn+1=x0f(xn)−xnf(x0)f(xn)−f(x0)x_{n + 1} = \dfrac{x_0 f(x_n) - x_n f(x_0)}{f(x_n) - f(x_0)}。
        • 在 [a,b][a,b] 内的收敛条件：
          • f(x)f(x) 在 [a,b][a,b] 内二阶可导；
          • f(a)f(b)<0f(a)f(b) < 0；
          • f′(x)≠0f'(x) \ne 0，f′′(x)f''(x) 不变号；
          • f(x0)f′′(x0)>0f(x_0)f''(x_0) > 0；
          • f(x0)≠f(x1)f(x_0) \ne f(x_1)。
        • 收敛阶为 11。
      • 双点弦截法
        • 基于构造法 2 和单点弦截法，割线选取最后两个点的连线，λ=1ΔyΔx=xn−xn−1f(xn)−f(xn−1)\lambda = \dfrac{1}{\frac{\Delta y}{\Delta x}} = \dfrac{x_n - x_{n - 1}}{f(x_n) - f(x_{n - 1})}。
        • 迭代公式为 xn+1=xn−1f(xn)−xnf(xn−1)f(xn)−f(xn−1)x_{n + 1} = \dfrac{x_{n - 1} f(x_n) - x_n f(x_{n - 1})}{f(x_n) - f(x_{n - 1})}。
        • 在 [a,b][a,b] 内的收敛条件：
          • f(x)f(x) 在 [a,b][a,b] 内二阶可导；
          • f(a)f(b)<0f(a)f(b) < 0；
          • f′(x)≠0f'(x) \ne 0。
        • 收敛阶为 1+52\dfrac{1 + \sqrt 5}{2}。
数值计算误差方程组的迭代解法