西安交通大学《计算方法》课程课件-第五章
- 格式：pdf
- 大小：581.54 KB
- 文档页数：44
文档推荐
-
西安交大课程考试《政治经济学》在线作业页数:7
-
西安交通大学课程考试侵权行为法作业考核试题图文稿页数:16
-
西安交通大学课程考核办法页数:4
下载文档原格式
合集下载
《计算方法》PPT课件
就可以得到一个递推公式
uk uk1x ank ,
k=1,2, …,n (1.3)
这样的计算过程只需要计算n次乘法和n次加法。 这种算法和上一种算法相比，不仅逻辑结构简单， 而且计算也明显地减少了。多项式求值的这种算法 称为秦九韶算法（计算框图见图1.2)。
2020/12/7
.
10
1.2 误差的来源及其基本概念
5
2020/. 12/7
5.
⒊得不到准确解时，设法得到近似解
例：求 x a, a 已0知数。
由数学中的极限理论可知，
当lim n
xn
x时（，极限存在）
有：lim n
xn1
lim
n
1 2
( xn
a xn
)
即x 1 ( x a )
2
x
于是 x2 a, a 0, x a
又∵n只能有限，∴x是近似值。
2020/12/7
.
6
在计算方法中，我们还将讨论： ⒋解的特性（近似程度，敛散性） ⒌各种方法的优缺点（速度，存储量） ⒍各种方法的实用范围（收敛范围）
7
2020/. 12/7
7.
⑵ 一个好的方法应具有如下特点：
第一，面向计算机，要根据计算机特点提供实际可行的 有效算法，即算法只能包括加、减、乘、除运算和逻辑运 算，是计算机能直接处理的。
计算方法
1
1.1 计算方法研究的对象和特点
计算方法实际上就是计算机上使用的数值计算方法，所 以这门课程又称为数值计算方法或数值分析。它是专门研究 求解各种数学问题的数值计算方法。现在，由于大多数科学 计算都比较复杂，人工计算无法完成；而计算机科学的迅速 发展和广泛应用提供了解决这些复杂问题的新途径。
计算方法第五章4-5节
i 0
i
n i
求解时与梯形法（2.7）相同，要用迭代法方可算出 yn 1 .
p p i
yn 1
a
i 0
yn i h bi f n i ,
i 1
（4.1） （2.7）
yn 1 yn
h 2
[ f ( xn , y n ) f ( xn 1 , yn 1 )],
xn
到
积分求得.
10
也可以利用(4.4)由 c1
cr 0
p
推出， 对比
yn 1 yn h bi f n i
i 1
与
yn 1
cq
p
1 q!
p q
p q 1
{ [ ( i ) ak 1 q ( i ) 1
p i 0 i 1 i 1
若b1
0
，则令 c1
cr 0
来求得
b0 , b1 , , bp
11
.
以
p 2 为例，由
c1 c2 c3 0
，根据
b1 b0 b1 b2 1, 2(b1 b 2b2 ) 1, 1 3( b1 b 4b2 ) 1, 1
3
1
h 12 h
4
2
24 h
5
3
720
106 f n 2 19 f n 3 )
17
例6 用四阶Adams显式和隐式方法解初值问题
y y x 1, y (0) 1.
取步长 h 0.1. 解 本题
f n yn xn 1, xn nh 0.1n
（1.1） （5.2） （1.2）
西安交大计算方法A考点总结【1-9章】
k
x* xk 0
计算方法 A 知识点总结 仅供参考[2014 级化机]
矩阵收敛的充要条件是 lim
k
A* Ak 0
lim Bk 0 谱半径 B 1
k
2、迭代法的一般格式 3、雅克比迭代
xk 1 Bxk g （注：B 是个对角元素均为 0 的方阵）
i 1 n bi aij xjk 1 aij xjk ） j 1 j i
SOR 迭代格式（加松弛因子 w） ： xi 变形为 xSOR
k 1 k 1 1 xk xG S
k 1
xik rik 1 / aii
改进平方根法：A=LU=LDLT 比平方根法多了 5、追赶法（三对角方程组） 本质是三对角矩阵的 LU 分解。 6、向量范数
x
非负性；齐性；三角不等式。
x1 x
2
元素绝对值之和； 元素平方和的平方根； 元素绝对值的最大值；
x
7、矩阵范数
A
非负性；齐性；三角不等式；相容性。
A1 A2
列范数（第 1 到第 n 列元素绝对值之和的最大值） 谱范数（ AT A 的特征值的最大值的平方根） 行范数（第 1 行到第 n 行元素绝对值之和之和的最大值）
Dxk 1 1 Dxk Exk 1 Fxk b
1）迭代法收敛的充分条件：迭代矩阵 B 的范数 2）迭代法收敛的充要条件： lim B
k k
B 1
0 谱半径 B 1
3）超松弛迭代法收敛的必要条件是： 0 2
计算方法 A 知识点总结 仅供参考[2014 级化机]
第一章 1、误差的来源与分类：模型误差、观测误差、截断误差、舍入误差。 2、准确到 n 位小数：
x* xk 0
计算方法 A 知识点总结 仅供参考[2014 级化机]
矩阵收敛的充要条件是 lim
k
A* Ak 0
lim Bk 0 谱半径 B 1
k
2、迭代法的一般格式 3、雅克比迭代
xk 1 Bxk g （注：B 是个对角元素均为 0 的方阵）
i 1 n bi aij xjk 1 aij xjk ） j 1 j i
SOR 迭代格式（加松弛因子 w） ： xi 变形为 xSOR
k 1 k 1 1 xk xG S
k 1
xik rik 1 / aii
改进平方根法：A=LU=LDLT 比平方根法多了 5、追赶法（三对角方程组） 本质是三对角矩阵的 LU 分解。 6、向量范数
x
非负性；齐性；三角不等式。
x1 x
2
元素绝对值之和； 元素平方和的平方根； 元素绝对值的最大值；
x
7、矩阵范数
A
非负性；齐性；三角不等式；相容性。
A1 A2
列范数（第 1 到第 n 列元素绝对值之和的最大值） 谱范数（ AT A 的特征值的最大值的平方根） 行范数（第 1 行到第 n 行元素绝对值之和之和的最大值）
Dxk 1 1 Dxk Exk 1 Fxk b
1）迭代法收敛的充分条件：迭代矩阵 B 的范数 2）迭代法收敛的充要条件： lim B
k k
B 1
0 谱半径 B 1
3）超松弛迭代法收敛的必要条件是： 0 2
计算方法 A 知识点总结 仅供参考[2014 级化机]
第一章 1、误差的来源与分类：模型误差、观测误差、截断误差、舍入误差。 2、准确到 n 位小数：
西安交通大学计算方法C讲义--资料
计算方法（C）目录第1章绪论1.1 数值计算1.2 数值方法的分析1.2.1计算机上数的运算1.2.2算法分析第2章线性代数方程组2.1 Gauss消去法2.1.1消去法2.1.2主元消去法2.2 矩阵分解2.2.1Gauss消去法的矩阵意义2.2.2矩阵的LU分解及其应用2.2.3其他类型矩阵的分解2.2.4解三对角矩阵的追赶法2.3线性方程组解的可靠性2.3.1向量和矩阵范数2.3.2残向量与误差的代数表征2.4解线性方程组解的迭代法2.4.1基本迭代法2.4.2迭代法的矩阵表示2.4.3收敛性第3章数据近似3.1 多项式插值3.1.1插值多项式3.1.2Lagrange插值多项式3.1.3Newton插值多项式3.1.4带导数条件的插值多项式3.1.5插值公式的余项3. 2 最小二乘近似3.2.1 最小二乘问题的法方程3.2.2 正交化算法第4章数值微积分4.1 内插求积，Newton-Cotes公式4.1.1Newton-Cotes公式4.1.2复化求积公式4.1.3步长的选取4.1.4Romberg方法4.1.5待定系数法4.2数值微分4.2.1插值公式方法4.2.2Taylor公式方法(待定系数法)4.2.3外推法第5章非线性方程求解5.1 解一元方程的迭代法5.1.1简单迭代法5.1.2Newton法5.1.3割线法5.1.4区间方法5.2 收敛性问题5.2.1简单迭代——不动点5.2.2收敛性的改善5.2.3Newton法的收敛性5.2.4收敛速度第1章绪论1.1数值计算现代科学的发展，已导致科学与技术的研究从定性前进到定量，尤其是现代数字计算机的出现及迅速发展，为复杂数学问题的定量研究与解决，提供了强有力的基础。
通常我们面对的理论与技术问题，绝大多数都可以从其物理模型中抽象出数学模型，因此，求解这些数学模型已成为我们面临的重要任务。
一、本课程的任务：寻求解决各种数学问题的数值方法——如何将高等数学的问题回归到初等数学（算术）的方法求解——了解计算的基础方法，基本结构（否则只须知道数值软件）——并研究其性质。
计算方法课件1(崔丽鸿)
§1.3 绝对误差和相对误差
一．绝对误差 /* absolute error */
设
称
x
——准确值，x * ——近似值。
*
*
e( x ) x x 为 x 的绝对误差(简称误差) | e( x ) | 为 x * 的绝对误差限。
二．相对误差 /* relative error */
14/47
§1.1 引言
算法影响计算的精度
例2
令
设多项式为 ( x-2)9 , 我们来计算其在区间 [1.92, 2.08]上的值。
p(x) = ( x-2)9 q(x) = x9 – 18 x8 + 144 x7 – 672 x6 + 2016 x5 4032 x4 + 5376 x3 – 4608 x2 + 2304 x - 512
NY
BJ
以上是一个病态问题
/* ill-posed problem*/ 关于本身是病态的问题，还是留给数学家去头痛吧！
30/47
蝴蝶效应是气象学家洛伦兹1963年提出来的。其大意 为：一只南美洲亚马孙河流域热带雨林中的蝴蝶，偶 尔扇动几下翅膀，可能在两周后引起美国德克萨斯引 起一场龙卷风。
数值分析
理学院
崔丽鸿
教材：西安交通大学出版社
《计算方法》
作者：邓建中
2/47
主要参考书
1.《数值分析基础教程》,
李庆杨,
高等教育出版社,
2001年第1版
3/47
主要参考书
2.《数值方法和MATLAB实现与应用》, （美） Gerald Recktenwald 著 伍卫国 万群 张辉 等译, 机械工业出版社,
西安交通大学计算方法(C)讲义
资料范本本资料为word版本，可以直接编辑和打印，感谢您的下载西安交通大学计算方法(C)讲义地点：__________________时间：__________________说明：本资料适用于约定双方经过谈判，协商而共同承认，共同遵守的责任与义务，仅供参考，文档可直接下载或修改，不需要的部分可直接删除，使用时请详细阅读内容计算方法（C）目录第1章绪论1.1 数值计算1.2 数值方法的分析计算机上数的运算算法分析第2章线性代数方程组2.1 Gauss消去法消去法主元消去法2.2 矩阵分解Gauss消去法的矩阵意义矩阵的LU分解及其应用其他类型矩阵的分解解三对角矩阵的追赶法线性方程组解的可靠性向量和矩阵范数残向量与误差的代数表征解线性方程组解的迭代法基本迭代法迭代法的矩阵表示收敛性第3章数据近似3.1 多项式插值插值多项式Lagrange插值多项式Newton插值多项式带导数条件的插值多项式插值公式的余项3. 2 最小二乘近似3.2.1 最小二乘问题的法方程3.2.2 正交化算法第4章数值微积分4.1 内插求积，Newton-Cotes公式Newton-Cotes公式复化求积公式步长的选取Romberg方法待定系数法数值微分插值公式方法Taylor公式方法 (待定系数法)外推法第5章非线性方程求解5.1 解一元方程的迭代法简单迭代法Newton法割线法区间方法5.2 收敛性问题简单迭代——不动点收敛性的改善Newton法的收敛性收敛速度第1章绪论1.1数值计算现代科学的发展，已导致科学与技术的研究从定性前进到定量，尤其是现代数字计算机的出现及迅速发展，为复杂数学问题的定量研究与解决，提供了强有力的基础。
通常我们面对的理论与技术问题，绝大多数都可以从其物理模型中抽象出数学模型，因此，求解这些数学模型已成为我们面临的重要任务。
本课程的任务：寻求解决各种数学问题的数值方法——如何将高等数学的问题回归到初等数学（算术）的方法求解——了解计算的基础方法，基本结构（否则只须知道数值软件）——并研究其性质。
计算方法课件
x g(x)
（2） 构造迭代公式
xk1 g(xk ), (k 0,1,2,)
在有根区间【a,b】上取一点 x0 (初始近似根)作为方程的近似值，代 入上面公式右端，求得 x1 g(x0 ) ，在把 x1 作为预测值，得到
x2 g(x1), 如此反复进行下去，得到一个近似根的序列
| g(x) | q 1
则迭代公式 xk1 g(xk ) 对于任意初值 x0 [a,b] 均收敛于方程
x g(x) 在区间 [a,b] 上的惟一根 x*, 且有如下误差估计式
q
qk
| x * xk | 1 q | xk xk 1 | 1 q | x1 x0 |
二. 误差
1. 误差的来源 模型误差：由于数学建模过程中往往要忽略一些次要的因 素而产生的，它是实际问题的客观量与其理论数学模型 精确解之间的差。（不讨论）
观测误差：在数学模型中的数据如果是从观测得到的，由 此产生的误差叫做观测误差。（不讨论）
截断误差（方法误差）：数学模型的精确解与近似算法的 解之间的差成为该算法的截断误差。
断 f (x) 的符号，逐步将有根区间缩小，直至有根区间足够的小，便求 出满足精度要求的近似根。
a x*
b
a
x*
b
■
bk
ak
bk 1
ak1 2
ba 2k
令
xk
1 2
(ak
bk ),
则
lim
k
xk
x*
误差估计式： | x * xk | (bk ak ) / 2 (b a) / 2(k1)
（3） 若 | x1 x0 | , 则停止计算；否则 x0 x1, 转（2）。
（2） 构造迭代公式
xk1 g(xk ), (k 0,1,2,)
在有根区间【a,b】上取一点 x0 (初始近似根)作为方程的近似值，代 入上面公式右端，求得 x1 g(x0 ) ，在把 x1 作为预测值，得到
x2 g(x1), 如此反复进行下去，得到一个近似根的序列
| g(x) | q 1
则迭代公式 xk1 g(xk ) 对于任意初值 x0 [a,b] 均收敛于方程
x g(x) 在区间 [a,b] 上的惟一根 x*, 且有如下误差估计式
q
qk
| x * xk | 1 q | xk xk 1 | 1 q | x1 x0 |
二. 误差
1. 误差的来源 模型误差：由于数学建模过程中往往要忽略一些次要的因 素而产生的，它是实际问题的客观量与其理论数学模型 精确解之间的差。（不讨论）
观测误差：在数学模型中的数据如果是从观测得到的，由 此产生的误差叫做观测误差。（不讨论）
截断误差（方法误差）：数学模型的精确解与近似算法的 解之间的差成为该算法的截断误差。
断 f (x) 的符号，逐步将有根区间缩小，直至有根区间足够的小，便求 出满足精度要求的近似根。
a x*
b
a
x*
b
■
bk
ak
bk 1
ak1 2
ba 2k
令
xk
1 2
(ak
bk ),
则
lim
k
xk
x*
误差估计式： | x * xk | (bk ak ) / 2 (b a) / 2(k1)
（3） 若 | x1 x0 | , 则停止计算；否则 x0 x1, 转（2）。
计算方法上课用PPT课件
1. 方程组阶数n很大，例如n=20,计算机运算速度 1亿次/秒,用不好的方法,大约需算30多万年; 好方法不到一分钟。另外，有计算结果可靠性 问题。
2. 特征值定义 A x x ( x 0 ) A xx0(AI)x0 | AI|0
14
3. f ( x) 形式复杂时求根和求积分很困难。
4.线性微分方程易解， 如
“计算方法"研究对象与特点
“计算方法"是计算数学的一个分支，它研究用计算机求解数学问题的数
值计算方法及其软件实现.计算数学几乎与数学科学的一切
分支有联系，它利用数学领域的成果发展了新的更有效的
算法及其理论，反过来很多数学分支都需要探讨和研究适
用于计算机的数值方法.因此，"计算方法"内容十分广泛.但
实际问题 程序设计
数学问题 上机计算
提供计算方法 结果分析
12
基本的数学问题:
1.大型线性代数方程组Ax=b求解;
2.矩阵A的特征值和特征向量计算;
3.非线性方程 f ( x ) 0 求解(求根);
4.积分 b a
f
( x)dx计算;
5.常微分方程初值问题求解;
6.其它。
13
求精确解(值)一般非常困难。例如：
17
截断误差 在求解过程中，往往以近似替代， 化繁为简，这样产生的误差称为截断误差。
舍入误差 在计算机上运算时受机器字长的 限制，一般必须进行舍入，此时产生的误 差称为舍入误差。
18
3. 截断误差，如
sin xxx3 x5 ....,.. 3! 5!
7
数值计算方法或数值分析主要是研究如何 运用计算机去获得数学问题的数值解的理 论和方法.对那些在经典数学中,用解析方法 在理论上已作出解的存在,但要求出他的解 析解又十分困难,甚至是不可能的这类数学 问题,数值解法就显得不可缺少,同时有十分 有效.
2. 特征值定义 A x x ( x 0 ) A xx0(AI)x0 | AI|0
14
3. f ( x) 形式复杂时求根和求积分很困难。
4.线性微分方程易解， 如
“计算方法"研究对象与特点
“计算方法"是计算数学的一个分支，它研究用计算机求解数学问题的数
值计算方法及其软件实现.计算数学几乎与数学科学的一切
分支有联系，它利用数学领域的成果发展了新的更有效的
算法及其理论，反过来很多数学分支都需要探讨和研究适
用于计算机的数值方法.因此，"计算方法"内容十分广泛.但
实际问题 程序设计
数学问题 上机计算
提供计算方法 结果分析
12
基本的数学问题:
1.大型线性代数方程组Ax=b求解;
2.矩阵A的特征值和特征向量计算;
3.非线性方程 f ( x ) 0 求解(求根);
4.积分 b a
f
( x)dx计算;
5.常微分方程初值问题求解;
6.其它。
13
求精确解(值)一般非常困难。例如：
17
截断误差 在求解过程中，往往以近似替代， 化繁为简，这样产生的误差称为截断误差。
舍入误差 在计算机上运算时受机器字长的 限制，一般必须进行舍入，此时产生的误 差称为舍入误差。
18
3. 截断误差，如
sin xxx3 x5 ....,.. 3! 5!
7
数值计算方法或数值分析主要是研究如何 运用计算机去获得数学问题的数值解的理 论和方法.对那些在经典数学中,用解析方法 在理论上已作出解的存在,但要求出他的解 析解又十分困难,甚至是不可能的这类数学 问题,数值解法就显得不可缺少,同时有十分 有效.
计算方法PPT
数 学 系 University of Science and Technology of China
第0章 绪论
计算方法的作用 计算方法的内容 误差 一些例子
DEPARTMENT OF MATHEMATICS
数 学 系 University of Science and Technology of China
学习的目的、要求
会套用、修改、创建公式 编制程序完成计算
课程评分方法 (Grading Policies)
总分 (100) = 平时作业(20)+上机作业(10)+期末 (70)
DEPARTMENT OF MATHEMATICS
数 学 系 University of Science and Technology of China
x 50.25 x 55.81
DEPARTMENT OF MATHEMATICS
数 学 系 University of Science and Technology of China
例：蝴蝶效应 —— 纽约的一只蝴蝶翅膀一拍，风和日丽的北 京就刮起台风来了？！
NY
BJ
以上是一个病态问题
/* ill-posed problem*/
内容 : 一次作业一个附件，并在内容中写出运行结果
DEPARTMENT OF MATHEMATICS
数 学 系 University of Science and Technology of China
内容
1、数值逼近－数学分析中的数值求解，如微分、积分、
b
a
f ( x)dx F (b) F (a)
DEPARTMENT OF MATHEMATICS
计算方法课件适合打印版
2 3
在F (2,3, -1, 2)中
2
(0.100 2 ) (0.110 2 ) 0.110 2
在F (2,3, -1, 2)中
(0.100 20 ) (0.111 20 ) 0.1101 21
(0.100 20 ) (0.110 21 ) 0.110 22
第1章 绪论
1.2 数值方法的分析
1.2 数值方法的分析
1.2.1 计算机上数的运算 浮点数运算结果产生误差的情况 (3)在浮点数系中数据的尾数字长t是有限
1.2.1 计算机上数的运算
浮点运算应注意
(4)在相同的指数条件下，两个数量相差较大的数字相 加（减）时，较小数的有效数字会被丧失
(1)避免产生大结果的运算，尤其是避免小数作为除数 参加运算； (2)避免“大”“小”数相加减； (3)避免相近数相减，防止大量有效数字损失； (4)尽可能简化运算步骤，减少运算次数。
算法SUM4(A,n,S) 将数组A中的数按其符号分成两组,分别按算法 SUM3求和,最后计算和S 1. 0->n1;0->n2; 2. For i=1,2,…,n 2.1 if a[i]>=0 then n1+1->n1; a[i]->b[n1]; else n2+1->n2; a[i]->c[n2]; 3. 调用SUM3(B,n1,S1); 4. 调用SUM3(C,n2,S2); 5. S1+S2->S
定义 通常以计算机完成操作 a+b*c ,即一次浮点加法 一次浮点乘法，所需的时间作为一个时间单位，称为 浮点运算，记为flop.
例1.3 设A1 , A2 , A3 , A4分别为10 20, 20 50,50 1,1100的矩阵,则按 结合律,有
在F (2,3, -1, 2)中
2
(0.100 2 ) (0.110 2 ) 0.110 2
在F (2,3, -1, 2)中
(0.100 20 ) (0.111 20 ) 0.1101 21
(0.100 20 ) (0.110 21 ) 0.110 22
第1章 绪论
1.2 数值方法的分析
1.2 数值方法的分析
1.2.1 计算机上数的运算 浮点数运算结果产生误差的情况 (3)在浮点数系中数据的尾数字长t是有限
1.2.1 计算机上数的运算
浮点运算应注意
(4)在相同的指数条件下，两个数量相差较大的数字相 加（减）时，较小数的有效数字会被丧失
(1)避免产生大结果的运算，尤其是避免小数作为除数 参加运算； (2)避免“大”“小”数相加减； (3)避免相近数相减，防止大量有效数字损失； (4)尽可能简化运算步骤，减少运算次数。
算法SUM4(A,n,S) 将数组A中的数按其符号分成两组,分别按算法 SUM3求和,最后计算和S 1. 0->n1;0->n2; 2. For i=1,2,…,n 2.1 if a[i]>=0 then n1+1->n1; a[i]->b[n1]; else n2+1->n2; a[i]->c[n2]; 3. 调用SUM3(B,n1,S1); 4. 调用SUM3(C,n2,S2); 5. S1+S2->S
定义 通常以计算机完成操作 a+b*c ,即一次浮点加法 一次浮点乘法，所需的时间作为一个时间单位，称为 浮点运算，记为flop.
例1.3 设A1 , A2 , A3 , A4分别为10 20, 20 50,50 1,1100的矩阵,则按 结合律,有
- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
特点
(1)速度快:Newton迭代法比简单迭代法收敛快
(2)由于要计算导数,因此计算量稍大
可以使用一点Newton迭代法
x ( k 1)
(k ) (k ) f ( x ) f ( x ) (k ) x( k ) x , k 0,1, 2... (k ) (0) f ( x ) f ( x )
因此,由连续函数的介值定理知, , 必有x* [a, b], 使 ( x* ) 0
即有x* ( x* ), 因此, ( x)在[a, b]中存在不动点x* (2)证明根唯一 __ __ __ 若 ( x)在[a, b]还有一个不动点 x ,使 x = ( x ),则
x x (x ) ( x) q x x x x
第5章 非线性方程求解 5.2 收敛性问题 5.2.1 简单迭代---不动点
证明: (1)证明有根 由条件(2)知,函数 ( x)连续 ,构造辅助函数 ( x) x ( x)
则 ( x)在[a, b]上也连续 ,由条件(1)知 ( a ) a (a) 0 同理 (b) b (b) 0
否则令x
(k )
x ,取I
( k 1)
(k )
=[ x , x( k 1) ]
( k 1)
__
(4)计算区间长度,若 x
x
x( k ) x( k 1) < , 则停止,令x , 输出 2
*
否则,令k k 1, 转(2)
第5章 非线性方程求解 5.2 收敛性问题 5.2.1 简单迭代---不动点
x( k 1) ( x( k ) ), k 0,1, 2,...
(5-3)
当给定初始近似值x(0)后,只需逐次计算函数值, 可获得迭代序列{x( k ) }
由于这一迭代过程十分简单, 因此称为简单迭代法
( x)称为迭代函数
迭代格式的获得 将(5 1)改写为x ( x), 可得到形如(5 - 3)的等价方程 不动点 若 ( x)为连续函数, 则当迭代式(5 - 3)产生的序列{x( k ) }收敛
演示
x(0) 0时收敛
x(0) 1时收敛
x(0) 1.5时不收敛
取x( k 1) ln( x( k ) 2), k 0,1, 2,... x(0) 1.5时收敛
当x(0) (1.841406, )时收敛 当x(0) (2, 1.841406)时不收敛
第5章 非线性方程求解
x
(k )
( k 1) ( k ) f ( x( k ) ) f ( x( k ) ) ( x x ) / 1 ( k 1) ( k 1) f ( x ) f ( x )
第5章 非线性方程求解 5.1 解一元方程的迭代法 5.1.4 区间方法
第5章 非线性方程求解 5.1 解一元方程的迭代法 5.1.3 割线法
为避免求导数值, 可以通过( x( k 1) , f ( x( k 1) ))和( x( k ) , f ( x( k ) ))
的线性插值公式近似f ( x)
f ( x( k ) ) f [ x( k 1) , x( k ) ]( x x( k ) ) 0 得到割线法的迭代式
则任取x [a, b],由迭代公式x
(0) ( k 1) (k )
(k ) 生成的序列 x =(x )
必收敛于在[a, b]中的唯一不动点x* = ( x* )
且有误差估计
x* x ( k ) 1 ( k 1) ( k ) q k (1) (0) x x x x 1- q 1- q
割线法的迭代公式可以写为
x( k 1) ( x( k ) , x( k -1) )
因此,称其为两步法方法 其速度比简单方法快,比Newton方法慢
当x( k ) , x( k 1) 接近于x*时, f ( x( k ) ), f ( x( k -1) )也较接近,因此会引起较大误差
x
( k 1)
并且满足 lim x ( k ) x*时, 有x* ( x* )
则x 为方程(5-1)的解,也称为 ( x)的不动点
*
k
第5章 非线性方程求解 5.1 解一元方程的迭代法 5.1.1 简单迭代法
例 5.1 设方程x e x - 2 0, 在[0,1]中有一解
得到迭代格式 ( x) x - f ( x), 取x(0) 0
x( k ) x* ( x( k 1) ) ( x* ) q x( k 1) x* q k x(0) x*
(k ) * 由于q 1 ,当k 时, qk 0,由此可知 x x 0
因此{x( k ) }收敛 且收敛于 ( x)在[a, b]中的唯一的不动点x*
x* lim x( k )
k
第5章 非线性方程求解 5.2 收敛性问题 5.2.1 简单迭代---不动点
(4)证明迭代格式误差 取m k , 有 x( m1) x( m) ( x( m) ) ( x( m1) ) q x( m) x( m1) q mk x( k 1) x( k )
思想: 迭代过程确定了一个区间的序列{I ( k ) } ,使每个区间I ( k )
都包含方程的一个解x* , 且区间I ( k )长度趋向于零 ,则当区间长度
足够小时, 必有区间中的任一点与x*的差小于给定误差值 , 则
可取区间中的任一点作为x*
要解决的问题: (1)初始区间的确定
满足f ( x0 ) f ( x1 ) 0的区间[ x0 , x1 ]都可以作为初始区间
例.非线性方程求解
演示
第5章 非线性方程求解 5.1 解一元方程的迭代法 5.1.2 牛顿迭代法
设第k次近似x( k )已知 ,以x( k )处的两个函数信息f ( x( k ) )和f ( x( k ) ) 构造Newton插值多项式
l ( x) f ( x( k ) ) f ( x( k ) )( x - x( k ) )
同理 x( k 1) x( k ) q k x(1) x(0)
x( m1) x( k ) ( x( m1) x( m) ) ( x( m) x( m1) )
x ( j 1) x( j )
q j k x ( k 1) x ( k ) 1 q mk 1 ( k 1) ( k ) 1 q mk 1 k (1) (0) x x q x x 1 q 1 q
f ( x) an xn an-1 xn-1 a1 x a0 0的方程,其中n 1
只有当f ( x)为不超过4次的多项式时,可使用公式求出其解
第5章 非线性方程求解 5.1 解一元方程的迭代法
可以使用迭代法获得f ( x) 0的近似解
需要讨论以下几个问题 (1)迭代格式的构造
* * * *
__
__
__
__
矛盾
因此,x*为唯一的一个不动点.
第5章 非线性方程求解 5.2 收敛性问题 5.2.1 简单迭代---不动点
(3)证明迭代格式收敛
由条件(1)知,任取x(0) [a, b] ,由迭代格式产生的x( k ) [a, b], k 0,1, 2,... 由条件(2)知,
x ( k 1)
(k ) f ( x ) x( k ) , k 0,1, 2,... (k ) ( k 1) f (x ) f (x ) x ( k ) x ( k 1)
或 x
( k 1)
(k ) ( k 1) x x (k ) x( k ) f ( x ), k 0,1, 2,... (k ) ( k 1) f (x ) f (x )
令m , q m-k 1 0 , x( m1) x* 得证
j k
m
+( x( k 1) x( k ) ) |
j k m
第5章 非线性方程求解 5.2 收敛性问题 5.2.1 简单迭代---不动点
分析
1 ( k 1) ( k ) (1) 由 x x x x 1- q 可以用相邻两步的近似误差来做事后估计 k q (2) 由 x* x( k ) x(1) x(0) 1- q 可以对误差进行先验估计 ,即根据误差确定迭代次数
在局部代替函数f ( x) ,有 f ( x( k ) ) f ( x( k ) )( x - x( k ) ) 0 得到 f ( x(k ) ) (k ) ( k 1) xx x f ( x ( k ) )
这一迭代方法称为Newton迭代法
其迭代函数为 f ( x) ( x) x f ( x)
(2)计算区间I [ x , x
k (k )
__
1 ] 的中点 x ( x( k ) x ( k 1) ) 2 __ __ __ (k ) ( k 1) ( k 1) (k ) (3)若f ( x ) f ( x ) 0, 则令x x ,取I =[x , x ],
( k 1) __
第5章 非线性方程求解
第5章 非线性方程求解 5.1 解一元方程的迭代法
一个变量的非线性方程是指形如以下形式的方程 f ( x) 0
其中,f ( x)是实变量x的非线性实单值函数
满足方程(5-1)的实数x* , 使f ( x* ) 0成立 ,称为非线性方程(5 1)的解
(5-1)
一元非线性方程是指f ( x)是多项式的非线性方程 ,即形如
x ( k 1) f ( x ( k ) ) x ( k ) f ( x ( k 1) ) , k 0,1, 2,... (k ) ( k 1) f (x ) f (x )