Chapter2-Solving nonlinear equations

Continue our journey in Chapter1-Fundanentals, the notes are based on the textbook¹

The Bisection Method

Given initial interval $[a,b]$ such that $f(a)f(b)<0$

def bisection(f, a, b, tol=1e-6, maxiter=100):
    for i in range(maxiter):
        c = (a + b) / 2
        if f(c) == 0 or abs(b - a) < tol:
            return c
        if f(a) * f(c) < 0:
            b = c
        else:
            a = c
    return c

the approximate error is ${\epsilon }_{error}=\frac{b-a}{2^{n+1}}$ ($n=0$ is the initial error)

---

Fixed-point Iteration

• fixed point: the real number $r$ is a fixed point of the function $g$ if $g(r)=r$

def fixed_point_iteration(f, x0, tol=1e-6, maxiter=100):
    x = x0
    for i in range(maxiter):
        x1 = f(x)
        if abs(x1 - x) < tol:
            return x1
        x = x1
    return x

The FPI function can be different.

For equation $x^3+x-1=0$, there exists different FPI functions, along with different convergence speed.

different FPI functions, different convergence speed.

• Linear convergence: Let ${\epsilon }_i=\frac{{\epsilon }_{i-1}}{2}$ denote the error at step $i$ of an iterative method. If

$$\underset{i\to \infty }{\lim }\frac{{\epsilon }_{i+1}}{{\epsilon }_i}=S<1$$

the method is said to obey linear convergence with rate S

Assume that $g$ is continuously differentiable, that $g(r)=r$ , and that $S=|g^{\prime }(r)|<1$ . Then Fixed-Point Iteration converges linearly with rate S to the fixed point $r$ for initial guesses sufficiently close to $r$ .

Convergent Types

• Locally convergent: An iterative method is called locally convergent to $r$ if the method converges to r for initial guesses sufficiently close to $r$

• Globally convergent: For any $x\in I$, the method converges to $r$ for any initial guesses of $x$.

The Bisection Method is guaranteed to converge linearly. Fixed-Point Iteration is only locally convergent, and when it converges it is linearly convergent. Both methods require one function evaluation per step. The bisection cuts uncertainty by $1/2$ for each step, compared with approximately $S=|g^{\prime }(r)|$ for FPI. Therefore, Fixed-Point Iteration may be faster or slower than bisection, depending on whether S is smaller or larger than 1/2. Newton’s Method, a particularly refined version of FPI, where $S$ is designed to be zero

Cases when FPI works

1. Function $f(x)$ is continue in $[a,b]$
   1. $\forall x\in [a,b],a⩽f(x)⩽b$ , then there exists fixed-point.
   2. Based on 1, if $\exists L\in (0,1),s.t.|f(x_1)-f(x_2)⩽L(x_1-x_2)|\forall x_1,x_2\in [a,b]$
      • $f(x)$ exists only one global fixed-point.
      • Error satisfies $|x_k-x^{\ast }|\le \frac{L}{1-L}|x_k-x_{k-1}|\le \cdots \le \frac{L^k}{1-L}|x_1-x_0|$

Local Convergence Theorem: Let $x^{\ast }$ be the fixed-point, if $f^{\prime }(x)$ is continue in $[a,b]$ and $|f^{\prime }(x^{\ast })|<1$ .Then the FPI is locally convergent.

---

Limits of Accuracy

• Forward and backward error: Assume that $f$ is a function and that $r$ is a root, meaning that it satisfies $f(r)=0$. Assume that $x_a$ is an approximation to $r$. For the root-finding problem, the backward error of the approximation $x_a$ is $|f(x_a)-0|=|f(x_a)|$ and the forward error is $|r-x_a|$

Sensitivity of Root-finding

A problem is called sensitive if small errors in the input, in this case the equation to be solved, lead to large errors in the output, or solution.

Assume that the problem is to find a root $r$ of $f(x)=0$, but that a small change $g(x)$ is made to the input, where is small. Let $r$ be the corresponding change in the root:

$$f(r+\Delta r)+\epsilon g(r+\Delta r)=0$$ $$\Delta r\approx -\epsilon g\frac{r}{f^{\prime }(r)+\epsilon g^{\prime }(r)}\approx -\epsilon \frac{g(r)}{f^{\prime }(r)}$$

Example 1.9

• Error magnification factor : relative forward error / relative backward error. $\left|\frac{\Delta r/r}{ϵg(r)/g(r)}\right|=\left|\frac{-ϵg(r)/\left(r{f}^{\prime }(r)\right)}{ϵ}\right|=\frac{|g(r)|}{|r{f}^{\prime }(r)|}$

Examle of Wilkinson polynomial

The condition number of a problem is defined to be the maximum error magnification over all input changes, or at least all changes of a prescribed type. A problem with high condition number is called ill-conditioned, and a problem with a condition number near 1 is called well-conditioned

---

Newton’s Method

Newton's Method

x_0 & =\text { initial guess } \ x_{i+1} & =x_i-\frac{f\left(x_i\right)}{f^{\prime}\left(x_i\right)} \text { for } i=0,1,2, \ldots \end{aligned}$$

If $f(x)\in C^2(\mathbb{R})$ is a monotonically increasing convex function, and $f(r)=0$ , then $r$ is the only root and for $\forall x_0\in \mathbb{R}$ , Newton’s method will converges to $r$ .

Convergence Speed

Based on the Rate of convergence - Wikipedia, the order of convergence² and the rate of convergence of a convergent sequence are quantities that represent how quickly the sequence approaches its limit. A sequence $(x_n)$ that converges to $x^{\ast }$ is said to have order of convergence $q\ge 1$ and the rate of convergence $\mu$ if :

$$\underset{n\to \infty }{\lim }\frac{\left|x_{n+1}-x^{\ast }\right|}{{\left|x_n-x^{\ast }\right|}^q}=\mu$$

The rate of convergence $\mu$ is also called the asymptotic error constant.

• $q=1$ is called linear convergence if, and the sequence is said to _converge Q-linearly to $L$.
• $q=2$ is called quadratic convergence.
• $q=3$ is called cubic convergence.
• Etc.

Empirically, if the function $g\in C^p(a,b)$ is convergent to $x^{\ast }$ ，and its $p$ differential $g^{(p)}(x^{\ast })\ne 0$ , while $g^{(q)}(x^{\ast })=0,q=1,2,\cdots ,p-1$ then it’s said that $x_{i+1}=g(x_i)$ has $p$ order convergence speed, and it’s local convergent. For FPI, we have:

$$\underset{i\to \infty }{\lim }\frac{e_{i+1}}{e_i^p}=\frac{|g^{(p)}(x^{\ast })|}{p!}$$

Let $f\in C^2[a,b]$ and $f(r)=0$. If $f^{\prime }(r)\ne 0$, then Newton’s Method is locally and quadratically convergent to $r$. The error $e_i$ at step $i$ satisfies

$$\underset{i\to \infty }{\lim }\frac{e_{i+1}}{e_i^2}=\frac{f^{\prime \prime }(r)}{2f^{\prime }(r)}$$

If $f\in C^{(m+1)}[a,b]$ , which contains a root $r$ of multiplicity $m>1$ , then Newton’s Method’s error $e_i$ satisfies

$$\underset{t\to \infty }{\lim }\frac{e_{i+1}}{e_i}=\frac{m-1}{m}$$

converges locally and linearly to $r$ .

If $f\in C^{(m+1)}[a,b]$ , which contains a root $r$ of multiplicity $m>1$ , and $f^{(m+1)}(r)\ne 0$ , then Modified Newton’s Method

$$x_{i+1}=x_i-\frac{mf(x_i)}{f^{{}^{\prime }}(x_i)}$$

error $e_i$ satisfies

$$\underset{t\to \infty }{\lim }\frac{e_{i+1}}{e_i^2}=\frac{1}{m(m+1)}\left|\frac{f^{(m+1)}(r)}{f^{(m)}(r)}\right|$$

converges locally and quadratically to $r$ .

Examples of error approximation

Discuss When Newton’s Method Fails

1. The initial guess is not in locally convergence domain
2. Its differential equals to 0
3. The root function contains negative result.

An examle when the Newton's method fails

find the root of $f(x)=4x^4-6x^2-\frac{11}{4}$ with $x_0=1/2$

Methods without Derivatives

Secant Method and Variants

Secant method

$\begin{array}{rl}{x}_0,x_1& =\text{ initial guesses }\\ x_{i+1}& =x_i-\frac{f\left(x_i\right)\left(x_i-x_{i-1}\right)}{f\left(x_i\right)-f\left(x_{i-1}\right)}\text{ for }i=1,2,3,\dots \end{array}$

the approximate error relationship:

$e_{i+1}\approx |\frac{f^{{}^{\prime \prime }}(r)}{2f^{{}^{\prime }}(r)}|e_i{e}_{i+1}{e}_{i+1}\approx |\frac{f^{{}^{\prime \prime }}(r)}{2f^{{}^{\prime }}(r)}{|}^{\alpha -1}{e}_i^{\alpha }\alpha =\frac{1+\sqrt{5}}{2}$

Three Generalizations of the Secant Method

False Position

Given interval $[a,b]$ such that $f(a)f(b)<0$ for $i=1,2,3,\dots$ $\begin{array}{rl}& c=\frac{bf(a)-af(b)}{f(a)-f(b)}\\ & \text{ if }f(c)=0,\text{ stop, end }\\ & \text{ if }f(a)f(c)<0\\ & b=c\end{array}$ else $a=c$ end end

Newton’s method in solving nonlinear equation

For equations like

$$\begin{array}{rl}& \{\begin{array}{c}{f}_1\left(x_1,x_2,...,x_n\right)=0\\ f_2\left(x_1,x_2,...,x_n\right)=0\\ ⋮\\ f_n\left(x_1,x_2,...,x_n\right)=0\end{array}\end{array}$$

Let’s Define $F={\left[f_1,f_2,\cdots ,f_3\right]}^T$ , and Jacobi Matrix: $J\left(X\right)=F^{\prime }\left(X\right)=\left(\begin{array}{ccc}\frac{\partial f_1\left(X\right)}{\partial x_1}& \cdots & \frac{\partial f_1\left(X\right)}{\partial x_n}\\ ⋮& \ddots & ⋮\\ \frac{\partial f_n\left(X\right)}{\partial x_1}& \cdots & \frac{\partial f_n\left(X\right)}{\partial x_n}\end{array}\right)$

Then here comes the Newton’s method:

$$X_{i+1}=X_i-J^{-1}\left(X_i\right)F\left(X_i\right)$$

Example of Newton's Method in solving nonlinear equations

• 例: 求解方程组

$$\{\begin{array}{c}{f}_1(u,v)=v-u^3=0\\ f_2(u,v)=u^2+v^2-1=0\end{array}$$

Jacobi i矩阵

$$J(u,v)=\left[\begin{array}{cc}-3u^2& 1\\ 2u& 2v\end{array}\right]$$

牛顿迭代式 $\left(X=[u,v{]}^T,F=\left[f_1,f_2\right]\right)$ : $J\left(u_i,v_i\right)\left(X_{i+1}-X_i\right)=-F\left(X_i\right)$ 取 $X_0=[1,2]$ 第一步迭代计算为

$$\left[\begin{array}{cc}-3& 1\\ 2& 4\end{array}\right]\left[\begin{array}{l}{u}_{i+1}-u_i\\ v_{i+1}-v_i\end{array}\right]=-\left[\begin{array}{l}1\\ 4\end{array}\right]\Rightarrow \left[\begin{array}{l}{u}_{i+1}\\ v_{i+1}\end{array}\right]=\left[\begin{array}{l}1\\ 1\end{array}\right]$$

Footnotes

1. Sauer, Timothy. Numerical analysis. Addison-Wesley Publishing Company, 2011. ‌ ↩

2. Wikipedia Contributors (2023) Rate of convergence. In: Wikipedia. https://en.wikipedia.org/wiki/Rate_of_convergence. Accessed 13 Mar 2023 ↩