5430人阅读
数据结构与算法（22）
& & & &牛顿迭代法（Newton’s method）又称为牛顿-拉夫逊（拉弗森）方法（Newton-Raphson method），它是牛顿在17世纪提出的一种在实数域和复数域上近似求解方程的方法。
& & & &既然牛顿迭代法可以用来求解方程的根，那么不妨以方程 x2=n 为例，来试着求解它的根。为此。令f(x)=x2-n， 也就是相当于求解 f(x)=0 的解，如上图所示。
& & & &首先随便找一个初始值
x0不是解，做一个经过 (x0,f(x0)) 这个点的切线，与x轴的交点为x1。同样的道理，如果 x1不是解，做一个经过(x1,f(x1))这个点的切线，与x轴的交点为x2。 以此类推。以这样的方式得到的xi会无限趋近于 f(x)=0 的解。
判断xi是否是f(x)=0的解有两种方法： 一是直接计算f(xi)的值判断是否为0，二是判断前后两个解xi和xi-1是否无限接近。
经过(xi,f(xi))这个点的切线方程为f(x)=f(xi)+f′(xi)(x-xi)其中，f′(x)为f(x)的导数，本题中为2x。令切线方程等于 0，即可求出xi+1=xi-f(xi)f′(xi)
xi+1=xi-x2i-n2xi=xi-xi2+n2xi=xi2+n2xi
基于上述迭代公式，我们其实给出了一个求平方根的算法。事实上，这也的确是很多语言中内置的开平方函数的实现方法。
Leetcode上也有一道经典面试题目涉及到开平方函数的实现，如下
基于我们已经给出的牛顿迭代法，下面就可来编程解决该问题了，示例代码如下
class Solution {
int mySqrt(int x) {
if (x ==0)
double cur = 1;
cur = x / (2 * pre) + pre / 2.0;
} while (abs(cur - pre) & 0.00001);
return int(cur);
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：1898570次
积分：24574
积分：24574
排名：第265名
原创：319篇
转载：15篇
评论：3908条
《图像处理中的数学修炼》
图像处理书籍读者群（）非本书读者勿扰，本群谢绝吃瓜群众围观。唯有看书本身能使你提高，只加群而不学习将毫无意义。而看书学习是自己的事，别人不会因为你不学习而受损
1. 在博客文章下留言，博客私信一律不回。
2. 邮件，将#换成@。
3. 算法与数据结构QQ群：，仅限算法之美读者交流之用。
文章：13篇
阅读：40114
文章：44篇
阅读：352308关于牛顿迭代法的课程设计实验指导；非线性方程（或方程组）问题可以描述为求x使得f(；一、牛顿迭代法及其收敛速度；牛顿迭代法又称为牛顿-拉夫逊方法（Newton-；x0做初始近似值，使用函数f(x)在x0处的泰勒；处局部线性化计算出x2，求得近似解x2，??；详细叙述如下：假设方程的解x在x0附近（x0是*；方程解x的近似），函数f(x)在点x0处的局部线；f
关于牛顿迭代法的课程设计实验指导
非线性方程（或方程组）问题可以描述为求 x 使得f(x) = 0。在求解非线性方程的方法中，牛顿迭代法是求非线性方程（非线性方程组）数值解的一种重要的方法。牛顿是微积分创立者之一，微积分理论本质上是立足于对世界的这种认识：很多物理规律在微观上是线性的。近几百年来，这种局部线性化方法取得了辉煌成功，大到行星轨道计算，小到机械部件设计。牛顿迭代法正是将局部线性化的方法用于求解方程。 一、牛顿迭代法及其收敛速度 牛顿迭代法又称为牛顿-拉夫逊方法（Newton-Raphson method），是一种在实数域和复数域上通过迭代计算求出非线性方程的数值解方法。方法的基本思路是利用一个根的猜测值x0做初始近似值，使用函数f(x)在x0处的泰勒级数展式的前两项做为函数f(x)的近似表达式。由于该表达式是一个线性函数，通过线性表达式替代方程f(x) = 0中的f(x)求得近似解x1。即将方程f(x) = 0在x0处局部线性化计算出
y 近似解x1，重复这一过程，将方程f(x) = 0在x1 处局部线性化计算出x2，求得近似解x2，??。 *详细叙述如下：假设方程的解x在x0附近（x0是 *方程解x的近似），函数f(x)在点x0处的局部线化 表达式为 f(x)?f(x0)?(x?x0)f?(x0)
x0 由此得一次方程 f(x0)?(x?x0)f?(x0)?0 求解，得 x1?x0?f(x0)f?(x0)图1 牛顿迭代法示意图
如图1所示，x1比x0更接近于x*。该方法的几何意义是：用曲线上某点（x0，y0）的切线代替曲线，以该切线与x轴的交点（x1，0）作为曲线与x轴的交点（x*，0）的近似（所以牛顿迭代法又称为切线法）。设xn是方程解x的近似，迭代格式 f(xn)xn?1?xn?
( n = 0，1，2，??) ?f(xn)就是著名的牛顿迭代公式，通过迭代计算实现逐次逼近方程的解。牛顿迭代法的最大优点是收敛速度快，具有二阶收敛。以著名的平方根算法为例，说明二阶收敛速度的意义。 例1．已知2?1.4，求2等价于求方程f(x) = x2 C 2 = 0的解。由于f?(x)?2x。应用牛顿迭代法，得迭代计算格式 xn?1?12(xn?2/xn)，（n = 0，1，2，??） *取x0= 1.4为初值，迭代计算3次的数据列表如下 表1 牛顿迭代法数值实验 迭代次数 近似值 15位有效数 0 1 2 3 1.4 1.71 1.56 1.09 误差 1.10 -1.42e-002 1.10 7.21e-005 1.10 1.84e-009 1.10 -2.22e-016 其中，第三栏15位有效数是利用MATLAB的命令sqrt(2)计算结果。观察表中数据，第一次迭代数据准确到小数点后四位，第二次迭代数据准确到小数点后八位，??。二阶收敛速度可解释为，每迭代一次，近似值的有效数位以二倍速度递增。对于计算任意正数C的平方根，牛顿迭代法计算同样具有快速逼近的性质。 二、牛顿迭代法的收敛性 牛顿迭代法在使用受条件限制，这个限制就是通常所说的牛顿迭代法的局部收敛性。 定理
假设f(x)在x*的某邻域内具有连续的二阶导数，且设f(x*)=0，f?(x*)?0，则**对充分靠近x的初始值x0，牛顿迭代法产生的序列{xn}收敛于x。 下面例子是牛顿迭代法不收敛的反例。反例说明，牛顿迭代法局部收敛性要求初始点要取得合适，否则导致错误结果。 3例2用牛顿迭代法解方程 f(x) = x C x C 3 = 0。 分析：利用MATLAB求多项式零点命令roots(p)，计算得三次方程的三个根如下表 表2 三次方程的三个根 r1 r2 r3 1.8 - 1.0469i
-0.8358 + 1.0469i 显然，三次方程有一个实根r1。 为了使用牛顿迭代法计算，对于 f(x) = x3 C x C 3 ，首先求导数，得f?(x)?3x?1。取x0 = 0和x0 = 1取分别用牛顿迭代法计算，得 表3 不同初始值的迭代计算结果 0 1 x0 -3.0 x1 -1.6 x2 -1.9 x3 -0.6 x4 -3.7 x5 -1.7 x6 ?? ?? ?? 对于迭代初值取x0=0，迭代数列中的第四项又回到初始点x0 = 0附近，算法将陷入死循环。
y=x C x C 3
3图2 牛顿迭代法初值不收敛示意图 而迭代初值取x0=1，可以使牛顿迭代法得到收敛。 三、特殊代数方程的牛顿迭代法收敛区域
将牛顿迭代法用于求解高阶代数方程时，首先回顾一个代数基本定理，即“一个n阶多项式在复数域内有n个根”。根据牛顿迭代法的局部收敛性质，任意取一个数据做为牛顿迭代的初值，可能导致迭代不收敛，即使这一个初值可以使迭代法收敛，下一个有趣的问题是“迭代序列将收敛于哪一个根”，其规律如何？ 3例3牛顿迭代法的收敛区域问题：Newton迭代法可以用于求解复数方程 z C 1 = 0，该方程在复平面上三个根分别是 z1?1，z2??12?32i，z3??12?32i 选择中心位于坐标原点，边长为4的正方形内的任意点作初始值，进行迭代，将不收敛的点定义为第一类，给它们标一种颜色；再把收敛到三个根的初值分为三类，并分别标上不同颜色。对充分多的初始点进行实验，绘出牛顿迭代法对该方程的收敛域彩色图。
图3 牛顿迭代法收敛区域色图 问题分析：记f(z) = z3 C 1，则f?(z)?3z2，所以牛顿迭代公式为 zn?1?zn?(zn?1/zn)/3 2由于牛顿迭代法的二阶收敛速度，对于一个取定的初值z0，如果z0是一个可以导致迭代收敛的初值，则迭代10次已经达到足够精度，故可以取迭代次数为10。考虑以坐标原点为中心的正方形区域 ??{(x,y)|?2?x?2,?2?y?2} 取步长h=0.02，在区域内取离散网格点 ?xj??2?j?h，( j，k =0，1，?，200) ?y??2?k?h?k由此可以构造出规则的复数 zjk = xj + i yk，( j，k =0，1，?，200) 对于这些点，逐一用牛顿迭代法取初值进行迭代实验，判断是否收敛？如果收敛，到底以该点为初值的迭代序列收敛到哪方程的一个根？ 为了记录实验结果，构造四个阶数均为201×201矩阵：Z0、Z1、Z2、Z3，开始时这四个矩阵都设为全零矩阵。如果以zjk为初值的迭代实验结果是不收敛，则将Z0的第j行第k列的元素改写为1；如果以zjk为初值的迭代实验结果是收敛到第一个根，则将Z1的第j行第k列的元素改写为1；如果以zjk为初值的迭代实验结果是收敛到第二个根，则将Z2的第j行第k列的元素改写为1；如果以zjk为初值的迭代实验结果是收敛到第三个根，则将Z3的第j行第k列的元素改写为1。 首先分析矩阵Z0的数据，由于该矩阵在开始时刻为全零矩阵，而在迭代实验结束后，不收敛的点对应元素被改写为“1”。所以，矩阵的元素只可能是“0”或“1”，根据该矩阵的全部的非零元素所在的位置可以使用MATLAB的图形绘制命令spy()或pcolor()等显示出一个特殊的图形。根据Z0数据绘的图形如下所示
图4 牛顿迭代法不收敛区域色图 导致牛顿迭代法不收敛的初始点所形成的平面点集是一个著名的集合，称为茹莉亚集（为纪念法国女数学家茹莉亚而命名）。 为了得到全局的收敛或不收敛情况，需要对四个矩阵进行叠加。如果直接相加将导致一个全“1”矩阵，不可能得出希望的结果。故，对矩阵做如下组合处理，令 Z = Z0 + 2Z1 + 3Z2 + 4Z3 则矩阵Z的元素由“1”、“2”、“3”、“4”这四个元素组成。该矩阵的某一位置上数据为“1”，说明这一位置上的复数做初值导致牛顿迭代法不收敛；位置上数据为“2”，说明这一位置上的复数做初值导致牛顿迭代法收敛到第一个根；位置上数据为“3”，说明这一位置上的复数做初值导致牛顿迭代法收敛到第二个根；位置上数据为“4”，说明这一位置上的复数做初值导致牛顿迭代法收敛到第三个根。所以该矩阵包含了矩阵区域内离散点集合做为牛顿迭代法收敛实验结果的全部信息。将这一矩阵用MATLAB作图命令pcolor()作用，将绘出图3所示的收敛区域色图。 导致牛顿迭代法收敛到第一个根的初始点所形成的平面点集，可以根据Z1数据绘图形
四、关于实验的注记 1．MATLAB相关命令介绍 （1）求多项式零点命令roots() 该命令用于求多项式P(x) = a1xn + a2 xn-1 + ? + anx + an+1的全部零点。例如z3 C 1 = 0的三个零点，只需用命令：roots([1 0 0 -1])，可得 ans =
-0.5000 + 0.8660i
-0.5000 - 0.8660i
（2）绘伪彩色图命令pcolor() 该命令主要用于绘制矩阵色图，根据矩阵中元素数据的大小不同绘不同颜色。常常与命令shading interp结合使用效果会更好。 在 MATLAB命令窗口中键入help pcolor，可获得英文帮助信息。 2． 例题3所用MATLAB程序及注释： X=roots([1,0,0,-1]);
%利用MATLAB命令求三次方程的根 r1=X(1);r2=X(2);r3=X(3); h=0.02;N=1+4/h;
%确定网格步长及网格点规模 z0(N,N)=0;z1=z0;z2=z0;z3=z0;
%定义四个大矩阵为全零矩阵 t=(-2:h:2)+ [x,y]=meshgrid(t);
%确定网格点坐标 z=x+y*i; for j=1:N
%提取迭代初始点
for n=1:10
p=p-(p-1/p^2)/3;
%牛顿迭代操作
if abs(p-r1)<0.01
z1(j,k)=1;
%确定收敛到第一个根的初始点
elseif abs(p-r2)<0.01
z2(j,k)=1;
%确定收敛到第二个根的初始点
elseif abs(p-r3)<0.01
z3(j,k)=1;
%确定收敛到第三个根的初始点
z0(j,k)=1;
%确定不收敛的初始点
end end Z=z0+2*z1+3*z2+4*z3; figure(1) pcolor(x,y,Z),shading interp
%绘牛顿迭代法收敛域 figure(2) pcolor(x,y,z0),shading interp
%绘牛顿迭代法不收敛域
课程设计实验题目 1．牛顿迭代法解复方程z n + 1 = 0的收敛域问题。 了解Newton迭代法解复方程z n + 1 = 0(n≥3)时收敛域的结构。 实验原理： Newton迭代法可以用于求解复数方程z n + 1 = 0，例如对 z6 + 1 = 0，该方程在复平面上六个根分别是 z1??32?12i，z2??32?1232?12i，z3?i， 32?12i 实验目的： z4??i，z5?i，z6?选择中心位于坐标原点，边长为4的正方形内的任意点作初始值进行迭代，将不收敛的初值点归为第一类，再把收敛到六个根的初值归为另外六类，分别以不同颜色做图。对充分多的初始点进行实验，绘出牛顿迭代法对该方程的收敛域彩色图。 2．牛顿迭代法计算隐函数值实验 实验目的： 了解隐函数存大定理与牛顿迭代法之间的联系。 实验原理： 隐函数存在定理叙述为：如果f(x，y)及fy?(x,y)皆在（x0，y0）附近连续，而且 f(x0，y0) = 0，fy?(x0,y0)?0 则在（x0，y0）的附近，方程f(x，y) = 0恰有一个连续解y =y(x)。 隐函数存在定理具有局部性，这种局部性与牛顿迭代法的局部收敛性有相通之处。在邻域 ?(x0，y0) =?(x0)×?(y0)={(x，y) | |x C x0| < ?，|y C y0| < ? } 内计算隐函数的值。取x1∈?(x0)={x | |x C x0| < ? }，存在y1∈?(y0)={y | |y C y0| < ? }，使得y1 =y(x1)满足f(x1，y1) = 0。由此导出关于函数值y的一元非线性方程 g(y) = f(x1，y) = 0 由于f(x，y)及fy?(x,y)皆在?(x0，y0)连续，故fy?(x1,y1)?0，且y1≈y0。应用牛顿迭代法，得迭代计算格式 迭代初值取为：y(0) = y0。由牛顿迭代法的局部收敛性可知，迭代计算可求得隐函数的高精度函数值。将这一过程进行下去可计算出一系列的函数值并制做出函数表。 例如对于二元多项式函数G(x，y) = 3x7 + 2y2 C x3 + y C 3，方程G(x，y)=0定义了隐函数y =y(x)。当x=0时，有y=0。应用牛顿迭代法，从x= 0开始，以0.1为步长依次进行到y (k+1)= y (k) C f(x1，y (k) )/fy(x1，y (k)) x=4为止。 3．牛顿迭代法计算矩阵近似逆。 实验目的： 了解矩阵近似逆的迭代计算过程。 实验原理： 设A 为主对角严格占优矩阵，求A-1 的牛顿迭代公式为：Xn+1 = Xn(2I CAXn )，迭代计算的收敛要求为初值满足条件：|| I C A X0 || < 1。
附：牛顿迭代法课程设计实验报告格式 实验名称： 姓名（学号）： 一、问题叙述 二、问题分析 三、实验程序及注释 四、实验数据结果及分析 五、实验结论 三亿文库包含各类专业文献、行业资料、专业论文、各类资格考试、应用写作文书、幼儿教育、小学教育、高等教育、关于牛顿迭代法的课程设计实验指导02等内容。　
　牛顿迭代法实验报告_数学_自然科学_专业资料。用牛顿迭代法求方程的根一、 实验目的 1. 用牛顿迭代法求解方程的根 2. 了解迭代法的原理 3. 改进和修缮迭代法 ... 　关于牛顿迭代法的课程设... 6页 免费 牛顿迭代法...牛顿迭代法实验报告 1.功能 . 本程序采用牛顿法,...2014年执业医师考试指导 口腔执业医师实践技能复习资料... 　关于牛顿迭代法的课程设计实验指导非线性方程(或方程组)问题可以描述为求 x 使得 f(x) = 0。在求解非线性方程的方 法中,牛顿迭代法是求非线性方程(非线性方程... 　牛顿迭代法实验报告_数学_自然科学_专业资料 暂无评价|0人阅读|0次下载|举报文档 牛顿迭代法实验报告_数学_自然科学_专业资料。今日推荐 ... 　实验报告 实验名称 课程名称 姓名 1C26217 计算方法 牛顿迭代法求根 指导老师 学号评分 实验地点 实验日期 一、实验题目 1.了解牛顿迭代法的含义,方法和特点。 2... 　学习非线性方程求根的方法及程序设计算法 2)实验题目 1、迭代函数对收敛性的...关于牛顿迭代法的课程设... 6页 免费 牛顿迭代法的实验报告 3页 免费 实验15... 　《数值分析》课程实验报告 用二分法和牛顿迭代法求方程的根 算法名称 用二分法和...(x)=0 无解析解,但如果对任意 的精度要求,设计迭代方程,数值计算出方程的... 　一、牛顿―迭代法迭代程序 1.M 文件 function [p0,err,k,y]=newton(f,df,p0,delta,epsilon,max1) %Input - f is the object function input as a ...求助 关于 二分法 迭代法 牛顿迭代法【高等数学吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：239,927贴子：
求助 关于 二分法 迭代法 牛顿迭代法收藏
鄙人作业需要自己找到一个方程且可以同时用二分法 迭代法 牛顿迭代法求解。 小人不才 绞尽脑汁想出一个 最后还卡在了迭代法上.望数学吧的各位大神 能帮忙提供一个一元五次方程能同时运用在此三个解法上.谢谢 拜托了
自考高等数学一资料一览,江苏16月自考招生简章,新生报名须知.自考高等数学一资料:自考注册,自考流程,自考政策.详情点击&&
王守仁。。。还没学到捏
登录百度帐号推荐应用求牛顿迭代法的有关问题【数学吧】_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：426,649贴子：
求牛顿迭代法的有关问题收藏
牛顿迭代法怎么解出复根额？求根轨迹解点常用到。。知道的朋友告诉我下
翡翠原石:购买、加盟、批发-高货翡翠原石尽在鑫劦飞翡翠年代翡翠原石集团
跟实根一样地求
如果在虚根处迭代收敛的话,以一个靠近此虚根的初值直接迭代就行了.
登录百度帐号推荐应用}