最陡下降以找到具有希尔伯特矩阵的线性系统的解

Question

我正在使用最速下降法来找出具有5x5希尔伯特矩阵的线性系统的解.我相信代码很好,因为它给了我正确的答案.

我的问题是:

1. 我认为这需要太多的迭代才能得到正确的答案.我相信我可能错过了算法中的一些东西,但我不知道此时是什么.

2. 我不确定这是否是实现算法的最有效方法,另外,选择"tol"有点令人困惑.

任何有关这些的见解将不胜感激(尤其是1.).谢谢!

% Method of Steepest Descent with tol 10^-6
h = hilb(5);                            %Hilbert 5x5 matrix
b = [1;1;1;1;1];                        %solution matrix
solution = zeros(d,1);                  %Initialization 
residual = h*solution - b;
tol = 10^(-6)
count = 0; 

while residual'*residual > tol;
    roe = (residual'*residual)/(residual'*h*residual);
    solution = solution - roe*residual;
    residual = h*solution - b;
    count = count + 1;
end

count 
solution 


%Method of Steepest Descent with tol 10^-12
solution = zeros(d,1);
residual = h*solution - b;
tol = 10^(-12)
count = 0; 

while residual'*residual > tol;
    roe = (residual'*residual)/(residual'*h*residual);
    solution = solution - roe*residual;
    residual = residual - roe*h*residual;
    count = count + 1;
end

count
solution

%another_solution = invhilb(5)*b           %Check for solution

Answer 1

我没有从数学方面处理你的问题的知识，但从编程的角度来看，我可以注意到一点。

确实你是对的。它需要太多迭代才能得到结果：

Elapsed time is 6.487824 seconds.

count =

      292945

当您定义步长以接近最终结果时，必须优化步长。否则，你要么接近答案的速度太慢，要么因为步长太大而多次经过最佳答案并围绕它进行锯齿形调整。

为了优化步长，我首先根据您的脚本形成一个函数（加上一些小的修改）：

function [solution, count, T] = SDhilb(d, step)
h = hilb(d);
tic
b = ones(d, 1);
solution = zeros(d, 1);
residual = h * solution - b;
res2 = residual' * residual;
tol = 10^(-6);
count = 0;
while res2 > tol;
    roe = res2/(residual' * h * residual);
    solution = solution - step * roe * residual; % here the step size appears
    residual = h * solution - b;
    count = count + 1;
    res2 = residual' * residual; % let's calculate this once per iteration
end
T = toc;

现在将此函数用于一系列步长 (0.1:0.1:1.3) 和几个希尔伯特矩阵 (d = 2, 3, 4, 5)，很明显这1不是一个有效的步长：

相反，step = 0.9似乎效率要高得多。让我们看看在以下情况下它的效率如何hilb(5)：

[result, count, T] = SDhilb(5, 0.9)

result =

    3.1894
  -85.7689
  481.4906
 -894.8742
  519.5830


count =

        1633


T =

    0.0204

速度快了两个数量级以上。

以类似的方式，您可以尝试不同的值，tol看看它对速度的影响有多大。在这种情况下，没有最佳值：容差越小，需要等待的时间就越长。