第四章 非线性方程和非性方程组的解法 4.1 非线性方程的解法 4.2 非线性方程组的线性化解法 4.3 非线性方程组的极值求解法

Slides:



Advertisements
Similar presentations
数值分析 第五节 数值微分 在实际问题中,往往会遇到某函数 f(x) 是用表格 表示的, 用通常的导数定义无法求导, 因此要寻求其他 方法近似求导。常用的数值微分方法有 : 一. 运用差商求数值微分 二.运用插值函数求数值微分 三. 运用样条插值函数求数值微分 四. 运用数值积分求数值微分.
Advertisements

高等数学( XJD ) 第二章 导数与微分 返回 高等数学( XAUAT ) 高等数学( XJD ) 求导法则 基本公式 导 数 导 数 微 分微 分 微 分微 分 求导方法 高阶导数 微分法则 导数与微分关系图导数与微分关系图.
一、 一阶线性微分方程及其解法 二、 一阶线性微分方程的简单应用 三、 小结及作业 §6.2 一阶线性微分方程.
第五节 全微分方程 一、全微分方程及其求法 二、积分因子法 三、一阶微分方程小结. 例如 所以是全微分方程. 定义 : 则 若有全微分形式 一、全微分方程及其求法.
第五节 函数的微分 一、微分的定义 二、微分的几何意义 三、基本初等函数的微分公式与微分运算 法则 四、微分形式不变性 五、微分在近似计算中的应用 六、小结.
第二章 导数与微分 习题课 主要内容 典型例题 测验题. 求 导 法 则求 导 法 则 求 导 法 则求 导 法 则 基本公式 导 数 导 数 微 分微 分 微 分微 分 高阶导数 高阶微分 一、主要内容.
目录 上页 下页 返回 结束 习题课 一、导数和微分的概念及应用 二、导数和微分的求法 导数与微分 第二章.
第九章 常微分方程数值解法 §1 、引言. 微分方程的数值解:设方程问题的解 y(x) 的存在区间是 [a,b] ,令 a= x 0 < x 1
2.8 函数的微分 1 微分的定义 2 微分的几何意义 3 微分公式与微分运算法则 4 微分在近似计算中的应用.
第八章 第四节 机动 目录 上页 下页 返回 结束 一个方程所确定的隐函数 及其导数 隐函数的微分法.
一、会求多元复合函数一阶偏导数 多元复合函数的求导公式 学习要求: 二、了解全微分形式的不变性.
2.6 隐函数微分法 第二章 第二章 二、高阶导数 一、隐式定义的函数 三、可微函数的有理幂. 一、隐函数的导数 若由方程 可确定 y 是 x 的函数, 由 表示的函数, 称为显函数. 例如, 可确定显函数 可确定 y 是 x 的函数, 但此隐函数不能显化. 函数为隐函数. 则称此 隐函数求导方法.
1 热烈欢迎各位朋友使用该课件! 广州大学数学与信息科学学院. 2 工科高等数学 广州大学袁文俊、邓小成、尚亚东.
5.4 微 分 一、微分概念 二、微分的运算法则与公式 三、微分在近似计算上的应用. 引例 一块正方形金属片受热后其边长 x 由 x 0 变到 x 0  x  考查此薄片的面积 A 的改变情况  因为 A  x 2  所以金属片面 积的改变量为  A  (x 0 
2.5 函数的微分 一、问题的提出 二、微分的定义 三、可微的条件 四、微分的几何意义 五、微分的求法 六、小结.
第二章 导数与微分 一. 内 容 要 点 二. 重 点 难 点 三. 主 要 内 容 四. 例 题与习题.
第二章 导数与微分. 二、 微分的几何意义 三、微分在近似计算中的应用 一、 微分的定义 2.3 微 分.
全微分 教学目的:全微分的有关概念和意义 教学重点:全微分的计算和应用 教学难点:全微分应用于近似计算.
2.3 函数的微分. 四川财经职业学院 课前复习 高阶导数的定义和计算方法。 作业解析:
第三节 微分 3.1 、微分的概念 3.2 、微分的计算 3.3 、微分的应用. 一、问题的提出 实例 : 正方形金属薄片受热后面积的改变量.
1.非线性振动和线性振动的根本区别 §4-2 一维非线性振动及其微分方程的近似解法 方程
第四章无约束优化方法 第一节 概述 从第一章列举的机械设计问题,大多数实际问题是约束优化问题。
一、二阶行列式的引入 用消元法解二元线性方程组. 一、二阶行列式的引入 用消元法解二元线性方程组.
第三章 函数逼近 — 最佳平方逼近.
《高等数学》(理学) 常数项级数的概念 袁安锋
第四节 对数留数与辐角原理 一、对数留数 二、辐角原理 三、路西定理 四、小结与思考.
恰当方程(全微分方程) 一、概念 二、全微分方程的解法.
高等数学电子教案 第五章 定积分 第三节 微积分基本定理.
第五节 微积分基本公式 、变速直线运动中位置函数与速度 函数的联系 二、积分上限函数及其导数 三、牛顿—莱布尼茨公式.
一、原函数与不定积分 二、不定积分的几何意义 三、基本积分公式及积分法则 四、牛顿—莱布尼兹公式 五、小结
第二节 微积分基本公式 1、问题的提出 2、积分上限函数及其导数 3、牛顿—莱布尼茨公式 4、小结.
第四章 定积分及其应用 4.3 定积分的概念与性质 微积分基本公式 定积分的换元积分法与分部积分法 4.5 广义积分
第四章 一元函数的积分 §4.1 不定积分的概念与性质 §4.2 换元积分法 §4.3 分部积分法 §4.4 有理函数的积分
第5章 定积分及其应用 基本要求 5.1 定积分的概念与性质 5.2 微积分基本公式 5.3 定积分的换元积分法与分部积分法
第三节 格林公式及其应用(2) 一、曲线积分与路径无关的定义 二、曲线积分与路径无关的条件 三、二元函数的全微分的求积 四、小结.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
第二章 导数与微分 第二节 函数的微分法 一、导数的四则运算 二、复合函数的微分法.
第三章 导数与微分 习 题 课 主要内容 典型例题.
2-7、函数的微分 教学要求 教学要点.
§5 微分及其应用 一、微分的概念 实例:正方形金属薄片受热后面积的改变量..
第5章 §5.3 定积分的积分法 换元积分法 不定积分 分部积分法 换元积分法 定积分 分部积分法.
第2章 Z变换 Z变换的定义与收敛域 Z反变换 系统的稳定性和H(z) 系统函数.
第4章 非线性规划 一维搜索方法 2011年11月.
§2 求导法则 2.1 求导数的四则运算法则 下面分三部分加以证明, 并同时给出相应的推论和例题 .
第一章 函数 函数 — 研究对象—第一章 分析基础 极限 — 研究方法—第二章 连续 — 研究桥梁—第二章.
第二章 非线性方程的数值解法 非线性方程 n次代数方程 : 超越方程: n=1,2 n=3,4 n≥5 求根公式 查数学手册 ? 如
第 五 章 无约束最优化方法.
第4章 非线性规划 4.5 约束最优化方法 2019/4/6 山东大学 软件学院.
6.4不等式的解法举例(1) 2019年4月17日星期三.
概 率 统 计 主讲教师 叶宏 山东大学数学院.
Three stability circuits analysis with TINA-TI
线 性 代 数 厦门大学线性代数教学组 2019年4月24日6时8分 / 45.
WPT MRC. WPT MRC 由题目引出的几个问题 1.做MRC-WPT的多了,与其他文章的区别是什么? 2.Charging Control的手段是什么? 3.Power Reigon是什么东西?
第16讲 相似矩阵与方阵的对角化 主要内容: 1.相似矩阵 2. 方阵的对角化.
§6.7 子空间的直和 一、直和的定义 二、直和的判定 三、多个子空间的直和.
3.1 变化率与导数   3.1.1 变化率问题 3.1.2 导数的概念.
第三章 函数的微分学 第二节 导数的四则运算法则 一、导数的四则运算 二、偏导数的求法.
学习任务三 偏导数 结合一元函数的导数学习二元函数的偏导数是非常有用的. 要求了解二元函数的偏导数的定义, 掌握二元函数偏导数的计算.
1.非线性规划模型 2.非线性规划的Matlab形式
建模常见问题MATLAB求解  .
一元二次不等式解法(1).
第15讲 特征值与特征向量的性质 主要内容:特征值与特征向量的性质.
2019/5/20 第三节 高阶导数 1.
第二节 函数的极限 一、函数极限的定义 二、函数极限的性质 三、小结 思考题.
正弦、余弦函数的性质 华容一中 伍立华 2017年2月24日.
§2 方阵的特征值与特征向量.
第三节 函数的微分 3.1 微分的概念 3.2 微分的计算 3.3 微分的应用.
教学大纲(甲型,54学时 ) 教学大纲(乙型, 36学时 )
《偏微分方程》第一章 绪论 第一章 绪论 1.1.
§4.5 最大公因式的矩阵求法( Ⅱ ).
Presentation transcript:

第四章 非线性方程和非性方程组的解法 4.1 非线性方程的解法 4.2 非线性方程组的线性化解法 4.3 非线性方程组的极值求解法 第四章 非线性方程和非性方程组的解法  4.1 非线性方程的解法 4.2 非线性方程组的线性化解法     4.3 非线性方程组的极值求解法 4.4 最速下降法 4.5 共轭梯度法 4.6 牛顿过程及变度量法 4.7 直接法 4.8 方法的选择与总结 浙江大学研究生学位课程 《实用数值计算方法》

1.非线性方程的解法 2.非线性方程组的线性化解法 --牛顿迭代法 3.非线性方程组的极值求解法 --最速下降法 | 单纯形法   1.非线性方程的解法   2.非线性方程组的线性化解法    --牛顿迭代法   3.非线性方程组的极值求解法    --最速下降法 | 单纯形法    --共轭梯度法 | Powell 方法    --变尺度法 |    (可变矩阵方法)| 直接法     DFP 方法 | 浙江大学研究生学位课程 《实用数值计算方法》

4.1 引言 在科学研究中,常常会遇到非线性方程 或非线性方程组的问题。例如解方程 或 一般的,我们记非线性方程为 浙江大学研究生学位课程 第四章 4.1 引言   在科学研究中,常常会遇到非线性方程 或非线性方程组的问题。例如解方程  或  一般的,我们记非线性方程为 浙江大学研究生学位课程 《实用数值计算方法》

其中fi(i=1,2,…,n)是n维实空间Rn 上的 实值函数。用向量形式表示: 4.1 非线性方程组的一般形式是: 其中fi(i=1,2,…,n)是n维实空间Rn 上的   实值函数。用向量形式表示: 这里     均是n维向量。为了方便   计,还是用    分别表示上述向量。 简记为: 浙江大学研究生学位课程 《实用数值计算方法》

4.1 d c a d b c a 图 4.1 非线性方程求根示意图 浙江大学研究生学位课程 《实用数值计算方法》

 方程的解亦称方程的根或函数的零点。  根可能是实数或复数。  若 则 称为单根; 若 而 ,则 称为 k 重根。 4.1  方程的解亦称方程的根或函数的零点。   根可能是实数或复数。   若          则 称为单根;   若    而     ,则 称为 k 重根。 常见的求解问题有两种:  (1) 要求定出在给定范围内的某个解。  (2) 要求定出在给定范围内的全部解。  非线性问题,除少数情况外,一般不能   不利用公式求解。而要采用某种迭代解法。   即构造出一近似值序列           逼近真解 。 浙江大学研究生学位课程 《实用数值计算方法》

 迭代过程的收敛性一般与初值的选取和方 程的性态有关,某些解法仅与初值有关。  收敛速度一般由迭代方法所决定,方程的 4.1    迭代过程的收敛性一般与初值的选取和方   程的性态有关,某些解法仅与初值有关。  收敛速度一般由迭代方法所决定,方程的   性态也会起一些作用。 本章主要介绍非线性方程组的解法, 而方程的解法用较少的篇幅在4.2中扼要介绍。   解非线性方程和方程组有很大区别。后者   要困难得多。主要的区别在于一维情形可   以找到一个根的范围,然后缩小,最终找   到根。而多维情况则很难确定根的存在。   直到你求得它的解。 浙江大学研究生学位课程 《实用数值计算方法》

4.2 非线性方程的解法 4.2.1 二分法 对于连续函数 ,如果在 和 处异号: 则 在 内至少有一个根。 浙江大学研究生学位课程 4.2 非线性方程的解法 4.2.1 二分法    对于连续函数  ,如果在      和   处异号:          则  在  内至少有一个根。 浙江大学研究生学位课程 《实用数值计算方法》

用图来表示这个过程: 确定根所在的范围[a,b]对有的函数 也是一件困难的事。所幸的是,在实际应 用中,根据其物理或工程的背景,在绝大 4.2.1 用图来表示这个过程: y a a b b 0 a b x 图 4.2 二分法方程求根 确定根所在的范围[a,b]对有的函数   也是一件困难的事。所幸的是,在实际应   用中,根据其物理或工程的背景,在绝大   部分场合是不困难的。对给定的函数也有   确定范围的方法。 浙江大学研究生学位课程 《实用数值计算方法》

图 4.3 寻找隔根区间示意1 a x1 b c f c x1 d a x2 x3 b 4.2.1 浙江大学研究生学位课程 图 4.3 寻找隔根区间示意1 浙江大学研究生学位课程 《实用数值计算方法》

4.2.1 图 4.4 寻找隔根区间示意2 a c b 图 4.5 寻找隔根区间示意3 浙江大学研究生学位课程 《实用数值计算方法》

例如,在[a,b]之间寻找 f(x) 可能有 的根可以用等分试探法: a b 图 4.6 等分试探法寻找隔根区间示意 4.2.1   的根可以用等分试探法: a b 图 4.6 等分试探法寻找隔根区间示意 浙江大学研究生学位课程 《实用数值计算方法》

用二分法求函数FUNC位于(x1,x2)之间的根,准确性为XACC。 FUNCTION RTBIS (FUNC,X1,X2,XACC) 4.2.1 用二分法求函数FUNC位于(x1,x2)之间的根,准确性为XACC。 FUNCTION RTBIS (FUNC,X1,X2,XACC) PARAMETER (JMAX=40) FMID=FUNC(X2) F=FUNC(X1) IF (F*FMID.GE.0.) PAUSE '函数FUNC在x1,x2处不异号' IF (F.LT.0.) THEN RTIBIS=X1 DX=X2-X1 ELSE RTBIS=X2 DX=X1-X2 ENDIF DO 11 J=1, JMAX DX=DX*0.5 XMID=RTBIS+DX FMID=FUNC(XMID) IF (FMID.LE.0.) RTBIS=XMID IF (ABS(DX) .LT. XACC .OR. FMID .EQ. 0.) RETURN 11 CONTINUE PAUSE '迭代次数越界' END 浙江大学研究生学位课程 《实用数值计算方法》

PRINT *, '方程在(-1,0)区间内有一个根,X=', ROOT STOP 4.2.1 FUNCTION FF(X) FF = X*X + 2.5*X + 0.5+SIN(X) END PROGRAM ROOTFIND EXTERNAL FF X1=-1.0 X2=0.0 ROOT=RTBIS(FF, X1, X2, 1.0E-5) PRINT *, '方程在(-1,0)区间内有一个根,X=', ROOT STOP 浙江大学研究生学位课程 《实用数值计算方法》

4.2.2 线性插值法(又称弦位法) f(x) x 图 4.7 Secant Method 浙江大学研究生学位课程 《实用数值计算方法》

4.2.2 浙江大学研究生学位课程 《实用数值计算方法》

4.2.2 浙江大学研究生学位课程 《实用数值计算方法》

4.2.2 f(x) 2 3 4 x 1 图 4.8 线性插值法求根示意 浙江大学研究生学位课程 《实用数值计算方法》

4.2.2 f(x) x 1 3 4 5 图 4.9 线性插值法发散示例 浙江大学研究生学位课程 《实用数值计算方法》

4.2.3 Newton 法 F(x) x 图 4.10 Newton 法示意 浙江大学研究生学位课程 《实用数值计算方法》

4.2.3 F(x) x 图 4.11 导数变化对算法的影响 浙江大学研究生学位课程 《实用数值计算方法》

每次函数求值相当的收敛阶为: b. 求 fk' 有时工作量大,甚至不可能。 (4) 选用收敛域较大的方法(如二分法)     每次函数求值相当的收敛阶为:   b. 求 fk' 有时工作量大,甚至不可能。  (4) 选用收敛域较大的方法(如二分法)    先进行迭代,然后再用Newton法。     --组合方法。 4.2.4 二次插值法     设 f(x)=0 的三个近似解及函数值 构造二次函数g(y)使得: 浙江大学研究生学位课程 《实用数值计算方法》

4.2.4 浙江大学研究生学位课程 《实用数值计算方法》

4.2.4 F(x) g(x) f(x) x 图 4.12 二次插值法求根示意 浙江大学研究生学位课程 《实用数值计算方法》

(1) 要有三个初始值 (2) 当 。且收敛速度 是 1.84 阶。(单根) 二重根的收敛阶是1.23。 (3) (4) 发生超射、越界。 4.2.4 (1) 要有三个初始值 (2) 当 。且收敛速度 是 1.84 阶。(单根) 二重根的收敛阶是1.23。 (3) (4) 发生超射、越界。 表 4.1 各种插值方法的比较 浙江大学研究生学位课程 《实用数值计算方法》

4.2.5 组合方法(Brent Method) 能否有一种方法综合上述方法的优 点呢?Brent 做了一些工作。     能否有一种方法综合上述方法的优   点呢?Brent 做了一些工作。     Brent 把二分法和二次插值法结合   起来。   (1)一定收敛。   (2)收敛速度至少线性。   (3)在解附近足够光滑时,收敛速度       将是 1.84 或 1.23。   有关多项式的求根还有一些特殊方法。 浙江大学研究生学位课程 《实用数值计算方法》

4.3 非线性方程组及牛顿法 非线性方程组的向量形式可表示为 解法: 1. 几乎不可能用直接法 2. 线性化,迭代逼近。牛顿法 4.3 非线性方程组及牛顿法 非线性方程组的向量形式可表示为   解法: 1. 几乎不可能用直接法 2. 线性化,迭代逼近。牛顿法 3. 最优化,求函数极小值。下降法。 例如, 求 的极小值点。 最速下降法,共轭梯度法,变尺度方法。 浙江大学研究生学位课程 《实用数值计算方法》

作线性函数(Taylor 展开,取一阶精度) 4.3.1 牛顿法     为方便计,用二维情形来讨论。 假定(4-6)的解   作线性函数(Taylor 展开,取一阶精度) 浙江大学研究生学位课程 《实用数值计算方法》

在 内用线性函数(4-7)代替 非线性方程组(4-6)中的f1,f2, 从而 如果在 中矩阵(称Jacobi矩阵) 非奇异,则可解出。 4.3.1     在    内用线性函数(4-7)代替   非线性方程组(4-6)中的f1,f2, 从而 如果在    中矩阵(称Jacobi矩阵)   非奇异,则可解出。 浙江大学研究生学位课程 《实用数值计算方法》

4.3.1 浙江大学研究生学位课程 《实用数值计算方法》

4.3.1 浙江大学研究生学位课程 《实用数值计算方法》

4.3.1 浙江大学研究生学位课程 《实用数值计算方法》

4.3.2 牛顿法的改进   改进1 带松弛因子的牛顿迭代格式改善了   对初始值近似程度的要求。 浙江大学研究生学位课程 《实用数值计算方法》

4.3.2 (4-10) 中引入了松弛因子  ,有 浙江大学研究生学位课程 《实用数值计算方法》

4.3.2 图 4.13 凸函数示例 浙江大学研究生学位课程 《实用数值计算方法》

4.3.2 浙江大学研究生学位课程 《实用数值计算方法》

4.3.2 图 4.14 0.618法搜索极小点过程 浙江大学研究生学位课程 《实用数值计算方法》

4.3.2 (2) 二次插值法求一维函数极小值: 图 4.15 二次插值法进行一维极小点搜索 浙江大学研究生学位课程 《实用数值计算方法》

的选取可以在满足(4-12)的前提下取很大值。 (1)改善对初值的要求 (2)当 =0时为牛顿法,收敛最快。 4.3.2 改进2.带阻尼因子的牛顿迭代格式 克服了矩阵   的奇异或病态。(4-10)中 引入阻尼因子 :  的选取可以在满足(4-12)的前提下取很大值。  (1)改善对初值的要求  (2)当 =0时为牛顿法,收敛最快。  (3)为满足(4-12),实际上需要多次试算,     工作量大。   改进3. 修正牛顿法 尽可能减少矩阵求逆次数。 浙江大学研究生学位课程 《实用数值计算方法》

一种简单的办法是每次使用同一个Jacobi 矩阵的逆。 4.3.2   一种简单的办法是每次使用同一个Jacobi   矩阵的逆。   但大大影响收敛速度。   另一种办法是若干次迭代后求一个矩阵逆: 它减少了矩阵求逆,又保证了收敛。    换一个角度看,如果说它的求逆次数与   牛顿法相同(k次),则它的收敛阶为m+1。 浙江大学研究生学位课程 《实用数值计算方法》

作为特例,取m=2: 或 迭代格式(4-15)具有3阶收敛速度。 在几何上表现为m步迭代 过程保持斜率 f'(xk) 不变。 如图4.16: 4.3.2 作为特例,取m=2:   或  迭代格式(4-15)具有3阶收敛速度。 对一维情况,Newton法  在几何上表现为m步迭代  过程保持斜率 f'(xk) 不变。  如图4.16: f(x) x 图 4.16 m=2的迭代效果 浙江大学研究生学位课程 《实用数值计算方法》

非线性代数方程组求解问题 1. Newton--Raphson 迭代法 2. 极值化求解。 问题的转化: 4.3.2 浙江大学研究生学位课程   非线性代数方程组求解问题 1. Newton--Raphson 迭代法 2. 极值化求解。   问题的转化: 浙江大学研究生学位课程 《实用数值计算方法》

4.4 最速下降法 4.4.1 极值化 求解 的零极值点。 求解(4-16)的极值点也是一个无约束的最 优化问题。 浙江大学研究生学位课程 4.4 最速下降法 4.4.1 极值化   求解   的零极值点。 求解(4-16)的极值点也是一个无约束的最   优化问题。 浙江大学研究生学位课程 《实用数值计算方法》

4.4.1   求解最优化问题,通常采用下降法。下降法 一般描述如下: 浙江大学研究生学位课程 《实用数值计算方法》

4.4.1   下降法的迭代步骤 浙江大学研究生学位课程 《实用数值计算方法》

4.4.1 最速下降法取 因此 浙江大学研究生学位课程 《实用数值计算方法》

图 4.17 等高线 图 4.18 偏导数示意 等高线图: f(x)=Ci f(x1,x2)=Ci 4.4.1 浙江大学研究生学位课程 图 4.17 等高线 图 4.18 偏导数示意 浙江大学研究生学位课程 《实用数值计算方法》

4.4.2 讨论与改进 优点: 1. 程序简单,每步迭代计算量少,存储省。 2. 对于不太好的初始点x0,往往也能收敛。 缺点: 4.4.2 讨论与改进   优点: 1. 程序简单,每步迭代计算量少,存储省。 2. 对于不太好的初始点x0,往往也能收敛。   缺点:    最速下降法是名不符实的,一般来说,  它只有线性的收敛速度。 浙江大学研究生学位课程 《实用数值计算方法》

4.4.2 图 4.19 锯齿形搜索路径情况 浙江大学研究生学位课程 《实用数值计算方法》

4.4.2 浙江大学研究生学位课程 《实用数值计算方法》

4.4.2 浙江大学研究生学位课程 《实用数值计算方法》

4.4.2     一般来说,开始几步下降速度   较快,但越靠近极小值点越慢。     改进: 浙江大学研究生学位课程 《实用数值计算方法》

4.4.2 最速下降法算法框图: 停 停 图 4.20 最速下降法算法框图 浙江大学研究生学位课程 《实用数值计算方法》

4.4.2 图 4.21 搜索路径示意 浙江大学研究生学位课程 《实用数值计算方法》

4.5 共轭梯度法 (Conjugate Gradient Methods) 4.5.1 共轭方向 图 4.22 共轭方向 浙江大学研究生学位课程 《实用数值计算方法》

4.5.1   浙江大学研究生学位课程 《实用数值计算方法》

4.5.1 浙江大学研究生学位课程 《实用数值计算方法》

4.5.1 图 4.23 二次函数的共轭方向 图 4.24 二次函数 浙江大学研究生学位课程 《实用数值计算方法》

4.5.1 浙江大学研究生学位课程 《实用数值计算方法》

4.5.1 浙江大学研究生学位课程 《实用数值计算方法》

4.5.1 浙江大学研究生学位课程 《实用数值计算方法》

4.5.2 共轭梯度法 Conjugate Gradient Method 利用共轭方向,对二次型求极值问题 可以得到n步收敛的结果。     利用共轭方向,对二次型求极值问题   可以得到n步收敛的结果。     现在的问题是:   1.如何构造n个共轭方向?   2.对一般的非线性函数f(x)怎么办?   3.由于舍入误差等影响,n次迭代不收敛    时怎么办? 浙江大学研究生学位课程 《实用数值计算方法》

4.5.2 浙江大学研究生学位课程 《实用数值计算方法》

4.5.2 浙江大学研究生学位课程 《实用数值计算方法》

4.5.10 浙江大学研究生学位课程 《实用数值计算方法》

4.5.2 浙江大学研究生学位课程 《实用数值计算方法》

* F-R方法和P-R方法的区别在于它们对二 次型是一样的。而对一般函数用P-R方法 可能更合适。 4.5.2     共轭梯度法是从梯度向量出发构造   共轭向量。   * 由于误差积累等因素,对二次型,迭代    n次也未能达到极小点。   * F-R方法和P-R方法的区别在于它们对二 次型是一样的。而对一般函数用P-R方法    可能更合适。   * 共轭梯度法具有二次收敛速度。     那么对一般的函数的共轭梯度法 又是怎样的呢? 浙江大学研究生学位课程 《实用数值计算方法》

4.5.2   在极小值点附近进行二次逼近: 浙江大学研究生学位课程 《实用数值计算方法》

达到精度(kn),则xk就作为x*的近似。 当经过n步迭代仍不可能满足要求时,令 4.5.2     但是求导数f(xk)是必须的。 另外,我们总假定f(x)在极值点附近   性质足够好,满足各种要求。 对一般函数f(x),共轭梯度法(4-23)有 限步收敛几乎是不可能的。如果迭代k 步 达到精度(kn),则xk就作为x*的近似。 当经过n步迭代仍不可能满足要求时,令   再进行第二次循环。     但是,实际计算中,不一定迭代   k=n 步才进行“重置”。 浙江大学研究生学位课程 《实用数值计算方法》

则进行(m+n)次迭代(1m<n)就 收敛了。而进行 k 次迭代(k  n)就 重置的话,有可能会不收敛。 4.5.2 (1) 在极小点附近是一个高度偏心的二次    函数。    则进行(m+n)次迭代(1m<n)就    收敛了。而进行 k 次迭代(k  n)就    重置的话,有可能会不收敛。 (2) 在极小点附近或稍远处不是二次函数。    此时称“扭曲”现象。    则   留有非二次函数的痕迹,故    可能对收敛很有害。此时最好重置。 浙江大学研究生学位课程 《实用数值计算方法》

共轭梯度法 Conjugate Gradient Methods 算法框图 4.5.2 共轭梯度法 Conjugate Gradient Methods 算法框图 图 4.25 共轭梯度法算法框图 浙江大学研究生学位课程 《实用数值计算方法》

(3) 如何判别是高度偏心的二次函数还是 扭曲的函数呢? 启发性的办法是: 对一般非二次函数,若x0离x*较远, 4.5.2   (3) 如何判别是高度偏心的二次函数还是    扭曲的函数呢?    启发性的办法是: 对一般非二次函数,若x0离x*较远,    则迭代n次不收敛时,就重置。但以后不    再重置。      对既高度偏心,又严重扭曲的函数,    则经常性的重置是有好处的。 浙江大学研究生学位课程 《实用数值计算方法》

4.5.2    它在点(1,1)处有极小值4. 其图象为: 图 4.26 函数等高线图 浙江大学研究生学位课程 《实用数值计算方法》

4.5.2      表4.3 最速下降法计算结果 浙江大学研究生学位课程 《实用数值计算方法》

4.5.2  表4.4 各种重置循环的共轭梯度法计算结果 浙江大学研究生学位课程 《实用数值计算方法》

4.6 牛顿过程及变度量法 4.6.1 Newton--Raphson 迭代 把函数f(x)在第k次近似解 xk 附近进行 Taylor展开: 浙江大学研究生学位课程 《实用数值计算方法》

4.6.1 浙江大学研究生学位课程 《实用数值计算方法》

4.6.1 浙江大学研究生学位课程 《实用数值计算方法》

图 4.27 初值对Newton-Raphson 方法的影响 4.6.1 图 4.27 初值对Newton-Raphson 方法的影响 浙江大学研究生学位课程 《实用数值计算方法》

4.6.1 浙江大学研究生学位课程 《实用数值计算方法》

改一次Jk-1,是一种方案。但不是最好的。     然而这个方法的致命弱点是要计算   Jk-1。4.2提供的办法,即迭代若干次修   改一次Jk-1,是一种方案。但不是最好的。 4.6.2 变量的尺度变换     为改变函数的偏心程度,从而改变极   小化方法的收敛性质,采用变量替换是个 很好的措施。 浙江大学研究生学位课程 《实用数值计算方法》

4.6.2 浙江大学研究生学位课程 《实用数值计算方法》

4.6.2 图 4.28 函数进行尺度变换的效果 浙江大学研究生学位课程 《实用数值计算方法》

尺度变换目的是把函数的偏心程度降 到最低限度(它放大或缩小各个坐标), 但并不能完全消除偏心问题。 把尺度变换应用于各种算法,都有一 4.6.2     尺度变换目的是把函数的偏心程度降   到最低限度(它放大或缩小各个坐标),   但并不能完全消除偏心问题。     把尺度变换应用于各种算法,都有一   定效果。     一般地 浙江大学研究生学位课程 《实用数值计算方法》

即变换后的二次函数偏心率为0,它是圆。 它用最速下降法一步可以达到极小点。 现在希望直接处理原来的函数,而定 4.6.2   即变换后的二次函数偏心率为0,它是圆。   它用最速下降法一步可以达到极小点。     现在希望直接处理原来的函数,而定   义一个算子。用它产生通过极小点的向量。   考虑这样的T:   从Newton--Raphson 过程 浙江大学研究生学位课程 《实用数值计算方法》

4.6.2 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 变尺度法   —— DFP方法   —— BFGS方法 常用的度量是 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 浙江大学研究生学位课程 《实用数值计算方法》

变尺度法 Variable Matrix Methods 算法框图: 4.6.3 变尺度法 Variable Matrix Methods 算法框图: 图 4.29 变尺度法算法框图 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 浙江大学研究生学位课程 《实用数值计算方法》

4.6.3 表4.5 各种方法比较 浙江大学研究生学位课程 《实用数值计算方法》

大量的目标函数是很复杂的,有时连解析式都没有,因而它的导数 4.7 直接法(Simplex, Powell)   大量的目标函数是很复杂的,有时连解析式都没有,因而它的导数         f(x)  很难求,有时甚至不存在。 4.7.1 单纯形法 Simplex Method Nelder--Mead (1965)提出这种简单的方法。它不需要求导数(梯度) 对变元不多的情况是有效的。 程序简单。 浙江大学研究生学位课程 《实用数值计算方法》

(它们构成单纯形)上引进函数值比较。丢弃 最坏的点并代之以新点。它们仍然构成单纯 形。以此逐步逼近极小点。 4.7.1     单纯形的思想是在n维空间的(n+1)个点   (它们构成单纯形)上引进函数值比较。丢弃   最坏的点并代之以新点。它们仍然构成单纯   形。以此逐步逼近极小点。 浙江大学研究生学位课程 《实用数值计算方法》

4.7.1 图 4.30 单纯形法中的反射 浙江大学研究生学位课程 《实用数值计算方法》

4.7.1 图 4.31 单纯形法中的延伸 浙江大学研究生学位课程 《实用数值计算方法》

4.7.1 浙江大学研究生学位课程 《实用数值计算方法》

4.7.1 图 4.32 单纯形法中的收缩 浙江大学研究生学位课程 《实用数值计算方法》

4.7.1 e) 缩小边长 图 4.33 单纯形法中的缩小边长 浙江大学研究生学位课程 《实用数值计算方法》

4.7.1 单纯形法(Simplex)框图: 解x*x0 图 4.34 单纯形法计算框图 浙江大学研究生学位课程 《实用数值计算方法》

Powelll 方法是一种不依赖于目标函数 梯度的直接搜索法。 它逐步构造共轭方向并作为搜索方向, 因此Powell方法也是一种共轭方向法。     以上的迭代过程直到满足精度为止。   精度:     则x0作为所求的近似解。 4.7.2 Powelll 方法      Powelll 方法是一种不依赖于目标函数   梯度的直接搜索法。     它逐步构造共轭方向并作为搜索方向,   因此Powell方法也是一种共轭方向法。   它的基本过程如下: 浙江大学研究生学位课程 《实用数值计算方法》

表4.6 Powell 方法解题过程 图 4.35 Powell搜索路径 4.7.2 5.0 2.5 浙江大学研究生学位课程 《实用数值计算方法》

4.7.2 浙江大学研究生学位课程 《实用数值计算方法》

4.7.2 Powell方法过程图示: 图4.36 Powell 方法计算过程图示 浙江大学研究生学位课程 《实用数值计算方法》

 循环上面(1)--(3),直至P0点函数值不再减 小为止。  当循环k次(kn)以后,un与它前面的k-1个 4.7.2    循环上面(1)--(3),直至P0点函数值不再减    小为止。    当循环k次(kn)以后,un与它前面的k-1个    向量 un-k+1,,un-1共轭。因此对于二次函数,    理论上只要循环n次即可求得极小值。即具    有二次收敛性。事实上,因为     P0和Pn是沿相同方向un求得的极小值,   所以PnP0与un方向共轭。 图 4.37 共轭方向 浙江大学研究生学位课程 《实用数值计算方法》

4.7.2 图 4.38 Powell 方法计算过程示意 浙江大学研究生学位课程 《实用数值计算方法》

4.7.2 表4.7 Powell方法第一次循环计算结果 浙江大学研究生学位课程 《实用数值计算方法》

4.7.2 图 4.39 单纯形法求一维极值示意图(1) 浙江大学研究生学位课程 《实用数值计算方法》

4.7.2 图 4.40 单纯形法求一维极值示意图(2) 浙江大学研究生学位课程 《实用数值计算方法》

因为每一循环都用Pn--P0“挤掉”u1,所以 新的向量系ui(I=1,…,n)有可能线性相关, 例如,某一循环中,如果10则 4.7.2    但是,实际计算中对二次函数也不能保证   n步内达到极小值点。   因为每一循环都用Pn--P0“挤掉”u1,所以   新的向量系ui(I=1,…,n)有可能线性相关,   例如,某一循环中,如果10则   这样,u2,u3,…, Pn--P0是线性相关的。     当发生这种情况时,以后的搜索就在   n 维的子空间中进行。最后的解就不正确。   解决的办法是Pn--P0不是挤掉u1。而是挤掉   ur, 而r0。一般取最大下降方向(the Direction of the Largest Decrease) 浙江大学研究生学位课程 《实用数值计算方法》

这是因为最大下降方向ur已经在平均方向 Pn-P0中得到最充分的体现。  这一简单的思想有两种例外情况:此时 并不修改方向。 4.7.2   这一简单的思想有两种例外情况:此时   并不修改方向。 浙江大学研究生学位课程 《实用数值计算方法》

b) Pn-P0方向上二阶导数很大,这表明在 Pn附近有可能有极小点。 4.7.2   因为下列两个原因之一成立:   a) Pn-P0方向的下降主要不是因为f. b) Pn-P0方向上二阶导数很大,这表明在     Pn附近有可能有极小点。 图 4.41 函数变化的影响 浙江大学研究生学位课程 《实用数值计算方法》

图4.42 修正Powell算法框图: fEf0 4.7.2 收敛准则 P*= Pkn,计算结束 浙江大学研究生学位课程 《实用数值计算方法》

4.7.2 浙江大学研究生学位课程 《实用数值计算方法》

4.7.2 P* 图 4.43 计算结果图示 浙江大学研究生学位课程 《实用数值计算方法》

4.8 方法的选择与总结 4.8.1 方法的选择 1. 原则: (1)有效性 (2)运算量 (3)存储量 2. 非线性代数方程 4.8 方法的选择与总结 4.8.1 方法的选择 1. 原则: (1)有效性 (2)运算量 (3)存储量 2. 非线性代数方程 (1)二分法具有良好的有效性 (2)二次插值和有理插值运算 量少 (3)一般采用组合方法 浙江大学研究生学位课程 《实用数值计算方法》

3. 非线性方程组 (1)一般采用最优化方法 (2)对于无梯度(或不易求梯度)问题, 一般不用CG方法,因为稳定性太 差。 4.8.1  3. 非线性方程组  (1)一般采用最优化方法  (2)对于无梯度(或不易求梯度)问题,     一般不用CG方法,因为稳定性太     差。      用有限差商近似导数不是好的选择。     但是当问题很大时(n200)由于存     贮的限制,POW方法和VM方法     不能用时,只能考虑CG方法。       对小问题(2 n  10),选择     POW方法或VM方法(差商近似     导数)均可考虑。有效性依赖于问     题。 浙江大学研究生学位课程 《实用数值计算方法》

4.8.1 浙江大学研究生学位课程 《实用数值计算方法》

4.8.1 浙江大学研究生学位课程 《实用数值计算方法》

1.迭代法,而不是解析法 2.线性化,极值化方法 3.降维法 4.下降法 5.插值逼近法 6.组合法 7.梯度方向 共轭方向 改变度量 4.8.2 算法思想小结 1.迭代法,而不是解析法   2.线性化,极值化方法   3.降维法   4.下降法   5.插值逼近法   6.组合法   7.梯度方向    共轭方向    改变度量 浙江大学研究生学位课程 《实用数值计算方法》

第四章 习 题 浙江大学研究生学位课程 《实用数值计算方法》

浙江大学研究生学位课程 《实用数值计算方法》