如何确定矩阵是否是“正定”矩阵通过 SQL？

Question

有什么方法，纯粹在MSSQL中，可以确定以下 maxtrix 是否会计算为正定？

A C D G H I
A 1.00 0.68 0.24 0.62 0.90 0.00
C 0.68 1.00 0.25 0.46 0.61 0.00
D 0.24 0.25 1.00 0.60 0.08 0.00
G 0.62 0.46 0.60 1.00 0.46 0.00
H 0.90 0.61 0.08 0.46 1.00 0.00
I 0.00 0.00 0.00 0.00 0.00 1.00

现在，我们正在使用第 3 方应用程序 ExtremeNumerics，以相当黑盒的方式处理确定。如果我有一个可以输入资产、相关资产和价值的 SQL 表，是否有办法进行数学计算？

我查了一下，并没有真正看到 MSSQL 中有任何处理矩阵数学的东西。

谢谢。

编辑：微软 SQL 2008

Answer 1

好的，我们开始吧。这确实有效，但确实给人一种我们必须强制 SQL Server 去做它并不真正想做的事情的感觉。我不愿意建议在现实生活中这样做 - 我相当确定它的矩阵大小将缩放为 O(n^3) 。也许有更好的方法，进行 Cholesky 分解 而不是这种方式 - 我可能会在稍后的日期。说完这些注意事项，让我们继续：

这需要 SQL Server 2008，因为它的表数据类型

（即使这样，也没有达到应有的帮助） ，正如我们将看到的...）

首先是方法。我们将使用西尔维斯特准则，因为它是最容易理解的：实对称矩阵是 PD 当且仅当所有主次要因素的行列式都是正的。所以我们需要一种计算行列式的方法。同样，我们将使用一种简单的方法（拉普拉斯展开），而不是任何为计算而设计的方法效率。

基础工作

我们首先定义将用于传递矩阵的用户定义表类型：

create type Matrix
as table ( Row int, Col int, Val float )
go

计算行列式

为此，我们将定义两个相互递归函数，因为这是我可以使其工作的唯一方法考虑到 SQL Server 2008 中 table 类型数据的功能有限。

首先，入口点（也处理基本情况）：

create function Determinant ( @matrix Matrix readonly )
returns float
as
begin
    -- Base case of recursion
    if ((select count(*) from @matrix) = 1) 
        return (select Val from @matrix)

确定我们不在基本情况（1x1 矩阵）时，我们现在有工作要做。第一件事是将输入中的行数和列数“规范化”，从现在的行数和列数变为 1..n

    -- canonicalize row and col numbers (doesn't affect answer)
    declare @rowMap table ( fr_row int, to_row int )
    declare @colMap table ( fr_col int, to_col int )

    insert @rowMap
    select row, row_number() over(order by row) from @matrix
    group by row

    insert @colMap
    select col, row_number() over(order by col) from @matrix
    group by col

    declare @canonicalMatrix Matrix
    insert @canonicalMatrix 
    select 
        to_row, to_col, Val
    from @matrix m
    inner join @rowMap rm on m.row = rm.fr_row
    inner join @colMap cm on m.col = cm.fr_col

我们现在准备使用 拉普拉斯展开式。这涉及到调用我们的相互递归同志，它将按我们请求的行和列进行小数化，然后回调我们来计算小数的行列式，

    -- apply laplace expansion on first row
    return
    (
        select sum(
            (case col % 2 
            when 1 then 1   -- odd col
            when 0 then -1  -- even col
            end
            )
                    * Val 
                    * dbo.DeterminantOfMinor ( @canonicalMatrix, 1, col ) 
            ) from @canonicalMatrix where row = 1
    )
end
go

事实证明，DeterminantOfMinor 非常简单，如果 table 值在 SQL Server 中更一流，则没有必要：

create function dbo.DeterminantOfMinor ( 
    @matrix Matrix readonly
    , @drop_row int
    , @drop_col int 
)
returns float
as
begin

    declare @minor Matrix
    insert @minor select * from @matrix 
        where row <> @drop_row and col <> @drop_col
    return
        dbo.Determinant( @minor )

end
go

有了行列式计算器，我们就快成功了。

正定性测试

根据 Sylvester 准则，矩阵是 PD 当且仅当所有的行列式其主要未成年人呈阳性。因此，我们可以构建一个（自）递归函数来检查这一点，唯一的问题是，值得确保我们首先执行廉价行列式：

create function dbo.is_positive_definite ( @matrix Matrix readonly )
returns bit
as
begin
    -- base case of recursion
    -- a 1x1 matrix is PD iff the single value is positive
    if ((select count(*) from @matrix) = 1) 
        return (select case when Val > 0 then 1 else 0 end from @matrix)

我们构建我们的矩阵输入没有最后一行和最后一列：

    declare @smallerMat Matrix
    insert @smallerMat
    select row, col, Val from @matrix
    where row < (select max(row) from @matrix)
    and col < (select max(col) from @matrix)

并向下递归，仅如果我们所有的主要次要因素都被确认为 PD，则计算我们输入的行列式：

    -- for our input to be PD, its smaller version must be PD:
    return
        ( select case dbo.is_positive_definite( @smallerMat )
        when 1 then 
                (select case 
                     when dbo.Determinant ( @matrix ) > 0 
                     then 1 
                     else 0 
                     end)
        else 0
        end
        )

end
go

就是这样！

测试

我使用了您的示例：

declare @test Matrix

insert @test values ( 1, 1, 1.00 )
insert @test values ( 1, 2, 0.68 )
insert @test values ( 1, 3, 0.24 )
/* snip */
insert @test values ( 6, 4, 0.00 )
insert @test values ( 6, 5, 0.00 )
insert @test values ( 6, 6, 1.00 )

select dbo.Determinant ( @test )
select dbo.is_positive_definite ( @test )


----------------------
0.0333962320000001

(1 row(s) affected)


-----
1

(1 row(s) affected)

这些结果与我从此在线计算器获得的结果一致，所以我很高兴这有效。

时间

在我测试的系统上使用测试数据的前 n 列：

n   Time (s)
1   < 1
2   < 1
3   < 1
4   < 1
5   1
6   17

令人担忧的趋势，我相信您会同意。因此我的：

警告

我认为这段代码只不过是一个概念证明：

• 以这种朴素的方式计算行列式的执行时间随着矩阵大小的 O(n^3) 增长
• 此代码重复计算相同的值不进行记忆化
• 绝对没有健全性或错误检查 - 例如，一个不是正方形的矩阵，或者Matrix输入值中的值没有意义，将导致一切 也就是说
• 我没有考虑数值稳定性，而数值稳定性是现实世界数值计算所必需的。

，这是一个有趣的练习，希望能为您提供一些有用的指导，告诉您如何在现实生活中实际实现这一点。

也许稍后我会考虑使用 Cholesky 分解 来实现......