计算方法复习提纲(包括定义定理).

R n 中一向量序列，x
k
k
lim x ( k ) x
lim x ( k ) x 0 ，其中
x 为任一种向量范数。
k
lim x ( k ) x

0 lim x ( k ) x
k
2. 矩阵范数
若对 R nn 上任一矩阵A，皆对应一个非负实数 A ，且满足如下条件 (1)非负性: ‖A‖ (2)齐次性: ‖ 0 ,且‖A‖=0当且仅当A=0 |‖A‖, ‖A‖+‖B‖ R A‖=|
a1 j u1 j
ai1 li1u11
比较第1行： 比较第1列：
j 1,, n
u1 j a1 j ai1 i 2,, n li1 u11
以三阶为例
a11 a 21 a31 a12 a22 a32 a13 1 l a23 L= 21 1 U= l l 1 a33 31 32
定义1：如果矩阵的每一行中，不在主对角线上的所有 元素绝对值之和小于主对角线上元素的绝对值， 即
a
j 1 j i
n
ij
aii
i 1, 2, , n
则称矩阵A按行严格对角占优，类似地，也有按列
严格对角占优。
定理3：若线性方程组AX = b的系数矩阵A按行严格对角 占优，则雅克比迭代法和高斯―赛得尔迭代法 对任意给定初值均收敛。
x1 0.99972 x 2 6.00002 x 2.99985 3
精确解是
3 -4 5 -12 0 0.33332 -0.66665 0.00004 0 2.33332 0.33335 14.99996
(10) (11) (12) (13) (14) (15)
3 -4 5 -12 0 2.33332 0.33335 14.99996 0 0.33332 -0.66665 0.00004 3 -4 5 -12 0 2.33332 0.33335 14.99996 0 0 -0.71427 -2.14270
(k=0,1,2,…,n-1)，称为函数y=f (x)在点xk上的一阶差分。
yk 1 yk 称为函数f (x)在xk上的二阶差分，记为
2 y k
，即
2 yk yk 1 yk
一般地，将
(k=0,1,2,…,n-2)
m yk m1 yk 1 m1 yk
称为函数f (x)在xk上的m阶差分。
称为矩阵A的2范数或谱范数或欧几里德范数。
定义3.6 设{A(k)}为
R nn中一矩阵序列，A
R nn
，如果
k
(k ) lim a ij a ij (i, j=1,2,…,n)，则称A(k) 收敛于矩阵A，记为
k
定理3.6 是
lim A ( k ) A
As和
R nn上任意两种矩阵范数是等价的，即若
x k (k=0,1,2,…)收敛于方程
ek x k
，若存在实数
k e p k
x ( x) 的根

，记
p 1 及非零常数c，使得
lim
ek 1
c
则称迭代过程是p阶收敛的。 当p=1时，称为线性收敛； 当p>1时，称为超线性收敛；当p=2时，称为平方收敛。 显然，p越大收敛速度越快。
(k=0,1,2,…,n-m)
2.差分表
各阶差分中所含的系数正好是二项式展开系数， 所以n阶差分的计算公式为
n n s n n y k y n k y y ( 1 ) y ( 1 ) yk 1 n k 1 2 n k 2 s nk s n n(n 1) (n s 1) 其中 s s!
k
( A) <1。
定理： 若 证：

为
A
的特征值，则
A
x A x
x为A的特征向量
x A x
x x A x A x
A
定义5.2：
A x x

#证毕
谱半径
( A) max r
1 r n
易知：
( A) A
(i=1,2,…,n)，则称x(k) 收敛于向量x，记为
k
lim x ( k ) x
R 上的任意两种向量范数是等价的，即若
c1 x s x t c2 x
n
定理3.3
x
s
和
x
t
是
Rn
Rn
上的任意两种向量范数，则存在常数c1>0，c2>0，使得对任意x 皆有
s
n R，则
定理3.4 设{x(k)}为 的充要条件是
分解的理论由Gauss消元得出，因此分解能够进行的条件与Gauss消元一样：系 数矩阵的各阶顺序主子式都不为零。
1、LU分解 L为单位下三角，U为上三角，若A=LU，根据矩阵相等可以求出L和U。
a11 a21 a n1
a12 a22 an 2
a1n 1 u11 u12 u1n a2 n l21 1 u22 u2 n l ann l 1 u nn n1 n 2
A
为任一种矩阵范数。
3. 谱半径
定义3.7 设A
R nn
1 i n
，其特征值为
i
(i=1,2,…,n)，则称
( A) max i
定理3.8 设A
为A的谱半径。
R nn
A
，则
( A) A
其中
为A的任一种算子范数。
定理3.9 设A
R nn
，则
lim A ( k )=0的充要条件是
知准确值 x 的范围 定义 1.2
近似值 x*的误差与其准确值 x 之比 E E x x * 称为近似值 x*的相对误差。 r
相对误差绝对值的任一个上界
r
均称为相对误差限。
x
x
定理 1.1 设 x*是准确值 x 的某个近似值， 其规格化形式为(1.1)，X*=
0.a1a2 an an1 am 10k
，皆有
A
t
R nn上的任意两种矩阵范数，则存在常数c1>0，c2>0，使得对
任意A
R nn
c1 A s A t c2 A s
R nn
，则 ，其中
定理3.7 设{A(k)}为
R nn 中一矩阵序列，A
k
lim A
(k )
A
的充要条件是
k
lim A ( k ) A 0
3.5.1 向量范数和矩阵范数
1. 向量范数 定义3.1 若对 如下条件 (1) 正定性：
R n 上任一向量x，皆对应一个非负实数
x ，且满足
x ≥0，等号当且仅当x=0时成立；
(2) 齐次性：对任意实数 (3) 三角不等式： 则称

，都有 ，有
x
= x
x, y R n
x y x y
n x 是 R 上的一个向量范数（上述三个条件称为范数公理）。
实数的绝对值、复数的模、三维向量的模等都满足范数公理 设x=(x1,x2,…,xn)T，常用的向量范数有三种： (1) 1-范数：
n
n 1 xi2 ) 2
x 1 xi
i 1
(2) 2-范数：
x
2
(
i 1
(3)∞-范数：
x

max x i
1 i n
定义3.2 设{x(k)}为
R n 中一向量序列，x
Rn，
(k ) (k ) (k ) T x ( k ) ( x1 , x2 ,, xn ) (k=1,2,…)，
x ( x1 , x2 ,, xn ) T
如果
k
lim xi( k ) xi
n
定理2 (抛物线公式的误差)设f(x)在［a, b］上有连续的四阶导数,则抛物线公式的 误差为
2、列主元的高斯消元法
例3.3 用列主元高斯消去法解线性方程组
x1 (1) (2) (3) (4) (5) (6) (7) (8) (9) x2 x3 右端项 -4 -12 11 -12 -4 11 说 明 1 -1 1 3 -4 5 1 1 2 3 -4 1 -1 1 1 5 1 2 在第一列上选主元3
A=
u11 u12 u 22
u13 u 23 u33
u12 u11 LU= l21u11 l21u12 u22 l31u11 l31u12 l32u22
l21u13 u23 l31u13 l32u23 u33 u13
x1 x 2 x3 4 3x1 4 x 2 5 x3 12 x x 2 x 11 2 3 1
回代得
(1) (2) 计算 l21=1/3=0.33333 l31=1/3=0.33333 (5)-(4)×l21 (6)-(4)×l31 在第二列的子列上选主元 2.33332 (8) (9)计算 l32=0.33332/2.33332 =0.14285 (12)-(11)×l32
1
* n1 (1) 若 x*具有 n 位有效数字，则 x*的相对误差 E * 满足 Er 10 r 2
(2) 若 x*的相对误差
E*
* 10n E 满足 则 x*至少具有 n 位有效数字 r r 2
1
收敛速度
定义2.1 设由迭代公式
xk 1 ( xk )
产生的迭代序列
§2 迭代法的收敛条件
X ( k 1) CX ( k ) F
(4.8)
定理1：对任意初始向量X(0)及常向量F，迭代格式(4.8)
收敛的充分必要条件是迭代矩阵B的谱半径
定理2：若迭代矩阵C的某种范数 则（4.8C ） 1
(C) < 1。
确定的迭代法对任意初值X(0)均收敛于方程组
X = CX + F的唯一解x*。
区分两类基本算法
掌握三种基本技术
www.themegallery.com
第2章 主要内容
第3章 小结
计算机基础教育系
第4章 小结
第5章 小结
误差:近似值与准确值之差，称为误差。 定义 1.1 设 x 为准确值，x*为其近似值，称 E=x-x*为近似值 x*的绝对误差，简称误差。
E x x * 。ε 称为 x*的绝对误差限，简称误差限，也叫精度。由误差限ε 可
(3)三角不等式:‖A+B‖ (4)相容性:‖AB‖ 则称 A 是
‖A‖‖B‖
R nn 上的一个矩阵范数。
定义：设‖x‖是一种向量范数
A max n
Ax x
xR , x 0
max Ax n
xR , x 1
称之为由向量范数派生的矩阵算子范数.
定理3.5 设A
R nn ，x R n ，则
第1章 小结
学习数值算法
计算机算法的设计原 理都是将复杂化归为 简单的重复，或说通 过简单的重复生成复 杂. 领悟一条基本原理
算法大致分为直接法和 迭代法两大类。直接法 通过有限步计算直接得 出问题的解，而迭代法 则通过某种迭代过程逐 步逼近所求的解
Βιβλιοθήκη Baidu
化大为小的缩减技术，化难 为易的校正技术及化粗为精 的松弛技术，缩减技术和校 正技术分别适用于直接法和 迭代法，而恰当地使用松弛 技术有可能显著提高迭代过 程的收敛速度
x1 1 x2 6 x 3 3
3.3 矩阵的LU分解
若有存在L和U，使得
A LU
L为单位下三角阵，U为上三角阵， 则原方程组可以分解为两个三角形方程组
Ly b Ax b LUx b Ux y
我们可以通过求两个三角方程组求解方程组
注意：
4.5 差分与等距节点插值公式
4.5.1 差分与差分表 1.差分 定义4.2 设函数y=f(x)在n+1个等距节点
xk x0 kh 上函数值为
y k f ( xk )
函数在每一小区间
(k=0,1,2,…,n)，这里，h为常数，称为步长。 上的增量 [ xk , xk 1 ]
yk yk 1 yk
相容的矩阵算子范数
(1) 与
x

A

max aij
1i n j 1
n
n
称为矩阵A的行范数； (2) 与
x
1
相容的矩阵算子范数
A 1 max aij
1 j n i 1
称为矩阵A的列范数； (3) 与
x 相容的矩阵算子范数 2
(
A 2 1
1是ATA的最大特征值)，。