Numerical Analysis Lecture (V): Nonlinear Systems of Equations

... views ... visitors ... total

中文版

It is best to read Numerical Analysis Lecture (IV): Solving Linear Systems and Matrix Computations Part II first. This article introduces nonlinear systems of equations, the local convergence of Newton’s method, and globalization strategies.

---

5.1 Introduction

This chapter discusses methods for solving nonlinear systems of equations.

Nonlinear system of equations. We seek $x\in D$ such that

\[F(x)=0\]

where a mapping

\[F= \begin{pmatrix} F_1\\ \vdots\\ F_n \end{pmatrix} :D\to\mathbb{R}^n, \qquad D\subseteq\mathbb{R}^n\]

is given. Here, $D$ is a nonempty closed set.

Many practically relevant problems, especially in engineering, are nonlinear and require the solution of nonlinear systems. For example, large nonlinear systems arise in circuit simulation and in the discretization of nonlinear partial differential equations, including weather and climate models, structural mechanics, and forming processes in manufacturing.

The solution set of a linear system can only be a singleton, empty, or an entire affine subspace. Nonlinear equations, by contrast, may have several isolated solutions or even infinitely many isolated solutions.

Example 5.1.1

1. $n=1$, $D=\mathbb{R}$, and $F(x)=x^2-a$ with $a>0$. There are two real solutions:

\[x=\pm\sqrt a.\]

1. $n=1$, $D=\mathbb{R}$, and $F(x)=x^2+a$ with $a>0$. There is no real solution.

2. $n=1$, $D=\mathbb{R}$, and $F(x)=x\sin(x)$. There are infinitely many solutions:

\[x=k\pi, \qquad k\in\mathbb{Z}.\]

1. Consider the intersection of the unit circle with the line $G:x_2=ax_1+b$, where $a,b\in\mathbb{R}$. Let $n=2$, $D=\mathbb{R}^2$, and

\[F(x)= \begin{pmatrix} x_1^2+x_2^2-1\\ x_2-ax_1-b \end{pmatrix}.\]

The number of solutions depends on $a$ and $b$: there may be two, one, or no real solutions.

In many applications, the function $F$ is continuously differentiable, meaning that its partial derivatives

\[\frac{\partial F_i}{\partial x_j}, \qquad 1\le i,j\le n\]

exist and are continuous. In this case, the first-order Taylor expansion gives

\[F(x+s)=F(x)+F'(x)s+R(x;s),\]

where the Jacobian matrix is

\[F'(x)= \begin{pmatrix} \frac{\partial F_1}{\partial x_1}(x)&\cdots&\frac{\partial F_1}{\partial x_n}(x)\\ \vdots&\ddots&\vdots\\ \frac{\partial F_n}{\partial x_1}(x)&\cdots&\frac{\partial F_n}{\partial x_n}(x) \end{pmatrix},\]

and $R(x;s)$ is the remainder term satisfying

\[\lim_{s\to 0}\frac{\|R(x;s)\|}{\|s\|}=0, \qquad \text{abbreviated as } R(x;s)=o(\|s\|).\]

This provides the basis for constructing fast solution methods.

5.2 Newton’s Method

Newton’s method is one of the most important methods for solving nonlinear systems because it usually converges very rapidly near a solution. For ease of exposition, we assume below that $D=\mathbb{R}^n$.

Consider solving the system

\[F(x)=0 \tag{5.1}\]

with Newton’s method, where $F:\mathbb{R}^n\to\mathbb{R}^n$ is continuously differentiable.

5.2.1 Derivation

Intuition in one dimension

First let $n=1$. Then $F(x):\mathbb{R}\to\mathbb{R}$ is a real-valued function. Let $x^{(k)}$ be an approximation to a solution $\overline x$ of (5.1). The idea of Newton’s method is to approximate the graph $(x,F(x))$ by its tangent line at $x^{(k)}$, and to use the intersection of that tangent line with the $x$-axis as the next iterate $x^{(k+1)}$.

The tangent line is

\[y=F(x^{(k)})+F'(x^{(k)})(x-x^{(k)}),\]

and $x^{(k+1)}$ is the solution of

\[F(x^{(k)})+F'(x^{(k)})(x-x^{(k)})=0.\]

If $F’(x^{(k)})\ne 0$, then

\[x^{(k+1)} =x^{(k)}-F'(x^{(k)})^{-1}F(x^{(k)}).\]

Thus,

\[x^{(k+1)}=x^{(k)}+s^{(k)},\]

where $s^{(k)}$ is obtained by solving

\[F'(x^{(k)})s^{(k)}=-F(x^{(k)}).\]

Example 5.2.1. For $F(x)=x^2-a$ with $a>0$,

\[x^{(k+1)} =x^{(k)}-\frac1{2x^{(k)}}\left((x^{(k)})^2-a\right) =\frac12\left(x^{(k)}+\frac{a}{x^{(k)}}\right).\]

General case

In the general case, let $x^{(k)}\in\mathbb{R}^n$ be the current iterate. Then $\overline x$ is a solution of (5.1) if and only if $\overline x=x^{(k)}+s$ for some $s$ satisfying

\[F(x^{(k)}+s)=0. \tag{5.2}\]

Newton’s method approximates $F(x^{(k)}+s)$ by its first-order Taylor expansion:

\[F(x^{(k)}+s) =F(x^{(k)})+F'(x^{(k)})s+o(\|s\|),\]

where $F’(x^{(k)})$ is the Jacobian matrix of $F$ at $x^{(k)}$; when $s$ is small, the remainder is small as well.

Therefore, at the $k$th Newton iteration, (5.2) is replaced by the linearized equation

\[F(x^{(k)})+F'(x^{(k)})s=0.\]

This gives the following algorithm.

Algorithm 5.2.2: Local Newton method for systems of equations

Choose an initial point $x^{(0)}\in\mathbb{R}^n$.

For $k=0,1,\ldots$:

1. If $F(x^{(k)})=0$, stop and return $x^{(k)}$.
2. Solve the Newton equation for the Newton step $s^{(k)}\in\mathbb{R}^n$:

\[F'(x^{(k)})s^{(k)}=-F(x^{(k)}).\]

1. Set

\[x^{(k+1)}=x^{(k)}+s^{(k)}.\]

Figure 5.1: Geometric intuition for local Newton's method

The illustration uses $F(x)=x^2-2$. At each iterate, draw the tangent and take its intersection with the $x$-axis as the next iterate; when the initial point is sufficiently close to the root, the iterates quickly approach $\overline x=\sqrt{2}$.

5.2.2 Local Superlinear and Quadratic Convergence of Newton’s Method

Under suitable conditions, Newton’s method can be shown to converge locally at a very high rate.

For notational simplicity, we use the Euclidean norm $|\cdot|_2$ and its induced matrix norm throughout. Other norms could of course be used as well.

The following theorem gives the local superlinear and quadratic convergence of Newton’s method.

Theorem 5.2.3 (Fast local convergence of Newton’s method). Let $F:\mathbb{R}^n\to\mathbb{R}^n$ be continuously differentiable, and let $\overline x\in\mathbb{R}^n$ satisfy

\[F(\overline x)=0\]

with $F’(\overline x)$ nonsingular. Then there exists $\delta>0$ such that:

i) Within the ball

\[B_\delta(\overline x) := \{x\in\mathbb{R}^n:\|x-\overline x\|_2<\delta\},\]

$\overline x$ is the unique zero of $F$.

ii) For every $x^{(0)}\in B_\delta(\overline x)$, Algorithm 5.2.2 either reaches $x^{(k)}=\overline x$ at some step and terminates, or generates a sequence satisfying

\[(x^{(k)})\subset B_\delta(\overline x),\]

which converges superlinearly to $\overline x$, that is,

\[\lim_{k\to\infty}x^{(k)}=\overline x,\]

and

\[\|x^{(k+1)}-\overline x\|_2 \le \nu_k\|x^{(k)}-\overline x\|_2,\]

where $\nu_k\downarrow 0$, meaning that the convergence factor tends to zero.

iii) If $F’$ satisfies a Lipschitz condition on $B_\delta(\overline x)$, with Lipschitz constant $L$, namely

\[\|F'(x)-F'(y)\|_2 \le L\|x-y\|_2 \qquad \forall x,y\in B_\delta(\overline x),\]

then $(x^{(k)})$ converges to $\overline x$ quadratically, that is,

\[\lim_{k\to\infty}x^{(k)}=\overline x,\]

and

\[\|x^{(k+1)}-\overline x\|_2 \le C\|x^{(k)}-\overline x\|_2^2,\]

where, for sufficiently small $\delta>0$, one may choose

\[C=L\cdot\|F'(\overline x)^{-1}\|_2.\]

Note: If $F$ has continuous second derivatives on the closed ball $B_\delta(\overline x)$, then $F’$ automatically satisfies a Lipschitz condition.

However, Algorithm 5.2.2 usually converges only when the initial point is sufficiently close to a solution $\overline x$.

Example 5.2.4. Consider

\[F(x)=\frac{x}{\sqrt{1+x^2}}.\]

The function $F$ has exactly one zero, $\overline x=0$, is continuously differentiable, and satisfies $F’(x)>0$. Nevertheless, when $\lvert x^{(0)}\rvert>1$, Newton’s method does not converge from any such initial point (see the exercises).

To make Newton’s method converge from every initial point, it must be suitably globalized.

5.2.3 Globalization of Newton’s Method

This section presents one improvement to Newton’s method. For a broad class of functions $F$, the improvement guarantees global convergence from any initial point.

The method is based on the following observation: every solution $\overline x$ of (5.1) is a global minimizer of

\[\min_{x\in\mathbb{R}^n}\|F(x)\|_2^2.\]

The strategy is as follows:

• Use the Newton step $s^{(k)}$, but scale it by a step size $\sigma_k\in(0,1]$, setting

\[x^{(k+1)}=x^{(k)}+\sigma_k s^{(k)}.\]

• Choose $\sigma_k$ so that

\[\|F(x^{(k+1)})\|_2<\|F(x^{(k)})\|_2 \tag{5.3}\]

holds, with a sufficiently large decrease.

For the function

\[\phi(\sigma) := \|F(x^{(k)}+\sigma s^{(k)})\|_2^2,\]

Figure 5.2: Armijo step-size selection in globalized Newton's method

The globalization strategy backtracks over the discrete candidate step sizes $1,1/2,1/4,\ldots$ and chooses the largest one satisfying the Armijo condition. In the figure, the full step $\sigma=1$ increases the squared residual, so $\sigma=1/2$ is used instead.

Expanding at $\sigma=0$ gives

\[\phi(\sigma) =\phi(0)+\phi'(0)\sigma+o(\sigma) = \|F(x^{(k)})\|_2^2 +2\sigma F(x^{(k)})^T F'(x^{(k)})s^{(k)} +o(\sigma).\]

Substituting the Newton equation

\[F'(x^{(k)})s^{(k)}=-F(x^{(k)})\]

into this expression yields

\[\|F(x^{(k)}+\sigma s^{(k)})\|_2^2 = \|F(x^{(k)})\|_2^2 -2\sigma\|F(x^{(k)})\|_2^2 +o(\sigma).\]

Fix $\delta\in(0,1)$. If $F(x^{(k)})\ne 0$ and $\sigma$ is sufficiently small, then

\[\|F(x^{(k)}+\sigma s^{(k)})\|_2^2 \le \|F(x^{(k)})\|_2^2 -2\delta\sigma\|F(x^{(k)})\|_2^2.\]

This motivates the following Armijo step-size rule.

Armijo step-size selection. Choose

\[\delta\in(0,\tfrac12)\]

(for example, $\delta=10^{-3}$ usually works well). From the set

\[\sigma_k\in\left\{1,\frac12,\frac14,\ldots\right\}\]

select the largest step size satisfying

\[\|F(x^{(k)}+\sigma_k s^{(k)})\|_2^2 \le \|F(x^{(k)})\|_2^2 -2\delta\sigma_k\|F(x^{(k)})\|_2^2. \tag{5.4}\]

This gives the following algorithm.

Algorithm 5.2.5: Globalized Newton method for systems of equations

Choose an initial point $x^{(0)}\in\mathbb{R}^n$.

For $k=0,1,\ldots$:

1. If $F(x^{(k)})=0$, stop and return $x^{(k)}$.
2. Solve the Newton equation for the Newton step $s^{(k)}\in\mathbb{R}^n$:

\[F'(x^{(k)})s^{(k)}=-F(x^{(k)}).\]

1. Determine $\sigma_k$ using the Armijo rule (5.4).
2. Set

\[x^{(k+1)}=x^{(k)}+\sigma_k s^{(k)}.\]

The following theorem guarantees the corresponding convergence.

Theorem 5.2.6. Let $F:\mathbb{R}^n\to\mathbb{R}^n$ be continuously differentiable, and choose any initial point $x^{(0)}\in\mathbb{R}^n$. Define

\[f(x)=\|F(x)\|_2^2,\]

and the level set

\[N_f(x^{(0)}) := \{\,y:f(y)\le f(x^{(0)})\,\}.\]

If the Jacobian matrix $F’(x)$ is invertible at every point $x$ in this level set, and $N_f(x^{(0)})$ is compact (equivalently, bounded and closed in $\mathbb{R}^n$), then starting from $x^{(0)}$ and running Algorithm 5.2.5 either terminates in finitely many steps or generates a sequence

\[(x^{(k)})\subset N_f(x^{(0)}),\]

such that:

i) $(x^{(k)})$ converges to a solution $\overline x$ of (5.1).

ii) There exists $l\ge 0$ such that $\sigma_k=1$ for every $k\ge l$. Thus, the algorithm eventually becomes the local method that takes a full Newton step at every iteration, and converges to $\overline x$ at a superlinear or quadratic rate.

---

Return to Numerical Analysis Lecture (IV): Solving Linear Systems and Matrix Computations Part II.

Source, Copyright, and Usage Notes

This article is organized from Chapter 4 of the locally saved TU Darmstadt 2016 Mathematik 4 ET/3Inf lecture file Skript-Mathe4ET-3Inf-2016-Kap4-5.pdf, with reference to the Chinese translation draft Skript-Mathe4ET-3Inf-2016-Kap4.zh.md in the same local directory. It is published for personal study, translation, and knowledge organization. The English wording, supplementary explanations, and remade figures in this article do not represent the original authors or an official position.

My organization, English wording, supplementary explanations, and remade figures in this article may be used for non-commercial study, discussion, and citation, provided that the author and original material source are credited. Because parts of this article are based on translation and organization of course lecture notes, the original lecture notes and any materials they may contain should still be governed by their original authors, course pages, and relevant authorization statements. For commercial use, systematic republication, publication, or large-scale adaptation, please confirm the authorization status of the original materials first.

If there are omissions or errors in translation, formulas, terminology, or interpretation, or if a relevant rights holder considers the use of any content inappropriate, please contact me and I will handle or remove it promptly.