当前位置:
文档之家› 计算方法复习提纲(包括定义定理).
计算方法复习提纲(包括定义定理).
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
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
分解的理论由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
第1章 小结
学习数值算法
计算机算法的设计原 理都是将复杂化归为 简单的重复,或说通 过简单的重复生成复 杂. 领悟一条基本原理
算法大致分为直接法和 迭代法两大类。直接法 通过有限步计算直接得 出问题的解,而迭代法 则通过某种迭代过程逐 步逼近所求的解
化大为小的缩减技术,化难 为易的校正技术及化粗为精 的松弛技术,缩减技术和校 正技术分别适用于直接法和 迭代法,而恰当地使用松弛 技术有可能显著提高迭代过 程的收敛速度
区分两类基本算法
掌握三种基本技术
第2章 主要内容
第3章 小结
计算机基础教育系
第4章 小结
第5章 小结
误差:近似值与准确值之差,称为误差。 定义 1.1 设 x 为准确值,x*为其近似值,称 E=x-x*为近似值 x*的绝对误差,简称误差。
E x x * 。ε 称为 x*的绝对误差限,简称误差限,也叫精度。由误差限ε 可
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越大收敛速度越快。
定义1:如果矩阵的每一行中,不在主对角线上的所有 元素绝对值之和小于主对角线上元素的绝对值, 即
a
j 1 j i
n
ij
aii
i 1, 2, , n
则称矩阵A按行严格对角占优,类似地,也有按列
严格对角占优。
定理3:若线性方程组AX = b的系数矩阵A按行严格对角 占优,则雅克比迭代法和高斯―赛得尔迭代法 对任意给定初值均收敛。
§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*。
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
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 1 x2 6 x 3 3
3.3 矩阵的LU分解
若有存在L和U,使得
A LU
L为单位下三角阵,U为上三角阵, 则原方程组可以分解为两个三角形方程组
Ly b Ax b LUx b Ux y
我们可以通过求两个三角方程组求解方程组
注意:
3.5.1 向量范数和矩阵范数
1. 向量范数 定义3.1 若对 如下条件 (1) 正定性:
R n 上任一向量x,皆对应一个非负实数
x (2) 齐次性:对任意实数 (3) 三角不等式: 则称
,都有 ,有
x
= x
x, y R n
x y x y
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
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的充要条件是
(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阶差分。
(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)}为 的充要条件是
(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!
相容的矩阵算子范数
(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的最大特征值),。
,皆有
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
知准确值 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
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
称为矩阵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,记为