Функции невязки, ошибок

Итерационный процесс решения систем линейных алгебраических уравнений

Решение системы линейных уравнений методом факторизации матрицы

Трехдиагональная линейная система уравнений может быть записана в следующем виде:

a_i*u_i-1-b_i*u_i+c_i*u_i+1+f_i=0,

где 0<=i<N, a₀=c_N-1=0, u - искомое решение.

Матрица этой системы состоит из главной диагонали (с коэффициентами -b_i) и примыкающих к ней сверху и снизу диагоналей (соответственно c_i и a_i).

Прямое (безытерационное) решение этой системы уравнений можно проводить методом ее факторизации (прогонка, или алгоритм Томаса), либо методом последовательного исключения сначала нечетных, затем делящихся на 2, но не на 4, и т.д. уравнений и соответствующего преобразования коэффициентов. Последний метод называется редукцией или бинарным исключением.

Алгоритм Томаса

Решение ищется в виде:

u_i-1=bet_i*u_i+gam_i

В этом случае для bet и gam получаются рекуррентные формулы:

bet_i+1=c_i*fi, gam_i+1=(f_i+a_i*gam_i)*fi, fi=1/(b_i-a_i*bet_i); bet₀=gam₀=0.

По этим формулам вспомогательные массивы вычисляются для i от 1 до N, затем находится u_N-1=gam_N, а затем при известных вспомогательных массивах вычисляются все значения u.

Алгоритм принципиально не может иметь ведущего элемента, и есть вероятность того, что он не сойдется даже для несингулярной матрицы. Для этого в программе, реализующей прогонку, необходимо контролировать значения fi. Еще два замечания: длины рекуррентных цепочек порядка N, поэтому при экспоненциальном накоплении погрешностей (что происходит при преобладании значений |bet_i|>1) прогонка практически обязательно разойдется. Второе: алгоритм сохраняет исходные значения коэффициентов. Доказано, что для устойчивой работы алгоритма Томаса достаточно диагонального преобладания, однако, во многих случаях он сходится и при отсутствии такового.

Итерационные методы решения СЛАУ используются для решения СЛАУ большой размерности с разреженными матрицами, а также для уточнения решения СЛАУ, полученного с помощью прямого метода. Формулировка и применение итерационных методов требует определенных знаний и определенного опыта. Выбор эффективного итерационного метода решения конкретной задачи существенно зависит от ее характерных свойств и от архитектуры вычислительной машины, на которой будет решаться задача. Поэтому никаких общих правил выбора наилучшего итерационного метода решения не существует.

Метод минимизации обобщенной невязки

Итерационный метод минимизации обобщенной невязки также реализован в системе MATLAB. Для этого используется функция gmres:

• gmres (А, В. restart) — возвращает решение X СЛУ А*Х=В. А —квадратная матрица. Функция gmres начинает итерации от начальной оценки, представляющей собой вектор размера и, состоящий из нулей. Итерации производятся либо до сходимости к решению, либо до появления ошибки, либо до достижения максимального числа итераций. Сходимость достигается, когда относительный остаток norm(B-A*X)/norm(B) меньше или равен заданной погрешности (по умолчанию 1е-6). Максимальное число итераций — минимум из n/restart и 10. Функция gmres (...) имеет и ряд других форм записи, аналогичных описанным для функции bieg(...). Пример:

» gmres(A.B)

GMRES(4) converged at Iteration 1(4) to a solution with relative residual le-016

ans =

1.0000

2.0000

3.0000

4.0000

Квазиминимизация невязки — функция qmr

Метод решения СЛУ с квазиминимизацией невязки реализует функция qmr:

• qmr (А, В) — возвращает решение X СЛУ А*Х=Ь. Матрица А должна быть квадратной. Функция qmr начинает итерации от начальной оценки, представляющей собой вектор длиной п, состоящий из нулей. Итерации производятся либо до сходимости метода, либо до появления ошибки, либо до достижения максимального числа итераций. Максимальное число итераций — минимум из п и 20. Функция qmr(...) имеет и ряд других форм записи, аналогичных описанным для функции bi eg (...). Пример:

» qmr(A.B)

QMR converged at iteration 4 to a solution

with relative residual l.le-014

ans =

1.0000

2.0000

3.0000

4.0000

Дата добавления: 2015-04-24