数值分析 周维祺
Ax⃗=b⃗A\vec x=\vec bAx=b, A∈Rn×n\quad A\in\mathbb R^{n\times n}A∈Rn×n可逆，主对角线上不含000，x⃗,b⃗∈Rn\vec x,\vec b\in\mathbb R^nx,b∈Rn
令DDD为AAA的主对角线组成的对角阵，即Dij={Aiji=j0i≠jD_{ij}=\begin{cases}A_{ij} & i=j \\ 0 & i\neq j\end{cases}Dij={Aij0i=ji=j
令x⃗(0)\vec x^{(0)}x(0)为初值，记x⃗(k)\vec x^{(k)}x(k)为第kkk步所得的近似解
x⃗(k+1)=x⃗(k)+D−1(b⃗−Ax⃗(k))⏟=r⃗(k)\vec x^{(k+1)}=\vec x^{(k)}+D^{-1}\underbrace{(\vec b-A\vec x^{(k)})}_{=\vec r^{(k)}} x(k+1)=x(k)+D−1=r(k)(b−Ax(k))
第kkk步近似解代入后，与实际值的差异
x∗x^*x∗是原线性方程组的精确解
以x⃗(0)=(1,1,1)T\vec x^{(0)}=(1,1,1)^Tx(0)=(1,1,1)T为初值，用Jacobi法计算以下线性方程组的近似解
(210131012)(x1x2x3)=(000)\begin{pmatrix}2 & 1 & 0 \\ 1 & 3 & 1 \\ 0 & 1 & 2 \end{pmatrix}\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}=\begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} ⎝⎛210131012⎠⎞⎝⎛x1x2x3⎠⎞=⎝⎛000⎠⎞
计算两步，并给出每一步误差向量的长度
D=(200030002)D=\begin{pmatrix}2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 2 \end{pmatrix}D=⎝⎛200030002⎠⎞
D−1=(120001300012)D^{-1}=\begin{pmatrix}\frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{3} & 0 \\ 0 & 0 & \frac{1}{2} \end{pmatrix}D−1=⎝⎛210003100021⎠⎞
准确解为x⃗∗=(0,0,0)T\vec x^*=(0,0,0)^Tx∗=(0,0,0)T，初值误差∥x⃗(0)−x⃗∗∥=3\|\vec x^{(0)}-\vec x^*\|=\sqrt3∥x(0)−x∗∥=3
余项：r⃗(1)=(000)−(210131012)(111)=(−3−5−3)\vec r^{(1)}=\begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}-\begin{pmatrix}2 & 1 & 0 \\ 1 & 3 & 1 \\ 0 & 1 & 2 \end{pmatrix}\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}=\begin{pmatrix} -3 \\ -5 \\ -3 \end{pmatrix}r(1)=⎝⎛000⎠⎞−⎝⎛210131012⎠⎞⎝⎛111⎠⎞=⎝⎛−3−5−3⎠⎞
x⃗(1)=(111)+(120001300012)(−3−5−3)=(−12−23−12)\vec x^{(1)}=\begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}+\begin{pmatrix}\frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{3} & 0 \\ 0 & 0 & \frac{1}{2} \end{pmatrix}\begin{pmatrix} -3 \\ -5 \\ -3 \end{pmatrix}=\begin{pmatrix} -\frac{1}{2} \\ -\frac{2}{3} \\ -\frac{1}{2} \end{pmatrix}x(1)=⎝⎛111⎠⎞+⎝⎛210003100021⎠⎞⎝⎛−3−5−3⎠⎞=⎝⎛−21−32−21⎠⎞
误差：∥x⃗(1)−x⃗∗∥=14+49+14=3436<3\|\vec x^{(1)}-\vec x^*\|=\sqrt{\frac{1}{4}+\frac{4}{9}+\frac{1}{4}}=\sqrt{\frac{34}{36}}<\sqrt3∥x(1)−x∗∥=41+94+41=3634<3
余项：r⃗(2)=(000)−(210131012)(−12−23−12)=(53353)\vec r^{(2)}=\begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}-\begin{pmatrix}2 & 1 & 0 \\ 1 & 3 & 1 \\ 0 & 1 & 2 \end{pmatrix}\begin{pmatrix} -\frac{1}{2} \\ -\frac{2}{3} \\ -\frac{1}{2} \end{pmatrix}=\begin{pmatrix} \frac{5}{3} \\ 3 \\ \frac{5}{3} \end{pmatrix}r(2)=⎝⎛000⎠⎞−⎝⎛210131012⎠⎞⎝⎛−21−32−21⎠⎞=⎝⎛35335⎠⎞
x⃗(2)=(−12−23−12)+(120001300012)(53353)=(131313)\vec x^{(2)}=\begin{pmatrix} -\frac{1}{2} \\ -\frac{2}{3} \\ -\frac{1}{2} \end{pmatrix}+\begin{pmatrix}\frac{1}{2} & 0 & 0 \\ 0 & \frac{1}{3} & 0 \\ 0 & 0 & \frac{1}{2} \end{pmatrix}\begin{pmatrix} \frac{5}{3} \\ 3 \\ \frac{5}{3} \end{pmatrix}=\begin{pmatrix} \frac{1}{3} \\ \frac{1}{3} \\ \frac{1}{3} \end{pmatrix}x(2)=⎝⎛−21−32−21⎠⎞+⎝⎛210003100021⎠⎞⎝⎛35335⎠⎞=⎝⎛313131⎠⎞
误差：∥x⃗(2)−x⃗∗∥=19+19+19=1236<3436<3\|\vec x^{(2)}-\vec x^*\|=\sqrt{\frac{1}{9}+\frac{1}{9}+\frac{1}{9}}=\sqrt{\frac{12}{36}}<\sqrt{\frac{34}{36}}<\sqrt3∥x(2)−x∗∥=91+91+91=3612<3634<3
若k→∞k\to\inftyk→∞时，误差向量的长度∥x⃗(k)−x⃗∗∥→0\|\vec x^{(k)}-\vec x^*\|\to0∥x(k)−x∗∥→0
给定n×nn\times nn×n的矩阵AAA，用AijA_{ij}Aij表示第iii行第jjj列的元素
行严格对角占优：∣Aii∣>∑j=1,j≠in∣Aij∣|A_{ii}|> \sum\limits_{j=1,j\neq i}^n|A_{ij}|∣Aii∣>j=1,j=i∑n∣Aij∣ 对i=1,…,ni=1,\ldots,ni=1,…,n都成立
列严格对角占优：∣Ajj∣>∑i=1,i≠jn∣Aij∣|A_{jj}|> \sum\limits_{i=1,i\neq j}^n|A_{ij}|∣Ajj∣>i=1,i=j∑n∣Aij∣ 对j=1,…,nj=1,\ldots,nj=1,…,n都成立
主对角线上元素的绝对值比该行（列）其它元素绝对值之和都大
在复平面上，n×nn\times nn×n矩阵AAA的任意特征值都在某个以AiiA_{ii}Aii为圆心，∑j=1,j≠in∣Aij∣\sum\limits_{j=1,j\neq i}^n|A_{ij}|j=1,j=i∑n∣Aij∣为半径的圆盘中(i=1,…,ni=1,\ldots,ni=1,…,n)
求矩阵(210121012)\begin{pmatrix}2 & 1 & 0 \\ 1 & 2 & 1 \\ 0 & 1 & 2 \end{pmatrix}⎝⎛210121012⎠⎞的特征值
画出上述定理中的圆盘，并标出特征值对应的点
设λ\lambdaλ是AAA的一个特征值，x⃗=(x1,…,xn)\vec x=(x_1,\ldots,x_n)x=(x1,…,xn)是对应的一个特征向量
不妨设xk=1x_k=1xk=1，且对j=1,…,nj=1,\ldots, nj=1,…,n都有∣xj∣≤1|x_j|\le 1∣xj∣≤1 (思考：为什么)
考察Ax=λxAx=\lambda xAx=λx的第kkk行：∑j=1nAkjxj=λxk\sum_{j=1}^nA_{kj}x_j=\lambda x_k∑j=1nAkjxj=λxk
即 ∣λ−Akk∣≤∑j=1,j≠kn∣Akjxj∣≤∑j=1,j≠kn∣Akj∣ |\lambda-A_{kk}|\le\sum\limits_{j=1,j\neq k}^n|A_{kj}x_j|\le\sum\limits_{j=1,j\neq k}^n|A_{kj}|\;∣λ−Akk∣≤j=1,j=k∑n∣Akjxj∣≤j=1,j=k∑n∣Akj∣ (思考：为什么)
证明以下两个命题:
在复平面上，n×nn\times nn×n矩阵AAA的任意特征值也都在某个以AjjA_{jj}Ajj为圆心，∑i=1,i≠jn∣Aij∣\sum\limits_{i=1,i\neq j}^n|A_{ij}|i=1,i=j∑n∣Aij∣为半径的圆盘中(i=1,…,ni=1,\ldots,ni=1,…,n)
行（列）严格对角占优矩阵是可逆矩阵
若AAA行（列）严格对角占优 则对任意b⃗\vec bb和初值x⃗(0)\vec x^{(0)}x(0)，Jacobi法对Ax⃗=b⃗A\vec x=\vec bAx=b都收敛
（证明留待第14讲）
设DDD是AAA的主对角线部分，若AAA和2D−A2D-A2D−A都正定 则对任意b⃗\vec bb和初值x⃗(0)\vec x^{(0)}x(0)，Jacobi法对Ax⃗=b⃗A\vec x=\vec bAx=b都收敛
（证明留作拓展思考）
以x⃗(0)=(1,1,1)T\vec x^{(0)}=(1,1,1)^Tx(0)=(1,1,1)T为初值，用Jacobi法计算以下线性方程组的近似解是否收敛，说明理由