Korean, Edit

第25章数值分析算法集

推荐帖子：【算法】【算法索引】(https://jb243.github.io/pages/1278)

1. 托马斯算法

2. 【高斯消除算法】(#2-gauss-elimination-algorithm)

3. 杜利特尔方法

4. 乔列斯基方法

5. 雅可比迭代法

6. 高斯-赛德尔算法

7. 改进的欧拉算法（Heum 方法）

8. 经典RUNGE-KUTTA算法

9. 改进的RUNGE-KUTTA算法

10. RUNGE-KUTTA-FEHLBERG 算法

11. Adams-Bashforth 算法

12. Adams-Moulton 算法

13. 显式方法

14. [完全（简单）隐式方法]（#14-完全简单隐式方法）

15. 曲柄尼科尔森方法

16. 积分近似公式

17. 优化算法


1.托马斯算法

A → A* = [ajk] = [Ar]

该算法对三对角矩阵 A 唯一计算 Ax = [xj] 或表明不存在唯一解。

（这里，设 A 的对角线元素为 f、下对角线元素为 e、上对角线元素为 g。）

输入：n × (n+1) 的增广矩阵 A* = [ajk]，其中 aj, n+1 = bj

输出：方程 (1) 的解 x = [xj] 或指示无唯一解的消息

// 分解

DO k = 2, …, n

ek = ek / fk-1

fk = fk - ek × gk-1

结束

// 前向替换

DO k = 2, …, n

rk = rk - ek × rk-1

结束

// 向后替换

xn = rn / fn

DO k = n - 1, …, 1

xk = (rk - gk × xk+1) / fk

结束

结束高斯



2.高斯消去算法

A → A* = [ajk] = [Ab]

该算法唯一计算 Ax = b 的 x = [xj] 或表明不存在唯一解。

输入：n × (n+1) 的增广矩阵 A* = [ajk]，其中 aj, n+1 = bj

输出：方程 (1) 的解 x = [xj] 或指示无唯一解的消息

对于 k = 1, …, n - 1 执行：

m = k

对于 j = k + 1, …, n，执行：

如果 amk < ajk 那么 m = j 结束

结束

如果 amk = 0 那么

输出“没有唯一的解决方案”

停止

结束

否则将 k 行与 m 行交换

对于 j = k + 1, …, n，执行：

mjk = ajk / akk

对于 p = k + 1, …, n + 1，执行：

ajp = ajp - mjkakp

结束

结束

结束

如果 ann = 0 那么

输出“没有唯一的解决方案”

停止

结束

xn = an,n+1 / ann [开始向后替换]

对于 i = n - 1, …, 1，执行：

xi = (1/aii)(ai,n+1 - (ai,i+1xi+1 + … + ai, nxn))

结束

输出 x = [xj]

停止

结束高斯



3.杜利特尔法

Ax = LUx = b

Ux = L-1b = y

x = U-1y



4.乔列斯基法—

Ax = LLTx = b

LTx = L-1b = y

x = (LT)-1y



5.雅可比迭代法

例如

x1 - 0.25x2 - 0.25x3 = 50 ⇔ x1 = 0.25x2 + 0.25x3 + 50

-0.25x1 + x2 - 0.25x4 = 50 ⇔ x2 = 0.25x1 + 0.25x4 + 50

-0.25x1 + x3 - 0.25x4 = 25 ⇔ x3 = 0.25x1 + 0.25x4 + 25

-0.25x2 - 0.25x3 + x4 = 25 ⇔ x4 = 0.25x2 + 0.25x3 + 25

参见

x(m+1) = b - Lx(m) - Ux(m) = b - (L+U)x(m)



6.高斯-赛德尔算法

A, b , x(0), ε, N

该算法在给定 n × n 矩阵 A = [ajk] 的初始近似 x(0) 的情况下，计算 Ax = b 的解 x，其中，对于 j = 1, …, n，ajj ≠ 0。

输入：A，b，初始近似x(0)，容差ε，最大迭代次数N

输出：近似值 x(m) = [x j(m)] 或指示 x(N) 不满足容差条件的错误消息

对于 m = 0, …, N - 1 执行：

对于 j = 1, …, n 执行：

xj(m) = (1/ajj)(bj - (aj1x1(m+1) + … + aj, j-1xj-1(m+1)) - (aj, j+1xj+1(m) + … + ajnxn(m)))

结束

如果 ∀j, xj(m+1) - xj(m) 然后

输出 x(m+1)

停止

结束

结束

输出

结束高斯-赛德尔

例如

x1 - 0.25x2 - 0.25x3 = 50 ⇔ x1 = 0.25x2 + 0.25x3 + 50

-0.25x1 + x2 - 0.25x4 = 50 ⇔ x2 = 0.25x1 + 0.25x4 + 50

-0.25x1 + x3 - 0.25x4 = 25 ⇔ x3 = 0.25x1 + 0.25x4 + 25

-0.25x2 - 0.25x3 + x4 = 25 ⇔ x4 = 0.25x2 + 0.25x3 + 25

参见

x(m+1) = b - Lx(m+1) - Ux(m) ⇔ x(m+1) = (I + L)-1b - (I + L)-1Ux(m)



7.改进的欧拉算法（Heum 法）

f、x0、y0、h、N

该算法解决等距点 x1 = x0 + h、x2 = x0 + 2h、…、xN = x0 + Nh 处的初始值问题 y’ = f(x, y)、y(x0) = y0。

这里，f 是定义在 [x0, xN] 上的函数，保证唯一的解决方案。

INPUT：初始值x0，y0，步长h，步数N

输出：在 xn+1 = x0 + (n+1)h (n = 0, …, N-1) 处解 y(xn+1) 的近似值 yn+1

对于 n = 0, 1, …, N-1 执行：

xn+1 = xn + h

k1 = hf(xn, yn)

k2 = hf(xn+1, yn+k1)

yn+1 = yn + 0.5(k1 + k2)

输出 xn+1, yn+1

结束

停止

结束欧拉



8.经典的 RUNGE-KUTTA 算法

f、x0、y0、h、N该算法解决等距点 x1 = x0 + h、x2 = x0 + 2h、…、xN = x0 + Nh 处的初始值问题 y’ = f(x, y)、y(x0) = y0。

这里，f 是定义在 [x0, xN] 上的函数，保证唯一的解决方案。

INPUT：初始值x0，y0，步长h，步数N

输出：在 xn+1 = x0 + (n+1)h (n = 0, …, N-1) 处解 y(xn+1) 的近似值 yn+1

对于 n = 0, 1, …, N-1 执行：

k1 = hf(xn, yn)

k2 = hf(xn + 0.5h, yn + 0.5k1)

k3 = hf(xn + 0.5h, yn + 0.5k2)

k4 = hf(xn + h, yn + k3)

xn+1 = xn + h

yn+1 = yn + (1/6)(k1 + 2k2 + 2k3 + k4)

输出 xn+1, yn+1

结束

停止

结束龙格-库塔



9。改进的 RUNGE-KUTTA 算法

f、x0、y0、h、N

该算法解决等距点 x1 = x0 + h、x2 = x0 + 2h、…、xN = x0 + Nh 处的初始值问题 y’ = f(x, y)、y(x0) = y0。

这里，f 是定义在 [x0, xN] 上的函数，保证唯一的解决方案。

INPUT：初始值x0，y0，步长h，步数N

输出：在 xn+1 = x0 + (n+1)h (n = 0, …, N-1) 处解 y(xn+1) 的近似值 yn+1

对于 n = 0, 1, …, N-1 执行：

k1 = hf(xn, yn)

k2 = hf(xn + (1/4)h, yn + (1/4)k1)

k3 = hf(xn + (3/8)h, yn + (3/32)k1 + (9/32)k2)

k4 = hf(xn + (12/13)h, yn + (1932/2197)k1 - (7200/2197)k2 + (7296/2197)k3)

k5 = hf(xn + h, yn + (439/216)k1 - 8k2 + (3680/513)k3 - (845/4104)k4)

xn+1 = xn + h

yn+1 = yn + (25/216)k1 + (1408/2565)k3 + (2197/4104)k4 - (1/5)k5

输出 xn+1, yn+1

结束

停止

结束龙格-库塔



10。龙格-库塔-菲尔伯格算法

f、x0、y0、h、N

该算法解决等距点 x1 = x0 + h、x2 = x0 + 2h、…、xN = x0 + Nh 处的初始值问题 y’ = f(x, y)、y(x0) = y0。

这里，f 是定义在 [x0, xN] 上的函数，保证唯一的解决方案。

INPUT：初始值x0，y0，步长h，步数N

输出：在 xn+1 = x0 + (n+1)h (n = 0, …, N-1) 处解 y(xn+1) 的近似值 yn+1

对于 n = 0, 1, …, N-1 执行：

k1 = hf(xn, yn)

k2 = hf(xn + (1/4)h, yn + (1/4)k1)

k3 = hf(xn + (3/8)h, yn + (3/32)k1 + (9/32)k2)

k4 = hf(xn + (12/13)h, yn + (1932/2197)k1 - (7200/2197)k2 + (7296/2197)k3)

k5 = hf(xn + h, yn + (439/216)k1 - 8k2 + (3680/513)k3 - (845/4104)k4)» k6 = hf(xn + (1/2)h, yn - (8/27)k1 + 2k2 + (3544/2565)k3 - (1859/4104)k4 - (11/40)k5)

xn+1 = xn + h

yn+1 = yn + (16/135)k1 + (6656/12825)k3 + (28561/56430)k4 - (9/50)k5 + (2/55)k6

输出 xn+1, yn+1

结束

停止

结束龙格-库塔



11。 Adams-Bashforth 算法

xn、xn-1、xn-2、xn-3、fn、fn-1、fn-2、fn-3、h、N

该算法考虑在某些包含 x0 的开区间中具有唯一解的初始值问题：

y’ = f(x, y), y(x0) = y0, fn = f(xn, yn)。

该方法使用牛顿后向差分公式将被积函数 f(x, y(x)) 替换为插值多项式，然后对其进行积分。

输入：xn、xn-1、xn-2、xn-3、fn、fn-1、fn-2、fn-3、h、N

输出：步骤 xn+m = x0 + (n+m)h (m = 1, …, N) 处的解 y(xn+m) 的近似值 yn+m

k4 = hfn

k3 = hfn-1

k2 = hfn-2

k1 = hfn-3

对于 m = 1, …, N 执行：

xn+m = xn+m-1 + h

yn+m = yn+(m-1) + (1/24)(55k4 - 59k3 + 37k2 - 9k1)

k1 = k2

k2 = k3

k3 = k4

k4 = hf(xn+m, yn+m)

输出 xn+m, yn+m

结束

停止

结束 ADAMS-巴什福斯



12。亚当斯-莫尔顿算法

xn、xn-1、xn-2、xn-3、fn、fn-1、fn-2、fn-3、h、N

该算法考虑在某些包含 x0 的开区间中具有唯一解的初始值问题：

y’ = f(x, y), y(x0) = y0, fn = f(xn, yn)。

该方法添加了预测器-校正器步骤。误差估计如下：

εn+1 = (1/15)(yn+1 - y*n+1)。

输入：xn、xn-1、xn-2、xn-3、fn、fn-1、fn-2、fn-3、h、N

输出：步骤 xn+m = x0 + (n+m)h (m = 1, …, N) 处的解 y(xn+m) 的近似值 yn+m

k4 = hfn

k3 = hfn-1

k2 = hfn-2

k1 = hfn-3

对于 m = 1, …, N 执行：

xn+m = xn+m-1 + h

y*n+m = yn+(m-1) + (1/24)(55k4 - 59k3 + 37k2 - 9k1)

k* = f(xn+m, y*n+m)

yn+m = yn+(m-1) + (1/24)(9k* + 19k4 - 5k3 + k2)

k1 = k2

k2 = k3

k3 = k4

k4 = hf(xn+m, yn+m)

输出 xn+m, yn+m

结束

停止

结束 亚当斯-莫尔顿



13。显式方法

x(m+1) = Ax(m) + b

例如

3×3：A = ((1 - 2λ, λ, 0)T, (λ, 1 - 2λ, λ)T, (0, λ, 1 - 2λ)T), b = (λx0, 0, λxn+1)T



14。完全（简单）隐式方法

—x(m+1) = A-1x(m) - A-1b

例如

3×3: A = ((1 + 2λ, -λ, 0)T, (-λ, 1 + 2λ, -λ)T, (0, -λ, 1 + 2λ)T), b = (λx0, 0, λxn+1)T



15。曲柄尼科尔森法

x(m+1) = Aim-1(Aexx(m) + bex) - A-1bim

例如

3×3: A = ((1 + 2λ, -λ, 0)T, (-λ, 1 + 2λ, -λ)T, (0, -λ, 1 + 2λ)T), b = (λx0, 0, λxn+1)T



16。积分近似公式

⑴ 梯形法则

①数值积分法。

② 证明： 假设f是线性的（一次）并证明等式在单位区间上成立。


스크린샷 2024-12-04 11 40 59


⑵ 辛普森法则

①数值积分法

② 证明： 假设f是二次（抛物线）并证明等式在单位区间上成立。

③ 比梯形法则更准确。


스크린샷 2024-12-04 11 41 19


⑶ 辛普森3/8规则

①数值积分法

② 证明： 假设f是三次方（三次）并证明等式在单位区间上成立

③ 比辛普森法则更准确。


스크린샷 2024-12-04 11 41 32


⑷ 波德法则


스크린샷 2024-12-04 11 41 49


⑸ 移动平均法

17。优化算法

⑴【牛顿-拉夫逊法】(https://jb243.github.io/pages/1773)

⑵【最优传输定理】(https://jb243.github.io/pages/2386)

⑶ Nelder-Mead 方法


受保护_0


⑷【鲍威尔法】(https://docs.scipy.org/doc/scipy/reference/optimize.minimize-powell.html#optimize-minimize-powell)

⑸ CG方法

⑹【BFGS方法】(https://www.sciencedirect.com/science/article/pii/0009261485805741?viaihub)

①定义：近似Hessian矩阵的逆，以减少牛顿法的计算量。

② 公式


스크린샷 2024-12-04 11 42 24


⑺ L-BFGS-B方法

⑻【TNC方法】(https://docs.scipy.org/doc/scipy/reference/optimize.minimize-tnc.html#optimize-minimize-tnc)

⑼ COBYLA方法

⑽ 【SLSQP方法】(https://docs.scipy.org/doc/scipy/reference/optimize.minimize-slsqp.html#optimize-minimize-slsqp)

⑾ 信任约束方法

⑿ 【狗腿法】(https://docs.scipy.org/doc/scipy/reference/optimize.minimize-dogleg.html#optimize-minimize-dogleg)

⒀ 牛顿CG方法⒁ Trust-NCG 方法

⒂ 信任精确方法

⒃ Trust-Krylov 方法

⒄ 涅斯特罗夫法

⒅ SANN（模拟退火）

① 一种慢速随机全局优化方法。

② 适用于不可微分或非凸函数。

⒆ 与编程相关

① 优化算法相关的R包及函数：RSolnp、optim、GenSA、alabama


输入：2016.12.11 02:10

修改时间：2024.03.28 22:20

results matching ""

    No results matching ""