course |
course_year |
question_number |
tags |
title |
year |
Numerical Analysis |
II |
106 |
II |
2017 |
Numerical Analysis |
|
Paper 1, Section II, A |
2017 |
State the Householder-John theorem and explain how it can be used in designing iterative methods for solving a system of linear equations $A \mathbf{x}=\mathbf{b}$. [You may quote other relevant theorems if needed.]
Consider the following iterative scheme for solving $A \mathbf{x}=\mathbf{b}$. Let $A=L+D+U$, where $D$ is the diagonal part of $A$, and $L$ and $U$ are the strictly lower and upper triangular parts of $A$, respectively. Then, with some starting vector $\mathbf{x}^{(0)}$, the scheme is as follows:
$$(D+\omega L) \mathbf{x}^{(k+1)}=[(1-\omega) D-\omega U] \mathbf{x}^{(k)}+\omega \mathbf{b} .$$
Prove that if $A$ is a symmetric positive definite matrix and $\omega \in(0,2)$, then, for any $\mathbf{x}^{(0)}$, the above iteration converges to the solution of the system $A \mathbf{x}=\mathbf{b}$.
Which method corresponds to the case $\omega=1 ?$