## 條件數

$\Vert A+B\Vert\le\Vert A\Vert+\Vert B\Vert$

$\Vert AB\Vert\le\Vert A\Vert\cdot\Vert B\Vert$

$A(\mathbf{x}+\delta\mathbf{x})=\mathbf{b}+\delta\mathbf{b}$

$\displaystyle\frac{\Vert\delta\mathbf{x}\Vert}{\Vert\mathbf{x}\Vert}=\frac{\Vert A^{-1}(\delta\mathbf{b})\Vert}{\Vert\mathbf{x}\Vert}\le\frac{\Vert A^{-1}\Vert\cdot\Vert\delta\mathbf{b}\Vert}{\Vert\mathbf{x}\Vert}\le\left(\Vert A\Vert\cdot\Vert A^{-1}\Vert\right)\frac{ \Vert\delta\mathbf{b}\Vert}{\Vert\mathbf{b}\Vert}$

$\displaystyle \frac{\Vert\delta\mathbf{x}\Vert}{\Vert\mathbf{x}\Vert}\ge\frac{\Vert\delta\mathbf{b}\Vert}{\Vert A\Vert\cdot\Vert\mathbf{x}\Vert}\ge\left(\Vert A\Vert\cdot\Vert A^{-1}\Vert\right)^{-1}\frac{\Vert\delta\mathbf{b}\Vert}{\Vert\mathbf{b}\Vert}$

$\kappa(A)=\Vert A\Vert\cdot\Vert A^{-1}\Vert$

$\displaystyle \kappa(A)^{-1}\frac{\Vert\delta\mathbf{b}\Vert}{\Vert\mathbf{b}\Vert}\le\frac{\Vert\delta\mathbf{x}\Vert}{\Vert\mathbf{x}\Vert}\le\kappa(A)\frac{\Vert\delta\mathbf{b}\Vert}{\Vert\mathbf{b}\Vert}$

$\displaystyle \sigma_1=\max_{\Vert\mathbf{x}\Vert=1}\Vert\Sigma\mathbf{x}\Vert=\max_{\Vert\mathbf{x}\Vert=1}\Vert A\mathbf{x}\Vert=\Vert A\Vert_2$

$\displaystyle \sigma_n=\min_{\Vert\mathbf{x}\Vert=1}\Vert\Sigma\mathbf{x}\Vert=\min_{\Vert\mathbf{x}\Vert=1}\Vert A\mathbf{x}\Vert=\frac{1}{\Vert A^{-1}\Vert_2}$

$\displaystyle \kappa(A)=\Vert A\Vert_2\cdot\Vert A^{-1}\Vert_2=\frac{\sigma_1}{\sigma_n}\ge 1$

$A$ 為對稱可逆矩陣，計算

$A^2=AA^T=(U\Sigma V^T)(V\Sigma U^T)=U\Sigma^2U^T$

$\displaystyle \kappa(A)=\left|\frac{\lambda_1}{\lambda_n}\right|$

$A\mathbf{v}_j=\sigma_j\mathbf{u}_j,~~~j=1,\ldots,n$

$\displaystyle \mathbf{x}=A^{-1}\mathbf{b}=A^{-1}(\alpha\mathbf{u}_1)=\frac{\alpha}{\sigma_1}\mathbf{v}_1$

$\displaystyle \delta\mathbf{x}=A^{-1}(\delta\mathbf{b})=A^{-1}(\beta\mathbf{u}_n)=\frac{\beta}{\sigma_n}\mathbf{v}_n$

$\displaystyle\frac{\Vert\delta\mathbf{x}\Vert}{\Vert\mathbf{x}\Vert}=\left(\frac{\sigma_1}{\sigma_n}\right)\frac{\vert\beta\vert}{\vert\alpha\vert}=\kappa(A)\frac{\Vert\delta\mathbf{b}\Vert}{\Vert\mathbf{b}\Vert}$

$\displaystyle\frac{\Vert\delta\mathbf{x}\Vert}{\Vert\mathbf{x}\Vert}=\left(\frac{\sigma_n}{\sigma_1}\right)\frac{\vert\beta\vert}{\vert\alpha\vert}=\kappa(A)^{-1}\frac{\Vert\delta\mathbf{b}\Vert}{\Vert\mathbf{b}\Vert}$

$A=\begin{bmatrix} .540&.387\\ .647&.323 \end{bmatrix},~B=\begin{bmatrix} .540&.323\\ .647&.387 \end{bmatrix}$

\begin{aligned} \kappa(A)&=.978920/.077605=12.614\\ \kappa(B)&=.981991/.000001=981,991\approx 10^{6}\end{aligned}

$(A+\delta A)(\mathbf{x}+\delta\mathbf{x})=\mathbf{b}+\delta\mathbf{b}$

$\Vert A^{-1}(\delta A)\Vert\le\Vert A^{-1}\Vert\cdot\Vert\delta A\Vert\le\epsilon\Vert A^{-1}\Vert\cdot\Vert A\Vert=k<1$

$(A+\delta A)(\mathbf{x}+\delta\mathbf{x})=\mathbf{b}+\delta\mathbf{b}$ 等號兩邊左乘 $A^{-1}$

$(I+A^{-1}(\delta A))(\mathbf{x}+\delta\mathbf{x})=\mathbf{x}+A^{-1}(\delta\mathbf{b})$

$\mathbf{x}+\delta\mathbf{x}=( I+A^{-1}(\delta A))^{-1}(\mathbf{x}+A^{-1}(\delta\mathbf{b}))$

$\displaystyle \Vert\mathbf{x}+\delta\mathbf{x}\Vert\le\Vert(I+A^{-1}(\delta A))^{-1}\Vert\cdot(\Vert\mathbf{x}\Vert+\epsilon\Vert A^{-1}\Vert\cdot\Vert\mathbf{b}\Vert)\le\frac{1}{1-k}\left(\Vert\mathbf{x}\Vert+k\frac{\Vert\mathbf{b}\Vert}{\Vert A\Vert}\right)$

$\Vert\mathbf{b}\Vert=\Vert A\mathbf{x}\Vert\le\Vert A\Vert\cdot\Vert\mathbf{x}\Vert$，所以

$\displaystyle \Vert\mathbf{x}+\delta\mathbf{x}\Vert\le\frac{1}{1-k}(\Vert\mathbf{x}\Vert+k\Vert\mathbf{x}\Vert)=\frac{1+k}{1-k}\Vert\mathbf{x}\Vert$

$\Vert\delta\mathbf{x}\Vert\le\Vert A^{-1}\Vert\cdot\Vert\delta\mathbf{b}-(\delta A)(\mathbf{x}+\delta\mathbf{x})\Vert$

$\Vert\delta\mathbf{x}\Vert\le\epsilon\Vert A^{-1}\Vert\cdot\Vert\mathbf{b}\Vert+\epsilon\Vert A^{-1}\Vert\cdot\Vert A\Vert\cdot\Vert\mathbf{x}+\delta\mathbf{x}\Vert$

$\displaystyle\frac{\Vert\delta\mathbf{x}\Vert}{\Vert\mathbf{x}\Vert}\le\epsilon\kappa(A)\frac{\Vert\mathbf{b}\Vert}{\Vert A\Vert\cdot\Vert\mathbf{x}\Vert}+\epsilon\kappa(A)\frac{\Vert\mathbf{x}+\delta\mathbf{x}\Vert}{\Vert\mathbf{x}\Vert}\le\epsilon\kappa(A)\left(1+\frac{1+k}{1-k}\right)=\frac{2\epsilon}{1-k}\kappa(A)$

Gene H. Golub, Charles F. Van Loan，Matrix Computations，2nd ed.，1989。

This entry was posted in 線性代數專欄, 數值線性代數 and tagged , , , , , , , , . Bookmark the permalink.

### 2 則回應給 條件數

1. edge 說：

可以請老師提供partial pivoting的證明嗎??
需要這顆定心丸

• ccjou 說：

我再找找看。