12.非線性方程的數(shù)值求法-二分法和簡單迭代法.ppt

第七章非線性方程與方程組的數(shù)值解法 引言在科學(xué)研究和工程設(shè)計中 經(jīng)常會遇到的一大類問題是非線性方程f x 0的求根問題 其中f x 為非線性函數(shù) 方程f x 0的根 亦稱為函數(shù)f x 的零點如果f x 可以分解成 其中m為正整數(shù)且 則稱x 是f x 的m重零點 或稱方程f x 0的m重根 當(dāng)m 1時稱x 為單根 若f x 存在m階導(dǎo)數(shù) 則x 是方程f x 的m重根 m 1 當(dāng)且僅當(dāng) 記筆記 當(dāng)f x 不是x的線性函數(shù)時 稱對應(yīng)的函數(shù)方程為非線性方程 如果f x 是多項式函數(shù) 則稱為代數(shù)方程 否則稱為超越方程 三角方程 指數(shù) 對數(shù)方程等 一般稱n次多項式構(gòu)成的方程 為n次代數(shù)方程 當(dāng)n 1時 方程顯然是非線性的一般稍微復(fù)雜的3次以上的代數(shù)方程或超越方程 很難甚至無法求得精確解 本章將介紹常用的求解非線性方程的近似根的幾種數(shù)值解法 記筆記 通常方程根的數(shù)值解法大致分為三個步驟進行 判定根的存在性 即方程有沒有根 如果有根 有幾個根 確定根的分布范圍 即將每一個根用區(qū)間隔離開來 這個過程實際上是獲得方程各根的初始近似值 根的精確化 將根的初始近似值按某種方法逐步精確化 直到滿足預(yù)先要求的精度為止 本章介紹方程的迭代解法 它既可以用來求解代數(shù)方程 也可以用來解超越方程 并且僅限于求方程的實根 運用迭代法求解方程的根應(yīng)解決以下兩個問題 確定根的初值 將進一步精確化到所需要的精度 記筆記 7 1二分法 二分法又稱二分區(qū)間法 是求解非線性方程的近似根的一種常用的簡單方法 設(shè)函數(shù)f x 在閉區(qū)間 a b 上連續(xù) 且f a f b 0 根據(jù)連續(xù)函數(shù)的性質(zhì)可知 f x 0在 a b 內(nèi)必有實根 稱區(qū)間 a b 為有根區(qū)間 為明確起見 假定方程f x 0在區(qū)間 a b 內(nèi)有惟一實根x 二分法的基本思想是 首先確定有根區(qū)間 將區(qū)間二等分 通過判斷f x 的符號 逐步將有根區(qū)間縮小 直至有根區(qū)間足夠地小 便可求出滿足精度要求的近似根 7 1 1確定有根區(qū)間的方法 為了確定根的初值 首先必須圈定根所在的范圍 稱為圈定根或根的隔離 在上述基礎(chǔ)上 采取適當(dāng)?shù)臄?shù)值方法確定具有一定精度要求的初值 對于代數(shù)方程 其根的個數(shù) 實或復(fù)的 與其次數(shù)相同 至于超越方程 其根可能是一個 幾個或無解 并沒有什么固定的圈根方法求方程根的問題 就幾何上講 是求曲線y f x 與x軸交點的橫坐標(biāo) 由高等數(shù)學(xué)知識知 設(shè)f x 為區(qū)間 a b 上的單值連續(xù) 如果f a f b 0 則 a b 中至少有一個實根 如果f x 在 a b 上還是單調(diào)地遞增或遞減 則僅有一個實根 記筆記 由此可大體確定根所在子區(qū)間 方法有 1 畫圖法 2 逐步搜索法 y f x a b y x 1 畫圖法 畫出y f x 的略圖 從而看出曲線與x軸交點的大致位置 也可將f x 0分解為 1 x 2 x 的形式 1 x 與 2 x 兩曲線交點的橫坐標(biāo)所在的子區(qū)間即為含根區(qū)間 例如xlogx 1 0可以改寫為logx 1 x畫出對數(shù)曲線y logx 與雙曲線y 1 x 它們交點的橫坐標(biāo)位于區(qū)間 2 3 內(nèi) 1 畫圖法 0 2 3 y x 對于某些看不清根的函數(shù) 可以擴大一下曲線 1 畫圖法 記筆記 A B 2 逐步搜索法 2 搜索法 對于給定的f x 設(shè)有根區(qū)間為 A B 從x0 A出發(fā) 以步長h B A n n是正整數(shù) 在 A B 內(nèi)取定節(jié)點 xi x0 ih i 0 1 2 n 從左至右檢查f xi 的符號 如發(fā)現(xiàn)xi與端點x0的函數(shù)值異號 則得到一個縮小的有根子區(qū)間 xi 1 xi 例1方程f x x3 x 1 0確定其有根區(qū)間解 用試湊的方法 不難發(fā)現(xiàn)f 0 0在區(qū)間 0 2 內(nèi)至少有一個實根設(shè)從x 0出發(fā) 取h 0 5為步長向右進行根的搜索 列表如下 x f x 00 51 01 52 可以看出 在 1 0 1 5 內(nèi)必有一根 用逐步搜索法進行實根隔離的關(guān)鍵是選取步長h要選擇適當(dāng)h 使之既能把根隔離開來 工作量又不太大 為獲取指定精度要求的初值 可在以上隔離根的基礎(chǔ)上采用對分法繼續(xù)縮小該含根子區(qū)間二分法可以看作是搜索法的一種改進 取有根區(qū)間 a b 之中點 將它分為兩半 分點 這樣就可縮小有根區(qū)間 7 1 2二分法求根過程 設(shè)方程f x 0在區(qū)間 a b 內(nèi)有根 二分法就是逐步收縮有根區(qū)間 最后得出所求的根 具體過程如下 對壓縮了的有根區(qū)間施行同樣的手法 即取中點 將區(qū)間再分為兩半 然后再確定有根區(qū)間 其長度是的二分之一 如此反復(fù)下去 若不出現(xiàn) 即可得出一系列有根區(qū)間序列 上述每個區(qū)間都是前一個區(qū)間的一半 因此的長度 當(dāng)k 時趨于零 這些區(qū)間最終收斂于一點x 即為所求的根 每次二分后 取有根區(qū)間的中點作為根的近似值 得到一個近似根的序列該序列以根x 為極限只要二分足夠多次 即k足夠大 便有這里 為給定精度 由于 則 當(dāng)給定精度 0后 要想成立 只要取k滿足即可 亦即當(dāng) 時 做到第k 1次二分 計算得到的就是滿足精度要求的近似根 在程序中通常用相鄰的與的差的絕對值或與的差的絕對值是否小于 來決定二分區(qū)間的次數(shù) 二分法算法實現(xiàn) 例設(shè)已知 求在區(qū)間 1 5 2 內(nèi)根的近似值 計算結(jié)果列表如下 取 誤差限 例證明方程在區(qū)間 2 3 內(nèi)有一個根使用二分法求誤差不超過0 5 10 3的根要二分多少次 證明令 且f x 在 2 3 上連續(xù) 故方程f x 0在 2 3 內(nèi)至少有一個根 又當(dāng)時 故f x 在 2 3 上是單調(diào)遞增函數(shù) 從而f x 在 2 3 上有且僅有一根 給定誤差限 0 5 10 3 使用二分法時 誤差限為只要取k滿足 即可 亦即 所以需二分10次便可達到要求 二分法的優(yōu)點是不管有根區(qū)間多大 總能求出滿足精度要求的根 且對函數(shù)f x 的要求不高 只要連續(xù)即可 計算亦簡單 它的局限性是只能用于求函數(shù)的實根 不能用于求復(fù)根及重根 7 2不動點迭代法及其收斂性 對于一般的非線性方程 沒有通常所說的求根公式求其精確解 需要設(shè)計近似求解方法 即迭代法 它是一種逐次逼近的方法 用某個固定公式反復(fù)校正根的近似值 使之逐步精確化 最后得到滿足精度要求的結(jié)果 7 2 1迭代法的基本思想為求解非線性方程f x 0的根 先將其寫成便于迭代的等價方程 5 3 其中為x的連續(xù)函數(shù) 即如果數(shù)使f x 0 則也有 反之 若 則也有 稱為迭代函數(shù)任取一個初值 代入式的右端 得到 再將代入式的右端 得到 依此類推 得到一個數(shù)列 其一般表示 式 5 4 稱為求解非線性方程的簡單迭代法 5 4 如果由迭代格式產(chǎn)生的序列收斂 即 則稱迭代法收斂 實際計算中當(dāng)然不可能也沒必要無窮多步地做下去 對預(yù)先給定的精度要求 只要某個k滿足 即可結(jié)束計算并取 當(dāng)然 迭代函數(shù)的構(gòu)造方法是多種多樣的 例 用迭代法求方程在內(nèi)的實根 取 解 對方程進行如下三種變形 建立迭代格式 這是一個發(fā)散的迭代格式 建立迭代格式 該迭代格式收斂 建立迭代格式 該迭代格式收斂 結(jié)論 可見 對的迭代函數(shù) 1 不唯一 2 發(fā)散或收斂 3 收斂的快 慢 下面將討論兩個問題 收斂性和收斂速度 首先 看一下迭代法的幾何意義 迭代法的幾何意義 通常將方程f x 0化為與它同解的方程的方法不止一種 有的收斂 有的不收斂 這取決于的性態(tài) 方程的求根問題在幾何上就是確定曲線y 與直線y x的交點P 的橫坐標(biāo) 圖7 2所示 a b 圖7 2迭代法的幾何意義 7 2 4迭代法的算法框圖 二 收斂條件 定理設(shè)函數(shù)在有限區(qū)間上滿足如下條件 1 當(dāng) 即 2 存在正常數(shù) 對恒成立 則 在上的解存在惟一 產(chǎn)生的序列收斂到 證明 由 1 知 于連續(xù) 令 則 故 在上至少有一個根 現(xiàn)證有唯一根 反之 若 均有 則由 2 有 即 矛盾 現(xiàn)證收斂 記 推論若條件 2 改為在上有界且 則定理1中的結(jié)論成立 例求 在 0 1 內(nèi)的一個實根 將方程化為等價方程 因為 此時定理1中的條件 1 成立 又 所以定理1中條件 2 也成立 對于 0 1 中任意初值 迭代序列 收斂 計算結(jié)果如下表 取 注 方程也可化為等價方程 但此時定理 推論條件不成立 迭代序列不能保證收斂 例5對方程 構(gòu)造收斂的迭代格式 求其最小正根 計算過程保留4位小數(shù) 解容易判斷 1 2 是方程的有根區(qū)間 且在此區(qū)間內(nèi) 所以此方程在區(qū)間 1 2 有且僅有一根 將原方程改寫成以下兩種等價形式 即不滿足收斂條件 即此時迭代公式滿足迭代收斂條件 誤差估計 在上面定理的條件下 有誤差估計式 7 7 證明思路 只需證明下列兩個結(jié)論成立即可 1 證明 兩邊整理后得結(jié)論 2 以下證明 事實上 由 1 即證 存在的困難 的值很難滿足在隔根區(qū)間內(nèi) 7 2 5局部收斂性當(dāng)?shù)瘮?shù)較復(fù)雜時 通常只能設(shè)法使迭代過程在根的鄰域 局部 收斂 定理設(shè)在的根的鄰域中有連續(xù)的一階導(dǎo)數(shù) 且則迭代過程具有局部收斂性 證 由于 存在充分小鄰域 使成立這里L(fēng)為某個定數(shù) 根據(jù)微分中值定理由于 又當(dāng)時 故有由定理1知對于任意的都收斂 例6設(shè) 要使迭代過程局部收斂到 求的取值范圍 解 由在根鄰域具有局部收斂性時 收斂條件 所以 例7已知方程在內(nèi)有根 且在上滿足 利用構(gòu)造一個迭代函數(shù) 使局部收斂于 解 由可得 故 迭代公式 局部收斂 例 用迭代法求方程在內(nèi)的實根 取 解 對方程進行如下三種變形 理論分析 由上述定理知 迭代格式發(fā)散 和計算結(jié)果吻合 理論分析 由定理知 迭代格式收斂 和計算結(jié)果吻合 理論分析 由定理知 迭代格式收斂 和計算結(jié)果吻合 而且 由 5 式知 和 都收斂 但 收斂的效果比 好 收斂速度的粗略判別 值愈小 迭代法收斂得愈快 若 則收斂快 接近于1 則收斂很慢 三 迭代過程的收斂速度 收斂階 定義設(shè)迭代序列 收斂于 階收斂方法 收斂速度的階 判斷迭代方法收斂快慢的重要標(biāo)準(zhǔn) 定理設(shè) 是 的根 于 的鄰域 則只要初始值選得充分接近 迭代方法 階收斂 且有 例8已知迭代公式收斂于證明該迭代公式平方收斂 證 迭代公式相應(yīng)的迭代函數(shù)為 將代入 根據(jù)定理7 3可知 迭代公式平方收斂 為了使迭代過程收斂或提高收斂的速度 可設(shè)法 提高初值的精度以減少迭代的次數(shù) 提高收斂的階數(shù)p 7 3迭代過程的加速 1 加權(quán)法設(shè)是根的某個近似值 用迭代公式校正一次得又根據(jù)中值定理有 其中 當(dāng)范圍不大時 設(shè)變化不大 其估計值為L 則有 可見 若將迭代值與加權(quán)平均 則可得到的 是比更好的近似根 迭代 改進 或合并寫成 例9用加權(quán)法加速技術(shù)求方程在0 5附近的一個根 解 因為在附近取L 0 6 建立如下迭代公式 仍取 逐次計算得 0 56658