Решение системы уравнений методом скорейшего спуска

Решение систем линейных алгебраических уравнений

Страницы работы

Содержание работы

Лабораторная работа №3

Решение систем линейных алгебраических уравнений

Практика использования итерационных методов решения системы линейных алгебраических уравнений. Сравнительный анализ методов.

Решить систему линейных алгебраических уравнений (САУ)

, , ,

итерационными методами Зейделя и наискорейшего спуска с точностью до e = 0,001. Для сравнения с истинными значениями корней выполнить решение указанной САУ методом Гаусса.

Общий вид алгоритма Зейделя и наискорейшего спуска

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

Расчетные соотношения метода Зейделя для подготовленной системы уравнений (4.13) имеют вид

,(4.18)

.

При составлении программы для вычислений на ЭВМ вместо соотношения (4.18) удобнее использовать выражение, в котором фигурируют элементы исходной системы уравнений

,

.

Если матрица симметрическая и положительно определенная, а подготовленная к итерациям система определяется в виде

(4.13)

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

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

.

Метод наискорейшего спуска. Данный метод относится к группе нелинейных градиентных алгоритмов. Градиентные алгоритмы, уточнение решения в которых осуществлялось по отдельным координатам, предполагают траекторию движения к истинному решению сразу по всем координатам по линии наискорейшего спуска в направлении, противоположном вектору градиента функционала, связанного с ошибкой между истинным решением и решением на -й итерации. Именно такой выбор направления обеспечивает наиболее быстрое убывание функционала ошибки. Вычислительная схема метода наискорейшего спуска выглядит следующим образом. Задаются некоторым начальным приближением (если нет никакой априорной информации, то полагают ), а далее осуществляется итерационный процесс уточнения

, (4.19)

где — вектор невязки, представляющий собой ошибку в виде разности между правой и левой частями системы уравнений, компоненты которого определяются как

, (4.20)

. (4.21)

Чтобы упростить процедуру определения вектора невязки, особенно при больших порядках матрицы системы уравнений, рекомендуется вычислять его по формуле

.

Однако из-за наличия вычислительных погрешностей векторы после нескольких итераций могут отклоняться от истинных невязок и потому время от времени их следует корректировать по выражению (4.20).

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

SUBROUTINE N1YMGS (A,B,N,G,X),

SUBROUTINE N1YMNS (A,B,N,G,X)

реализуют алгоритмы решения САУ методами Зейделя и наискорейшего спуска (одна итерация) соответственно.

Входные параметры подпрограмм:

А(N,N) — (N ´ N)-мерная матрица САУ;

B(N) — N-мерный вектор правой части САУ;

N — мерность САУ;

G(N) — N-мерный вектор невязки (g = b — Ax);

X(N) — N-мерный вектор начальных условий решения САУ.

Выходные параметры подпрограммы:

X(N) — N-мерный вектор уточненных значений решения САУ.

Окончание итерационной процедуры производиться при выполнении условия , где , i[1, n], k = 1, 2, 3, …,

SUBROUTINE N1YGAU (A,B,X,N)

реализует алгоритм метода Гаусса с выбором главного элемента.

Входные A, B, N и выходной X параметры подпрограммы N1YGAU совпадают по описанию с аналогичными параметрами в подпрограммах N1YMGS, N1YMNS.

В подпрограмме N1YGAU матрица A приводится к треугольной.

3.8. Метод скорейшего спуска (градиента) для случая . системы линейных алгебраических уравнений

В рассматриваемом ниже итерационном методе вычислительный алгоритм строится таким образом, чтобы обеспечить минимальную погрешность на шаге (максимально приблизиться к корню).

Представим систему линейных уравнений в следующем виде:

(3.38)

Запишем выражение (3.38) в операторной форме:

(3.39)

Здесь приняты следующие обозначения:

; ; . (3.40)

В методе скорейшего спуска решение ищут в виде

, (3.41)

Где и — векторы неизвестных на P и P+1 шагах итераций; вектор невязок на P-ом шаге определяется выражением

, (3.42)

А (3.43)

В формуле (3.43) используется скалярное произведение двух векторов, которое определяется следующей формулой:

(3.44)

В формуле (3.43) — транспонированная матрица Якоби, вычисленная на P-ом шаге. Матрица Якоби вектор – функции F(X) определяется как

(3.45)

Нетрудно убедиться, что для системы (3.39) матрица Якоби равна

(3.46)

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

· Как видно из выражения (3.45), матрица Якоби не зависит от шага итерации.

· Требования минимизации погрешности на каждом шаге обусловили то, что метод градиента более сложен (трудоемок), чем методы Якоби и Зейделя.

· В методе градиента итерационный процесс естественно закончить при достижении , вектор невязок входит в вычислительную формулу.

· В приближенных методах можно обеспечить практически любую погрешность, если итерационный процесс сходится.

· Итерационный процесс можно прервать на любом K–ом шаге и продолжить позднее, введя в качестве нулевого шага значения X(K).

· В качестве недостатка приближенных методов можно отметить то, что они часто расходятся, достаточные условия сходимости (преобладание диагональных элементов) можно обеспечить только для небольших систем из 3 – 6 уравнений.

Пример 3.7. Методом скорейшего спуска решим систему уравнений

Так как диагональные элементы матрицы являются преобладающими, то в качестве начального приближения выберем:

Следовательно, вектор невязок на нулевом шаге равен

Далее последовательно вычисляем

Отсюда

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

Вопросы для самопроверки

· Назовите известные вам методы решения СЛАУ.

· Чем точные методы отличаются от приближенных?

· Что такое прямой и обратный ход в методе Гаусса?

· Нужен ли обратный ход при вычислении методом Гаусса а) обратной матрицы; б) определителя?

· Что такое невязка?

· Сравните достоинства и недостатки точных и приближенных методов.

· Что такое матрица Якоби?

· Надо ли пересчитывать матрицу Якоби на каждом шаге итерации в методе градиента?

· Исходная СЛАУ решается независимо тремя методами – методом Якоби, методом Зейделя и методом градиента. Будут ли равны значения

А) начального приближения (нулевой итерации);

Б) первой итерации?

· При решении СЛАУ (n > 100) итерационными методами решение расходится. Как найти начальное приближение?

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

Стандартные итерационные методы

В разделах Метод исключения Гаусса и Методы решения систем с симметричными матрицами процедуры решения систем алгебраических уравнений были связаны с разложением матрицы коэффициентов \( A \). Методы такого типа называются прямыми методами. Противоположностью прямым методам являются итерационные методы. Эти методы порождают последовательность приближенных решений \( \ < x^<(k)>\> \). При оценивании качества итерационных методов в центре внимания вопрос от том, как быстро сходятся итерации \( x^ <(k)>\).

Итерации Якоби и Гаусса — Зейделя

Простейшей итерационной схемой, возможно, являются итерации Якоби. Они определяются для матриц с ненулевыми диагональными элементами. Идею метода можно представить, используя запись \( 3 \times 3 \)-системы \( Ax = b \) в следующем виде: $$ \begin x_1 &= (b_1 — a_<12>x_2 — a_<13>x_3) / a_<11>, \\ x_2 &= (b_2 — a_<21>x_1 — a_<23>x_3) / a_<22>, \\ x_3 &= (b_3 — a_<31>x_1 — a_<32>x_2) / a_<33>. \\ \end $$ Предположим, что \( x^ <(k)>\) — какое-то приближение к \( x = A^<-1>b \). Чтобы получить новое приближение \( x^ <(k+1)>\), естественно взять: $$ \begin x_1^ <(k+1)>&= (b_1 — a_<12>x_2^ <(k)>— a_<13>x_3^<(k)>) / a_<11>, \\ x_2^ <(k+1)>&= (b_2 — a_<21>x_1^ <(k)>— a_<23>x_3^<(k)>) / a_<22>, \\ x_3^ <(k+1)>&= (b_3 — a_<31>x_1^ <(k)>— a_<32>x_2^<(k)>) / a_<33>. \\ \end $$

Эти формулы и определяют итерации Якоби в случае \( n = 3 \). Для произвольных \( n \) мы имеем $$ \begin \tag <7>x_i^ <(k+1)>= \left( b_i — \sum_^ a_x_j^ <(k)>— \sum_^ a_x_j^ <(k)>\right)/a_, \quad i = 1, 2, \ldots, n. \end $$

Заметим, что в итерациях Якоби при вычислении \( x_i^ <(k+1)>\) не используется информация, полученная в самый последний момент. Например, при вычислении \( x_2^ <(k+1)>\) используется \( x_1^ <(k)>\), хотя уже известна компонента \( x_1^ <(k+1)>\). Если мы пересмотрим итерации Якоби с тем, чтобы всегда использовать самые последние оценки для \( x_i \), то получим: $$ \begin \tag <8>x_i^ <(k+1)>= \left( b_i — \sum_^ a_x_j^ <(k+1)>— \sum_^ a_x_j^ <(k)>\right)/a_, \quad i = 1, 2, \ldots, n. \end $$ Так определяется то, что называется итерациями Гаусса — Зейделя.

Для итераций Якоби и Гаусса — Зейделя переход от \( x^ <(k)>\) к \( x^ <(k+1)>\) в сжатой форме описывается в терминах матриц \( L, D \) и \( U \), определяемых следующим образом: $$ \begin L &= \begin 0 & 0 &\cdots & \cdots & 0 \\ a_ <21>& 0 &\cdots & \cdots & 0 \\ a_ <31>& a_ <32>& 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots &\vdots\\ a_ & a_ & \cdots & a_ & 0 \end, \\ D &= \mathrm(a_<11>, a_<12>, \ldots, a_), \\ U &= \begin 0 & a_ <12>&a_ <13>& \cdots & a_ <1n>\\ 0 & 0 & a_ <23>& \cdots & a_ <2n>\\ \vdots & \vdots & \ddots & \ddots &\vdots\\ 0 & 0 & \cdots & 0 & a_ \\ 0 & 0 & \cdots & 0 & 0 \end. \end $$ Шаг Якоби имеет вид \( M_J x^ <(k+1)>= N_J x^ <(k)>+ b \), где \( M_J = D \) и \( N_J = -(L+U) \). С другой стороны, шаг Гаусса — Зейделя определяется как \( M_G x^ <(k+1)>= N_G x^ <(k)>+ b \), где \( M_G = (D+L) \) и \( N_G = -U \).

Процедуры Якоби и Гаусса — Зейделя — это типичные представители большого семейства итерационных методов, имеющих вид $$ \begin \tag <9>M x^ <(k+1)>= N x^ <(k)>+ b, \end $$ где \( A = M-N \) — расщепление матрицы \( A \). Для практического применения итераций (9) должна «легко» решаться система с матрицей \( M \). Заметим, что для итераций Якоби и Гаусса — Зейделя матрица \( M \) соответственно диагональная и нижняя треугольная.

Сходятся ли итерации (9) к \( x = A^<-1>b \), зависит от собственных значений матрицы \( M^<-1>N \). Определим спектральный радиус произвольной \( n \times n \)-матрицы \( G \) как $$ \rho(G) = \max \< |\lambda| :\ \lambda \in \lambda(G) \>, $$ тогда если матрица \( M \) невырожденная и \( \rho(M^<-1>N) —>