牛顿法
迭代公式：(1)2()1()[()]()k k k k x x f x f x +-=-??
Matlab 代码：
function [x1,k] =newton(x1,eps)
hs=inline('(x-1)^4+y^2'); 写入函数
ezcontour(hs,[-10 10 -10 10]); 建立坐标系
hold on; 显示图像
syms x y 定义变量
f=(x-1)^4+y^2; 定义函数
grad1=jacobian(f,[x,y]); 求f 的一阶梯度
grad2=jacobian(grad1,[x,y]); 求f 的二阶梯度
k=0; 迭代初始值
while 1 循环
grad1z=subs(subs(grad1,x,x1(1)),y,x1(2)); 给f 一阶梯度赋初值 grad2z=subs(subs(grad2,x,x1(1)),y,x1(2)); 给f 二阶梯度赋初值 x2=x1-inv(grad2z)*(grad1z)'; 核心迭代公式
if norm(x1-x2) break; else plot([x1(1),x2(1)],[x1(2),x2(2)],'-r*'); 画图 k=k+1; 迭代继续 x1=x2; 赋值 end end end 优点：在极小点附近收敛快 缺点：但是要计算目标函数的hesse 矩阵 最速下降法 1. ：选取初始点xo ，给定误差 2. 计算一阶梯度。若一阶梯度小于误差，停止迭代，输出 3. 取()()()k k p f x =? 4. 10 t ()(), 1.min k k k k k k k k k k t f x t p f x tp x x t p k k +≥+=+=+=+进行一维搜索，求，使得令转第二步 例题： 求min (x-2)^4+(x-2*y)^2.初始值（0,3）误差为0.1 (1)编写一个目标函数，存为f.m function z = f( x,y ) z=(x-2.0)^4+(x-2.0*y)^2; end (2)分别关于x 和y 求出一阶梯度，分别存为fx.m 和fy.m function z = fx( x,y ) z=2.0*x-4.0*y+4.0*(x-2.0)^3; end 和 function z = fy( x,y ) z=8.0*y-4.0*x; end （3）下面是脚本文件，一维搜索用的是黄金分割法Tic 计算时间 eps=10^(-4);误差 err=10; dt=0.01; x0=1.0;初始值 y0=1.0; mm=0; while err>eps 黄金分割法 dfx=-fx(x0,y0); dfy=-fy(x0,y0); tl=0;tr=1;确定一维搜索的区间 h=3; nn=0; gerr=10; geps=10^(-4); while gerr>geps tll=tl+0.382*abs(tr-tl); trr=tl+0.618*abs(tr-tl); if f(x0+tll*h*dfx,y0+tll*h*dfy)>f(x0+trr*h*dfx,y0+trr*h*dfy) tl=tll; else tr=trr; end gerr=abs(tl-tr); 区间的长度之差 tt=0.5*(tl+tr); nn=nn+1;步数增加 if nn>200 迭代终止条件 break end end x0=x0+tt*h*dfx; 重新迭代 y0=y0+tt*h*dfy; err=sqrt(fx(x0,y0)^2+fy(x0,y0)^2); mm=mm+1;步数增加 if mm>700 迭代步数超过700，终止 break end end res=[x0,y0];输出最后的x，y。 toc 计算运行时间 拟牛顿法（DFP 算法） 220'412010min ()4,(1,1),,1001f x x x x H ε-??=+=== ??? 取 这是一个脚本文件可以直接运行 syms x1 x2;定义变量 eps=0.00001; x0=[1,1]';初始值 h0=[1,0;0,1]; f=x1^2+4*x2^2;待求函数 fx=diff(f,x1);对x求导 fy=diff(f,x2);对y求导 df=[fx,fy];f的一阶梯度 dfx0=[subs(fx,[x1,x2],x0),subs(fy,[x1,x2],x0)]';赋初值 d0=-dfx0;搜索方向 n=1; while 1 syms t; s0=x0+t*d0;引入变量t ff=subs(f,[x1,x2],s0)给f赋值; t=solve(diff(ff));求ff的极小点 xx1=x0+t*d0;更新初始值 dfx1=[subs(fx,[x1,x2],xx1'),subs(fy,[x1,x2],xx1')]';赋值 pp=sqrt(dfx1*dfx1');判断此时一阶梯度的值 if(pp<0.001)迭代终止条件 break end a1=xx1-x0; r1=dfx1-dfx0; h1=h0+(a1*a1')/(a1'*r1)-(h0*r1*r1'*h0)/(r1'*h0*r1);h0的更新d1=-h1*dfx1;搜索方向的更新 d0=d1;循环赋值 牛顿插值法 插值法是利用函数f (x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f (x)的近似值。如果这特定函数是多项式，就称它为插值多项式。当插值节点增减时全部插值基函数均要随之变化，这在实际计算中很不方便。为了克服这一缺点，提出了牛顿插值。牛顿插值通过求各阶差商，递推得到的一个公式： f(x)=f[x0]+f[x0,x1](x-x0)+f[x0,x1,x2](x-x0)(x-x1)+...f[x0,...xn](x-x0 )...(x-xn-1)+Rn(x)。 插值函数 插值函数的概念及相关性质[1] 定义：设连续函数y-f(x) 在区间[a,b]上有定义，已知在n+1个互异的点 x0,x1,…xn上取值分别为y0,y1,…yn （设a≤ x1≤x2……≤xn≤b)。若在函数类中存在以简单函数P(x) ，使得P(xi)=yi,则称P(x) 为f(x)的插值函数. 称x1,x2,…xn 为插值节点，称[a,b]为插值区间。 定理：n次代数插值问题的解存在且唯一。 牛顿插值法C程序 程序框图#include matlab实现牛顿迭代法求解非线性方程组 已知非线性方程组如下 3*x1-cos(x2*x3)-1/2=0 x1^2-81*(x2+0.1)^2+sin(x3)+1.06=0 exp(-x1*x2)+20*x3+(10*pi-3)/3=0 求解要求精度达到0.00001 ———————————————————————————————— 首先建立函数fun 储存方程组编程如下将fun.m保存到工作路径中: function f=fun(x); %定义非线性方程组如下 %变量x1 x2 x3 %函数f1 f2 f3 syms x1 x2 x3 f1=3*x1-cos(x2*x3)-1/2; f2=x1^2-81*(x2+0.1)^2+sin(x3)+1.06; f3=exp(-x1*x2)+20*x3+(10*pi-3)/3; f=[f1 f2 f3]; ———————————————————————————————— 建立函数dfun 用来求方程组的雅克比矩阵将dfun.m保存到工作路径中: function df=dfun(x); %用来求解方程组的雅克比矩阵储存在dfun中 f=fun(x); df=[diff(f,'x1');diff(f,'x2');diff(f,'x3')]; df=conj(df'); ———————————————————————————————— 编程牛顿法求解非线性方程组将newton.m保存到工作路径中: function x=newton(x0,eps,N); con=0; %其中x0为迭代初值eps为精度要求N为最大迭代步数con用来记录结果是否收敛for i=1:N; f=subs(fun(x0),{'x1' 'x2' 'x3'},{x0(1) x0(2) x0(3)}); df=subs(dfun(x0),{'x1' 'x2' 'x3'},{x0(1) x0(2) x0(3)}); x=x0-f/df; for j=1: length(x0); il(i,j)=x(j); end if norm(x-x0) 西京学院数学软件实验任务书 实验五实验报告 一、实验名称：最速下降法与共轭梯度法解线性方程组。 二、实验目的：进一步熟悉理解掌握最速下降法与共轭梯度法解法思路，提高matlab 编程能力。 三、实验要求：已知线性方程矩阵，应用最速下降与共轭梯度法在相关软件编程求解线性方程组的解。 四、实验原理： 1．最速下降法： 从某个初始点)0(X 出发，沿)(X f 在点)0(X 处的负梯度方向 )0()0()0()(AX b X f r -=-?= 求得)(X f 的极小值点)1(X , 即 )(min )0()0(0 r X f λλ+> 然后从)1(X 出发，重复上面的过程得到)2(X 。如此下去，得到序列{)(k X } )(...)()()()1()0(k X f X f X f >>> 可以证明，从任一初始点)0(X 出发， 用最速下降法所得到的序列{)(k X }均收敛于问题使X 最小化)(X f 的解，也就是方程组b AX =的解。其收敛速度取决于 1 1 λλλλ+-n n ，其中1λ ,n λ分别 为A 的最小,最大特征值。最速下降法迭代格式：给定初值)0(X ， )(k X 按如下方法决定： ()) ()(1)(k )()()()(k ) ()(X ,,)(k k k k T k k T k k k k r X Ar r r r AX b X f r λλ+=> <><=-=-?=+ 2．共轭梯度法 其基本步骤是在点)(k X 处选取搜索方向)(k d , 使其与前一次的搜索方向)1(-k d 关于A 共轭，即 (1)()(1),0k k k d d Ad --<>= 然后从点)(k X 出发，沿方向)(k d 求得)(X f 的极小值点 )1(+k X , 即 )(min )() ()(0 )1(k d X f X f k k λλ+=>+ 如此下去, 得到序列{)(k X }。不难求得0,)1()(>=<-k k Ad d 的解为 ) () 1()1()()() () 1(,,k k k k k k k d Ad d d AX b X X > <>-<+=--+ 注意到)(k d 的选取不唯一，我们可取 Matlab实现数值分析插值及积分 摘要： 数值分析(numerical analysis)是研究分析用计算机求解数学计算问题的数值计算方法及其理论的学科，是数学的一个分支，它以数字计算机求解数学问题的理论和方法为研究对象。在实际生产实践中，常常将实际问题转化为数学模型来解决，这个过程就是数学建模。学习数值分析这门课程可以让我们学到很多的数学建模方法。 分别运用matlab数学软件编程来解决插值问题和数值积分问题。题目中的要求是计算差值和积分，对于问题一，可以分别利用朗格朗日插值公式，牛顿插值公式，埃特金逐次线性插值公式来进行编程求解，具体matlab代码见正文。编程求解出来的结果为：=+。 其中Aitken插值计算的结果图如下： 对于问题二，可以分别利用复化梯形公式，复化的辛卜生公式，复化的柯特斯公式编写程序来进行求解，具体matlab代码见正文。编程求解出来的结果为： 0.6932 其中复化梯形公式计算的结果图如下： 问题重述 问题一：已知列表函数 表格 1 分别用拉格朗日，牛顿，埃特金插值方法计算。 问题二：用复化的梯形公式，复化的辛卜生公式，复化的柯特斯公式计算积分，使精度小于5。 问题解决 问题一：插值方法 对于问题一，用三种差值方法：拉格朗日，牛顿，埃特金差值方法来解决。 一、拉格朗日插值法： 拉格朗日插值多项式如下： 首先构造1+n 个插值节点n x x x ,,,10 上的n 插值基函数，对任一点i x 所对应的插值基函数 )(x l i ，由于在所有),,1,1,,1,0(n i i j x j +-=取零值，因此)(x l i 有因子 )())(()(110n i i x x x x x x x x ----+- 。又因)(x l i 是一个次数不超过n 的多项式，所以只 可能相差一个常数因子，固)(x l i 可表示成： )())(()()(110n i i i x x x x x x x x A x l ----=+- 利用1)(=i i x l 得： .0],;,[0 ),()(),()(),(0),()(),()(),(,.**,0],;,[),()()(),()()(,0),(),(),(])()[(),(),(),(),(),(])()[(),(),(2,),(])()[(21),(])()[(),(),()(2 )(''))((')()(: 1n 1n 110101010100000000000000000000000000200000000000 00 000fg g f y y g f g f g f fg x x g g f f y x g y y y x g x x y x g y x f y y y x f x x y x f y x y x y x g f g f fg g f y y g f g f g f fg x x g f g f fg g f y y g f g f g f fg x x g g f f y x g y x g y y y x g x x y x f y x f y y y x f x x y x g y x f y x g y y y x x x y x g y x g y x f y x g y x f y y y x x x y x f y x f y x y x f y y y x x x y x f y y y x x x y x f y x f x x f x x x f x f x f x x n n x y y x y y y x y x n n y n n n x n n n n n y n n n x n n n n n x y y x x x x y y x y y x y y x x x x y y x y y y x y x y x y x y y x x y y x x y x y y x x ，则其解可记为： 的行列式不为若系数矩阵： 附近的线性化方程组为在一元方程牛顿迭代法，类似 ，的新近似值于是就得到了根，则可得解： 的行列式不为若系数矩阵），（），（ ），（），（ 则两式构成方程组： 令可得： 构成二元方程组，同样与若另有一方程： 阶小项，得到线性方程忽略在方程根附近取值时，当二元函数的展开为： 开类似一元函数的泰勒展?????+-+=-+-+=?????=-+-+=-+-+??? ????-+-+=-+-+=????????-+-=--+-=-?????-=-+--=-+-==??-+??-+=??-+??-+=??-+??-+??-+??-+=-+ -+=++========η ξξ MATLAB 程序 1、图示牛顿迭代法（M 文件）文件名：newt_g function x = new_g(f_name,x0,xmin,xmax,n_points) clf,hold off % newton_method with graphic illustration del_x = 0.001; wid_x = xmax - xmin; dx = (xmax - xmin)/n_points; xp = xmin:dx:xmax; yp = feval(f_name,xp); plot(xp,yp);xlabel('x');ylabel('f(x)'); title('newton iteration'),hold on ymin = min(yp); ymax = max(yp); wid_y = ymax-ymin; yp = 0. * xp; plot(xp,yp) x = x0; xb = x+999; n=0; while abs(x-xb) > 0.000001 if n > 300 break; end y=feval(f_name,x); plot([x,x],[y,0]);plot(x,0,'o') fprintf(' n = % 3.0f, x = % 12.5e, y = % 12.5e \ n', n, x, y); xsc = (x-xmin)/wid_x; if n < 4, text(x,wid_y/20,[num2str(n)]), end y_driv = (feval(f_name,x + del_x) - y)/del_x; xb = x; x = xb - y/y_driv; n = n+1; plot([xb,x],[y,0]) end plot([x x],[0.05 * wid_y 0.2 * wid_y]) text( x, 0.2 * wid_y, 'final solution') plot([ x ( x - wid_x * 0.004)], [0.01 * wid_y 0.09 * wid_y]) plot([ x ( x + wid_x * 0.004)], [0.01 * wid_y 0.09 * wid_y]) 传热问题 假设一个火炉是用厚度为0.05m 的砖单层砌成的。炉内壁温度为T 0=625K, 外壁温度为T 1（未知）。由于对流和辐射造成了外壁的热量损失，温度T 1由下式决定： 44111()()()()0f k f T T T T T h T T x εσ∞=-+-+-=? 其中： k ：炉壁的热传导系数，1.2W/mK ε: 发射率，0.8 T 0：内壁温度，625K T 1：外壁温度（未知），K T ∞：环境温度，298K T f ：空气温度，298K H ：热交换系数，20W/m 2K 用MATLAB 实现共轭梯度法求解实例 康福 1 一．无约束优化方法 1.1 无约束优化方法的必要性 一般机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它 们都属于约束优化问题。但是为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达到。所以无约束优 化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 （4）对于多维无约束问题来说，古典极值理论中令一阶导数为零，但要求二阶可 微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无 实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典 极值理论是无约束优化方法发展的基础。 1.2共轭梯度法 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向 上的差别。 （1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺度法、共轭梯度 法等。 （2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。 用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方 法较适用于解决变量个数较少的（n ≤20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。 搜索方向的构成问题乃是无约束优化方法的关键。 共轭梯度法是沿着共轭方向进行搜索，属于共轭方向法中的一种，该方法中 每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。共轭梯度法作为一种实用的迭代法，它主要有下面的优点： （1）算法中，系数矩阵Ａ的作用仅仅是用来由已知向量P 产生向量W=AP ，这不仅 可充分利用Ａ的稀疏性，而且对某些提供矩阵Ａ较为困难而由已知向量P 产 生向量W=AP 又十分方便的应用问题是很有益的。 （2）不需要预先估计任何参数就可以计算，这一点不像SOR 等； （3）每次迭代所需的计算，主要是向量之间的运算，便于并行化。 共轭梯度法原理的知识较多，请详见《机械优化设计》第四章的第四、五节。 图1为共轭梯度法的程度框图 1(0,1,2,) k k k k s k α+=+=x x 最优化课程设计--共轭梯度法算法分析与实现(设计程序) 题目共轭梯度法算法分析与实现 班级 / 学号 14140101/2011041401011 学生姓名黄中武指导教师王吉波王微微 课程设计任务书 课程名称最优化方法课程设计院(系) 理学院专业信息与计算科学 课程设计题目共轭梯度法算法分析与实现课程设计时间: 2014 年 6月 16日至 2014 年 6月 27日 课程设计的要求及内容: [要求] 1. 学习态度要认真，要积极参与课程设计，锻炼独立思考能力; 2. 严格遵守上机时间安排; 3. 按照MATLAB编程训练的任务要求来编写程序; 4. 根据任务书来完成课程设计论文; 5. 报告书写格式要求按照沈阳航空航天大学“课程设计报告撰写规范”; 6. 报告上交时间:课程设计结束时上交报告; 7. 严禁抄袭行为，一旦发现，课程设计成绩为不及格。 一、运用共轭梯度法求解无约束最优化问题 要求:1)了解求解无约束最优化问题的共轭梯度法; 2)绘出程序流程图; 3)编写求解无约束最优化问题的共轭梯度法MATLAB程序; 4)利用编写文件求解某无约束最优化问题; 5)给出程序注释。 指导教师年月日 负责教师年月日 学生签字年月日 沈阳航空航天大学 课程设计成绩评定单 课程名称最优化理论与算法课程设计院(系) 理学院专业信息与计算科学课程设计题目共轭梯度法算法分析与实现学号 2011041401011 姓名黄中武指导教师评语: 课程设计成绩 指导教师签字 年月日 最优化方法课程设计沈阳航空航天大学课程设计用纸目录 目录 一、正 文 (1) 二、总结 ............................................................... 8 参考文 献 ............................................................... 9 附录 .. (10) 第 I 页 最优化方法课程设计沈阳航空航天大学课程设计用纸正文 一、正文 一无约束最优化问题的共轭梯度法 1. 二元函数的newton 迭代法理论分析 设),(y x f z =在点),(00y x 的某一邻域内连续且有直到2阶的连续偏导数，),(00h y h x ++为该邻域内任意一点，则有 ?? ? ????? +??+≈++==00) ,(),(),(),(0000y y x x y x f y k y x f x h y x f k y h x f 其中 0x x h -=，0y -=y k 于是方程0),(=y x f 可近似表示为 0) ,(),(),(k =?? ? ????? +??+==k k y y x x k y x f y k y x f x h y x f 即 0),()(),()(),(y k =-+-+k k k k k x k k y x f y y y x f x x y x f 同理，设y)g(x,z =在点),(00y x 的某一邻域内连续且有直到2阶的连续偏导数，),(00h y h x ++为该邻域内任意一点，亦有 ?? ?????? +??+≈++==00),(),(),(),(0000y y x x y x g y k y x g x h y x g k y h x g 其中0x x h -=，0y -=y k 于是方程0),(g =y x 可近似表示为 0) ,(),(),(k =?? ? ????? +??+==k k y y x x k y x g y k y x g x h y x g 即 0),(g )(),()(),(y k =-+-+k k k k k x k k y x y y y x g x x y x g 于是得到方程组 ? ??=-+-+=-+-+0),(g )(),()(),(0),()(),()(),(y k y k k k k k k x k k k k k k k x k k y x y y y x g x x y x g y x f y y y x f x x y x f 题目一：多项式插值 某气象观测站在8：00（AM ）开始每隔10分钟对天气作如下观测，用三次多项式插值函数（Newton ）逼近如下曲线，插值节点数据如上表，并求出9点30分该地区的温度（x=10）。 二、数学原理 假设有n+1个不同的节点及函数在节点上的值（x 0，y 0），……（x n ，y n ），插值多项式有如下形式： ）（） ）（（）（）（）（n 10n 102010n x -x )(x -x x -x x P x x x x x x -??-+??+-++=αααα （1） 其中系数i α（i=0,1,2……n ）为特定系数，可由插值样条i i n y x P =） （（i=0,1,2……n ）确定。 根据均差的定义，把x 看成[a,b]上的一点,可得 f(x)= f （0x ）+f[10x x ，]（0x -x ） f[x, 0x ]= f[10x x ，]+f[x,10x x ，] （1x -x ） …… f[x, 0x ，…x 1-n ]= f[x, 0x ，…x n ]+ f[x, 0x ，…x n ](x-x n ) 综合以上式子，把后一式代入前一式，可得到： f(x)= f[0x ]+f[10x x ，]（0x -x ）+ f[210x x x ，，]（0x -x ）（1x -x ）+ …+ f[x, 0x ，…x n ]（0x -x ）…(x-x 1-n )+ f[x, 0x ，…x n ,x ]） （x 1n +ω= N n （x ）+） （x n R 其中 N n （x ）= f[0x ]+f[10x x ，]（0x -x ）+ f[210x x x ，，]（0x -x ）（1x -x ）+ …+ f[x, 0x ，…x n ]（0x -x ）…(x-x 1-n ) （2） ）（x n R = f(x)- N n （x ）= f[x, 0x ， (x) n ,x ]） （x 1n +ω （3） ） （x 1n +ω=（0x -x ）…(x-x n ) Newton 插值的系数i α（i=0,1,2……n ）可以用差商表示。一般有 f k =α[k 10x x x ??，] （k=0,1,2，……，n ） （4） 把（4）代入（1）得到满足插值条件N ）（） （i i n x f x =（i=0,1,2，……n ）的n 次Newton 插值多项式 N n （x ）=f （0x ）+f[10x x ，]（1x -x ）+f[210x x x ，，]（1x -x ）（2x -x ）+……+f[n 10x x x ??，]（1x -x ）（2x -x ）…（1-n x -x ）. 其中插值余项为： ） （）！ （） （）（）（）（x 1n f x N -x f x R 1n 1 n n +++==ωξ ξ介于k 10x x x ??，之间。 三、程序设计 function [y,A,C,L]=newdscg(X,Y,x,M) % y 为对应x 的值，A 为差商表，C 为多项式系数，L 为多项式 % X 为给定节点，Y 为节点值，x 为待求节点 n=length(X); m=length(x); % n 为X 的长度 for t=1:m 实验七 牛顿迭代法 【实验目的】 1．了解牛顿迭代法的基本概念。 2．了解牛顿迭代法的收敛性和收敛速度。 3．学习掌握MATLAB 软件有关的命令。 【实验内容】 用牛顿迭代法求方程0123=-++x x x 的近似根，误差不超过310-。 【实验准备】 1．牛顿迭代法原理 设已知方程0)(=x f 的近似根0x ,则在0x 附近)(x f 可用一阶泰勒多项式))((')()(000x x x f x f x p -+=近似代替.因此, 方程0)(=x f 可近似地表示为0)(=x p .用1x 表示0)(=x p 的根,它与0)(=x f 的根差异不大. 设0)('0≠x f ,由于1x 满足,0))((')(0100=-+x x x f x f 解得 ) (')(0001x f x f x x -= 重复这一过程,得到迭代格式 ) (')(1n n n n x f x f x x -=+ 这就是著名的牛顿迭代公式,它相应的不动点方程为 ) (')()(x f x f x x g -=. 2. 牛顿迭代法的几何解析 在0x 处作曲线的切线，切线方程为))((')(000x x x f x f y -+=。令 0=y ，可得切线与x 轴的交点坐标) (')(0001x f x f x x -=，这就是牛顿法的迭代公式。因此，牛顿法又称“切线法”。 3．牛顿迭代法的收敛性 计算可得2)] ('[)(")()('x f x f x f x g -=,设*x 是0)(=x f 的单根,有0)(',0)(**≠=x f x f ,则 0)]('[)(")()('2**** =-=x f x f x f x g , 故在*x 附近,有1)(' 最优化方法第四次作业 题目：利用FR-共轭梯度法求解无约束优化问题222 12122min ()44412x R f x x x x x x ∈=+--。初始点(0)(0.5,1).T x =- () ()T k k T k k k k k k k g g g g k d g k g d 111110.0,;0,-----=???≥+-=-=ββ 一、程序 function [x,val,k]=frcg(fun,gfun,x0) %功能：用FR 共轭梯度法求解无约束问题min f （x ） %输入：x0是初始点，fun,gfun 分别是求目标函数和梯度 %输出：x,val 分别是近似最优点和最优值，k 是迭代次数 maxk=5000; rho=0.6; sigma=0.4; k=0; epsilon=1e-4; n=length(x0); while (k while (m<20) %用Armijo 搜索求步长 if (feval(fun,x0+rho^m*d) MATLAB程序设计期中作业 ——编程实现牛顿插值 成员:刘川（P091712797）签名＿＿＿＿＿ 汤意（P091712817）签名＿＿＿＿＿ 王功贺（P091712799）签名＿＿＿＿＿ 班级:2009信息与计算科学 学院:数学与计算机科学学院 日期:2012年05月02日 牛顿插值的算法描述及程序实现 一：问题说明 在我们的实际应用中，通常需要解决这样的问题，通过一些已知的点及其对应的值，去估算另外一些点的值，这些数据之间近似服从一定的规律，于是，这就引入了插值法的思想。 插值法是利用函数f (x)在某区间中若干点的函数值，作出适当的特定函数，在这些点上取已知值，在区间的其他点上用这特定函数的值作为函数f (x)的近似值。如果这特定函数是多项式，就称它为插值多项式。利用插值基函数很容易得到拉格朗日插值多项式，公式结构紧凑，在理论分析中甚为方便，但当插值节点增减时全部插值基函数均要随之变化，整个公式也将发生变化，这在实际计算中是很不方便的，为了克服这一缺点，提出了牛顿插值。 二：算法分析 newton 插值多项式的表达式如下： 010011()()()()()n n n N x c c x x c x x x x x x -=+-+???+--???- 其中每一项的系数c i 的表达式如下： 12011010 [,,,][,,,] [,,,]i i i i i f x x x f x x x c f x x x x x -???-???=???= - 即为f (x)在点01,,,i x x x ???处的i 阶差商，（[]()i i f x f x =，1,2,,i n = ），由差商01[,,,]i f x x x ???的性质可知： () 010 1 [,,,]()i i i j j k j k k j f x x x f x x x ==≠???=-∑∏ 牛顿插值的程序实现方法： 第一步：计算[][][][]001012012,,,,,,,n f x f x x f x x x f x x x x 、、、 、。 第二步：计算牛顿插值多项式中01[,,,]i f x x x ???011()()()i x x x x x x ---???-，1,2,,i n = ，得到n 个多项式。 【最新整理，下载后即可编辑】 用MATLAB 实现共轭梯度法求解实例 康福 201103710031 一．无约束优化方法 1.1 无约束优化方法的必要性 一般机械优化设计问题，都是在一定的限制条件下追求某一指标为最小，它们都属于约束优化问题。但是为什么要研究无约束优化问题? （1）有些实际问题，其数学模型本身就是一个无约束优化问题。 （2）通过熟悉它的解法可以为研究约束优化问题打下良好的基础。 （3）约束优化问题的求解可以通过一系列无约束优化方法来达 到。所以无约束优化问题的解法是优化设计方法的基本组成部分，也是优化方法的基础。 （4）对于多维无约束问题来说，古典极值理论中令一阶导数为零， 但要求二阶可微，且要判断海赛矩阵为正定才能求得极小点，这种方法有理论意义，但无实用价值。和一维问题一样，若多元函数F(X)不可微，亦无法求解。但古典极值理论是无约束优化方法发展的基础。 1.2共轭梯度法 目前已研究出很多种无约束优化方法，它们的主要不同点在于构造搜索方向上的差别。 （1）间接法——要使用导数，如梯度法、（阻尼）牛顿法、变尺 度法、共轭梯度法等。 （2）直接法——不使用导数信息，如坐标轮换法、鲍威尔法单纯形法等。 用直接法寻找极小点时，不必求函数的导数，只要计算目标函数值。这类方法较适用于解决变量个数较少的（n ≤20）问题，一般情况下比间接法效率低。间接法除要计算目标函数值外，还要计算目标函数的梯度，有的还要计算其海赛矩阵。 1(0,1,2,)k k k k s k α+=+=x x 搜索方向的构成问题乃是无约束优化方法的关键。 共轭梯度法是沿着共轭方向进行搜索，属于共轭方向法中的一种，该方法中每一个共轭向量都是依赖于迭代点处的负梯度而构造出来。共轭梯度法作为一种实用的迭代法，它主要有下面的优点： （1）算法中，系数矩阵Ａ的作用仅仅是用来由已知向量P产生向量W=AP，这不仅可充分利用Ａ的稀疏性，而且对某些提供 矩阵Ａ较为困难而由已知向量P产生向量W=AP又十分方便 的应用问题是很有益的。 （2）不需要预先估计任何参数就可以计算，这一点不像SOR等；（3）每次迭代所需的计算，主要是向量之间的运算，便于并行化。 共轭梯度法原理的知识较多，请详见《机械优化设计》第四章的第四、五节。 图1为共轭梯度法的程度框图 6.3.5 牛顿插值法的MATLAB 综合程序 求牛顿插值多项式、差商、插值及其误差估计的MATLAB 主程序 function [y,R,A,C,L]=newdscg(X,Y,x,M) n=length(X); m=length(x); for t=1:m z=x(t); A=zeros(n,n);A(:,1)=Y'; s=0.0; p=1.0; q1=1.0; c1=1.0; for j=2:n for i=j:n A(i,j)=(A(i,j-1)- A(i-1,j-1))/(X(i)-X(i-j+1)); end q1=abs(q1*(z-X(j-1)));c1=c1*j; end C=A(n,n);q1=abs(q1*(z-X(n))); for k=(n-1):-1:1 C=conv(C,poly(X(k))); d=length(C);C(d)=C(d)+A(k,k); end y(k)= polyval(C, z); end R=M*q1/c1;L(k,:)=poly2sym(C); 例6.3.6 给出节点数据00.27)00.4(=-f ，00.1)00.0(=f ，00.2)00.1(=f ，00.17)00.2(=f ，作三阶牛顿插值多项式，计算)345.2(-f ，并估计其误差. 解 首先将名为newdscg.m 的程序保存为M 文件，然后在MATLAB 工作窗口输入程序 >> syms M,X=[-4,0,1,2]; Y =[27,1,2,17]; x=-2.345; [y,R,A,C,P]=newdscg(X,Y,x,M) 运行后输出插值y )345.2(-≈f 及其误差限公式R ，三阶牛顿插值多项式P 及其系数向量C ，差商的矩阵A 如下 y = 22.3211 R = 65133/562949953421312*M （即R =2.3503*M ） A= 27.0000 0 0 0 1.0000 -6.5000 0 0 2.0000 1.0000 1.5000 0 17.0000 15.0000 7.0000 0.9167 C = 0.9167 4.2500 -4.1667 1.0000 P = 11/12*x^3+17/4*x^2-25/6*x+1 基于Matlab 实现牛顿迭代法解非线性方程组 已知非线性方程组如下 2211221212 10801080x x x x x x x ?-++=??+-+=?? 给定初值0(0,0)T x =，要求求解精度达到0.00001 首先建立函数F(x)，方程组编程如下，将F.m 保存到工作路径中： function f=F(x) f(1)=x(1)^2-10*x(1)+x(2)^2+8; f(2)=x(1)*x(2)^2+x(1)-10*x(2)+8; f=[f(1) f(2)]; 建立函数DF(x),用于求方程组的Jacobi 矩阵，将DF.m 保存到工作路径中： function df=DF(x) df=[2*x(1)-10,2*x(2);x(2)^2+1,2*x(1)*x(2)-10]; 编程牛顿迭代法解非线性方程组，将newton.m 保存到工作路径中： clear; clc x=[0,0]'; f=F(x); df=DF(x); fprintf('%d %.7f %.7f\n',0,x(1),x(2)); N=4; for i=1:N y=df\f'; x=x-y; f=F(x); df=DF(x); fprintf('%d %.7f %.7f\n',i,x(1),x(2)); if norm(y)<0.0000001 break ; else end end 运行结果如下： 0 0.0000000 0.0000000 1 0.8000000 0.8800000 2 0.9917872 0.9917117 3 0.9999752 0.9999685 4 1.0000000 1.0000000 实验2 最速下降法和共轭梯度法的程序设计 一、实验目的 1、熟悉无约束优化问题的最速下降算法和共轭梯度法。 2、培养matlab 编程与上机调试能力。 二、实验课时：2个课时 三、实验准备 1、预习无约束优化问题的最速下降算法和共轭梯度法。 2、熟悉matlab 软件的基本操作及程序编写。 四、实验内容 课堂实验演示 根据最速下降法编写程序，求函数 21222121342)(min x x x x x x x f -++-= 的极小值，其中初始点为()01,1T x = 算法步骤如下： Step1:：给出初始点0x ，和精度1;0k ε<<=； Step2：计算()k f x ?，如果()k f x ε?≤，则停止迭代，输出结果；否则转step3； Step3：令下降方向()k k d f x =-?，计算步长因子k λ使得0()min ()k k k k k f x d f x d λλλ≥+=+，令1,1k k k k x x d k k λ+=+=+，转step2。 其程序如下： function [x,iter,val,dval] = Steepest_Descent_Method(x,eps) k = 1; dy = grad_obj(x); x_mat(:,1) = x;%存储每一次迭代得到的点x while norm(dy)>eps d = -dy; % 搜索方向 lambda = line_search(x,d);%步长 x = x + d*lambda; k = k + 1; x_mat(:,k) = x; dy = grad_obj(x); end iter = k - 1; val = obj(x);%目标函数在极值点处的函数值 实验十七牛顿迭代法 【实验目的】 1.了解牛顿迭代法的基本概念。 2.了解牛顿迭代法的收敛性和收敛速度。 3.学习、掌握MATLAB软件的有关命令。 【实验内容】 用牛顿迭代法求方程3210 x x x 10-。 ++-=的近似根，误差不超过3【实验准备】 1.牛顿迭代法原理 2.牛顿迭代法的几何解析 3.牛顿迭代法的收敛性 4.牛顿迭代法的收敛速度 5.迭代过程的加速 6.迭代的MATLAB命令 MATLAB中主要用for,while等控制流命令实现迭代。 【实验重点】 1.牛顿迭代法的算法实现 2.牛顿迭代法收敛性和收敛速度 【实验难点】 1.牛顿迭代法收敛性和收敛速度 【实验方法与步骤】 练习1用牛顿迭代法求方程3210 ++-=在x=0.5附近的近似 x x x 根，误差不超过310-。 牛顿迭代法的迭代函数为 322()1()()321 f x x x x g x x x f x x x ++-=-=-'++ 相应的MATLAB 代码为 >>clear; >>x=0.5; >>for i=1:3 >>x=x-(x^3+x^2+x-1)/(3*x^2+2*x+1) >>end 可算的迭代数列的前3项0.5455，0.5437，0.5437。经三次迭代，就大大超过了精度要求。 练习2 用牛顿迭代法求方程2(0)x a a =>的近似正实根，由此建立一种求平方根的计算方法。 由计算可知，迭代格式为1()()2a g x x x =+，在实验12的练习4中已经进行了讨论。 【练习与思考】 1.用牛顿迭代法求方程ln 1x x =的近似根。 2.为求出方程310x x --=的根，在区间[1,2]内使用迭代函数进行迭代，纪录迭代数据，问迭代是否收敛？对迭代进行加速，对比加速前的数据，比较加速效果。 3.使用在不动点*x 的泰勒公式，证明牛顿迭代法收敛原理。 MATLAB实现最速下降法_和牛顿法和共轭梯度法最速下降法: 题目:f=(x-2)^2+(y-4)^2 M文件: function [R,n]=steel(x0,y0,eps) syms x; syms y; f=(x-2)^2+(y-4)^2; v=[x,y]; j=jacobian(f,v); T=[subs(j(1),x,x0),subs(j(2),y,y0)]; temp=sqrt((T(1))^2+(T(2))^2); x1=x0;y1=y0; n=0; syms kk; while (temp>eps) d=-T; f1=x1+kk*d(1);f2=y1+kk*d(2); fT=[subs(j(1),x,f1),subs(j(2),y,f2)]; fun=sqrt((fT(1))^2+(fT(2))^2); Mini=Gold(fun,0,1,0.00001); x0=x1+Mini*d(1);y0=y1+Mini*d(2); T=[subs(j(1),x,x0),subs(j(2),y,y0)]; temp=sqrt((T(1))^2+(T(2))^2); x1=x0;y1=y0; n=n+1; end R=[x0,y0] 调用黄金分割法: M文件: function Mini=Gold(f,a0,b0,eps) syms x;format long; syms kk; u=a0+0.382*(b0-a0); v=a0+0.618*(b0-a0); k=0; a=a0;b=b0; array(k+1,1)=a;array(k+1,2)=b; while((b-a)/(b0-a0)>=eps) Fu=subs(f,kk,u); Fv=subs(f,kk,v); if(Fu<=Fv) b=v; v=u; u=a+0.382*(b-a); k=k+1; elseif(Fu>Fv) a=u; u=v; v=a+0.618*(b-a); k=k+1;牛顿插值法原理及应用
matlab实现牛顿迭代法求解非线性方程组教学文稿
数学实验“线性方程组的最速下降法与共轭梯度法解法”实验报告(内含matlab程序代码)
matlab实现数值分析报告插值及积分
牛顿迭代法解元方程组以及误差分析matlab实现
MATLAB程序(牛顿法及线形方程组)
用MATLAB实现共轭梯度法求解实例
最优化课程设计--共轭梯度法算法分析与实现
非线性方程组求解的牛顿迭代法用MATLAB实现
matlab牛顿插值法例题与程序
2-8牛顿迭代法matlab
作业4-FR共轭梯度法
牛顿插值MATLAB算法
用MATLAB实现共轭梯度法求解实例(精编文档).doc
牛顿插值法的MATLAB综合程序
基于Matlab的牛顿迭代法解非线性方程组
实验2 最速下降法和共轭梯度法的程序设计
matlab实验十七__牛顿迭代法
MATLAB实现最速下降法_和牛顿法和共轭梯度法
相关主题
文本预览