科学计算作业 二

科学计算

陆一洲 5140309557

2.45

设 $A^{-1}Bc=d$，那我们有 $Bc=Ad$.
我们先计算 $Bc$，复杂度为 $O(n^2)$，再解方程 $Bc=Ad$，复杂度为 $O(n^3)$。
$\therefore$ 总体复杂度为 $O(n^2 + n^3)=O(n^3)$

2.48

$A^Tx=(LU)^Tx=U^T(L^Tx)=b$
设 $L^Tx=y$ ，由于 $L$ 由矩阵分解而
$\therefore$ 求解 $U^Ty=b$ 的复杂度为 $O(n^2)$
又 求解 $U^T$ 的复杂度也为 $O(n^2)$
$\therefore$ 解出 $y$ 总复杂度为 $O(n^2)$。
同理 求解 $x$ 的复杂度也为 $O(n^2)$
$\therefore$ 最终总复杂度为 $O(n^2)$

2.49

$\because$ $L$ 是满秩下三角矩阵
$\therefore$ 求解 $L^{-1}$ 与 $Lx=y$ 的复杂度为 $O(n^2)$
(a) $x=bL^{-1}P^{-1}$ 复杂度为 $O(n^2)$
(b) $x=bP^{-1}L^{-1}$ 复杂度为 $O(n^2)$

2.51

$\because$ $\forall \,v=(x,y)$, $\| v \|_1=|x|+|y|$, $\| v \|_{\infty}=\max(|x|,|y|)$
$\therefore$ $\| v \|_1=|x|+|y|>\max(|x|,|y|)=\| v \|_{\infty}$
$\therefore$ 不可能

2.52

$\| A \|_1$只需要在 $O(n^2)$ 的时间，然而 $\| A \|_2$ 需要计算奇异值，需要 $O(n^3)$ 的时间，所以 $\| A \|_1$ 更容易计算。

2.61

ill-conditioned: (a) (d)
well-conditioned: (b) (c)

2.77

$\begin{pmatrix} 4 & 2 \\ 2 & 2 \\ \end{pmatrix} = \begin{pmatrix} 2 & 0 \\ 1 & 1 \\ \end{pmatrix} \begin{pmatrix} 2 & 1 \\ 0 & 1 \\ \end{pmatrix}$

2.10

即证 $PP^T=I$。rtui
当 $i=j$，$a_{ij}=\sum_{k=1}^n a_{ik}a'_{kj}=a'_{p_ij}=a_{jp_i}=a_{ip_i}=1$；
当 $i\neq j$，$a_{ij}=\sum_{k=1}^n a_{ik}a'_{kj}=a'_{p_ij}=a_{jp_i}=0$
综上所述，$PP^T=I$。

2.31

(1) 因为 $A$ 是一个正定矩阵，所以当 $x\neq o$，$x^TAx>0$，$\|x\|_A=(x^TAx)^{1/2}>0$。
(2) $\forall\ \gamma$, $\|\gamma x\|_A=|\gamma|\|x\|_A=((\gamma x)^TA(\gamma x))^{1/2}=|\gamma|(x^TAx)^{1/2}$。
(3) |x+y|_A\leqslant|x|_A+|y|_A。因为 $A$ 正定，所以 $\exists\ C$，使得 $A=C^TC$，记 $x'=Cx$，$y'=Cy$

$$\begin{align*} \|x+y\|_A^2&=(x+y)^TA(x+y)\\ &=x'^Tx'+y'^Ty'+2x'^Ty'\\ (\|x\|_A+\|y\|_A)^2&=x'^Tx'+y'Ty'+2(x'^Tx'y'^Ty')^{1/2} \end{align*}$$
显然 $x'^Ty'\leqslant(x'^Tx'y'^Ty')^{1/2}$，所以命题成立。

代码题

核心代码：

double error=0;
for (int T=0; T<100; T++){
    n=Git<int>();
    A=L=U=Matrix(n,n);
    for (int i=0; i<n; i++)
        for (int j=0; j<n; j++){
            scanf("%lf", a[i][j]);
            U[i]=A[i][j]=a[i][j];
        }
    LU_Elimination(A,L,U);
    error+=(A-L*U).Value()/A.value()
}
error/=100;
cout<<error<<endl;

1.平凡非奇异矩阵：

n	不选主元	选主元
1	0	0
2	1.01153e-017	0
3	6.01559e-018	2.11871e-017
4	6.47473e-017	4.61901e-017
5	1.17848e-016	3.91786e-017
6	1.78841e-016	6.14059e-017
7	6.22113e-016	9.41769e-017
8	2.48236e-016	1.07673e-016
9	8.40014e-016	1.13877e-016
10	1.07437e-015	1.50405e-016
20	4.07612e-015	2.75951e-016
30	4.32251e-014	3.88372e-016
40	4.20150e-014	5.99496e-016
50	5.08233e-013	7.00987e-016
60	1.32075e-013	9.20237e-016
70	1.33806e-013	1.04561e-015
80	4.75215e-013	1.23230e-015
90	4.21401e-013	1.42855e-015
100	5.90438e-013	1.56641e-015

显然不选主元的误差相对更大，而且随着 $n$ 的增加越来越显著。说明选取主元可以提升精确度。

2.正定矩阵

n	不选主元	选主元
1	0	0
2	0	0
3	7.50643e-018	4.51165e-018
4	1.63602e-017	1.35679e-017
5	3.14955e-017	2.79771e-017
6	4.39255e-017	4.37454e-017
7	5.16210e-017	5.29137e-017
8	6.37737e-017	6.26609e-017
9	6.72592e-017	6.92372e-017
10	7.59455e-017	7.31411e-017
20	1.19586e-016	1.19897e-016
30	1.54374e-016	1.54739e-016
40	1.79363e-016	1.79698e-016
50	1.98275e-016	1.98923e-016
60	2.20468e-016	2.20408e-016
70	2.41584e-016	2.40563e-016
80	2.52688e-016	2.52600e-016
90	2.71620e-016	2.71558e-016
100	2.85865e-016	2.86123e-016

差异不大，可能是因为随机生成的正定矩阵条件数比较小造成的。

3.对角占优矩阵

n	不选主元	选主元
1	0	0
2	2.96766e-017	2.96766e-017
3	2.05896e-017	2.05896e-017
4	4.79800e-017	4.79800e-017
5	5.64444e-017	5.64444e-017
6	8.77177e-017	8.77177e-017
7	1.00794e-016	1.00794e-016
8	1.13478e-016	1.13478e-016
9	1.23648e-016	1.23648e-016
10	1.30896e-016	1.30896e-016
20	2.14969e-016	2.14969e-016
30	3.08761e-016	3.08761e-016
40	4.09684e-016	4.09684e-016
50	4.94445e-016	4.94445e-016
60	5.62137e-016	5.62137e-016
70	6.45086e-016	6.45086e-016
80	6.8769e0-016	6.8769e0-016
90	7.69171e-016	7.69171e-016
100	7.56749e-016	7.56749e-016

在对角占优矩阵中，选取的主元都在对角线上，与不选主元没区别，所以误差也一样。