《计算方法》PPT课件.pptx

1计算方法1.1 1.1 计算方法研究的对象和特点计算方法研究的对象和特点 计算方法计算方法实际上就是计算机上使用的数值计算方法，所实际上就是计算机上使用的数值计算方法，所以这门课程又称为以这门课程又称为数值计算方法数值计算方法或或数值分析数值分析。它是专门研究。它是专门研究求解各种数学问题的求解各种数学问题的数值计算数值计算方法。现在，由于大多数科学方法。现在，由于大多数科学计算都比较复杂，人工计算无法完成；而计算机科学的迅速计算都比较复杂，人工计算无法完成；而计算机科学的迅速发展和广泛应用提供了解决这些复杂问题的新途径。发展和广泛应用提供了解决这些复杂问题的新途径。用计算机解决科学计算问题的一般过程，可以概括为：用计算机解决科学计算问题的一般过程，可以概括为：实际问题实际问题数学模型数学模型计算方法计算方法 程序设计程序设计上机计算上机计算结果分析结果分析32023/2/10主讲 韩光朋 由实际问题应用有关科学知识和数学理由实际问题应用有关科学知识和数学理论建立数学模型这一过程，通常作为论建立数学模型这一过程，通常作为应用数学应用数学的的任务。而根据数学模型提出求解的计算方法直到任务。而根据数学模型提出求解的计算方法直到编出程序上机算出结果，进而对计算结果进行分编出程序上机算出结果，进而对计算结果进行分析，这一过程则是析，这一过程则是计算数学计算数学的任务，也是数值计的任务，也是数值计算方法的研究对象。算方法的研究对象。因此，因此，数值计算方法就是研究用计算机解决数值计算方法就是研究用计算机解决数学问题的数值方法及其理论的科学数学问题的数值方法及其理论的科学。它的内容它的内容包括包括：误差理论、线性与非线性方程：误差理论、线性与非线性方程(组组)的数值的数值解、矩阵的特征值与特征向量计算、曲线拟合与解、矩阵的特征值与特征向量计算、曲线拟合与函数逼近、插值方法、函数逼近、插值方法、数值积分与数值微分、常数值积分与数值微分、常微分方程与偏微分方程数值解等。微分方程与偏微分方程数值解等。42023/2/10主讲 韩光朋1.1.把实际问题归结为数值问题把实际问题归结为数值问题制定数值问题的算法制定数值问题的算法得不到准确解时，设法得到近似解得不到准确解时，设法得到近似解解的特性（近似程度，敛散性）解的特性（近似程度，敛散性）各种方法的优缺点（速度，存储量）各种方法的优缺点（速度，存储量）各种方法的实用范围（收敛范围）各种方法的实用范围（收敛范围）计算方法要解决的几个问题：计算方法要解决的几个问题：（或研究的对象）（或研究的对象）52023/2/10主讲 韩光朋 把实际问题归结为数值问题把实际问题归结为数值问题 由于电子数字计算机的广泛使用，使越来越多的由于电子数字计算机的广泛使用，使越来越多的实际问题能归结为数值问题而得到解决（如：曲线拟合，数实际问题能归结为数值问题而得到解决（如：曲线拟合，数值逼近等）。值逼近等）。【什么是数值问题呢？什么是数值问题呢？所谓数值问题，指的是所谓数值问题，指的是由一组已知数据（又称输入数据）求出一组结果数据（又称由一组已知数据（又称输入数据）求出一组结果数据（又称输出数据），使得这两组数据之间满足预先指定的某种关系输出数据），使得这两组数据之间满足预先指定的某种关系（函数关系）的问题。（即由一组数求得另一组数）（函数关系）的问题。（即由一组数求得另一组数）】制定数值问题的算法制定数值问题的算法 【什么叫算法？什么叫算法？用完全确定的运算规则（包括用完全确定的运算规则（包括运算的逻辑顺序），对某一类数值问题的输入数据进行处理，运算的逻辑顺序），对某一类数值问题的输入数据进行处理，判断此数值问题是否有解，在解存在的情况下，给出输出数判断此数值问题是否有解，在解存在的情况下，给出输出数据，此种据，此种过程过程称为称为算法算法。】62023/2/10主讲 韩光朋得不到准确解时，设法得到近似解得不到准确解时，设法得到近似解 例例：求：求 已知数。已知数。由数学中的极限理论可知，由数学中的极限理论可知，（极限存在）（极限存在）于是于是 又又n只能有限，只能有限，x是近似值。是近似值。72023/2/10主讲 韩光朋在计算方法中，我们还将讨论：在计算方法中，我们还将讨论：解的特性（近似程度，敛散性）解的特性（近似程度，敛散性）各种方法的优缺点（速度，存储量）各种方法的优缺点（速度，存储量）各种方法的实用范围（收敛范围）各种方法的实用范围（收敛范围）82023/2/10主讲 韩光朋 一个好的方法应具有如下特点：一个好的方法应具有如下特点：第一第一，面向计算机，要根据计算机特点提供实际可行的，面向计算机，要根据计算机特点提供实际可行的有效算法，即算法只能包括加、减、乘、除运算和逻辑运有效算法，即算法只能包括加、减、乘、除运算和逻辑运算，是计算机能直接处理的。算，是计算机能直接处理的。第二第二，有可靠的理论分析，能任意逼近并达到精度要，有可靠的理论分析，能任意逼近并达到精度要求，对近似算法要保证方法的收敛性和数值稳定性，还要对求，对近似算法要保证方法的收敛性和数值稳定性，还要对误差进行分析，这些都建立在相应数学理论基础上。误差进行分析，这些都建立在相应数学理论基础上。第三第三，要有好的计算复杂性（即时间复杂性和空间复杂，要有好的计算复杂性（即时间复杂性和空间复杂性）；性）；时间复杂性时间复杂性好是指节省时间，好是指节省时间，空间复杂性空间复杂性好是指节省好是指节省存储量，这也是建立算法要研究的问题，它关系到算法能否存储量，这也是建立算法要研究的问题，它关系到算法能否在计算机上实现。在计算机上实现。第四第四，要有数值实验，即任何一个算法除了从理论上要，要有数值实验，即任何一个算法除了从理论上要满足上述三点外，还要通过满足上述三点外，还要通过数值试验数值试验证明是行之有效的。证明是行之有效的。92023/2/10主讲 韩光朋 例：例：一个简单的算法问题，设要对给定一个简单的算法问题，设要对给定 的的 求多项式求多项式 的值。的值。一种一种计算过程是直接计算计算过程是直接计算 的每一的每一项后逐项求和，这样要做项后逐项求和，这样要做 次乘法和次乘法和 次加法。次加法。102023/2/10主讲 韩光朋 另一种另一种算法就是先将算法就是先将 变形为如下形变形为如下形式：式：再由内层向外层计算，如设再由内层向外层计算，如设 ：就可以得到一个递推公式就可以得到一个递推公式k=1,2,n (1.3)这样的计算过程只需要计算这样的计算过程只需要计算n次乘法和次乘法和n次次加法。这种算法和上一种算法相比，不仅逻辑结构加法。这种算法和上一种算法相比，不仅逻辑结构简单，而且计算也明显地减少了。多项式求值的这简单，而且计算也明显地减少了。多项式求值的这种算法称为种算法称为秦九韶秦九韶算法（计算框图见图算法（计算框图见图1.2)。112023/2/10主讲 韩光朋1.2 误差的来源及其基本概念误差的来源及其基本概念1.2.1 误差来源：误差来源：用数值计算方法解决科学技术中的具体问题，用数值计算方法解决科学技术中的具体问题，一一般说都有误差，其来源有下列般说都有误差，其来源有下列四种四种：（注：注：由于人为的粗心大意造成的计算由于人为的粗心大意造成的计算错误错误，不算，不算误差误差）1.模型误差模型误差 数学描述和实际问题之间的误差数学描述和实际问题之间的误差 如：匀加速运动或自由落体运动公式如：匀加速运动或自由落体运动公式 略去了风力，空略去了风力，空气阻力等。气阻力等。2.观察误差观察误差 如：读表、读尺、读温度计。如：读表、读尺、读温度计。122023/2/10主讲 韩光朋3.3.截断误差截断误差 如：对如：对 x 0，求，求 。利用泰勒公式有。利用泰勒公式有取其部分和作为取其部分和作为 ，就产生了，就产生了截断误差截断误差。4.4.舍入误差舍入误差 由于计算机的字长有限，对超过位由于计算机的字长有限，对超过位数的数字要进行舍入，通常取与它们接近的数来表数的数字要进行舍入，通常取与它们接近的数来表示，由此产生的误差称为示，由此产生的误差称为舍入误差舍入误差。例如，我们通。例如，我们通常使用常使用2.718282.71828和和3.14163.1416来表示来表示 的近似值，的近似值，由此所产生的误差就是舍入误差。由此所产生的误差就是舍入误差。132023/2/10主讲 韩光朋 本课程仅讨论后两种误差（本课程仅讨论后两种误差（截断误差截断误差和和舍入误差舍入误差），讨论它们在计算过程中的传），讨论它们在计算过程中的传播和对计算结果的影响，研制能够控制误差播和对计算结果的影响，研制能够控制误差的影响且保证最终结果有足够精度的算法。的影响且保证最终结果有足够精度的算法。142023/2/10主讲 韩光朋1.2.2 误差的概念和有效数字误差的概念和有效数字1.1.绝对误差绝对误差定义定义1.11.1 设某数的精确值为设某数的精确值为 ，其近似值为，其近似值为 ，那，那么么 与与 之差之差称为近似值称为近似值 的的绝对误差绝对误差，简称，简称误差误差。一般地，某数的精确值一般地，某数的精确值 是不知道的，因而是不知道的，因而 不能求出，但往往可以估计出它的大小范围，亦即不能求出，但往往可以估计出它的大小范围，亦即可以确定一个正数可以确定一个正数 ，使得，使得此时，称此时，称 为为 的的绝对误差限绝对误差限。有时也用。有时也用表示近似值表示近似值 的精确值的精确值 或精确值或精确值 的所在范围。的所在范围。152023/2/10主讲 韩光朋2.2.相对误差相对误差 绝对误差反映不了一个近似数的准确程度。如：绝对误差反映不了一个近似数的准确程度。如：称一头大象误差十公斤，称一只蚂蚁误差一克，谁称一头大象误差十公斤，称一只蚂蚁误差一克，谁的近似程度好，显然大象的近似应好些。于是引进的近似程度好，显然大象的近似应好些。于是引进了了相对误差相对误差。记。记 称称 为近似值为近似值x的的相对误差相对误差，由于精确值，由于精确值 一一般不知道，实际计算时通常取般不知道，实际计算时通常取 作为近似值作为近似值x的相对误差。的相对误差。若能求出一个正数若能求出一个正数 ，使得，使得 ，则，则 称为近似值称为近似值x的的相对误差限相对误差限。它是无量纲的数，通常。它是无量纲的数，通常用百分比表示。用百分比表示。162023/2/10主讲 韩光朋 例：甲用米尺测量10M长的物体，所产生的绝对误差为2cm，乙用同一米尺测量1M长的物体，所产生的绝对误差为1cm，他们谁的测量精度好？解：根据上述定义可知，甲测量时的相对误差 乙测量时的相对误差可见甲测量结果比乙精确。172023/2/10主讲 韩光朋 3.有效数字 当准确数的位数很多时，我们常按“四舍五入”原则减少位数，得其近似数。并用“有效数字”来描述它。定义1.2 如果近似值 的误差限是某一位的半个单位，该位到 的第一位非零数字共有 位，则称 有 位有效数字。如果 的每一位都是有效数字，则称 为有效数。如 ：，有5位有效数字 ，有6位有效数字182023/2/10主讲 韩光朋 任何一个实数 ，经四舍五入后得到的近似值 都可以表示为如下标准形式：（其中m可为正负数）如果其绝对误差限满足则称近似值 具有n位有效数字。192023/2/10主讲 韩光朋例例1 1 设设 =0.0270=0.0270是某数是某数 经经“四舍五入四舍五入”所得，则所得，则 误差误差 不超过不超过 末位的半个单位，即：末位的半个单位，即：又又 ,故该不等式又可写为故该不等式又可写为 由有效数字定义可知由有效数字定义可知,有有3 3位有效数字，分别位有效数字，分别 是是 2,72,7，0 0。202023/2/10主讲 韩光朋例例2 2 又又 ,故该不等式又可故该不等式又可写为写为故故 有有3 3位有效数字，分别是位有效数字，分别是 3,2 3,2，8 8。由于由于 中的数字中的数字9 9不是有效数字不是有效数字,故故 不是不是有效数有效数。思考思考：有几位有效数字？有几位有效数字？有效数位为有效数位为3位位有效数位为有效数位为5位位有效数位为有效数位为4位位222023/2/10主讲 韩光朋4.有效数字与绝对误差、相对误差有如下关系:若某数 的近似值 有n位有效数字，那么这个近似值 的绝对误差限为 （注：由（1.4）式可知：m为整数位，n为小数位）由此看出：当m相同时，n越大，则m-n越小，从而有效位数越多，其绝对误差限越小。数据也就越精确。232023/2/10主讲 韩光朋 用式(1.4)表示的近似数 ，若具有n位有效数字，则其相对误差限为 则 至少具有n位有效数字。反之，若 的相对误差限为242023/2/10主讲 韩光朋证明 由知，若x具有n位有效数字，则从而（将上式代入）（参见（参见1.41.4式）式）252023/2/10主讲 韩光朋 反之，若x的相对误差限为 所以x至少有n位有效数字。由(2)可以看出，有效位数越多，相对误差限就越小，精确度也就越高。262023/2/10主讲 韩光朋 1.2.3 初值误差的传播 近似数参加运算后所得到的值也是近似值，含有误差，将这一现象称为误差传播。数值运算中误差的传播情况比较复杂，主要表现在：算法本身可能有截断误差；初始数据在计算机内的浮点表示一般有舍入误差；每次运算一般又会产生新的误差，并且传播以前已经引入的误差。因此，对误差进行准确分析是困难的，但也是很重要的。它关系到一个方法是否稳定,计算结果是否可靠。误差的传播与积累误差的传播与积累例例3：蝴蝶效应蝴蝶效应 纽约的一只蝴蝶翅膀一拍，风和日丽的北纽约的一只蝴蝶翅膀一拍，风和日丽的北京就刮起台风来了？！京就刮起台风来了？！NYBJ以上是一个病态问题以上是一个病态问题 282023/2/10主讲 韩光朋 1.3 1.3 选用和设计算法应注意的问题选用和设计算法应注意的问题 一般衡量算法的标准有：算法是否稳定，算法的运算次数和算法的存储量是否尽量少，同时还要考虑误差的传播等。选用和设计算法应注意如下几个问题:选用数值稳定的计算公式 防止两个相近数相减 防止大数“吃掉”小数 简化计算步骤，减少运算次数292023/2/10主讲 韩光朋1.3.1 选用数值稳定的计算公式选用数值稳定的计算公式 如果数值算法的计算舍入误差积累是可以控制的，则称其为数值稳定的；反之，称为数值不稳定的。例：计算定积分 （序列序列）利用分部积分法不难求得递推关系式为 公式推导302023/2/10主讲 韩光朋由式（1.16）可依次算出如下结果：(p011.c)注意到（注：从积分中按注：从积分中按x的最小和最大值提出的最小和最大值提出ex)?(1.17)由上面 的不等式可以看出312023/2/10主讲 韩光朋 因此按递推关系式（1.16）所算出的 计算值是错误的，严重偏离其准确值。发生这种现象的原因是因为 本身有不超过 的误差。设 是具有精确初始值 ，并按式（1.16)计算而得的，则有 由此可见，初始值微小的误差会随着计算步数的增加而迅速扩大，最终使计算结果失真。故算法式（1.16)不能控制误差的传播，是数值不稳定的。322023/2/10主讲 韩光朋如果将式（1.16）改写为（1.18)又注意到结合式（1.17）得由上面的估计式取开始按式（1.18）计算，有如下结果：（p012.c)332023/2/10主讲 韩光朋 由此可以看出按递推关系式（1.18）算出的 与 结果相差无几，已精确到小数点后第四位。分析误差的传播，则有 这表明，随着计算步骤的增加，初始误差可以得到控制，于是可知算法（1.18）式是数值稳定的。公式推导342023/2/10主讲 韩光朋1.3.2 防止两个相近数相减防止两个相近数相减 在数值计算中若有两个相近的数相减，则这两个数的前几位相同的有效数字会在它们之差中消失，从而使有效数字的位数减少。如果遇到两个相近的数相减运算，可考虑对公式进行处理，避免减法。例如，当例如，当 很大时，下两式应作如下处理：很大时，下两式应作如下处理：352023/2/10主讲 韩光朋1.3.3 1.3.3 绝对值太小的数不宜作除数绝对值太小的数不宜作除数 算法语言中已讲过，在机器上若用很小的数作除数会溢出停机，而且当很小的数稍有一点误差时，对计算结果影响很大。例如：362023/2/10主讲 韩光朋 1.3.4 防止大数防止大数“吃掉吃掉”小数小数 例：设a=63281312，b=0.1，c=0.9，求a,b,c之和。如果按（a+b)+c 次序来编制程序，此时按照加法浮点运算的对阶规则，应有 在八位的计算机上计算时，上式后面的两个数在计算机上变为了“机器零”，被“吃掉”。其结果为63281312。如果改变计算次序为（b+c)+a，则有（0.10.9）63281312 163281312 63281313。这样就避免了小数被大数“吃掉”的现象。372023/2/10主讲 韩光朋1.3.5 简化计算步骤，减少运算次数简化计算步骤，减少运算次数 对于同一个问题的计算，可以有不同的计算方法，如计算 的值，如果逐个相乘，则要计算254次乘法；但如果写成 只要做14次乘法运算就可以完成。由此可见，如果方法选择得当，则不仅能减少计算次数，提高计算速度，也可以简化逻辑结构，减少误差积累，从而达到提高计算精度的目的。382023/2/10主讲 韩光朋 误差问题是计算方法中既重要而又困难的课题，本章介绍了误差来源及相关基本概念，同时还给出设计算法时应注意的问题，这对今后学习是必须的。习题4.要使 的相对误差不超过 至少需要保留多少位有效数字？所有至少要保留5位有效数字。10 二月 2023第40页在许多科学技术和工程计算等实际问题中，常常会遇到求解非线性方程的问题。例如例如:求n次代数方程 的根；或求由三角函数、指数函数和对数函数等组成的超越方程。例如例如:求超越方程 的解。这些都可表示为求非线性方程 的根，或称为求非线性方程的解，即求函数 的零点。方程 的根可以是实数，也可以是复数；00111=+-axaxaxannnnL10 二月 2023第41页根的概念给定方程给定方程f(x)=0，如果有，如果有使得使得 f()=0，则，则称称为为f(x)=0 的的根根或或 f(x)的的零点零点.设有正整数设有正整数m使得使得 f(x)=(x-)mg(x),且且 g()0；则当；则当m 2 时，称时，称为为f(x)=0的的 m重根重根；当当m=1时，称为时，称为f(x)=0的的单根单根.本章只讨论本章只讨论实根实根的求法的求法.10 二月 2023第42页求根一般步骤 （1 1）确定所给方程存在多少个根）确定所给方程存在多少个根.（2 2）进行根的隔离，找出每个有根区间）进行根的隔离，找出每个有根区间(参考清参考清华大学出版，靳天飞主编华大学出版，靳天飞主编计算方法计算方法）。）。有根区间有根区间内的任一点都可看成是该根的一个近似值。内的任一点都可看成是该根的一个近似值。（3 3）逐步把近似根精确化，直到足够精确为止）逐步把近似根精确化，直到足够精确为止.本章主要讨论本章主要讨论单根单根问题。问题。求根的方法很多，如：求根的方法很多，如：二分法二分法（又称对分法）、（又称对分法）、牛顿法牛顿法（又称切线法）、（又称切线法）、双点弦截法双点弦截法（又称快速弦截（又称快速弦截法）、法）、迭代法迭代法等。等。10 二月 2023第43页2.12.1二分法二分法10 二月 2023第44页10 二月 2023第45页10 二月 2023第46页10 二月 2023第47页三、二分法的定义、计算步骤与框图三、二分法的定义、计算步骤与框图 1.定义定义2.02.0 象方法介绍那样，通过将区间a,b对分，逐步缩小根的范围而求出方程f(x)=0的实根的方法称为二分法，也称为对分法。2.计算步骤计算步骤 输入有根区间的端点a、b及预先给定的容许精度e；计算 ；若f(a)f(b)0,则bx，转向下一步；否则ax,转向下一步；若|b-a|e，则输出方程满足精度要求的值x，否则转向。10 二月 2023第48页3.3.程序框图与程序实例程序框图与程序实例 程序框图程序框图 图图2.22.2表示了用二分法表示了用二分法求方程求方程 f(x)=0(x)=0的根上机实的根上机实习编制程序的框图。习编制程序的框图。程序实例：程序实例：我们用我们用C C语言编制了用语言编制了用二分法求方程二分法求方程 根的程序，程序文本及计根的程序，程序文本及计算结果可见第八章程序实算结果可见第八章程序实例例2.2.10 二月 2023第49页10 二月 2023第50页10 二月 2023第51页2.2 2.2 迭代法迭代法本节分三步介绍：一.迭代法的基本思想二.迭代法需要解决的两个基本问题 （如何选取初值，何时停机）三.迭代法的计算步骤和计算框图 10 二月 2023第52页10 二月 2023第53页思考：如何选取初值？思考：如何选取初值？10 二月 2023第54页10 二月 2023第55页二二.迭代法需要解决的两个基本问题迭代法需要解决的两个基本问题 1.如何选取初始近似值 、以及迭代函数g(x)，才能保证按迭代公式 求出的迭代序列 收敛？2.当迭代序列 收敛时，用计算机如何决定迭代过程结束？10 二月 2023第56页2.2.2 迭代法的收敛条件（解决第一个问题）定理2.1 设迭代函数g(x)在区间a,b上具有一阶导数，且满足：存在正数L1时称为时称为超线性收敛超线性收敛；p=2时称为时称为平方收敛平方收敛。显然，数显然，数p的大小反映了迭代法收敛的快慢，的大小反映了迭代法收敛的快慢，p越大则越大则收敛越快。因此，迭代法的收敛阶是衡量迭代法优劣的重收敛越快。因此，迭代法的收敛阶是衡量迭代法优劣的重要标志之一。要标志之一。10 二月 2023第67页10 二月 2023第68页10 二月 2023第69页10 二月 2023第70页10 二月 2023第71页2.3Newton 迭代法（略）10 二月 2023第72页10 二月 2023第73页3.Newton3.Newton迭代法收敛定理（定理迭代法收敛定理（定理 2.52.5）（略）（略）则则 Newton Newton 迭代法（迭代法（2.122.12）产生的数列）产生的数列收敛到根收敛到根。为例证明（其它情况类似）为例证明（其它情况类似）10 二月 2023第74页（略）（略）10 二月 2023第75页例例6 6（略）（略）解：设解：设用用 Newton Newton 迭代法求迭代法求10 二月 2023第76页10 二月 2023第77页xyxnXn+1Xn+2tn(x)tn+1(x)02.3 2.3 牛顿（牛顿（Newton)Newton)法法 解非线性方程 f(x)=0的牛顿(Newton)法，就是将非线性方程线性化的一种方法。牛顿法具有实用面广，收敛快等优点。2.3.1 方法介绍 所谓牛顿法，就是用f(x)=0的解的近似值xn(n=0,1,2,)的切线方程图2.4(2.11)作为f(x)的近似表达式，然后取tn(x)=0的解xn+1作为f(x)=0的解的进一步近似，如图2.4所示。由式(2.11)，令tn(x)=0就得到了牛顿法的迭代公式(2.12)10 二月 2023第78页 由图2.4可以看出，牛顿法实际上是在每一步都使用不同的切线方程去逼近非线性方程。因此，牛顿法也称为切线法，它是一种将非线性方程线性化的方法。由迭代格式(2.12)可知，牛顿法是一种特殊的迭代法，其迭代函数 在f(x)及其导数满足一定条件的情况下，通过选择适当的初始值x0，迭代格式(2.12)所产生的迭代序列xn将收敛。(2.13)10 二月 2023第79页2.3.2 牛顿法收敛的充分条件 定理2.5 设函数f(x)在闭区间a,b上存在二阶导数且满足条件：在区间a,b上保号；设 且 则牛顿迭代格式(2.12)产生的迭代序列 收敛于方程 f(x)=0的一个解 。（证明P32略）10 二月 2023第80页10 二月 2023第81页10 二月 2023第82页10 二月 2023第83页例6 设 c 为正实数，导出用牛顿法求 的公式，并证明迭代序列的误差 满足关系式 解 设 ；则 ，所以 由于 所以f(x)0在区间0,+1内有一正根。又由于在区间 内，若取 ，则 在区间 内满足定理2.5的条件，所以收敛的牛顿迭代式为 10 二月 2023第84页记 ，则有 *由例6中误差满足的关系式(2.14)，可得 对上式取极限可得 由此可知，在用牛顿法求 时是2阶收敛的。(2.14)10 二月 2023第85页 2.3.3 牛顿法的收敛阶 定理2.6 设函数f(x)充分光滑，对于方程f(x)=0：若在区间(a,b)内存在单根 ，则用牛顿法求 的近似解时是2阶收敛的。若在区间(a,b)内存在m(2)重根 ，则用牛顿法求 的近似解时是线性收敛的。（证明P35略）写出求10 二月 2023第86页 2.3.4 2.3.4 计算步骤和程序框图计算步骤和程序框图 牛顿法的计算步骤为：选定初值 ，计算 按公式 迭代，得新的近似值 ，并计算 对于给定的允许精度 ，如果 ，则终止迭代，取 ；否则 ，再转回步骤计算。图2.6给出了用牛顿法求非线性方程f(x)=0解的程序框图，其中N为设定的最大迭代次数。10 二月 2023第87页1k输出迭代失败标志结束开始输出x1输出奇异标志=图图2.610 二月 2023第88页f(x)x0-1-2112345687例7 求方程 的解。解 粗略地绘出函数的草图，如图2.7所示。图2.710 二月 2023第89页 对函数f(x)求导可得若取初值x0=3，用牛顿法求解例7的迭代格式为经计算可得：x1=1.15999,x2=0.189438,x5=0.783595,x6=0.783599.若只需6位有效数字，则 x60.783599。10 二月 2023第90页 在（2.18)式中，若取初值x0=8，经计算可得：x1=34.778107，x2=865.1519，。继续迭代可知，xn 随着n 的增大将无限增大，此时迭代格式(2.18)发散。例 7 说明，使用牛顿法求解非线性方程，初值x0的选择非常重要，选择得不好会引起迭代序列发散，求不出方程的近似解。本例还说明，定理 2.5 的条件仅是一个充分条件，当条件不满足时，仍有可能收敛。如取 x03 时，迭代格式收敛；但 f(3)=-1.4723660，由式(2.17)知 ，故不满足定理2.5中的条件条件。10 二月 2023第91页 2.3.5 2.3.5 双点弦截法（快速弦截法）双点弦截法（快速弦截法）在方程f(x)=0的根附近任取两初始近似根x0,x1，由迭代公式 (2.20)逐次逼近f(x)=0的根，这种求根算法称为弦截法.10 二月 2023第92页10 二月 2023第93页10 二月 2023第94页10 二月 2023第95页10 二月 2023第96页10 二月 2023第97页本章重点：对给定方程F(X)0构造的两种迭代函数G1(x)和G2(x)，判断其敛散性。习题习题10 二月 2023主讲：韩光朋9810 二月 2023主讲：韩光朋9910 二月 2023主讲：韩光朋1003.1 高斯高斯(Gauss)消去法消去法高斯消去法的基本思想：高斯消去法的基本思想：高斯消去法就是逐步消去变元的系数，将原方程组高斯消去法就是逐步消去变元的系数，将原方程组A Ax=b=b化为系数矩阵化为系数矩阵为三角形的等价方程组为三角形的等价方程组Ux=d，然后求解系数矩阵为三角形的方程组而得到，然后求解系数矩阵为三角形的方程组而得到原方程组解的方法。我们把逐步消去变元的系数，将原方程组化为以系数原方程组解的方法。我们把逐步消去变元的系数，将原方程组化为以系数矩阵为上三角形的等价方程组的过程称为矩阵为上三角形的等价方程组的过程称为消元过程消元过程；把求系数矩阵为上三；把求系数矩阵为上三角形方程组的过程称为角形方程组的过程称为回代过程回代过程。最初的求解线性代数方程组的高斯消去。最初的求解线性代数方程组的高斯消去法也称为法也称为顺序消去法顺序消去法，它是由消元过程和回代过程组成。，它是由消元过程和回代过程组成。10 二月 2023主讲：韩光朋10110 二月 2023主讲：韩光朋10210 二月 2023主讲：韩光朋10310 二月 2023主讲：韩光朋10410 二月 2023主讲：韩光朋10510 二月 2023主讲：韩光朋10610 二月 2023主讲：韩光朋10710 二月 2023主讲：韩光朋10810 二月 2023主讲：韩光朋10910 二月 2023主讲：韩光朋11010 二月 2023主讲：韩光朋11110 二月 2023主讲：韩光朋11210 二月 2023主讲：韩光朋11310 二月 2023主讲：韩光朋11410 二月 2023主讲：韩光朋11510 二月 2023主讲：韩光朋11610 二月 2023主讲：韩光朋117注意注意：全主元消去法应增加一个解向量的伴随向量，记录每次：全主元消去法应增加一个解向量的伴随向量，记录每次交换交换的信息。的信息。10 二月 2023主讲：韩光朋11810 二月 2023主讲：韩光朋11910 二月 2023主讲：韩光朋12010 二月 2023主讲：韩光朋1213.2 矩阵的三角分解（矩阵的三角分解（略，了解略，了解）（转（转3.5节节63屏）屏）10 二月 2023主讲：韩光朋12210 二月 2023主讲：韩光朋123（上标从1开始）10 二月 2023主讲：韩光朋12410 二月 2023主讲：韩光朋12510 二月 2023主讲：韩光朋12610 二月 2023主讲：韩光朋12710 二月 2023主讲：韩光朋128（见例（见例1 1）10 二月 2023主讲：韩光朋12910 二月 2023主讲：韩光朋13010 二月 2023主讲：韩光朋13110 二月 2023主讲：韩光朋13210 二月 2023主讲：韩光朋133上例10 二月 2023主讲：韩光朋13410 二月 2023主讲：韩光朋13510 二月 2023主讲：韩光朋13610 二月 2023主讲：韩光朋13710 二月 2023主讲：韩光朋13810 二月 2023主讲：韩光朋13910 二月 2023主讲：韩光朋14010 二月 2023主讲：韩光朋14110 二月 2023主讲：韩光朋14210 二月 2023主讲：韩光朋14310 二月 2023主讲：韩光朋14410 二月 2023主讲：韩光朋145主讲：韩光朋主讲：韩光朋10 二月 2023主讲：韩光朋14610 二月 2023主讲：韩光朋14710 二月 2023主讲：韩光朋14810 二月 2023主讲：韩光朋14910 二月 2023主讲：韩光朋15010 二月 2023主讲：韩光朋15110 二月 2023主讲：韩光朋15210 二月 2023主讲：韩光朋15310 二月 2023主讲：韩光朋15410 二月 2023主讲：韩光朋15510 二月 2023主讲：韩光朋15610 二月 2023主讲：韩光朋15710 二月 2023主讲：韩光朋15810 二月 2023主讲：韩光朋15910 二月 2023主讲：韩光朋1603.5 3.5 线性代数方程组的性态线性代数方程组的性态10 二月 2023主讲：韩光朋161（向量范数的计算（向量范数的计算方法）方法）10 二月 2023主讲：韩光朋162（略）（略）10 二月 2023主讲：韩光朋16310 二月 2023主讲：韩光朋164（说明三种范数等价，了解）（说明三种范数等价，了解）10 二月 2023主讲：韩光朋16510 二月 2023主讲：韩光朋1663.5.2 3.5.2 矩阵范数矩阵范数1.1.矩阵范数的定义矩阵范数的定义（利用向量范数定义矩阵范数）（利用向量范数定义矩阵范数）10 二月 2023主讲：韩光朋16710 二月 2023主讲：韩光朋1682.N2.N阶矩阵阶矩阵A A的范数具有下列基本性质的范数具有下列基本性质10 二月 2023主讲：韩光朋1693.3.矩阵范数的计算矩阵范数的计算10 二月 2023主讲：韩光朋170(此处将矩阵问题转换成此处将矩阵问题转换成 向量问题进行讨论）向量问题进行讨论）（略）（略）10 二月 2023主讲：韩光朋171（略）（略）10 二月 2023主讲：韩光朋172（求特征值）（求特征值）（得到谱半径）（得到谱半径）（重点）（重点）10 二月 2023主讲：韩光朋1733.5.3 3.5.3 线性方程组的性态线性方程组的性态10 二月 2023主讲：韩光朋174（直接展开并移项）（直接展开并移项）10 二月 2023主讲：韩光朋17510 二月 2023主讲：韩光朋176（定理（定理3.5说明说明误差与条件数误差与条件数有关）有关）10 二月 2023主讲：韩光朋17710 二月 2023主讲：韩光朋17810 二月 2023主讲：韩光朋179（定义条件数）（定义条件数）10 二月 2023主讲：韩光朋1804.4.关于方程组性态的判断关于方程组性态的判断（定义什么叫（定义什么叫“病态病态”和和“良态良态”方程组）方程组）10 二月 2023主讲：韩光朋18110 二月 2023主讲：韩光朋1823.5.4 3.5.4 方程组近似解可靠性判别法方程组近似解可靠性判别法（能否用余向量或残量来判断，不能）（能否用余向量或残量来判断，不能）10 二月 2023主讲：韩光朋18310 二月 2023主讲：韩光朋18410 二月 2023 主讲 韩光朋1854.1 4.1 三种基本的迭代法三种基本的迭代法 4.1.1 Jacobi 4.1.1 Jacobi迭代法迭代法 (1.公式的推导公式的推导,2.Jacobi迭代法的矩阵形式迭代法的矩阵形式,3.Jacobi迭代法的缺陷迭代法的缺陷)1.1.公式的推导公式的推导10 二月 2023 主讲 韩光朋18610 二月 2023 主讲 韩光朋187 对于n阶方程组Ax=b,假定系数矩阵A的对角元 (i=1,2,n)时，类似于(4.3)式的推导，可得雅可比迭代格式为：10 二月 2023 主讲 韩光朋188 在一定条件下，对任意初始向量 ，按迭代公式(4.4)求出的向量序列的极限存在且等于方程的解。这种用迭代格式(4.4)求线性代数方程组近似解的方法称为雅可比迭代法雅可比迭代法，也称简单迭代法简单迭代法。10 二月 2023 主讲 韩光朋1892.Jacobi2.Jacobi迭代法的矩阵形式迭代法的矩阵形式10 二月 2023 主讲 韩光朋19010 二月 2023 主讲 韩光朋1913.Jacobi3.Jacobi迭代法的缺陷迭代法的缺陷10 二月 2023 主讲 韩光朋1924.1.2 4.1.2 高斯赛德尔高斯赛德尔(Gauss Seidel)(Gauss Seidel)迭代法迭代法1.迭代公式迭代公式（将（将4.3式作一点改进，得到下式：）式作一点改进，得到下式：）10 二月 2023 主讲 韩光朋1932.2.用矩阵形式表示用矩阵形式表示10 二月 2023 主讲 韩光朋194（重点）（重点）10 二月 2023 主讲 韩光朋19510 二月 2023 主讲 韩光朋19610 二月 2023 主讲 韩光朋1973.3.程序框图程序框图10 二月 2023 主讲 韩光朋198（参看（参看4.84.8式）式）4.1.3 4.1.3 超松弛迭代法超松弛迭代法(SOR(SOR方法方法)（要求了解）（要求了解）（预算一次）（预算一次）10 二月 2023 主讲 韩光朋199（重算一次）（重算一次）（将两步并为一步）（将两步并为一步）10 二月 2023 主讲 韩光朋2002.2.用矩阵形式表示用矩阵形式表示10 二月 2023 主讲 韩光朋2013.SOR3.SOR方法的程序框图方法的程序框图10 二月 2023 主讲