第2章 非线性方程(组)的数值解法1

非线性方程 组 的数值解法 基础教学部数学教研室彭晓华 方程是很多工程和科学工作的发动机 非线性现象广泛存在于物质世界与社会生活中 在工程和科学计算中 常涉及到非线性方程或非线性方程组的求解问题 例如 2 1引言 1 在光的衍射理论 thetheoryofdiffractionoflight 中 我们需要求x tanx 0的根 2 在行星轨道 planetaryorbits 的计算中 对任意的a和b 我们需要求x asinx b的根 数值求解方程组的必要性 3 在数学中 需要求n次多项式 4 在天体力学中 有如下开普勒 Kepler 方程 其中 表示时间 表示弧度 行星运动的轨道 是 的函数 也就是说 对每个时刻 上述方程 运动轨道位置 超越方程 有唯一解 的根 在非线性方程的求解中 多项式求根是最常见 最简单的情形 例如想通过矩阵的特征多项式求特征根 就会遇到这一问题 一元二次方程求根公式 一元三次方程求根公式 根据代数基本定理 在复数域内 n次代数多项式有且只有n个根 而由伽罗华 Galois 理论 5次以上 含5次 的多项式方程无求根公式 例如求代数方程 的根 除了多项式求根之外 更多的是超越方程求根问题 超越方程是指包含指数函数 三角函数等特殊函数的方程 例如前面的几个例子 又如求解非线性方程组 上述这些问题 都归结为寻求非线性函数 使 称为方程或方程组 为向量函数时 的零点 的根或函数 由于自然现象和实际问题的复杂性 对函数方程和方程组求解问题 没有哪一种方法能求出一般方程的准确解 因此 求其数值解就非常必要了 方程的根 即求 本章目的 介绍用于实际计算中求f x 0的根的近似值的几种常用方法 主要有 二分法 不动点迭代法 牛顿迭代法 方程根的数值计算大致可以分为三个步骤 1 判断根的存在性 2 确定根的分布范围 根的隔离 3 根的精确化 如果f x 可以分解成 其中m为正整数且 则称x 是f x 的m重零点 或称方程f x 0的m重根 当m 1时称x 为单根 若f x 存在m阶导数 则x 是方程f x 的m重根 m 1 当且仅当 1 重根 方程求根的理论依据 设f x 0为复系数n次代数方程 则f x 0在复数域上恰有n个根 m重根按m个计算 若f x 0为实系数n次代数方程 则复数根成对出现 2 代数基本定理 3 零点定理 设 且 则方程在区间上至少有一个根 如果在上恒正或恒负 则此根唯一 1 分析法 利用对函数f x 的各种性质的分析来确定根的分布范围 练习 试确定f x x3 6x2 9x 1 0各根的分布范围 隔根区间为 0 1 1 3 3 4 根的隔离 例2 1求方程 的有根区间 在 内连续 而且 所以 为单调增加函数 则 在 内最多只有一个实根 又因为 所以 就是所求的有根区间 解因为 先确定方程f x 0的所有实根所在的区间 a b 再按照选定的步长h b a n 取点xk a kh k 0 1 2 n 逐步计算函数值f xk 依据函数值异号及实根的个数确定隔根区间 必要时可以调整步长h 总可以把隔根区间全部找出 2 逐步搜索法 代数方程根的模上下界定理 例2 2求方程 解根据有根区间定义 对 的根进行搜索计算 结果如表2 1 的有根区间 由表2 1可知方程的有根区间为 1 2 3 4 5 6 表2 1逐次搜索计算f x 的符号 得 0 2 4 2即 4 2 0 2 0 2 4 2取n 8 h 0 5 计算f xk 由上表可知隔根区间为 0 7 0 2 1 2 1 7 1 7 2 2 解 设方程的根为 由 max 3 2 1 9 0 8 3 2 v 1 0 8 max 1 3 2 1 9 4 例2 3 求方程 的隔根区间 3 图解法 解因为 在 内连续 要判别 与 例2 4判别方程 有3个实根 方程有3个实根 即要判别 轴有3个 内只有一个根 交点 只须判别有3个有根区间 且每个区间 由函数图像来确定根的大体位置 x 1 0 01 4 y exp x 3 x 2 plot x y r x 0 x gridon 利用MATLAB画图来确定有根区间 由函数图1可判别 3个有根区间分别为 1 0 0 5 1 3 5 4 图1判别函数的有根区间 根的精确化 即求根的方法 二分法迭代法牛顿迭代法 数值分析 解非线性方程 组 并按下式进行判断 对于给定的精度要求 用表示方程在区间上的根 1 取区间 的中点 对于给定的精度要求 2 2二分法 如此反复二分下去 得到一系列有根区间 以 作为 的近似值 其绝对误差 只要二分足够多次 即k充分大 便有 其中 因此 得到满足精度所需的二分次数为 为给定的精度 因而 二分法终止的条件为 表2 2二分计算结果 二分法算法实现 例2 5求 在区间 由 内的根 要求准确到小数点后两位 即 解 二分法的结果表1所示 二分法的优缺点 1 优点 算法直观 简单 且总能保证收敛 数值分析 解非线性方程 组 2 缺点 收敛速度较慢 是线性收敛 3 作用 一般不单独将其用于求根 只用其为根求得一个较好的近似 数值分析 解非线性方程 组 2 3迭代法及其收敛性 方程的根 2 不动点迭代公式 一 不动点迭代 1 不动点 代入方程 代入方程 则有 称 为函数 的不动点 由此确定了相应的迭代法 首先将方程 组 写成等价的迭代形式 1 称 为迭代函数 当 即 的根 这种求得不动点的方法称为不动点迭代法 数值分析 解非线性方程 组 求得序列 如果当 时 就是不动点的近似序列 称为迭代序列 2 称 为不动点迭代公式 3 时 称为迭代收敛 为不动点 4 通常将方程f x 0化为与它同解的方程的方法不止一种 有的收敛 有的不收敛 这取决于的性态 方程的求根问题在几何上就是确定曲线y 与直线y x的交点P的横坐标 如图所示 2 迭代法的几何意义 数值分析 解非线性方程 组 迭代法的几何意义 数值分析 解非线性方程 组 例2 6 三种迭代结果见表2 为什么 1 2 发散 3 收敛 取 正根为 数值分析 解非线性方程 组 4 构造迭代函数的方法 表2 3 的迭代例子 问题 如何构造 才能使迭代序列 一定收敛于不动点 近似解的误差怎样估计 设迭代公式为 即 而且序列 二 不动点迭代法收敛性 满足微分中值定理条件时 有 当 显然只要 时 式 成立 收敛于不动点 因而有 x 分析 定理3 映内压缩性定理 收敛的充分性条件 设方程 在 上存在唯一解 是迭代函数 如果 1 映内性 对任何 称正数 则迭代公式 收敛于方程 在 上的唯一根 2 压缩性 为压缩因子 且 对任意的初值 并有误差估计式 2 10 证明 收敛性是显然的 下面证明误差估计式 因为 据此递推 可得 于是对任意正整数 有 在上式中令 即得 2 10 式 定理证毕 注意到 对任意正整数 有 令 则有 注 1 事前误差估计 对于收敛的迭代序列 2 控制迭代次数 根据事前误差估计公式 2 10 公式 2 10 右端项可用于误差上限的估计 其中 为取定的迭代次数 压缩因子取为 为使近似解达到精度要求 由 2 11 即用前后两次迭代结果之差的绝对值是否小于允许误差来判断迭代是否终止 也可用于误差上限的事后估计 3 事后误差估计 由公式 2 11 可作为迭代算法的终止条件 可得所需要的最少迭代次数k 即 迭代法的算法框图 例2 7求方程 的正根 因为是求正根 所以不考虑 所以在 解 解得驻点 令 1 确定有根区间 内有正根 2 选取恰当的迭代函数 判别根的收敛性 取 由于 所以在 内有正根 映内性 压缩性 因此迭代公式 3 迭代计算 迭代公式 必收敛 取初值为 由表2 4可知 x7已达到6位有效数字 可取1 32472作为所求根的近似值 数值结果如表2 4 对于任意的值 1 32472 1 32472 1 32473 1 32476 1 32494 1 32588 1 33086 1 35721 xk 8 7 6 5 4 3 2 1 k 表2 4例5迭代值 数值分析 解非线性方程 组 若将原方程改写为 用迭代公式计算 则迭代过程是发散的 四 局部收敛性与收敛阶 1 全局收敛 大范围收敛 若对 中的任意一点 作初始值 迭代均收敛 这种形式的收敛称为全局收敛或大范围收敛 2 局部收敛 若在 的某个邻域 内的每一点 迭代均收敛 称这种形式的收敛为局部收敛 定理4 局部收敛性 设 在 的邻近连续 且 则迭代过程 在 邻近具有局部收敛性 数值分析 解非线性方程 组 证明因为 连续 所以存在 的一个 邻域 使得对任意 有 成立 并有 即对任意 有 因此 满足定理3的映内压缩性条件 从而 对任意 迭代过程局部收敛 例2 8求方程 附近的一个根 要求精确到 解将原方程改写为 在 由于在根附近 选取 迭代公式为 取初值 迭代计算 数值结果列于下表 数值分析 解非线性方程 组 所以局部收敛 迭代到第18次时 0 56711880 56715710 56713540 56714770 5671407 1415161718 0 56843800 56640940 56755960 56690720 56727720 56706730 5671863 78910111213 0 50 60653060 54523920 57970310 56006460 57117210 5648629 0123456 为所求近似根 方程的精确解为 返回例2 11 数值分析 解非线性方程 组 显然 这里选取的迭代公式收敛 并且收敛速度较快 注 由例8可知 如果构造的 满足定理条件 并且使 尽量小 可使迭代计算加速收敛 定义1 收敛阶 设迭代过程收敛于的根 记迭代误差若存在常数p p 1 和c c 0 使 则称序列是p阶收敛的 c称渐近误差常数 数p的大小反映了迭代法收敛的速度的快慢 p愈大 则收敛的速度愈快 故迭代法的收敛阶是对迭代法收敛速度的一种度量 五 迭代法的收敛速度 特别地 p 1时称为线性收敛 p 2时称为平方收敛 1 p 2时称为超线性收敛 一种迭代法具有实用价值 首先要求它是收敛的 其次还要求它收敛得比较快 例2 9解方程 选取 使迭代计算收敛 并计算根 故取 使 为使收敛速度快 取 使 因此迭代公式为 取初值 迭代计算 数值结果如下 解由于根 定理5设迭代过程 若在所求根的邻域连续且则迭代过程在邻域是p阶收敛的 证明由于 由定理4可知迭代过程 具有局部收敛性 将 在根 处作泰勒展开 利用条件 2 13 则有 数值分析 解非线性方程 组 2 13 这表明迭代过程 由上式得 必为阶收敛 证毕 由定理5可知 迭代过程的收敛速度依赖于迭代函数 的选取 如果当 时 则该迭代过程只能是线性收敛 数值分析 解非线性方程 组 因此对迭代误差 当 时有 例2 10已知迭代公式收敛于证明该迭代公式平方收敛 数值分析 解非线性方程 组 证 迭代公式相应的迭代函数为 所以 该迭代公式平方收敛 1 分析法 利用对函数f x 的各种性质的分析来确定根的分布范围 1 代数学基本定理 2 零点定理 一 判定根的存在性及有根区间的隔离 小结 2 搜索法 利用代数方程根的模上下界定理 确定有根区间 再用搜索法实现有根区间的分离 3 图形法 利用函数的图形确定函数零点的 个数及其分