更稳定的反向替换方法?

计算科学 线性求解器 正则
2021-12-09 10:04:31

我在 Fortran (2008) 中进行了一些修改并编写了以下内容来解决 上三角形 ,Rx=bRRn×nx,bRn

我的代码如下所示:

function backsub_upper(R, b) result(x)

    ! R is a square upper triangular matrix
    ! b is the vector to be solved for
    ! x is the solution to Rx=b

    real(kind=wp), dimension(:,:), intent(in)   :: R
    real(kind=wp), dimension(:) , intent(in)    :: b

    real(kind=wp), dimension(:)                 :: x(size(b)), bc(size(b))
    integer(kind=sp)                            :: i,j

    x = 0.0_wp
    bc(:) = b(:)
    write(*,*)"solving"
    do j=1,size(bc)
        i = size(bc)+1-j
        x(i) = bc(i)/R(i,i)

        if (i/=1) bc(1:i-1) = bc(1:i-1) - x(i)*R(1:i-1,i)
    end do
    write(*,*)"done"

end function backsub_upper

我用随机(上三角)和随机进行了测试。效果很好,但超过 n=~50 时,错误开始变得疯狂。我可以通过强制执行一些对角优势来降低误差,但只是想知道是否有更好的算法可以更好地控制一般矩阵的误差?Rb

我意识到随机矩阵不是“通用的”,但这个功能让我担心

2个回答

反向替换是向后稳定的,这意味着它的误差与将输入数据截断到机器精度(机器精度)x(问题的条件数)所引起的误差具有相同的数量级。

因此,如果反向替换给你一个不准确的答案,那么在同一个问题上,没有其他算法可以给你更好的答案(对于通用数据,除了最坏情况因子 O(n),通常甚至更低)。

这里的问题可能是输入的选择,随机三角矩阵的条件可能非常糟糕。这里更好的选择是来自随机矩阵的 LU 分解的 L 或 U 因子,或者来自随机矩阵的 QR 分解的 R 因子。