第2章 非線性方程(組)的數(shù)值解法1

非線性方程 組 的數(shù)值解法 基礎教學部數(shù)學教研室彭曉華 方程是很多工程和科學工作的發(fā)動機 非線性現(xiàn)象廣泛存在于物質(zhì)世界與社會生活中 在工程和科學計算中 常涉及到非線性方程或非線性方程組的求解問題 例如 2 1引言 1 在光的衍射理論 thetheoryofdiffractionoflight 中 我們需要求x tanx 0的根 2 在行星軌道 planetaryorbits 的計算中 對任意的a和b 我們需要求x asinx b的根 數(shù)值求解方程組的必要性 3 在數(shù)學中 需要求n次多項式 4 在天體力學中 有如下開普勒 Kepler 方程 其中 表示時間 表示弧度 行星運動的軌道 是 的函數(shù) 也就是說 對每個時刻 上述方程 運動軌道位置 超越方程 有唯一解 的根 在非線性方程的求解中 多項式求根是最常見 最簡單的情形 例如想通過矩陣的特征多項式求特征根 就會遇到這一問題 一元二次方程求根公式 一元三次方程求根公式 根據(jù)代數(shù)基本定理 在復數(shù)域內(nèi) n次代數(shù)多項式有且只有n個根 而由伽羅華 Galois 理論 5次以上 含5次 的多項式方程無求根公式 例如求代數(shù)方程 的根 除了多項式求根之外 更多的是超越方程求根問題 超越方程是指包含指數(shù)函數(shù) 三角函數(shù)等特殊函數(shù)的方程 例如前面的幾個例子 又如求解非線性方程組 上述這些問題 都歸結(jié)為尋求非線性函數(shù) 使 稱為方程或方程組 為向量函數(shù)時 的零點 的根或函數(shù) 由于自然現(xiàn)象和實際問題的復雜性 對函數(shù)方程和方程組求解問題 沒有哪一種方法能求出一般方程的準確解 因此 求其數(shù)值解就非常必要了 方程的根 即求 本章目的 介紹用于實際計算中求f x 0的根的近似值的幾種常用方法 主要有 二分法 不動點迭代法 牛頓迭代法 方程根的數(shù)值計算大致可以分為三個步驟 1 判斷根的存在性 2 確定根的分布范圍 根的隔離 3 根的精確化 如果f x 可以分解成 其中m為正整數(shù)且 則稱x 是f x 的m重零點 或稱方程f x 0的m重根 當m 1時稱x 為單根 若f x 存在m階導數(shù) 則x 是方程f x 的m重根 m 1 當且僅當 1 重根 方程求根的理論依據(jù) 設f x 0為復系數(shù)n次代數(shù)方程 則f x 0在復數(shù)域上恰有n個根 m重根按m個計算 若f x 0為實系數(shù)n次代數(shù)方程 則復數(shù)根成對出現(xiàn) 2 代數(shù)基本定理 3 零點定理 設 且 則方程在區(qū)間上至少有一個根 如果在上恒正或恒負 則此根唯一 1 分析法 利用對函數(shù)f x 的各種性質(zhì)的分析來確定根的分布范圍 練習 試確定f x x3 6x2 9x 1 0各根的分布范圍 隔根區(qū)間為 0 1 1 3 3 4 根的隔離 例2 1求方程 的有根區(qū)間 在 內(nèi)連續(xù) 而且 所以 為單調(diào)增加函數(shù) 則 在 內(nèi)最多只有一個實根 又因為 所以 就是所求的有根區(qū)間 解因為 先確定方程f x 0的所有實根所在的區(qū)間 a b 再按照選定的步長h b a n 取點xk a kh k 0 1 2 n 逐步計算函數(shù)值f xk 依據(jù)函數(shù)值異號及實根的個數(shù)確定隔根區(qū)間 必要時可以調(diào)整步長h 總可以把隔根區(qū)間全部找出 2 逐步搜索法 代數(shù)方程根的模上下界定理 例2 2求方程 解根據(jù)有根區(qū)間定義 對 的根進行搜索計算 結(jié)果如表2 1 的有根區(qū)間 由表2 1可知方程的有根區(qū)間為 1 2 3 4 5 6 表2 1逐次搜索計算f x 的符號 得 0 2 4 2即 4 2 0 2 0 2 4 2取n 8 h 0 5 計算f xk 由上表可知隔根區(qū)間為 0 7 0 2 1 2 1 7 1 7 2 2 解 設方程的根為 由 max 3 2 1 9 0 8 3 2 v 1 0 8 max 1 3 2 1 9 4 例2 3 求方程 的隔根區(qū)間 3 圖解法 解因為 在 內(nèi)連續(xù) 要判別 與 例2 4判別方程 有3個實根 方程有3個實根 即要判別 軸有3個 內(nèi)只有一個根 交點 只須判別有3個有根區(qū)間 且每個區(qū)間 由函數(shù)圖像來確定根的大體位置 x 1 0 01 4 y exp x 3 x 2 plot x y r x 0 x gridon 利用MATLAB畫圖來確定有根區(qū)間 由函數(shù)圖1可判別 3個有根區(qū)間分別為 1 0 0 5 1 3 5 4 圖1判別函數(shù)的有根區(qū)間 根的精確化 即求根的方法 二分法迭代法牛頓迭代法 數(shù)值分析 解非線性方程 組 并按下式進行判斷 對于給定的精度要求 用表示方程在區(qū)間上的根 1 取區(qū)間 的中點 對于給定的精度要求 2 2二分法 如此反復二分下去 得到一系列有根區(qū)間 以 作為 的近似值 其絕對誤差 只要二分足夠多次 即k充分大 便有 其中 因此 得到滿足精度所需的二分次數(shù)為 為給定的精度 因而 二分法終止的條件為 表2 2二分計算結(jié)果 二分法算法實現(xiàn) 例2 5求 在區(qū)間 由 內(nèi)的根 要求準確到小數(shù)點后兩位 即 解 二分法的結(jié)果表1所示 二分法的優(yōu)缺點 1 優(yōu)點 算法直觀 簡單 且總能保證收斂 數(shù)值分析 解非線性方程 組 2 缺點 收斂速度較慢 是線性收斂 3 作用 一般不單獨將其用于求根 只用其為根求得一個較好的近似 數(shù)值分析 解非線性方程 組 2 3迭代法及其收斂性 方程的根 2 不動點迭代公式 一 不動點迭代 1 不動點 代入方程 代入方程 則有 稱 為函數(shù) 的不動點 由此確定了相應的迭代法 首先將方程 組 寫成等價的迭代形式 1 稱 為迭代函數(shù) 當 即 的根 這種求得不動點的方法稱為不動點迭代法 數(shù)值分析 解非線性方程 組 求得序列 如果當 時 就是不動點的近似序列 稱為迭代序列 2 稱 為不動點迭代公式 3 時 稱為迭代收斂 為不動點 4 通常將方程f x 0化為與它同解的方程的方法不止一種 有的收斂 有的不收斂 這取決于的性態(tài) 方程的求根問題在幾何上就是確定曲線y 與直線y x的交點P的橫坐標 如圖所示 2 迭代法的幾何意義 數(shù)值分析 解非線性方程 組 迭代法的幾何意義 數(shù)值分析 解非線性方程 組 例2 6 三種迭代結(jié)果見表2 為什么 1 2 發(fā)散 3 收斂 取 正根為 數(shù)值分析 解非線性方程 組 4 構造迭代函數(shù)的方法 表2 3 的迭代例子 問題 如何構造 才能使迭代序列 一定收斂于不動點 近似解的誤差怎樣估計 設迭代公式為 即 而且序列 二 不動點迭代法收斂性 滿足微分中值定理條件時 有 當 顯然只要 時 式 成立 收斂于不動點 因而有 x 分析 定理3 映內(nèi)壓縮性定理 收斂的充分性條件 設方程 在 上存在唯一解 是迭代函數(shù) 如果 1 映內(nèi)性 對任何 稱正數(shù) 則迭代公式 收斂于方程 在 上的唯一根 2 壓縮性 為壓縮因子 且 對任意的初值 并有誤差估計式 2 10 證明 收斂性是顯然的 下面證明誤差估計式 因為 據(jù)此遞推 可得 于是對任意正整數(shù) 有 在上式中令 即得 2 10 式 定理證畢 注意到 對任意正整數(shù) 有 令 則有 注 1 事前誤差估計 對于收斂的迭代序列 2 控制迭代次數(shù) 根據(jù)事前誤差估計公式 2 10 公式 2 10 右端項可用于誤差上限的估計 其中 為取定的迭代次數(shù) 壓縮因子取為 為使近似解達到精度要求 由 2 11 即用前后兩次迭代結(jié)果之差的絕對值是否小于允許誤差來判斷迭代是否終止 也可用于誤差上限的事后估計 3 事后誤差估計 由公式 2 11 可作為迭代算法的終止條件 可得所需要的最少迭代次數(shù)k 即 迭代法的算法框圖 例2 7求方程 的正根 因為是求正根 所以不考慮 所以在 解 解得駐點 令 1 確定有根區(qū)間 內(nèi)有正根 2 選取恰當?shù)牡瘮?shù) 判別根的收斂性 取 由于 所以在 內(nèi)有正根 映內(nèi)性 壓縮性 因此迭代公式 3 迭代計算 迭代公式 必收斂 取初值為 由表2 4可知 x7已達到6位有效數(shù)字 可取1 32472作為所求根的近似值 數(shù)值結(jié)果如表2 4 對于任意的值 1 32472 1 32472 1 32473 1 32476 1 32494 1 32588 1 33086 1 35721 xk 8 7 6 5 4 3 2 1 k 表2 4例5迭代值 數(shù)值分析 解非線性方程 組 若將原方程改寫為 用迭代公式計算 則迭代過程是發(fā)散的 四 局部收斂性與收斂階 1 全局收斂 大范圍收斂 若對 中的任意一點 作初始值 迭代均收斂 這種形式的收斂稱為全局收斂或大范圍收斂 2 局部收斂 若在 的某個鄰域 內(nèi)的每一點 迭代均收斂 稱這種形式的收斂為局部收斂 定理4 局部收斂性 設 在 的鄰近連續(xù) 且 則迭代過程 在 鄰近具有局部收斂性 數(shù)值分析 解非線性方程 組 證明因為 連續(xù) 所以存在 的一個 鄰域 使得對任意 有 成立 并有 即對任意 有 因此 滿足定理3的映內(nèi)壓縮性條件 從而 對任意 迭代過程局部收斂 例2 8求方程 附近的一個根 要求精確到 解將原方程改寫為 在 由于在根附近 選取 迭代公式為 取初值 迭代計算 數(shù)值結(jié)果列于下表 數(shù)值分析 解非線性方程 組 所以局部收斂 迭代到第18次時 0 56711880 56715710 56713540 56714770 5671407 1415161718 0 56843800 56640940 56755960 56690720 56727720 56706730 5671863 78910111213 0 50 60653060 54523920 57970310 56006460 57117210 5648629 0123456 為所求近似根 方程的精確解為 返回例2 11 數(shù)值分析 解非線性方程 組 顯然 這里選取的迭代公式收斂 并且收斂速度較快 注 由例8可知 如果構造的 滿足定理條件 并且使 盡量小 可使迭代計算加速收斂 定義1 收斂階 設迭代過程收斂于的根 記迭代誤差若存在常數(shù)p p 1 和c c 0 使 則稱序列是p階收斂的 c稱漸近誤差常數(shù) 數(shù)p的大小反映了迭代法收斂的速度的快慢 p愈大 則收斂的速度愈快 故迭代法的收斂階是對迭代法收斂速度的一種度量 五 迭代法的收斂速度 特別地 p 1時稱為線性收斂 p 2時稱為平方收斂 1 p 2時稱為超線性收斂 一種迭代法具有實用價值 首先要求它是收斂的 其次還要求它收斂得比較快 例2 9解方程 選取 使迭代計算收斂 并計算根 故取 使 為使收斂速度快 取 使 因此迭代公式為 取初值 迭代計算 數(shù)值結(jié)果如下 解由于根 定理5設迭代過程 若在所求根的鄰域連續(xù)且則迭代過程在鄰域是p階收斂的 證明由于 由定理4可知迭代過程 具有局部收斂性 將 在根 處作泰勒展開 利用條件 2 13 則有 數(shù)值分析 解非線性方程 組 2 13 這表明迭代過程 由上式得 必為階收斂 證畢 由定理5可知 迭代過程的收斂速度依賴于迭代函數(shù) 的選取 如果當 時 則該迭代過程只能是線性收斂 數(shù)值分析 解非線性方程 組 因此對迭代誤差 當 時有 例2 10已知迭代公式收斂于證明該迭代公式平方收斂 數(shù)值分析 解非線性方程 組 證 迭代公式相應的迭代函數(shù)為 所以 該迭代公式平方收斂 1 分析法 利用對函數(shù)f x 的各種性質(zhì)的分析來確定根的分布范圍 1 代數(shù)學基本定理 2 零點定理 一 判定根的存在性及有根區(qū)間的隔離 小結(jié) 2 搜索法 利用代數(shù)方程根的模上下界定理 確定有根區(qū)間 再用搜索法實現(xiàn)有根區(qū)間的分離 3 圖形法 利用函數(shù)的圖形確定函數(shù)零點的 個數(shù)及其分