4.1-3 非线性方程简介及二分法：略
4.4 - 10 简单迭代法的构造与收敛性
构造简单迭代法
\[ \begin{array}{c}\begin{aligned} f(x)=0\quad&\Leftrightarrow\quad x=\varphi(x)\\ f(x)的根\quad&\Leftrightarrow\quad\varphi(x)的不动点 \end{aligned}\end{array} \]
其中 \(x_{k+1}=\varphi(x_k),\quad (k=0,1,2,\dots)\) 称为迭代格式， \(\varphi(x)\) 称为迭代函数。
简单迭代法的收敛条件
几何解释：求方程 \(x=\varphi(x)\) 的根，就是求直线 \(y=x\) 和曲线 \(y=\varphi(x)\) 的交点的横坐标。（图略。）
如果 \(x_{k+1}=\varphi(x_k)\)
收敛，则迭代函数 \(y=\varphi(x)\)
的曲线走势平坦，即 \(\left|\varphi'(x)\right|<1\)
；
如果 \(x_{k+1}=\varphi(x_k)\)
发散，则迭代函数 \(y=\varphi(x)\)
的曲线走势陡峭，即 \(\left|\varphi'(x)\right|\ge1\) ；
迭代法收敛的判定定理：设函数 \(\varphi(x)\) 满足条件： \[ \begin{array}{l}(1)\quad \forall x\in[a,b],\ a\le\varphi(x)\le b;\\ (2)\quad \exists0\le L<1,\ \begin{array}{l}\forall x,y\in[a,b],\ |\varphi(x)-\varphi(y)|\le L|x-y|\\或\ |\varphi'(x)\le L<1|\end{array}\end{array} \]
则 \(\forall x_0\in[a,b]\) ，由 \(x_{k+1}=\varphi(x_K)\) 得到的序列 \(\{x_k\}_{k=0}^\infty\) 收敛于 \(\varphi(x)\) 在 \([a,b]\) 上的唯一不动点。并且由误差估计式： \(\begin{array}{l}\displaystyle\left|x^*-x_k\right|\le\frac{1}{1-L}\left|x_k-x_{k-1}\right|\\\displaystyle\left|x^*-x_k\right|\le\frac{L^k}{1-L}\left|x_1-x_0\right|\end{array}\) 。由第一式分析误差；由第二式得到结论 \(L\) 越小，收敛越快 。
局部收敛性
定义：若存在 \(x^*\) 的某个邻域 \(S=\{|x-x^*|\le\delta\}\subset[a,b]\) ，使迭代过程 \(x_{k+1}=\varphi(x_k)\) 对于任一初值 \(x_0\in S\) 均收敛则称迭代过程 \(x_{k+1}=\varphi(x_k)\) 在根 \(x^*\) 邻近具有局部收敛性。
判定定理： \(\varphi(x)\) 在方程 \(x=\varphi(x)\) 的精确根 \(x^*\) 的邻域连续，且 \(|\varphi'(x^*)|<1\) ，则迭代过程 \(x_{k+1}=\varphi(x_k)\) 在根 \(x^*\) 的邻域具有局部收敛性。
不严格的准则：只要在一个不大的有根区间上， \(|\varphi'(x)|<1\) 明显成立，则从该区间内一点 \(x_0\) 出发， \(x_{k+1}=\varphi(x_k)\) 产生的迭代序列 \(\{x_k\}\) 一般是收敛的。
收敛阶（描述收敛速度）
观察得到， \(|\varphi'(x)|\) 越小，收敛速度越快，越大越慢。
定义：记迭代误差 \(e_k=x^*-x_k\) ，对收敛于方程 \(x=\varphi(x)\) 的根 \(x^*\) 的迭代过程 \(x_{k+1}=\varphi(x_k)\) ，若存在常数 \(p\ge1\) 和非零常数 \(C\) ，使得 \(\displaystyle\lim_{k\to\infty}\frac{|e_{k+1}|}{|e_k|^p}=C\)
，则称迭代过程是 \(\mathbf{p}\)
阶收敛的， \(C\)
是渐进误差常数。
其中， \(p=1\)
时称线性收敛， \(p>1\) 时称超线性收敛，
\(p=2\) 时称平方收敛。
\(p\) 越大，收敛速度越快。
定理：若 \(\varphi'(x)\) 在 \(\varphi(x)\) 的不动点 \(x^*\) 邻域连续，且 \(\varphi'(x)\neq0\) ，则迭代过程 \(x_{k+1}=\varphi(x_k)\) 在 \(x^*\) 的邻域是线性收敛的。
\(\mathbf{p}\) 阶收敛的迭代法
定理：若 \(x^*\) 是 \(\varphi(x)\) 的不动点，对于整数 \(p>1\) ，迭代函数 \(\varphi(x)\) 及其 \(p\) 阶导数在 \(x^*\) 的邻域上连续，且满足： \(\varphi'(x^*)=\varphi''(x^*)=\dots=\varphi^{(p-1)}(x^*)=0,\quad \varphi^{(p)}(x^*)\neq0\) ，则迭代过程 \(x_{k+1}=\varphi(x_k)\) 在 \(x^*\) 的邻域是 \(p\) 阶收敛的。且有： \(\displaystyle\lim_{k\to\infty}\frac{e_{k+1}}{e_k^p}=\frac{\varphi^{(p)}(x^*)}{p!}\) 。
因此， \(\varphi'(x^*)\neq0\) 时，迭代过程只可能是线性的，因此绝大部分迭代方法只能是线性收敛的。
Aitken加速算法
由于 \(\begin{array}{l}x_{k+1}-x^*=\varphi'(\xi_1)(x_k-x^*)\\x_{k+2}-x^*=\varphi'(\xi_2)(x_{k+1}-x^*)\end{array}\) ，当 \(k\) 较大时，假设 \(\varphi'(\xi_1)\approx\varphi'(\xi_2)\) ，则有： \(\displaystyle\frac{x_{k+1}-x^*}{x_{k+2}-x^*}\approx\frac{x_k-x^*}{x_{k+1}-x^*}\) 。然后解得 \(x^*\approx \hat x_k=x_k-\displaystyle\frac{(x_{k+1}-x_k)^2}{x_{k+2}-2x_{k+1}+x_k}\) 。
则序列 \(\{\hat x_k\}\) 比序列 \(\{x_k\}\) 更快地收敛于 \(x^*\) ，可构造如下Aitken加速算法： \[ \left\{\begin{array}{l} y_k=\varphi(x_k)\\ z_k=\varphi(y_k)\\ x_{k+1}=x_k-\displaystyle\frac{(y_k-x_k)^2}{z_k-2y_k+x_k}, \quad k=0,1,2,\dots \end{array}\right. \] 若第 \(k\) 步发生 \(z_k-2y_k+x_k=0\) ，则中止计算，取 \(x^*\approx x_k\) 。
代码：二分法
//
// Created by xa on 2021-03-03.
//
#include <iostream>
double f(double x);
double solve(double a, double b);
void iterate(double &a, double &b);
int main() {
double x = solve(1,2);
std::cout << "The solve in [1, 2] is : x = " << x << std::endl;
}
double f(double x) {
return x * x * x + 4 * x - 7;
}
double solve(double a, double b) {
if (f(a) * f(b) > 0) { std::cout << "WRONG INTERVAL" << std::endl; return 0; }
double epsilon = 1e-5;
while (std::abs(a-b) >= epsilon) {
iterate(a, b);
std::cout << (a + b) / 2 << std::endl;
}
return (a + b) / 2;
}
void iterate(double &a, double &b) {
double f_a = f(a);
double f_b = f(b);
double f_c = f((a + b) / 2);
if (f_c == 0) return;
else if (f_a * f_c < 0) b = (a + b) / 2;
else if (f_b * f_c < 0) a = (a + b) / 2;
}代码：简单迭代法与Aitken加速算法比较
//
// Created by xa on 2021-03-03.
//
#include <iostream>
#include <cmath>
double phi(double x);
double x_simple;
double next_x_simple;
int count_simple;
void simple();
double x_aitken;
double next_x_aitken;
int count_aitken;
void aitken();
int main() {
simple();
aitken();
}
double phi(double x) {
return 1.6 + 0.99 * cos(x);
}
void simple() {
x_simple = 1.57;
while (x_simple = next_x_simple, ++count_simple,
std::cout << x_simple << "; ") {
next_x_simple = phi(x_simple);
if (std::abs(next_x_simple - x_simple) < 1e-5) break;
}
std::cout << std::endl << "The count is " << count_simple << std::endl;
}
void aitken() {
x_aitken = 1.57;
while (x_aitken = next_x_aitken, ++count_aitken,
std::cout << x_aitken << "; ") {
double y = phi(x_aitken);
double z = phi(y);
next_x_aitken = x_aitken
- (pow(y - x_aitken, 2)
/ (z - 2 * y + x_aitken) );
if (std::abs(next_x_aitken - x_aitken) < 1e-5) break;
}
std::cout << std::endl << "The count is " << count_aitken << std::endl;
}