分享@the bisection method 二分逼近法

• Numerical Analysis數值分析筆記
  
• 2.1 The Bisection Method
  
• 練習題組 2.1
  
  

在第2章中，要學習的是  在一個變數下方程式找解，即在 $f(x)=0$，求 $x$。 首先第一個學習的就是 the bisection method 二分逼近法。

• google搜尋「the bisection method 二分逼近法」
  • Bisection method: example 影片

網路上已經有許多分享文章。 the bisection method 二分逼近法 去來求根是根據 Intermediate Value Theorem(IVT) 中間值定理，在高中時期時我們叫它勘根定理。如下

Intermediate Value Theorem(IVT): (詳見其它網頁) 如果函數 $f$ : 

1. 是在區間 $[a,b]$ 連續函數及
   
   
2. $p$ 介於 $f(a)$ 與 $f(b)$ 之間，則
   
   

存在 $c$ 使得 $p=f(c)$。 

由定理可知，連續函數在區間 $[a,b]$ 若 $f(a)f(b)<0$，即區間端點之函數值相乘會小於零，則存在根$p$, i.e., $f(p)=0$，以此定理來尋找函數在此區間的根。而二分逼近法則是把「所尋找的區間以二分(除2)」來作修正/縮小/逼近。若函數 $f$ 在 $a$ $b$ 端點函數值相乘值小於零，則取 $p_1=(a+b)/2$ 為根的近似值，所以我們得到兩個區間$[a, p_1]$ 與 $[p_1, b]$，找出端點函數值，若 $f(a)f(p_1)<0$，則取 $p_2=(a+p_1)/2$，反之，則取 $p_2=(p_1+b)/2$，依此類推下去。

 

bisection method algorithm (詳見課本)

例子 1：

use the bisection method to find $p_3$ for $f(x)=x^3+4x^2-10$ on $[1,2]$. (例子 1 more...) 例子1的題目問題求的是尋找 $p_3$ 即可，但如果今天問題是請尋找誤差小於$10^{-2}$的$p$，此時例子1的求法，可是會遇到困難(不知道要算到多少個才行)，所以，如果可以先解決「要算到第幾個即可」這步，也許會使尋找的過程中安心不少吧！以下的定理提供了這個想法。

 

定理 2.1 (詳見課本)

suppose that $f\in\mathit{C}\left[a,\ b\right]$ and $f(a)f(b)<0$,the Bisection method generates a sequence $\left\{ p_{n}\right\} _{n=1}^{\infty}$approximating a zero $p$ of $f$ with

$\left|p_{n}-p\right|\leq\frac{b-a}{2^{n}}$, when $1\leq n$.

 

例子 2：

  use the Bisection method to find solution accurate to within $10^{-3}$ for the $f(x)=x^{3}+4x^{2}-10=0$ on $\left[1,\ 2\right]$.

Bisection method 在什麼情況下才能使用呢？什麼情況會失效呢？