Иллюстрированный самоучитель по MatLab

Решение СЛУ с разреженными матрицами. Точное решение, метод наименьших квадратов и сопряженных градиентов.

Решение СЛУ с разреженными матрицами – хотя и не единственная, но несомненно одна из основных сфер применения аппарата разреженных матриц, описанного в уроке 12. Ниже приведены функции, относящиеся к этой области применения разреженных матриц. Большинство описанных методов относится к итерационным, т. е. к тем, решение которых получается в ходе ряда шагов – итераций, постепенно ведущих к получению результата с заданной погрешностью или с максимальным правдоподобием [33]. Описанные ниже функции MATLAB могут и должны применяться и при решении обычных СЛУ – без разреженных матриц. [Использование всех этих функций, кроме Isqr, как правило, ограничено системами уравнений, в которых А – нормальная квадратная матрица, т. е. А* А – АА*, где А*– сопряженная (эрмитова) матрица А. – Примеч. ред.]

Точное решение, метод наименьших квадратов и сопряженных градиентов

• lsqr(A, В)– возвращает точное решение X СЛУ А*Х=В, если матрица последовательная, в противном случае – возвращает решение, полученное итерационным методом наименьших квадратов. Матрица коэффициентов А должна быть прямоугольной размера тхя, а вектор-столбец правых частей уравнений В должен иметь размер т. Условие m>=n может быть и необязательным. Функция Isqr начинает итерации от начальной оценки, по умолчанию представляющей собой вектор размером n, состоящий из нулей. Итерации производятся или до сходимости к решению, или до появления ошибки, или до достижения максимального числа итераций (по умолчанию равного min(20, m, n) – либо 20, либо числу уравнений, либо числу неизвестных). Сходимость достигается, когда отношение вторых норм векторов norm(B-Ax)/norm(B) меньше или равно погрешности метода tol (по умолчанию 1е-б);
• lsqr(A.B,tol) – возвращает решение с заданной погрешностью (порогом отбора) tol;
• lsqr(A,b.tol.maxlt) – возвращает решение при заданном максимальном числе итераций maxit вместо, возможно, чересчур малого числа, заданного по умолчанию;
• lsqr(A,b.tol.maxit,M) и lsqr(A,b,tol.maxit.M1.M2) – при решении используются матрица предусловий М или М=М1*М2, так что производится решение системы inv(M)*A*x=inv(M)*b относительно х. Если M1 или М2 – пустые матрицы, то они рассматривается как единичные матрицы, что эквивалентно отсутствию входных условий вообще;
• lsqr(A.B,tol.maxit.M1.M2.X0) – точно задается начальное приближение Х0. Если Х0 – пустая матрица, то по умолчанию используется вектор, состоящий из нулей;
• X = lsqr(A,B.tol.maxit,M1.M2.X0) – при наличии единственного выходного параметра возвращает решение X. Если метод Isqr сходится, выводится соответствующее сообщение. Если метод не сходится после максимального числа итераций или по другой причине, на экран выдается относительный остаток попп(В-А*Х)/ norm(B) и номер итерации, на которой метод остановлен;
• [X.flag] = lsqr(A.X.tol.maxit.M1.M2.X0) – возвращает решение X и флаг flag. описывающий сходимость метода;
• [X.flag.relres] = lsqr(A,X,tol.maxit,M1.M2.X0) – также возвращает относительную вторую норму вектора остатков rel res=norm(B-A*X)/norm(B). Если флаг flag равен 0, то relres<tol;
• [X.flag.relres.iter] = bicg(A,B.tol,maxit,M1,M2.X0) – также возвращает номер итерации, на которой был вычислен X. Значение iter всегда удовлетворяет условию 0<iter<maxit;
• [X.flag.relres,iter,resvec]= lsqr(A.B.tol.maxit.M1.M2.X0) – также возвращает вектор вторых норм остатков resvec для каждой итерации начиная с res-vec(l)=norm(B=A*X0). Если флаг flag равен 0, то resvec имеет длину iter+1 и resvec(end)<tol*norm(B). Возможны значения flag, равные 0, 1, 2, 3 и 4. Значения flag предоставляют следующие данные о сходимости решения:
  • flag=0 – решение сходится при заданной точности tol и числе итераций не более заданного maxit;
  • flag=1 – число итераций равно заданному maxit, но сходимость не достигнута;
  • flag=2 – матрица предусловий М плохо обусловлена;
  • flag=3 – процедура решения остановлена, поскольку две последовательные оценки решения оказались одинаковыми;
  • flag=4 – одна из величин в процессе решения вышла за пределы допустимых величин чисел (разрядной сетки компьютера).

Если значение flag больше нуля, то возвращается не последнее решение, а то решение, которое имеет минимальное значение отношения вторых норм векторов norm(B-A*x)/norm(B).

Пример:

Введенные в этом примере матрица А и вектор В будут использованы и в других примерах данного раздела. В примере процесс итераций сходится на пятом шаге с относительным остатком (отношением вторых норм векторов невязки и свободных членов) 1.9 10^-13.

Пример: