计算声学第三章非线性方程的数值解法.ppt

第三章非线性方程的数值解法 科学技术研究与工程实践中 经常会遇到求解非线性方程的问题 一般归纳为求解方程其中是一元非线性实函数 根据是代数多项式还是超越函数 指数函数 对数函数 三角函数等 方程分别称为代数方程或超越方程 次代数方程 超越方程 第三章非线性方程的数值解法 对于代数方程 根的数目与方程的次数相同 不高于4次的代数方程已有求根公式 高于4次的代数方程没有精确的求根公式 超越方程则复杂得多 如果有解 可能是一个或多个 或无穷多个 没有精确的求解公式 因此 需要研究如何采用一定的数值算法求得满足一定精度要求的近似根 内容提要 隔根区间的确定 二分法 迭代法 牛顿迭代法 弦截法重点内容 迭代法 牛顿迭代法 第三章非线性方程的数值解法 数值方法求方程根的近似值 要解决三个问题 1 根的存在性 方程有没有根 如果有根 有几个 2 根的隔离 找出有根区间 把有根区间分成较小的子区间 每个子区间只有一个根 隔根区间 3 根的精确化 确定了隔根区间后 可以用各种方法将某一近似根逐步精确化 按照一定的方法产生一个序列 此序列在一定的条件下收敛于方程的根 产生序列的不同方法就构成了不同的方程求根方法 第三章非线性方程的数值解法 应用举例 本征声线求解本征声线 从声源出发经过一定的传播路径到达接收点的声线 接收点处的声场是所有本征声线能量叠加的结果 折射定律 Snell 第三章非线性方程的数值解法 对于给定的海洋环境 每条声线的轨迹由声线的起始掠射角唯一决定 设声源位于处 接收点位于处 声线轨迹方程 需要导出声线以掠射角从声源出发 经过一定水平距离到达深度的计算公式 有改变 给定精度要求 进行求解 第三章非线性方程的数值解法 1根的搜索与二分法 根的搜索定义 隔根区间 如果在区间内只有方程的一个根 则称区间为隔根区间 隔根区间的确定描图法逐步搜索法 介值定理 定理1 设函数在区间上连续 且 则方程在上至少有一个根 定理2 设函数在区间上是单调连续函数 且 则方程在有且仅有一个根 1根的搜索与二分法 1根的搜索与二分法 描图法 画出的简图 由曲线与轴的交点位置确定出隔根区间 或者将方程等价变形为 画出函数和的简图 从两条曲线交点的横坐标位置确定隔根区间 例 求方程的隔根区间 解 由图可知 方程仅有一个实根 隔根区间为 1根的搜索与二分法 逐步搜索法 首先确定方程的实根所在区间再按照选定的步长 n为正整数 逐点计算处的函数值 当与异号时 则即为方程的一个隔根区间 对于次代数方程其根的绝对值的上下界有如下结论 1 如果 则方程的根的绝对值小于 2 如果 则方程根的绝对值大于 1根的搜索与二分法 例 求方程的隔根区间 解 利用逐步搜索法设方程的根为 则即根的所在区间为和 取计算 隔根区间为 1根的搜索与二分法 二分法基本思想 通过计算隔根区间的中点 逐步缩小隔根区间 从而得到方程的近似根序列 过程 设为连续函数 方程的隔根区间为 则函数值异号 1 将区间二分得到中点 计算函数值 2 根据计算得到的函数值进行判断 如果 则方程的根为 否则判断的符号 如果其与异号 则隔根区间变为 如果其与异号 则隔根区间变为 1根的搜索与二分法 3 把新的隔根区间记为 继续按照上述规则对隔根区间进行二分 满足精度要求则停止 通过不断的二分 就得到一系列隔根区间有 由于后一区间的长度都是前一区间长度的一半 所以的长度为当时 区间的长度趋于零 即区间最终会收敛于方程的解 实际计算中 只要二分的次数足够多 可取最后区间中点作为方程根的近似值 即 1根的搜索与二分法 误差 如果事先给定精度要求为 则满足时 停止计算 1根的搜索与二分法 例 用二分法求方程在内的根的近似值 要求绝对误差不超过 解 即严格单调增加 又 所以方程在上有唯一实根 令 得到 取 即至少二分7次 计算过程如下 1根的搜索与二分法 functionf f3 x f x 3 4 x x 10 a0 1 b0 2 k 0 while1k k 1 x a0 b0 2 iff3 x f3 a0 0b0 x elsea0 x endif b0 a0 2 0 005break endendx b0 a0 2 1根的搜索与二分法 所以最后得 1根的搜索与二分法 例 用二分法求方程在内的根 要求精确到小数点后第三位小数 需要二分多少次 解 设 由于 所以在区间内方程有唯一实根 令 求得所需对分次数至少是10次 特点 运算简单 方法可靠 对函数只要求在区间上连续 但收敛速度慢 不能用来求复数根及偶数重根 常用于为其它求根方法提供较好的近似初始值 2迭代法及其迭代收敛的加速方法 迭代法 逐次逼近 基本思想 利用某种递推算式 使某个预知的近似根 初值 逐次精确化 直到得到满足精度要求的近似根 算法 给定方程 其中在有根区间上连续 设是方程的一个近似根 将方程改写为 代入初值构造迭代序列 2迭代法及其迭代收敛的加速方法 这种求方程近似根的方法称为迭代法 或简单迭代法 称为迭代函数 如果由迭代法产生的迭代序列极限存在 即 则称收敛 否则称发散 称为迭代函数的不动点 或是方程的解 由转化为时 迭代函数不是唯一的 不同 会产生不同的序列 从而收敛情况也不一样 2迭代法及其迭代收敛的加速方法 几何意义 求方程的根 在几何上就是求直线与曲线交点的横坐标 如图所示 从图中可以看出 当迭代函数的导数在根处满足不同条件时 迭代过程的收敛情况也有所不同 所以迭代过程的收敛依赖于迭代函数的构造 为使迭代法有效 必须保证其收敛性 2迭代法及其迭代收敛的加速方法 2迭代法及其迭代收敛的加速方法 2迭代法及其迭代收敛的加速方法 例 已知方程在内有一个根 用两种不同的迭代公式 1 2 进行迭代 观察所得序列的收敛性 解 计算结果如表所示 2迭代法及其迭代收敛的加速方法 x0 0 3 k 0 while1k k 1 xk 10 x0 2 公式1 xk log10 x0 2 公式2ifabs xk x0 0 0005break endx0 xk end 2迭代法及其迭代收敛的加速方法 例 对于方程 试采用如下迭代法求方程的根 1 2 3 选取初值 解 计算结果见下表 x0 1 5 k 0 while1k k 1 xk x0 6 1 公式1 发散 xk x0 1 1 6 公式2 收敛 xk 1 x0 5 1 公式3 发散ifabs xk x0 0 0005break endx0 xk end 2迭代法及其迭代收敛的加速方法 2迭代法及其迭代收敛的加速方法 迭代法收敛定理 设方程 若迭代函数在有根区间上满足 1 当时 2 在上可导 且有 则有 1 方程在上有唯一的根 2 对任意初值 迭代公式产生的数列收敛于方程的唯一根 即 3 误差估计 2迭代法及其迭代收敛的加速方法 拉格朗日中值定理 如果函数在闭区间上连续 在开区间内可导 则至少存在一点使得 2迭代法及其迭代收敛的加速方法 证明 1 根的存在性 令 则在上连续 由条件1有由连续函数的介值定理 必存在使得 即为方程的根 根的唯一性 假设另有也是方程的根 则有两式相减并应用微分中值定理得 2迭代法及其迭代收敛的加速方法 式中在和之间 所以 由条件 2 有上式不成立 所以有 2 收敛性 取时 有 由微分中值定理可知 在和之间存在使得 反复应用上述关系可得由条件 2 所以即 2迭代法及其迭代收敛的加速方法 3 误差估计 由微分中值定理 在和之间存在使得同样得到同时即因为所以反复应用 最后得到 2迭代法及其迭代收敛的加速方法 迭代次数估计 给定精度要求 即 只要从而迭代次数满足 2迭代法及其迭代收敛的加速方法 注意 由式可以看出 当越小时 序列收敛越快 只要相邻两次迭代的偏差足够小 就可以保证近似解有足够的精度 所以 常采用条件来控制迭代次数 2迭代法及其迭代收敛的加速方法 例 求方程的最大根 要求精度 解 1 求隔根区间方程变为 做和的图形 由图可知方程的最大根在区间内 2迭代法及其迭代收敛的加速方法 2 建立迭代公式 判断收敛性 方程变形为 迭代公式为在区间内可导 并且单调递增 又 所以 当时 由于 所以迭代法收敛 2迭代法及其迭代收敛的加速方法 3 迭代计算过程如下表所示 所以方程的最大根 x0 3 5 k 0 while1k k 1 xk log10 x0 7 2 ifabs xk x0 0 0001break endx0 xk end 2迭代法及其迭代收敛的加速方法 2迭代法及其迭代收敛的加速方法 定理 局部收敛性定理 设是方程的根 在的某一邻域连续 且 则必存在的一个邻域 对任意选取的初值 迭代公式产生的数列收敛于方程的根 称迭代法在的邻域具有局部收敛性 注意 在实际应用中事先不知道 因此条件无法验证 但是如果已知根的初始值在根的附近 又根据的连续性 可采用条件来代替 2迭代法及其迭代收敛的加速方法 2迭代法及其迭代收敛的加速方法 例 用迭代法求方程在隔根区间内的根 要求精确到小数点后第4位 解 1 构造迭代公式 迭代公式为 2 判断收敛性 由局部收敛性定理 所以迭代法收敛 2迭代法及其迭代收敛的加速方法 3 迭代计算过程如下表所示 2迭代法及其迭代收敛的加速方法 x0 1 5 k 0 while1k k 1 xk x0 x0 1 1 3 ifabs xk x0 0 00005break endx0 xk end 2迭代法及其迭代收敛的加速方法 用迭代法求方程根的近似值的计算步骤如下 1 准备 选定初值 确定方程的等价方程 2 迭代 按迭代公式计算出 3 判别 如果 则终止迭代计算 取作为方程的近似根 否则 转到第 2 步继续迭代计算 2迭代法及其迭代收敛的加速方法 迭代收敛的加速方法迭代 加速公式 记 则由微分中值定理有其中在和之间 设在根附近变化不大 又设 由迭代收敛条件 有上式整理为 2迭代法及其迭代收敛的加速方法 上式说明作为根的近似值时绝对误差大致为如果把该误差作为一种补偿 可以得到更好的近似值记得到迭代 加速公式 2迭代法及其迭代收敛的加速方法 例 用迭代 加速公式求在区间内的根 解 加速 迭代公式为 2迭代法及其迭代收敛的加速方法 x0 1 5 k 0 while1k k 1 xk1 x0 x0 1 1 3 xk 20 xk1 11 9 x0 11 ifabs xk x0 0 00005break endx0 xk end 3牛顿 Newton 迭代法 应用范围 用于求解高次代数方程 超越方程等非线性方程 可求方程的实根 复根 也可求单根和重根 基本思想 将非线性方程逐步转化为线性方程来进行求解 牛顿迭代法的最大优点是在方程的单根附近具有较高的收敛速度 是一种将近似根精确化的相当有效的迭代法 3牛顿 Newton 迭代法 对于非线性方程 设连续可微 将在处泰勒 Taylor 展开如果 则可在点附近取线性部分近似替代 得到的近似方程进行变换 得 3牛顿 Newton 迭代法 由迭代法思想 上式写为迭代公式的一般形式称上式为牛顿 Newton 迭代公式 其迭代函数为 3牛顿 Newton 迭代法 几何意义 3牛顿 Newton 迭代法 如图所示 假设是非线性方程在隔根区间内的根 在内可导 且对于有 任取初值 过曲线上的点作切线以其作为曲线的近似表达式 切线交轴于 则以作为方程根的第一次近似值 同理 过曲线上点做切线 3牛顿 Newton 迭代法 切线交轴于 则然后以作为方程根的第二次近似值 反复作切线 第k 1条切线方程为它与轴的交点横坐标为由此得到方程的近似根数列 几何意义即依次用切线代替曲线 用线性函数的零点作为函数零点的近似值 牛顿迭代法又称为切线法 3牛顿 Newton 迭代法 初始值的选取 定理 局部收敛性定理 设是方程的根 若 1 函数在的邻域内具有连续的二阶导数 2 在的邻域内 则存在的某个邻域 对于任意的初值 由牛顿迭代法产生的数列收敛于根 3牛顿 Newton 迭代法 证明 迭代函数的导数为由条件 1 和 2 可知 在的邻域内可导 又 所以在的某个邻域内恒有 3牛顿 Newton 迭代法 定理 非局部收敛定理 设是方程在隔根区间内的根 如果 1 对于连续且不变号 2 选取初始值 使 则由牛顿迭代公式产生的数列收敛于根 如果在上的符号不容易判断 则利用下式确定初值即如果在处 满足上式 并且 则大多数情况下可以保证牛顿迭代法是收敛的 3牛顿 Newton 迭代法 计算步骤 1 选定初值 构造迭代公式 2 迭代计算 得到 3 迭代终止判断 由迭代终止控制条件控制迭代计算是否终止 4 迭代计算终止 得到方程根的近似值 3牛顿 Newton 迭代法 例 用牛顿迭代法求方程在隔根区间内的根 要求精确到小数点后第4位小数 解 1 令 牛顿迭代公式为 2 判断收敛性所以取时满足 牛顿迭代法收敛 3牛顿 Newton 迭代法 3 计算过程如下表 x0 1 5 k 0 while1k k 1 xk 2 x0 3 x0 2 1 3 x0 2 2 x0 ifabs xk x0 0 00005break endx0 xk end 3牛顿 Newton 迭代法 3牛顿 Newton 迭代法 例 用牛顿迭代法求方程在附近的根 精确到小数点后第4位 解 所以由此成立 所以可取为初始值 迭代公式为 3牛顿 Newton 迭代法 迭代计算过程如下表所示 x0 1 k 0 while1k k 1 xk 40 x0 41 2 x0 3 1 41 x0 40 3 x0 2 ifabs xk x0 0 00005break endx0 xk end 3牛顿 Newton 迭代法 3牛顿 Newton 迭代法 例 用牛顿迭代法建立计算近似值的迭代公式 解 令 则以上问题化为求方程的正根 牛顿迭代公式为继续证明对于任意初值 上面迭代公式恒收敛 证明 对于任意有即序列有下界 3牛顿 Newton 迭代法 又即单调下降 所以迭代公式收敛 计算的近似值 的值在10 11之间 取初值 迭代公式为 3牛顿 Newton 迭代法 x0 10 C 115 k 0 while1k k 1 xk x0 C x0 2err abs xk x0 iferr 0 000005break endx0 xk end 3牛顿 Newton 迭代法 迭代计算过程如下 迭代过程的收敛速度 定义 如果从任何可取得的初始值出发 由迭代法产生的迭代序列都收敛于方程的根 则称该迭代法是大范围收敛 如果选取的初始值充分接近于方程的根 或者说存在根的某一邻域 使得在其中任意选取初始值 迭代序列都收敛于方程的根 则称该迭代法为局部收敛 一种迭代法具有使用价值 不但需要是收敛的 还要求收敛的比较快 所谓迭代过程的收敛速度 是指在接近收敛时迭代误差的下降速度 迭代过程的收敛速度 定义 设迭代法产生的数列收敛于的根 令误差 如果存在某个实数以及正常数 使则称数列是阶收敛的 相应的迭代法是阶方法 常数称为渐进误差常数 迭代过程的收敛速度 可以看出 和为同阶无穷小量 即以为基本无穷小量时 为阶无穷小量 阶数越高 收敛速度越快 收敛速度是误差的收缩率 阶数越高 误差下降的越快 当时 称数列线性收敛 当时 称数列为平方收敛 或二阶收敛 当时 称数列为超线性收敛 显然 越大 数列收敛的越快 所以迭代法的收敛阶是对迭代法收敛速度的一种度量 迭代过程的收敛速度 证明简单迭代法是线性收敛 设是方程的根 在的某一邻域连续 在邻域内有 且 则简单迭代法线性收敛 证明 设迭代过程收敛于 则式中在和之间 令 则于是迭代过程一阶收敛 线性收敛 迭代过程的收敛速度 证明牛顿迭代法平方收敛 设是在隔根区间内的根 如果 1 对于连续且不变号 2 选取初始值 使 则牛顿迭代法平方收敛 证明 将在处做泰勒展开 有式中介于之间 整理上式得 迭代过程的收敛速度 即两边取极限 并利用得所以牛顿迭代法平方收敛 4弦截法 如果函数比较复杂 求导可能比较困难 有时甚至导函数不存在 尤其是当很小时 计算中容易产生很大的误差 这时可将牛顿迭代公式中的用差商来代 即就得到求解非线性方程的弦截法 4弦截法 4弦截法 设方程的一个隔根区间为 如图所示 连结曲线上的两点得到弦AB 令 则弦AB的方程为则弦AB与轴交点的横坐标为以作为方程根的一个近似值 4弦截法 然后过曲线上的两点做弦 得到其与轴交点的横坐标为于是把作为方程根的一个新的近似值 反复做弦 得到迭代公式的一般形式为利用上述公式求方程根的近似值的方法就叫做弦截法 4弦截法 几何意义 依次用弦来代替曲线 用线性函数的零点作为函数零点的近似值 定理 弦截法收敛定理 如果在根的某个邻域内有二阶连续导数 且对任意 有 则当邻域充分小时 对邻域内任意的 由弦截法迭代公式得到的近似值序列收敛到方程的根 并可证明弦截法是按阶收敛的 4弦截法 计算步骤 1 准备 选定初始近似值 并计算 2 迭代计算 依迭代公式计算得到 并计算 3 控制 如果或 则终止迭代 否则以分别代替 转 2 继续迭代计算 弦截法和牛顿法比较 都是先把线性化 但方式不同 牛顿法用切线方程来近似代替非线性方程 而弦截法是用弦线来近似代替非线性方程 4弦截法 例 用弦截法求方程在区间内根的近似值 精确到小数点后第4位 解 令 取 弦截法迭代公式为 4弦截法 迭代计算过程如下表所示 4弦截法 x0 0 5 x1 1 k 0 while1k k 1 xk x1 exp 2 x1 x1 4 x1 x0 exp 2 x1 x1 exp 2 x0 x0 ifabs xk x0 0 00005break endx0 x1 x1 xk end 课后题 1 二分法求方程在区间内的根 要求误差不超过 2 已知方程在区间内有一根 试问用二分法求根 使其具有5位有效数字至少应二分多少次 3 判断下列方程由几个根 求出隔根区间 并写出收敛的迭代公式 1 2 5 用迭代法求的正根 要求准确到小数点后第5位 课后题 4 方程在1 5附近有根 把方程写成4种不同的等价形式 并建立相应的迭代公式 判断每种迭代公式产生的数列在1 5附近的收敛性 并用 1 的迭代公式求方程的根 要求误差不超过 课后题 6 用迭代法求方程的根 要求准确到小数点后第4位 7 用迭代 加速公式求方程在附近的根 要求准确到小数点后第4位 9 应用牛顿法于方程和 分别导出求的迭代公式 并求10 用牛顿法求方程在附近的根 要求准确到小数点后第3位 课后题 11 证明计算的牛顿迭代公式为取 计算 要求 12 用弦截法求的根 取 计算到为止 1 解 令 则所以单调增 所以在区间内单调减 又 所以方程有唯一实根 有 课后题 2 解 根的区间为 近似值具有5位有效数字 则精确到小数点后4为小数 即取 4 解 1 所以迭代公式收敛 课后题 2 收敛 3 4 利用公式 1 计算方程的根 列表如下 课后题 5 解 方程变形为 分别画出和的图形 可知交点在的范围 取 则 可知交点在的范围 所以隔根区间可取为 令 从而单调减 单调增 满足条件1 满足条件2 所以迭代公式收敛 课后题 迭代公式为 计算过程如下 课后题 6 解 1 求隔根区间方程变形为 做和的图形 由图可知 方程的根在区间内 2 建立迭代公式 判断其收敛性将方程等价变形为 迭代函数 迭代公式为 课后题 因为 当时 所以单调递减 又 所以 所以 由定理可知 迭代公式收敛 3 计算 取 列表计算 课后题 7 解 取 迭代 加速公式为 计算过程如下 课后题 9 证明 1 对于方程 牛顿迭代公式为所以 课后题 2 对于方程 牛顿迭代公式为所以 课后题 10 解 令 牛顿迭代公式为牛顿迭代公式为满足局部收敛性定理 计算过程如下表所示 课后题 11 证明 由 牛顿迭代公式为取 计算过程如下 课后题 课后题 12 解 令 满足收敛条件 取 弦截法迭代公式为计算过程如下表所示 第三章非线性方程的数值解法 主要内容 1 确定隔根区间 2 二分法 3 简单迭代法 4 迭代收敛的加速方法 5 牛顿迭代法 6 弦截法 7 迭代法的收敛阶 第三章非线性方程的数值解法 二分法 迭代法收敛定理 设方程 若迭代函数在有根区间上满足 1 当时 2 在上可导 且有 则有 1 方程在上有唯一的根 2 对任意初值 迭代公式产生的数列收敛于方程的唯一根 即 3 误差估计 第三章非线性方程的数值解法 第三章非线性方程的数值解法 定理 局部收敛性定理 设是方程的根 在的某一邻域连续 且 则必存在的一个邻域 对任意选取的初值 迭代公式产生的数列收敛于方程的根 称迭代法在的邻域具有局部收敛性 第三章非线性方程的数值解法 迭代 加速公式 牛顿迭代法 第三章非线性方程的数值解法 初始值的选取 定理 局部收敛性定理 设是方程的根 若 1 函数在的邻域内具有连续的二阶导数 2 在的邻域内 则存在的某个邻域 对于任意的初值 由牛顿迭代法产生的数列收敛于根 第三章非线性方程的数值解法 定理 非局部收敛定理 设是方程在隔根区间内的根 如果 1 对于连续且不变号 2 选取初始值 使 则由牛顿迭代公式产生的数列收敛于根 如果在上的符号不容易判断 则利用下式确定初值即如果在处 满足上式 并且 则大多数情况下可以保证牛顿迭代法是收敛的 第三章非线性方程的数值解法 二分法 由公式有取 即采用二分法求解 得到满足精度要求的根需要二分13次 第三章非线性方程的数值解法 简单迭代法 方程变形为而即迭代函数单调减 又 所以单调减 所以所以在区间上迭代法收敛 取初始值 第三章非线性方程的数值解法 迭代计算过程如下表所示 第三章非线性方程的数值解法 迭代 加速公式 取 公式为取初始值 第三章非线性方程的数值解法 迭代计算过程如下表所示 第三章非线性方程的数值解法 牛顿迭代法 当时 不变号 又 所以取 迭代公式为 第三章非线性方程的数值解法 迭代计算过程如下表所示 总结 1 对非线性方程求根 首选要对的性态及根的近似位置有一个大致了解 使用较小的有根区间把方程的根分离出来 2 简单迭代法是一种逐次逼近的方法 需要判断收敛性 了解收敛速度 可以采用加速公式 3 牛顿迭代法是最常用的一种迭代方法 具有二阶收敛速度 但是对初值的选取比较苛刻 需要靠近方程的根 否则可能不收敛 4 弦截法是牛顿迭代法的一种修改 虽然收敛速度较牛顿法慢 但不需要计算导数 使用更加方便 同样要求初始值的选取比较靠近方程的根 第三章非线性方程的数值解法