Let
$$
A=\left[\begin{array}{rrr}
0 & -2 & 1 \\
1 & -1 & 3 \\
-2 & 1 & -4
\end{array}\right] \quad \text { and } \quad b=\left[\begin{array}{r}
1 \\
0 \\
-1
\end{array}\right]
$$
(a) [5 Points] Apply LU factorization with partial pivoting to $A$.
(b) [4 Points] Use your results obtained in (a) to solve the linear system $A x=b$.
Solution: In the first step, we need to interchange rows 1 and 3:
$$
P=\left[\begin{array}{lll}
0 & 0 & 1 \\
0 & 1 & 0 \\
1 & 0 & 0
\end{array}\right], \quad\left[\begin{array}{rrr}
-2 & 1 & -4 \\
1 & -1 & 3 \\
0 & -2 & 1
\end{array}\right] \quad \longrightarrow \quad\left[\begin{array}{rrr}
-2 & 1 & -4 \\
-\frac{1}{2} & -\frac{1}{2} & 1 \\
0 & -2 & 1
\end{array}\right]
$$
In the second step, we need to interchange rows 2 and 3 :
$$
\left.P=\left[\begin{array}{lll}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{array}\right], \quad\left[\begin{array}{rrr}
-2 & 1 & -4 \\
0 & -2 & 1 \\
-\frac{1}{2} & -\frac{1}{2} & 1
\end{array}\right] \stackrel{0}{2}\right] \stackrel{0}{\longrightarrow}\left[\begin{array}{rrr}
-2 & 1 & -4 \\
0 & -2 & 1 \\
-\frac{1}{2} & \frac{1}{4} & \frac{3}{4}
\end{array}\right]
$$
Thus
$$
P=\left[\begin{array}{lll}
0 & 0 & 1 \\
1 & 0 & 0 \\
0 & 1 & 0
\end{array}\right], \quad L=\left[\begin{array}{rrr}
1 & 0 & 0 \\
0 & 1 & 0 \\
-\frac{1}{2} & \frac{1}{4} & 1
\end{array}\right], \quad \text { and } \quad U=\left[\begin{array}{rrr}
-2 & 1 & -4 \\
0 & -2 & 1 \\
0 & 0 & \frac{3}{4}
\end{array}\right]
$$
Since $P A=L U$, solving $A x=b$ is equivalent to solving the lower-triangular linear system $L y=P b$ for $y$ and the upper-triangular linear system $U x=y$ for $x$.
Solution of $L y=P b$ :
$$
\left[\begin{array}{rrr}
1 & 0 & 0 \\
0 & 1 & 0 \\
-\frac{1}{2} & \frac{1}{4} & 1
\end{array}\right] y=P b=\left[\begin{array}{r}
-1 \\
1 \\
0
\end{array}\right] \quad \Longrightarrow \quad y=\left[\begin{array}{r}
-1 \\
1 \\
-\frac{3}{4}
\end{array}\right]
$$
Solution of $U x=y$ :
$$
\left[\begin{array}{rrr}
-2 & 1 & -4 \\
0 & -2 & 1 \\
0 & 0 & \frac{3}{4}
\end{array}\right] x=\left[\begin{array}{r}
-1 \\
1 \\
-\frac{3}{4}
\end{array}\right] \quad \Longrightarrow \quad x=\left[\begin{array}{r}
2 \\
-1 \\
-1
\end{array}\right]
$$
Let $A \in \mathbb{R}^{6 \times 6}$ be a matrix with characteristic polynomial
$$
p_{A}(\lambda):=\operatorname{det}(A-\lambda I)=(\lambda+4)(\lambda-1)(\lambda-2)(\lambda-3)\left(\lambda^{2}+1\right)
$$
(a) [2 Points] Determine all eigenvalues of $A$.
(b) [3 Points] We apply the power method to $A$. Which eigenvalue does the method converge to and what is the the ratio of the convergence rate?
(c) [4 Points] We apply inverse iteration with shift $s=\frac{7}{4}$ to $A$. Which eigenvalue does the method converge to and what is the ratio of the convergence rate?
Solution: The eigenvalues of the shifted and inverted matrix
Solution: The eigenvalues of $A$ are the zeros of $p_{A}(\lambda):$
$$
-4,1,2,3, i,-i
$$
where $i=\sqrt{-1}$
The dominant eigenvalue of $A$ is $-4,$ and the second largest in absolute value is $3 .$ Thus the power method converges to the eigenvalue -4 and
$$
\text { ratio }=\frac{3}{4}
$$
The eigenvalues of the shifted and inverted matrix
$$
(A-s I)^{-1}=\left(A-\frac{7}{4} I\right)^{-1}
$$
are
$$
\frac{1}{-4-\frac{7}{4}}, \quad \frac{1}{1-\frac{7}{4}}, \quad \frac{1}{2-\frac{7}{4}}, \quad \frac{1}{3-\frac{7}{4}}, \quad \frac{1}{1-\frac{7}{4}}, \quad \frac{1}{-\mathrm{i}-\frac{7}{4}}
$$
The dominant eigenvalue of $(A-s I)^{-1}$ is
$$
\frac{1}{2-\frac{7}{4}}=4
$$
and the second largest in absolute value is
$$
\frac{1}{1-\frac{7}{4}}=-\frac{4}{3}
$$
Thus inverse iteration converges to the eigenvalue 2 of $A$ and
ratio $=\frac{1}{3}$.
Let
$$
A=\left[\begin{array}{rc}
1 & -1+\delta \\
-1 & 1
\end{array}\right]
$$
where $\delta \in \mathbb{R}$ is a parameter.
(a) [2 Points] Show that $A$ is nonsingular if, and only if, $\delta \neq 0$. Determine $A^{-1}$ for $\delta \neq 0$.
(b) [4 Points] For $\delta \neq 0$, determine the condition number $\kappa_{1}(A)$ of $A$ with respect to the matrix norm $\|\cdot\|_{1}$
(c) [3 Points] Discuss the accuracy of the computed solution that you can expect when you solve linear systems $A x=b$ numerically.
Solution: Since
$$
\operatorname{det} A=1 \cdot 1-(-1+\delta) \cdot(-1)=\delta
$$
the matrix $A$ is nonsingular if, and only if, $\delta \neq 0$.
For $\delta \neq 0$
$$
A^{-1}=\frac{1}{\operatorname{det} A} \operatorname{Adj}(A)=\frac{1}{\delta}\left[\begin{array}{cc}
1 & 1-\delta \\
1 & 1
\end{array}\right]
$$
Recall that $\|\cdot\|_{1}$ is the maximumabsolute column sum of the matrix. Thus, we have
$$
\|A\|_{1}=\max \{2,|-1+\delta|+1\}=\left\{\begin{array}{ll}
2 & \text { if } 0<\delta \leq 2 \\
1+|\delta-1| & \text { otherwise }
\end{array}\right.
$$
and
$$
\left\|A^{-1}\right\|_{1}=\frac{1}{|\delta|} \max \{2,|1-\delta|+1\}=\left\{\begin{array}{ll}
\frac{2}{|\delta|} & \text { if } 0<\delta \leq 2, \\
\frac{1+|\delta-1|}{|\delta|} & \text { otherwise. }
\end{array}\right.
$$
It follows that
$$
\kappa_{1}(A)=\|A\|_{1} \cdot\left\|A^{-1}\right\|_{1}=\left\{\begin{array}{ll}
\frac{4}{|\delta|} & \text { if } 0<\delta \leq 2, \\
\frac{(1+|\delta-1|)^{2}}{|\delta|} & \text { otherwise }
\end{array}\right.
$$
If $\kappa_{1}(A) \gg 1,$ the problem of solving linear systems $A x=b$ is ill-conditioned. In this case, we cannot expect to solve $A x=b$ numerically with any reasonable accuracy, no matter what algorithm we employ. The expression for $\kappa_{1}(A)$ obtained in (b) shows that $A x=b$ is ill-conditioned for $\delta \approx 0$ and for $|\delta| \gg 1$.
E-mail: [email protected] 微信:shuxuejun
MATH 4260 – Numerical Analysis: Linear and Nonlinear Problems代写线性代数代写
请认准uprivateta™
更多统计代写案例请参考另外一份统计代写案例
uprivateta™是一个服务全球中国留学生的专业代写公司
专注提供稳定可靠的北美、澳洲、英国代写服务
专注于数学，统计，金融，经济，计算机科学，物理的作业代写服务
