Как решить линейную систему только для одного компонента в MATLAB - PullRequest
Новая
       30

Как решить линейную систему только для одного компонента в MATLAB

0 голосов
/ 31 мая 2018

Мне нужно решить линейную систему 

A x = b

, которая может быть эффективно выполнена с помощью 

x = A \ b

Но теперь A очень велика, и мне действительно нужен только один компонент,скажем x(1).Есть ли способ решить эту проблему более эффективно, чем вычислить все компоненты x?

A не редкость.Здесь эффективность на самом деле является проблемой, потому что это делается для многих b.

Кроме того, сохранение инверсии K и умножение только ее первой строки на b невозможно, поскольку Kплохо обусловлен.При использовании оператора \ в этом случае используется решатель LDL, и при явном использовании обратного теряется точность.

Ответы [ 2 ]

0 голосов
/ 31 мая 2018

Метод mldivide, обычно представляемый как \, допускает решение множества систем с одним и тем же A одновременно.

x = A\[b1 b2 b3 b4] # where bi are vectors with n rows

Решает систему для каждого b и возвращает матрицу nx4, где каждый столбец является решением каждого b.Вызов mldivide, подобный этому, должен повысить эффективность, потому что декомпозиция выполняется только один раз.

Как и во многих разложениях, таких как LU o LDL '(и в той, которая вас интересует), матричное умножение x имеет верхнюю диагональпервое решаемое значение - x(n).Однако, при необходимости выполнить декомпозицию LDL, простой алгоритм обратной замены не будет узким местом кода.Следовательно, разложение можно сохранить, чтобы избежать повторения расчета для каждого bi.Таким образом, код будет выглядеть примерно так: 

[LA,DA] = ldl(A);
DA = sparse(DA);
% LA = sparse(LA); %LA can also be converted to sparse matrix
% loop over bi
  xi = LA'\(DA\(LA\bi));
% end loop

Как вы можете видеть в документации по mldivide ( Алгоритмы, раздел ), он выполняет некоторые проверки входных матриц и, имеяLA определяется как полное, а DA - как разреженное, оно должно напрямую указывать на треугольный решатель и трехдиагональный решатель.Если бы LA был преобразован в разреженный, он также использовал бы треугольный решатель, и я не знаю, будет ли преобразование в разреженный представлять какое-либо улучшение.

0 голосов
/ 31 мая 2018

Я не думаю, что вы технически получите ускорение по сравнению с очень оптимизированной подпрограммой Matlab, однако, если вы понимаете, как она решается, вы можете просто решить для одной части x.Например, следующий. в традиционном солвере, например, вы используете backsub для QR-решения.В LU решить использовать как задний саб и передний саб.Я мог бы получить LU.К сожалению, это фактически начинается в конце из-за того, как это решает это.То же самое относится и к ЛПНП, который будет использовать оба.Это не исключает того факта, что могут быть более эффективные способы решения того, что у вас есть.

 function [Q,R] = qrcgs(A)
%Classical Gram Schmidt for an m x n matrix 

[m,n] = size(A); 
% Generates the Q, R matrices
Q = zeros(m,n); 
R = zeros(n,n);
    for k = 1:n
        % Assign the vector for normalization
        w = A(:,k);
        for j=1:k-1
            % Gets R entries
            R(j,k) = Q(:,j)'*w;
        end

        for j = 1:k-1
           % Subtracts off orthogonal projections 
           w = w-R(j,k)*Q(:,j);
        end
        % Normalize 
        R(k,k) = norm(w);
        Q(:,k) = w./R(k,k);
    end

end

function x = backsub(R,b)
% Backsub for upper triangular matrix.
[m,n] = size(R);
p = min(m,n);
x  = zeros(n,1);

    for i=p:-1:1
        % Look from bottom, assign to vector
        r = b(i);
        for j=(i+1):p
            % Subtract off the difference
            r = r-R(i,j)*x(j);
        end
        x(i) = r/R(i,i);
    end

end
...