\documentclass[a4paper]{ctexart} %CTEX報告文章格式



\usepackage[top=3cm,bottom=2cm,left=2cm,right=2cm]{geometry} % 頁邊距
\usepackage{amsmath} %數(shù)學公式
\usepackage{amsthm}
%\usepackage{longtable} %長表格
\usepackage{graphicx} %圖片
\usepackage{tikz} %畫圖
\usepackage{cite}
\usepackage{listings}
\usepackage{amsfonts}
\usepackage{subfigure}
\usepackage{float}
%\usepackage[colorlinks,linkcolor=black,hyperindex,CJKbookmarks,dvipdfm]{hyperref}
\lstset{language=Mathematica}%這條命令可以讓LaTeX排版時將Mathematica鍵字突出顯示
\lstset{extendedchars=false}%這一條命令可以解決代碼跨頁時饼拍，章節(jié)標題完慧，頁眉等漢字不顯示的問題
\usetikzlibrary{shapes,arrows} %tikz圖形庫
\usepackage{overpic} %圖上標記
\usepackage{ccaption} %中英文題注
%\usepackage[numbers,sort&compress]{natbib} %參數(shù)代表：數(shù)字和排序與壓縮
%\bibliographystyle{GBT7714-2005NLang} %參考文獻格式設為GBT7714-2005N.bst
%\usepackage[draft=false,colorlinks=true,CJKbookmarks=true,linkcolor=black,citecolor=black,urlcolor=blue]{hyperref} %參考文獻跳轉，此宏包會自動載入graphicx
\usepackage{textcomp} %攝氏度符號
%\usepackage{ccmap} %pdf中文復制
%\usepackage{myfont} %字體
\usepackage{color} %gnuplot彩色文字
%\usepackage{texshade} %texshade珠十，此宏包與graphicx沖突，故放最后
% \usepackage{indentfirst}
% \setlength{\parindent}{2em}
%\makeatletter
%%\renewcommand{\chapter} {\endgraf
%%   \thispagestyle{empty}           % Page style of chapter page is 'plain'
%%   \global\@topnum\z@              % Prevents figures from going at top of page.
%%   \@afterindenttrue               % Inserts indent in first paragraph.  Change
%%   \secdef\@chapter\@schapter}     % to \@afterindentfalse to remove indent.
%\makeatother




%\renewcommand{\textfraction}{0.15}
%\renewcommand{\topfraction}{0.85}
%\renewcommand{\bottomfraction}{0.65}
%\renewcommand{\floatpagefraction}{0.60}
%\author{陸嵩}





\begin{document}
%\CTEXoptions[contentsname={\bfseries\zihao{4} 目\quad 錄}]
%%\CTEXsetup[nameformat+={\zihao{3}}]{chapter}
%%\CTEXsetup[titleformat+={\zihao{3}}]{chapter}
%\CTEXsetup[number={\arabic{chapter}}]{chapter}
%\CTEXsetup[name={,}]{chapter}
%\CTEXsetup[format={\zihao{4}}]{section}
%\CTEXsetup[format={\bfseries\zihao{4}}]{subsection}
%\CTEXsetup[format={\bfseries\zihao{-4}}]{paragraph}
%%\CTEXsetup[beforeskip={0em}]{paragraph}
%\CTEXsetup[beforeskip={0pt}]{chapter}
%\CTEXsetup[afterskip={2em}]{chapter}
%%\CTEXsetup[afterskip={0pt}]{subsection}
%%\captionwidth{0.8\textwidth}
%%\changecaptionwidth
%\thispagestyle{empty}
%%%\pagestyle{plain}
%%\newpage
%\setcounter{page}{1}
%\pagenumbering{Roman}
%\noindent\addcontentsline{toc}{section}{摘要}
\begin{center}\zihao{3}\textbf{15級計算機科學與技術二班\\優(yōu)良學風創(chuàng)建情況報告}\end{center}
\begin{center}\zihao{5}\textbf{鄭州大學\ 數(shù)學與統(tǒng)計學院 \ 信息與計算科學 \ 陸嵩}\end{center}
\begin{center}\zihao{4}\textbf{摘要}\quad\zihao{-4}\end{center}
\vspace{1em}
%\noindent\zihao{4}\textbf{關鍵詞}\quad\zihao{-4} 最小旋轉曲面任柜；Mathematica哨鸭；樣條插值；變分法
%\tableofcontents
\setcounter{page}{1}
\pagenumbering{arabic}
\pagestyle{headings}

5.5到5.8節(jié)主要介紹了了多項式求根和一些典型的求根方法往枣。其中有很多我們想不到的方法。比如說粉渠，正如我們看到的分冈，Bauer（1956）、Jenkins和Traub（1970）霸株、Nickel（1966）以及Henrici（1974）雕沉，這些人提到了一些。

我們確定一般多項式的根的一般方法的重要性有時會被評價過高去件。在實際應用中的多項式大部分會以一種特定的形式給定蘑秽，比如說，特征多項式就是這樣箫攀。之后肠牲，你將學習到，多項式的根就是矩陣的特征值靴跛，進一步缀雳，我們將在第六章詳細描述這個方法。

我們將詳細講述牛頓方法在尋找給定多項式$p(x)$的根方面的應用梢睛。為了評價牛頓迭代方程肥印，
\[{x_{k{\rm{ + }}1}}: = {x_k} - \frac{{p({x_k})}}{{p'({x_k})}}\]
我們不得不計算多項式以及多項式一階導在點$x=x_k$ 處的值识椰。假定多項式以下列的形式給出
\[p(x) = {a_0}{x^n} + {a_1}{x^{n - 1}} +  \cdots  + {a_n}\]
那么$p(x_k)$和$p'(x_k)$可用如下方法計算：對于$x = \xi $,
\[p(\xi ) = ( \cdots (({a_0}\xi  + {a_1})\xi  + {a_2})\xi  +  \cdots )\xi  + {a_n}\].
對于在這個表達式中乘數(shù)$\xi$，可用如下的遞歸格式
\begin{equation}
\label{5.5.1}
\begin{array}{l}
{b_0}: = {a_0}\\
{b_i}: = {b_{i - 1}}\xi  + {a_i},i = 1,2,...,n.
\end{array}
\end{equation}
多項式$p$在$\xi$出的值可以這樣給定：
\[p(\xi ) = {b_n}\]

通過遞歸式子(\ref{5.5.1})評估多項式的算法被稱作 Horner方法深碱。我們所能得到的$b_i$的量腹鹉，也正是以下多項式的的系數(shù)
\[{p_1}(x): = {b_0}{x^{n - 1}} + {b_1}{x^{n - 2}} + ... + {b_{n - 1}}\]
用$x-\xi$去除$p(x)$，我們能得到：
\begin{equation}\label{5.5.2}
p(x) = (x - \xi )p{}_1(x) + {b_n}
\end{equation}
這通過比較式(ref{5.5.2})兩邊的系數(shù)敷硅，很容易被證實功咒。進一步，對式(ref{5.5.2})關于$x$兩邊求導绞蹦，并讓$x=\xi$,我們得到
\[p'(\xi ) = {p_1}(\xi )\]
因此力奋，一階導數(shù)$p'(\xi)$能通過重復使用Horner方法來確定，用前一個的結果來做后一個式子的系數(shù)幽七。
\[p'(\xi ) = ( \cdots ({b_0}\xi  + {b_1})\xi {\rm{ + }} \cdots )\xi  + {b_{n - 1}}\]

通常地景殷，多項式$p(x)$一般是以除此之外的其他一些格式給出的，
\[p(x) = {a_0}{x^n} + {a_1}{x^{n - 1}} +  \cdots  + {a_n}\]
特別重要一種情況是澡屡，$p(x)$正好是三對角矩陣的特征多項式
\[J = \left[ {\begin{array}{*{20}{c}}
{{\alpha _1}}&{{\beta _2}}&{}&0\\
{{\beta _2}}& \ddots & \ddots &{}\\
{}& \ddots & \ddots &{{\beta _n}}\\
0&{}&{{\beta _n}}&{{a_n}}
\end{array}} \right]\]
其中猿挚，${\alpha _i},{\beta _i}$是實數(shù)。
也就是說驶鹉，多項式是特征矩陣
\[{p_i}(x) = \det \left( {\left[ {\begin{array}{*{20}{c}}
{{\alpha _1} - x}&{{\beta _2}}&{}&0\\
{{\beta _2}}& \ddots & \ddots &{}\\
{}& \ddots & \ddots &{{\beta _i}}\\
0&{}&{{\beta _i}}&{{a_i} - x}
\end{array}} \right]} \right)\]
原則上的順序主子式绩蜻。我們有遞推序列:
\begin{equation}
\begin{array}{l}\label{5.5.3}
{p_0}(x): = 1\\
{p_1}(x): = ({\alpha _1} - x) \cdot 1\\
{p_i}(x): = ({\alpha _i} - x){p_{i - 1}}(x) - {\beta _i}^2{p_{i - 2}}(x)\;\;\;\;\;\;\;\;\;\;i = 2,3, \cdots n.\\
p(x): = det(J - xI): = {p_n}(x)
\end{array}
\end{equation}
這些公式能夠被用來計算對于任意$x=\xi$的$p(\xi)$，和任意給定的矩陣元素$\alpha_i,\beta_i$梁厉。類似地，我們通過對式(\ref{5.5.3}) 求導踏兜，可以推得$p'(x)$的遞推方程如下：
\begin{equation}\label{5.5.4}
\begin{array}{l}
{p_0}'(x): = 0\\
{p_1}'(x): =  - 1\\
{p_i}'(x): =  - {p_{i - 1}}(x) + ({\alpha _i} - x)p{'_{i - 1}}(x) - {\beta _i}^2p{'_{i - 2}}(x)\;\;\;\;\;\;\;\;\;\;i = 2,3, \cdots n.\\
p'(x): = p{'_n}(x)
\end{array}
\end{equation}
兩個遞推公式(\ref{5.5.3})和(\ref{5.5.4})能夠同時被計算词顾。

通過5.3節(jié)對牛頓方法一般性的討論，我們清楚地知道碱妆，當且僅當初始點$x_0$足夠接近零點$\xi$的時候肉盹，由牛頓方法確定的$x_k$是收斂的。一個糟糕的初始值可能會導致序列$x_k$發(fā)散疹尾，即使是對多項式也不例外上忍。如果實多項式$p(x)$沒有實根（例如：$p(x)=x_2+1$），那么牛頓方法對于任意的實數(shù)域內(nèi)的初始值是不可能收斂的纳本。對于任意的多項式個例窍蓝，我們沒有通用而保險的選取有效初值的方法。但是呢繁成，在一種重要而特別的情況下吓笙，我們確實存在一種通用的方法。也就是這種情況巾腕，如果所有的根$\xi$是實的($i=1,2,...,n.)$)面睛，并且滿足：
\[{\xi _1} \ge {\xi _2} \ge  \cdots  \ge {\xi _n}.\]
在5.6部分絮蒿，定理（5.6.5）將向我們證明，那么由式(\ref{5.5.3})定義的多項式在矩陣元素$\alpha_i,\beta_i$是實數(shù)的前提下將具備這種屬性叁鉴。

\newtheorem{theorem}{Theorem}
\begin{theorem}\label{5.5.5}
$p(x)$是維度$n \ge 2$的實系數(shù)多項式土涝，如果對于所有的根$\xi_i$都是實數(shù)，其中幌墓，
${\xi _1} \ge {\xi _2} \ge  \cdots  \ge {\xi _n}.$
那么但壮，牛頓方法對于任意的初值$x_0 \ge \xi_1$,都能產(chǎn)生一個嚴格遞減的序列$x_k$.
\end{theorem}
\begin{proof}[證明]
不失一般性，我們可以假設$p(x_0) > 0$
既然$p(x_0)$對于$x>\xi_1$不換號克锣，那么對于任意的$x>\xi_1$我們有茵肃，
\[p(x) = {a_0}{x^n} +  \cdots  + {a_n} > 0\]
因此，我們可以知道$a_0>0$.并且通過羅爾定理袭祟，我們知道验残，導數(shù)$p'(x)$有$n-1$個實根，并且
\[{\xi _1} \ge {\alpha _1} \ge {\xi _2} \ge {\alpha _2} \ge  \cdots  \ge {\alpha _{n - 1}} \ge {\xi _n}\]
因為$p'$的維度是$n-1$且大等于1巾乳，上面表示的$\alpha_i$恰好是它全部的根您没。因$a_0>0$容易推知，對于任意的$x>\alpha_1$胆绊，我們有$p'(x)>0$氨鹏。再次運用羅爾定理，和重新使用條件$n \ge 2$,我們可以知道
\begin{equation}\label{5.5.6}
\begin{array}{l}
p''(x) > 0\;\;\;x > \alpha {}_1\\
p'''(x) \ge 0\;\;\;x \ge \alpha {}_1
\end{array}
\end{equation}
因此压状，對于任意的$x \ge \alpha_1$,$p,p'$都是下凸函數(shù)仆抵。


現(xiàn)在，由于$p'(x_k)>0 ,p(x_k)>0$$x_k>\xi_i$暗示著
\[{x_{k + 1}} = {x_k} - \frac{{p({x_k})}}{{p'({x_k})}} < {x_k}\]
現(xiàn)在還有待證明的是种冬，我們用牛頓方法不能“過調”镣丑。從式（\ref{5.5.6}）,我們知道$x_k>\xi_1 \ge \alpha_1$，進一步娱两，由泰勒定理莺匠，我們可以推導得到
\[0 = p({\xi _1}) = p({x_k}) + ({\xi _1} - {x_k})p'({x_k}) + \frac{1}{2}{({\xi _1} - {x_k})^2}p''(\delta ) > p({x_k}) + ({\xi _1} - {x_k})p'({x_k})\;\;\;{\xi _1} < \delta  < {x_k}\]
由$x_{k+1}$的定義式，移向我們可以得到$p(x_k)=p'(x_k)(x_k-x_k+1)$十兢，因此趣竣，
\[0 > p'({x_k})({x_k} - {x_{k + 1}} + {\xi _1} - {x_k}) = p'({x_k})({\xi _1} - {x_{k + 1}})\]
再由$p'(x_k)>0$，立得$x_k+1>\xi_1$
\end{proof}

為了之后的使用旱物，我們注意定理\ref{5.5.6}接下來的結果:
\newtheorem{lemma}{Lemma}
\begin{lemma}\label{5.5.7}
設$p(x) = {a_0}{x^n} + {a_1}{x^{n - 1}} +  \cdots  + {a_n}>0,$ 是一個維度$n \ge 2$且所有根都是實數(shù)的實系數(shù)多項式遥缕。假如$\alpha_1$是$p'$ 最大的根，那么對于任意的$x \ge \alpha_1$宵呛，有$p'''(x) \ge 0$,換言之通砍，對于任意的$x \ge \alpha_1$，$p'$是一個下凸函數(shù)。
\end{lemma}


我們?nèi)匀幻媾R一個問題封孙。那就是在事前不知道$\xi_1$ 的前提下迹冤，如何尋找一個比$\xi_1$大的初值$x_0$呢？以下的定理可以解決這個問題：
\begin{theorem}\label{5.5.8}
對任意的一個多項式$p(x) = {a_0}{x^n} + {a_1}{x^{n - 1}} +  \cdots  + {a_n}$虎忌，它的所有根$\xi$都滿足：
\[\left| {{\xi _i}} \right| \le \max \left\{ {\left| {\frac{{{a_n}}}{{{a_0}}}} \right|,1 + \left| {\frac{{{a_{n - 1}}}}{{{a_0}}}} \right|, \cdots ,1 + \left| {\frac{{{a_1}}}{{{a_0}}}} \right|} \right\}\]
\[\left| {{\xi _i}} \right| \le \max \left\{ {1,\sum\limits_{j = 1}^n {\left| {\frac{{{a_j}}}{{{a_0}}}} \right|} } \right\}\]
\[\left| {{\xi _i}} \right| \le \max \left\{ {\left| {\frac{{{a_n}}}{{{a_{n - 1}}}}} \right|,2\left| {\frac{{{a_{n - 1}}}}{{{a_{n - 2}}}}} \right|, \cdots ,2\left| {\frac{{{a_1}}}{{{a_0}}}} \right|} \right\}\]
\[\left| {{\xi _i}} \right| \le \sum\limits_{j = 0}^{n - 1} {\left| {\frac{{{a_{j + 1}}}}{{{a_j}}}} \right|} \]
\[\left| {{\xi _i}} \right| \le 2\max \left\{ {\left| {\frac{{{a_1}}}{{{a_0}}}} \right|,\sqrt {\left| {\frac{{{a_2}}}{{{a_0}}}} \right|} ,\sqrt[3]{{\left| {\frac{{{a_3}}}{{{a_0}}}} \right|}} \cdots ,\sqrt[n]{{\left| {\frac{{{a_n}}}{{{a_0}}}} \right|}}} \right\}\]
\end{theorem}

這些差異中的一部分將在6.9節(jié)中證明泡徙，同時也和Househoder(1970)做一個比較。其他的不同將在Marden(1949)能找到膜蠢。

二次收斂并不意味著快速收斂堪藐。如果選取的初值離根非常遠的話，那么牛頓方法在開始的時候可能就收斂得非常緩慢挑围。事實上礁竞，如果$x_k$足夠大，那么
\[{x_{k + 1}} = {x_k} - \frac{{x_k^n +  \cdots }}{{nx_k^{n - 1} +  \cdots }} \approx {x_k}\left( {1 - \frac{1}{n}} \right)\]
導致在$x_k$和$x_{k+1}$之間變化非常小杉辙。這些結果導致我們?nèi)で蟾玫摹半p步法”來代替直接的牛頓方法模捂，如下：
\[{x_{k + 1}} = {x_k} - 2\frac{{p({x_k})}}{{p'({x_k})}}\;\;\;k = 0,1,2, \ldots \]


當然，現(xiàn)在我們有了“過調”的風險蜘矢。特別地狂男，在多項式只有實根，且初值$x_0 \ge \xi_1$的情況下品腹，迭代出的某些$x_{k+1}$可能會越過最大一個根$\xi_1$,從而失去了定理\ref{5.5.5}的優(yōu)勢岖食。但是不要怕，這種“過調”導致的不收斂是可以被消除的舞吭。由于多項式的一些優(yōu)良屬性泡垃，在上述情況發(fā)生的前提下，我們可以找到一個好的新初值$y(\xi_1 \ge > \xi_2)$羡鸥，接著用牛頓方法進行迭代蔑穴，最后也能收斂。之后將給出以下定理的結果：
\begin{theorem}\label{5.5.9}
設$p(x) = {a_0}{x^n} + {a_1}{x^{n - 1}} +  \cdots  + {a_n}>0,$ 是一個維度$n \ge 2$且所有根都是實數(shù)的實系數(shù)多項式兄春。并且$p(x)$ 的根排序如下澎剥，${\xi _1} \ge {\xi _2} \ge  \cdots  \ge {\xi _n}.$ 另外锡溯，假如$\alpha_1$是$p'$最大的根赶舆，
\[{\xi _1} \ge {\alpha _1} \ge {\xi _2}\]
對于$n=2$,我們需要特別要求$\xi_1 \ge \xi_2$，那么對于每一個$z>\xi_1$,一些符號的定義如下：
\[z': = z - \frac{{p(z)}}{{p'(z)}},y: = z - 2\frac{{p(z)}}{{p'(z)}},y': = y - \frac{{p(y)}}{{p'(y)}}\]
（圖\ref{Figure 8}很好地刻畫了這個問題）祭饭，則有以下結論：
\[\begin{array}{l}\label{5.5.10}
{\alpha _1} < y\\
{\xi _1} \le y' \le z'
\end{array}\]
\begin{figure}[!h]
\small
\centering
\includegraphics[width=12cm]{111.eps}
\caption{Geometric interpretation of the double-step method} \label{Figure 8}
\end{figure}
\end{theorem}
容易證明當$n=2$并且$\xi_1=\xi_2$時芜茵，也就意味著對于任意的$z>\xi_1$,都有$y=\xi_1$
\begin{proof}[證明]
再次假設當$z>\xi_1$時，$p(z)>0$倡蝙。對于這樣一個$z$值九串，我們假設有兩個兩個量$\Delta_0,\Delta_1$(如圖\ref{Figure 8}所示)定義如下：
\[{\Delta _0}: = p(z') = p(z') - p(z) - (z' - z)p'(z) = \int_z^{z'} {\left[ {p'(t) - p'(z)} \right]} dt\]
\[{\Delta _1}: = p(z') - p(y) - (z' - y)p'(y) = \int_y^{z'} {\left[ {p'(t) - p'(y)} \right]} dt\]
當然，這兩個量還可以分別地被解釋為關于$p'(x)$的圖上的兩塊區(qū)域，見圖\ref{Figure 9}猪钮。
\begin{figure}[!h]
\small
\centering
\includegraphics[width=12cm]{222.eps}
\caption{The quantities $\Delta_0$ and $\Delta_1$ interpreted as areas} \label{Figure 9}
\end{figure}
通過引理\ref{5.5.7},$p'(x)$在$x \ge \alpha_1$是個下凸函數(shù)品山。因此，我們知道$z'-y=z-z'>0$(由定理\ref{5.5.5}知道它是正值)烤低，我們可以得到
\begin{equation}\label{5.5.11}
{\Delta _1} \le {\Delta _0}\;\;\;y \ge {\alpha _1}
\end{equation}
$\Delta_0=\Delta_1$當且僅當$p'$是線性函數(shù)肘交，也就是說$p$是次數(shù)為2的多項式。現(xiàn)在我們分為$y>\xi_1,y=\xi_1,y<\xi_1$三種情況來討論扑馁。對于$y>\xi_1$,由定理\ref{5.5.5},立證得涯呻。對于$y=\xi_1$,我們首先證明$\xi_2<\alpha_1<\xi_1$,也就是說$\xi_1$是$p$的單根。假如$y=\xi_1=\xi_2=\alpha_1$是復根腻要，那么复罐，通過$n \ge 3$的假設，由式\ref{5.5.11},我們能得到雄家，$\Delta_1<\Delta_0$. 這樣將導出矛盾
\[{\Delta _1} = p(z') - p({\xi _1}) - (z' - {\xi _1})p'({\xi _1}) = p(z') < {\Delta _0} = p(z')\]
因而效诅，$\xi_1$一定是單根。因此$\xi_2<\xi_1<y<\alpha_1$,因此在第二種情況下咳短，結論貌似也是對的填帽。


現(xiàn)在只剩下$y<\xi_1$這種情況了。如果$alpha_1<y$,那么命題正確性可由如下方法建立咙好。既然$p(x)>0$并且$\xi_2<\alpha_1<y<\xi_1$,我們可以得到$p(y)<0,p'(y)>0.$,特別是$y$是適定的情況篡腌。進一步，因為$p(y)=(y-y')p'(y)$且$\Delta_0 \ge \Delta_1$,我們有
\[{\Delta _0} - {\Delta _1} = p(y) + (z' - y)p'(y) = p'(y)(z' - y') \ge 0\]
因此$z' \ge y'$,泰勒展開勾效，最后得到
\[p({\xi _1}) = 0 = p(y) + ({\xi _1} - y)p'(y) + \frac{1}{2}{({\xi _1} - y)^2}p''(\delta )\;\;\;y < \delta  < {\xi _1}\]
進一步嘹悼，因為當$x \ge \alpha_1$時，$p''(x) \ge 0$,且$p(y)=(y-y')p'(y)$和$p'(y)>0$
\[0 \ge p(y) + ({\xi _1} - y)p'(y) = p'(y)({\xi _1} - y')\]
因此$y' \ge \xi_1$

為了完成證明层宫，我們接著要證明杨伙，對于任意的$z>\xi_1$,有這樣的結論
\begin{equation}\label{5.5.12}
y = y(z) > {\alpha _1}
\end{equation}
我們再次分為兩種情況。$\xi_1>\alpha_1>\alpha_2$和$\xi_1=\alpha_1=\xi_2$.

如果$\xi_1>\alpha_1>\alpha_2$萌腿，那么由\ref{5.5.12},在任何情況下
\[{\xi _1} < z < {\xi _1} + ({\xi _1} - {\alpha _1})\]
這是因為定理\ref{5.5.5}暗示著$z>z' \ge \xi_1$,因此由$y=y(z)$的定義限匣，可得
\[y = z' - (z - z') > {\xi _1} - ({\xi _1} - {\alpha _1}) = {\alpha _1}\]
從而我們可以選擇一個$z_0$使得$y(z_0)>\alpha_1$.假設存在一個$z_1>\xi_1$,使得$y(z_1) \le \alpha_1$,由連續(xù)函數(shù)的介值定理，存在一個$\overline z  \in [{z_0},{z_1}]$,使得$\overline y=y(\overline z)=\alpha_1$,從\ref{5.5.11},對于$z=\overline z$
\[{\Delta _1} = p(\overline z ') - p(\overline y ) - (\overline z ' - \overline y )p'(\overline y ) = p(\overline z ') - p(\overline y ) \le {\Delta _0} = p(\overline z ')\]
進而$p(\overline y)=p(alpha) \ge 0$毁菱。另一方面呢米死，由$\xi_1$是在我們的例子中是單根，導致$p(x)$變號贮庞，這是矛盾的峦筒，因此式\ref{5.5.12}必須對所有的$z>\xi_1$都要成立。

如果$\xi_1=\alpha_1=\xi_2$,那么由假設$n \ge 3$,不失一般性窗慎，我們假定
\[p(x) = {a_0}{x^n} + {a_1}{x^{n - 1}} +  \cdots  + {a_n}\]
進而
\[z' = z - \frac{{p(z)}}{{p'(z)}} = z - \frac{z}{n}\frac{{1 + \frac{{{a_1}}}{z} +  \cdots  + \frac{{{a_n}}}{{{z^n}}}}}{{1 + \frac{{n - 1}}{n}\frac{{{a_1}}}{z} +  \cdots  + \frac{{{a_{n - 1}}}}{{n{z^{n - 1}}}}}} = z - \frac{z}{n}\left( {1 + O(\frac{1}{z})} \right)\]
從而
\[y = y(z) = z + 2(z' - z) = z - \frac{{2z}}{n}\left( {1 + O(\frac{1}{z})} \right) = z\left( {1 - \frac{2}{n}} \right) + O(1)\]
因為$n \ge 3$,那么隨著$z$的增大到正無窮物喷，$y(z)$的值也無限增大卤材。因此，我們也再次推斷存在一個$z_0>\xi$,使得$y_0=y(z_0)>\alpha_1$.假如并不是對所有的$z>\xi_1$,式\ref{5.5.12}成立的話峦失，那么我們就能像前面推導那樣扇丛，存在一個$\overline z$,使得$y=y(z)=alpha_1$，然而在證明的前面部分尉辑，我們已經(jīng)知道了$\overline y=\alpha_1=\xi_1=\xi_2$是不可能的晕拆。
\end{proof}


這個定理的實際意義我們是這樣子說的。如果我們開始時就有初值$x_0>\xi_1$,那么由"雙步法"
\[{x_{k + 1}} = {x_k} - 2\frac{{p({x_k})}}{{p'({x_k})}}\]
產(chǎn)生的值滿足
\[{x_0} \ge {x_1} \ge  \cdots  \ge {x_k} \ge {x_{k + 1}} \ge  \cdots  \ge {\xi _1}\;\;\;\mathop {\lim }\limits_{k \to \infty } {x_k} = {\xi _1}\]
或者呢材蹬，存在一個初值$x_{k_0}:=y$,滿足
\[p({x_0})p(x{}_k) > 0\;\;\;0 \le k < {k_0}\]
\[p({x_k})p({x_{{k_0}}}) < 0\]
在這種情況下实幕，所有的值$p_{x_k}$都是同號的。
\[p({x_0})p(x{}_k) \ge 0\]
$x_k$快速而直接地單調收斂到根$\xi_1$（肯定比直接用牛頓方法快啦)堤器。第二種情況昆庇，
\[{x_0} > {x_1} >  \cdots  > {x_{{k_0} - 1}} > {\xi _1} > y = {x_{{k_0}}} \ge {\alpha _1} \ge {\xi _2}\]
使用$y_0:=y$牛頓方法子序列的新起點
\[{y_{k + 1}} = {y_k} - \frac{{p({y_k})}}{{p'({y_k})}}\;\;\;k = 0,1, \ldots \]
這樣呢，也能夠單調收斂
\[{y_1} \ge {y_2} \ge  \cdots  \ge {\xi _1}\;\;\;\mathop {\lim }\limits_{k \to \infty } {y_k} = {\xi _1}\]

既然已經(jīng)找到了多項式最大的根闸溃，進一步整吆，我們當然是要找到多項式其他的根咯。以下的方法告訴我們可以“除去”已經(jīng)得到的根$\xi_1$辉川。也就是說表蝙，我可以這樣形成一個$n-1$次多項式
\[{p_1}(x): = \frac{{p(x)}}{{x - {\xi _1}}}\]
這個過程稱為"降次"。$p_1(x)$最大的根是$\xi_2$,也可以通過之前描述的方法來得到乓旗。這里的$\xi_1$,或者一個更好的值$y=x_{k_0}$ （通過第一次“過調”得到）府蛇，都可以作為迭代的初值。以此類推屿愚，最后所有的根都可以被找到汇跨。

當然，一般來說妆距，“降次法”也不是十全十美的穷遂。因為舍入誤差會帶來$p_1(x)$一定程度上的磨損。實際上娱据，用來代替$p_1(x)$的多項式有不同于$\xi_2,\xi_3,...,\xi_n$的根蚪黑。沒次使用“降次”都帶來一定誤差，累加起來中剩，最后可能會產(chǎn)生大誤差忌穿，乃至錯誤。當然咽安，如果留心的話伴网，“降次”也能保證數(shù)值上的穩(wěn)定蓬推。除去一個根之后妆棒，降次后的多項式的系數(shù)
\[{p_1}(x) = a_0'{x^{n - 1}} + a_1'{x^{n - 2}} +  \cdots  + a_{n - 1}'\]
可以以順序$a'_0,a'_1,...,a'_{n-1}$(前向降次)，或者以相反的順序（逆向降次）。如果最小絕對值的根被除掉糕珊，那么前者是數(shù)值穩(wěn)定的动分。反之，后者是數(shù)值穩(wěn)定的红选。而混合使用確定系數(shù)的方法澜公，對于絕對值不大不小的根是穩(wěn)定的。詳見 Peters 和 Wilkinson(1971)喇肋。





相對于“降次法”的“零點刪去法”部分翻譯和例子不寫坟乾。
\end{document}