斯特芬森迭代法（Python）

清疚 2022-05-21 00:16 491阅读 0赞

## 简述 ##

斯特芬森迭代法，本质上就使用了埃特金加速法的不动点迭代法。

> **GitHub:[https://github.com/Sean16SYSU/Algorithms4N][https_github.com_Sean16SYSU_Algorithms4N]**

# Steffensen’s method #

## Aitken 加速方法 ##

x 1 = φ ( x 0 ) x\_1 = \\varphi(x\_0) x1=φ(x0)  
再结合微分中值定理，有  
 x 1 − x ∗ = φ ( x 0 ) − φ ( x ∗ ) = φ ′ ( ξ ) ( x 0 − x ∗ ) x\_1 - x^\* = \\varphi(x\_0) - \\varphi(x^\*) = \\varphi'(\\xi)(x\_0 -x^\*) x1−x∗=φ(x0)−φ(x∗)=φ′(ξ)(x0−x∗)  
假设 φ ′ ( ξ ) \\varphi'(\\xi) φ′(ξ)变化不大话，再代入有，  
 x 2 − x ∗ = φ ( x 1 ) − φ ( x ∗ ) = φ ′ ( ξ ) ( x 1 − x ∗ ) x\_2 - x^\* = \\varphi(x\_1) - \\varphi(x^\*) = \\varphi'(\\xi)(x\_1 -x^\*) x2−x∗=φ(x1)−φ(x∗)=φ′(ξ)(x1−x∗)  
则，消去 φ ′ ( ξ ) \\varphi'(\\xi) φ′(ξ)后，得到，  
 x ∗ = x 0 − ( x 1 − x 0 ) 2 x 2 − 2 x 1 + x 0 x^\* = x\_0 - \\frac\{(x\_1 - x\_0)^2\}\{x\_2 - 2x\_1+x\_0\} x∗=x0−x2−2x1\+x0(x1−x0)2

## 斯特芬森迭代法 ##

使用了Aitken加速的不动点迭代法

\{ y k = φ ( x k ) , z k = φ ( y k ) x k + 1 = x k − ( y k − x k ) 2 z k − 2 y k + x k \\left\\\{ \\begin\{aligned\} y\_k = \\varphi(x\_k), z\_k = \\varphi(y\_k) \\\\ x\_\{k+1\} = x\_k - \\frac\{(y\_k - x\_k)^2\}\{z\_k - 2y\_k+x\_k\} \\end\{aligned\} \\right. ⎩⎪⎨⎪⎧yk=φ(xk),zk=φ(yk)xk\+1=xk−zk−2yk\+xk(yk−xk)2

[可以结合不动点迭代法来看，点击访问][Link 1]

## 代码 ##

关于求解根号3

x = 1
    for i in range(5):
        y = x - 0.1 * (x ** 2 - 3)
        z = y - 0.1 * (y ** 2 - 3)
        x = x - (y-x)**2 / (z-2*y+x)
    print(x)

输出的结果过是：

1.7320508075688767

画图和一般的作对比：

TIME = 5
    x = 1
    data = []
    for i in range(TIME):
        data.append(x)
        y = x - 0.1 * (x ** 2 - 3)
        z = y - 0.1 * (y ** 2 - 3)
        x = x - (y-x)**2 / (z-2*y+x)
        
    data.append(x)
    plt.plot(data, label='stf')
    
    data = []
    x = 1
    for i in range(TIME * 5):
        data.append(x)
        x = x - 0.1 * (x ** 2 - 3)
    data.append(x)
    print(x)
    
    plt.plot(data, label='iter')
    
    plt.legend()
    plt.show()

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70]

[https_github.com_Sean16SYSU_Algorithms4N]: https://github.com/Sean16SYSU/Algorithms4N
[Link 1]: https://blog.csdn.net/a19990412/article/details/80814435
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ExOTk5MDQxMg_size_16_color_FFFFFF_t_70]: /images/20220521/cec50d4273e94cb0a368d305315b0a20.png