Numerical analysis notes (I): equation root

---

Search of root

• Step by step search

  In a given interval $[a,b]$ Up from the left endpoint $x=a$ Start , In steps $h$ Take it step by step $f(x_0)$ and $f(x_0+h)$, If found to be true $f(x_0)\cdot f(x_0+h)\le 0$ Then in the interval $[x_0,x_0+h]$ Rooted .

  When $h$ Too many searches are required when it is too small , Too much calculation .

• Two point search

  Yes, there are root intervals $[a_0,b_0]$ Implement the following dichotomy procedures ： Midpoint $x_0=\frac{a_0+b_0}{2}$ Divide the interval into two halves , Judge the root $x^{\ast }$ stay $x_0$ Which side of the road , So as to determine the new rooted interval $[a_1,b_1]$, The length of $[a_0,b_0]$ Half of . If the infinite loop goes on , There is a root interval It must be convergent At one point $x^{\ast }$.

• Trial position method （Method of False Position
  ）

  thought ： Looking for $f(a)$ and $f(b)$ Secant and x The intersection of the axes $(c,0)$

Iterative method

The core idea of iterative method is Explicit implicit equation . Put the equation $f(x)=0$ to $x=\phi (x)$, Give an approximate value of the root of the equation $x_k$, Plug in , have to $x_{k+1}=\phi (x_k)$, That is, we can get the sequence starting from the given initial value $x_1,x_2,x_3,\cdots$. If this sequence is convergent , Then obviously there is the root of the equation $x^{\ast }=\underset{k\to \infty }{\lim }{x}_k$.

Judgment of convergence

If there is a neighborhood $\Delta :|x-x^{\ast }|\le \delta ,\forall \delta >0$, In the iteration process $\forall x_0\in \Delta$, It is called at the root $x^{\ast }$ Proximity convergence . among $x_0$ Is the initial value of the iteration .

set up $\phi (x)$ In the equation $x=\phi (x)$ The root of the $x^{\ast }$ The neighborhood of has a continuous first derivative , And established $|{\phi }^{\prime }(x^{\ast })|<1$, Then the iterative process $x_{k+1}=\phi (x_k)$ stay $x^{\ast }$ Proximity has local convergence . in other words , Iterative process with local convergence $x_{k+1}=\phi (x_k)$ For sufficiently accurate iterative initial values $x^{\ast }$ convergence .

Convergence rate

For iterative processes with local convergence $x_{k+1}=\phi (x_k)$, if ${\phi }^{\prime }(x^{\ast })\ne 0$ The iterative process is said to be linearly convergent , And when ${\phi }^{\prime }(x^{\ast })=0$ And ${\phi }^{\prime \prime }(x^{\ast })\ne 0$, The iterative process is said to be square convergent .

To accelerate the iteration

First, consider the linear iterative function

set up $\phi (x)$ Is a linear function $\phi (x)=Lx+d,L>0$

Then the iterative formula of the given equation is $x_{k+1}=L{x}_k+d$

The root of the equation $x^{\ast }$ Satisfy $x^{\ast }=L{x}^{\ast }+d$

Subtracting two formulas , Yes $x^{\ast }-x_{k+1}=L(x^{\ast }-x_k)$

For iteration error $e_k=|x^{\ast }-x_k|$, Yes $e_{k+1}=L{e}_k$

Repeat , Yes $e_k=L^k{e}_0$

$L<1$ when , The iterative sequence converges , And L The smaller the size, the faster the convergence rate .

Use the above ideas , We can accelerate the iterative process . set up $x_k$ It's a root $x^{\ast }$ An approximation of , Use the iterative formula to correct once , Yes ${\bar{x}}_{k+1}=\phi (x_k)$. hypothesis ${\phi }^{\prime }(x)$ There is little change in the scope of investigation , Its estimated value is $L$, be $x^{\ast }-{\bar{x}}_{k+1}\approx L(x^{\ast }-x_k)$. Find out $x^{\ast }$, Yes $x^{\ast }\approx \frac{1}{1-L}{\bar{x}}_{k+1}-\frac{L}{1-L}{x}_k$. That is to say
$\{\begin{array}{lr}{\bar{x}}_{k+1}=\phi (x_k),& Overlappinggeneration\\ x_{K+1}=\frac{1}{1-L}{\bar{x}}_{k+1}-\frac{L}{1-L}{x}_k,& Addspeed\end{array}$

namely $x_{k+1}=\frac{1}{1-L}[\phi (x_k)-L{x}_k]$

However, the above accelerated iteration method needs to deal with the first derivative , It is not convenient for some iterative formulas . A more general , We have Aitken Acceleration method

$\{\begin{array}{lr}{\bar{x}}_{k+1}=\phi (x_k),& Overlappinggeneration\\ {\tilde{x}}_{k+1}=\phi ({\bar{x}}_{k+1}),& Overlappinggeneration\\ x_{K+1}={\tilde{x}}_{k+1}-\frac{(x_{k+1}-{\bar{x}}_{k+1}{)}^2}{{\tilde{x}}_{k+1}-2{\bar{x}}_{k+1}+x_k},& Addspeed\end{array}$

The idea is to use the estimated value for the second iteration , Then do business to eliminate $L$, Finally, the solution is $x^{\ast }$, Just replace it .Aitken Its shortcomings are also obvious ： It takes two iterations to get an estimate .

Newton Law （ Tangent method ）

Newton method is the most widely used iterative method . The Newton formula is derived below . Investigate $f(x)=0$, Let the approximate root be known $x_k$, Obviously , We hope that $x_{k+1}=x_k+\Delta x$ Try to satisfy $f(x_k+\Delta x)\approx 0$. Replace its left end with its linear principal part , Yes $f(x_k)+f^{\prime }(x_k)\Delta x=0$, thus , figure out $\Delta x=-\frac{f(x_k)}{f^{\prime }(x_k)}$, Thus to $x_{k+1}=x_k+\Delta x$ Yes

$x_{k+1}=x_k-\frac{f(x_k)}{f^{\prime }(x_k)}$

That's the famous one Newton Iterative formula

solve $f(x)=x^2-a=0$ when ,$f^{\prime }(x)=2x$, Its Newton The iteration function is $\phi (x)=x-\frac{f(x_k)}{f^{\prime }(x_k)}=\frac{1}{2}\left(a+\frac{a}{x}\right)$, This is the opening method of Ancient Mathematics .

Newton Improvement of the method

Newton How to go down the mountain

The basic idea ： Each iteration ensures the descent condition , namely $|f(x_{k+1})|<|f(x_k)|$, This ensures global convergence .

specific working means ： Add the downhill factor $\lambda$, Will improve the value $x_{k+1}$ And the result of the previous step $x_k$ Take the weighted average , namely $x_{k+1}=\lambda {\bar{x}}_{k+1}+(1-\lambda )x_k$, That is to say , The iterative formula becomes $x_{k+1}=x_k-\lambda \frac{f(x_k)}{f^{\prime }(x_k)}$, among $\lambda$ Take from 1 Begin to $\lambda$ Repeat and halve , Until you meet $|f(x_{k+1})|<|f(x_k)|$.

String cutting

In order to avoid the calculation of derivatives , We can take secant instead of tangent , Thus, the iterative formula of chord cut method is derived ：$x_{k+1}=x_k-\frac{f(x_k)}{f(x_k)-f(x_0)}(x_k-x_0)$. Although the chord cut method avoids the calculation of derivatives , But its iteration speed is only one order .

Fast chord cut

To improve the efficiency of chord cutting , Then process the chord cutting formula , Thus, we derive the formula of fast chord cut method ：$x_{k+1}=x_k-\frac{f(x_k)}{f(x_k)-f(x_{k-1})}(x_k-x_{k-1})$. The convergence speed of fast chord cut method is undoubtedly faster than that of chord cut method , But it needs to provide two iteration initial values , So it is also called two-step .

Improved Newton method

For the case of multiple roots , When $f(x)=(x-x^{\ast }{)}^{m}g(x)$ And $g(x^{\ast })\ne 0$ when , Directly use Newton's method , Its ${\phi }^{\prime }(x^{\ast })=1-\frac{1}{m}>0$, It is only linear convergence .

One way to improve is to modify the iteration formula , elimination $m$, At this point, the iteration formula becomes $\phi (x)=x-m\frac{f(x)}{f^{\prime }(x)}$, here ${\phi }^{\prime }(x^{\ast })=0$, Convergence becomes better . But this improvement method needs to know the specific order of multiple roots $m$.

Another way to improve is to use $\mu (x)=\frac{f(x)}{f^{\prime }(x)}$ And $f(x)=(x-x^{\ast }{)}^{m}g(x)$ The nature of the same root , Yes $\mu (x)$ Using Newton's method ,$\phi (x)=x-\frac{\mu (x)}{{\mu }^{\prime }(x)}=x-\frac{f(x)f^{\prime }(x)}{|f^{\prime }(x){|}^2-f(x)f^{\prime \prime }(x)}$ Thus, the iterative formula is $x_{k+1}=x_k-\frac{f(x_k)f^{\prime }(x_k)}{|f^{\prime }(x_k){|}^2-f(x_k)f^{\prime \prime }(x_k)}$, It's easy to prove , It is second-order convergent .