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

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

• lsqr(A, В)—возвращает точное решение X СЛУ А*Х=В, если матрица последовательная, в противном случае — возвращает решение, полученное итерационным методом наименьших квадратов. Матрица коэффициентов А должна быть прямоугольной размера тхя, а вектор-столбец правых частей уравнений В должен иметь размер т. Условие m>=n может быть и необязательным. Функция 1 sqr начинает итерации от начальной оценки, по умолчанию представляющей собой вектор размером п, состоящий из нулей. Итерации производятся или до сходимости к решению, или до появления ошибки, или до достижения максимального числа итераций (по умолчанию равного 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.Ml.M2) — при решении используются матрица предусловий М или М=М1*М2, так что производится решение системы inv(M)*A*x=inv(M)*b относительно х. Если Ml или М2 — пустые матрицы, то они рассматривается как единичные матрицы, что эквивалентно отсутствию входных условий вообще;

• lsqr(A.B,tol .maxit.Ml.M2.X0) — точно задается начальное приближение Х0. Если Х0 — пустая матрица, то по умолчанию используется вектор, состоящий из нулей;

• X = lsqr(A,B.tol .maxit,Ml.M2.X0) — при наличии единственного выходного параметра возвращает решение X. Если метод 1 sqr сходится, выводится соответствующее сообщение. Если метод не сходится после максимального числа итераций или по другой причине, на экран выдается относительный остаток попп(В-А*Х)/ norm(B) и номер итерации, на которой метод остановлен;

• [X.flag] = lsqr(A.X.tol.maxit.Ml.M2.X0) — возвращает решение X и флаг flag. описывающий сходимость метода;

• [X.flag.relres] = lsqr(A,X,tol.maxit,Ml.M2.X0) — также возвращает относительную вторую норму вектора остатков rel res=norm(B-A*X)/norm(B). Если флаг flag равен 0, то relres<tol;

• [X.flag.relres.iter] = bicg(A,B.tol,maxit,Ml,M2.X0) — также возвращает номер итерации, на которой был вычислен X. Значение iter всегда удовлетворяет условию 0<iter<maxit;

• [X.flag.relres,iter,resvec]= lsqr(A.B.tol.maxit.Ml.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=l - число итераций равно заданному maxit, но сходимость не достигнута;

  • flag=2 - матрица предусловий М плохо обусловлена;

  • flag=3 - процедура решения остановлена, поскольку две последовательные оценки решения оказались одинаковыми;

  • fl ag=4 - одна из величин в процессе решения вышла за пределы допустимых величин чисел (разрядной сетки компьютера).

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

Пример:

» А=[0 012; 1300; 0101; 1010];

» В=[11; 7; 6; 4];

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

Пример:

» lsqr(A,B.1e-6.5)

Isqr converged at iteration 5 to a solution

with relative residual 

1.9e-013 

ans =

1.0000 

2.0000 

3.0000

4.0000