不动点迭代法求方程的根（Python实现）

ゝ一纸荒年。 2022-05-21 00:09 398阅读 0赞

# 不动点迭代法 #

将原先的  
 f ( x ) = 0 f(x) = 0 f(x)=0  
转化成  
 x = h ( x ) x = h(x) x=h(x)  
的方式进行求解。

## 不动点的存在性定理 ##

**定理1**

如果  f ( x ) f(x) f(x) 为区间 \[ a , b \] \[a, b\] \[a,b\]上的连续函数，且满足下面两个条件：

1.  压缩性：对于  x ∈ \[ a , b \] x \\in \[a, b\] x∈\[a,b\],  a ≤ f ( x ) ≤ b a \\leq f(x) \\leq b a≤f(x)≤b
2.  大L性质：存在正常数L<1, 使得，对于任意的 x , y ∈ \[ a , b \] x, y \\in \[a, b\] x,y∈\[a,b\] 都有，  
     ∣ f ( x ) − f ( y ) ∣ ≤ L ∣ x − y ∣ |f(x) - f(y)| \\leq L|x-y| ∣f(x)−f(y)∣≤L∣x−y∣

则存在有唯一的不动点。

构造 h ( x ) = f ( x ) − x h(x) = f(x) - x h(x)=f(x)−x，再用连续函数的介值定理就可以证明存在性，唯一性代入就可证明。

**局部收敛定理：**

若有这样的不动点  x ∗ x^\* x∗ ，如果存在有在不动点附近的某个领域，满足有 h ′ ( x ) < 1 h'(x) < 1 h′(x)<1，则迭代法：  
 x t + 1 = h ( x t ) x\_\{t+1\} = h(x\_t) xt\+1=h(xt)  
局部收敛。

*   h ′ ( x ∗ ) h'(x^\*) h′(x∗)数值越接近0，收敛速度越快。
 *  如果对于小于n次的导数在不动点出都为0，且 h ( n ) ( x ) h^\{(n)\}(x) h(n)(x) 不一定为0，则称为n阶收敛

## 举列子 ##

*  求根号数的迭代（不妨取根号3）

迭代方式有很多种比如:  
 x 2 − 3 = 0 x = x − λ ( x 2 − 3 ) λ ∈ \[ 0 , 1 \] x k + 1 = x k − λ ( x k 2 − 3 ) \\begin\{aligned\} x^2 - 3 =& 0 \\\\ x =& x - \\lambda (x^2 - 3) & \\lambda \\in \[0, 1\] \\\\ x\_\{k+1\} =& x\_\{k\} - \\lambda (x\_\{k\}^2 - 3)\\\\ \\end\{aligned\} x2−3=x=xk\+1=0x−λ(x2−3)xk−λ(xk2−3)λ∈\[0,1\]

**代码：**

x = 1
    for i in range(100):
        x = x - 0.1 * (x ** 2 - 3)
    print(x)

**输出：**

1.7320508075688772

x 2 − 3 = 0 n x 2 = ( n − 1 ) x 2 + 3 n ∈ N x = ( n − 1 ) x n + 3 n x x k + 1 = ( n − 1 ) x k n + 3 n x k \\begin\{aligned\} x^2 - 3 =& 0 \\\\ nx^2 =& (n-1)x^2 + 3 & n \\in N \\\\ x =& \\frac\{(n-1)x\}\{n\} + \\frac\{3\}\{nx\} \\\\ x\_\{k+1\} =& \\frac\{(n-1)x\_k\}\{n\} + \\frac\{3\}\{nx\_k\}\\\\ \\end\{aligned\} x2−3=nx2=x=xk\+1=0(n−1)x2\+3n(n−1)x\+nx3n(n−1)xk\+nxk3n∈N

**代码：**

x, n = 2, 2
    for i in range(100):
        x = (n - 1) / n * x + 3 / (n * x)
    print(x)

**输出：**

1.7320508075688772

*  实际上的 3 \\sqrt\{3\} 3

import math
    math.sqrt(3)

*  输出：`1.7320508075688772`

## 尾记 ##

*  本文链接: [https://blog.csdn.net/a19990412/article/details/80814435][https_blog.csdn.net_a19990412_article_details_80814435]
 *  对应github: [https://github.com/Sean16SYSU/Algorithms4N][https_github.com_Sean16SYSU_Algorithms4N]

[https_blog.csdn.net_a19990412_article_details_80814435]: https://blog.csdn.net/a19990412/article/details/80814435
[https_github.com_Sean16SYSU_Algorithms4N]: https://github.com/Sean16SYSU/Algorithms4N