IS CS-2018S2-01

题目来源：Problem 1 日期：2024-08-10 题目主题: Math-Numerical Algorithms-Ordinary Differential Equations

Solution

1. Necessary and Sufficient Condition for Eigenvalues of ${\mathbf{A}}_0$

Given that $\mathbf{A}(t)={\mathbf{A}}_0$ is a constant matrix independent of $t$, we consider the solution of the system

$$\frac{\mathrm{d}\mathbf{x}}{\mathrm{d}t}={\mathbf{A}}_0\mathbf{x},$$

where $\mathbf{x}(t)$ is the vector of functions $x_i(t)$, and ${\mathbf{A}}_0$ has distinct eigenvalues. The general solution to this system can be written as

$$\mathbf{x}(t)=\mathbf{P}\exp (\mathbf{\Lambda }t){\mathbf{P}}^{-1}\mathbf{x}(0),$$

where $\mathbf{\Lambda }$ is the diagonal matrix of eigenvalues of ${\mathbf{A}}_0$, and $\mathbf{P}$ is the matrix of corresponding eigenvectors. The solution $x_i(t)\to 0$ as $t\to \infty$ if and only if all the eigenvalues of ${\mathbf{A}}_0$ have negative real parts.

Necessary and Sufficient Condition: The eigenvalues ${\lambda }_i$ of ${\mathbf{A}}_0$ must satisfy

$$\mathrm{Re}({\lambda }_i)<0,\forall i=1,2,\cdots ,n,$$

for the solution $x_i(t)$ to tend to zero as $t\to \infty$ for any initial value $\mathbf{x}(0)$.

2. Recurrence Formula for Forward Euler Method and Local Truncation Error

The forward Euler method is a simple numerical method for solving ODEs. Applied to the system $†$, the forward Euler method gives the recurrence relation:

$$\mathbf{x}(t+h)=\mathbf{x}(t)+h\mathbf{A}(t)\mathbf{x}(t).$$

For a discrete sequence at time steps $t_k=kh$, where $k$ is the step number:

$$\mathbf{X}(k+1)=\mathbf{X}(k)+h\mathbf{A}(kh)\mathbf{X}(k),$$

where $\mathbf{X}(k)$ approximates $\mathbf{x}(kh)$. This can be expressed component-wise as:

$$X_i(k+1)=X_i(k)+h\sum _{j=1}^n{a}_{i,j}(kh)X_j(k).$$

Local Truncation Error: The local truncation error of the forward Euler method is $O(h^2)$, which means that the error per step is proportional to $h^2$.

3. Condition for the Eigenvalues of ${\mathbf{A}}_0$ for the Forward Euler Method

If $\mathbf{A}(t)={\mathbf{A}}_0$ is constant, then the forward Euler method gives:

$$\mathbf{X}(k+1)=(\mathbf{I}+h{\mathbf{A}}_0)\mathbf{X}(k).$$

The system’s stability depends on the eigenvalues of the matrix $\mathbf{I}+h{\mathbf{A}}_0$. For the method to ensure that $X_i(k)\to 0$ as $k\to \infty$ for any initial value $\mathbf{X}(0)$, the eigenvalues ${\mu }_i$ of $\mathbf{I}+h{\mathbf{A}}_0$ must satisfy

$$|{\mu }_i|<1\forall i=1,2,\cdots ,n.$$

Necessary and Sufficient Condition: The eigenvalues ${\lambda }_i$ of ${\mathbf{A}}_0$ must satisfy

$$\mathrm{Re}({\lambda }_i)<-\frac{1}{h},\forall i=1,2,\cdots ,n,$$

for the forward Euler method to ensure that $X_i(k)\to 0$ as $k\to \infty$ for any initial value $\mathbf{X}(0)$.

4. Advantage of the Backward Euler Method

Stability: The backward Euler method is implicit, and it is unconditionally stable for all step sizes $h>0$. This means that it can handle stiff differential equations, where the forward Euler method may require prohibitively small step sizes to maintain stability.

5. Computational Complexity of Forward and Backward Euler Methods

• Forward Euler Method: At each step, the computational complexity is dominated by the matrix-vector multiplication ${\mathbf{A}}_0\mathbf{X}(k)$, which is $O(n^2)$.

• Backward Euler Method: This method requires solving a system of linear equations at each step, specifically $(\mathbf{I}-h{\mathbf{A}}_0)\mathbf{X}(k+1)=\mathbf{X}(k)$. The complexity of solving this linear system using methods like Gaussian elimination is $O(n^3)$.

Thus, the computational complexity for one step of the forward Euler method is $O(n^2)$, whereas for the backward Euler method it is $O(n^3)$.

知识点

常微分方程数值分析向后欧拉法向前欧拉法特征值和特征向量

解题技巧和信息

• For stability in numerical methods for ODEs, always consider the eigenvalues of the coefficient matrix and the method’s stability region.
• The backward Euler method is preferred for stiff equations despite its higher computational cost.

重点词汇

eigenvalue 特征值

stability 稳定性

backward Euler method 向后欧拉法

forward Euler method 向前欧拉法

参考资料

1. Numerical Analysis, Richard L. Burden, J. Douglas Faires, Chap. 8