下降法

英文

descent method

简介

亦称极小化方法.一类重要的迭代法.这类方法将方程组求解问题转化为求泛函极小问题.设给出方程组F(x)=0，其中F=(f₁，f₂，…，f_n)^T，令

φ(x)=F(x)^TF(x)=f²_i(x)≥0，

则F(x)=0的充分必要条件是φ(x)=0.若φ(x)的极小点x^*使φ(x^*)=0，则x^*也是方程组F(x)=0的解.只要构造迭代序列{x^k}使

且满足

φ(x^k)=0，

就可求得方程组的足够好的近似解.
具体做法是选初始近似x⁰，沿一个使φ(x)下降的方向p₀，令x¹＝x⁰+μp₀，μ>0.然后选步长因子μ=μ₀，使φ(x⁰+μ₀p₀)<φ(x⁰)，得x¹＝x⁰+μ₀p₀.一般情况是从x^k出发，沿φ(x)下降方向p_k求出

x^k+1＝x^k+μ_kp_k (k=0，1，…)，

且φ(x^k+1)<φ(x^k)，直到φ(x^m)<ε为止，x^m就作为方程组解x^*的近似.上述算法中也可选μ_k使φ(x^k+μ_kp_k)= φ(x^k+μp_k)，这是一个求一维的极小问题.以上算法即为下降法.如果p_k选择不同，就可得到不同的下降法，特别地，若选p_k为φ的负梯度，即p_k＝-▿φ(x^k)，则得梯度算法

x^k+1＝x^k-μ_k▿φ(x^k)，

其中

φ(x^k+μ_kp_k)= φ(x^k+μp_k).

此算法也称最速下降法.此法的优点是计算量少，程序简单，但收敛慢.在下降法中可取下降方向p_k为牛顿方向，即

p_k＝-F′(x^k)^-1F(x^k).

特别地，当μ_k＝1时，就得到牛顿法，此外还可取沿坐标方向下降的方法，实际上就是一步的SOR牛顿法.

另一类较重要的下降法为共轭梯度法.共轭梯度法是最简单的下降法，早在1847年就由法国数学家、力学家柯西(Cauchy，A.-L.)提出，以后坦普尔(Temple，G.)、柯里(Curry，H.)等人也进行过研究并证明了方法的收敛性.20世纪50至60年代，又有不少学者对下降法做了很多研究，提出不少具体算法并建立了收敛性理论，使这类算法在解非线性方程组和最优化计算中得到广泛应用.