《各种计算方法》由会员分享，可在线阅读，更多相关《各种计算方法（28页珍藏版）》请在金锄头文库上搜索。
1、各种计算方法,信息学院 熊波,算法重在设计,所谓算法就是计算机上使用的计算方法 众所周知，行列式解法的Gramer(格莱姆)法则原则上可以用来求解线性方程组。用这种方法求解一个n阶方程组，要算n+1个n阶行列式的值,这个计算量是相当惊人的！,比如一个20阶的方程组，用巨型计算机来计算，要连续工作100年，这是完全没有实际意义的，而运用消元技术，一个20阶的线性方程组用普通的计算器也能很快地解出来。因此合理地选择算法是科学计算成败的关键,数学思维的化归策略,算法设计的基础是数学思维 数学家的思维特征：将问题加工变形，直到把它转化归纳为能够解决的问题化归策略,例1：提供水龙头、水壶、煤气灶与火柴，
2、怎样烧开水？烧开水程序分三步打开水龙头将水壶灌满用火柴点燃煤气灶把水壶放在煤气灶上,问题2： 所给条件与1相同，只是水壶已经装满了水，这是该怎样烧开水呢？,根据生活经验，这个问题比1简单，只用执行2、3步即可,但是数学家的思维方式，解决2更“合理”的方案是：先倒掉壶中的水，将问题2化归为问题1，再按1的方案进行,化归策略是算法设计的基本策略,一 方程求根的迭代方法,1 求开方值的迭代公式,相对于加减乘除四则运算来说，开方运算无疑是复杂的。人们自然希望将复杂的开方运算化归为四则运算,给定 ，求开方值 的问题转化为解方程,设给定某个预报值 ，希望借助于某种简单方法确定校正量 ，使校正值 能够比较准
3、确地满足所给方程,假设 是个小量，为简化计算舍去高阶小量 ，令,这是一个关于 的一次方程，据此求出 ，从而得到,反复施行上述过程，即可导出开方公式,从给定的某个初值 出发，利用上式反复迭代，即可获得满足精度要求的开方值,算法：任给 ，对 ，执行算式（1），直到偏差 为止（ 为给定精度），最终获得的近似值 即为所求,例：用开方算法求 ，设取,解： 的准确值为 ，这里迭代5次得到的结果,开方公式规定了预报值 与校正值 之间的一种函数关系 ，这里称为开方法的迭代函数,开方法的收敛性：,定理：开方法对任意给定初值 均收敛,2 NEWTON法,考虑一般形式的函数方程,设已知它的近似根 ，则自然要求校正值
4、 能更好的满足所给方程(2),取其线性主部 ，令,NEWTON迭代的思想是：,将非线性方程的求根过程线性化,NEWTON公式确定了预报值 与校正值 之间的一种函数关系 ，这里迭代函数为,Newton法的几何解释：,方程 的根 在几何上解释为曲线 与 轴交点的横坐标。设 是根 的某个近似值，对曲线 上横坐标为 的点 引切线，设该切线与 轴交点的横坐标记为 ，则这样获得的 即为按Newton法求得的近似根。由于这种几何背景Newton法亦称为切线法,Newton法的计算流程,开方法是Newton法的特殊情况,求开方值 就是求解方程,Newton法的迭代函数为,就是开方法的迭代函数,定义：如果迭代误
5、差 当 时成立 则称迭代过程是 阶收敛的,压缩映象原理,对于一般方程 ，为要使用迭代法，先将它改写成的形式，其中 为迭代函数，若据此建立迭代过程收敛，则极限值 显然就是所给方程 的根。,问题：怎样的迭代函数才能保证迭代过程收敛？,压缩映象原理：设 在 上具有连续的一阶导数，且满足以下两项条件：1 封闭性条件 对于任意 总有 ；2 压缩性条件 存在定数 ，使对于任意 成立则迭代过程 对任意初值 均收敛于方程 的根，且有下列误差估计式,定理给出了迭代过程收敛的条件，并且说明了可以用偏差 来控制迭代过程是否应该结束,同时定理要求迭代函数 在区间 内一致地满足压缩性条件，这项要求很苛刻，实际应用时很难
6、满足,定义：称一种迭代过程在根 邻近收敛，如果存在邻域 ，使迭代过程对于任意初值 均收敛,这种在根的邻近具有的收敛性称作局部收敛性,定理：设 在 的根 邻近有连续的一阶导数，且成立则迭代过程 在 邻近具有局部收敛性,局部收敛要求所选取的初值足够精确,定理：Newton法在 的单根 邻近为平方收敛,Newton法是方程求根的核心算法，它逻辑结构简单，并且收敛速度很快。不过Newton法也存在缺陷与不足：它仅有局部收敛性，如果初值选取不当，Newton法可能失效；此外，Newton法的每一步要求计算导数值 ，如果函数比较复杂，提供导数往往是困难的。因此Newton法有必要改进,3 Newton法的
7、改进与变形,（1）Newton下山法,针对Newton法对初值的依赖性，如果 偏离 较远，Newton法可能发散,为了防止迭代发散，通常对迭代过程附加一项要求，即保证函数值单调下降满足这种要求的算法称为下山法,将Newton法与下山法结合起来用，即在下山法保证函数值稳定下降的前提下，用Newton法加快收敛速度，称为Newton下山法,具体实施方法：,将Newton法的计算结果与前一步的近似值 加权平均作为新的改进值或者说采用迭代公式其中， 为下山因子，适当选取下山因子，使单调性条件成立。,下山因子的选择是逐步探索的过程，从 开始反复将 的值减半试算，一旦单调性条件成立，则“下山成功”,（2）
8、 弦截法,针对导数 计算困难的问题,为避开导数的计算，改用差商 替换Newton公式中的导数 ，即得到下列迭代公式,弦截法为线性收敛,弦截法的几何解释,记曲线 上横坐标为 的点为 ，则差商 表示弦线 的斜率。迭代公式求出的 实际上是弦线 与 轴的交点,（3）快速弦截法,为提高弦截法的收敛速度，再改用差商 替代Newton公式中的导数，得到如下迭代公式这种迭代法称为快速弦截法,快速弦截法虽然提高了收敛速度，但它也为此付出了“沉重”的代价：它在计算 时要用到前两步的信息 ，这种迭代法为两步法，在计算前必须先提供两个开始值,二 线性方程组的迭代法,借助于矩阵和向量的符号，线性方程组可以简单的表达为其中,线性方程组求解的难易程度取决于其系数矩阵的复杂程度,Jacobi迭代的设计思想是将所给的线性方程组逐步地对角化,1 Jacobi迭代,首先考察三阶方程组,令其左端仅保留对角成分，而将其余部分挪到右端，将方程改写成伪对角形式,根据这一等价形式设计出迭代法,它可以理解为关于迭代值 的对角方程组，其求解公式,称为Jacobi公式,
