Fixed-Point Iteration

Solution of a nonlinear fixed point problem

Consider the fixed-point problem \(x = g(x)\) for a continuously differentiable real-valued function \(g\) and assume that it has a solution \(\alpha \) for which \(|g'(\alpha )| < 1\). State and prove a convergence theorem for fixed point iteration \(x^{(k+1)} = g(x^{(k)})\) for this problem. Note: Do not assume more about the function \(g\) than is stated in the problem.

Fixed-point iteration for linear systems.

1. For \(T \in \mathbb {R}^{m \times m}\) and any matrix norm, show that \(\|T^k\| \to 0\) as \(k \to \infty \) if and only if \(\rho (T) < 1\) where \(\rho (T)\) is the spectral radius of \(T\). Do not assume that the matrix \(T\) is diagonalizable.
2. Suppose \(A \in \mathbb {R}^{m \times m}\) is nonsingular, that \(b \in \mathbb {R}^m\), and that \(Ax = b\). Suppose that \(x = T x + c\) is a fixed point problem equivalent to this linear system. What are the implications of part (a) for the convergence of the fixed-point iteration \(x^{(k+1)} = T x^{(k)} + c\) to the solution \(x\) of the linear system?

3. Suppose \(A\) is a symmetric, weakly diagonally dominant, and irreducible matrix. Define the Jacobi iterative method for solving \(Ax = b\), and show that this method converges to the solution of the linear system starting with any initial vector \(x^{(0)}\). (Hint: You might find it helpful to use the fact that a matrix which is both weakly diagonally dominant and irreducible is nonsingular.)

   Recall that: An \(m \times m\) matrix \(A\) is irreducible iff for all \(i,j \in \{1,2,\ldots ,m\}\), \(i \ne j\), either \(a_{ij} \ne 0\) or there are \(i_1,i_2,\ldots ,i_s\), each between 1 and \(m\), such that \(a_{i,i_1}a_{i_1,i_2}a_{i_2,i_3}\cdots a_{i_s,j} \ne 0\). A symmetric \(m \times m\) matrix \(A\) is weakly diagonally dominant if \(|a_{ii}| \ge \sum _{j\ne i}|a_{ij}|\) for all \(i\), and \(|a_{ii}| > \sum _{j\ne i}|a_{ij}|\) for at least one \(i\).

(Eigenvalues and Eigenvectors).

1. State the Rayleigh Quotient Iteration Algorithm to find eigenvalues/eigenvectors for general real symmetric matrix \(A \in \mathbb {R}^{m \times m}\).
2. Prove that the spectrum (the set of all eigenvalues) of any matrix \(A \in \mathbb {C}^{m \times m}\) is contained in the union of the following \(m\) disks, \(D_i\), in the complex plane: \[ D_i = \left \{z \in \mathbb {C} : |z - a_{ii}| \le \sum _{\substack {j=1\\ j\ne i}}^m |a_{ij}|\right \},\qquad 1 \le i \le m. \]

Solution of a nonlinear fixed point problem

Consider the fixed-point problem \(x = g(x)\) for a continuously differentiable real-valued function \(g\) and assume that it has a solution \(\alpha \) for which \(|g'(\alpha )| < 1\). State and prove a convergence theorem for fixed point iteration \(x^{(k+1)} = g(x^{(k)})\) for this problem. Note: Do not assume more about the function \(g\) than is stated in the problem.

Fixed-point iteration for linear systems.

1. For \(T \in \mathbb {R}^{m \times m}\) and any matrix norm, show that \(\|T^k\| \to 0\) as \(k \to \infty \) if and only if \(\rho (T) < 1\) where \(\rho (T)\) is the spectral radius of \(T\). Do not assume that the matrix \(T\) is diagonalizable.
2. Suppose \(A \in \mathbb {R}^{m \times m}\) is nonsingular, that \(b \in \mathbb {R}^m\), and that \(Ax = b\). Suppose that \(x = T x + c\) is a fixed point problem equivalent to this linear system. What are the implications of part (a) for the convergence of the fixed-point iteration \(x^{(k+1)} = T x^{(k)} + c\) to the solution \(x\) of the linear system?

3. Suppose \(A\) is a symmetric, weakly diagonally dominant, and irreducible matrix, define the Jacobi iterative method for solving \(Ax = b\), and show that this method converges to the solution of the linear system starting with any initial vector \(x^{(0)}\). (Hint: You might find it helpful to use the fact that a matrix which is both weakly diagonally dominant and irreducible is nonsingular.)

   Recall that: An \(m \times m\) matrix \(A\) is irreducible iff for all \(i,j \in \{1,2,\ldots ,m\}\), \(i \ne j\), either \(a_{ij} \ne 0\) or there are \(i_1,i_2,\ldots ,i_s\), each between 1 and \(m\), such that \(a_{i,i_1}a_{i_1,i_2}a_{i_2,i_3}\cdots a_{i_s,j} \ne 0\). A symmetric \(m \times m\) matrix \(A\) is weakly diagonally dominant if \(|a_{ii}| \ge \sum _{j\ne i}|a_{ij}|\) for all \(i\), and \(|a_{ii}| > \sum _{j\ne i}|a_{ij}|\) for at least one \(i\).

Numerical Algorithm to Find Eigenvalues/Eigenvectors

State the Rayleigh Quotient Iteration Algorithm to find eigenvalues/eigenvectors for general real symmetric matrix \(A\in \mathbb {R}^{m\times m}\).

Let \((X,d)\) be a complete metric space and \(f\) a contraction on \(X\) with contraction constant \(\alpha <1\). Let \(x_f\) be the unique fixed point of \(f\). Fix \(x_0\in X\) and consider the sequence of points defined by \(x_n=f(x_{n-1})\) for \(n\in \mathbb {N}\).

1. Prove that \[ d(x_n,x_f)\le \frac {\alpha ^n}{1-\alpha }d(x_0,x_1). \] Hint: consider \(d(x_m,x_n)\) for \(m>n\).
2. Let \(S=[1,\infty )\) and \(f:S\to S\) be defined by \(f(x)=\frac {1}{2}(x+2/x)\). Prove that \(f\) is a contraction mapping on \(S\) and compute a contraction constant. Determine all fixed points of \(f\) on \(S\). Using part (a), explain why the sequence \((x_n)\) might be useful.

Consider the transformation on the extended complex plane \(\overline {\mathbb {C}}\) \[ f(z)=w=z+\frac {1}{z}. \]

1. Find all possible fixed points.
2. Show that the image of the points in the upper half \(z\)-plane that are exterior to the circle \(\lvert z\rvert =1\) corresponds to the entire upper half \(w\)-plane.
3. Find the image of the unit circle.
4. Show that \(f(z)\) is a two-to-one function.

Let \(f\) be a real-valued and twice continuously differentiable on an interval \([a,b]\). Let \(\hat {x}\) be a simple zero of \(f\), i.e. \(f'(\hat {x})\ne 0\). Use the Banach Fixed Point Theorem to show that Newton’s method, defined by \[ x_{n+1}=x_n-\frac {f(x_n)}{f'(x_n)} \] converges to \(\hat {x}\) for any \(x_0\) sufficiently close to \(\hat {x}\).

Numerical Algorithm to Find Eigenvectors/Eigenvalues

State the Inverse Iteration Algorithm to find eigenvectors/eigenvalues for general real symmetric matrix \(A\in \mathbb {R}^{m\times m}\).

Elliptic Equations Consider the standard five-point difference approximation (centered difference for both the gradient and divergence operators) for the variable coefficient Poisson’s equation \[ -\nabla \cdot (a\nabla u)=f \] with Dirichlet boundary conditions, in a two-dimensional rectangular region. We assume that \(a(\mathbf {x})\ge \delta >0\). The approximate solution \(\{u_{i,j}\}\) satisfies a linear system \(Au=b\).

(a) State and prove the maximum principle for the numerical solution \(u_{i,j}\).

(b) Use the maximum principle to show that the coefficient matrix \(A\) is nonsingular.

(c) Derive the matrix \(A\) in the one-dimensional case and show that it is symmetric and positive definite.

(d) With this linear system, do we get convergence with Jacobi iterations? What about Gauss-Seidel iterations? Give reasons for your answers.

Iterative Methods Consider the fixed-point problem \(x=Tx+c\), where \(T\) is a real \(N\times N\) matrix and \(x\) and \(c\) are real \(N\)-vectors.

a) Show that the fixed point iteration \[ x^{(k+1)}=Tx^{(k)}+c \] converges for any choice of initial vector \(x^{(0)}\) if and only if the spectral radius of \(T\), \(\rho (T)\), satisfies \(\rho (T)<1\).

b) Consider the linear system \(Ax=b\) where \(A\) is a strictly diagonally dominant matrix, that is, \(a_{ii}>\sum _{j\ne i}\lvert a_{ij}\rvert \) for all \(i\), and strict inequality holds for at least one value of \(i\). Show that the Jacobi iterative scheme converges for this problem.

Iterative Methods for Linear Systems Consider the fixed-point iteration \[ u^{(k+1)}=Tu^{(k)}+c \] for finding a solution of the problem \[ u=Tu+c \] where \(T\) is an \(m\times m\) real matrix and \(c\) is a real \(m\)-vector.

a) Show that the fixed point iteration will converge for an arbitrary initial guess \(u^{(0)}\) if and only if the spectral radius of \(T\), \(\rho (T)\), is less than 1.

b) Consider the boundary value problem \[ -u''(x)=f(x),\qquad \text {for }0\le x\le 1 \] with \(u(0)=u(1)=0\), and the following discretization of it: \[ -U_{j-1}+2U_j-U_{j+1}=F_j \] for \(j=1,2,\ldots ,N-1\) where \(Nh=1\) and \(F_j=h^2f(jh)\).

Analyze the convergence properties of the Jacobi iterative method for this problem. In particular, express the speed of convergence as a function of the discretization stepsize \(h\). How does the number of iterations required to reduce the initial error by a factor of \(\delta \) depend on \(h\)? In practice, would you use this method to solve the given problem? If so, explain why this is a good idea? If not, how would you solve it in practice?

Suppose that \(T\) is a transformation of a complete metric space \(X\), and \(T^n\) (for a certain positive integer \(n\)) is a contraction with fixed point \(a\). Show that

1. \(a\) is a fixed point of \(T\);
2. \(T\) has only one fixed point;
3. the sequence of successive iterations \(u_0\), \(u_1=Tu_0\), \(u_2=Tu_1,\ldots \) tends to \(a\) for any initial element \(u_0\in X\).

Iterative Methods for Linear Systems a) Consider the fixed-point iteration \[ u^{(k+1)}=Tu^{(k)}+c \] for finding a solution of the problem \[ u=Tu+c \] where \(T\) is an \(m\times m\) real matrix and \(c\) is a real \(m\)-vector. Show that the fixed point iteration will converge for an arbitrary initial guess \(u^{(0)}\) if and only if the spectral radius of \(T\), \(\rho (T)\), is less than 1.

b) Consider the boundary value problem \[ -u''(x)=f(x),\qquad \text {for }0\le x\le 1 \] with \(u(0)=u(1)=0\), and the following discretization of it: \[ -U_{j-1}+2U_j-U_{j+1}=F_j \] for \(j=1,2,\ldots ,N-1\) where \(Nh=1\) and \(F_j=h^2f(jh)\).

Analyze the convergence properties of the Jacobi iterative method for this problem. In particular, express the speed of convergence as a function of the discretization stepsize \(h\). How does the number of iterations required to reduce the initial error by a factor of \(\delta \) depend on \(h\)? In practice, would you use this method to solve the given problem? If so, explain why this is a good idea? If not, how would you solve it in practice?

Broyden’s Method Consider the nonlinear system: \[ F(x)=0\qquad \text {where }F:\mathbb {R}^n\to \mathbb {R}^n \] and the iteration \[ x^{(k+1)}=x^{(k)}-(A^{(k)})^{-1}F(x^{(k)}) \] where \(x^{(0)}\in \mathbb {R}^n\) is given.

Newton’s Method is defined by the choice \(A^{(k)}=F'(x)\) where \(F'(x)\) is the Jacobean matrix of \(F\). An alternative choice for \(A^{(k+1)}\) is made in Broyden’s Method and is motivated as follows:

Let \(A^{(0)}\) be a given and suitably chosen matrix. The scalar Secant Method suggests imposing on \(A^{(k+1)}\) the condition \[ A^{(k+1)}(x^{(k+1)}-x^{(k)})=F(x^{(k+1)})-F(x^{(k)}). \] This however does not uniquely determine \(A^{k+1}\) as it does not give any information on how \(A^{k+1}\) acts on vectors perpendicular to \((x^{(k+1)}-x^{(k)})\). Thus require also that: \[ A^{(k+1)}t=A^{(k)}t \qquad \text {for all }t\in \mathbb {R}^n\text { such that } t^T(x^{(k+1)}-x^{(k)})=0 \] Use these conditions to derive an explicit expression for \(A^{(k+1)}\) in terms of \(A^{(k)}\), \(x^{(k)}\), and \(x^{(k+1)}\).