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

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

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

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

x = bicg(A,b);

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

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

Снова решить систему с помощью допуска 1e-4 и 100 итераций.

x = bicg(A,b,1e-4,100);

bicg stopped at iteration 100 without converging to the desired tolerance 0.0001
because the maximum number of iterations was reached.
The iterate returned (number 7) has relative residual 0.45.

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

Вычислите неполную факторизацию Холесского A, и использовать L' коэффициент как вход предкондиционера для bicg.

L = ichol(A);
x = bicg(A,b,1e-4,100,L');

bicg converged at iteration 58 to a solution with relative residual 7.8e-05.

Использование предкондиционера улучшает числовые свойства задачи достаточно, чтобы bicg способен сходиться.

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

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

load west0479
A = west0479;

Определите b чтобы истинное решение $\mathrm{Ax}=\mathit{b}$ является вектором всех таковых.

b = sum(A,2);

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

tol = 1e-12;
maxit = 20;

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

[x,fl0,rr0,it0,rv0] = bicg(A,b,tol,maxit);
fl0

fl0 = 1

rr0

rr0 = 1

it0

it0 = 0

fl0 равен 1, потому что bicg не сходится к запрошенному допуску 1e-12 в пределах запрошенных 20 итераций. На самом деле, поведение bicg настолько плох, что начальное предположение x0 = zeros(size(A,2),1) является лучшим решением и возвращается, как указано it0 = 0.

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

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

fl1 = 0

rr1

rr1 = 4.1336e-14

it1

it1 = 6

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

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

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')

Исследуйте эффект подачи bicg с начальным угадыванием решения.

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

n = 900;
e = ones(n,1);
A = spdiags([e 2*e e],-1:1,n,n);
b = sum(A,2);

Использование bicg решить $\mathrm{Ax}=\mathit{b}$ дважды: один раз с начальным предположением по умолчанию и один раз с хорошим начальным предположением решения. Используйте 200 итераций и допуск по умолчанию для обоих решений. Задайте начальное предположение во втором решении как вектор со всеми элементами, равными 0.99.

maxit = 200;
x1 = bicg(A,b,[],maxit);

bicg converged at iteration 35 to a solution with relative residual 9.5e-07.

x0 = 0.99*e;
x2 = bicg(A,b,[],maxit,[],[],x0);

bicg converged at iteration 7 to a solution with relative residual 8.7e-07.

В этом случае подача начального предположения включает bicg чтобы сходиться быстрее.

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

Решить линейную систему путем предоставления bicg с указателем на функцию, который вычисляет 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 умножает вектор, большинство элементов получившегося вектора являются нулями. Ненулевые элементы в результате соответствуют ненулевым триидиагональным элементам A.

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

$\mathit{A}\mathit{x}=\left[\begin{array}{ccccccc}10& 2& 0& \cdots & & \cdots & 0\\ 1& 9& 2& 0& & & ⋮\\ 0& 1& \ddots & 2& 0& & \\ ⋮& 0& 1& 0& \ddots & \ddots & ⋮\\ & & 0& \ddots & 1& \ddots & 0\\ ⋮& & & \ddots & \ddots & \ddots & 2\\ 0& \cdots & & \cdots & 0& 1& 10\end{array}\right]\left[\begin{array}{c}{\mathit{x}}_1\\ {\mathit{x}}_2\\ {\mathit{x}}_3\\ ⋮\\ ⋮\\ {\mathit{x}}_{21}\end{array}\right]=\left[\begin{array}{c}{10\mathit{x}}_1+2{\mathit{x}}_2\\ {\mathit{x}}_1+9{\mathit{x}}_2+2{\mathit{x}}_3\\ ⋮\\ ⋮\\ {\mathit{x}}_{19}+9{\mathit{x}}_{20}+2{\mathit{x}}_{21}\\ {\mathit{x}}_{20}+10{\mathit{x}}_{21}\end{array}\right]$.

Получившийся вектор может быть записан как сумма трех векторов:

$\mathit{A}\mathit{x}=\left[\begin{array}{c}{10\mathit{x}}_1+2{\mathit{x}}_2\\ {\mathit{x}}_1+9{\mathit{x}}_2+2{\mathit{x}}_3\\ ⋮\\ ⋮\\ {\mathit{x}}_{19}+9{\mathit{x}}_{20}+2{\mathit{x}}_{21}\\ {\mathit{x}}_{20}+10{\mathit{x}}_{21}\end{array}\right]$=$\left[\begin{array}{c}0\\ {\mathit{x}}_1\\ {\mathit{x}}_2\\ ⋮\\ {\mathit{x}}_{20}\end{array}\right]+\left[\begin{array}{c}{10\mathit{x}}_1\\ {9\mathit{x}}_2\\ ⋮\\ 9{\mathit{x}}_{20}\\ 10{\mathit{x}}_{21}\end{array}\right]+2\cdot \left[\begin{array}{c}{\mathit{x}}_2\\ {\mathit{x}}_3\\ ⋮\\ {\mathit{x}}_{21}\\ 0\end{array}\right]$.

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

${\mathit{A}}^{\mathit{T}}\mathit{x}=\left[\begin{array}{ccccccc}10& 1& 0& \cdots & & \cdots & 0\\ 2& 9& 1& 0& & & ⋮\\ 0& 2& \ddots & 1& 0& & \\ ⋮& 0& 2& 0& \ddots & \ddots & ⋮\\ & & 0& \ddots & 1& \ddots & 0\\ ⋮& & & \ddots & \ddots & \ddots & 1\\ 0& \cdots & & \cdots & 0& 2& 10\end{array}\right]\left[\begin{array}{c}{\mathit{x}}_1\\ {\mathit{x}}_2\\ {\mathit{x}}_3\\ ⋮\\ ⋮\\ {\mathit{x}}_{21}\end{array}\right]=\left[\begin{array}{c}{10\mathit{x}}_1+{\mathit{x}}_2\\ {2\mathit{x}}_1+9{\mathit{x}}_2+{\mathit{x}}_3\\ ⋮\\ ⋮\\ {2\mathit{x}}_{19}+9{\mathit{x}}_{20}+{\mathit{x}}_{21}\\ {2\mathit{x}}_{20}+10{\mathit{x}}_{21}\end{array}\right]$.

${\mathit{A}}^{\mathit{T}}\mathit{x}=\left[\begin{array}{c}{10\mathit{x}}_1+{\mathit{x}}_2\\ {2\mathit{x}}_1+9{\mathit{x}}_2+{\mathit{x}}_3\\ ⋮\\ ⋮\\ {2\mathit{x}}_{19}+9{\mathit{x}}_{20}+{\mathit{x}}_{21}\\ {2\mathit{x}}_{20}+10{\mathit{x}}_{21}\end{array}\right]=2\cdot \left[\begin{array}{c}0\\ {\mathit{x}}_1\\ {\mathit{x}}_2\\ ⋮\\ {\mathit{x}}_{20}\end{array}\right]+\left[\begin{array}{c}{10\mathit{x}}_1\\ {9\mathit{x}}_2\\ ⋮\\ 9{\mathit{x}}_{20}\\ 10{\mathit{x}}_{21}\end{array}\right]+\left[\begin{array}{c}{\mathit{x}}_2\\ {\mathit{x}}_3\\ ⋮\\ {\mathit{x}}_{21}\\ 0\end{array}\right]$.

В 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

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

Теперь решите линейную систему $\mathrm{Ax}=\mathit{b}$ путем предоставления bicg с указателем на функцию, который вычисляет A*x и A'*x. Используйте допуск 1e-6 и 25 итераций. Определить $\mathit{b}$ как суммы строк $\mathit{A}$ так что истинное решение для $\mathit{x}$ является вектором таковых.

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

bicg converged at iteration 19 to a solution with relative residual 4.8e-07.

x1 = 21×1

    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
    1.0000
      ⋮

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