计算方法第七章方程求根与二分法.ppt

* 弦截法算法实现 * §7.6 求根问题的敏感性与多项式的零点 * §7.7 非线性方程组的数值解法 　　一般的非线性方程组可写成F(x)=0,其中F和x都是n维向量，或写成 其中，　　　　　中至少有一个是 的非线性函数。当n=1时，就是单个的方程f(x)=0。非线性方程和方程组的求解是工程和科学领域中最常见的问题。 * 机器人手臂定位问题 　　考虑两环节机器人手臂定位问题。设两节臂长分别为d1和d2，如图所示，第一臂与水平方向所成的角为?，第二臂与第一臂所成的角为?。问题是求?和?，使第二臂的端点位于适当的位置，比如其坐标为(p1,p2) * 机器人手臂定位问题 设第一臂和第二臂的端点坐标分别为(x1,y1)和（x2,y2)，则有 * 机器人手臂定位问题 这样，我们的问题是要解下列方程组 显然，这是一个关于?和?的非线性方程组。 * 非线性方程组常用求解方法 1.线性化方法 即将非线性方程组以线性方程组来近似，对此构成迭代格式，用以逐次逼近所求的解。这类方法以Newton法为代表。 2. 极小化方法，即用非线性函数 构造模函数?，如 ： 求其极小点，此极小点可作为一组解。这类方法以最速下降法为代表。 * Newton法 考虑向量形式的非线性方程组 F(X)=0 将向量函数F(X)在点X(k)作一阶Taylor展开，得到近似方程： 其中 为n阶Jacobi矩阵 * Newton法 * Newton法 Newton法迭代公式 显然它是一元方程Newton法迭代公式的直接推广。 当 即 时（?为给定的精度），取X(k+1)作为方程组的近似解。 * Newton法 可以证明，当初始值X(0)充分接近方程组的解X*时Newton法的迭代过程是收敛的，而且是平方收敛的。 * Newton法 Newton法解方程组的计算步骤是 （1）给定初始值X(0),k←0； （2）计算向量F(X(k)) 和Jacobi矩阵 （3）迭代 （4）若 ，取X(k+1)为方程组 的近似解；否则，令k←k+1，转向（2），继续迭代。 * 例题 例7.9 求方程组 在 附近的解。 * 例题 解 计算向量函数 的Jacobi矩阵得： 代入初始向量 ,得 * 例题 * 例题 以 为初始向量继续迭代，迭代三次的结果如下表 k 0 1 2 3 x 1 1.0 0.998609 0.998607 y 0 -0.1029 -0.105531 -0.105531 因此可得所求的解 * 最速下降法 根据方程组构造模函数 任何使?(X)=0的极小点即为方程组的解。因此，非线性方程组的求解问题等价于模函数极小化问题。 * 最速下降法 最速下降法是函数逐次极小化的方法。它以多元函数在某点的负梯度方向是函数在该点下降最迅速为理论根据，每次都在?(X)的负梯度方向上取?(X)的相对极小点X(k)，直到?(X)值下降到充分小为止。此时，极小点序列{X(k)}收敛于方程组的解X*。 * 计算步骤 （1）给定初始值X(0), k←0； （2）计算负梯度向量 ； （3）作一维有哪些信誉好的足球投注网站计算探索步长hk，使 （4）作 ； （5）若 ，则取 ，停机；否则，令 k←k+1，转向（2），继续迭代。 * 计算步骤 步长hk可用如下方法决定。将 在h=0处作二阶Taylor展开，得其近似式为： * 计算步骤 令 ，并注意 有 * 计算步骤 取 。如果有 则置 作为解的新近似值；否则缩小h，例如每次缩小一半，直到使函数下降为止。 * 例题 例7.10 应用最速下降法求解例7.9的方程组。 解 构造模函数 计算 * 例题 及 得： * 例题 取 ，得 有 * 例题 于是得到第1次迭代近似解 模函数值为 以 为初始值继续迭代，得 * 例题 模函数值为 这个结果比在例1中选取同样初始值，应用Newton法迭代一次后得到的模函数值 还要大。一般来说，Newton法在解 附近的收敛速度比最速下降法快得多。 * 最速下降法 最速下降法对初始值的要求比Newton法对初始值的要求宽松许多，只是在解附近收敛速度减慢。因此，实际应用中，最速下降法常与Newton法结合使用。通常的作法是，先用最速下降法，当模函数值下降到一定程度后，便改