分享@數值。Fixed-Point Iteration 固定點疊代法

在第2章中，要學習的是  在一個變數下方程式找解(root-finding problem)，即在 $f(x)=0$，求 $x$。 接下來第二個介紹的是 Fixed-Point Iteration(固定點疊代法)。

什麼是「fixed-point」呢？A number $p$ is a fixed-point for a given function $g$ if $g(p)=p$.

例題1：
the function $g(x)= x^2-2$, for $-2\leqslant x\leqslant3$, has fixed points $x=-1$, $x=-2$.
$g(-1)=(-1)^{2}-2=-1$, $g(2)=(2)^{2}-2=2$.

定理2.2：

(1) if $g\in C[a,\ b]$, and $g(x)\in[a,\ b]$ for all $x\in[a,\ b]$, then $g$ has a fixed point in $[a,\ b]$.

(2) if, in addition, $g^{\prime}(x)$ exists on $(a,b)$ and a positive constant $k<1$ exists with $\left|g^{\prime}(x)\right|\leqslant k$, for all $x\in(a,b)$, then the fixed point in $[a,\ b]$ is unique.

分享@數值。Numerical Analysis 數值分析學習筆記

參考書
R. L. Burden and J. D. Faires, Numerical Analysis, 7 edition, Thomson Brooks/Cole, 2005



建立中…

1. Mathematical Preliminaries
• 1.1 Review of Calculus
• 1.2 Roundoff Errors and Computer Arithmetic
• 1.3 Algorthms and Convergence
• 1.4 Numerical Software
2. Solutions of Equations in One Variable
• 2.1 The Bisection Method
• 2.2 Fixed-Point Iteration
• 2.3 Newton's Method
• 2.4 Error Analysis for Iterative Methods
• 2.5 Accelerating Convergence
• 2.6 Zeros of Polynomials and Muller's Methods
• 2.7 Survey of Methods and Software

整理@文茜的世界財經週報。20131110 日

轉貼文章 20131110文茜的世界財經週報

回整理文章 / >>>詳見網路其它文章


20131110文茜的世界財經週報之1─美政黨鬥爭啟示錄
http://youtu.be/gwg9ZpBzMBY


20131110文茜的世界財經週報之2─美政黨鬥爭啟示錄
http://youtu.be/nFm216lpRoI


20131110文茜的世界財經週報之3─史上強風襲菲
http://youtu.be/K5u7yzi4sxI


20131110文茜的世界財經週報之4─推特真值得投資？
http://youtu.be/ob4msI2GZGw


20131110文茜的世界財經週報之5─半島革命？
http://youtu.be/kolIJWNWiCk

2.1 the besection method 習題組 2.1 NO.4

2.1 the besection method 習題組 2.1 NO.3

2.1 the besection method 習題組 2.1 NO.3

2.1 the besection method 習題組 2.1 NO.5

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

2.1 the besection method 習題組 2.1 NO.4

Numerical Analysis數值分析筆記 /  

2.1 The Bisection Method / 

習題組 2.1 /

NO.4.
use the Bisection method to find solutions accurate to within $10^{-2}$ for $x^{4}-2x^{3}-4x^{2}+x+4=0$ on each interval.

• 第01題 $\left[-2,\ -1\right]$
• 第02題 $\left[0,\ 2\right]$
• 第03題 $\left[2,\ 3\right]$
• 第04題 $\left[-1,\ 0\right]$

>>第01題<< | 第02題 | 第03題 | 第04題

C 語言程式：

1. #include <stdio.h>
2. /*前置處理指命，就是把stdio.h這個檔案(此檔案附於安裝編譯器的子資料夾下)的內容放在原始程式的最開頭*/
3. #include <stdlib.h>
4. /*為了避免結果一閃而過(在windowXP系統下會出現此情形，均需加上此程式)*/
5. #include <math.h>       /**/
6. float f(float x);
7. int main(void)
8. { 
9.     int i=0,N=100;
10.     float a=-2,b=-1,p=0.0,FA=0.0,FP=0.0;
11.     float TOL=0.00001;
12.     printf("n      an              bn              pn              f(pn)\n");
13.     /*Step1*/
14.     i=1;
15.     FA=f(a);
16.     /*Step2*/
17.     while(i<=N)
18.     {    /*Step3*/
19.          p=a+(b-a)/2;
20.          FP=f(p);
21.     printf("%2d    %+.9f    %+.9f    %+.9f    %+.9f\n",i,a,b,p,f(p));    
22.          /*Step4*/
23.          if(FP==0 || (b-a)/2<TOL)
24.          {printf("n=%d, p=%+f\n",i,p);break;}
25.          /*Step5*/
26.          i=i+1;
27.          /*Step6*/
28.          if(FA*FP>0){a=p;FA=FP;}
29.          else b=p;
30.          }
31.     printf("method failed after N=%d iterations.",N);
32.     /*Step*/
33.     /*Step*/
34.     /*Step*/
35. system("PAUSE"); /*為了避免結果一閃而過(在windowXP系統下會出現此情形，均需加上此程式)*/
36. return 0;       
37.    }
38. float f(float x)
39. {
40.       return pow(x,4)-2*pow(x,3)-4*pow(x,2)+4*x+4;
41.       }

C 語言程式執行結果： 

>>第01題<< | 第02題 | 第03題 | 第04題

2.1 the besection method 習題組 2.1 NO.3

Numerical Analysis數值分析筆記 /  

2.1 The Bisection Method / 

習題組 2.1 /

NO. 3.
use the Bisection method to find solutions accurate to within $10^{-2}$ for $x^{3}-7x^{2}+14x-6=0$ on each interval.

• 第01題 $\left[0,\ 1\right]$.
• 第02題 $\left[1,\ 3.2\right]$.
• 第03題 $\left[3.2,\ 44\right]$.

>>第01題<< | 第02題 | 第03題

C語言程式：

1. #include <stdio.h>
2. /*前置處理指命，就是把stdio.h這個檔案(此檔案附於安裝編譯器的子資料夾下)的內容放在原始程式的最開頭*/
3. #include <stdlib.h>
4. /*為了避免結果一閃而過(在windowXP系統下會出現此情形，均需加上此程式)*/
5. #include <math.h>       /**/
6. float f(float x);
7. int main(void)
8. { 
9.     int i=0,N=100;
10.     float a=0,b=1,p=0.0,FA=0.0,FP=0.0;
11.     float TOL=0.00001;
12.     printf("n    an            bn            pn            f(pn)\n");
13.     /*Step1*/
14.     i=1;
15.     FA=f(a);
16.     /*Step2*/
17.     while(i<=N)
18.     {    /*Step3*/
19.          p=a+(b-a)/2;
20.          FP=f(p);
21.     printf("%2d    %+.9f    %+.9f    %+.9f    %+.9f\n",i,a,b,p,f(p));    
22.          /*Step4*/
23.          if(FP==0 || (b-a)/2<TOL)
24.          {printf("n=%d, p=%+f\n",i,p);break;}
25.          /*Step5*/
26.          i=i+1;
27.          /*Step6*/
28.          if(FA*FP>0){a=p;FA=FP;}
29.          else b=p;
30.          }
31.     printf("method failed after N=%d iterations.",N);
32.     /*Step*/
33.     /*Step*/
34.     /*Step*/
35. system("PAUSE"); /*為了避免結果一閃而過(在windowXP系統下會出現此情形，均需加上此程式)*/
36. return 0;       
37.    }
38. float f(float x)
39. {
40.       return pow(x,3)-7*pow(x,2)+14*x-6;
41.       }

C語言程式執行結果：


 

>>第01題<< | 第02題 | 第03題 

2.1 the besection method 習題組 2.1 NO.2

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

NO.2.
$f(x)=3(x+1)(x-\frac{1}{2})(x-1)$. Use the Bisection method on the following intervals to find $p_{3}$.

• $\left[-2,\ 1.5\right]$

執行結果：

 

• $\left[-1.25,\ 2.5\right]$

執行結果：

好像有算錯了^__^

2.1 the besection method 習題組 2.1 NO.1

Numerical Analysis數值分析筆記 / 

2.1 The Bisection Method /

習題組 2.1 /

NO.1.
use the bisetion method to find the $p_3$ for $f(x)=\sqrt{x}-\cos x$ on $[0,1]$.

C 程式語言：

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <math.h>       /**/
4. float f(float x);
5. int sig(float v);
6. int main(void)
7. { 
8.     int i=0,N=100;
9.     float a=0.0,b=1.0,p=(a+b)/2,FA=0.0,FP=0.0;
10.     float TOL=0.00001;
11.    
12.     printf("n  an         bn         pn         f(pn)\n");
13.     /*Step1*/
14.     i=1;
15.     FA=f(a);
16.    
17.     /*Step2*/
18.     while(i<=N)
19.     {    /*Step3*/
20.          p=a+(b-a)/2;
21.          FP=f(p);
22.         
23.     printf("%2d  %.9f  %.9f  %.9f  %+.9f\n",i,a,b,p,f(p));    
24.         
25.          /*Step4*/
26.          if(FP==0 || (b-a)/2<TOL)
27.          {printf("n=%d, p=%+f\n",i,p);break;}
28.         
29.          /*Step5*/
30.          i=i+1;
31.         
32.          /*Step6*/
33.          if(sig(FA)*sig(FP)>0){a=p;FA=FP;}
34.          else b=p;
35.          }
36.     printf("method failed after N=%d iterations.",N);
37.    
38.    
39.    
40. system("PAUSE");
41. return 0;       
42.    }
43.   
44.   
45. float f(float x)
46. {
47.       return sqrt(x)-cos(x);
48.       }
49.      
50. int sig(float u)
51. {   
52.      if(u>0){return 1;}
53.      else if(u<0){return -1;}
54.      else {return 0;}
56.      }

c語言執行結果：

 

整理@GoodTV 科學與聖經

空中主日學(goodtv)
門徒造就／科學與聖經
講員：蘇緋雲博士
聖經與科學有衝突嗎？
人是猴子變的嗎？
山頂洞人的真相是什麼？
幾顆牙齒可以變出一個人合理嗎？恐龍上得了方舟嗎？
擁有化學及生物化學雙博士學位的蘇緋雲博士，用中肯、科學研究者的眼光，來說明這些大家常常感到困惑的問題。
您對科學與聖經有很多疑問嗎？
這個系列您一定不可錯過


空中主日學~
科學與聖經(1)~起初<<<<<<<<<<<<<<從第1章開始看吧！ 


空中主日學~科學與聖經(2)~各從其類 

空中主日學~科學與聖經(3)~化石也是各從其類

空中主日學~科學與聖經(4)~越變越好嗎 

空中主日學~科學與聖經(5)~外衣會舊嗎

空中主日學~科學與聖經(6)~不死不生（一） 

空中主日學~科學與聖經(7)~不死不生（二）

空中主日學~科學與聖經(8)~化石幾歲?(上) 

空中主日學~科學與聖經(9)~化石幾歲?(中) 

空中主日學~科學與聖經(10)~化石幾歲?(下) 

空中主日學~科學與聖經(11)~化石的年代 

空中主日學~科學與聖經(12)~創造或進化 

空中主日學~科學與聖經(13)~北京猿人 

空中主日學~科學與聖經(14)~上帝的形像 

空中主日學~科學與聖經(15)~其他猿人

空中主日學~科學與聖經(16)~男人角色

空中主日學~科學與聖經(17)~婚姻家庭 

空中主日學~科學與聖經(18)~夫妻親子

空中主日學~科學與聖經(19)~社會問題

空中主日學~科學與聖經(20)~真有恐龍嗎

空中主日學~科學與聖經(21)~恐龍絕種了嗎

空中主日學~科學與聖經(22)~恐龍見過人嗎

空中主日學~科學與聖經(23)~恐龍為什麼這麼大 

空中主日學~科學與聖經(24)~洪水三部曲

空中主日學~科學與聖經(25)~火山的啟示 

空中主日學~科學與聖經(26)~恐龍上了方舟嗎？

空中主日學~科學與聖經(27)~化石的教訓

EXERCISE SET 2.1

Numerical Analysis數值分析筆記 /  

2.1 The Bisection Method /  

習題組 2.1 /

NO.1.(more...)
use the bisetion method to find the $p_3$ for $f(x)=\sqrt{x}-\cos x$ on $[0,1]$.


NO.2.(more...)
$f(x)=3(x+1)(x-\frac{1}{2})(x-1)$. Use the Bisection method on the following intervals to find $p_{3}$.

• $\left[-2,\ 1.5\right]$ 
• $\left[-1.25,\ 2.5\right]$ 

NO.3.(more...)
use the Bisection method to find solutions accurate to within $10^{-2}$ for $x^{3}-7x^{2}+14x-16=0$ on each interval.

• $\left[0,\ 1\right]$
• $\left[1,\ 3.2\right]$
• $\left[3.2,\ 4\right]$

NO.4.(more...)
use the Bisection method to find solutions accurate to within $10^{-2}$ for $x^{4}-2x^{3}-4x^{2}+x+4=0$ on each interval.

• $\left[-2,\ -1\right]$
• $\left[0,\ 2\right]$
• $\left[2,\ 3\right]$
• $\left[-1,\ 0\right]$

NO.5.(more...)
use the Bisection method to find solutions accurate to within $10^{-5}$ for the following problems.

• $x-2^{-x}=0$ for $0\leq x\leq 1$
• $e^{x}-x^2+3x-2=0$ for $0\leq x\leq 1$
• $x2\cos(2x)-(x+1)^{2}=0$ for $-3\leq x\leq-2$ and $-1\leq x\leq0$
• $x\cos x-2x^{2}+3x-1=0$ for $0.2\leq x\leq0.3$ and $1.2\leq x\leq1.3$

NO.6.(more...) 
use the Bisection method to find solutions accurate to within $10^{-5}$ for the following problems.

• $3x-e^{x}=0$ for $1\leq x\leq2$
• $x+3\cos x-e^{x}=0$ for $0\leq x\leq1$
• $x^{2}-4x+4-\ln x=0$ for $1\leq x\leq2$ and $2\leq x\leq4$
• $x+1-2\sin\pi$x=0 for $0\leq x\leq0.5$ and $0.5\leq x\leq1$

NO.7.(more...)

sketch the graphs of $y=x$ and $y=2\sin x$. use the bisection method to find an  approximation to within $10^{-5}$ to the first positive value of $x$ with $x=2\sin x$.

NO.8.(more...)

sketch the graphs of $y=x$ and $y=\tan x$. use the bisection method to find an  approximation to within $10^{-5}$ to the first positive value of $x$ and $y=\tan x$.

NO.9.(more...)

sketch the graphs of $y=e^{x}-2$ and $y=\cos(e^{x}-2)$.  use the bisection method to find an approximation to within $10^{-5}$ to a value in $\left[0.5,\ 1.5\right]$  with $e^{x}-2=\cos(e^{x}-2)$.

NO.10.(more...)

let $f(x)=(x+2)(x+1)^{2}x(x-1)^{3}(x-2)$, to which zero of $f$ does the bisection method converge when applied on the following intervals?

• $\left[-1.5,\ 2.5\right]$  
• $\left[-0.5,\ 2.4\right]$ 
• $\left[-0.5,\ 3\right]$  
• $\left[-3,\ -0.5\right]$

NO.11.(more...)

let $f(x)=(x+2)(x++1)x(x-1)^{3}(x-2)$, to which zero of $f$ does the bisection method converge when applied on the following intervals?

• $\left[-3,\ 2.5\right]$  
• $\left[-2.5,\ 3\right]$
• $\left[-1.75,\ 1.5\right]$  
• $\left[-1.5,\ 1.75\right]$

NO.12.(more...)

find an approximation to $\sqrt{3}$ correcto within $10^{-4}$ using the bisection algorithm. hint: consider $f(x)=x^{2}-3$.

NO.13.(more...)

find an approximation to $\sqrt[3]{25}$ correct to within $10^{-4}$ using the bisection algorithm.

NO.14.(more...)

use theorem 2.1 to find a bound for the number of iterations needed to achieve an approximation with accuracy $10^{-3}$ to the solution of $x^{3}+x-4=0$ lying in the interval $\left[1,\ 4\right]$, find an approximation to the root with this degree of accuracy.

NO.15.(more...)

use theorem 2.1 to find a bound for the number of iterations needed to achieve an approximation with accuracy $10^{-4}$ to the solution of $x^{3}-x-1=0$ lying in the interval $\left[1,\ 2\right]$, find an approximation to the root with this degree of accurracy.

NO.16.(more...)

NO.17.(more...)

NO.18.(more...)

NO.19.(more...)

NO.20.(more...)

the bisection method 二分逼近法 例子1

例子 1：
use the bisection method to find $p_3$ for $f(x)=x^3+4x^2-10$ on $[1,2]$.

首先說明其有根：
因為函數 $f$ 在 $[1,2]$ 連續，且 $f(1)f(2)<0$，由 IVT 可知函數 $f$ 在 $[1,2]$ 中有根。

接者尋找 $p_3$ :

1. $a_1=1$, $b_1=2$,  則 $p_1=\frac{1}{2}(1+2)=\frac{3}{2}$.

2. $a_2=1$, $b_2=p_1=\frac{3}{2}$,  則 $p_2=\frac{5}{4}$.

3. $a_3=p_2=\frac{5}{4}$, $b_3=\frac{3}{2}$,  則 $p_3=\frac{1}{2}(\frac{5}{4}+\frac{3}{2})$.

 

using c language：

1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <math.h>       /**/
4. float f(float u);
5. int sig(float v);
6. int main(void)
7. { 
8.     int i=0,N=10000;
9.     float a=1.0,b=2.0,p=1.5,FA=0.0,FP=0.0;
10.     float TOL=0.0000001;
11.    
12.     printf("n   an          bn              pn             f(pn)\n");
13.     /*Step1*/
14.     i=1;
15.     FA=f(a);
16.    
17.     /*Step2*/
18.     while(i<=N)
19.     {    /*Step3*/
20.          p=a+(b-a)/2;
21.          FP=f(p);
22.         
23.     printf("%2d    %.9f    %.9f    %.9f    %+.9f\n",i,a,b,p,f(p));    
24.         
25.          /*Step4*/
26.          if(FP==0 || (b-a)/2<TOL)
27.          {printf("n=%d, p=%+f\n",i,p);break;}
28.         
29.          /*Step5*/
30.          i=i+1;
31.         
32.          /*Step6*/
33.          if(sig(FA)*sig(FP)>0){a=p;FA=FP;}
34.          else b=p;
35.          }
36.     printf("method failed after N=%d iterations.",N);
37.    
38.  
39.    
40. system("PAUSE");
41. return 0;       
42.    }
43.   
44.   
45. float f(float u)
46. {
47.       return u*u*u+4*u*u-10;
48.       }
49.      
50. int sig(float u)
51. {   
52.      if(u>0){return 1;}
53.      else if(u<0){return -1;}
54.      else 0; 
55.      }

其執行結果：

當 $n=3$, 則 $p_3=1.375$.