数值分析 各章重点 公式整理
- 格式:docx
- 大小:188.21 KB
- 文档页数:9
第一章 绪论误差来源:模型误差、观测误差、截断误差(方法误差)、舍入误差ε(x )=|x −x ∗|是x ∗的绝对误差,e =x ∗−x 是x ∗的误差,ε(x )=|x −x ∗|≤ε,ε为x ∗的绝对误差限(或误差限) e r =ex =x ∗−x x为x ∗ 的相对误差,当|e r |较小时,令 e r =ex ∗=x ∗−x x ∗相对误差绝对值得上限称为相对误差限记为:εr 即:|e r |=|x ∗−x||x ∗|≤ε|x ∗|=εr绝对误差有量纲,而相对误差无量纲若近似值x ∗的绝对误差限为某一位上的半个单位,且该位直到x ∗的第一位非零数字共有n 位,则称近似值 x ∗有n 位有效数字,或说 x ∗精确到该位。
例:设x=π=3.1415926…那么x ∗=3,ε1(x )=0.1415926…≤0.5×100,则x ∗有效数字为1位,即个位上的3,或说 x ∗精确到个位。
科学计数法:记x ∗=±0.a 1a 2⋯a n ×10m (其中a 1≠0),若|x −x ∗|≤0.5×10m−n ,则x ∗有n 位有效数字,精确到10m−n 。
由有效数字求相对误差限:设近似值x ∗=±0.a 1a 2⋯a n ×10m (a 1≠0)有n 位有效数字,则其相对误差限为12a 1×101−n由相对误差限求有效数字:设近似值x ∗=±0.a 1a 2⋯a n ×10m (a 1≠0)的相对误差限为为12(a 1+1)×101−n 则它有n 位有效数字令x ∗、y ∗是x 、y 的近似值,且|x ∗−x|≤η(x )、|y ∗−y|≤η(y)1. x+y 近似值为x ∗+y ∗,且η(x +y )=η(x )+η(y )和的误差(限)等于误差(限)的和2. x-y 近似值为x ∗−y ∗,且η(x +y )=η(x )+η(y )3. xy 近似值为x ∗y ∗,η(xy )≈|x ∗|∗η(y )+|y ∗|∗η(x)4. η(xy )≈|x ∗|∗η(y )+|y ∗|∗η(x)|y ∗|21.避免两相近数相减2.避免用绝对值很小的数作除数 3.避免大数吃小数 4.尽量减少计算工作量 第二章 非线性方程求根1.逐步搜索法设f (a ) <0, f (b )> 0,有根区间为 (a , b ),从x 0=a 出发, 按某个预定步长(例如h =(b -a )/N )一步一步向右跨,每跨一步进行一次根的搜索,即判别f (x k )=f (a +kh )的符号,若f (x k )>0(而f (x k -1)<0),则有根区间缩小为[x k -1,x k ] (若f (x k )=0,x k 即为所求根), 然后从x k -1出发,把搜索步长再缩小,重复上面步骤,直到满足精度:|x k -x k -1|< 为止,此时取x *≈(x k +x k -1)/2作为近似根。
数值分析重点公式下面是一些数值分析中的重点公式:1.最大值和最小值:- 最大值:记作 max(a, b) 表示 a 和 b 中较大的值。
- 最小值:记作 min(a, b) 表示 a 和 b 中较小的值。
2.线性插值:-线性插值:对于给定的两个点(x1,y1)和(x2,y2),如果希望在这两个点之间的x值为x的位置计算对应的y值,可以使用线性插值:y=y1+(y2-y1)*((x-x1)/(x2-x1))。
3.数值微分:-前向差商:用f'(x)≈(f(x+h)-f(x))/h的形式近似表示函数f(x)在点x处的导数,其中h是一个小的正数。
-后向差商:用f'(x)≈(f(x)-f(x-h))/h的形式近似表示函数f(x)在点x处的导数。
-中心差商:用f'(x)≈(f(x+h)-f(x-h))/(2*h)的形式近似表示函数f(x)在点x处的导数。
4.数值积分:-矩形法则:使用函数在每个小矩形中的平均值作为矩形高度来计算定积分的近似值。
-梯形法则:使用底边为区间长度的梯形面积的一半来计算定积分的近似值。
-辛普森法则:使用函数在每个小区间上的平均值和两个端点值的加权平均来计算定积分的近似值。
5.数值解线性方程组:-高斯消元法:将线性方程组转化为上三角矩阵,然后通过回代求解各个未知数。
-LU分解:将线性方程组的系数矩阵分解为一个下三角矩阵L和一个上三角矩阵U,再通过回代求解各个未知数。
-追赶法(托马斯算法):适用于解三对角系数矩阵的线性方程组,通过追赶的方式求解。
6.数值解非线性方程:-二分法:通过计算函数在区间端点的值的符号来确定函数在区间内的根的存在,并迭代缩小区间直至满足精度要求。
-牛顿法:通过迭代逼近函数的根,在每一步迭代中使用切线来逼近根的位置。
-弦截法:通过迭代逼近函数的根,在每一步迭代中使用割线来逼近根的位置。
7.数值解常微分方程:-欧拉方法:使用函数在当前点的导数值来估计下一个点的函数值。
第一章绪论1.数值运算的误差估计2.绝对误差、相对误差与有效数字3.避免误差的相关问题病态问题与条件数算法的数值稳定性数值运算中的若干原则第二章非线性方程求根1.不动点迭代格式不动点迭代格式的构造、计算全局收敛性判断局部收敛性与收敛阶判断(两个方法)2.Newton迭代格式、计算及几何意义局部收敛性及收敛阶(单、重根)非局部收敛性判断(两个方法)3.Steffensen迭代格式及计算(具有)二阶的局部收敛性4.Newton迭代的变形求重根的迭代法(三种方法)避免导数计算的弦割法(两种方法)Newton下山法*5.二分法计算预先估计对分次数第三章解线性方程组的直接法1.矩阵三角分解法及其方程组求解 直接三角分解法及其分解的条件平方根法(Cholesky 分解)追赶法列主元三角分解法* 2.Gauss 消去法Gauss 主元素消去法(列主元素消去法、全主元素消去法) Gauss 顺序消去法3.方程组的性态与误差分析 向量和矩阵的范数(基础知识) 方程组解的相对误差估计 矩阵的条件数 病态方程组的求解*第四章解线性代数方程组的迭代法1.迭代法的基本理论简单迭代法格式的构造、收敛性判断以及方程组的求解Gauss—Seidel迭代法格式的构造、收敛性判断以及方程组的求解2.三种迭代法的构造、收敛性判断以及方程组的求解Jacobi迭代法基于Jacobi迭代法的Gauss—Seidel迭代法逐次超松弛迭代法①掌握简单迭代收敛性判断的方法。
设B为迭代矩阵,如果||B||<1,则用||B||判断迭代的收敛性比用ρ(B)<1更为方便,但此结论仅为充分条件。
如果||B||≥1,判断迭代的收敛性需考察ρ(B)<1是否成立。
如果需证明迭代发散,则需证明ρ(B)≥1。
②简单迭代法的收敛快慢,依赖于迭代矩阵谱半径的大小。
当ρ(B)<1,迭代次数k≥(mln10)/(-lnρ(B)),则迭代矩阵谱半径越小,收敛越快。
第一章1霍纳(Horner )方法: n a 1-n a 2-n a ……2a 1a 0a输入=c+ n b *c c b n *1- c b *3 c b *2 c b *1n b 1-n b 2-n b 2b 1b 0bAnswer P (x )=0b该方法用于解决多项式求值问题P (x )=n a n x +1-n a 1-n x +2-n a 2-n x +……+2a 2x +1a x +0a2 注:p ˆ为近似值绝对误差:|ˆ|pp E p -=相对误差:|||ˆ|p pp R p -=有效数字:210|||ˆ|1d p p pp R -<-= (d 为有效数字,为满足条件的最大整数) 3 Big Oh(精度的计算): O(h ⁿ)+O(h ⁿ)=O(h ⁿ);O(h m )+O(h n )=O(h r ) [r=min{p,q}]; O(h p )O(h q )=O(h s ) [s=q+p]; 第二章2.1 求解x=g(x)的迭代法 用迭代规则,可得到序列值{}。
设函数g 。
如果对于所有x ,映射y=g(x)的范围满足y , 则函数g 在内有一个不动点; 此外,设定义在内,且对于所有x ,存在正常数K<1,使得,则函数g 在内有唯一的不动点P 。
定理2.3 设有(i )g ,g ’,(ii )K 是一个正常数,(iii )。
如果对于所有如果对于所有x 在这种情况下,P 成为排斥不动点,而且迭代显示出局部发散性。
. 波尔查诺二分法(二分法定理)<收敛速度较慢>试值(位)法:<条件与二分法一样但改为寻求过点(a,f(a))和(b,f(b))的割线L 与x 轴的交点(c,0)>应注意越来越小,但可能不趋近于0,所以二分法的终止判别条件不适合于试值法.牛顿—拉夫森迭代函数:)(')()(1111-----==k k k k k p f p f p p g p 其中k=1,2,……证明:用泰勒多项式证明第三章线性方程组的解法 对于给定的解线性方程组Ax=b一Gauss Elimination (高斯消元法 )第一步Forward Elimination 第二步 BackSubstitution二LU Factorization第一步 A = LU 原方程变为LUx=y ;第二步 令Ux=y,则Ly = b 由下三角解出y ; 第三步 Ux=y,又上三角解出x ;三Iterative Methods (迭代法)2n n 22221211n n 1212111b x a x a x a b x a x a x a =+++=+++nn nn 22n 11n 2n n 22221211n n 1212111b x a x a x a b x a x a x a b x a x a x a =+++=+++=+++初始值四 Jacobi Method1.选择初始值2.迭代方程为五Gauss Seidel Method1.迭代方程为00201,,,n x x x 00201,,,n x x x nnk n nn k n k n n k n k nn k k kn n k k a x a x a x a bx a x a x a bx a x a x a b x )()()(1122111222121212111212111--++++++-=++-=++-=k k k kn n k k kn n k k a x a x a bx a x a x a bx )()(1112221121212111212111++++++++-=++-=2.选择初始值 判断是否能用Jacobi Method 或者GaussSeidel Method 的充分条件(绝对对角占优原则)第四章 插值与多项式逼近·第一节 泰勒级数和函数计算一些常用函数的泰勒级数展开:for all x for all x for all x -1 -1for00201,,,nx x x定理4.1(泰勒多项式逼近)设,而是固定值。
数值分析知识点总结说明:本文只提供部分较好的例题,更多例题参考老师布置的作业题和课件相关例题。
一、第1章 数值分析与科学计算引论1. 什么是绝对误差与相对误差?什么是近似数的有效数字?它与绝对误差和相对误差有何关系?相对误差限:**r re ε=的一个上界。
有效数字:如果近似值*x 的误差限是某一位的半个单位,该位到*x 的第一位非零数字共有n 位,就说x *共有n 位有效数字。
即x *=±10m ×(a 1+a 2×10-1+…+a n ×10-(n-1)),其中a 1≠0,并且*11102m n x x -+-≤⨯。
其中m 位该数字在科学计数法时的次方数。
例如9.80的m 值为0,n 值为3,绝对误差限*211102ε-=⨯。
2. 一个比较好用的公式:f(x)的误差限:()***()'()()f x f x x εε≈ 例题:二、第2章插值法例题:5. 给出插值多项式的余项表达式,如何用其估计截断误差?6. 三次样条插值与三次分段埃尔米特插值有何区别?哪一个更优越?7. 确定n+1个节点的三次样条插值函数需要多少个参数?为确定这些参数,需加上什么条件?8. 三弯矩法:为了得到三次样条表达式,我们需要求一些参数:对于第一种边界条件,可导出两个方程:,那么写成矩阵形式:公式 1对于第二种边界条件,直接得端点方程:,则在这个条件下也可以写成如上公式1的形式。
对于第三种边界条件,可得:也可以写成如下矩阵形式:公式 2求解以上的矩阵可以使用追赶法求解。
(追赶法详见第五章)例题:数值分析第5版清华大学出版社第44页例7三、第3章函数逼近与快速傅里叶变换的正交多项式?什么是[-1,1]上的勒让德多项式?它有3.什么是[a,b]上带权()x什么重要性质?4.什么是切比雪夫多项式?它有什么重要性质?5.用切比雪夫多项式零点做插值点得到的插值多项式与拉格朗日插值有何不同?6.什么是最小二乘拟合的法方程?用多项式做拟合曲线时,当次数n较大时,为什么不直接求解法方程?例题请参考第3章书上的作业题和课件上的例题。
第一章非线性方程和方程组的数值解法I B j J L2) 迭代法收敛阶:lim 匚4 =c^0,若p=1则要求Occ<1F 闾。
3) 单点迭代收敛定理:定理一:若当x 乏[a,b ]时,④(X )E [a,b ]且®'(x)兰I cl, P [a,b ],则迭代格式收敛 于唯一的根;定理二:设 (x)满足:①x :」a,b 1时,:(x) := a,b I ②亦,x 2 亡 ta,b 1 有 ®(x L ) -申(x 2)| 兰I 为—x 2 ,0 <1 c l 则对任意初值x^a,b i 迭代收敛,且:« —xX j 卅一x1 -I I j僅 一 x 兰X i — Xo1 -I定理三:设(x)在〉的邻域内具有连续的一阶导数, 且「'(:•):::1,则迭代格式具有局部收 敛性;定理四:假设 (x)在根〉的邻域内充分可导,则迭代格式x;:(x j )是P 阶收敛的=0,j =1,|l(, P-1,心(:)=0( Taylor 展开证明)f (x),4) Newton 迭代法:x+=x - —-,平方收敛f (x)5) Newton 迭代法收敛定理:设f (x)在有根区间La, b 1上有二阶导数,且满足:①: f (a)f(b) ::0 ; ②: f (x) = 0,x b,b 1 ;③: f 不变号,x •〔a,b 11)二分法的基本原理,误差:b -a④:初值x0•〔a,b 】使得f (x) f (x) ::: 0 ;则Newt on迭代法收敛于根〉。
f i-X26)多点迭代法: f (X i )f (X i ) f(X i 」)X j 1 — XjX 1X jf(X i ) — f(X i 」) f(X i ) — f(X i1) — f(X 1)—f(x)Xi —X 」收敛阶: PJ '5 2 7) Newton 迭代法求重根(收敛仍为线性收敛) ,对Newt on 法进行修改①:已知根的重数「,x 卄“老(平方收敛) ②:未知根的重数: X i 1 二 X - '( ),u(x),(),:•为 f (x)的重根,则〉为 u(x)的单u (X i ) f (X)根。
第一章 非线性方程和方程组的数值解法 1)二分法的基本原理,误差:~12k b ax α+--<2)迭代法收敛阶:1lim0i pi ic εε+→∞=≠,若1p =则要求01c <<3)单点迭代收敛定理:定理一:若当[],x a b ∈时,[](),x a b ϕ∈且'()1x l ϕ≤<,[],x a b ∀∈,则迭代格式收敛于唯一的根; 定理二:设()x ϕ满足:①[],x a b ∈时,[](),x a b ϕ∈, ②[]121212,,, ()(),01x x a b x x l x x l ϕϕ∀∈-≤-<<有 则对任意初值[]0,x a b ∈迭代收敛,且:110111i i iii x x x llx x x lαα+-≤---≤-- 定理三:设()x ϕ在α的邻域内具有连续的一阶导数,且'()1ϕα<,则迭代格式具有局部收敛性;定理四:假设()x ϕ在根α的邻域内充分可导,则迭代格式1()i i x x ϕ+=是P 阶收敛的()()()0,1,,1,()0j P j P ϕαϕα==-≠(Taylor 展开证明)4)Newton 迭代法:1'()()i i i i f x x x f x +=-,平方收敛 5)Newton 迭代法收敛定理:设()f x 在有根区间[],a b 上有二阶导数,且满足: ①:()()0f a f b <; ②:[]'()0,,f x x a b ≠∈; ③:[]'',,f x a b ∈不变号④:初值[]0,x a b ∈使得''()()0f x f x <; 则Newton 迭代法收敛于根α。
6)多点迭代法:1111111()()()()()()()()()i i i i i i i i i i i i i i i f x f x f x x x x x f x f x f x f x f x f x x x -+-----=-=+----收敛阶:12P +=7)Newton 迭代法求重根(收敛仍为线性收敛),对Newton 法进行修改 ①:已知根的重数r,1'()()i i i i f x x x rf x +=-(平方收敛) ②:未知根的重数:1''()(),()()()i i i i u x f x x x u x u x f x +=-=,α为()f x 的重根,则α为()u x 的单根。
第一章误差限计算:第二章一多項式函數f(x),在 x = a 的泰勒展開式是:拉格朗日插值基函数:*).(|*)(|*))(( *)(x x f x f x f εε'≈的误差限得).(*)( ),,(,,,,,),,(*1***11**11k nk kn n n n x x f f x x f x x x x x x f εε∑=⎪⎪⎭⎫ ⎝⎛∂∂≈的误差限同理得的近似值为准确值,多元函数 ∏∏∏≠=≠=≠=--=--=nkj j jk j nkj j j knk j j jk x x x x x xxx x l 000)()()(∑==nk kky x lx P 0)()(.||)(||)(||)/( ),(||)(||)( ),()()( 2*2*1*2*2*1*2*1*1*2*2*1*2*1*2*1*2*1x x x x x x x x x x x x x x x x x εεεεεεεεε+≈+≈+=±牛顿插值其中an 为第n 阶差商,0阶差商即为f(x0). 余项 差商表差商导数求法牛顿前插公式(等距点适用)差分表)())(())(()()(110102010----++--+-+=n n n x x x x x x a x x x x a x x a a x N []0101(),,,()()()n n n R x f x x x x x x x x x x =---第三章最小二乘法拟合:直线拟合求a0和a1 多项式拟合⎪⎪⎩⎪⎪⎨⎧=+=+∑∑∑∑∑=====mi ii mi m i i i mi i m i i y x x a x a y x a m a 1110211110xa a x y 10)(+=0121011201ni n i i n i i n i i i n n n n i i n i i i a m a x a x y a x a x a x x y a x a x a x x y++⎧+++=⎪+++=⎪⎨⎪⎪+++=⎩∑∑∑∑∑∑∑∑∑∑∑第四章辛普森求积公式插值求积公式 (拉格朗日插值)插值求积公式余项复合梯形公式复合辛普森公式∑⎰=≈nk k kbax f Adx x f 0)()(⎰=bak k dxx l A )()()()()(0k k nkj j jk j k x x x x x x x x x l ωω'-=--=∏≠=[]⎰⎰+=-=+ban ba dxx n fdxx P x f f R )()!1()()()()()1(ωξ[]b a ,∈ξ⎥⎦⎤⎢⎣⎡++=∑-=)()(2)(211b f x f a f h T n k k n 121101()4()2()()6n n n k k k k h S f a f x f x f b --+==⎡⎤=+++⎢⎥⎣⎦∑∑高斯点及系数表将求积区间[a,b]变换到[-1,1]上数值求导两点公式数值求导三点公式22batabx++-=[]),(2)()(1)(1ξfhxfxfhxf''--='[]).(2)()(1)(11ξfhxfxfhxf''+-='),(3)]()(4)(3[21)(221ξfhxfxfxfhxf'''+-+-='),(6)]()([21)(221ξfhxfxfhxf'''-+-=').(3)](3)(4)([21)(2212ξfhxfxfxfhxf'''++-='第五章杜利特尔分解L y=b 求解 y U x=y 求解 x追赶法L y=b 求解 y U x=y 求解 x范数:⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=nn nn n n u u u u u u U l l l L222112112121,111⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡----11112122111122211n n nn nn n n u u u l a l al b a c b a c b a c b⎪⎩⎪⎨⎧-=-===+++1,,2,1/11111n i ua b l l c u b l i i i i ii i()111112m ax 8)m ax (m ax ((2()0ij nniji nj nijj ni TTTn A a Aa A A a A AA A A A A f E A A λλλ∞≤≤=≤≤=====-=-=∑∑矩阵范数计算公式定理对阶方阵(称为的行范数)称为的列范数)称为的范数)其中表示的最大特征值即常用的条件数第六章雅可比迭代高斯-塞德尔迭代(i=1,2,…,n k=0,1,2,…)收敛性)det(G I -λ求最大特征值)(G ρ,若>1,发散,若>1,收敛。
第七章牛顿迭代公式快速弦截法)()(||||||||)cond( ||||||||)cond( ||||||||)cond( min max 212211111A A A A AA A A A A AA A TTλλ=⋅=⋅=⋅=-∞-∞∞-ni x a b a x nij j k j ij i iik i,2,1)(11)()1(=-=∑≠=+)(1111)()1()1(∑∑-=+=++--=i j ni j k jijk jij i iik ixaxa b a x)()(1k k k k x f x f x x '-≈+)()()()(111--+---=k k k k k k k x x x f x f x f x x第八章幂法求特征值其中的VK 即是特征向量,miuK 为特征值(最大)第九章四阶龙格:向前欧拉法两步欧拉公式改进欧拉法预测 校正(2.9))1,2,(./),max(, , )0(10010 =⎪⎪⎩⎪⎪⎨⎧====≠-k a k k k k k k kμμv u v Auv v u v 计算,对任何非零初始向量⎪⎪⎪⎪⎪⎩⎪⎪⎪⎪⎪⎨⎧++++=+=+=+==++++)22(6),()2,()2,(),(43211314221312121k k k k h y y hk y x f k k h y x f k k hy x f k y x f k i i i i i i i i i i ),(1i i i i y x hf y y +=+),(211i i i i y x hf y y +=-+[]⎪⎩⎪⎨⎧++=+=++++),(),(2),(1111i i i i i i i i i i y x f y x f hy y y x hf y y梯形公式[]),(),(2111+++++=i i i i i i y x f y x f h y y。