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

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