2013年12月19日 星期四

分享@數值。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

2013年11月10日 星期日

整理@文茜的世界財經週報。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







2013年4月26日 星期五

2.1 the besection method 習題組 2.1 NO.5

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

2.1 NO.05a_01
2.1 NO.05b_01

2013年4月25日 星期四

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題

2.1 NO.04a_01
2.1 NO.04a_02
2.1 NO.04a_03
2.1 NO.04a_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.     int i=0,N=100;
  9.     float a=-2,b=-1,p=0.0,FA=0.0,FP=0.0;
  10.     float TOL=0.00001;
  11.     printf("n      an              bn              pn              f(pn)\n");
  12.     /*Step1*/
  13.     i=1;
  14.     FA=f(a);
  15.     /*Step2*/
  16.     while(i<=N)
  17.     {    /*Step3*/
  18.          p=a+(b-a)/2;
  19.          FP=f(p);
  20.     printf("%2d    %+.9f    %+.9f    %+.9f    %+.9f\n",i,a,b,p,f(p));    
  21.          /*Step4*/
  22.          if(FP==0 || (b-a)/2<TOL)
  23.          {printf("n=%d, p=%+f\n",i,p);break;}
  24.          /*Step5*/
  25.          i=i+1;
  26.          /*Step6*/
  27.          if(FA*FP>0){a=p;FA=FP;}
  28.          else b=p;
  29.          }
  30.     printf("method failed after N=%d iterations.",N);
  31.     /*Step*/
  32.     /*Step*/
  33.     /*Step*/
  34. system("PAUSE"); /*為了避免結果一閃而過(在windowXP系統下會出現此情形,均需加上此程式)*/
  35. return 0;       
  36.    }
  37. float f(float x)
  38. {
  39.       return pow(x,4)-2*pow(x,3)-4*pow(x,2)+4*x+4;
  40.       }

C 語言程式執行結果: 


2.1  BisectionNO.4a


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




2013年4月24日 星期三

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]$.

2.1 NO.03a_01

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.     int i=0,N=100;
  9.     float a=0,b=1,p=0.0,FA=0.0,FP=0.0;
  10.     float TOL=0.00001;
  11.     printf("n    an            bn            pn            f(pn)\n");
  12.     /*Step1*/
  13.     i=1;
  14.     FA=f(a);
  15.     /*Step2*/
  16.     while(i<=N)
  17.     {    /*Step3*/
  18.          p=a+(b-a)/2;
  19.          FP=f(p);
  20.     printf("%2d    %+.9f    %+.9f    %+.9f    %+.9f\n",i,a,b,p,f(p));    
  21.          /*Step4*/
  22.          if(FP==0 || (b-a)/2<TOL)
  23.          {printf("n=%d, p=%+f\n",i,p);break;}
  24.          /*Step5*/
  25.          i=i+1;
  26.          /*Step6*/
  27.          if(FA*FP>0){a=p;FA=FP;}
  28.          else b=p;
  29.          }
  30.     printf("method failed after N=%d iterations.",N);
  31.     /*Step*/
  32.     /*Step*/
  33.     /*Step*/
  34. system("PAUSE"); /*為了避免結果一閃而過(在windowXP系統下會出現此情形,均需加上此程式)*/
  35. return 0;       
  36.    }
  37. float f(float x)
  38. {
  39.       return pow(x,3)-7*pow(x,2)+14*x-6;
  40.       }

C語言程式執行結果:


2.1  BisectionNO.3a 

2013年4月11日 星期四

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]$
2.1 NO.02_012.1 NO.02_02

執行結果:

2.1  BisectionNO.2a 
  • $\left[-1.25,\ 2.5\right]$

2.1 NO.02_03

執行結果:
2.1  BisectionNO.2b

好像有算錯了^__^

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]$.


2.1 NO.01


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

    c語言執行結果:

     2.1  BisectionNO.1

    2013年3月3日 星期日

    整理@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})$.
     
    000

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

    其執行結果:

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

     
    example1

    教學用,若不慎侵犯絕非故意,請留言通知必於第一時間移除,謝謝。