幂迭代算法双停止条件失效及误差计算异常问题排查

问题描述 #

编写的基础幂迭代函数用于求解主特征值，期望通过迭代次数上限和精度阈值两个条件停止迭代，但实际运行中其中一个条件被忽略；同时误差计算结果异常：期望误差为当前特征向量与前一特征向量的范数差，初始误差设为0，但得到的误差值（如8左右）与特征值已接近真实值的收敛情况严重不符。

原代码 #

#power ite. vanilla
import numpy as np
A = np.random.uniform(low=-5.0, high=10.0, size=[3,3])
def power_iteration(A, maxiter, threshold):
    b0 = np.random.rand(A.shape[1])
    it = 0
    error = 0
    while True:
        for i in range(maxiter):
            b1 = np.dot(A, b0)
            b1norm = np.linalg.norm(b1)
            error = np.linalg.norm(b1-b0)
            b0 = b1/b1norm
            domeig = (b0@A@b0)/np.dot(b0, b0)
            
        if error<threshold:
            break
        elif it>maxiter:
            break
        else:
            error = 0
        it = it + 1
    return b0, domeig, it, error

result = power_iteration(A, 10, 0.1)
result

原输出 #

(array([ 0.06009408,  0.95411524, -0.2933476 ]),
 9.001665234545708,
 11,
 8.001665234545815)

注：特征值结果接近真实值（约9），但误差值明显不合理。

错误分析 #

• 嵌套循环逻辑完全错误：原代码用while嵌套for循环，每次while循环直接执行maxiter次迭代，这导致迭代次数上限的控制完全失效，实际迭代次数变成maxiter * (it+1)，和预期的单次迭代计数逻辑不符。
• 误差计算逻辑错误：原代码计算的是未归一化的向量b1和归一化后的向量b0的范数差，两者量级差异极大（b1的范数约等于主特征值，这里是9左右），所以误差值必然偏离真实的向量收敛误差。正确的误差应该是前后两次归一化后的特征向量的范数差。
• 停止条件判断时机错误：原代码在执行完maxiter次迭代后才判断停止条件，无法在迭代过程中根据精度阈值提前终止；同时it的计数逻辑混乱，导致迭代次数上限的条件被忽略。

修正后的代码 #

import numpy as np
A = np.random.uniform(low=-5.0, high=10.0, size=[3,3])
def power_iteration(A, maxiter, threshold):
    # 初始化归一化的特征向量
    b0 = np.random.rand(A.shape[1])
    b0 = b0 / np.linalg.norm(b0)
    it = 0
    error = np.inf  # 初始误差设为无穷大，确保第一次迭代执行
    
    while it < maxiter and error > threshold:
        # 幂迭代核心步骤
        b1 = np.dot(A, b0)
        b1 = b1 / np.linalg.norm(b1)
        # 计算归一化后前后向量的范数差作为误差
        error = np.linalg.norm(b1 - b0)
        # 更新特征向量
        b0 = b1
        # 计算当前主特征值（Rayleigh商）
        domeig = np.dot(b0, np.dot(A, b0)) / np.dot(b0, b0)
        # 迭代次数加1
        it += 1
    
    return b0, domeig, it, error

result = power_iteration(A, 10, 0.1)
print(result)

修正说明 #

1. 移除嵌套循环：改用单while循环，同时判断迭代次数上限和精度阈值两个停止条件，符合预期逻辑。
2. 修正误差计算：计算两次归一化后的特征向量的范数差，真实反映向量的收敛程度。
3. 初始化归一化向量：初始向量直接归一化，避免首次迭代时的量级问题。
4. 调整停止条件判断时机：每次迭代后立即判断是否满足停止条件，可提前终止迭代。

内容的提问来源于stack exchange，提问作者Mephistopheles Faust