1.3下降算法 定义1.15（下降南数、收敛性） 对解集合∈X与X上的算法A,X上的连续实函数中：X→R称为关于与A的下降函数 当且仗当： ()<(x)x生n,y∈A(a ()≤(r)x∈，y∈A(a 对解集合2∈X与X上的算法A,若从x0CX出发，无论每次的E+1从A(红)中如何选取， 得到序列{红}的每个收敛子列极限都在D中，则称A在0处收敛于L。若对每个y∈Y都有 A在处收敛于，则称A在Y上收敛于B. 作如上的抽象后，就可以从数学角度找到算法收敛的必要条件，也即： 定理1.16（收敛性条件） 对解集合2∈X与X上的算法A,从某个初始点0出发，每次E+1从A(x)中任意选取，得 到序列{红n}。在下列条件均满足时，{红n}的每个收敛子列极限都在中： 。{红n}包含于X的个紧子集中“。 。存在关于卫与A的下降西数中。 。A在X\2上是闭的。 “在R”上，包含在紧集中即为有界。 证明先证（工）的极限存在。由%包舍在紧子集中，其存在收敛子列：，设极限为工。由连续性可 知（工k,)→（四）。另一方面，根据条件(rk)是单调下降的，由数列极限知识即得()→()。 若x生2，考虑子列k+1,其必然也有收敛子列，假设收敛至五，根据已证，有()=()。 然而，由于A在卫补集上闭，工k+1∈A(%,)可推出五∈A(),根据下降函数定义与工生即有 ()<()，矛盾。 1.3.2迭代方法概述 虽然我们从理论中得到了收敛性的结果，对现实的算法，迭代不可能无穷下去，需要规定一些实 用的终止迭代过程的准则，一般称为收敛准则或停机准则，例如（仁为充分小正数）： 。rk+1-x<e或 :ll <E 。fe)-fe<e或<e o7f(xk)‖<e 而评价算法优劣的一个重要标准就是收敛的快慢，在数学上可以定义为： 定义1.17（收敛阶、线性收敛） 假设imk→oxk=x,且满足（假设所有rk均非r*) nzk+1-‖ 0≤1 lim sup-xP =B<0 则称{红n}以p阶收敛。 设所有这样的p构成集合P,称其上确界%=spP为{红n}的收敛阶。 若P0=1,且存在0<B<1使P取1时定义式成立，则称{红n}是以收敛比B线性收敛的。若 1.3 下降算法 定义 1.15 (下降函数、收敛性) ♣ 对解集合 Ω ∈ X 与 X 上的算法 A，X 上的连续实函数 ψ : X → R 称为关于 Ω 与 A 的下降函数 当且仅当：    ψ(y) < ψ(x) x /∈ Ω, y ∈ A(x) ψ(y) ≤ ψ(x) x ∈ Ω, y ∈ A(x) 对解集合 Ω ∈ X 与 X 上的算法 A，若从 x0 ⊂ X 出发，无论每次的 xk+1 从 A(xk) 中如何选取， 得到序列 {xn} 的每个收敛子列极限都在 Ω 中，则称 A 在 x0 处收敛于 Ω。若对每个 y ∈ Y 都有 A 在 y 处收敛于 Ω，则称 A 在 Y 上收敛于 Ω。 作如上的抽象后，就可以从数学角度找到算法收敛的必要条件，也即： 定理 1.16 (收敛性条件) ♡ 对解集合 Ω ∈ X 与 X 上的算法 A，从某个初始点 x0 出发，每次 xk+1 从 A(xk) 中任意选取，得 到序列 {xn}。在下列条件均满足时，{xn} 的每个收敛子列极限都在 Ω 中： {xn} 包含于 X 的某个紧子集中a。 存在关于 Ω 与 A 的下降函数 ψ。 A 在 X\Ω 上是闭的。 a在 R n 上，包含在紧集中即为有界。 证明 先证 ψ(xk) 的极限存在。由 xk 包含在紧子集中，其存在收敛子列 xki，设极限为 x。由连续性可 知 ψ(xki ) → ψ(x)。另一方面，根据条件 ψ(xk) 是单调下降的，由数列极限知识即得 ψ(xk) → ψ(x)。 若 x /∈ Ω，考虑子列 xki+1，其必然也有收敛子列，假设收敛至 x¯，根据已证，有 ψ(¯x) = ψ(x)。 然而，由于 A 在 Ω 补集上闭，xki+1 ∈ A(xki ) 可推出 x¯ ∈ A(x)，根据下降函数定义与 x /∈ Ω 即有 ψ(¯x) < ψ(x)，矛盾。 1.3.2 迭代方法概述 虽然我们从理论中得到了收敛性的结果，对现实的算法，迭代不可能无穷下去，需要规定一些实 用的终止迭代过程的准则，一般称为收敛准则或停机准则，例如 (ε 为充分小正数)： ∥xk+1 − xk∥ < ε 或 ∥xk+1−xk∥ ∥xk∥ < ε |f(xk+1) − f(xk)| < ε 或 |f(xk+1)−f(xk)| |f(xk)| < ε ∥∇f(xk)∥ < ε 而评价算法优劣的一个重要标准就是收敛的快慢，在数学上可以定义为： 定义 1.17 (收敛阶、线性收敛) 假设 limk→∞ xk = x ∗，且满足 (假设所有 xk 均非 x ∗ ) 0 ≤ lim sup k→∞ ∥xk+1 − x ∗∥ ∥xk − x ∗∥ p = β < ∞ 则称 {xn} 以 p 阶收敛。 设所有这样的 p 构成集合 P，称其上确界 p0 = sup P 为 {xn} 的收敛阶。 若 p0 = 1，且存在 0 < β < 1 使 p 取 1 时定义式成立，则称 {xn} 是以收敛比 β 线性收敛的。若 8