Метод квази-минимальных невязок
x = qmr (A, b)
qmr (A, b, tol)
qmr (A, b, tol, maxit)
qmr (A, b, tol, maxit, M)
qmr (A, b, tol, maxit, M1, M2)
qmr (A, b, tol, maxit, M1, M2, x0)
[x, флаг] = qmr (A, b...)
[x, флаг, relres] = qmr (A, b...)
[x, флаг, relres, проход] = qmr (A, b...)
[x, флаг, relres, проход, resvec] = qmr (A, b...)
x = qmr(A,b) пытается решить систему линейных уравнений A*x=b для x. n-by-n матрица коэффициентов A должен быть квадратным и должен быть большим и разреженным. Вектор - столбец b должен иметь длину n. Можно задать A как указатель на функцию, afun, такой, что afun(x,'notransp') возвращает A*x, и afun(x,'transp') возвращает A'*x.
Параметризация Функций объясняет, как предоставить дополнительные параметры функциональному afun, а также функцию перед формирователем mfun, описанный ниже, при необходимости.
Если qmr сходится, сообщение к тому эффекту отображено. Если qmr не удается сходиться после максимального количества итераций или остановов по любой причине, предупреждающее сообщение распечатано, отобразив относительный остаточный norm(b-A*x)/norm(b) и номер итерации в который метод, остановленный или не пройдено.
qmr(A,b,tol) задает допуск метода. Если tol является [], то qmr использует значение по умолчанию, 1e-6.
qmr(A,b,tol,maxit) задает максимальное количество итераций. Если maxit является [], то qmr использует значение по умолчанию, min(n,20).
qmr(A,b,tol,maxit,M) и предварительные формирователи использования qmr(A,b,tol,maxit,M1,M2) M или M = M1*M2 и эффективно решают систему inv(M)*A*x = inv(M)*b для x. Если M является [] затем, qmr не применяет предварительного формирователя. M может быть указателем на функцию mfun, таким образом, что mfun(x,'notransp') возвращает M\x, и mfun(x,'transp') возвращает M'\x.
qmr(A,b,tol,maxit,M1,M2,x0) задает исходное предположение. Если x0 является [], то qmr использует значение по умолчанию, весь нулевой вектор.
[x,flag] = qmr(A,b,...) также возвращает флаг сходимости.
Флаг | Сходимость |
|---|---|
|
|
|
|
| Предварительный формирователь |
| Метод застоялся. (Два последовательных выполняют итерации, было то же самое.) |
| Один из скаляров, вычисленных во время |
Каждый раз, когда flag не является 0, решение, возвращенный x то, что с минимальной невязкой нормы, вычисленной по всем итерациям. Никакие сообщения не отображены, если flag вывод задан.
[x,flag,relres] = qmr(A,b,...) также возвращает относительный остаточный norm(b-A*x)/norm(b). Если flag является 0, relres <= tol.
[x,flag,relres,iter] = qmr(A,b,...) также возвращает номер итерации, в котором x был вычислен, где 0 <= iter <= maxit.
[x,flag,relres,iter,resvec] = qmr(A,b,...) также возвращает вектор остаточных норм в каждой итерации, включая norm(b-A*x0).
Этот пример показывает, как использовать qmr с матричным входным параметром. Код:
n = 100; on = ones(n,1); A = spdiags([-2*on 4*on -on],-1:1,n,n); b = sum(A,2); tol = 1e-8; maxit = 15; M1 = spdiags([on/(-2) on],-1:0,n,n); M2 = spdiags([4*on -on],0:1,n,n); x = qmr(A,b,tol,maxit,M1,M2);
отображения сообщение:
qmr converged at iteration 9 to a solution... with relative residual 5.6e-009
Этот пример заменяет матричный A в предыдущем примере с указателем на функцию матричного векторного произведения afun. Пример содержится в файле run_qmr это
Вызовы qmr с указателем на функцию @afun в качестве его первого аргумента.
Содержит afun как вложенную функцию, так, чтобы все переменные в run_qmr были доступны afun.
Следующее показывает код для run_qmr:
function x1 = run_qmr
n = 100;
on = ones(n,1);
A = spdiags([-2*on 4*on -on],-1:1,n,n);
b = sum(A,2);
tol = 1e-8;
maxit = 15;
M1 = spdiags([on/(-2) on],-1:0,n,n);
M2 = spdiags([4*on -on],0:1,n,n);
x1 = qmr(@afun,b,tol,maxit,M1,M2);
function y = afun(x,transp_flag)
if strcmp(transp_flag,'transp') % y = A'*x
y = 4 * x;
y(1:n-1) = y(1:n-1) - 2 * x(2:n);
y(2:n) = y(2:n) - x(1:n-1);
elseif strcmp(transp_flag,'notransp') % y = A*x
y = 4 * x;
y(2:n) = y(2:n) - 2 * x(1:n-1);
y(1:n-1) = y(1:n-1) - x(2:n);
end
end
endКогда вы входите
x1=run_qmr;
MATLAB отображает сообщение
qmr converged at iteration 9 to a solution with relative residual 5.6e-009
Этот пример демонстрирует использование предварительного формирователя.
Загрузите A = west0479, действительное 479 479 несимметричная разреженная матрица.
load west0479;
A = west0479;Задайте b так, чтобы истинное решение было вектором из всех единиц.
b = full(sum(A,2));
Установите допуск и максимальное количество итераций.
tol = 1e-12; maxit = 20;
Используйте qmr, чтобы найти решение в требуемом допуске и количестве итераций.
[x0,fl0,rr0,it0,rv0] = qmr(A,b,tol,maxit);
fl0 равняется 1, потому что qmr не сходится к требуемому допуску 1e-12 в требуемых 20 итерациях. Семнадцатые выполняют итерации, лучшее приближенное решение и тот, возвращенный, как обозначено it0 = 17. MATLAB хранит остаточную историю в rv0.
Постройте график поведения qmr.
semilogy(0:maxit,rv0/norm(b),'-o'); xlabel('Iteration number'); ylabel('Relative residual');
График показывает, что решение не сходится. Можно использовать предварительный формирователь, чтобы улучшить результат.
Создайте предварительный формирователь с ilu, поскольку матричный A несимметричен.
[L,U] = ilu(A,struct('type','ilutp','droptol',1e-5));
Error using ilu There is a pivot equal to zero. Consider decreasing the drop tolerance or consider using the 'udiag' option.
MATLAB не может создать неполный LU, когда это привело бы к сингулярному фактору, который бесполезен как предварительный формирователь.
Можно попробовать еще раз с уменьшенным допуском отбрасывания, как обозначено сообщением об ошибке.
[L,U] = ilu(A,struct('type','ilutp','droptol',1e-6)); [x1,fl1,rr1,it1,rv1] = qmr(A,b,tol,maxit,L,U);
fl1 0, потому что qmr управляет относительной невязкой к 4.1410e-014 (значение rr1). Относительная невязка является меньше, чем предписанный допуск 1e-12 в шестой итерации (значение it1), когда предобусловленный неполной LU-факторизацией с допуском отбрасывания 1e-6. Выводом rv1(1) является norm(b), и выводом rv1(7) является norm(b-A*x2).
Можно следовать, прогресс qmr путем графического изображения относительных невязок в каждой итерации, начинающей с первоначальной сметы (выполните итерации номера 0).
semilogy(0:it1,rv1/norm(b),'-o'); xlabel('Iteration number'); ylabel('Relative residual');
[1] Барретт, Ягода R., M., Т. F. Чан, и др., Шаблоны для Решения Линейных систем: Стандартные блоки для Итеративных Методов, SIAM, Филадельфия, 1994.
[2] Freund, Роланд В. и Неель М. Нэчтигэл, “QMR: метод квази-минимальных невязок для неэрмитовых линейных систем”, SIAM Journal: Numer. Математика. 60, 1991, стр 315–339.