数值分析复习要点

λmax ( AT A) σ 1 = λmin ( AT A) σ n
A对称时，cond ( A) 2 =|| A−1 ||2 || A ||2 | λ ( A) |max = | λ ( A) |min
距离概念
向量空间的距离 （x , y ) = ρ || x − y || p = (∑ | xi − yi | p )
T百度文库
v1= 2, u= v= 2ε 1 1 1
1 1 1 1 T v1 = ( , , , ) 2 2 2 2
u2 = v2 + 3ε 1 = ε 2 + 3ε 1
T
1 1 1 1 T v2 = 1, ε2 = v2 v2 = (− , , , − ) 2 2 2 2
v3 = u3 − ( u3 , ε 1 )ε 1 − ( u3 , ε 2 )ε 2 1 1 1 1 T 1 1 1 1 T (2, 3,1, 6) − 6( , , , ) − ( −2)( − , , , − ) 2 2 2 2 2 2 2 2 ( −2,1, −1, 2)T =
u1
1 2 2 1
2 3 ，试求A的正交分解. 1 6
T = = (1,1,1,1) , u2 (1, 2, 2,1)T , u3 (2, 3,1, 6)T
S = {u1 , u2 , u3 }是R( A)的一组基.
v = u = v1 (1,1,1,1) , ε= 1 1 1
T
1 1 1 1 T v2 = u2 − ( u2 , ε 1 )ε 1 = (1, 2, 2,1) − 3( , , , ) 2 2 2 2 1 1 1 1 T (− , , , − ) = 2 2 2 2
迭代矩阵 A = D − L−U BJ = D −1 ( L + U ) BG = ( D − L ) −1 U Bω = ( D − ω L)−1 (ωU + (1 − ω ) D )
3.已知一组线性无关的向量 u1 = ( −1,1,1)T , u2 = (1, 0, −1)T , u1 = (0,1,1)T , 由此向量组，按Schmidt正交化方法，求一组对应的 3 1 0 A − 共轭向量组,其中A= 1 3 1 0 1 3
1 1 例：已知矩阵A = 1 1 解 : A的列线性无关,
1 2 1 5.对矩阵A = 3 1 2 , 用Householder 阵将A 4 2 1 相似约化为上Hessenberg阵 , 即HAH 为上Hessenberg阵 .
返回
四.矩阵的正交分解
Schmidt正交化法 P65-例2-34 Householder变换法 P67-例2-35
u= v= 2ε 1 1 1 u 2= v2 + 3ε 1 = ε 2 + 3ε 1
u 3 =v3 + 6ε 1 − 2ε 2 = 10ε 3 + 6ε 1 − 2ε 2
2 3 ε3 ) 0 1 0 0 6 −2 10
(u
1
u2
u3)
(ε 1 ε 2
A = QR 称为A的正交分解.
一. 基本概念
绝对误差,相对误差,有效数字,数值稳定性等. 向量范数
n
|| x ||1 = ∑ | xi |
i =1
|| x ||2 = (∑ | xi | )
i =1
n
1 2 2
|| x ||∞ = max | xi |
1≤i ≤ n
矩阵范数
|| A || F = ( ∑ | aij | )
i , j =1
n
1 2 2
|| A || p = max
|| x|| ≠ 0
|| Ax || p || x || p
T
p = 1,2, ∞, || A ||∞ （行范数）
p103−106
|| A ||1 （列范数）
|| A ||2 = λmax ( A A) （谱范数）
矩阵范数
①矩阵A的1 − 范数(又称为A的列范数) A 1 = max ∑ aij
数值分析复习要点
一. 基本概念
二. Gauss变换与矩阵的三角分解 三. Householder变换与矩阵的相似变换 四. 矩阵的正交分解 五. 解线性方程组Ax=b的直接法 六. 解线性方程组Ax=b的迭代法 七. 列满秩最小二乘问题
八. 构造正交多项式 九. 连续函数的最佳平方逼近 十. 离散数据的最佳平方逼近 十一. 函数插值 十二. 数值积分 十三. 数值微分 十四. 非线性方程的数值解法 十五. 数值计算的基本思想 十六.读程序
(1) A为对称阵, 用H阵可将A作相似变换为三对角阵
即 : HAH
习题
1. 已知向量x = (2,0,2,1) , 试构造Householde r阵H
T
使Hx = ke3 , 其中e3 = (0,0,1,0 ) , k ∈ R .
T +
2.已知向量x = (1,2,1,−2)T , 试构造Householde r阵H 使Hx = (1,−σ 2 ,0,0)T .
1≤ j ≤ n i =1 n
②矩阵A的∞ − 范数(又称为A的行范数) A
∞
= max ∑ aij
1≤ i ≤ n j =1
n
③矩阵A的2 − 范数(又称为A的谱范数) = A2 = λmax ( AT A) σ 1 其中λmax ( AT A)表示( AT A)的最大特征值,
σ 1为A的最大奇异值.
六. 解线性方程组Ax=b的迭代法
( k +1) 迭代格式 x= Bx ( k ) + g k →∞ 收敛的充分必要条件 B k → 0 ⇔ ρ ( B) < 1
收敛的充分条件
|| B || p < 1, p = 1, 2，∞
Jacobi迭代法,Gauss-Seidel迭代法,SOR松弛迭代法 的分量形式,迭代矩阵,收敛条件. P110-118 估计迭代次数
习题 : 3 2 1 1.已知矩阵A = 2 3 0 , 试计算 1 0 3 (1) A的谱半径ρ ( A), (2) A的谱条件数cond ( A) 2 , (3) A的奇异值 2.已知向量x = (1, 4, −3, 0)T , y = (3, 6,1, 2)T , 求x, y之间的距离ρ ( x, y ).
谱半径
ρ ( A) =| λ ( A) |max
Σ r ≠ 0, i 1,..., = λi ( A A) = r, Σ 0
T
奇异值与奇异值矩阵 = σi 0 0
条件数 cond ( A) p =|| A−1 || p || A || p ,
p = F ,1,2, ∞
谱条件数
cond ( A) 2 =|| A−1 ||2 || A ||2 =
a b 1 p
p = 1,2, ∞,
p26− 27
数值算法的稳定性 例 利用递推公式 y0 = ln 6 − ln 5 ≈ 0.182 = y 0 1 − 5 yn −1 n= 1, 2， ... yn = n 计算yn，试分析算法的稳定性 习题：p15 − − − 10
数值计算中应注意的问题 (1) 防止相近的两数相减 (2) 防止大数吃小数 (3) 防止接近零的数做除数 (4) 注意计算步骤的简化,减小运算次数
−1
|| δA || || δb || ) + || A |||| A || ( || δx || || A || || b || ≤ * −1 1− || A |||| δA || || x ||
何为事后误差估计.
|| e || || r || −1 答 :由计算解估计误差 ∗ ≤|| A |||| A || || x || || b ||
返回
二. Gauss变换与矩阵的三角分解
Gauss变换阵
1 1 Lj = − l j +1, j − ln , j
T
1 1
构造Gauss变换阵G，使Gx = (x1 ,..., x j ,0,...,0) 解 : G = L j , 其中li , j xi = , xj
五. 解线性方程组的直接法
习题:P138—14,16. 系数矩阵A为哪些矩阵时,可用顺序Gauss消元 法求解Ax=b. 系数矩阵A为哪些矩阵时,可用列主元Gauss 消元法求解Ax=b. 何为病态矩阵,如何判别矩阵为病态矩阵. 举例说明数学稳定性与数值稳定性 的区别.
解的精度改进的常用方法.P102-105 何为先验误差估计.
i =1 n 1 p
p= 1, 2, ∞, p25
矩阵空间的距离 ρ ( A, B) =|| A − B || p
p = 1,2, ∞, F
连续函数空间的距离 ρ ( f ( x), g ( x)) =|| f ( x) − g ( x) || p = ( ∫ | f ( x) − g ( x) | p dx)
三. Householder变换,矩阵的相似变换
Householde r变换阵 H = I − 2 wwT , 其中 || w ||2 = 1
定理 : 设n维向量x , y , x ≠ y , 但 || x ||2 = || y ||2 , u = x − y, u 则存在Householder 变换阵 H = I − 2 ww , w = , || u ||2
已知向量 = = 3. x (1, 2, 2)T , y (0, 3, 4)T , 试构造一个 = Householder阵H 使 Hx ky，k ∈ R。给出k 值和 变换阵H .
返回
1 3 4 4.对矩阵A = 3 1 2 , 用Householder 阵 4 2 1 将A相似约化为三对角阵 , 即 HAH 为三对角阵 .
2 1 1 2 T v3 = v3 / v3 = ε3 = 10, (− , ,− , ) 10 10 10 10
u3 =v3 + 6ε 1 − 2ε 2 = 10ε 3 + 6ε 1 − 2ε 2
得到R( A)的标准正交基为{ε 1 , ε 2 , ε 3 }. 1 1 1 1 T 1 1 1 1 T ε1 = ( , , , ) ,ε2 = (− , , , − ) , 2 2 2 2 2 2 2 2 1 ε 3= ( −2,1, −1, 2)T 10
T
使Hx = y .
应用 : (2) A为非对称阵, 用H阵可将A作相似变换为上 Hessenberg 阵.
= , HAH
|| x ( k )
k || || B || x (1) − x ( 0 ) ||< 10 −3 → k > ? − x * ||≤ 1− || B ||
收敛速度 R = − ln( ρ ( B ))
SOR分量形式 : (以二阶方程组为例)
ω ( k +1) (k ) (k ) (k ) = + − − x x ( b a x a x 1 1 11 1 12 2 ) 1 a11 ω (k ) ( k + 1) (k ) x ( k +1) = + − − x ( b a x a x 2 2 2 21 1 22 2 ) a22
对∀x = (x1 ,..., x j ,..., xn ) ≠ 0,
xj ≠ 0
T
i = j + 1, j + 2,...n
LU分解 列主元三角分解 PA=LU
习题 : 1.设 = x (2,1, −1, 3) , 求一Gauss变换阵L,
T
使Lx = (2, 0, 0, 0)T . 1 2 3 A = 2 6 2, 2.已知矩阵 3 1 5 对矩阵A作三角分解, 即A = LU .
习题 : 1 2 1.设矩阵A = 2 1 , 用Schmidt正交化方法, −1 2 对A作正交分解A = QR.
2 −1 7 2.设矩阵A = 0 3 10 , 用Householde r变换法, 0 4 5 对A作正交分解A = QR.