方程求根

• 代数方程：$f(x)=\sum_{i=0}^n a_{n-i}x^{i}$
  • 复数域中有 $n$ 个根
• 非线性方程
  • 超越方程：必须明确定义域
• 搜索法求有根区间
• 二分法
  • 收敛速度不快
  • 可以确定初始区间

不动点迭代法

• 不动点迭代法：求 $f(x)=0$ 转换为求 $ x=\varphi(x)$ 的不动点
  • 迭代法：$x_{k+1}=\varphi(x_k)$
  • 收敛：$\lim_{k\rightarrow\infty} x_k$ 存在
  • 定理：$\varphi(x)\in C[a,b]$ 满足以下条件则在 $[a,b]$ 上存在唯一的不动点
    • $\forall x\in[a,b],a\leq \varphi(x)\leq b$
    • $\exists L\in (0,1),\forall x,y\in C[a,b],|\varphi(x)-\varphi(y)|\leq L|x-y|$ （或 $|\varphi’(x)|\leq L<1$）
  • 收敛充分条件：满足以上条件的函数，$\forall x_0\in[a,b]$，由 $x_{k+1}=\varphi(x_k)$ 得到的迭代序列 ${x_k}$ 收敛到不动点，且 $|x_k-x^*|\leq\frac{L^k}{1-L}|x_1-x_0|$
  • 迭代误差 $\epsilon_k=x_k-x^*$
  • $p$ 阶收敛：$\frac{\epsilon_{k+1}}{\epsilon_k^p}\rightarrow C\neq 0$
• 若 $x_{k+1}=\varphi(x_k),\varphi^{(p)}(x)$ 在 $x^$ 附件连续，且 $\varphi’(x^)=\varphi’’(x^)=\cdots=\varphi^{(p-1)}(x^)=0,\varphi^{(p)}(x^)\neq 0$，则迭代过程在 $x^$ 附件 $p$ 阶收敛
• 局部收敛
• 全局收敛

牛顿法

• 基本思想：将非线性方程逐步线性化形成迭代公式
• 取 $x_0\approx x^*$，$f(x)$ 在 $x_0$ 处做一阶 Taylor 展开：$f(x)=f(x_0)+f’(x_0)(x-x_0)+\frac{f’’(\xi)}{2}(x-x_0)^2$
  • $x^*\approx x_0-\frac{f(x_0)}{f’(x_0)}$
• 牛顿法：$x_{k+1}=x_k-\frac{f(x_k)}{f’(x_k)}$
• 牛顿法收敛的充分条件：若 $f\in C^2[a,b]$
  • $f(a)f(b)<0$
  • $[a,b]$ 上 $f’’$ 不变号且 $f’(x)\neq 0$
  • $\forall x_0\in[a,b],f(x_0)f’’(x_0)>0$
• 局部收敛性：$f\in C^2[a,b],x^$ 为 $f(x)$ 在 $[a,b]$ 上的根且 $f’(x)\neq 0$，则存在 $x^$ 的邻域，使任意邻域上的初值产生的序列收敛到 $x^$，且 $\lim_{k\rightarrow\infty}\frac{x^-x_{k+1}}{(x^-x_k)^2}=-\frac{f’’(x^)}{2f’(x^*)}$
• 割线法：$x_{k+1}=x_k-\frac{f(x_k)(x_k-x_{k_1})}{f(x_k)-f(x_{k-1})}$
• 下山法：若 $x_{k+1}$ 处的值不比原有的小，则在 $(x_k,x_{k+1})$ 间找一个更好的点使值变小：$\overline{x_{k+1}}=x_k-\lambda\frac{f(x_k)}{f’(x_k)}$
• 特殊情况
  • 重根：线性收敛
  • $f’(x^*)\neq 0$ 至少平方收敛

迭代过程加速方法

• 埃特金加速收敛方法（Aitken）：$x_{k+1}=x_k-\frac{(\tilde{x}{k+1}-x_k)^2}{\overline{x}{k+1}-2\tilde{x}_{k+1}+x_k}$
  • 超线性收敛：$\lim_{k\rightarrow\infty}\frac{|e_{k+1}|}{|e_k|}=0$