南大数值分析课件§2.2 线性方程组的误差分析.ppt

§2 Error Analysis for .
精确解为
例:

§2 线性方程组的误差分析
/* Error Analysis for Linear system of Equations */
求解时,A 和的误差对解有何影响?
设 A 精确, 有误差,得到的解为,即
绝对误差放大因子
又
相对误差放大因子
§2 Error Analysis for .
设精确,A有误差,得到的解为,即
Wait a minute …
Who said that ( I + A1 A )
is invertible?
(只要 A充分小,使得
是关键
的误差放大因子,称为
A的条件数,记为cond (A) ,
越则 A 越病态,
难得准确解。
大
§2 Error Analysis for .
注:  cond (A) 的具体大小与|| · || 的取法有关,但相对大小一致。
 cond (A) 取决于A,与解题方法无关。

常用条件数有:
cond (A)1
cond (A)
cond (A)2
特别地,若 A 对称,则
条件数的性质:
 A可逆,则 cond (A)p  1;
 A可逆, R 则 cond ( A) = cond (A) ;
 A正交,则 cond (A)2=1;
 A可逆,R正交,则 cond (RA)2 = cond (AR)2 = cond (A)2 。
§2 Error Analysis for .
精确解为
例:
计算cond (A)2 。
A1 =
解:考察 A 的特征根
39206 >> 1
测试病态程度:
给一个扰动
,其相对误差为
此时精确解为
> 200%
§2 Error Analysis for .
例:Hilbert 阵
cond (H2)=
27
cond (H3)
748
cond (H6)=
 106
cond (Hn) as n 
注:一般判断矩阵是否病态,并不计算A1,而由经验得出。
行列式很大或很小(如某些行、列近似相关);
元素间相差大数量级,且无规则;
主元消去过程中出现小主元;
特征值相差大数量级。
§2 Error Analysis for .
近似解的误差估计及改善:
设的近似解为,则一般有
cond (A)
误差上限
改善方法:
Step 1: 近似解
Step 2:
Step 3:
Step 4:
若可被精确解出,则有
就是精确解了。
经验表明:若 A 不是非常病态(例如: ),则如此迭代可达到机器精度;但若 A 病态,则此算法也不能改进。
HW:
#19, #22, #25
#27.
第四章解线性方程组的迭代法
/* Iterative Techniques for Solving Linear Systems */
求解
思路
与解 f (x)=0 的不动点迭代相似……
,将等价
改写为形式,建立迭代。从初值出发,得到序列。
计算精度可控,特别适用于求解系数为大型稀疏矩阵/* sparse matrices */ 的方程组。
研究内容:
如何建立迭代格式? 收敛速度?
向量序列的收敛条件? 误差估计?
§3 Jacobi 法和 Gauss - Seidel 法
/* Jacobi & Gauss-Seidel Iterative Methods */
 Jacobi Iterative Method
写成矩阵形式:
A =
L
U
D
B
Jacobi 迭代阵
§3 Jacobi & Gauss-Seidel Iterative Methods
Algorithm: Jacobi Iterative Method
Solve given an initial approximation .
Input: the number of equations and unknowns n; the matrix entries a[ ][ ];
the entries b[ ]; the initial approximation X0[ ]; tolerance TOL;
maximum number of iterations Nmax.
Output: approximate solution X[ ] or a message of failure.
Step 1 Set k = 1;
Step 2 While ( k  Nmax) do steps 3-