§4 迭代法的收敛性 /* Convergence of Iterative methods */

Presentation on theme: "§4 迭代法的收敛性 /* Convergence of Iterative methods */"— Presentation transcript:

1 §4 迭代法的收敛性 /* Convergence of Iterative methods */
的收敛条件 充分条件: ||B|| < 1 等价于对 任何算子范数有 必要条件: ？ 定义 设： A k =    lim 是指 ij a ) ( 对所有 1 i, j  n 成立。

2 seriously expect me to compute Bk whenever I want to check
§4 Convergence of Iterative methods 定理 设 存在唯一解，则从任意 出发， 迭代 收敛   k B 证明： Bk  0 || Bk ||  0 But hey, you don’t seriously expect me to compute Bk whenever I want to check the convergence, do you? 对任意非零向量 成立 对任意非零向量 成立 “”：取 则 第 i 位 “”：对任意非零向量 有 从任意 出发， 记 ，则 as k   收敛

3 对任意  > 0, 存在算子范数 || · || 使得 || A ||   (A) +  。
§4 Convergence of Iterative methods 定理 Bk  0   ( B ) < 1 证明： “” 若  是 B 的eigenvalue, 则k 是 Bk 的eigenvalue 。 证明：对 A 做 Jordan 分解，有 ，其中 ， ， i 为 A 的 eigen value。 令 ，则有 易证： 是由 导出的算子范数。 所以只要取  <  ，就有|| A || <  (A) +  。 则 [ (B)]k = [ max |  | ]k = | mk |   ( Bk )  || Bk ||  0   (B) < 1  “” 首先需要一个引理 /* Lemma */ 对任意  > 0, 存在算子范数 || · || 使得 || A ||   (A) +  。 由  (B) < 1 可知存在算子范数|| · || 使得 || B || < 1。 || Bk ||  || B ||k  0 as k   Bk  0 迭代从任意向量出发收敛 Bk  0  ( B ) < 1

4 定理  （充分条件）若存在一个矩阵范数使得 || B || = q < 1, 则迭代收敛，且有下列误差估计： ① ② 证明： ① ②
§4 Convergence of Iterative methods 定理 （充分条件）若存在一个矩阵范数使得 || B || = q < 1, 则迭代收敛，且有下列误差估计： ① ② 证明： ①  ②

5 若A 为SDD阵，则det(A)  0，且所有的 aii  0。 Geršgorin Disc Theorem (p.72)。
§4 Convergence of Iterative methods 定理 （充分条件）若A 为严格对角占优阵 /* strictly diagonally dominant matrix */ 则解 的Jacobi 和 Gauss - Seidel 迭代均收敛。 证明：首先需要一个引理 /* Lemma */ 显然 若A 为SDD阵，则det(A)  0，且所有的 aii  0。 证明：若不然，即det(A) = 0，则 A 是奇异阵。 我们需要对 Jacobi 迭代和 Gauss-Seidel迭代分别证明：任何一个|  |  1 都不可能是对应迭代阵的特征根，即 | I  B |  0 。 存在非零向量 使得 Jacobi: BJ = D1( L + U ) 关于Gauss-Seidel迭代的证明 与此类似 (p.73)。 另一种证明引理的方法利用 Geršgorin Disc Theorem (p.72)。 记 如果 |  |  1 则 是SDD阵 HW: p.76 #1 aii  0 | I  B |  0 

6 §5 松弛法 /* Relaxation Methods */
换个角度看Gauss - Seidel 方法： 其中ri(k+1) = 相当于在 的基础上加个余项生成 。 /* residual */ 下面令 ，希望通过选取合适的  来加速收敛，这就是松弛法 /* Relaxation Methods */ 。 ii k i a r x ) 1 ( + = w 0 <  < 1 低松弛法 /* Under- Relaxation methods */  = 1 Gauss - Seidel 法  > 1 (渐次)超松弛法 /* Successive Over- Relaxation methods */

7 定理 写成矩阵形式： 松弛迭代阵 设 A 可逆，且 aii  0，松弛法从任意 出发对某个  收敛   ( H ) < 1。
§5 Relaxation Methods 写成矩阵形式： 松弛迭代阵 定理 设 A 可逆，且 aii  0，松弛法从任意 出发对某个  收敛   ( H ) < 1。 Oooooh come on! It’s way too complicated to compute H , and you can’t expect me to get its spectral radius right! There’s gotta be a short cut …

8 定理 （Kahan 必要条件）设 A 可逆，且 aii  0，松弛法 从任意 出发收敛  0 <  < 2 。
§5 Relaxation Methods 定理 （Kahan 必要条件）设 A 可逆，且 aii  0，松弛法 从任意 出发收敛  0 <  < 2 。 证明：从 出发 利用 ，而且收敛  | i | < 1 总成立 可知收敛  | det(H) | < 1  | det(H) | = | 1   |n < 1  0 <  < 2

9 Q: What factor determines the speed of convergence?
§5 Relaxation Methods 定理 （Ostrowski-Reich 充分条件）若A 对称正定，且有 0 <  < 2，则松弛法从任意 出发收敛。 Q: What factor determines the speed of convergence? 考察迭代 ：设 B 有特征根 1、…、n 对 应 n 个线性无关的特征向量 。则从任意 出发， 可表为 的线性组合，即 A: The smaller  ( B ) is, the faster the iterations will converge. ~ 对于SOR法，希望找  使得  ( H ) 最小。

10 §5 Relaxation Methods 定理 若 A 为对称正定三对角阵，则 且SOR的最佳松弛因子 /* optimal choice of  for SOR method */ 为 ，此时 。 例： ，考虑迭代格式 问：  取何值可使迭代收敛？   取何值时迭代收敛最快？ 解：考察 B = I +  A 的特征根 1 = 1+  , 2 = 1+ 3  收敛要求 ( B )< /3 <  < 0 -2/3 -1/3    (B) = max { | 1+  |, | 1+ 3 | } 当 取何值时最小？  = - 1/2 HW: p.77 #5 #7

11 §5 Relaxation Methods Lab 08. SOR Method Use the SOR method to solve a given n×n linear system with an initial approximation and a set of ’s. Input There are several sets of inputs. For each set: The 1st line contains an integer 100  n  0 which is the size of a matrix. n = 1 signals the end of file. The following n lines contain the augmented matrix in the following format: The numbers are separated by spaces and new lines. The next line contains a real number TOL, which is the tolerance for || · || norm, and an integer N  0 which is the maximum number of iterations. The last line of each test case contains an integer m > 0, followed by m real ’s.

12 注意：检查每个aii时，先向下 找最大元，若非0则交换到对角线上； 否则向上找最大元，若非0则 将该行加到第 i 行上。
§5 Relaxation Methods Output ( represents a space) For each , there must be a set of outputs in the following format: The 1st line contains an  and the corresponding number of iterations taken. In the C printf: fprintf(outfile, "%4.2f%d\n", omega, iter_no ); The corresponding solution or error messages are to be printed as the following: Each entry of the solution is to be printed as in the C fprintf: fprintf(outfile, "%12.8f\n", x ); If the matrix A has a zero column, print the message “Matrixhas azerocolumn. No uniquesolutionexists.\n”. If the method fails to give a solution after N iterations, print the message “Maximumnumberof iterationsexceeded.\n”. If there is an entry of that is out of the range [ 2127, 2127 ], print the message “No convergence.\n”. The outputs of two test cases must be seperated by a blank line. 注意：检查每个aii时，先向下 找最大元，若非0则交换到对角线上； 否则向上找最大元，若非0则 将该行加到第 i 行上。

13 Sample Input ( represents a space) Sample Output
§5 Relaxation Methods Sample Input ( represents a space) 3 4–101 –14–14 0–14–3 1000 21.051.2 10–109 –110–27 0–4106 1000 11 –1 Sample Output 1.057   – 1.2011   – 1.0010