定点迭代法（带埃特金加速）流程图

完整的 Python 实现

import math

def fixed_point_aitken_strict(phi, a, b, epsilon=1e-6, max_iter=100):
    """
    的定点迭代法（带埃特金加速）
    
    参数:
    phi: 迭代函数 φ(x)
    a, b: 区间 [a, b]
    epsilon: 收敛容差
    max_iter: 最大迭代次数
    
    返回:
    x: 近似根
    iterations: 迭代次数
    """
    
    # 初始值
    x0 = (a + b) / 2
    x1 = phi(x0)
    
    print(f"定点迭代法（带埃特金加速）")
    print(f"区间: [{a}, {b}]")
    print(f"容差: {epsilon}")
    print(f"{'迭代':>3} {'x0':>12} {'x1':>12} {'x2':>12} {'x_acc':>12} {'误差':>12} {'方法':>8}")
    print("-" * 80)
    
    for i in range(max_iter):
        # 计算 x2 = φ(x1)
        x2 = phi(x1)
        
        # 检查普通收敛条件 |x2 - x1| < ε
        if abs(x2 - x1) < epsilon:
            print(f"{i:3d} {x0:12.6f} {x1:12.6f} {x2:12.6f} {'':>12} {abs(x2-x1):12.6e} {'普通'}")
            print(f"\n收敛! 根 ≈ {x2:.10f}, 迭代次数: {i+1}")
            return x2, i+1
        
        # 计算分母 d = x2 - 2x1 + x0
        d = x2 - 2*x1 + x0
        
        # 检查分母是否足够大（避免除零）
        if abs(d) > 1e-20:
            # 埃特金加速公式：x = (x0*x2 - x1²)/d
            x_acc = (x0 * x2 - x1 * x1) / d
            y = phi(x_acc)
            
            # 检查加速后的收敛条件 |x - y| < ε
            if abs(x_acc - y) < epsilon:
                print(f"{i:3d} {x0:12.6f} {x1:12.6f} {x2:12.6f} {x_acc:12.6f} {abs(x_acc-y):12.6e} {'埃特金'}")
                print(f"\n收敛! 根 ≈ {x_acc:.10f}, 迭代次数: {i+1}")
                return x_acc, i+1
            
            print(f"{i:3d} {x0:12.6f} {x1:12.6f} {x2:12.6f} {x_acc:12.6f} {abs(x_acc-y):12.6e} {'埃特金'}")
        else:
            print(f"{i:3d} {x0:12.6f} {x1:12.6f} {x2:12.6f} {'分母太小':>12} {abs(x2-x1):12.6e} {'普通'}")
        
        # 更新变量
        x0 = x1
        x1 = x2
    
    print(f"\n警告: 达到最大迭代次数 {max_iter} 仍未收敛")
    return x1, max_iter

def test_example_1():
    """例1: x³ - 5x + 1 = 0"""
    print("=" * 70)
    print("例1: x³ - 5x + 1 = 0")
    print("方程变形: x = (x³ + 1)/5")
    print("区间: [0, 1], 精确解 ≈ 0.201640")
    
    def phi(x):
        return (x**3 + 1) / 5
    
    root, iterations = fixed_point_aitken_strict(phi, 0, 1, epsilon=1e-4, max_iter=10)
    
    # 验证结果
    residual = abs(root - phi(root))
    print(f"验证: |x - φ(x)| = {residual:.2e}")
    return root, iterations

def test_example_2():
    """例2: x = 0.25*exp(x)"""
    print("=" * 70)
    print("例2: x = 0.25*exp(x)")
    print("精确解 ≈ 0.357403")
    
    def phi(x):
        return 0.25 * math.exp(x)
    
    root, iterations = fixed_point_aitken_strict(phi, 0, 1, epsilon=1e-6, max_iter=20)
    
    # 验证结果
    residual = abs(root - phi(root))
    print(f"验证: |x - φ(x)| = {residual:.2e}")
    return root, iterations

def test_example_3():
    """例3: x = log₂(x + 1.5)"""
    print("=" * 70)
    print("例3: x = log₂(x + 1.5)")
    print("对应方程: x - 2ˣ + 1.5 = 0")
    
    def phi(x):
        return math.log2(x + 1.5)
    
    root, iterations = fixed_point_aitken_strict(phi, 0, 2, epsilon=1e-6, max_iter=20)
    
    # 验证结果
    residual = abs(root - phi(root))
    print(f"验证: |x - φ(x)| = {residual:.2e}")
    return root, iterations

def convergence_analysis():
    print("\n" + "=" * 70)
    print("收敛性分析")
    print("=" * 70)
    
    # 分析例1的收敛条件
    def phi1(x):
        return (x**3 + 1) / 5
    
    def phi1_prime(x):
        return 3*x**2 / 5  # φ'(x) = 0.6x²
    
    print("例1: x = (x³ + 1)/5")
    print("φ'(x) = 0.6x²")
    print("在区间[0,1]上:")
    print("max|φ'(x)| = φ'(1) = 0.6 < 1")
    print("满足收敛条件: |φ'(x)| ≤ L < 1")
    print("∴ 迭代收敛")
    
    # 计算收敛速度
    root1, _ = test_example_1()
    convergence_rate = phi1_prime(root1)
    print(f"收敛速度常数 C = |φ'(x*)| ≈ {abs(convergence_rate):.6f}")
    print("收敛阶数: 1阶（线性收敛）")

# 主程序
if __name__ == "__main__":
    print("定点迭代法（带埃特金加速）")
    print("=" * 70)
    
    # 运行所有测试
    results = []
    
    print("\n1. 基本定点迭代法测试")
    results.append(("例1: x³ - 5x + 1 = 0", test_example_1()))
    results.append(("例2: x = 0.25*exp(x)", test_example_2()))
    results.append(("例3: x = log₂(x + 1.5)", test_example_3()))
    
    # 收敛性分析
    convergence_analysis()
    
    # 总结
    print("\n" + "=" * 70)
    print("测试总结")
    print("=" * 70)
    for name, (root, iterations) in results:
        print(f"{name}")
        print(f"  根 ≈ {root:.8f}, 迭代次数: {iterations}")