清华大学出版社 解非线性方程组 RESS 求解下面的非线性方程组 f(x1,x2,…xn)=0 f2(xu,x )=0 X.x )=0 其中,x1,X2,…,xn是实变量,f是未知量X1,X2…,xn的非线性实函 数。要求确定上述方程组在指定求根范围内的组解x,x2;…x 在指定求根区域D内,选定一个随机点x作为随机搜索的出发 点。在算法的搜索过程中,假设第步随机搜索得到的随机搜 索点为X。在第+1步,计算出下一步的随机搜索增量ΔX。从 当前点依A得到第+1步的随机搜索点。当X时,取为所求 非线性方程组的近似解。否则进行下—步新的随机搜索过程
6 解非线性方程组 求解下面的非线性方程组 = = = ( , , , ) 0 ( , , , ) 0 ( , , , ) 0 1 2 2 1 2 1 1 2 n n n n f x x x f x x x f x x x 其中，x1 ,x2 ,…,xn是实变量，f i是未知量x1 ,x2 ,…,xn的非线性实函 数。要求确定上述方程组在指定求根范围内的一组解 * * 2 * 1 , , , n x x x 在指定求根区域D内，选定一个随机点x0作为随机搜索的出发 点。在算法的搜索过程中，假设第j步随机搜索得到的随机搜 索点为xj。在第j+1步，计算出下一步的随机搜索增量xj。从 当前点xj依xj得到第j+1步的随机搜索点。当x<时，取为所求 非线性方程组的近似解。否则进行下一步新的随机搜索过程
清华大学出版社 TSINGHUA UNIVERSITY PRESS 舍伍德( Sherwood)算法 设A是一个确定性算法,当它的输入实例为刈时所需的计算时间记 为tA(∞。设Ⅹ是算法A的输入规模为η的实例的全体,则当问题的 输入规模为n时,算法A所需的平均时间为 t(m)=∑t1(x)/|Xn 这显然不能排除存在ⅹ∈Ⅺn使得t1(x)>A(n)的可能性。希望获得 个概率算法B,使得对问题的输入规模为η的每一个实例均有 tB(x=ta(n+s(n) 这就是舍伍德算法设计的基本思想。当s(η)与tm框比可忽略时, 舍伍德算法可获得很好的平均性能
7 舍伍德(Sherwood)算法 设A是一个确定性算法，当它的输入实例为x时所需的计算时间记 为tA(x)。设Xn是算法A的输入规模为n的实例的全体，则当问题的 输入规模为n时，算法A所需的平均时间为 = Xn x A n t A (n) t (x) / | X | 这显然不能排除存在x∈Xn使得 的可能性。希望获得 一个概率算法B，使得对问题的输入规模为n的每一个实例均有 这就是舍伍德算法设计的基本思想。当s(n)与tA(n)相比可忽略时， 舍伍德算法可获得很好的平均性能。 t (x) t A (n) A t (x) t A (n) s(n) B = +