什麼都能忘，就是不能忘了 Euler's Method (理論篇)

0. Motivation

Euler's Method 的發想，主要來源自 Taylor's Theorem。那這篇，主要是從解析函數(Analytic Functions)的視角切入，再由 Taylor's Theorem 引導出 Euler's Method。

1. Analytic Functions

首先，我們要先定義，什麼是一個可解析的(analytic)函數。

Definition

假設一個非空區間 $I = (a, b)\subseteq\mathbf{R}$，且函數 $f:I\rightarrow\mathbf{R}$ 為一個解析函數，那其意義等價於

• 給定任意一個點 $x_0\in I$，存在 $x_0$ 的收斂冪級數，皆收斂於 $f$。
  又可以等價於
• 存在一實數列 $\lbrace a_k \rbrace, k = 0, 1, ...$，且任意 $x_0\in (c, d)\subseteq I$ 並

$$
f(x) = \sum_{k=0}^{\infty} a_k(x - x_0)^k,
$$

$\forall x\in (c, d).$

到這邊，還沒有出現我們熟悉的泰勒展開式，首先我們先給一個 Lemma

Lemma

假設 $f(x) = \sum_{k=0}^{\infty} a_k(x - x_0)^k$ 有一個正實數收斂半徑 $R$，根據這個假設，我們可以得到 $f\in\mathcal{C}^{\infty}(x_0 - R, x_0 + R)$ 和

$$
f^{(k)}(x) = \sum_{n=k}^{\infty} \frac{n!}{(n-k)!}a_n(x - x_0)^{n-k},
$$

$\forall x\in (x_0 - R, x_0 + R)$ 且 $k\in\mathbf{N}$。

證明這個 Lemma 不是我們這個主題的重點，此證明可以參考 William R. Wade 寫的高等分析導論(An Introduction to Analysis)，接下來我們證明以下的定理

Theorem (Uniqueness)

假設 $x_0\in (c, d)\subseteq\mathbf{R}$ 且 $c < d$，並假設 $f:(c, d)\rightarrow\mathbf{R}$。那麼，當

$$
f(x) = \sum_{k=0}^{\infty} a_k(x - x_0)^k
$$

對於所有 $x\in (c, d)$ 時，$f\in\mathcal{C}(c, d)$ 並同時滿足

$$
a_k = \frac{f^{(k)}(x_0)}{k!}, k=0, 1, ...
$$。

Proof. 首先，我們可以很清楚知道 $f(x_0) = a_0$，那我們繼續討論 $k\in\mathbf{N}$ 的情況，

那根據定理的前提假設，我們可以得到一個 $\sum_{k=0}^{\infty} a_k(x - x_0)^k$ 的正實數收斂半徑 $R$ ，並且 $(c, d)\subseteq (x_0 - R, x_0 + R)$。這剛好滿足我們前面 Lemma 的前提假設，因次我們可以知道，$f\in\mathcal{C}^{\infty}(c, d)$ 以及

$$
f^{(k)}(x) = \sum_{n=k}^{\infty} \frac{n!}{(n-k)!}a_n(x - x_0)^{n-k},
$$

$\forall x\in(c, d)$。那這邊，我們將 $x$ 以 $x_0$ 代入，那當 $n > k$ 時 $f^{(k)} = 0$，而當 $n = k$ 時，$f^{(n)}(x_0) = k!a_k$，因此得到 $a_k = \frac{f^{(k)}(x_0)}{k!}, k=0, 1, ...$。

2. Taylor's Theorem

觀察一下前面的理論，可以發現已經幫你把無限項的情況都處理好了，當然，我們在使用電腦模擬的時候，不可能讓你算無限項到天荒地老，於是根據上面的定理，我們可以得到有限項的泰勒定理

Theorem

令 $n\in\mathbf{N}$ 的有限正整數，並假設 $f\in\mathcal{C}[a,b]$, $f^{(n+1)}\in [a,b]$, 以及 $x_0\in [a, b]$。
那麼，對於所有 $x\in [a, b]$，存在一個實數 $\xi(x)$ 在 $x$ 與 $x_0$ 之間，並且

$$
f(x) \approx P(x) + R(x) = P_n(x) + R_n(x),
$$

當中

$$
P(x)=\sum_{k=0}^{n}\frac{f^{(k)}(x_0)}{k!}(x - x_0)^k, R(x) = \frac{f^{(n+1)}(\xi(x))}{(n+1)!}(x - x_0)^{n+1}.
$$

3. Euler's Method

我們開始考慮一個常微分方程的初始值問題 :

$$
\frac{dy}{dt} = f(t, y), t\in[a, b], y(a)=k.
$$

這邊我們可以將 $[a, b]$ 切成 $N$ 等分，每等分長度定為 $h = (b - a)/N$，當中我們可以額外定義

$$
t_i = a + ih, \forall i = 0, 1, 2, ..., N.
$$

之後根據上面的 Taylor's Theorem，對於所有 $i = 0, 1, 2, ..., N-1$，可以得到

$$
y(t_{i+1}) = y(t_i) + hy'(t_i) + \frac{h^2}{2}y''(\xi_i)
$$

又等價於

$$
y(t_{i+1}) = y(t_i) + hf(t_i, y(t_i)) + \frac{h^2}{2}y''(\xi_i).
$$

其實到這邊，就已經得到我們要的了，後面的二階微分項，其實就是我們的誤差項，那 Euler's Method 最簡要的寫法如下

$$
y(t_0) = y(a) = k,
$$

$$
y(t_{i+1}) = y(t_i) + hf(t_i, y(t_i)), \forall i = 0, 1, 2, ..., N-1.
$$

4. Reference

Burden, Faires, Burden, Numerical Analysis, 10th ed
William R. Wade, An Introduction to Analysis, 4th ed