数值分析知识点手册

数值分析知识点手册

・基础知识

・二进制/十进制转换

二进制表达+进制表达

…力2瓦斯……电2?+仇2，+M2°+b-i2~‘+6-22-2…

•十进制转换二进制

・整数部分：连续除以2记录余项.从小数点向左记录来记录余项0或1

・小数部分：连续乘以2记录余项。从小数点向右记录来记录余项0或1

・二进制转换十进制:直接按指数即可

・实数的浮点数表示

•浮点数：符号、尾数，指数

•(Normalized)浮点数表示

±1.励…bx2P

1精度|符号⑤|指数(M)尾数(N)|

单精度(32bit)1823

双精度(64bit)11152

长精度(80bit)11564

•机器精度1和最小的比1大的浮点数的距离定义为机器精度，记为Ejmach}

•双精度：E_{mach}

emach=2一52、2,2X10-16

・有效数字缺失

•舍入误差(roundingerror):上溢/下溢(overflowandunderflow)何忽略的加法/有效数字

的丢失:两个很相近数的相减

・相近的两个数字相减导致有效数字的丢失，需要等价形式变化(例如方程求根问题)

・求解方程

•二分法

・二分法的理论基础：令口(口)是区间［口,口］上的连续函数，满足□(□)□(口)<0,则函数□在该区间

上至少一个根，即存在口，满足□<口(口，以及口(口)=0

•误差分析:二分法得到的序列满足以下公式

b—a

\xn-r\<—

・如果误差小于0.5x10人{-口},称解精确到小数点后□位

・不动点迭代

•若□（口）=口，称□为函数□（口）的不动点

•不动点迭代算法：令口_0为初始值，□_{□+1}=□（n_□），口=0,L•，若迭代收敛,则收敛到一

个不动点。

・存在唯一性

•设口G□[□,口]且对任意口e[□,口]有口（口）G[□,□],则□在该区间上有Y不动点

・若同时□'（口）存在，且存在正常数口<1使得□'（口）<□,V□G（□,□）,则[口,口]区间上的不

动点是唯一的

•收敛性

•令□_□表示迭代第口步的误差，若下式成立，则该方法称为线性收敛，收敛速度为S

乡+1

lim—=S<1

i-*ooS[

・设口连续可微，□（□）=□,□=,□'（□）1<1,则对于一个足够接近口的初始估计，以速度口线

性收敛到不动点r

•迭代终止条件

.决定终止算法的条件，称终止条件

・绝对终止条件

]xi+1-xt\<rqj

・相对误差条件

\xi+i-Xi\/\xi+1\<TOL

•混合终止条件

I项+i-%il/max（|%i+J6）<TOL

・精度的极限

•后向和前向误差

・设口为函数口的根，即口（口）=o,设口_□是□的近似值。对于求根问题，近似口一口的后向误差

为|口（口_口）|,前向误差为|口-

・后向误差是描述问题（函数口）改变量的误差。前向误差是所求的解的误差

・设□为可微函数□的根，□(1■)=0,若f在r点的1阶导数、2阶导数……m-1阶导数为0,

而m阶导数非零，则称函数在□点有口重根

•1重根称为单根

・误差放大因子

•描述问题：令□为口(口)=0的根，假设对问题有一个小的变化口口(口)，求相对应根的变

化，即求△口使得口(口+△□)+□□(□+△0)=0

•根的敏感公式：令□为□(□)=0的根，□+△口为口(口)+□□(□)的根，则当口很小时，

△□«-□□(□)/□'(□)

・误差放大因子:相对前向误差/相对后向误差

g(r)一

r//(r)

•所有输入上的变化造成的最大误差放大，称为条件数

・高条件数问题称病态问题，否则称良态问题

・牛顿法和无梯度方法

・牛顿法

・用口_口点上切线的解作为迭代的下一步□一{口+1}

•令□_□表示第口步的误差，若满足以下条件，则称迭代二次收敛

M=lim<8

•定理：令□为二阶连续可微函数，满足□(口)=0和□(□)w0,则牛顿方法局部二次收敛，

误差满足：

..e/"(r)

hm-i+j1-=M=.、

i->82f(r)

•重根问题和改进的牛顿方法

・重根问题：牛顿方法不能二次收敛到重根。

•如果口(口)有(口+1)阶连续，包含口重根，则改进牛顿法□_{□+1)=-

收敛，具有二次收敛速度

・割线法

•思想：用差商替代牛顿法中的导数

・割线法

/(%)(4—々1)

Xi+i=Xi

f(.xt)-f(劭-1)

・超线性收敛：

a-1

/〃(r)

fif+1«

2f'(r)靖

a=(1+V5)/2«1.618

・割线法的推广

•试位方法：在割线法的基础上重新选择区间进行运算

・Muller方法：使用最后三个迭代值进行抛物线拟合

•逆二次插值:在Muller算法的基础上选择x=P(y)型的抛物线插值

•Brent方法：对给定口_□,□_□，使用逆二次方法

・后向误差得到改进

・包含根的区间至少减少一半

・割线法的收敛阶

•若□'(口),□"(□)*0,则近似误差

♦插值

.拉格朗日插值

・给定口个数据点，找到次数为口-1的插值多项式

•拉格朗日插值的一般形式

L(])=(工一工1)…(z-zi)(z-Z+)…(z—占)

_*一©)…(z*-zi)("-zQ…5—占)

Pn-1(z)=MLi(x)+…+y„Ln(x)

•多项式插值的主定理对□个不同点，(口」,口」),-,(□_□,□,□),存在并仅存在一个不高于口

-1次的多项式口(口)满足□(□_□)=□_0»

•牛顿差商

•差商

・零阶差商

f[x0]=f(x0)

•一阶差商

…上小"。]

七一/

・二阶差商

门1/［项，士］一"工。，项1

/［九o,/，々］二------------------

^2-^0

•n阶差商

〃阶差商：flx0,X“…,5］=旦上2匕但

•差商与节点顺序无关

・牛顿差商公式

3工)=£[工门+*4z](x-X|)+/CxiXix](x-,ri)(x-X2)

2—一:-3------------------------------

+/E-t|x：-13X4](X-X1)(T—X2)(z—Z3)/

._________+•••zK^Zfxi—Zi)…(工-zi).―

・插值误差分析

•经过(□!,□!),-,(□_□,□,□)的口-1阶插值多项式的误差是

•Hermite插值多项式:经过(C1,01),,(□□,□□),且在这些节点上的导数值口1','

给定，所得到的2口-1阶插值多项式

•龙格现象:插值次数越高，插值结果越偏离原函数的现象(解决：使用切比雪夫插值或者减少插

值点)

・切比雪夫插值

・减小误差多项式的分子：取极小时口一口(口)称为口阶切比雪夫多项式

(%-与)…-=F?马(%)

•切比雪夫多项式

・定义

Tn(x)=cos(narccos%)

•递归关系

To(%)=1,Ti(x)=%,

Tn+1M=2xTn(X)-Tn-l(x)

・□_□(□)为n次多项式，最高次项系数为2A(口-1)

・□_□(1)=1,□_□(-!)=(-1”口,最大绝对值为1

•□=cos(Darccos口)的零点为

(2i-1)7T

xi=~~y=L…'九

•=cos(Darccos口)的值在-1和1之间变化口+1次，这些极值点为

讥

Xi=cos——,i=0,…，n

n一

・三次样条

・分段多项式构成的插值函数称为样条

•三次样条的通常的端点条件

・s'(x0)=f0',s'(xn)=fn'

・s"(x0)=f0",s"(xn)=fn"

•s(x0)=s(xn)(j=0,1,2)

•额外的条件

•)自竺二域逢」注■在边界的拐点)b)非tfi结三次样条(在区间［0,2］和

5】的三次方程)

12345

c)抛物线■点方程d)钳制三次样条(在甬个■点花制为•率。)

・自然样条

Si=0,Sn.i=0

•曲率调整样条

Si=VltSn_1=v2

・钳制样条

Sj=处,S；_1=v2

•抛物线端点样条

cl1—0,d九一1=0

•贝塞尔曲线与最小一乘

.贝塞尔曲线

•主要思想：曲线参数化

•由端点和控制点可以确定一条三阶贝塞尔曲线

端点：♦——*（—%4,、—4）

控制点:（如力），（工3，、3）

四）=*+/>“+，、<+，/£

y（z）=ri+bvt+cvt~+4M乙

=3（X2—盯）

Cx=3（X3-X2）-瓦

dx=X4-X]-bx-cx

by=3（冷-yi）

c.v=3（户一Q）-by

dy=V4-JI-by-Cy.

・离散最小二乘逼近

•不一致方程组的求解，函数逼近：正交多项式

•针对不一致系统Ax=b,求解法线方程：A'Ax=A'b

・数据的最小二乘拟合模型:给定（□,□,□_□）,-,（□_□,）,找出最佳逼近的直线：口=口_0

•数据线性化:建立线性化的数据模型，例如：

.=任3）^^回g=1畛+C2t

•正交多项式

・最小二乘函数逼近：给定函数口，求P-口（口）使误差极小，称口_口（口）为该函数的最小二乘逼近多

项式,误差由以下公式给出

■1t-

b—

2

E=[[f（x）-Pn（x）]dx

•给定函数集合｛□<•,□_□｝,设对所有口G[□,□],只要口_0口_0（□）+-+□_□□_□（□）=

。就有系数皆为零，则该集合线性无关，否则该集合线性相关

•正交基:｛口.0,…，□_口｝为区间口□]上的关于权函数口（口）正交集合函数，若□一口=1,则称标准正

交

bHk

.

w(x)0)(x)Wk(x)dx=J=

・…为区间口□]上的关于权函数口的正交集合，则口(口)在该区间上的最小二乘逼近

为

n

6(%)=Wak(PkM

k=0

_—w(%)3晨%)/(%)dx_:w(%)0k(x)f(%)dx

kSal<PkM]2dx

・数值微分和积分

・数值微分

•只利用用口)来计算口'□□,口'',

•二点前向差分:h>0;二点后向差分:h<0

f(x+h)-/(g)

f'Qo)x0

h

•三点中心差分：

)(g+八)一/(须)-h)

f'M七-2h

・误差分析：Taylor展开

尸(珀=加山？三皿-华h.

•■二阶公式(三点中心差分公式)

・差分公式总结

•前向差分：口0,口0+h

f(x+h)~/(x)

----0----7-------0-,error=O\n)

•后向差分:DO,DO-fi

/3o)二/Qo-h)

error=O(h).

h~

•三点中心差分：DO-h,no,ao+ii

/(XQ+/?­)-/(Xp-/l)

error=O(/i2).

2h

・五点差分：00-2h,00-晨口0,DO+鼠口0+2h

f3)—2/i)—8f(xo-h)+8/(XQ+h)—/(①0+2h)

error=0(//)

12/i

•理查德森外推

•理查德森外推n阶公式口仇）：□h口"+□八八n

•外推公式

空包3—。出+1）

邛2n-1，，'/

・Newton-Cotes公式

•用低阶多项式来逼近待积分函数，用简单定积分代替

・梯形法则：区间［00,口1=DO+配两点拉格朗日插值公式

,,'x-xix-x0/"(ex)

〃为二加五二五+以力；+2!

P(x)dx=g(/(g)+/(xi))

E(x)dx

•辛普森法则：区间［口_0,D_2=口_0+2/i］三点拉格朗日插值公式（辛普森法的精度为3.）:

p(}=(:r-力)(才一也(二一-())(#一.运)"上()).一.-门)

(70-6Vl(6-®o)(xi-a：i)

)(即-X2)x2)"(数-x0)(x2-

(x—①o)Q—a:i)(x—X2)

E(r)=

3!

(0

f(x)dx=1(如+4如+y2)-^/(c)

・代数精度:最大的整数□使得数值积分方法对所有的□阶或更低阶多项式积分是精确的，称为口阶

（代数）精度

•复合牛顿-科特斯公式:将积分区间［a,b］等分成:□=口_0<0_1<口一2<<□_{□-!}<

=□

・复合梯形法则:m个连续的子区间上对梯形法则公式求和

£/（x）dx=•1•（"+%+2>y）-S濯丸/<c）

其中A=（6—以）/帆，c在a和6之间.

•复合辛普森公式：m个连续的子区间上对梯形法则公式求和

0（工出=:［g+y.,+4号+2卧'"（5.25）

其中c在a和6之间.

・开牛顿-科特斯公式

•中点公式

琮/•一）〃=⑵（%+9+//（。）

•复合中点公式

fafWdx=九鸵+9+”与〃（c）

・龙贝格积分

《数值分析》P239

•复合梯形法可表达为，令□=2A{D-l},cJ是h无关的，于是可以外推

|/（力业='1■（%+%+zgy）+cN+cH+qh6+•••

•步长序列的定义

h\=b-a

人2=—a）

乙

*

*

hi=奈"（6-a）

•R_{jl}是使用步长为hj的复合梯形法则

）,对于j=2,3,…，

Z，T

Rjt=2/（a+（2t-1）A；）

•R_{jk}公式

R_4iR,,i-R,T.I

K"-41—］

・自适应积分

•根据划分检测以判断是否复合精度需要继续计算

if|St..«-Sc.,tj-SCf.H|<3.TOL.（号一）

接受S【..,J+SSJ作为区间［a,6］上的近似

else

对于区间［a,c］和［c,句递归重复上面的步骤

end

・高斯积分

・高斯积分

，(5.44)

其中

G=JL.(x)cLru=1

系数G的值放在如上所述的表中，同时具有较高的精度.表5.1中的值一直给到〃=4.

•高斯积分表

»51高斯积分系数N阶勘让值多项式(5.44)的根x,以及系数c.

itWx.系数c.

-/I7T--0.577350269189631-1.00000000000000

2

7173-O.577350269189631*1.00000000000000

-y57s=-0.774596669241485/9-0.55555555555555

30-0.000000000000008/9-0.88888888888888

y57T-O.774596669241485/9-0.5SS5555555SS55

-0.861136311S9405-：V-■-0.34785484513745

180

-j!匕套庖--0.33998104358486丝舒度=0.65214515486255

J*叁晅7339981043S8486典捻图=0.6521451548625S

生Q晅-0.34785484S13745

8611363115940S

•在ab］区间上的高斯积分

,7（x）dx=1/八6二%+6+。）宁&

aJ一1、Z，Z

・方程组直接法

・高斯消去法

•写成增广矩阵的形式进行高斯消去过程

•主元:斜对角线元素为0

・主元为0导致高斯消去法终止

・高斯消去法的复杂度为口但3)

•消去的复杂度为2/303

•回代的复杂度为1/3于

.LU分解

・LU分解将系数矩阵A写成下三角矩阵□和上三角矩阵口的乘积，问题变为□□口=b

•LU分解方法

数值分析P72线代P171

•使用结论

•将矩阵□的从第□行减去第□行的□倍可表示为矩阵□一口口(-□)口,其中口一口□(-0)为主

对角为I,(□，⑴元素为一口，其他元素为0的矩阵

•-□)的逆(c)

・步骤

・确定A化为U的行变换

・把标出的元素除以主元以后放在L的左下方

•图示

•特殊的分解

・Doolittle分解:L的主元为1

・Crount分解:U的主元为1(可以通过LDU求得)

・LDU分解：L单位下三角矩阵，U单位上三角矩阵，D非奇异对角矩阵

IDU分制

在U中黑取出对角受湾D

18行等小对角元崇的

・choleski分解:L和U的主元相等

・误差来源

•向量和矩阵范数

・向量范数

・定义与性质

*||口||称为向量范数

•正性，||口||>0,等号当前仅当口=□时成立

.线性性，||口口||=|叶||口||

・三角不等式,II口+D||<II口II+||y||

・定义方式

・1-范数：向量元素绝对值之和

II训1=£区1

i=l

・2-范数：向量元素绝对值的平方和再开方

1同2=\£姆

\4=1

•8.范数：所有向量元素绝对值中的最大值

x|L=max\Xi|

t

・矩阵的范数

・定义与性质

・IHI称为口X口矩阵的范数

•正性，II口||20,等号当前仅当口=口时成立

•线性性，||口口||=|斗网|

・三角不等式，||口+n||<||口||+||口||

・相容性：||口口||<||口||中口||

•称II口-口||为两矩阵之间的距离

•定义方式

・1-范数：列和范数，即所有矩阵列向量绝对值之和的最大值

Il^lli=max£M』

3i=l

•2-范数：即A，A矩阵的最大特征值的开平方

11却2=

・8-范数：所有矩阵行向量绝对值之和的最大值

N

ll^lloo=maxV|aij|

*#1

・特征值、特征向量和谱半径

・特征多项式：□(X)=det(口-人口)

•特征值：特征多项式的零点

・特征向量：若特征值人满足口口=入口，口H0,则称□为特征向量

•谱半径:绝对值最大的特征值，口(□)=max|入|,人为口的特征值

・□(□)4||口||对任意算子范数成立

•误差放大和条件数

•误差放大因子:相对前向误差/相对后向误差

llxi—allg/llxlls

llrlloo/ll^lloo

・前向误差:解误差的无穷范数||口-La||

•后向误差：余项的无穷范数||口-

・条件数:方阵□的条件数cond(口)为最大的误差放大因子

•□X□矩阵□的条件数为cond(□)=||口||||口八(-1)||

・Hilbert矩阵:元素口口口=1/(口+□-1)

・PA=LU

•部分主元

・在消去第k列时，找到第p行，k<p<n,定位最大的a_pk,必要时交换第p行和第k行，

然后继续进行消元

•L的元素的绝对值不大于1

•置换矩阵

•□x□矩阵，其每行、每列仅以一个1,其他元素全为0

・置换矩阵基础定理：□为单位矩阵经过一组特定行交换以后的置换阵，贝11□□为矩阵口经过相

同行交换以后的矩阵

・PA=LU过程

•进行部分主元过程

・计算置换矩阵P

・0作为存储位置.在位置(i,j)的每个0里,保存用于消去该位置元素的乘子

・再次进行部分主元过程

・迭代法

•迭代方法

・Jacobi迭代方法

・D表示A的主对角线矩阵，L表示矩阵A的下三角矩阵(主对角线以下的元素)，U表示

上三角矩阵(主对角线以上的元素)

・A=L+D+U

・迭代过程：x_{k+l}=DA{-l}(b-(L+U)x)

•Gauss-Seidel迭代

•最近更新的未知变量的值在每一步中都使用

・x_{k+l}=DA{-l}(b-Ux_k-Lx_(k+l))

•SOR迭代

・迭代公式

*+1=

，)Bux^+fu

_»3=(O+wZ)-1[(1-3)。—,九=+3E)Tb.

•迭代法的收敛性

・严格对角占优矩阵：对角元比非对角元大

|a“|＞〉:|。灯|

•若□为严格对角占优矩阵，则Jacobi和Gauss-Seidel迭代收敛

・稀疏矩阵计算

・稀疏矩阵：很多元素都是0系数矩阵

•稀疏矩阵中的nA2个矩阵元素，只有0(n)个非零元素

•完全矩阵——直接法；稀疏矩阵——迭代法

•在存储空间、计算量具有优势

•对称正定矩阵

•对称正定矩阵

・对称矩阵：A'=A

•正定矩阵:X'Ax>0对任意x成立

・对称矩阵是正定矩阵当且仅当所有特征值是正数

・□是口X□对称正定矩阵，X是满秩n*m矩阵，n>=m,则X'AX对称正定

•任何对称正定矩阵的主子矩阵对称正定

・楚列斯基分解

•楚列斯基因子分解:口=R'R

・若口对称正定，则存在□满足口=n1R

•楚列斯基分解过程

数值分析P109

•最上面一行第一位数开方，剩下的元素除以第一个元素记为向量u

・在剩下的主子阵中减去外积U'u

•找到剩下的R

・共朝梯度法

・n元函数□(口)的梯度：f函数对每一个变量求导所组成的向量

▽/(工)=gradf(x)=圜聂,…，豪)

•□是□阶对称正定矩阵，口是方程组口口=口的解的充分必要条件是口是二次函数□(□)=1/2口

力□的极小点

Ax*=6<=>〃'*)=酵八为.

・令A是对称正定的n*n矩阵。对于两个n维向量v和w,定义A内积(v,w)_A=v'Aw,当A

内积为0时，向量v和w为共辗

・求解方法具体见数值分析P110页

•适用矩阵：大型稀疏矩阵，良态矩阵

・病态矩阵的预处理方法

•预条件子：一个和A足够接近的容易求逆的n*n的矩阵,形式是MA-lAx=MA-lb

•雅克比预条件子：M=D;MA-1=D，1,是对角线元素的倒数

•高斯-赛德尔预条件子：M=(D+L)DA-1(D+U)

・非线性方程组

・多元牛顿方法

•雅可比矩阵：多变量情况下的导数f

・多变量牛顿方法：x_{k+l}=x_k-（雅克比矩阵”-l*F（x_k）

・多变量牛顿方法求解:计算（雅可比矩阵）s=x_k的解，s是下一个迭代值

•Broden方法

•可以更好的近似估计，见数值分析P120

・特征值和奇异值

•特征值

・特征值问题等价于求特征多项式的根

•若□为□的特征值

•□□为□□的特征值

•□-□为口-□□的特征值

・□A□为□人口特征值

•口为对称矩阵，则

•所有特征值均为实数

•有□个线性无关特征向量

•存在正交矩阵□使得口,口口},其中□的第口列向量为对应于口_□的特征

向量

•Gerschgorin圆盘定理

•复平面上的圆

/?,=lzeC|lz-a.,1<y|a0|I

[得）

・□的所有特征值在区域所有的圆盘上，并且若□个圆盘的并集与剩余口一口个圆盘不交，则

该并集包含□个特征值

・特征值计算

・鬲法

・若|D_1|>|口_2|>->|□_□!>0,则可以用幕法求得最大的特征值口」

•与最大的特征值口」相关的向量我们称作占优特征向量

•幕迭代方法：考虑AAk*x的迭代方式，x在迭代过程中要时刻归一,不要太大

・反幕法

・可将幕法进行简单的修改得到更快的收敛

・反黑法：设口为口X口矩阵,特征值□」,•，口_n,则(□-□□)A{-1}(□H□□)有

特征值：l/(Ll-q),,l/(Ln-q),对应的特征向量保持不变

•使用幕法求(□-口口)7-1}(口X□□)的最大特征值，□一k此为矩阵□最接近口的特

征值

心…占

|4一1i内一q|

・瑞利商迭代

・瑞利商：口=(x'Ax)/(x'x),其中若x是特征向量的近似，贝卯是特征值的最优近似

雪)=等

•设□为口X口实对称矩阵，特征值人」>->A_Q,则

(4%,%)(Ax,%)

入1=max------,入八=min------

xeRn(%,%)XERn(x,x)

•可利用Rayleigh商估计最大特征值，瑞利商迭代对称矩阵三次收敛，一般则二次收敛

•QR分解方法计算特征值

・相似矩阵：口和□相似，若存在□使得口=□A{-i}ns

•相似矩阵具有相同的特征值

•QR算法

・方阵正交：Q'=QA{-1}

・若口为正交矩阵,口为向量,则：||Qx||_2=||x||_2

•QR分解的思想:若A=QR,Ax=b等价于Rx=Q'b

•数据求解与最小二乘拟合模型相同

•利用Gram-Schmidt正交化进行QR

・Schmidt正交化过程

・首先正交(使用投影办法)

R=a_也®nB

'(%A)(“4T)

・然后归T名即可

•QR分解过程

・先将A的列向量施密特正交化找到Q

・R=Q'A

・Householder变换

・Householder反射(变换)□'□=1,口长度为(！，□=□-2口口’

•Householder反射对称正交:口A{-1}=□'=口

・构造Householder变换:设口和口eCIA口具有相同的长度||口||_2=||Q||_2,则存在□使

得口=□-2口口’，满足□口=y

・迭代得到上海森伯格矩阵

•QR算法求特征值

・A是上海森