Документация

x = lsqr(A,b) попытки решить систему линейных уравнений A*x = b для x использование Метода наименьших квадратов. lsqr находит решение методом наименьших квадратов для x это минимизирует norm(b-A*x). Когда A сопоставимо, решение методом наименьших квадратов является также решением линейной системы. Когда попытка успешна, lsqr отображает сообщение, чтобы подтвердить сходимость. Если lsqr сбои, чтобы сходиться после максимального количества итераций или остановов по любой причине, это отображает диагностическое сообщение, которое включает относительный остаточный norm(b-A*x)/norm(b) и номер итерации, в который остановленный метод.

x = lsqr(A,b,tol) задает допуск к методу. Допуском по умолчанию является 1e-6.

x = lsqr(A,b,tol,maxit) задает максимальное количество итераций, чтобы использовать. lsqr отображает диагностическое сообщение, если ему не удается сходиться в maxit итерации.

x = lsqr(A,b,tol,maxit,M) задает матрицу перед формирователем M и вычисляет x путем эффективного решения системы $A M^{- 1} y = b$ для y, где $y = M x$ . Используя предварительный формирователь матрица может улучшить числовые свойства проблемы и КПД вычисления.

x = lsqr(A,b,tol,maxit,M1,M2) задает факторы матрицы перед формирователем M таким образом, что M = M1*M2.

x = lsqr(A,b,tol,maxit,M1,M2,x0) задает исходное предположение для вектора решения x. Значением по умолчанию является нулевой вектор.

[x,flag] = lsqr(___) возвращает флаг, который задает, сходился ли алгоритм успешно. Когда flag = 0, сходимость была успешна. Можно использовать этот выходной синтаксис с любой из предыдущих комбинаций входных аргументов. Когда вы задаете flag выведите, lsqr не отображает диагностических сообщений.

[x,flag,relres] = lsqr(___) также возвращает остаточную ошибку вычисленного решения x. Если flag 0, затем x решение методом наименьших квадратов, которое минимизирует norm(b-A*x). Если relres мал, затем x также единое решение, начиная с relres представляет norm(b-A*x)/norm(b).

[x,flag,relres,iter] = lsqr(___) также возвращает номер итерации iter в котором x был вычислен.

[x,flag,relres,iter,resvec] = lsqr(___) также возвращает вектор норм невязки в каждой итерации, включая первый остаточный norm(b-A*x0).

[x,flag,relres,iter,resvec,lsvec] = lsqr(___) также возвращает lsvec, который является оценкой масштабированной ошибки нормального уравнения в каждой итерации.

Примеры

Итеративное решение линейной системы

Решите прямоугольную линейную систему с помощью lsqr с настройками по умолчанию, и затем настраивают допуск и количество итераций, используемых в процессе решения.

Создайте случайную разреженную матрицу A с 50%-й плотностью. Также создайте случайный векторный b для правой стороны $Ax = b$ .

rng default
A = sprand(400,300,.5);
b = rand(400,1);

Решить $Ax = b$ использование lsqr. Выходное отображение включает значение относительной остаточной ошибки $\frac{‖ Ax - b ‖}{‖ b ‖}$ .

x = lsqr(A,b);

lsqr stopped at iteration 20 without converging to the desired tolerance 1e-06
because the maximum number of iterations was reached.
The iterate returned (number 20) has relative residual 0.26.

lsqr по умолчанию использование 20 итераций и допуск 1e-6, и алгоритм не может сходиться в тех 20 итерациях для этой матрицы. Поскольку невязка является все еще большой, это - хороший индикатор, что необходимо больше итераций (или матрица перед формирователем). Также можно уменьшать допуск, чтобы облегчить для алгоритма сходиться.

Решите систему снова с помощью допуска 1e-4 и 70 итераций. Задайте шесть выходных параметров, чтобы возвратить относительный остаточный relres из расчетного решения, а также остаточной истории resvec и история невязки наименьших квадратов lsvec.

[x,flag,relres,iter,resvec,lsvec] = lsqr(A,b,1e-4,70);
flag

flag = 0

Начиная с flag 0, алгоритм смог соответствовать желаемому ошибочному допуску в конкретном количестве итераций. Можно обычно настраивать допуск и количество итераций вместе, чтобы сделать компромиссы между скоростью и точностью этим способом.

Исследуйте относительную невязку и невязку наименьших квадратов расчетного решения.

relres

relres = 0.2625

lsres = lsvec(end)

lsres = 2.7640e-04

Эти нормы невязки указывают на тот x решение методом наименьших квадратов, потому что relres не меньше, чем заданный допуск 1e-4. Поскольку никакое единое решение линейной системы не существует, лучшее, которое может сделать решатель, должно заставить невязку наименьших квадратов удовлетворить допуску.

Постройте остаточные истории. Относительный остаточный resvec быстро достигает минимума и не может сделать дальнейшие успехи, в то время как невязка наименьших квадратов lsvec продолжает минимизироваться на последующих итерациях.

N = length(resvec);
semilogy(1:N,lsvec,'--o',1:N,resvec,'-o')
legend("Least-squares residual","Relative residual")

Используя `lsqr` с Предварительным формирователем

Исследуйте эффект использования матрицы перед формирователем с lsqr решить линейную систему.

Загрузите west0479, действительное 479 479 несимметричная разреженная матрица.

load west0479
A = west0479;

Задайте b так, чтобы истинное решение было вектором из всех единиц.

b = sum(A,2);

Установите погрешность и максимальное количество итераций.

tol = 1e-12;
maxit = 20;

Используйте lsqr найти решение в требуемом допуске и количестве итераций. Задайте шесть выходных параметров, чтобы возвратить информацию о процессе решения:

x0 вычисленное решение A*x0 = b.
fl0 флаг, указывающий, сходился ли алгоритм.
rr0 невязка вычисленного ответа x0.
it0 номер итерации когда x0 был вычислен.
rv0 вектор остаточной истории для $‖ Ax - b ‖$ .
lsrv0 вектор истории невязки наименьших квадратов.

[x0,fl0,rr0,it0,rv0,lsrv0] = lsqr(A,b,tol,maxit);
fl0

fl0 = 1

rr0

rr0 = 0.0017

it0

it0 = 20

Начиная с fl0 = 1, алгоритм не сходился к заданному допуску в максимальном количестве итераций.

Чтобы помочь с медленной сходимостью, можно задать матрицу перед формирователем. Начиная с A несимметрично, используйте ilu сгенерировать предварительный формирователь $M = L U$ . Задайте допуск отбрасывания, чтобы проигнорировать недиагональные записи со значениями, меньшими, чем 1e-6. Решите предобусловленную систему $\tilde{A} y = {AM}^{- 1} (M x) = b$ путем определения L и U как вводит к lsqr.

setup = struct('type','ilutp','droptol',1e-6);
[L,U] = ilu(A,setup);
[x1,fl1,rr1,it1,rv1,lsrv1] = lsqr(A,b,tol,maxit,L,U);
fl1

fl1 = 0

rr1

rr1 = 7.0954e-14

it1

it1 = 13

Использование ilu предварительного формирователя производит относительную невязку меньше, чем предписанный допуск 1e-12 в 13-й итерации. Выход rv1(1) norm(b), и выход rv1(end) norm(b-A*x1).

Можно следовать за прогрессом lsqr путем графического вывода относительных остаточных значений в каждой итерации. Постройте остаточную историю каждого решения с линией для заданного допуска.

semilogy(0:length(rv0)-1,rv0/norm(b),'-o')
hold on
semilogy(0:length(rv1)-1,rv1/norm(b),'-o')
yline(tol,'r--');
legend('No preconditioner','ILU preconditioner','Tolerance','Location','East')
xlabel('Iteration number')
ylabel('Relative residual')

Предоставление исходного предположения

Исследуйте эффект предоставления lsqr с исходным предположением решения.

Создайте случайную прямоугольную разреженную матрицу. Используйте сумму каждой строки как вектор для правой стороны $Ax = b$ так, чтобы ожидаемое решение для $x$ вектор из единиц.

A = sprand(700,900,0.1);
b = sum(A,2);

Используйте lsqr решить $Ax = b$ дважды: одно время со значениями опции по умолчанию, и одно время с исходным предположением решения. Используйте 75 итераций в обоих решениях и задайте исходное предположение как вектор со всеми элементами, равными 0,99.

maxit = 75;
x1 = lsqr(A,b,[],maxit);

lsqr converged at iteration 64 to a solution with relative residual 8.7e-07.

x0 = 0.99*ones(size(A,2),1);
x2 = lsqr(A,b,[],maxit,[],[],x0);

lsqr converged at iteration 26 to a solution with relative residual 9.6e-07.

С исходным предположением близко к ожидаемому решению, lsqr может сходиться в меньшем количестве итераций.

Возвращение промежуточных результатов

Также можно использовать исходное предположение, чтобы получить промежуточные результаты путем вызова lsqr в цикле for. Каждый вызов решателя выполняет несколько итераций и хранит расчетное решение. Затем вы используете то решение в качестве начального вектора для следующего пакета итераций.

Например, этот код выполняет 100 итераций четыре раза и хранит вектор решения после каждой передачи в цикле for:

x0 = zeros(size(A,2),1);
tol = 1e-8;
maxit = 100;
for k = 1:4
    [x,flag,relres] = lsqr(A,b,tol,maxit,[],[],x0);
    X(:,k) = x;
    R(k) = relres;
    x0 = x;
end

X(:,k) вектор решения, вычисленный в итерации k из цикла for и R(k) относительная невязка того решения.

Используя указатель на функцию вместо числовой матрицы

Решите линейную систему путем обеспечения lsqr с указателем на функцию, который вычисляет A*x и A'*x вместо матрицы коэффициентов A.

Создайте несимметричную трехдиагональную матрицу. Предварительно просмотрите матрицу.

A = gallery('wilk',21) + diag(ones(20,1),1)

A = 21×21

    10     2     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     1     9     2     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     1     8     2     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     1     7     2     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     1     6     2     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     1     5     2     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     1     4     2     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     1     3     2     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     1     2     2     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     1     1     2     0     0     0     0     0     0     0     0     0     0
      ⋮

Поскольку эта трехдиагональная матрица имеет специальную структуру, можно представлять операцию A*x с указателем на функцию. Как каждая строка A умножает элементы в x, только несколько результатов являются ненулевыми (соответствие ненулям на tridiagonals).

Выражение $A x$ становится:

$A x = [\begin{array}{c} 10 & 2 & 0 & \dots & \dots & 0 \\ 1 & 9 & 2 & 0 & ⋮ \\ 0 & 1 & ⋱ & 2 & 0 \\ ⋮ & 0 & 1 & 0 & ⋱ & ⋱ & ⋮ \\ 0 & ⋱ & 1 & ⋱ & 0 \\ ⋮ & ⋱ & ⋱ & ⋱ & 2 \\ 0 & \dots & \dots & 0 & 1 & 10 \end{array}] [\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ ⋮ \\ ⋮ \\ x_{21} \end{array}] = [\begin{array}{c} {10 x}_{1} + 2 x_{2} \\ x_{1} + 9 x_{2} + 2 x_{3} \\ ⋮ \\ ⋮ \\ x_{19} + 9 x_{20} + 2 x_{21} \\ x_{20} + 10 x_{21} \end{array}]$ .

Итоговый вектор может быть записан как сумма трех векторов:

$A x = [\begin{array}{c} {10 x}_{1} + 2 x_{2} \\ x_{1} + 9 x_{2} + 2 x_{3} \\ ⋮ \\ ⋮ \\ x_{19} + 9 x_{20} + 2 x_{21} \\ x_{20} + 10 x_{21} \end{array}]$ = $[\begin{array}{c} 0 \\ x_{1} \\ x_{2} \\ ⋮ \\ x_{20} \end{array}] + [\begin{array}{c} {10 x}_{1} \\ {9 x}_{2} \\ ⋮ \\ 9 x_{20} \\ 10 x_{21} \end{array}] + 2 \cdot [\begin{array}{c} x_{2} \\ x_{3} \\ ⋮ \\ x_{21} \\ 0 \end{array}]$ .

Аналогично, выражение для $A^{T} x$ становится:

$A^{T} x = [\begin{array}{c} 10 & 1 & 0 & \dots & \dots & 0 \\ 2 & 9 & 1 & 0 & ⋮ \\ 0 & 2 & ⋱ & 1 & 0 \\ ⋮ & 0 & 2 & 0 & ⋱ & ⋱ & ⋮ \\ 0 & ⋱ & 1 & ⋱ & 0 \\ ⋮ & ⋱ & ⋱ & ⋱ & 1 \\ 0 & \dots & \dots & 0 & 2 & 10 \end{array}] [\begin{array}{c} x_{1} \\ x_{2} \\ x_{3} \\ ⋮ \\ ⋮ \\ x_{21} \end{array}] = [\begin{array}{c} {10 x}_{1} + x_{2} \\ {2 x}_{1} + 9 x_{2} + x_{3} \\ ⋮ \\ ⋮ \\ {2 x}_{19} + 9 x_{20} + x_{21} \\ {2 x}_{20} + 10 x_{21} \end{array}]$ .

$A^{T} x = [\begin{array}{c} {10 x}_{1} + x_{2} \\ {2 x}_{1} + 9 x_{2} + x_{3} \\ ⋮ \\ ⋮ \\ {2 x}_{19} + 9 x_{20} + x_{21} \\ {2 x}_{20} + 10 x_{21} \end{array}] = 2 \cdot [\begin{array}{c} 0 \\ x_{1} \\ x_{2} \\ ⋮ \\ x_{20} \end{array}] + [\begin{array}{c} {10 x}_{1} \\ {9 x}_{2} \\ ⋮ \\ 9 x_{20} \\ 10 x_{21} \end{array}] + [\begin{array}{c} x_{2} \\ x_{3} \\ ⋮ \\ x_{21} \\ 0 \end{array}]$ .

В MATLAB® запишите функцию, которая создает эти векторы и добавляет их вместе, таким образом давая значение A*x или A'*x, В зависимости от входа флага:

function y = afun(x,flag)
if strcmp(flag,'notransp') % Compute A*x
    y = [0; x(1:20)] ...
        + [(10:-1:0)'; (1:10)'].*x ...
        + 2*[x(2:end); 0];
elseif strcmp(flag,'transp') % Compute A'*x
    y = 2*[0; x(1:20)] ...
        + [(10:-1:0)'; (1:10)'].*x ...
        + [x(2:end); 0];
end
end

(Эта функция сохранена как локальная функция в конце примера.)

Теперь решите линейную систему $Ax = b$ путем обеспечения lsqr с указателем на функцию, который вычисляет A*x и A'*x. Используйте допуск 1e-6 и 25 итераций. Задать $b$ как суммы строки $A$ так, чтобы истинное решение для $x$ вектор из единиц.

b = full(sum(A,2));
tol = 1e-6;  
maxit = 25;
x1 = lsqr(@afun,b,tol,maxit)

lsqr converged at iteration 21 to a solution with relative residual 5.4e-13.

Локальные функции

function y = afun(x,flag)
if strcmp(flag,'notransp') % Compute A*x
    y = [0; x(1:20)] ...
        + [(10:-1:0)'; (1:10)'].*x ...
        + 2*[x(2:end); 0];
elseif strcmp(flag,'transp') % Compute A'*x
    y = 2*[0; x(1:20)] ...
        + [(10:-1:0)'; (1:10)'].*x ...
        + [x(2:end); 0];
end
end

Входные параметры

`A` — Матрица коэффициентов
матрица | указатель на функцию

Матрица коэффициентов в виде матрицы или указателя на функцию. Эта матрица является матрицей коэффициентов в линейной системе A*x = b. Обычно A большая разреженная матрица или указатель на функцию, который возвращает продукт большой разреженной матрицы и вектор-столбца.

Определение `A` как указатель на функцию

Можно задать матрицу коэффициентов как указатель на функцию вместо матрицы, чтобы сохранить память в вычислении. Указатель на функцию возвращает матричные векторные произведения вместо того, чтобы формировать целую матрицу коэффициентов, делая вычисление более эффективным.

Чтобы использовать указатель на функцию, используйте функциональную подпись function y = afun(x,opt). Параметризация Функций объясняет, как предоставить дополнительные параметры функциональному afun, при необходимости. Функциональный afun должен удовлетворить этим условиям:

afun(x,'notransp') возвращает продукт A*x.
afun(x,'transp') возвращает продукт A'*x.

Пример приемлемой функции:

function y = afun(x,opt,B,C,n)
if strcmp(opt,'notransp')
    y = [B*x(n+1:end); C*x(1:n)];
else
    y = [C'*x(n+1:end); B'*x(1:n)];
end

Функциональный afun использование B и C вычислить любой A*x или A'*x (в зависимости от заданного флага), на самом деле не формируя целую разреженную матрицу A = [zeros(n) B; C zeros(n)]. Это использует шаблон разреженности матрицы, чтобы сохранить память в расчете A*x и A'*x.

Типы данных: double | function_handle
Поддержка комплексного числа: Да

`b` — Правая сторона линейного уравнения
вектор

Правая сторона линейного уравнения в виде вектор-столбца. b должен быть вектор-столбец с длиной, равной size(A,1).

Типы данных: double
Поддержка комплексного числа: Да

`tol` — Допуск метода
`[]` или `1e-6` (значение по умолчанию) | положительная скалярная величина

Допуск метода в виде положительной скалярной величины. Используйте этот вход для точности компромисса и времени выполнения в вычислении. lsqr должен соответствовать допуску в количестве позволенных итераций, чтобы быть успешным. Меньшее значение tol означает, что ответ должен быть более точным для вычисления, чтобы быть успешным.

Типы данных: double

`maxit` — Максимальное количество итераций
`[]` или `min(size(A,1),20)` (значение по умолчанию) | положительное скалярное целое число

Максимальное количество итераций в виде положительного скалярного целого числа. Увеличьте значение maxit позволить больше итераций для lsqr соответствовать допуску tol. Обычно меньшее значение tol средние значения больше итераций требуются, чтобы успешно завершать вычисление.

`M`, `M1`, `M2` — Матрицы перед формирователем (в качестве отдельных аргументов)
`eye(size(A))` (значение по умолчанию) | матрицы | указатели на функцию

Матрицы перед формирователем в виде отдельных аргументов матриц или указателей на функцию. Можно задать матрицу перед формирователем M или его матричные факторы M = M1*M2 улучшить числовые аспекты линейной системы и облегчить для lsqr сходиться быстро. Можно использовать неполные матричные функции факторизации ilu и ichol сгенерировать матрицы перед формирователем. Также можно использовать equilibrate до факторизации, чтобы улучшить число обусловленности матрицы коэффициентов. Для получения дополнительной информации о предварительных формирователях смотрите Итерационные методы для Линейных систем.

lsqr обрабатывает незаданные предварительные формирователи как единичные матрицы.

Определение `M` как указатель на функцию

Можно задать любой M, M1, или M2 как указатели на функцию вместо матриц, чтобы сохранить память в вычислении. Указатель на функцию выполняет матрично-векторные операции вместо того, чтобы формировать целую матрицу перед формирователем, делая вычисление более эффективным.

Чтобы использовать указатель на функцию, сначала создайте функцию с подписью function y = mfun(x,opt). Параметризация Функций объясняет, как предоставить дополнительные параметры функциональному mfun, при необходимости. Функциональный mfun должен удовлетворить этим условиям:

mfun(x,'notransp') возвращает значение M\x или M2\(M1\x).
mfun(x,'transp') возвращает значение M'\x или M1'\(M2'\x).

Пример приемлемой функции:

function y = mfun(x,opt,a,b)  
if strcmp(opt,'notransp')
    y = x.*a;
else
    y = x.*b;
end
end

В этом примере функциональный mfun использование a и b вычислить любой M\x = x*a или M'\x = x*b (в зависимости от заданного флага), на самом деле не формируя целую разреженную матрицу M.

Типы данных: double | function_handle
Поддержка комплексного числа: Да

`x0` — Исходное предположение
`[]` или вектор-столбец из нулей (значение по умолчанию) | вектор-столбец

Исходное предположение в виде вектор-столбца с длиной равняется size(A,2). Если можно обеспечить lsqr с более разумным исходным предположением x0 чем нулевой вектор по умолчанию затем это может сохранить время вычисления и помочь алгоритму сходиться быстрее.

Типы данных: double
Поддержка комплексного числа: Да

Выходные аргументы

`x` — Решение для линейной системы
вектор

Решение для линейной системы, возвращенное как вектор. Этот выход дает приближенное решение линейной системы A*x = b.

Если flag 0 и relres <= tol, затем x единое решение A*x = b.
Если flag 0 но relres > tol, затем x решение методом наименьших квадратов, которое минимизирует norm(b-A*x).

Каждый раз, когда вычисление не успешно (flag ~= 0), решение x возвращенный lsqr тот с минимальной невязкой нормы, вычисленной по всем итерациям.

`flag` — Флаг Convergence
скаляр

Флаг Convergence, возвращенный как одно из скалярных значений в этой таблице. Флаг сходимости указывает, было ли вычисление успешно и дифференцируется между несколькими различными формами отказа.

Флаговое значение	Сходимость
0	Успех — `lsqr` сходившийся к желаемому допуску `tol` в `maxit` итерации.
1	Отказ — `lsqr` выполненный с помощью итераций `maxit` итерации, но не сходились.
2	Отказ — матрица перед формирователем `M` или `M = M1*M2` isIllConditioned.
3	Отказ — `lsqr` застоявшийся после того, как две последовательных итерации были тем же самым.
4	Отказ — Один из скаляров, вычисленных `lsqr` алгоритм стал слишком маленьким или слишком большим, чтобы продолжить вычислять.

`relres` — Относительная остаточная ошибка
скаляр

Относительная остаточная ошибка, возвращенная как скаляр. Относительная остаточная ошибка является индикацией относительно как точный данный ответ x . lsqr отслеживает относительную невязку и невязку наименьших квадратов в каждой итерации в процессе решения, и алгоритм сходится, когда любая невязка соответствует заданному допуску tol. relres выведите содержит значение невязки, которая сходилась, или относительная невязка или невязка наименьших квадратов:

Относительная остаточная ошибка равна norm(b-A*x)/norm(b) и обычно невязка, которая соответствует допуску tol когда lsqr сходится. resvec выведите отслеживает историю этой невязки по всем итерациям.
Остаточная ошибка наименьших квадратов равна norm((A*inv(M))'*(B-A*X))/norm(A*inv(M),'fro'). Эта невязка вызывает lsqr сходиться менее часто, чем относительная невязка. lsvec выведите отслеживает историю этой невязки по всем итерациям.

`iter` — Номер итерации
скаляр

Номер итерации, возвращенный как скаляр. Этот выход указывает на номер итерации в который вычисленный ответ для x был вычислен.

Типы данных: double

`resvec` — Остаточная ошибка
вектор

Остаточная ошибка, возвращенная как вектор. Остаточная ошибка norm(b-A*x) показывает, как близко алгоритм к схождению для данного значения x. Число элементов в resvec равно количеству итераций. Можно исследовать содержимое resvec помочь решить, изменить ли значения tol или maxit.

Типы данных: double

`lsvec` — Масштабированная ошибка нормального уравнения
вектор

Масштабированная ошибка нормального уравнения, возвращенная как вектор. Для каждой итерации, lsvec содержит оценку масштабированной невязки нормального уравнения norm((A*inv(M))'*(B-A*X))/norm(A*inv(M),'fro'). Число элементов в lsvec равно количеству итераций.

Больше о