数值计算方法课件

1数值计算方法2主要内容算法和误差非线性方程线性方程组特征值插值和拟合微分和积分微分方程3第一章算法与误差数值计算是求解数学问题的常用方法，随着计算机技术的飞速发展，数值计算方法在现代科学研究中的作用越来越广泛。数值计算的算法的研究越来越受到人们的重视。1)数值计算是应用数学一个重要分支,比如:微分方程,现代物理.2)新的数学,混沌理论(迭代法求非线性方程的根).与过去相比，现代数值计算方法有两个显著特点：1）数值计算的方法和理论都结合数字计算机的特点来研究。在进行算法研究时，注意算法与计算速度，计算内存消耗的关系2）在研究算法时，注重算法误差分析，注意数值解的收敛性和数值计算的稳定性问题。4模型：人们为了一定的目的，对客观事物的某一部分进行简化、抽象和提炼出来的替代物，它集中反映了客观事物中人们需要研究的那部分特征。数学模型：将模型的特征、内存规律用数学的语言和符号来描述的数学表述或数学结构。例如：人口增长模型求解问题的方法和步骤：•形成问题－明确待研究问题的特征、背景、用途•提出假设－抓住主要矛盾、忽略次要因素•建立模型－量化关键因素、建立数学结构和模型•算法求解－选择合适的算法对模型问题进行求解•算法分析－对算法的误差和灵敏度、稳定性进行分析•修正模型－对模型进行检验和修正•算法应用－应用成果解决实际问题51.1算法一、算法的概念当我们用数值计算方法求解一个比较复杂的数学问题时，常常要事先拟定一个计算方案，规划一下计算的步骤。所谓算法，就是指在求解数学问题时，对求解方案和计算步骤的完整而明确的描述。描述一个算法可以采用许多方法，最常用的一个方法是程序流程图。算法也可以用人的自然语言来描述。如果用计算机能接受的语言来描述算法，就称为程序设计。6二、算法的质量标准求解一个数学问题，可以采用不同的算法，比如：线性方程组，可用克莱姆法则，高斯消元法等多种方法求解。但是每一种方法的优劣不同，评价一个算法的好坏有以下几个标准：1）算法的计算量（时间复杂性）例1：用克莱姆法则求解一个n阶线性方程组时，需要计算（n+1）个n阶行列式的值。需要做次乘法。设n=20,若采用10亿/秒的计算机，要花费三十万年的时间进行计算。若用高斯消元法来求解，采用一个普通的586微机，在几分钟之内就可得结果。计算量的大小事衡量一个算法优劣的重要标准。2!nn7例2：天竺国，梵塔据说在东方的古国──印度土地上，有一座印度教的神庙，这庙有一块黄铜板，板上插著三根细细的、镶上宝石的细针，细针像菜叶般粗，而高就像成人由手腕到肘关节的长。当印度教的主神梵天在创造地球这个世界时，就在其中的一根针上从下到上放了半径由大到小的六十四片圆金片环，这就是有名的「梵塔」或称「汉内塔」（TowersofHanoi）。天神梵天要这庙的僧侣，把这些金片全部由一根针移到另外一根指定的针上，一次只能移一片，不管在什么情况下，金片环的大小次序不能变更，小金片环永远只能放在大金片环上面。只要有一天这六十四片的金环能从指定的针上完全转移到另外指定的针上，世界末日就来到。经过计算机的运算，移动的次数需18,446,744,073,709,551,615，一秒移动一次，大约需要5849亿年。82）算法的空间复杂性当使用计算机求解一个数学问题时，计算程序要占用许多工作单元（内存）。当计算一个大型的数学问题时，内存的消耗量是很大的。因此，算法占用内存数量的多少，是衡量算法优劣的另一个标准。3）算法逻辑结构的复杂性设计算法时应该考虑的另一个因素是逻辑结构问题，虽然计算机能自动执行极其复杂的计算程序，但是计算程序的每个细节都需要编程人员制定，因此算法的逻辑结构应尽量简单，才能使程序的编制、维修和使用比较方便。以上我们介绍了算法的一些基本概念。下面讨论数值计算中的另一个重要问题——误差。91.2误差在研究算法时，要进行误差分析，能估计误差的算法才是有实用价值的算法。一、误差的来源：引起计算误差的原因是多方面的。1）模型误差当解决一个工程实际问题时，常常需要用一定的数学表达式来描述，即建立一个数学模型。建立数学模型时，通常要根据实际需要做一些简化，忽略一些次要因素，是模型不致过分复杂，又能满足精度要求。这样建立起来的数学模型是客观现象的近似描述。这种近似必然产生误差。10212!!nxxxexn2）方法误差在计算过程中，由数学方法产生的误差，称为方法误差。例如，在计算指数函数的值时，常用到如下幂级数展开式：这是一个无穷级数。计算时，只能取有限项。2()12!!nnxxSxxn用有限项逼近无穷级数，会产生一个误差，这个误差是由数学方法产生的，所以是一种方法误差。113)舍入误差在计算过程中，当我们表示一个数时，常常只能取有限位。超出的尾数将会舍去，从而造成误差，这种误差称为舍入误差。舍入误差时我们数值计算中重点研究的对象，将贯穿整个课程之中。12二、误差的概念1）误差：某个量的真值与近似值的差的绝对值，称为近似值的误差，又称绝对误差，用e表示。exxxx—真值，—近似值，2）误差限在许多情况下，我们不知道某个量的真实值是多少，因此也不知道它的近似值的误差。但是我们能估计出误差不会超过某个确定的数值。这个数值就称为近似值的误差限。我们能用误差限定量的衡量一个近似值的误差。如果某近似值的误差限是ε，我们就说，在允许误差ε的条件下，近似值是准确的。133）有效数字我们还可以用有效数字的概念来说明一个近似值的准确程度。我们先介绍“四舍五入”的概念，四舍五入是数值计算时，取近似值的一种方法。若被舍去部分的头一位大于等于5时，就在所取数的末位加1；小于5时，就舍去。用四舍五入方法得到的近似值，称为有效数字。有效数字的末位到第一位非零数字的个数，称为该有效数字的位数。有效数字可用来表示一个近似值的准确程度，一个近似值的有效位数越多，这个近似值就越逼近真值。14由上面的有效数字的定义，我们能给出另外一种等价的定义。若近似值的误差小于某一位的半个单位，便称近似值准确到这一位。从这一位到第一个非零数字的个数就是近似值的有效位数。上述定义常用在数值计算的过程中，用来控制迭代的精度。151)3.142)3.14163)3.14150.00159260.005  2)0.000007ee1解：）是按四舍五入原则得到的，有三位有效数字。小于百分位上的半个单位。准确到百分位。从这一位到个位（第一位非零数字）有三位。有三位有效数字。30.00005小于万分位上的半个单位。准确到万分位。从万分位到个位有五位。有五位有效数字。例：圆周率π是一个无理数，π=3.14159265358979323…，考察下列近似值的有效位数。163）的万分位不是按四舍五入规则得到的，因此有四位有效数字，而不是五位有效数字。0.00009260.0005e小于千分位上的半个单位，从千分位到个位有四位。精确到千分位。3.1416有五位有效数字，准确到万分位。3.1415有四位有效数字，准确到千分位。这就是π的近似值采用3.1416而不采用3.1415的原因。171101101111100=1,2,3...enxnnxnnxnxExedxnExedxxnxedx三、算法与稳定性计算积分：解：用分部积分法11101nxnxedx1811110110111110011110110.367879441211(1)nnxxxxxEnEExedxxdeEexeedxeee或（n=2，3，...）这里取6位有效数字16521763290.367879160.127120120.264242170.110160130.207174nEEEEEEEEEE，计算的前个值8743985491180.118720140.170904190.068480150.145480xEEEEEEEE虽然被积函数xe在整个积分区间（0，1）是正的，可是计算的结果却是负的。1917213297*994.4121029!4.412100.16010.0684800.16010.EEEEEEEEe什么原因引起这么大的误差呢？计算机中唯一的舍入误差是在的舍入误差是，在计算时它乘了，在计算时中的误差又乘了+3，以此类推，的误差为：所以111009161nnnxnEEnnExedx（取三位有效数字）怎样避免这种不稳定的算法呢？改写递归关系式如下：（=,3,2）10110111nnxdxxnn202019199982019,01121201111112021101120212.5100nnEEEEEEEE当。如取的近似值为零，以它为起始值，则起始误差最大为。此误差在求时乘了，因此的误差最大为。的误差最大，为。时，起始误差已减小至。2019181817171616151514141310.0520110.050.05277781918110.05571900.05901761716110.06273220.06694771514EEEEEEEEEEEEE2113121211101110920110.07177330.07735221312110.08387710.09161231110EEEEEEEEE由于算法的稳定性，中的起始误差已经完全被抑制了。222.100,,20,,2fxabfxxabfafbabab第二章非线性方程二分法一、定理：设非线性方程，若：1）单调连续）＜则方程在有一个根二、基本思想：将分为相等的个小区间，计算小区间端点函数值，找出新的有根区间。重复上述过程，直到找到满足精度要求的根。23111ab2x222ab2x24*12211*233112*1111112122...1)2nnnnxxbabaxxbabanxxbaba三、误差估计：设近似根的误差限位则：第一次二分的误差））25111112balglg2nba令：解得：n二分法在迭代前可以确定迭代次数，但二分法的求解效率不高2632331()41001,2,10221lg110210.97lg211,fxxxn例题：求的根，x解：n取得下表：27x=1.36474609428例题的matlab程序：第一步先建立求根函数文件（efhans.m)：functionf=efhans(x)f=x^3+4*x^2-10;第二步建立M文件（efqgf.m)a=1;b=2;jingdu=0.0005;whileabs(b-a)jingdux=(a+b)/2;ifefhans(a)*efhans(x)0a=x;elseb=x;endendgen=(a+b)/22910*2.200,1,2...(3)limkkkkkfxxxxxkxxxx迭代法一、基本思路：设方程（1）其等价形式为（2）其迭代格式为，式中：为初值，为迭代函数。如果：*x为方程的根，则称迭代格式收敛30**1'1,1,**kkkkkxxxxxxabxxabxxxxxx二、定理：，迭代格式（3）收敛的充要条件是（4）（5）设为连续函数，　　　证：相减：****'**1,kkkkkxxxxxxxxxx由中值定理若是方程的根，则称为方程的不动点。*x*x*x31''***1*1*101*11)1max,lim0limkkkkk