數值計算和最優(yōu)化lecture誤差和二分法

由上面討論能夠看出，為了求得滿意計算解，在選用計算公式和設計算法時，都應注意以下普遍標準：(1)預防大數吃小數主要由計算機位數引發(fā)選取算法應遵照標準計算機中數計算特點：加法先對階，后運算，再舍入。乘法先運算，再舍入。不在計算機數系中數做四舍五入處理。數值計算和最優(yōu)化lecture誤差和二分法第1頁作一個有效數字為4位連加運算而假如將小數放在前面計算在作連加時，為預防大數吃小數，應從小到大進行相加，如此，精度將得到適當改進。當然也可采取別方法。例數值計算和最優(yōu)化lecture誤差和二分法第2頁(2)作減法時應防止兩個相近數相減兩個相近數相減，會使有效數字位數嚴重損失！例1.2.10用四位浮點數計算

解只有一位有效數字,有效數字大量損失，造成相對誤差擴大。結果依然有四位有效數字。這說明了算法設計主要性。在算法設計中，若可能出現兩個相近數相減，則改變計算公式，如使用三角變換、有理化等等。數值計算和最優(yōu)化lecture誤差和二分法第3頁(3)防止小數作除數和大數作乘數小數作除數或大數作乘數會產生溢犯錯誤，因而產生大誤差。在算法設計時，要防止這類情況在計算公式中出現。此時能夠依據一些詳細情況,把一些算式改寫成另一個等價形式，如分母有理化等。依據誤差傳輸預計式數值計算和最優(yōu)化lecture誤差和二分法第4頁§3.算法穩(wěn)定性如前所述，因為各種誤差存在，計算機往往只能近似地求解實際問題，因而計算時會冒風險。一、問題性態(tài)數值計算和最優(yōu)化lecture誤差和二分法第5頁如把方程組系數舍入成兩位有效數字它準確解為x1=-6.222...x2=38.25…x3=-33.65...例求解線性方程組其準確解為x1=x2=x3=1.數值計算和最優(yōu)化lecture誤差和二分法第6頁若對方程組系數和中間結果均取3位10進制有效數字，然后用Gauss消元法求解，得到計算解為：顯然，該計算解精度較差。一樣用Gauss消元法求解方程組：也取3位10進制有效數字，得到計算解為：輕易驗證，它是方程組準確解。數值計算和最優(yōu)化lecture誤差和二分法第7頁上述例子表明，數值問題計算解精度，與數值問題本身性態(tài)相關。定義1.3.1在數值問題中，假如輸出數據對輸入數據擾動（如誤差）很敏感，即若輸入數據（如原始數據）有較小改變，會引發(fā)輸出數據（如計算解）較大變化，稱這類數值問題為病態(tài)問題或壞條件問題。非病態(tài)問題又稱為良態(tài)問題。問題輸出變量相對誤差與輸入變量相對誤差商稱為問題條件數數值計算和最優(yōu)化lecture誤差和二分法第8頁二、算法穩(wěn)定性與設計標準例1.3.3計算定積分解一個程序往往要進行大量四則運算才能得出結果，每一步運算均可能會產生舍入誤差。在大量計算中,舍入誤差是積累還是能控制,這與算法相關。數值計算和最優(yōu)化lecture誤差和二分法第9頁誤差放大5千倍!并假設計算過程中不產生新舍入誤差。誤差會放大由公式可推出：數值計算和最優(yōu)化lecture誤差和二分法第10頁顯然算法不穩(wěn)定。理論上成立算法，在計算機上計算時，因為初值誤差在計算過程中傳輸，而造成結果失真，這是我們數值計算方法所要研究。(2)利用遞推公式誤差不會放大數值穩(wěn)定，在運算過程中，舍入誤差不增大。

數值計算和最優(yōu)化lecture誤差和二分法第11頁定義1.3.2假如對于良態(tài)問題，在運算過程中,舍入誤差能控制在某個范圍內算法稱之為數值穩(wěn)定算法,不然就稱之為不穩(wěn)定算法。前面例子說明，不穩(wěn)定算法可能造成計算結果不可靠甚至嚴重失真。所以，在計算時，應該采取穩(wěn)定數值計算方法。數值計算和最優(yōu)化lecture誤差和二分法第12頁算法優(yōu)劣標準從截斷誤差觀點看，算法必須是截斷誤差小，收斂速速要快。即運算量小，機器用時少。從舍入誤差觀點看，舍入誤差在計算過程中要能控制，即算法數值要穩(wěn)定。從實現算法觀點看，算法邏輯結構不宜太復雜，便于程序編制和上機實現.數值計算和最優(yōu)化lecture誤差和二分法第13頁設計算法時應遵照標準要含有數值穩(wěn)定性，即能控制誤差傳輸。防止大數吃小數，即兩數相加時，預防較小數加不到較大數上。防止兩相近數相減，以免有效數字大量丟失。防止分母很小或乘法因子很大，以免產生溢出。數值計算和最優(yōu)化lecture誤差和二分法第14頁非線性方程求根第二章數值計算和最優(yōu)化lecture誤差和二分法第15頁當代科學技術或工程技術領域許多實際問題，經常能夠歸結為求解函數方程：假如函數能寫成以下形式假如有使得，則稱為方程根，或稱為函數零點。數值計算和最優(yōu)化lecture誤差和二分法第16頁如：①當f(x)為代數方程時，理論上已經證實，大于五次多項式普通沒有代數解法。②當f(x)為超越方程時，普通不能用代數方法求其根。

所以，超越方程(含有指數和對數等)代數方程（多項式）對于普通非線性方程，只能用數值方法求解。數值計算和最優(yōu)化lecture誤差和二分法第17頁方程求根問題分成兩步：第二步：根隔離確定根所在區(qū)間，使方程在這個小區(qū)間內僅有一個根，該區(qū)間叫隔根區(qū)間。第三步：根準確化已知根一個近似值后，用某種方法對其進行加工，使之滿足給定精度要求。第一步：根存在性數值計算和最優(yōu)化lecture誤差和二分法第18頁求隔根區(qū)間普通方法理論依據：數值計算和最優(yōu)化lecture誤差和二分法第19頁本章主要介紹二分法與迭代法（包含Newton迭代法及其變型、弦割法等）§1.二分法二分法是方程求根最慣用而且也是最保險方法之一。一、算法基本思想將區(qū)間對分，保留有根區(qū)間，舍去無根區(qū)間。如此往復，以逐步迫近方程根。基本條件：數值計算和最優(yōu)化lecture誤差和二分法第20頁二、算法步驟數值計算和最優(yōu)化lecture誤差和二分法第21頁ax0ba1b1三、算法收斂性此時有誤差預計：慣用來預計k值數值計算和最優(yōu)化lecture誤差和二分法第22頁四、算法優(yōu)點與缺點缺點：不能求偶數重根及復根；收斂速度非常遲緩，與以1/2為公比等比級數相同；沒有充分利用函數值。所以普通不單獨使用，往往為其它快速方法提供初值。優(yōu)點：計算簡單且必收斂，是一個可靠算法；對函數性質要求低，只要求函數f(x)連續(xù)就能夠了。用二分法求方程

在[1,1.5]內實根，要求

解即可推出所需迭代次數滿足

在區(qū)間[1,1.5]上最少存在一個根。其詳細過程以下：

例2.1.1因為因而由誤差預計式數值計算和最優(yōu)化lecture誤差和二分法第23頁

符號011.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51