91Ó°ÊÓ

Let \(A\) be real, symmetric, positive definite, and of order \(n\). Consider solving \(A x=b\) using Gaussian elimination without pivoting. The purpose of this problem is to justify that the pivots will be nonzero. (a) Show that all of the diagonal elements satisfy \(a_{i i}>0\). This shows that \(a_{11}\) can be used as a pivot element. (b) After elimination of \(x_{1}\) from equations 2 through \(n\), let the resulting matrix \(A^{(2)}\) be written as $$ A^{(2)}=\left[\begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1 n} \\ 0 & & & \\ \vdots & & \hat{A}^{(2)} & \\ 0 & & & \end{array}\right] $$ Show that \(\hat{A}^{(2)}\). is symmetric and positive definite. This procedure can be continued inductively to each stage of the elimination process, thus justifying the existence of nonzero pivots at evéry step. Hint: To prove \(\hat{A}^{(2)}\) is positive definite, first prove the identity $$ \sum_{i, j=2}^{n} a_{i j}^{(2)} x_{i} x_{j}=\sum_{i, j=1}^{n} a_{i j} x_{i} x_{j}-a_{11}\left[x_{1}+\sum_{j=2}^{n} \frac{a_{j 1}}{a_{11}} x_{j}\right]^{2} $$ for any choice of \(x_{1}, x_{2}, \ldots, x_{n} .\) Then choose \(x_{1}\) suitably.

The system \(A x=b\), $$ A=\left[\begin{array}{rrrrrr} 4 & -1 & 0 & -1 & 0 & 0 \\ -1 & 4 & -1 & 0 & -1 & 0 \\ 0 & -1 & 4 & 0 & 0 & -1 \\ -1 & 0 & 0 & 4 & -1 & 0 \\ 0 & -1 & 0 & -1 & 4 & -1 \\ 0 & 0 & -1 & 0 & -1 & 4 \end{array}\right] \quad b=\left[\begin{array}{l} 2 \\ 1 \\ 2 \\ 2 \\ 1 \\ 2 \end{array}\right] $$ has the solution \(x=[1,1,1,1,1,1]^{T} .\) Solve the system using the Gauss- Jacobi iteration method, and then solve it again using the Gauss-Seidel method. Use the initial guess \(x^{(0)}=0\). Note the rate at which the iteration error decreases. Find the answers with an accuracy of \(\epsilon=.0001\).