Main Content

pcg

求解线性系统 - 预条件共轭梯度法

说明

示例

x = pcg(A,b) 尝试使用预条件共轭梯度法求解关于 x 的线性系统 A*x = b。如果尝试成功,pcg 会显示一条消息来确认收敛。如果 pcg 无法在达到最大迭代次数后收敛或出于任何原因暂停,则会显示一条包含相对残差 norm(b-A*x)/norm(b) 以及该方法停止时的迭代序号的诊断消息。

示例

x = pcg(A,b,tol) 指定该方法的容差。默认容差是 1e-6

示例

x = pcg(A,b,tol,maxit) 指定要使用的最大迭代次数。如果 pcg 无法在 maxit 次迭代内收敛,将显示诊断消息。

示例

x = pcg(A,b,tol,maxit,M) 指定预条件子矩阵 M 并通过有效求解关于 y 的方程组 H1AHTy=H1b 来计算 x,其中 y=HTxH=M1/2=(M1M2)1/2。该算法不显式形成 H。使用预条件子矩阵可以改善问题的数值属性和计算的效率。

示例

x = pcg(A,b,tol,maxit,M1,M2) 指定预条件子矩阵 M 的因子,使得 M = M1*M2

示例

x = pcg(A,b,tol,maxit,M1,M2,x0) 指定解向量 x 的初始估计值。默认值为由零组成的向量。

示例

[x,flag] = pcg(___) 返回一个标志,指示算法是否成功收敛。当 flag = 0 时,收敛成功。您可以将此输出语法用于之前的任何输入参数组合。如果指定了 flag 输出,pcg 将不会显示任何诊断消息。

示例

[x,flag,relres] = pcg(___) 还会返回相对残差 norm(b-A*x)/norm(b)。如果 flag0,则 relres <= tol

示例

[x,flag,relres,iter] = pcg(___) 还会返回计算出 x 时的迭代序号 iter

示例

[x,flag,relres,iter,resvec] = pcg(___) 还会在每次迭代中返回残差范数向量(包括第一个残差 norm(b-A*x0))。

示例

全部折叠

使用采用默认设置的 pcg 求解系数矩阵为方阵的线性系统,然后在求解过程中调整使用的容差和迭代次数。

创建一个随机对称稀疏矩阵 A。还要为 Ax=b 的右侧创建一个由 A 的行总和组成的向量 b,使得实际解 x 是由 1 组成的向量。

rng default
A = sprand(400,400,.5);
A = A'*A;
b = sum(A,2);

使用 pcg 求解 Ax=b。输出显示包括相对残差 b-Axb 的值。

x = pcg(A,b);
pcg 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 3.6e-06.

默认情况下,pcg 使用 20 次迭代和容差 1e-6,对于此矩阵,算法无法在 20 次迭代后收敛。然而,残差接近容差,因此算法可能只需更多迭代即可收敛。

使用容差 1e-7 和 150 次迭代再次求解方程组。

x = pcg(A,b,1e-7,150);
pcg converged at iteration 129 to a solution with relative residual 1e-07.

检查使用指定了预条件子矩阵的 pcg 来求解线性系统的效果。

创建一个对称正定带状系数矩阵。

A = delsq(numgrid('S',102));

定义 b 作为线性方程 Ax=b 的右侧。

b = ones(size(A,1),1);

设置容差和最大迭代次数。

tol = 1e-8;
maxit = 100;

使用 pcg 根据请求的容差和迭代次数求解。指定五个输出以返回有关求解过程的信息:

  • x 是计算 A*x = b 所得的解。

  • fl0 是指示算法是否收敛的标志。

  • rr0 是计算的解 x 的相对残差。

  • it0 是计算 x 时所用的迭代序号。

  • rv0b-Ax 的残差历史记录组成的向量。

[x,fl0,rr0,it0,rv0] = pcg(A,b,tol,maxit);
fl0
fl0 = 1
rr0
rr0 = 0.0131
it0
it0 = 100

由于 pcg 未在请求的 100 次迭代内收敛至请求的容差 1e-8,因此 fl01

为了有助于缓慢收敛,您可以指定预条件子矩阵。由于 A 是对称矩阵,请使用 ichol 生成预条件子 M=L LT。通过指定 LL' 作为 pcg 的输入,求解预条件方程组。

L = ichol(A);
[x1,fl1,rr1,it1,rv1] = pcg(A,b,tol,maxit,L,L');
fl1
fl1 = 0
rr1
rr1 = 8.0992e-09
it1
it1 = 79

在第 79 次迭代中,使用 ichol 预条件子产生的相对残差小于规定的容差 1e-8 。输出 rv1(1)norm(b)rv1(end)norm(b-A*x1)

现在,使用 michol 选项创建修正的不完全乔列斯基预条件子。

L = ichol(A,struct('michol','on'));
[x2,fl2,rr2,it2,rv2] = pcg(A,b,tol,maxit,L,L');
fl2
fl2 = 0
rr2
rr2 = 9.9614e-09
it2
it2 = 47

该预条件子优于使用零填充不完全乔列斯基分解为本例中的系数矩阵生成的预条件子,因此 pcg 能够更快地收敛。

通过绘制从初始估计值(迭代编号 0)开始的每次残差历史记录,可以查看预条件子如何影响 pcg 的收敛速度。为指定的容差添加一个线条。

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

Figure contains an axes object. The axes object with xlabel Iteration number, ylabel Relative residual contains 4 objects of type line, constantline. These objects represent No Preconditioner, Default ICHOL, Modified ICHOL, Tolerance.

检查向 pcg 提供解的初始估计值的效果。

创建一个三对角稀疏矩阵。使用每行的总和作为 Ax=b 右侧的向量,使 x 的预期解是由 1 组成的向量。

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

使用 pcg 求解 Ax=b 两次:一次是使用默认的初始估计值,一次是使用解的良好初始估计值。对两次求解均使用 200 次迭代和默认容差。将第二种求解中的初始估计值指定为所有元素都等于 0.99 的向量。

maxit = 200;
x1 = pcg(A,b,[],maxit);
pcg converged at iteration 35 to a solution with relative residual 9.5e-07.
x0 = 0.99*e;
x2 = pcg(A,b,[],maxit,[],[],x0);
pcg converged at iteration 7 to a solution with relative residual 8.7e-07.

在这种情况下,提供初始估计值可以使 pcg 更快地收敛。

返回中间结果

您还可以通过在 for 循环中调用 pcg 来使用初始估计值获得中间结果。每次调用求解器都会执行几次迭代,并存储计算出的解。然后,将该解用作下一批迭代的初始向量。

例如,以下代码会循环执行四次,每次执行 100 次迭代,并在 for 循环中每通过一次后均存储解向量:

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

X(:,k) 是在 for 循环的第 k 次迭代时计算的解向量,R(k) 是该解的相对残差。

通过为 pcg 提供用来计算 A*x 的函数句柄(而非系数矩阵 A)来求解线性系统。

使用 gallery 生成一个 20×20 正定三对角矩阵。上对角线和下对角线上的元素都是 1,而主对角线上的元素是从 20 递减到 1。预览该矩阵。

n = 20;
A = gallery('tridiag',ones(n-1,1),n:-1:1,ones(n-1,1));
full(A)
ans = 20×20

    20     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     1    19     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     1    18     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     1    17     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     1    16     1     0     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     1    15     1     0     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     1    14     1     0     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     1    13     1     0     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     1    12     1     0     0     0     0     0     0     0     0     0     0
     0     0     0     0     0     0     0     0     1    11     1     0     0     0     0     0     0     0     0     0
      ⋮

由于此三对角矩阵有特殊的结构,您可以用函数句柄来表示 A*x 运算。当 A 乘以向量时,所得向量中的大多数元素为零。结果中的非零元素对应于 A 的非零三对角元素。此外,只有主对角线具有不等于 1 的非零值。

表达式 Ax 变为:

[2010001191000118100117100116100115100114100113000100011][x1x2x3x4x5x20]=[20x1+x2x1+19x2+x3x2+18x3+x4x18+2x19+x20x19+x20 ].

结果向量可以写为三个向量的和:

[20x1+x2x1+19x2+x3x2+18x3+x4x18+2x19+x20x19+x20 ]=[0x1x19]+[20x119x2x20]+[x2x200]

在 MATLAB® 中,编写一个函数来创建这些向量并将它们相加,从而给出 A*x 的值:

function y = afun(x)
y = [0; x(1:19)] + ...
    [(20:-1:1)'].*x + ...
    [x(2:20); 0];
end

(该函数作为局部函数保存在示例的末尾。)

现在,通过为 pcg 提供用于计算 A*x 的函数句柄,求解线性系统 Ax=b。使用容差 1e-12 和 50 次迭代。

b = ones(20,1);
tol = 1e-12;  
maxit = 50;
x1 = pcg(@afun,b,tol,maxit)
pcg converged at iteration 20 to a solution with relative residual 4.4e-16.
x1 = 20×1

    0.0476
    0.0475
    0.0500
    0.0526
    0.0555
    0.0588
    0.0625
    0.0666
    0.0714
    0.0769
      ⋮

检查 afun(x1) 是否产生由 1 组成的向量。

afun(x1)
ans = 20×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)
y = [0; x(1:19)] + ...
    [(20:-1:1)'].*x + ...
    [x(2:20); 0];
end

输入参数

全部折叠

系数矩阵,指定为对称正定矩阵或函数句柄。该矩阵是线性系统 A*x = b 中的系数矩阵。通常,A 是大型稀疏矩阵或函数句柄,它返回大型稀疏矩阵和列向量的乘积。请参阅判断矩阵是否为对称正定矩阵了解如何确认 A 是对称正定矩阵的信息。

A 指定为函数句柄

您可以选择将系数矩阵指定为函数句柄而不是矩阵。函数句柄返回矩阵向量乘积,而不是构建整个系数矩阵,从而使计算更加高效。

要使用函数句柄,请使用函数签名 function y = afun(x)参数化函数说明如何在必要时为函数 afun 提供附加参数。函数调用 afun(x) 必须返回 A*x 的值。

数据类型: double | function_handle
复数支持:

线性方程的右侧,指定为列向量。b 的长度必须等于 size(A,1)

数据类型: double
复数支持:

方法容差,指定为正标量。计算中使用此输入可在准确度和运行时间之间进行权衡。pcg 必须在允许的迭代次数内满足容差才能成功。较小的 tol 值意味着解必须更精确才能成功完成计算。

数据类型: double

最大迭代次数,指定为正整数标量。增加 maxit 的值,以允许 pcg 进行更多迭代,从而满足容差 tol。通常,较小的 tol 值意味着需要更多迭代才能成功完成计算。

预条件子矩阵,指定为由矩阵或函数句柄组成的单独参数。您可以指定预条件子矩阵 M 或其矩阵因子 M = M1*M2 来改进线性系统的数值方面,使 pcg 更容易快速收敛。您可以使用不完全矩阵分解函数 iluichol 来生成预条件子矩阵。您还可以在分解之前使用 equilibrate 来改进系数矩阵的条件数。有关预条件子的详细信息,请参阅线性方程组的迭代方法

pcg 将未指定的预条件子视为单位矩阵。

M 指定为函数句柄

您可以选择将 MM1M2 中的任一个指定为函数句柄而不是矩阵。函数句柄执行矩阵向量运算,而不是构建整个预条件子矩阵,从而使计算更加高效。

要使用函数句柄,请使用函数签名 function y = mfun(x)参数化函数说明如何在必要时为函数 mfun 提供附加参数。函数调用 mfun(x) 必须返回 M\xM2\(M1\x) 的值。

数据类型: double | function_handle
复数支持:

初始估计值,指定为长度等于 size(A,2) 的列向量。如果您能为 pcg 提供比默认的零向量更合理的初始估计值 x0,则它可以节省计算时间并帮助算法更快地收敛。

数据类型: double
复数支持:

输出参数

全部折叠

线性系统的解,以列向量形式返回。该输出给出线性系统 A*x = b 的近似解。如果计算成功 (flag = 0),则 relres 小于或等于 tol

每当计算不成功 (flag ~= 0) 时,pcg 返回的解 x 是在所有迭代中计算出的残差范数最小的解。

收敛标志,返回下表中的标量值之一。收敛标志指示计算是否成功,并区分几种不同形式的失败。

标志值

收敛

0

成功 - pcgmaxit 次迭代内收敛至所需容差 tol

1

失败 - pcg 执行了 maxit 次迭代,但未收敛。

2

失败 - 预条件子矩阵 MM = M1*M2 为病态。

3

失败 - pcg 在经过两次相同的连续迭代后已停滞。

4

失败 - 由 pcg 算法计算的标量数量之一变得太小或太大,无法继续计算。

相对残差,以标量形式返回。相对残差 relres = norm(b-A*x)/norm(b) 指示解的准确度。如果计算在 maxit 次迭代内收敛于容差 tol,则 relres <= tol

数据类型: double

迭代序号,以标量形式返回。此输出指示计算出 x 的解时所用的迭代序号。

数据类型: double

残差,以向量形式返回。残差 norm(b-A*x) 揭示对于给定的 x 值,算法接近收敛的程度。resvec 中元素的数量等于迭代次数。您可以检查 resvec 的内容,以帮助决定是否更改 tolmaxit 的值。

数据类型: double

详细信息

全部折叠

预条件共轭梯度法

预条件共轭梯度法 (PCG) 旨在利用对称正定矩阵的结构。其他一些算法也可以对对称正定矩阵执行运算,但 PCG 在求解这些类型的方程组方面是最快和最可靠的 [1]

提示

  • 大多数迭代方法的收敛取决于系数矩阵的条件数 cond(A)。当 A 是方阵时,您可以使用 equilibrate 来改进其条件数,它本身就能使大多数迭代求解器更容易收敛。但如果您随后会对经平衡处理的矩阵 B = R*P*A*C 进行因式分解,使用 equilibrate 还可以获得质量更好的预条件子矩阵。

  • 您可以使用矩阵重新排序函数(如 dissectsymrcm)来置换系数矩阵的行和列,并在系数矩阵被分解以生成预条件子时最小化非零值的数量。这可以减少后续求解预条件线性系统所需的内存和时间。

参考

[1] Barrett, R., M. Berry, T. F. Chan, et al., Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, 1994.

扩展功能

版本历史记录

在 R2006a 之前推出