完整版北京航空航天大学数值分析课程知识点总结docx.docx
- 文档编号:9198144
- 上传时间:2023-05-17
- 格式:DOCX
- 页数:107
- 大小:130.71KB
完整版北京航空航天大学数值分析课程知识点总结docx.docx
《完整版北京航空航天大学数值分析课程知识点总结docx.docx》由会员分享,可在线阅读,更多相关《完整版北京航空航天大学数值分析课程知识点总结docx.docx(107页珍藏版)》请在冰点文库上搜索。
完整版北京航空航天大学数值分析课程知识点总结docx
1.2误差知识与算法知识
1.2.2绝对误差、相对误差与有效数字
设a是准确值x的一个近似值,记e
xa,称e为近似值a的绝对误差,简称误差。
如果|e|的一个上界已知,记为
,即|e|
,则称为近似值a的绝对误差限或绝对误差
界,简称误差限或误差界。
记er
e
xa,称er
为近似值a的相对误差。
由于x未知,实际上总把
e作为a的
x
x
a
e
xa
e的上界,即r
相对误差,并且也记为er
,相对误差一般用百分比表示。
a
a
r
|a|
称为近似值a的相对误差限或相对误差界。
定义设数a是数x的近似值。
如果a的绝对误差限时它的某一位的半个单位,并且从该位
到它的第一位非零数字共有n位,则称用a近似x时具有n位有效数字。
1.2.3函数求值的误差估计
~
设u
f(x)存在足够高阶的导数,
a是x的近似值,则u
f(a)是u
f(x)的近似值。
~
若f
'(a)0且|f''(a)|/|f'(a)|不很大,则有误差估计
e(u)
f'(a)e(a)
~
。
(u)
f'(a)
(a)
若f'(a)f''(a)...
f(k1)(a)
0,
f(k)(a)
0,且比值
~
f
(k)
(a)
k
e(u)
k!
e(a)
大,则有误差估计
。
f
(k)
(a)
~
k
(u)
(a)
k!
~
n
f(a1,a2,...,an)e(a)
e(u)
i
1
xi
i
对于n元函数,有误差估计
~
n
f(a1,a2
...,an)
(u)
(ai)
i
1
xi
f(k1)(a)/f(k)(a)不很
;若一阶偏导全为零或很
小,则要使用高阶项。
1.2.4算法及其计算复杂性
(1)要有数值稳定性,即能控制舍入误差的传播。
(2)两数相加要防止较小的数加不到较大的数中所引起的严重后果。
(3)要尽量避免两个相近的近似值相减,以免严重损失有效数字。
(4)除法运算中,要尽量避免除数的绝对值远远小于被除数的绝对值。
1.3向量范数与矩阵范数
1.3.1向量范数
定义定义在Rn上的实值函数?
称为向量范数,如果对于
Rn中的任意向量
x和y满足:
(1)正定性:
x
0,当且仅当
x0时,x
0;
1
(2)齐次性:
对任一数
k
R,有
kx
k
x;
(3)成立三角不等式:
x
y
x
y
。
定理1.1
对Rn中的任一向量
x
(x1,x2,...,xn)T
,记
n
x1
xi
i1
n
x2
xi2
i1
x
maxxi
1i
n
则?
1,?
2和?
都是向量范数。
定理1.2
设?
和?
是Rn上的任意两种向量范数,则存在与向量
x无关的常数m和
M(0 mx x M x,x Rn 1.3.2矩阵范数 定义定义在Rnn上的实值函数 ? 称为矩阵范数,如果对于 Rnn中的任意矩阵A和B满 足: (1)A 0,当且仅当A 0 时,A 0 ; (2)对任一数kR,有kAkA; (3)ABAB; (4)AB AB。 定义对于给定的向量范数 ? 和矩阵范数? ,如果对于任一个x Rn和任一个A Rnn满 足Ax A x,则称所给的矩阵范数与向量范数是相容的。 定理1.3 设在Rn种给定了一种向量范数,对任一矩阵A Rnn,令A=max Ax,则由 x1 此定义的? 是一种矩阵范数,并且它与所给定的向量范数相容。 定理1.4设A[aij]Rnn,则 2 n A1 max aij 1jni1 A2 max(ATA) n A max aij 1in j 1 其中max(ATA)表示矩阵ATA的最大特征值(ATA是正定或半正定矩阵, 它的全部特征值 非负)。 n aij2 还有一种常见的矩阵范数 AF i,j ,且与向量范数? 2相容,但是不从属于任何 1 向量范数。 单位矩阵 I的任何一种算子范数 I =maxIx 1。 x 1 定理1.5设矩阵 A R nn A 1 I A 的某种范数 为非奇异矩阵,并且当该范数为算子 ,则 范数时,还有I A 1 1 成立。 1 A 2.1Gauss消去法 2.1.1顺序Gauss消去法 定理2.1顺序Gauss消去法的前 n-1个主元素akk(k)(k 1,2,...,n1)均不为零的充分必要条 a11 (1) ...a1 (1)k 件是方程组的系数矩阵 A的前n-1个顺序主子式Dk ... ...0,(k1,2,...,n1) ak (1)1 ...akk(k) 2.1.2列主元素Gauss消去法 定理2.2设方程组的系数矩阵 A非奇异,则用列主元素 Gauss消去法求解方程组时,各个 列主元素ai(kkk)(k1,2,...,n1)均不为零。 2.2直接三角分解法 2.2.1Doolittle 分解法(单位下三角+上三角)与Crout分解法(下三角+单位上三角) 定理2.3矩阵 A[aij]n n(n2)有唯一的Doolittle分解的充分必要条件是 A的前n-1个顺 序主子式Dk 0,(k1,2,...,n1)。 推论矩阵A [aij]nn(n 2)有唯一的Crout分解的充分必要条件是 A的前n-1个顺序主子 式Dk0,(k 1,2,...,n 1)。 2.2.2选主元的 Doolittle 分解法 3 定理2.4 若矩阵A Rnn非奇异,则存在置换矩阵 Q,使QA可做Doolittle 分解。 2.2.3三角分解法解带状线性方程组 定理2.5(保带状结构的三角分解 )设A [aij]nn是上半带宽为s、下半带宽为r的带状矩阵, 且A的前n-1个顺序主子式均不为零,则 A有唯一的Doolittle 分解 a11 a1,s 1 ...... ... ar 1,1 ... ... A ... ... ans,n ... ...... an,n r ... a 1 u11u12 ... u1,s1 l2,1 1 ...... ... ......... ... ... un s,n lr1,1 ...... ......... ... ...... ... un 1,n ln,nr ...ln,n 1 1 unn 为节省空间,用 C(m,n)存储A 的带内元素,其中 m=r+s+1,并且aij cijs1,j。 2.2.5拟三对角线性方程组的求解方法 a1 c1 d1 d2 a2 c2 A ......... ...... ... dn1 an1 cn1 cn dn an p1 1q1 s1 d2 p2 1q2 s2 ...... ...... ... ...... ... qn2 sn2 ... dn1 pn1 1 sn1 r1 r2 ...rn2 rn1 rn 1 2.3矩阵的条件数与病态线性方程组 2.3.1矩阵的条件数与线性方程组的性态 定义对非奇异矩阵A,称量||A||||A1||为矩阵A的条件数,记作cond(A)||A||||A1||。 矩阵A的条件数与所取的矩阵范数有关,常用的条件数是 4 cond(A) ||A||||A1||,cond(A)2 ||A||2||A1||2 性质1 对任何非奇异矩阵A,cond(A) 1。 性质2 设A是非奇异矩阵,k 0是常数,则有cond(kA) cond(A)。 性质3 设A是非奇异的是对称矩阵,则有 cond(A)2 1 ,其中1和 n分别是矩阵A的 n 模为最大和模为最小的特征值。 性质4 设A是正交矩阵,则有 cond(A)2 1。 2.3.2关于病态线性方程组的求解问题 (1)采用高精度的算术运算。 (2)平衡方法(行平衡,取每行绝对值最大数的倒数组成对角阵,乘在原方程左右两边) 。 (3)残差校正。 2.4迭代法 2.4.1迭代法的一般形式及其收敛性 x(k1) Gx(k) d(k 0,1,...) 定义设nn矩阵G的特征值是1, 2,...,n,称 (G) max| i|为矩阵G的谱半径。 1in 定理2.9 对任意的向量d,迭代法收敛的充分必要条件是 (G) 1。 定理2.9 如果矩阵G的某种范数||G||<1,则 (1)方程组的解x*存在且唯一; (2)对于迭代公式,有 limx(k) x*, x(0) R,且下列两式成立 k ||x(k) x* || ||G||k ||x (1) x(0) || 1 ||G|| ||x(k) x* || ||G|| ||x(k) x(k 1)|| 1 ||G|| 2.4.2Jacobi迭代法 AD L U x(k1) D 1(L U)x(k) D1b(k 0,1,...) GJ D1(L U) 定理2.10Jacobi迭代法收敛的充分必要条件是 (GJ) 1。 定理2.11如果|| || 1 ,则Jacobi迭代法收敛。 GJ 引理2.1若矩阵A Rnn是主对角线按行(或按列)严格占优阵,则 A是非奇异矩阵。 5 定理2.12如果方程组的系数矩阵式主对角线按行(或按列)严格占优阵,则用Jacobi迭代法 求解必收敛。 2.4.3Gauss-Seidel迭代法 A D L U x(k 1) (D L)1Ux(k) (D L)1b(k0,1,...) GG (DL)1U 定理2.13GS迭代法收敛的充分必要条件是 (GG) 1。 定理2.14 如果 || 1,则 迭代法收敛。 || Jacobi GG 定理2.15 如果方程组的系数矩阵式主对角线按行 (或按列)严格占优阵,则用GS法求解必收 敛。 定理2.16 如果方程组的系数矩阵 A是正定矩阵,则用 GS法求解必收敛。 2.4.4逐次超松弛迭代法 1 D L (1 1 )D U A x(k1) ( 1 D L)1[(1 1 )D U]x(k) ( 1 DL)1b(k 0,1,...) GS (1D L)1[(1 1)D U] 实际使用的形式 x(k 1) { D1Lx(k1) [(1 1 )I D 1U]x(k) D1b}(k 0,1,...) 它的分量形式是 x (k1) { i1aij x (k1) 1 )x (k) naij x (k) bi }(k 0,1,...) j (1 j i j1aii i ji1aii aii 定理2.17SOR方法收敛的充分必要条件是 (GS) 1。 定理2.18 如果 || 1,则 方法收敛。 || SOR GS 定理2.19SOR方法收敛的必要条件是 0 2。 定理2.20 如果方程组的系数矩阵 A是主对角线按行(或按列)严格占优阵,则用0 1的 SOR方法求解必收敛。 定理2.21 如果方程组的系数矩阵 A是正定矩阵,则用 0 2 的SOR方法求解必收敛。 ***实系数二次方程 x2 px q 0的两个根之模均小于 1的充要条件是: |q| 1,1 p q 0,1 p q0 ***A为正定矩阵A的各阶顺序主子式全大于零。 3.1幂法和反幂法 3.1.1幂法(用于计算矩阵的按模为最大的特征值和相应的特征向量) 第一种幂法迭代格式: 6 u0 Rn&u0 0 k 1 ukT 1uk1 yk 1 uk 1/k 1 uk Ayk 1 k ykT 1uk (k1,2,...) 第二种幂法迭代格式: u0 |hr(k yk1 uk k (k =(h1(0),...,hn(0))T&u0 1)(k1)|max|hj| uk1/|hr(k1)| (k)(k) Ayk1(h1,...,hn k1(k) sgn(hr)hr 1,2,...) 0 )T k作为1的近似值,yk-1作为A的属于1的特征向量。 3.1.2反幂法 第一种反幂法迭代格式: u Rn&u 0 0 0 k1 ukT 1uk1 yk1 uk 1 /k 1 Auk yk 1 kyTk1uk (k1,2,...) 1作为n的近似值,yk-1作为A的属于n的特征向量。 还可以用带原点平移的反幂法求 k 矩阵A的某个特征值s。 3.3QR方法 3.3.1矩阵的QR分解 设vRn是单位向量,令HI2vvT,则H是对称正交矩阵,称为Householder矩 阵。 引理3.1设有非零向量sRn和单位向量eRn,必存在Householder矩阵H,使得 Hse,其中是实数,并且||sTs。 (可取vse) (se)T(se) 7 定理3.2 任何n n实矩阵A总可以分解为一个正交矩阵 Q与一个上三角矩阵 R的乘积。 设ai1(i 2,3,...,n)不全为零,令 s (a,...,a)T 1 11 n1 c1sgn(a11)s1Ts1(取sgn(0)1) u1s1c1e1 H1I2u1u1T/(u1Tu1) c1a12 (2) 0... A2H1A ...... 0a (2)n2 ...a1 (2)n ... ... ...ann (2) 对第j列,a (
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 完整版 北京航空航天 大学 数值 分析 课程 知识点 总结 docx