1 非线性方程求解
非线性方程的形式
𝑓 (𝑥) = 0
根通常不止一个, 需要给定求解区间
2 二分法
有介值定理
对于任意 [𝑎, 𝑏] 上的连续函数 𝑓 (𝑥), 若 𝑓 (𝑎) 𝑓 (𝑏) < 0, 则
∃𝜉 ∈ (𝑎, 𝑏), 𝑠.𝑡. 𝑓 (𝜉) = 0
可以不断将区间二分从而缩小根的范围. 可以这么描述算法流程
1. 选择区间 [𝑎, 𝑏] 误差限 𝜖 和函数 𝑓 (𝑥)
2. 若
|
𝑎 − 𝑏
|
< 𝜖, 则停止, 输出
1
2
(𝑎 + 𝑏)
3. 计算中点 𝑐 =
𝑎+𝑏
2
以及 𝑓 (𝑐)
4. 若
|
𝑓 (𝑐)
|
< 𝜖, 则停止, 输出 𝑐
5. 若 𝑓 (𝑎) 𝑓 (𝑐) < 0, 则令 𝑏 = 𝑐, 否则令 𝑎 = 𝑐, 返回第 2 步
二分法有如下的缺点
1. 初始区间选择困难
2. 只能求出一个根
3. 只能求出实根
4. 可能存在根但是找不到
二分法的误差满足
|
𝑥 − 𝑥
∗
|
=
1
2
𝑛
(𝑏 − 𝑎)
其中 𝑥
∗
是根,𝑥 是二分法求得的值,𝑛 是迭代次数
3 不动点迭代法
对于非线性方程 𝑓 (𝑥) = 0, 可以变形为 𝑥 = 𝜑(𝑥) 的形式, 则能写出迭代形式
𝑥
𝑘+1
= 𝜑(𝑥
𝑘
), 𝑘 = 0, 1, 2, · · ·
其中 𝑥
0
是初始值. 若 𝜑(𝑥) 是 [𝑎, 𝑏] 上的连续函数, 且 𝜑(𝑥) ∈ [𝑎, 𝑏], 则不动点存在
∃𝜉 ∈ [𝑎, 𝑏], 𝑠.𝑡.𝜑(𝜉) = 𝜉
证明是简单的. 设
𝜓(𝑥) = 𝜑(𝑥) − 𝑥
则有
𝜓(𝑎)𝜓 (𝑏) ≤ 0
若 𝜑(𝑥) 的一阶导数也是连续的, 并且其导数的绝对值小于 1, 那么其在 [𝑎, 𝑏] 上的不动点是唯一的. 可以
利用反证法证明, 设存在两个不同的不动点 𝑥
∗
1
, 𝑥
∗
2
, 设
|
𝜑
′
(𝑥)
|
≤ 𝐿 < 1
则
𝑥
∗
1
− 𝑥
∗
2
=
𝜑(𝑥
∗
1
) − 𝜑(𝑥
∗
2
)
=
|
𝜑
′
(𝜉)
|
𝑥
∗
1
− 𝑥
∗
2
≤ 𝐿
𝑥
∗
1
− 𝑥
∗
2
<
𝑥
∗
1
− 𝑥
∗
2
得到矛盾, 所以不动点是唯一的
有收敛速度
|
𝑥
∗
− 𝑥
𝑘
|
≤
𝐿
𝑘
1 − 𝐿
|
𝑥
1
− 𝑥
0
|
证明只需要
|
𝑥
𝑘+1
− 𝑥
∗
|
=
|
𝜑(𝑥
𝑘
) − 𝜑(𝑥
∗
)
|
≤ 𝐿
|
𝑥
𝑘
− 𝑥
∗
|
· · · ≤ 𝐿
𝑘+1
|
𝑥
0
− 𝑥
∗
|
那么
𝑥
𝑘+𝑝
− 𝑥
𝑘
≤
𝑥
𝑘+𝑝
− 𝑥
𝑘+𝑝−1
+· · · +
|
𝑥
𝑘+1
− 𝑥
𝑘
|
≤
𝐿
𝑘+𝑝−1
+ 𝐿
𝑘+𝑝−2
+ · · · + 𝐿
𝑘
|
𝑥
1
− 𝑥
0
|
=
𝐿
𝑘
1 − 𝐿
(1 − 𝐿
𝑝
)
|
𝑥
1
− 𝑥
0
|
令 𝑝 → ∞, 则 𝑥
𝑘+𝑝
→ 𝑥
∗
, 那么
|
𝑥
∗
− 𝑥
𝑘
|
≤
𝐿
𝑘
1 − 𝐿
|
𝑥
1
− 𝑥
0
|
若 𝐿 较小, 则收敛速度较快
不动点迭代对函数的要求较高, 实际的函数不易满足. 当 𝐿 >
1
2
时, 不动点迭代的收敛速度慢于二分法
4 收敛阶
记误差为
𝑒
𝑘
=
|
𝑥
𝑘
− 𝑥
∗
|
若存在 𝑝 > 0, 𝑐 > 0 使得
lim
𝑘→∞
𝑒
𝑘+1
𝑒
𝑝
𝑘
= 𝑐
称迭代序列是 𝑝 阶收敛的,𝑐 称为渐进误差常数
对于二分法而言有
𝑒
𝑘
≤
1
2
𝑘
(𝑏 − 𝑎)
那么
lim
𝑘→∞
𝑒
𝑘+1
𝑒
𝑘
=
1
2
有 𝑝 = 1, 𝑐 =
1
2
, 所以二分法是一阶收敛的. 对于不动点迭代而言, 有
𝑒
𝑘
≤
𝐿
𝑘
1 − 𝐿
|
𝑥
1
− 𝑥
0
|
那么
lim
𝑘→∞
𝑒
𝑘+1
𝑒
𝑘
= 𝐿
有 𝑝 = 1, 𝑐 = 𝐿, 所以不动点迭代是一阶收敛的
5 牛顿法
可以利用展开将非线性方程转化为线性方程
𝑓 (𝑥) = 𝑓 (𝑥
0
) + 𝑓
′
(𝑥
0
)(𝑥 − 𝑥
0
) + · · ·
𝑓 (𝑥) = 0 的解可以近似为
𝑓 (𝑥
0
) + 𝑓
′
(𝑥
0
)(𝑥 − 𝑥
0
) = 0
即
𝑥 = 𝑥
0
−
𝑓 (𝑥
0
)
𝑓
′
(𝑥
0
)
如此迭代就是牛顿迭代法. 若迭代序列收敛
lim
𝑘→∞
𝑥
𝑘
= 𝛼
那么对迭代两端取极限得
𝛼 = 𝛼 −
𝑓 (𝛼)
𝑓
′
(𝛼)
那么
𝑓 (𝛼) = 0
为了考察牛顿迭代的收敛性, 假定 𝛼 是 𝑓 (𝑥) = 0 的单根, 那么
𝑓 (𝛼) = 0, 𝑓
′
(𝛼) ≠ 0
按照不动点迭代, 有
𝜑(𝑥) = 𝑥 −
𝑓 (𝑥)
𝑓
′
(𝑥)
检验其导数
𝜑
′
(𝑥) =
𝑓 (𝑥) 𝑓
′′
(𝑥)
𝑓
′
(𝑥)
2
因而
𝜑
′
(𝛼) = 0
若初值 𝑥
0
足够接近 𝛼, 那么 𝜑
′
(𝑥) 在 𝑥
0
附近的绝对值小于 1, 得牛顿法收敛. 若 𝛼 是 𝑓 (𝑥) = 0 的 𝑝 重根,
记
𝑓 (𝑥) = (𝑥 − 𝛼)
𝑝
ℎ(𝑥), ℎ(𝛼) ≠ 0
那么
𝜑(𝑥) = 𝑥 −
(𝑥 − 𝛼)ℎ(𝑥)
𝑝ℎ(𝑥) + (𝑥 − 𝛼)ℎ
′
(𝑥)
求其导
𝜑
′
(𝑥) = 1 −
[
(𝑥 − 𝛼)ℎ
′
(𝑥) + ℎ(𝑥)
]
·
[
𝑝ℎ(𝑥) + (𝑥 − 𝛼)ℎ
′
(𝑥)
]
− (𝑥 − 𝛼)ℎ(𝑥) ·
[
(𝑝 + 1)ℎ
′
(𝑥) + (𝑥 − 𝛼)ℎ
′′
(𝑥)
]
[
𝑝ℎ(𝑥) + (𝑥 − 𝛼)ℎ
′
(𝑥)
]
2
在 𝑥 = 𝛼 处
𝜑
′
(𝛼) = 1 −
1
𝑝
它也是小于 1 的, 所以牛顿法收敛. 考察其收敛阶
𝑥
𝑘+1
− 𝛼 = 𝜑(𝑥
𝑘
) − 𝛼 = 𝜑(𝑥
𝑘
) − 𝜑(𝛼) =
(
𝑥
𝑘
− 𝛼
)
𝜑
′
(𝜉) +
1
2
𝜑
′′
(𝜉)
(
𝑥
𝑘
− 𝛼
)
2
当 𝛼 是单根时, 有 𝜑
′
(𝛼) = 0, 所以
𝑒
𝑘+1
=
1
2
𝜑
′′
(𝜉)𝑒
2
𝑘
取极限有
lim
𝑘→∞
𝑒
𝑘+1
𝑒
2
𝑘
=
1
2
𝜑
′′
(𝛼)
所以牛顿法是二阶收敛的. 若 𝛼 是 𝑝 重根, 则可以稍微改造牛顿法
𝑥
𝑘+1
= 𝑥
𝑘
− 𝑝
𝑓 (𝑥
𝑘
)
𝑓
′
(𝑥
𝑘
)
这样就仍是二阶收敛的. 若不知道 𝛼 的重数, 则可以令
𝑢(𝑥) =
𝑓 (𝑥)
𝑓
′
(
𝑥
)
则是二阶收敛的
6 割线法
割线法用割线代替牛顿法的切线, 即
𝑥
𝑘+1
= 𝑥
𝑘
−
𝑓 (𝑥
𝑘
)(𝑥
𝑘
− 𝑥
𝑘−1
)
𝑓 (𝑥
𝑘
) − 𝑓 (𝑥
𝑘−1
)
它的收敛阶约为 1.618, 比牛顿法慢, 但是不需要求导
7 牛顿下山法
牛顿下山法是一种自适应步长的牛顿法, 即
𝑥
𝑘+1
= 𝑥
𝑘
− 𝜆
𝑓 (𝑥
𝑘
)
𝑓
′
(𝑥
𝑘
)
初始时取 𝜆 = 1, 若迭代后考虑
1. 若
|
𝑓 (𝑥
𝑘+1
)
|
<
|
𝑓 (𝑥
𝑘
)
|
, 则 𝜆 增大一倍
2. 若
|
𝑓 (𝑥
𝑘+1
)
|
>
|
𝑓 (𝑥
𝑘
)
|
, 则 𝜆 减小一半, 重新迭代直到
|
𝑓 (𝑥
𝑘+1
)
|
<
|
𝑓 (𝑥
𝑘
)
|
8 非线性方程组
考虑简单的情形, 即二阶方程组
𝑓 (𝑥, 𝑦) = 0
𝑔(𝑥, 𝑦) = 0
用向量的形式表示
F
(
x
)
=
0
,
x
=
"
𝑥
𝑦
#
, F (x) =
"
𝑓 (𝑥, 𝑦)
𝑔(𝑥, 𝑦)
#
不动点迭代即
𝐹 (x) = 0 ⇔ x = Φ(𝑥)
有压缩映像定理: 在闭域 𝐷 上, 设 Φ(x) 满足
1. 封闭性: 对任意 x ∈ 𝐷, 有 Φ(x) ∈ 𝐷
2. 压缩性: 存在常数 𝐿 < 1, 使得对任意 x, y ∈ 𝐷, 有
|
Φ(x) − Φ(y)
|
≤ 𝐿
|
x − y
|
那么存在唯一的不动点 x
∗
, 且迭代序列
x
𝑘+1
= Φ(x
𝑘
)
收敛到 x
∗
, 并且
||x
𝑘+1
− x
∗
|| ≤
𝐿
𝑘+1
1 − 𝐿
||x
1
− x
0
||
在 𝑥
0
, 𝑦
0
附近, 可以将 F (x) 展开为
𝑓 (𝑥, 𝑦) = 𝑓 (𝑥
0
, 𝑦
0
) + 𝑓
𝑥
(𝑥
0
, 𝑦
0
)(𝑥 − 𝑥
0
) + 𝑓
𝑦
(𝑥
0
, 𝑦
0
)(𝑦 − 𝑦
0
) + · · ·
𝑔
(
𝑥, 𝑦
)
=
𝑔
(
𝑥
0
, 𝑦
0
) +
𝑔
𝑥
(
𝑥
0
, 𝑦
0
)(
𝑥
−
𝑥
0
) +
𝑔
𝑦
(
𝑥
0
, 𝑦
0
)(
𝑦
−
𝑦
0
) + · · ·
近似保留一阶项, 令 Δ𝑥 = 𝑥 − 𝑥
0
, Δ𝑦 = 𝑦 − 𝑦
0
, 原方程变为
𝑓
𝑥
(𝑥
0
, 𝑦
0
)Δ𝑥 + 𝑓
𝑦
(𝑥
0
, 𝑦
0
)Δ𝑦 = − 𝑓 (𝑥
0
, 𝑦
0
)
𝑔
𝑥
(𝑥
0
, 𝑦
0
)Δ𝑥 + 𝑔
𝑦
(𝑥
0
, 𝑦
0
)Δ𝑦 = −𝑔(𝑥
0
, 𝑦
0
)
用矩阵表示
"
𝑓
𝑥
(𝑥
0
, 𝑦
0
) 𝑓
𝑦
(𝑥
0
, 𝑦
0
)
𝑔
𝑥
(𝑥
0
, 𝑦
0
) 𝑔
𝑦
(𝑥
0
, 𝑦
0
)
#"
Δ𝑥
Δ𝑦
#
= −
"
𝑓 (𝑥
0
, 𝑦
0
)
𝑔(𝑥
0
, 𝑦
0
)
#
考虑到
"
𝑥
𝑘
𝑦
𝑘
#
=
"
𝑥
𝑘−1
𝑦
𝑘−1
#
+
"
Δ𝑥
Δ𝑦
#
那么就有迭代序列
"
𝑥
𝑘
𝑦
𝑘
#
=
"
𝑥
𝑘−1
𝑦
𝑘−1
#
−
"
𝑓
𝑥
(𝑥
𝑘−1
, 𝑦
𝑘−1
) 𝑓
𝑦
(𝑥
𝑘−1
, 𝑦
𝑘−1
)
𝑔
𝑥
(
𝑥
𝑘−1
, 𝑦
𝑘−1
)
𝑔
𝑦
(
𝑥
𝑘−1
, 𝑦
𝑘−1
)
#
−1
"
𝑓 (𝑥
𝑘−1
, 𝑦
𝑘−1
)
𝑔
(
𝑥
𝑘−1
, 𝑦
𝑘−1
)
#
对于 𝑛 阶方程组, 可以类似推导
F (x) =
𝑓
1
(𝑥
1
, · · · , 𝑥
𝑛
)
.
.
.
𝑓
𝑛
(𝑥
1
, · · · , 𝑥
𝑛
)
那么
F (x) = 0 ⇔ F (x) = F (x
0
) + J (x
0
)𝚫x = 0
其中 J (x
0
) 是雅可比矩阵
J (x
0
) =
𝜕 𝑓
1
𝜕𝑥
1
· · ·
𝜕 𝑓
1
𝜕𝑥
𝑛
.
.
.
.
.
.
.
.
.
𝜕 𝑓
𝑛
𝜕𝑥
1
· · ·
𝜕 𝑓
𝑛
𝜕𝑥
𝑛
那么迭代序列为
x
𝑘+1
= x
𝑘
− J (x
𝑘
)
−1
F (x
𝑘
)
