Chapter7 非线性方程求根
7.1 前言
- 本质：对一些n次代数多项式or超越方程，它们的根是难以通过解析方法求得，因此需采取数值方法
- 主要有：
- 二分法
- 不动点迭代法：迭代加速
- 牛顿迭代法：牛顿法、割线法
7.2 二分法
- 数学基础：零点定理
- 基本步骤：
- 确定初始区间[a,b]=>satisfy f(a)f(b)<0,
- 记
x
0
=
a
+
b
2
x_{0}=\frac{a+b}{2}
x0=2a+b => calculate
f
(
x
0
)
f(x_{0})
f(x0)
- judge:
-
f
(
x
0
)
=
=
0
f(x_{0})==0
f(x0)==0 ==> out of loop
-
f
(
a
)
f
(
x
0
)
<
0
f(a)f(x_{0})<0
f(a)f(x0)<0 ==> new
x
0
∈
[
a
,
x
0
]
x_{0}\in [a,x_{0}]
x0∈[a,x0]
-
f
(
x
0
)
f
(
b
)
<
0
f(x_{0})f(b)<0
f(x0)f(b)<0 ==> new
x
0
∈
[
x
0
,
b
]
x_{0}\in [x_{0},b]
x0∈[x0,b]
- disadvantage:
- 只用了函数值的正负号，而非函数值的大小 => 收敛速度不快
- 二分法无法求复根
7.3 不动点迭代
7.3.1 基本概念
- 概念：类似于
x
(
k
+
1
)
=
B
⋅
x
(
k
)
+
g
x^{(k+1)}=B\cdot x^{(k)}+g
x(k+1)=B⋅x(k)+g，将非线性方程转换为
x
=
ϕ
(
x
)
x=\phi(x)
x=ϕ(x)，从而产生迭代算法
x
k
+
1
=
ϕ
(
x
k
)
x_{k+1}=\phi(x_{k})
xk+1=ϕ(xk)
- 基本步骤：
- 取初值
x
0
x_{0}
x0
- 迭代
x
k
+
1
=
ϕ
(
x
k
)
x_{k+1}=\phi(x_{k})
xk+1=ϕ(xk)
- when
∣
x
k
+
1
−
x
k
∣
<
ε
|x_{k+1}-x_{k}|<\varepsilon
∣xk+1−xk∣<ε，终止迭代
- 核心：
- 构造
x
=
ϕ
(
x
)
x=\phi(x)
x=ϕ(x)
- 判断是否收敛
7.3.2 收敛性
- 定理：
设迭代函数
φ
(
x
)
\varphi(\boldsymbol{x})
φ(x) 在
[
a
,
b
]
[\boldsymbol{a}, \boldsymbol{b}]
[a,b] 上连续, 且满足:
(a) 当
x
∈
[
a
,
b
]
x \in[a, b]
x∈[a,b] 时,
a
≤
φ
(
x
)
≤
b
a \leq \varphi(x) \leq b
a≤φ(x)≤b;
(b) 存在一正数
L
\boldsymbol{L}
L, 满足
0
<
L
<
1
0<\boldsymbol{L}<\mathbf{1}
0<L<1, 且
∀
x
∈
[
a
,
b
]
\forall \boldsymbol{x} \in[\boldsymbol{a}, \boldsymbol{b}]
∀x∈[a,b], 有
∣
φ
′
(
x
)
∣
≤
L
\left|\varphi^{\prime}(x)\right| \leq L
∣φ′(x)∣≤L
则:
(1) 方程
x
=
φ
(
x
)
\boldsymbol{x}=\varphi(\boldsymbol{x})
x=φ(x)在 [
a
,
b
\boldsymbol{a}, \boldsymbol{b}
a,b] 内有唯一解
x
∗
\boldsymbol{x}^*
x∗，且对于任意初值
x
0
∈
[
a
,
b
]
x_0 \in[a, b]
x0∈[a,b]，迭代法
x
k
+
1
=
φ
(
x
k
)
x_{k+1}=\varphi\left(x_k\right)
xk+1=φ(xk) 均收敛于
x
∗
x^*
x∗
(2) 序列
x
k
{x_{k}}
xk的收敛速度有估计
∣
x
k
−
x
∗
∣
≤
L
1
−
L
∣
x
k
−
x
k
−
1
∣
\left|\boldsymbol{x}_k-\boldsymbol{x} *\right| \leq \frac{L}{1-L}\left|\boldsymbol{x}_k-\boldsymbol{x}_{k-1}\right|
∣xk−x∗∣≤1−LL∣xk−xk−1∣
∣
x
k
−
x
∗
∣
≤
L
k
1
−
L
∣
x
1
−
x
0
∣
\left|\boldsymbol{x}_k-\boldsymbol{x} *\right| \leq \frac{L^k}{1-L}\left|x_1-x_0\right|
∣xk−x∗∣≤1−LLk∣x1−x0∣
- 证明：
(1.1) 存在性：构造
g
(
x
)
=
x
−
ϕ
(
x
)
g(x)=x-\phi(x)
g(x)=x−ϕ(x)，通过零点定理和条件(a)证明
g
(
a
)
g
(
b
)
<
0
g(a)g(b)<0
g(a)g(b)<0
(1.2) 唯一性：反证法，假设有一个新真值
y
∗
y^*
y∗，由拉格朗日微分中值定理->
∣
x
∗
−
y
∗
∣
=
∣
ϕ
(
x
∗
)
−
ϕ
(
y
∗
)
∣
=
ϕ
(
ξ
)
′
∣
x
∗
−
y
∗
∣
|x^*-y^*|=|\phi(x^*)-\phi(y^*)|=\phi(\xi)'|x^*-y^*|
∣x∗−y∗∣=∣ϕ(x∗)−ϕ(y∗)∣=ϕ(ξ)′∣x∗−y∗∣，显然，
∣
x
∗
−
y
∗
∣
=
ϕ
(
ξ
)
′
∣
x
∗
−
y
∗
∣
|x^*-y^*|=\phi(\xi)'|x^*-y^*|
∣x∗−y∗∣=ϕ(ξ)′∣x∗−y∗∣只有当
ϕ
(
ξ
)
′
=
=
1
\phi(\xi)'==1
ϕ(ξ)′==1时取等号，与条件(b)不符
(1.3) 收敛性：
∣
x
k
−
x
∗
∣
=
∣
ϕ
(
x
k
−
1
)
−
ϕ
(
x
∗
)
∣
=
ϕ
(
ξ
)
′
∣
x
k
−
1
−
x
∗
∣
≤
L
∣
x
k
−
x
∗
∣
|x_{k}-x^*|=|\phi(x_{k-1})-\phi(x^*)|=\phi(\xi)'|x_{k-1}-x^*|\leq L|x_{k}-x^*|
∣xk−x∗∣=∣ϕ(xk−1)−ϕ(x∗)∣=ϕ(ξ)′∣xk−1−x∗∣≤L∣xk−x∗∣递推，
∣
x
k
−
x
∗
∣
≤
L
k
∣
x
0
−
x
∗
∣
→
0
|x_{k}-x^*|\leq L^k|x_{0}-x^*|\rightarrow0
∣xk−x∗∣≤Lk∣x0−x∗∣→0，(L属于0,1；而x0和x*都是定值，所以趋近于0)
(2.1) 第一个等式：通过
∣
x
k
−
x
∗
∣
=
∣
x
k
−
x
k
+
1
+
x
k
+
1
−
x
∗
∣
=
∣
x
k
−
x
k
+
1
+
ϕ
(
x
k
)
−
ϕ
(
x
∗
)
∣
=
∣
x
k
−
x
k
+
1
+
ϕ
(
ξ
)
′
(
x
k
−
x
∗
)
∣
≤
∣
x
k
−
x
k
+
1
∣
+
L
∣
x
k
−
x
∗
∣
|x_{k}-x^*|=|x_{k}-x_{k+1}+x_{k+1}-x^*|=|x_{k}-x_{k+1}+\phi(x_{k})-\phi(x^*)|=|x_{k}-x_{k+1}+\phi(\xi)'(x_{k}-x^*)|\leq|x_{k}-x_{k+1}|+L|x_{k}-x^*|
∣xk−x∗∣=∣xk−xk+1+xk+1−x∗∣=∣xk−xk+1+ϕ(xk)−ϕ(x∗)∣=∣xk−xk+1+ϕ(ξ)′(xk−x∗)∣≤∣xk−xk+1∣+L∣xk−x∗∣，从而有
∣
x
k
−
x
∗
∣
≤
∣
x
k
−
x
k
+
1
∣
+
L
∣
x
k
−
x
∗
∣
|x_{k}-x^*|\leq|x_{k}-x_{k+1}|+L|x_{k}-x^*|
∣xk−x∗∣≤∣xk−xk+1∣+L∣xk−x∗∣，推出
∣
x
k
−
x
∗
∣
≤
L
1
−
L
∣
x
k
−
x
k
−
1
∣
\left|\boldsymbol{x}_k-\boldsymbol{x} *\right| \leq \frac{L}{1-L}\left|\boldsymbol{x}_k-\boldsymbol{x}_{k-1}\right|
∣xk−x∗∣≤1−LL∣xk−xk−1∣
(2.2) 第二个等式：由第一个等式递推即可
- 特点：L越小收敛越快，但是能满足这种条件的不动点函数实在是太困难了，但是如果将这个不动点收缩到一个邻域范围内，这样初值
x
0
x_{0}
x0只需要取到领域范围内的值即可收敛
- 局部收敛：这种在解的某个小领域内收敛的性质
- 全局收敛：没有这种要求，或者可以清楚地给出这个邻域区间范围的表达即为全局收敛
- 做法：先用二分法缩小根范围，再用局部收敛法定解
7.3.3 一道例题
- 提问：将
x
=
t
a
n
x
x=tanx
x=tanx化为合适的迭代格式，并求解x=4.5附近的根
- 回答：
由不动点迭代收敛定理：
① 确定根的范围：
f
(
x
)
=
x
−
t
a
n
(
x
)
→
f
′
(
x
)
=
−
t
a
n
2
(
x
)
<
0
f(x)=x-tan(x) \rightarrow f'(x)=-tan^2(x)<0
f(x)=x−tan(x)→f′(x)=−tan2(x)<0，由零点定理，根范围在[4.4,4.5]
② 判断tanx的导数是否小于1，显然
∣
f
′
(
x
)
=
−
t
a
n
2
(
x
)
∣
>
>
1
|f'(x)=-tan^2(x)|>>1
∣f′(x)=−tan2(x)∣>>1，因此，将原函数转换为
a
r
c
t
a
n
(
x
)
+
π
=
x
arctan(x)+\pi=x
arctan(x)+π=x
通过以下matlab代码求解：
clc,clear all
x1=4.5;
x2=g(x1);
while abs(x2-x1)>eps
x1=x2;
x2=g(x1);
end
x2
function y=g(x)
y=atan(x)+pi;
end
7.4 迭代加速
- 收敛阶：
记序列
x
k
k
=
0
∞
{x_{k}}^\infty _{k=0}
xkk=0∞收敛于
x
∗
x^*
x∗，记迭代误差
e
k
=
x
∗
−
x
k
e_k=x^*-x_k
ek=x∗−xk，若：
lim
k
→
∞
∣
e
k
+
1
∣
∣
e
k
∣
p
=
C
\lim _{k \rightarrow \infty} \frac{\left|e_{k+1}\right|}{\left|e_k\right|^p}=C
k→∞lim∣ek∣p∣ek+1∣=C
称为p阶收敛
p=1: 线性收敛；p=2：平方收敛
阶数越高，收敛越快
e
k
+
1
=
c
i
e
k
,
e
k
=
0.1
→
p
1
=
c
1
0.1
>
>
p
2
=
c
2
0.01
e_{k+1}=c_i e_{k}, e_{k}=0.1\rightarrow p1=c_1 0.1>>p2=c_{2} 0.01
ek+1=ciek,ek=0.1→p1=c10.1>>p2=c20.01
- 收敛速度定理
设
x
∗
x *
x∗ 是方程
x
=
φ
(
x
)
x=\varphi(x)
x=φ(x) 的根，
φ
(
x
)
\varphi(x)
φ(x) 在
x
∗
x^*
x∗ 邻近有连续的二阶导数，且
φ
′
(
x
∗
)
≤
1
\varphi^{\prime}\left(x^*\right) \leq 1
φ′(x∗)≤1
(1) 当
φ
′
(
x
∗
)
≠
0
\varphi^{\prime}\left(x^*\right) \neq 0
φ′(x∗)=0 时, 迭代格式
x
k
+
1
=
φ
(
x
k
)
x_{k+1}=\varphi\left(x_k\right)
xk+1=φ(xk) 线性收敛到
x
∗
x^*
x∗;
(2) 当
φ
′
(
x
∗
)
=
0
,
φ
′
′
(
x
∗
)
≠
0
\varphi^{\prime}\left(x^*\right)=0, \varphi^{\prime \prime}\left(x^*\right)\neq 0
φ′(x∗)=0,φ′′(x∗)=0 时, 迭代格式
x
k
+
1
=
φ
(
x
k
)
x_{k+1}=\varphi\left(x_k\right)
xk+1=φ(xk) 平方收敛到
x
∗
x^*
x∗;
- 证明：
(1) 微分中值定理
∣
e
k
+
1
∣
∣
e
k
∣
=
∣
x
k
+
1
−
x
∗
∣
∣
x
k
−
x
∗
∣
=
l
i
m
k
→
0
∣
ϕ
(
ξ
)
′
∣
∣
x
k
−
x
∗
∣
∣
x
k
−
x
∗
∣
=
ϕ
(
ξ
)
′
≠
0
\frac{\left|e_{k+1}\right|}{\left|e_k\right|}=\frac{\left|x_{k+1}-x^*\right|}{\left|x_k-x^*\right|}=lim_{k\rightarrow0}\frac{|\phi(\xi)'||x_{k}-x^*|}{|x_{k}-x^*|}=\phi(\xi)'\neq 0
∣ek∣∣ek+1∣=∣xk−x∗∣∣xk+1−x∗∣=limk→0∣xk−x∗∣∣ϕ(ξ)′∣∣xk−x∗∣=ϕ(ξ)′=0
(2) 泰勒二阶展开
∣
e
k
+
1
∣
∣
e
k
∣
2
=
∣
x
k
+
1
−
x
∗
∣
∣
x
k
−
x
∗
∣
2
=
∣
(
φ
(
x
∗
)
+
φ
′
(
x
∗
)
(
x
k
−
x
∗
)
+
φ
′
(
ε
)
2
!
(
x
k
−
x
∗
)
2
∣
∣
x
k
−
x
∗
∣
2
\frac{\left|e_{k+1}\right|}{\left|e_k\right|^2}=\frac{\left|x_{k+1}-x^*\right|}{\left|x_k-x^*\right|^2}=\frac{|\left (\varphi\left(x^*\right)+\varphi^{\prime}\left(x^{*}\right)\left(x_k-x^*\right)+\frac{\varphi^{\prime}(\varepsilon)}{2 !}\left(x_k-x^*\right)^2 |\right.}{\left|x_k-x^*\right|^2}
∣ek∣2∣ek+1∣=∣xk−x∗∣2∣xk+1−x∗∣=∣xk−x∗∣2∣(φ(x∗)+φ′(x∗)(xk−x∗)+2!φ′(ε)(xk−x∗)2∣
7.5 牛顿迭代
7.5.1 基本概念
- 推导：由泰勒二阶展开公式:
f
(
x
)
=
f
(
x
k
)
+
f
′
(
x
k
)
(
x
−
x
k
)
+
f
′
(
x
k
)
2
!
(
x
−
x
k
)
2
+
⋯
f(x)=f\left(x_k\right)+f^{\prime}\left(x_k\right)\left(x-x_k\right)+\frac{f^{\prime}\left(x_k\right)}{2 !}\left(x-x_k\right)^2+\cdots
f(x)=f(xk)+f′(xk)(x−xk)+2!f′(xk)(x−xk)2+⋯
↓
f
(
x
)
=
0
↓
f
(
x
k
)
+
f
′
(
x
k
)
(
x
−
x
k
)
=
0
↓
↓
x
k
+
1
=
x
k
−
f
(
x
k
)
f
′
(
x
k
)
\downarrow\\ f(x)=0\\ \downarrow\\ f\left(x_k\right)+f^{\prime}\left(x_k\right)\left(x-x_k\right)=0\\ \downarrow\\ \downarrow\\ x_{k+1}=x_k - \frac{f\left(x_k\right)}{f^{\prime}\left(x_k\right)}
↓f(x)=0↓f(xk)+f′(xk)(x−xk)=0↓↓xk+1=xk−f′(xk)f(xk)
- 例题：求解
f
(
x
)
=
3
∗
x
3
−
8
∗
x
2
−
8
∗
x
−
11
f(x)=3*x^3-8*x^2-8*x-11
f(x)=3∗x3−8∗x2−8∗x−11的某个近似根
由高中知识，判断该方程仅有一个解，解的范围在[3,4]
代码如下：
clc,clear all
x1=3.5;
x2=g(x1);
while abs(x2-x1)>eps
x1=x2;
x2=g(x1);
end
x2
function y=g(x)
y=x-(3*(x^3)-8*(x^2)-8*x-11)./(9*(x^2)-16*x-8);
end
- 特点
7.5.3 牛顿下山法
- 特点：在
f
(
x
k
)
f
′
(
x
k
)
\frac{f\left(x_k\right)}{f^{\prime}\left(x_k\right)}
f′(xk)f(xk)之前增加一个校正因子
λ
\lambda
λ，使每次牛顿迭代的f(x)单调递减
- 基本步骤：
- 算法：
(1) 给定初值
x
0
x_{0}
x0
(2) 若
∣
f
(
x
k
)
∣
≤
ε
|f(x_k)| \leq \varepsilon
∣f(xk)∣≤ε，则停止迭代
(3) 计算
d
k
=
f
(
x
k
)
f
′
(
x
k
)
d_k=\frac{f\left(x_k\right)}{f^{\prime}\left(x_k\right)}
dk=f′(xk)f(xk)，并取
λ
=
1
\lambda =1
λ=1
(4) 若
∣
f
(
x
k
+
λ
d
k
∣
<
∣
f
(
x
k
)
∣
|f(x_k+\lambda d_k|<|f(x_k)|
∣f(xk+λdk∣<∣f(xk)∣，则
x
k
+
1
=
x
k
+
λ
d
k
x_{k+1}=x_k+\lambda d_k
xk+1=xk+λdk，转(5)；否则，
λ
=
1
2
λ
\lambda=\frac{1}{2} \lambda
λ=21λ，当
λ
<
ε
\lambda<\varepsilon
λ<ε，停止迭代，下山失败。
(5) k=k+1，转(2)
function [x,it]=newtonfg(x0,f,g,maxit,tol)
x1=x0;
d=-feval(f,x0)./feval(g,x0);
x2=x1+d;
it=0;
while abs(x1-x2)>=tol
it=it+1;
if it>=maxit
break;
end
x1=x2;d=-feval(f,x1)./feval(g,x1);fx=feval(f,x1);
isdone=0;lambda=1;
while isdone==0
xn=x1+lambda*d;
fn=feval(f,xn);
if abs(fn)<=abs(fx)
isdone=1;
else
lambda=0.5*lambda;
if lambda<=tol
disp("misson fail");
break;
end
end
x2=xn;
end
end
x=x2;
7.5.4 割线法
- 本质：用两点割线计算
f
′
(
x
k
)
=
f
(
x
k
)
−
f
(
x
k
−
1
)
x
k
−
x
k
−
1
f'(x_k)=\frac{f(x_k)-f(x_{k-1})}{x_k-x_{k-1}}
f′(xk)=xk−xk−1f(xk)−f(xk−1)
- 特点：
- 不算导数，但是初始值要两个
- 收敛阶级：1.618（不证明）<牛顿下山法
