My name is Hanzhang Yin, and I have developed this website as a resource to facilitate the review of key concepts in abstract algebra, and it is not fully completed. Feel free to email me at hanyin@ku.edu if there are any errors or suggestions for improvement.
1. Consider the function \( g(x) = \frac{1}{2}(1 + 2x - x^2) \) defined on the closed interval \([1/2, 3/2]\).
Proof (a). Suppose that \(a, b\in [1/2, 3/2]\) and \(a\neq b\). Then, we have \[ |g(a) - g(b)| = \left|\frac{1}{2}(1 + 2a - a^2) - \frac{1}{2}(1 + 2b - b^2)\right| = \left|\frac12 (b^2 - a^2) + a - b\right| = \left|\frac12(b-a)(b+a) + a - b\right|. \] \[ \left|\frac{g(a) - g(b)}{a - b}\right| = \left|-\frac12(b+a) + 1\right|. \] Since \(a, b\in [1/2, 3/2]\), we have \(1 \leq b+a \leq 3\). Then, we can have \(|-\frac12(b+a) + 1| \leq \frac12\). Thus, we can know that \[ |g(a) - g(b)| \leq \frac12 |a - b|. \] By the Contraction Mapping Theorem, we can know that \(g(x)\) has a unique fixed point on the given interval. \( \blacksquare \)
Proof (b). Since we already showed that \(g(x)\) is a contraction mapping, we can know that the fixed point iteration \(x_n = g(x_{n-1})\) converges to the unique fixed point by contractive mapping theorem. \( \blacksquare \)
Solution (c). We firstly found the point it will converge to. Let \(g(x) = x\). We have \[ \frac{1}{2}(1 + 2x - x^2) = x. \] We solve for \(x\) and we have \(x = \pm 1\). Since it is in \([1/2, 3/2]\), we have \(x = 1\). Now, we let \[ \dfrac{\left|\frac12(1 + 2x - x^2) - 1\right|}{\left|x - 1\right|} = \dfrac{\left|\frac12(1 + 2x - x^2) - 1\right|}{\left|x - 1\right|} = \dfrac{\left|\frac12(1 + 2x - x^2) - 1\right|}{\left|x - 1\right|} = \dfrac{\left|-\frac12(x-1)^2\right|}{\left|x - 1\right|} = \dfrac{\frac12|x-1|^2}{|x-1|} = \dfrac12|x-1|. \] Thus, we can see that \[ \dfrac{\left|\frac12(1 + 2x - x^2) - 1\right|}{\left|x - 1\right|^2} = \dfrac12. \] Therefore, we say that the convergence rate of the fixed point iteration is quadratic.
2. (a) Consider the Gaussian quadrature of the form \[ G_2(f) = w f(-d) + w f(d) \approx \int_{-h}^{h} f(x) \, dx, \tag*{(1)} \] where \( h \) is a given positive number and \( w, d \) are unknown real numbers. Determine this Gaussian quadrature by finding \( w \) and \( d \).
(b) The Gaussian quadrature (1) has an error formula \[ \int_{-h}^{h} f(x) \, dx - G_2(f) = C f^{(r+1)}(\xi), \] where \( \xi \in [-h, h] \). Determine the constant \( C \) and the integer \( r \).
(c) Consider the composite Gaussian quadrature \( G_m(f) \) that approximates the integral \[ I(f) = \int_{0}^{b} f(x) \, dx. \] Let \( m > 0 \) be an integer and \( h = b/(2m) \). Divide the interval \([0, b]\) into \( m \) equally spaced sub-intervals \([x_k, x_{k+1}]\) of length \( 2h \) for \( k = 0, 1, \ldots, m-1 \), where the endpoints are determined by \( x_k = 2hk \) for \( k = 0, 1, \ldots, m \). The composite Gaussian quadrature \( G_m(f) \) is constructed by adapting (1) to each sub-interval \([x_k, x_{k+1}]\) ( \( k = 0, \ldots, m-1 \)). Derive a formula for \( G_m(f) \) and the error formula \[ I(f) - G_m(f) = D f^{(s+1)}(\eta), \quad \eta \in [0, b]. \] The constant \( D \) and the integer \( s \) need to be provided.
Solution (a). Let \(f(x) = 1\), we have \[ \int_{-h}^{h} f(x) \, dx = \int_{-h}^{h} 1 \, dx = 2h = w\cdot 1 + w\cdot 1 = 2w. \] Hence, we have \(w = h\). Now, set \(f(x) = x\), we have \[ \int_{-h}^{h} f(x) \, dx = \int_{-h}^{h} x \, dx = 0 = w\cdot (-d) + w\cdot d = 0, \] which does not provide too much information. Now, we set \(f(x) = x^2\), we have \[ \int_{-h}^{h} f(x) \, dx = \int_{-h}^{h} x^2 \, dx = \frac{2h^3}{3} = h\cdot d^2 + h\cdot d^2 = 2hd^2. \] Thus, we have \(d = \frac{\sqrt{3}h}{3}\). Hence, we have \(w = h\) and \(d = \frac{\sqrt{3}h}{3}\).
3. Consider the numerical ODE method \[ y_{k+1} = y_{k-1} + \frac{h}{3} \left( f(t_{k+1}, y_{k+1}) + 4f(t_k, y_k) + f(t_{k-1}, y_{k-1}) \right) \] for solving the initial value problem \( y' = f(t, y) \) for \( t \in (a, b] \) with \( y(a) = \alpha \), where \( h = \frac{(b-a)}{n} \), \( t_k = a + kh \) for \( k = 0, 1, \ldots, n \), and \( n > 0 \) is an integer.
(a) State whether this method is explicit or implicit, single-step or multistep.
(b) State and justify whether this method is weakly stable, strongly stable, or unstable.
(c) Derive the order of the local truncation error.
Solution (a). This method is implicit and multistep.
Solution (b). We firstly find the characteristic polynomial of the method. Hence, we have \(p(x) = x^2 - x\). Then, we can know that \(p(x) = x(x-1)\). Since the roots of the characteristic polynomial are \(0\) and \(1\), \(|0| \lt 1\) and \(p(1) = 0\). Moreover, \(p'(x) = 2x - 1\), and \(p'(1) = 1 \neq 0\). Therefore, we can know that this method is strongly stable.
4. Suppose that the real square matrix \( A = [a_{ij}] \in \mathbb{R}^{n \times n} \) has the properties \[ a_{ii} > \sum_{j=1, j \neq i}^{n} |a_{ij}| = |a_{i1}| + \ldots + |a_{i,i-1}| + |a_{i,i+1}| + \ldots + |a_{in}|, \quad i = 1, 2, \ldots, n. \]
(a) Prove that each eigenvalue of \( A \) has a positive real part.
(b) Prove \( \det A > 0 \).
(c) Prove that \( A \) has a unique LU factorization \( A = LU \), where \( L \) is unit lower triangular and \( U \) is upper triangular. Also, prove that all the diagonal entries of \( U \) are positive.
Proof (a). Since \(a_{ii} > \sum_{j=1, j \neq i}^{n} |a_{ij}| = |a_{i1}| + \ldots + |a_{i,i-1}| + |a_{i,i+1}| + \ldots + |a_{in}|\) for \(i = 1, 2, \ldots, n\). According to \(\textbf{the Gershgorin circle theorem}\), we have each eigenvalue of \(A\) \(\mu\) is in at least one of the Gershgorin discs, which is defined as \[ |\mu- a_{ii}| \leq \sum_{j=1, j \neq i}^{n} |a_{ij}|. \] Since \(a_ii>0\) and the radius of the dist is less than \(a_ii\), we can know that each disk is only in the right half plane. Therefore, each eigenvalue of \(A\) has a positive real part. \(\blacksquare\)
Proof (b). Suppose that \(\lambda_1, \lambda_2, \dots, \lambda_n\) are the eigenvalues of \(A\). If each \(\lambda_i\) is real, then we can know that each \(\lambda_i>0\), and hence \(\det A = \lambda_1\lambda_2\cdots\lambda_n > 0\). If there exists some complex eigenvalue, then we want to show that the complex conjugate of the eigenvalue is also the eigenvalue of \(A\). Suppose that \(p(x) = \text{det}(A - xI)\) is the characteristic polynomial of \(A\) and \(\lambda\) is a complex eigenvalue of \(A\). Firstly, we have \(p(x) = x^n + a_{n-1}x^{n-1} + \ldots + a_1x + a_0\), where \(a_i \in \mathbb{R}\). Then we can know that \(p(\lambda) = \lambda^n + a_{n-1}\lambda^{n-1} + \ldots + a_1\lambda + a_0 = 0\). Since \(\overline{p(\lambda)} = \overline{0} = 0\), we have \[ \overline{p(\lambda)} = \overline{\lambda^n + a_{n-1}\lambda^{n-1} + \ldots + a_1\lambda + a_0} = \overline{\lambda}^n + a_{n-1}\overline{\lambda}^{n-1} + \ldots + a_1\overline{\lambda} + a_0 = 0. \] Therefore, we can know that the complex conjugate of the eigenvalue is also the eigenvalue of \(A\). And \(\lambda\cdot \overline{\lambda} = a^2 + b^2 >0\), where \(\lambda = a + bi\). Hence, we can know that \(\det A > 0\). \(\blacksquare\)
Proof (c). Suppose that \(A\) has two \(LU\) factorizations, i.e., \(A = L_1U_1 = L_2U_2\), where \(L_1, L_2\) are lower triangular matrices and \(U_1, U_2\) are upper triangular matrices. Given the Gaussian elimination, we know that both \(L_1\) and \(L_2\) have 1's on the diagonal. And the inverse of \(L_1\) is the matrix such as all the diagonal entries are 1 and if \((i, j)\)-entry of \(L_1\) is \(l_{ij}\) where \(i\neq j\), then the \((i, j)\)-entry of the inverse of \(L_1\) is \(-l_{ij}\). Hence, we can know that the inverse of \(L_1\) is also a lower triangular matrix. If the inverse of an upper triangular matrix exists, then the inverse is also an upper triangular matrix. Since \(\det(A) = \det(L_1)\det(U_1) = \det(L_2)\det(U_2)\), we have \(\det(U_1) = \det(U_2) = \det(A)>0\). Thus, we can know that \(U_2^{-1}\) exists and \(U_1U_2^{-1} = L_2L_1^{-1}\). Since the product of two lower triangular matrices is a lower triangular matrix, \(L_2L_1^{-1}\) is lower triangular. Since the product of two upper triangular matrices is an upper triangular matrix, \(U_1U_2^{-1}\) is upper triangular. Given that \(U_1U_2^{-1}\) is both lower triangular and upper triangular, we can know that \(U_1U_2^{-1}\) is a diagonal matrix. Since \(L_2\cdot L_1^{-1}\) has all the diagonal entries of \(1\), we can know that \(U_1U_2^{-1}\) has all the diagonal entries of \(1\). Then we have \(U_1U_2^{-1} = I\), which implies that \(U_1 = U_2\).
For the second part, we will use induction to show that all diagonal entries of \(U\) are positive. Given the process of Gaussian elimination, we know that \[ L_1 = \begin{bmatrix} 1 & 0 & 0 & \cdots & 0\\ l_{21} & 1 & 0 & \cdots & 0\\ l_{31} & 0 & 1 & \cdots & 0\\ \vdots & \vdots & \vdots & \ddots & \vdots\\ l_{n1} & 0 & 0 & \cdots & 1 \end{bmatrix}. \] Thus, we can know that the first diagonal entry of \(U\) is the first diagonal entry of \(L_1\cdot A\), which is the first diagonal entry of \(A\). Since the first diagonal entry of \(A\), say \(a_{11}\), is positive by assumption, we can know that the first diagonal entry of \(U\) is positive.
5. Consider the square matrix \( A\in \mathbb{C}^{n\times n}\).Suppose that \(\sigma_1\) and \(\sigma_n\) are the largest and the smallest singular values of \(A\), respectively. Let \(\|\cdot \|_2\) be the \(2\)-norm.
(a) Prove \[ \sigma_1 = \max_{\|x\|_2 = 1}\|Ax\|_2, \qquad \sigma_n = \min_{\|x\|_2 = 1}\|Ax\|_2. \]
(b) Let \(\Lambda(A)\) be the spectrum of \(A\) (the set of all the eigenvalues of \(A\)). Prove \[ \max_{\lambda\in\Lambda(A)}|\lambda|\leq \sigma_1, \qquad \min_{\lambda\in\Lambda(A)}|\lambda|\geq \sigma_n. \] Also prove that both the equalities hold if \(A\) is Hermitian, i.e., \(A\) satisfies \(A = A^*\), where \(A^*\) is the adjoint (conjugate transpose) of \(A\).
Proof (a).Firstly, we showed that \(\sigma_1 = \max\limits_{\|x\|_2 = 1}\|Ax\|_2\). Since every matrix has a \(SVD\), we defined that \(A = U\Sigma V^*\), where \(U, V\) are unitary matrices and \(\Sigma\) is a diagonal matrix with singular values on the diagonal. Moreover, let the \(\sigma_{11}\) entry of \(\Sigma\) be \(\sigma_1\) and the \(\sigma_{nn}\) entry of \(\Sigma\) be \(\sigma_n\). Let \(\vec{v}\) be the vector such that \(\|\vec{v}\|_2 = 1\) and \(\max\limits_{\|x\|_2 = 1}\|Ax\|_2 = \|Av\|_2\). And we denote \(V^*\vec{v} = \vec{u} = [u_1, \dots, u_n]^T\). Hence, we have \[ \|Av\|_2 = \|U\Sigma V^*v\|_2 = \|\Sigma\vec{u}\|_2 = \left\|\begin{bmatrix}u_1\sigma_1\\ \vdots \\ u_n\sigma_n \end{bmatrix}\right\|_2 = \sqrt{\sum_{i=1}^{n}u_i^2\sigma_i^2} \leq \sqrt{\sum_{i=1}^{n}u_i^2\sigma_1^2} = \sigma_1\sqrt{\sum_{i=1}^{n}u_i^2} \] Since \(V^*\) is unitary and \(\|\vec{v}\|_2 = 1\), we have that \(\|\vec{u}\|_2 = \|V^*\vec{v}\|_2 = \|\vec{v}\| = 1\). Therefore, we have \(\sum_{i=1}^{n}u_i^2 = 1\). Thus, we get \(\|Av\|_2 \leq \sigma_1\). Suppose that \(V = \begin{bmatrix} \vec{v_1} & \vec{v_2} & \cdots & \vec{v_n} \end{bmatrix}\) where \(\vec{v_i}\) is the column vector of \(V\). Then, we have \(V^* = \begin{bmatrix} \vec{v_1}^* \\ \vec{v_2}^* \\ \vdots \\ \vec{v_n}^* \end{bmatrix}\). Since \(V\) is unitary, the columns of \(V\) are orthonormal. Thus, we have \[ \begin{align} \sigma_1 = \|\Sigma\cdot \vec{e_1}\|_2 = \|U\Sigma\cdot \vec{e_1}\|_2 = \|U\Sigma V^*\vec{v_1}\|_2 = \|A\vec{v_1}\|_2 \leq \max_{\|x\|_2 = 1}\|Ax\|_2. \end{align} \] Hence, we showed that \(\sigma_1 = \max_{\|x\|_2 = 1}\|Ax\|_2\).
Now, we showed that \(\sigma_n = \min\limits_{\|x\|_2 = 1}\|Ax\|_2\). We will use the same \(SVD\) of \(A\). Then, we can get \[ \min_{\|x\|_2 = 1}\|Ax\|_2 \leq \|U\Sigma V^*\vec{v_n}\|_2 = \|\Sigma V^*\vec{v_n}\|_2 = \|\Sigma\vec{e_n}\|_2 = \left\|\begin{bmatrix} 0 \\ \vdots \\ 0 \\ \sigma_n \end{bmatrix}\right\|_2 = \sigma_n. \] Similarly, we let \(\vec{v}\) be the vector such that \(\|\vec{v}\|_2 = 1\) and \(\min\limits_{\|x\|_2 = 1}\|Ax\|_2 = \|Av\|_2\). And we denote \(V^*\vec{v} = \vec{u} = [u_1, \dots, u_n]^T\). Hence, we have \[ \|Av\|_2 = \|U\Sigma V^*v\|_2 = \|\Sigma\vec{u}\|_2 = \left\|\begin{bmatrix}u_1\sigma_1\\ \vdots \\ u_n\sigma_n \end{bmatrix}\right\|_2 = \sqrt{\sum_{i=1}^{n}u_i^2\sigma_i^2} \geq \sqrt{\sum_{i=1}^{n}u_i^2\sigma_n^2} = \sigma_n\sqrt{\sum_{i=1}^{n}u_i^2} \] Since \(V^*\) is unitary and \(\|\vec{v}\|_2 = 1\), we have that \(\|\vec{u}\|_2 = \|V^*\vec{v}\|_2 = \|\vec{v}\| = 1\). Therefore, we have \(\sum_{i=1}^{n}u_i^2 = 1\). Thus, we get \(\|Av\|_2 \geq \sigma_n\). Therefore, we have \(\sigma_n = \min_{\|x\|_2 = 1}\|Ax\|_2\). \( \blacksquare \)
Proof (b). Firstly, we know that \(\sigma_1 = \max\limits_{\|x\|_2 = 1}\|Ax\|_2\) and \(\sigma_n = \min\limits_{\|x\|_2 = 1}\|Ax\|_2\). Suppose that \(\lambda_1\) is the eigenvalue such that \(|\lambda_1| = \max\limits_{\lambda\in\Lambda(A)}|\lambda|\) and \(v_1\) is the corresponding eigenvector where \(\|v_1\|_2 = 1\). Thus, we have \[ \sigma_1 = \max_{\|x\|_2 = 1}\|Ax\|_2\geq \|Av_1\|_2 = \|\lambda_1v_1\|_2 = |\lambda_1|\cdot \|v_1\|_2 = |\lambda_1|. \] Similarly, suppose that \(\lambda_2\) is the eigenvalue such that \(|\lambda_2| = \min_{\lambda\in\Lambda(A)}|\lambda|\) and \(v_2\) is the corresponding eigenvector where \(\|v_2\|_2 = 1\). Hence, we can get \[ \sigma_n = \min_{\|x\|_2 = 1}\|Ax\|_2\leq \|Av_2\|_2 = \|\lambda_1v_1\|_2 = |\lambda_2|\cdot \|v_2\|_2 = |\lambda_2|. \] Now, suppose that \(A\) is hermitian. Then, we have \(A = A^*\). Then we want to show that we have \(A\) is unitarily diagonalizable. For any square matrix (A), it has schur form as \(A = URU^*\), where \(U\) is unitary and \(T\) is upper triangular. Since \(A = A^*\), we have \(A = URU^* = (URU^*)^* = UR^*U^* = A^*\). Since \(U\) is unitary, we have \(R = R^*\). Since \(R\) is an upper triangular matrix and \(R^*\) is a lower triangular matrix, we have \(R\) is a diagonal matrix. Therefore, we have \(A = URU^* = UDU^*\), where \(D\) is a diagonal matrix and \(U\) is unitary. Hence, the entries of \(D\) are the eigenvalues of \(A\). Since \(A = UDU^*\), we have \(A\) is unitarily diagonalizable.
6. Consider the real symmetric matrix \( A = \begin{bmatrix} 0 & \epsilon \\ \epsilon & a \end{bmatrix} \), where \( a \) and \( \epsilon \) are real and \( \epsilon > 0 \) is sufficiently small.
(a) Compute the matrix \( A_1 \) generated by performing one QR iteration on \( A \) with the Rayleigh quotient shift.
(b) Use 6(a) to discuss the convergence behavior and convergence rate of the QR algorithm with the Rayleigh quotient shift applied to \( A \).
Solution (a). Suppose that the initial vector we pick is \(v = \begin{bmatrix} x \\ y \end{bmatrix}\) such that \(\|v\|_2=1\). Thus, we can find the Rayleigh quotient of \(A\) as \[ r = \frac{v^*Av}{v^*v} = \frac{2\epsilon xy + y^2a}{x^2 + y^2} = 2\epsilon xy + ay^2. \] Then, we want to find th \(QR\) factorization of \[ \begin{align} A - rI &= \begin{bmatrix} -r & \epsilon \\ \epsilon & a - r \end{bmatrix} \\ &= \begin{bmatrix} -2\epsilon xy - ay^2 & \epsilon \\ \epsilon & a - 2\epsilon xy - ay^2 \end{bmatrix}. \end{align} \] We will use Given rotation to find the \(QR\) factorization of \(A - rI\). We have \[ \begin{bmatrix} c & -s \\ s & c \end{bmatrix}\cdot \begin{bmatrix} -2\epsilon xy - ay^2 \\ \epsilon \end{bmatrix} = \begin{bmatrix} r \\ 0 \end{bmatrix}. \] Since \(r = \sqrt{(-2\epsilon xy - ay^2)^2 + \epsilon^2}\), we have \[ c = \frac{-2\epsilon xy - ay^2}{r} \quad \text{and} \quad s = \frac{\epsilon}{r}. \] Then, we have our \(R\) as \[ Q = \begin{bmatrix} \frac{-2\epsilon xy - ay^2}{r} & \frac{\epsilon}{r} \\ -\frac{\epsilon}{r} & \frac{-2\epsilon xy - ay^2}{r} \end{bmatrix}\cdot \begin{bmatrix} -2\epsilon xy - ay^2 & \epsilon \\ \epsilon & a - 2\epsilon xy - ay^2 \end{bmatrix} = \begin{bmatrix} r & 0 \\ 0 & -\frac{2\epsilon xy + ay^2}{r} \end{bmatrix}. \]