教学目的掌握解非线性方程组的二分法和插值法

第六章非线性方程组的迭代解法 教学目的教学目的 1.掌握解非线性方程（组）的二分法和插值法；掌握解非线性方程（组）的二分法和插值法；2.掌握解非线性方程（组）的一般迭代法及有关收敛性掌握解非线性方程（组）的一般迭代法及有关收敛性的证明与牛顿法；的证明与牛顿法；3.掌握解非线性方程（组）的牛顿法掌握解非线性方程（组）的牛顿法 4.了解加速收敛的方法。了解加速收敛的方法。教学重点及难点教学重点及难点 重点重点是解非线性方程（组）的牛顿法；是解非线性方程（组）的牛顿法；难点难点是迭代法的收敛性的证明。是迭代法的收敛性的证明。第第6章章 非线性方程和方程组非线性方程和方程组的数值解法的数值解法第六章非线性方程组的迭代解法 第第6章章 非线性方程和方程组非线性方程和方程组的数值解法的数值解法考虑两环节机器人手臂定位问题。设两节臂考虑两环节机器人手臂定位问题。设两节臂长分别为长分别为d1和和d2，如图，如图6-1所示，第一臂与水平所示，第一臂与水平方向所成的角为，第二臂与第一臂所成的角方向所成的角为，第二臂与第一臂所成的角为。问题是求和，使第二臂的端点为。问题是求和，使第二臂的端点位于适当的位置，比如其坐标为位于适当的位置，比如其坐标为 21,ppxy2d1d 图图6-1一般的非线性方程组可写成一般的非线性方程组可写成F(x)=0,其中其中F和和x都是都是n维向量，或写成维向量，或写成其中，中至少有一个是其中，中至少有一个是 的非线性函数。当的非线性函数。当n=1时，就是单个的方程时，就是单个的方程f(x)=0。非线性方程和方程组的求解是工程和。非线性方程和方程组的求解是工程和科学领域中最常见的问题。下面举一个例子：科学领域中最常见的问题。下面举一个例子：,n,2,1,0),(21 ixxxfninfff,21 12,nx xx第六章非线性方程组的迭代解法 则有和点坐标分别为设第一臂和第二臂的端),(),(2211yxyx这样，我们的问题是要解下列方程组这样，我们的问题是要解下列方程组121222coscos()sinsin()ddpddp的非线性方程组。和显然，这是一个关于1111c o s,sin.xdyd212212c o s(),sin().xxdyyd第六章非线性方程组的迭代解法 与线性方程组不同，除特殊情况外，求解非线性方程不能用直与线性方程组不同，除特殊情况外，求解非线性方程不能用直接法求数值解，而是要用迭代法。迭代法的基本问题是收敛性、收接法求数值解，而是要用迭代法。迭代法的基本问题是收敛性、收敛速度和计算效率。敛速度和计算效率。对于线性方程组，如前所述，若某迭代法收敛，则取任何初值对于线性方程组，如前所述，若某迭代法收敛，则取任何初值都收敛。但是，对于非线性方程，不同的初值可能有不同的收敛性都收敛。但是，对于非线性方程，不同的初值可能有不同的收敛性态，有的初值使迭代收敛，有的则不收敛。一般说来，为使迭代法态，有的初值使迭代收敛，有的则不收敛。一般说来，为使迭代法收敛，初值应取在解的附近。收敛，初值应取在解的附近。0.0111 axaxaxannnn我们先详细讨论单个方程的情形，其中有一类是形如我们先详细讨论单个方程的情形，其中有一类是形如的代数方程。当的代数方程。当 时，其根是不能用加、减、乘、除和开方时，其根是不能用加、减、乘、除和开方的有限次运算公式表示的，所以代数方程的解法也主要是迭代法。的有限次运算公式表示的，所以代数方程的解法也主要是迭代法。5 n第六章非线性方程组的迭代解法,0)(),()()(*xgxgxxxfm0)(,0)(.)()(*)(*)1(*xfxfxfxfmm方程的数值解法的收敛性，也与方程根的重数有关。对于一般的函方程的数值解法的收敛性，也与方程根的重数有关。对于一般的函数，若有数，若有,)(baCxf 其中其中m为正整数，我们称是为正整数，我们称是f(x)的的m重零点，或称是方程重零点，或称是方程f(x)=0的的m重根。显然，若是重根。显然，若是f(x)的的m重零点，且重零点，且g(x)充分光滑，则有充分光滑，则有 x x x当当m为奇数时，为奇数时，f(x)在点处变号，当在点处变号，当m为偶数时，为偶数时，f(x)在点处不变号。在点处不变号。x x第六章非线性方程组的迭代解法 6.1方程求根的二分法方程求根的二分法(),()()0,()0,fxCa bfafbfxa ba b设若则 方 程在内 至 少 有 一 个 根，称为 方 程 的 有 根 区 间。通 过 缩 小 有 根 区 间，我 们 可 以 形 成 方 程 求 根 的 数 值 解 法。下 面 我 们 给 出 方 程 求 根 的 二 分 法。00,()()0,nnnnnaba babxfafx设为 有 限 区 间，的 中 点 是若 有则 令 新 的 有 根 区 间第六章非线性方程组的迭代解法 1111,()()0,nnnnnnnnnnabaxfafxabxb若，则 令。这 样，若 反 复 二 分 下 去，即 可 得 出 一 系 列 有 限 区 间。，.,.,2211nnbabababa,kkab其 中 每 个 区 间 都 是 前 一 个 区 间 的 一 半。因 此，的 长 度0()2kkkbabak .第六章非线性方程组的迭代解法 由此可见，如果二分过程能无限地继续下去，这些区间最终必由此可见，如果二分过程能无限地继续下去，这些区间最终必收敛于一点收敛于一点 该点显然就是所求的根。该点显然就是所求的根。,*x*,()/2kkkkkkabxabxx每 次 二 分 之 后，设 去 有 限 区 间的 中 点，作 为 根 的 近 似 值，则 在 二 分 过程 中 可 以 获 得 一 个 近 似 根 的 序 列，该 序 列必 以 根为 极 限。在 实 际 计 算 时，我 们 不 可 能 完 成 这 个 无 限 过 程，其 实 也 没 有 这 种 必 要，因 为 数 值 分 析 的 结 果允 许 带 有 一 定 的 误 差。由 于第六章非线性方程组的迭代解法,221*kkkkababxx*,kkxx只 要 二 分 足 够 多 次（即充 分 大），则 有这 里位 预 定 的 精 度。36.1()1011.5fxxx例求 方 程在 区 间，内 的 一 个实根，要求准确到小数点后的第实根，要求准确到小数点后的第2位。位。1,1.5,()0,()0,abfafbab解这 里。取的,0)(,25.100 xfbax二等分，由于将区间中点第六章非线性方程组的迭代解法 0010111()()1.25,1.5,61fafxxaxbbab即与同 号，故 在的 右 侧 有 方 程 的 一 个实 根，这 时，令而 新 的有 限 区 间 为。二 分 过 程 可 如 此 反 复 下 去计 算 结 果 如 表。k)(kkkkxfxba1.32031.32811.3242-1.31251.32811.3203+1.31251.34381.3281-1.31251.3751.3438+1.251.3751.3125-1.251.51.375+11.51.25-6543210表表6-1 第六章非线性方程组的迭代解法 1()/20.005kba我 们 现 在 预 估 所 要 二 的 次 数。令可与实际计算结果相符。次就能达到预定的精度既二分得,005.06,66*xxk 上述二分法的优点是算法简单，而且在有限区间内，收敛性上述二分法的优点是算法简单，而且在有限区间内，收敛性总能得到保证。值得注意的是，为了求出足够精确的近似解，往总能得到保证。值得注意的是，为了求出足够精确的近似解，往往需要计算很多次函数值，是一种收敛较慢的方法，通常用求根往需要计算很多次函数值，是一种收敛较慢的方法，通常用求根的粗略近似值，把它作为后面要讨论的迭代法的初始值。另一方的粗略近似值，把它作为后面要讨论的迭代法的初始值。另一方面，二分法只使用于求一元方程的奇数重实根。面，二分法只使用于求一元方程的奇数重实根。第六章非线性方程组的迭代解法 在二分法中，是逐次将有根区间折半。更一般地是，从有限区间在二分法中，是逐次将有根区间折半。更一般地是，从有限区间的左端点出发，按预定的步长的左端点出发，按预定的步长h一步一步地向右跨，每跨一步进行一一步一步地向右跨，每跨一步进行一次根的次根的“搜索搜索”，即检查所在节点上的函数值的符号，一旦发现其与，即检查所在节点上的函数值的符号，一旦发现其与左端的函数值异号，则可确定一个缩小了的有限区间，其宽度等于预左端的函数值异号，则可确定一个缩小了的有限区间，其宽度等于预定的步长定的步长h。然后，再对新的。然后，再对新的有限区间，取新的更小的预定有限区间，取新的更小的预定步长，继续步长，继续“搜索搜索”，直到有限区间，直到有限区间的宽度足够小。称这种方法为的宽度足够小。称这种方法为逐步搜索法逐步搜索法。