Question

This exercise is concerned with proofs. Let \(\mathbf{f}(\mathbf{x})\) be Lipschitz continuously differentiable in an open convex set \(\mathcal{D} \subset \mathcal{R}^{n}\), i.e., there is a constant \(\gamma \geq 0\) such that $$ \|J(\mathbf{x})-J(\mathbf{y})\| \leq \gamma\|\mathbf{x}-\mathbf{y}\| \quad \forall \mathbf{x}, \mathbf{y} \in \mathcal{D} $$ where \(J\) is the \(n \times n\) Jacobian matrix of \(\mathbf{f}\). It is possible to show that if \(\mathbf{x}\) and \(\mathbf{x}+\mathbf{p}\) are in \(\mathcal{D}\), then $$ \mathbf{f}(\mathbf{x}+\mathbf{p})=\mathbf{f}(\mathbf{x})+\int_{0}^{1} J(\mathbf{x}+\tau \mathbf{p}) \mathbf{p} d \tau $$ (a) Assuming the above as given, show that $$ \|\mathbf{f}(\mathbf{x}+\mathbf{p})-\mathbf{f}(\mathbf{x})-J(\mathbf{x}) \mathbf{p}\| \leq \frac{\gamma}{2}\|\mathbf{p}\|^{2} $$ (b) Suppose further that there is a root \(\mathbf{x}^{*} \in \mathcal{D}\) satisfying $$ \mathbf{f}\left(\mathbf{x}^{*}\right)=\mathbf{0}, \quad J\left(\mathbf{x}^{*}\right) \text { nonsingular. } $$ Show that for \(\mathbf{x}_{0}\) sufficiently close to \(\mathbf{x}^{*}\), Newton's method converges quadratically.

Short answer

Question: Given a Lipschitz continuously differentiable function and Newton's method, prove that 1) the error term $\|\mathbf{f}(\mathbf{x}+\mathbf{p})-\mathbf{f}(\mathbf{x})-J(\mathbf{x})\mathbf{p}\|$ is less than or equal to $\frac{\gamma}{2}\|\mathbf{p}\|^2$ and 2) Newton's method converges quadratically if the initial guess is sufficiently close to the root. Solution: 1) We proved that $\|\mathbf{f}(\mathbf{x}+\mathbf{p})-\mathbf{f}(\mathbf{x})-J(\mathbf{x})\mathbf{p}\| \leq \frac{\gamma}{2}\|\mathbf{p}\|^2$ by rearranging the given equation, applying the triangle inequality, and using the Lipschitz condition. 2) We showed that the Newton's method converges quadratically for initial guesses close to the root by analyzing the Newton iteration and manipulating the error term. We used the result from part (a) and properties of nonsingular matrices to show that the error behaves quadratically in subsequent iterations, proving the desired convergence.

Step-by-step solution

Part (a) Proof

We are given $\mathbf{f}(\mathbf{x}+\mathbf{p})=\mathbf{f}(\mathbf{x})+\int_{0}^{1} J(\mathbf{x}+\tau \mathbf{p}) \mathbf{p} d \tau$. We want to find the error term, $$ \mathcal{E} \triangleq \|\mathbf{f}(\mathbf{x}+\mathbf{p})-\mathbf{f}(\mathbf{x})-J(\mathbf{x}) \mathbf{p}\|. $$ To find \(\mathcal{E}\), rearrange the given equation as: $$ \mathcal{E} = \left\|\int_{0}^{1} \left[ J(\mathbf{x}+\tau \mathbf{p}) - J(\mathbf{x}) \right] \mathbf{p} d \tau \right\|. $$ Now, apply the triangle inequality: $$ \mathcal{E} \leq \int_{0}^{1} \left\| \left[ J(\mathbf{x}+\tau \mathbf{p}) - J(\mathbf{x}) \right] \mathbf{p} \right\| d \tau. $$ By Lipschitz condition, we have \(\|J(\mathbf{x}+\tau\mathbf{p}) - J(\mathbf{x})\| \leq \gamma\|\tau\mathbf{p}\|\). So, $$ \mathcal{E} \leq \int_{0}^{1} \gamma\|\tau\mathbf{p}\| \|\mathbf{p}\| d \tau = \|\mathbf{p}\| \gamma \int_{0}^{1} \tau\|\mathbf{p}\| d \tau. $$ Evaluating the integral, we get: $$ \mathcal{E} \leq \|\mathbf{p}\| \gamma \left[ \frac{\tau^{2}\|\mathbf{p}\|}{2} \right]_{0}^{1} = \frac{\gamma}{2}\|\mathbf{p}\|^{2}. $$ Hence, we have proved $$ \|\mathbf{f}(\mathbf{x}+\mathbf{p})-\mathbf{f}(\mathbf{x})-J(\mathbf{x})\mathbf{p}\| \leq \frac{\gamma}{2}\|\mathbf{p}\|^{2}. $$

Part (b) Proof

To show that Newton's method converges quadratically, we first calculate the Newton iteration, given by: $$ \mathbf{x}_{k+1} = \mathbf{x}_{k} - J^{-1}(\mathbf{x}_{k})\mathbf{f}(\mathbf{x}_{k}). $$ Next, let \(\mathbf{e}_{k} = \mathbf{x}_{k} - \mathbf{x}^{*}\). Subtracting \(\mathbf{x}^{*}\) from both sides, we have: $$ \mathbf{e}_{k+1} = \mathbf{e}_{k} - J^{-1}(\mathbf{x}_{k})\mathbf{f}(\mathbf{x}_{k}). $$ Using the result from part (a): $$ \|\mathbf{f}(\mathbf{x}_k)-J(\mathbf{x}_k)(\mathbf{x}_k - \mathbf{x}^*)\| \leq \frac{\gamma}{2}\|\mathbf{x}_k - \mathbf{x}^*\|^2 = \frac{\gamma}{2}\|\mathbf{e}_k\|^2. $$ This implies that $$ \|J(\mathbf{x}_k)\mathbf{e}_k-\mathbf{f}(\mathbf{x}_k)\|\leq \frac{\gamma}{2}\|\mathbf{e}_k\|^2. $$ Now, rearrange to match the iteration formula: $$ \|J(\mathbf{x}_k)\mathbf{e}_k - J(\mathbf{x}_k)(\mathbf{x}^{*}-\mathbf{x}_{k+1})\| \leq \frac{\gamma}{2}\|\mathbf{e}_k\|^2. $$ Since \(J(\mathbf{x}^{*})\) is nonsingular, we can state that \(\|J(\mathbf{x}_k)(\mathbf{e}_k - \mathbf{e}_{k+1})\|\leq \frac{\gamma}{2}\|\mathbf{e}_k\|^2\). Divide both sides by \(\|J(\mathbf{x}_k)\|\) (which is nonzero, due to nonsingularity) to obtain: $$ \|\mathbf{e}_k - \mathbf{e}_{k+1}\|\leq \frac{\gamma}{2}\frac{\|\mathbf{e}_k\|^2}{\|J(\mathbf{x}_k)\|}. $$ For \(\mathbf{x}_0\) close enough to \(\mathbf{x}^*\), we have \(\|J(\mathbf{x}_0)\|\approx\|J(\mathbf{x}^*)\|\). Hence, we can write: $$ \|\mathbf{e}_k - \mathbf{e}_{k+1}\|\leq \frac{\gamma}{2}\frac{\|\mathbf{e}_k\|^2}{\|J(\mathbf{x}^*)\|}. $$ The right-hand side of this inequality is a constant (depending on \(\mathbf{x}_0\)) times \(\|\mathbf{e}_k\|^2\), which establishes that the error of each iteration behaves quadratically as desired, i.e., Newton's method converges quadratically for \(\mathbf{x}_{0}\) sufficiently close to \(\mathbf{x}^{*}\).

Key concepts

Lipschitz Continuity

Lipschitz continuity is a property of functions that serves as a mathematical condition for smoothness. A function is said to be Lipschitz continuous on a domain if there exists a constant \( \gamma \geq 0 \) such that for all pairs of points \( \mathbf{x} \) and \( \mathbf{y} \) in the domain, the change in function values is linearly bounded by the distance between these points. Formally, for a Lipschitz continuous function \( f \), the inequality \( |f(x) - f(y)| \leq \gamma |x - y| \) holds true.

In the context of the given exercise, this concept is applied to the Jacobian matrix \( J(\mathbf{x}) \) of a vector-valued function \( \mathbf{f}(\mathbf{x}) \). The Jacobian's entries are the first partial derivatives of \( \mathbf{f} \), and the Lipschitz condition ensures that these derivatives do not change too rapidly within the domain \( \mathcal{D} \).

• Constant \( \gamma \): This is the Lipschitz constant that provides a bound on how much the function can stretch.
• Application to Jacobian: This applies to the difference in Jacobians at different points, ensuring controlled behavior.

Understanding this property is crucial because it impacts the stability and convergence behavior of iterative methods like Newton’s Method.

Quadratic Convergence

Quadratic convergence is a term used to describe how rapidly an iterative method approaches the solution. Specifically, a method converges quadratically if, near the solution, the error decreases approximately as the square of the previous error, ensuring that convergence becomes faster as iterates approach the solution.

In Newton's Method, this rapid convergence occurs when we start with an initial guess \( \mathbf{x}_0 \) sufficiently close to the true solution \( \mathbf{x}^* \), where the Jacobian is nonsingular. The nonsingularity of \( J(\mathbf{x}^*) \) guarantees that division in Newton's update formula is valid, ensuring the rapid diminishing of the error.

• Rapid Error Reduction: Each iteration greatly reduces the error if the method is quadratically convergent.
• Sufficiently Close Start: The starting point must be close to ensure the quadratic behavior.

The beauty of quadratic convergence lies in its efficiency. Given the right conditions, it means fewer iterations are needed to achieve a high precision, making Newton's Method powerful for finding roots of differentiable functions.

Jacobian Matrix

The Jacobian matrix is a crucial concept in multivariable calculus, representing the gradient of a vector-valued function. For a function \( \mathbf{f} = [f_1, f_2, ..., f_n] \), the Jacobian matrix \( J(\mathbf{x}) \) is an \( n \times n \) matrix where each element \( J_{ij} \) is the partial derivative \( \frac{\partial f_i}{\partial x_j} \). This matrix encapsulates how changes in input variables affect the changes in the function outputs.

In optimization and root-finding methods like Newton's Method, the Jacobian plays a pivotal role as it is used to linearly approximate the function around a point. This approximation is fundamental for determining the direction and magnitude of the steps taken towards the solution.

• Linear Approximation: The Jacobian serves as a first-order approximation of the vector function.
• Role in Iterative Methods: Newton's Method utilizes the inverse of the Jacobian in its update steps to refine guesses of the roots.

The properties of the Jacobian, such as its nonsingularity, directly impact the convergence and stability of these numerical methods, making it essential to understand its behavior across different points in \( \mathcal{D} \).