程式設計科學/峰值與谷值

根據 CME，要找到具有自變數x的曲線的極小值或極大值，你需要求導，將導數設為零，然後解出x。在該點，原函式的斜率為零，因此必須是峰值上的最高點或谷值中的最低點。正如 CME 所說，你無法確定零斜率代表峰值還是谷值，但它必須是其中之一。

求解x的過程非常類似於簡化表示式的過程；這是一個超出本文範圍的複雜任務。因此，我們將無法象徵性地找到極小值/極大值。但是，由於艾薩克·牛頓爵士，我們將能夠以數值方式執行此任務。

在本章的其餘部分，我們將放棄我們的面向物件方法，並採用函式式方法，因為使用物件的目的就是執行符號任務。將我們以前的面向物件方法改編為執行數值任務（例如查詢極小值/極大值）被留作練習。

來自過去的爆炸

首先，我們必須學習如何將多項式及其導數表示為數值 Sway 函式。還記得我們在第 3 章和第 4 章中的比率函式嗎？我們用它來計算 ${\frac {dy}{dx}}$ 的數值。

   function ratio(x,dx,y)
       {
       var dy = y(x + dx) - y(x);
       dy / dx;
       }

在 Sway 中，我們不僅可以從函式中返回數字、字串和環境（物件），我們還可以返回函式本身。我們將使用這個事實來構建數值導數函式。

---

此時，你應該閱讀 Sway 參考手冊中關於 返回區域性函式 的內容。

---

因此，與其使用需要我們一遍又一遍地傳入相同y函式的比率函式，我們不如定義一個函式來返回一個自定義的比率，該比率只接受x值作為引數。看看程式碼將有很大幫助。

   function derivative(y,dx)
       {
       function ratio(x)
           {
           var dy = y(x + dx) - y(x);
           dy / dx;
           }
       }

由於derivative函式中的最後一個表示式是ratio的定義，因此它是ratio函式作為derivative的返回值。現在，我們可以將x值傳遞給原始函式及其導數。

與往常一樣，讓我們使用這個多項式作為實驗物件進行測試。

   $3x^{2}-10x+5$

將這個多項式以數值方式表示為 Sway 函式，我們有

   function y(x)
       {
       3 * (x ^ 2) - (10 * x) + 5;
       }
     
   var y' = derivative(y,0.000001);

我們預計y的符號導數為

   $6x-10$

因此，我們預計y(2)將產生 -3，以及y'(2)將產生 2。

   sway> y(2);
   INTEGER: -3
   sway> y'(2);
   REAL_NUMBER: 2.0000029988

第二個結果中的不精確度再次歸因於使用實數而不是整數。^[1]

一個好的固定點

在數值上查詢極小值/極大值的下一步是能夠找到函式的固定點。如果一個函式有一個固定點（並非所有函式都有），那麼存在一個值x，使得

   $f(x)=x$

例如，餘弦函式在約 0.7390851332 處有一個固定點。

   sway> cos(0.7390851332);
   REAL_NUMBER: 0.7390851332

我說約是因為 Sway 預設情況下不會顯示所有有效數字。

查詢固定點在演算法上很簡單。

   function fixedPoint(f,x)
       {
       if (f(x) == x)
           {
           x;
           }
       else
           {
           fixedPoint(f,x + f(x) / 2);
           }
       }

如果對於給定的x，$f(x)!=x$，我們嘗試使用新的x值再次進行。方便的是，x 和 $f(x)$ 的平均值是我們的下一次嘗試的數學上合理的數值。

雖然這段程式碼很好地說明了這種方法，但它也有一些問題。第一個問題是 f(x) 被計算了兩次。為了提高效率，我們應該只計算一次。

   function fixedPoint(f,x)
       {
       var next = f(x);
       if (next == x)
           {
           x;
           }
       else
           {
           fixedPoint(f,x + next / 2);
           }
       }

下一個問題是由於 Sway 中實數的精度有限。由於實數無法精確表示，因此通常不建議在實數精度極限的情況下進行相等比較。因此，除非你確切地知道（而在 fixedPoint 的情況下，你不確切地知道），否則你應該檢查數字是否在某個很小的範圍內。

   var FIXED_POINT_DELTA = 1e-10;

   function fixedPoint(f,x)
       {
       var next = f(x);
       if (abs(x - next) < FIXED_POINT_DELTA)
           {
           x;
           }
       else
           {
           fixedPoint(f,x + next / 2);
           }
       }

使用abs（絕對值）函式是因為x - next可能是一個很大的負值，這也將小於 $1*10^{-10}$。^[2]

在呼叫fixedPoint時，我們需要一個x的初始值。事實證明，1.0 幾乎總是好的猜測，所以讓我們硬編碼它。這裡有一個很巧妙的技巧。

   function fixedPoint(f)
       {
       function helper(f,x)
           {
           var next = f(x);
           if (abs(x - next) < FIXED_POINT_DELTA)
               {
               x;
               }
           else
               {
               helper(f,x + next / 2);
               }
           }
       helper(f,1.0);
       }

這個技巧的本質是將你想為其固定某些引數的函式重新命名為一個好的名稱，比如helper。^[3] 然後，你使用具有原始名稱的函式包裝該函式，使helper成為一個區域性函式。然後，你在包裝函式中做的最後一件事是呼叫 helper，固定所需引數的值。

我們可以透過注意到fixedPoint' 的形式引數f繫結到與helper' 的形式引數f相同的值來改進最新版本，因此我們可以在定義和呼叫中刪除helper' 的版本。

   function fixedPoint(f)
       {
       function helper(x)
           {
           var next = f(x);
           if (abs(x - next) < FIXED_POINT_DELTA)
               {
               x;
               }
           else
               {
               helper(x + next / 2);
               }
           }
       helper(1.0);
       }

不要忘記更改遞迴呼叫。

牛頓的變換

牛頓提出了一種巧妙的方法來找出多項式（以及其他可微函式）在哪裡具有零值。他說，某個函式f 的零點也是從f 派生的新函式的固定點。這個新函式，$f_{NT}$，是

   $f_{NT}(x)=x-{\frac {f(x)}{f\,'(x)}}$

因此，要找到某個函式的零點，我們使用牛頓變換生成一個新函式，並將變換後的函式傳遞給我們的固定點查詢器。它返回的值就是我們的零點！

首先，讓我們實現牛頓變換。

   function NewtonsTransform(f)
       {
       var f' = derivative(f,0.000001);
       function y(x)
           {
           x - (f(x) / f'(x));
           }
       }

現在讓我們測試我們的多項式。

   $y=3x^{2}-10x+5$

我們使用 Sway 函式實現它，與以前一樣，並建立導數函式。

   function y(x)
       {
       3 * (x ^ 2) - (10 * x) + 5;
       }
     
   var y' = derivative(y,0.000001);

函式y在哪裡產生零點？

   sway> fixedPoint(NewtonsTransform(y));
   REAL_NUMBER: 0.6125741133
   sway> y(0.6125741133);
   REAL_NUMBER: -1.441567e-10

考慮到我們固有的不精確度，0.6125741133 似乎確實接近y 的零點。y' 呢？

   sway> fixedPoint(NewtonsTransform(y));
   REAL_NUMBER: 1.6666661669
   sway> y(1.6666661669);
   REAL_NUMBER: 1.776357e-09

同樣，對於政府工作來說足夠接近零。

問題

1. 修改符號系統以處理數值導數。為了使數值導數相容，derivative函式應該返回一個具有toString 和value 方法的物件。