Решение алгебраических уравнении и систем. Уточнение корней. Решение систем линейных алгебраических уравнений, страница 3

B=bi/aii        A= -aij/aii, i!=j или 0, i=j

В качестве начального приближения х0 рекомендуется выбирать

вектор В  свободных членов системы (4.13) [5].

В развернутом виде последовательные приближения осуществляется

 по формулам

xi(k+1)=Bi + сумма(aij*xj(k))             j=1..n

xi(0)=Bi

Приведем без доказательства теорему сходимости метода

простых итераций [13].

Теорема. Для того чтобы последовательность хk сходилась к

истинному решению х* при любом начальном приближении х ,

необходимо и достаточно, чтобы все собственные числа матрицы а были по модулю <меньше единицы.

Однако определение собственных чисел матрицы представляет

cобой весьма трудоемкую задачу. В качестве достаточного

признака сходимости в [13] указывается более простое правило. Для того что-

бы метод простых итераций сходился, достаточно, чтобы какая-

либо из норм матрицы а была меньше единицы. Данное положение будет особенно очевидным, если матрица А будет иметь преобладающую диагональ.

При практическом решении задач можно воспользоваться

одним из следующих соотношений проверки сходимости:

(4.15)сумма(/aij/)<1 j=1...n    (4.16)сумма(/aij/)<1 i=1...n   (4.17)сумма(/aij/^2)<1 i!=j

В алгоритме (4.14) решение на (k + 1 )-й итерации определяется

через все компоненты вектора решения на й-й итерации. В этом смысле метод простых итераций относится к группе полношаговых  алгоритмов.

Метод Зейделя. Метод Зейделя отличается от простых итераций

только тем, что найденное на (k + 1)-ой итерации значение какой-

либо компонента вектора решения на этой же итерации используется

для вычисления остальных компонент определяемого решения. Именно

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

Расчетные соотношения метода Зейделя для подготовленной сис-

темы уравнений (4.13) имеют вид

xi(k+1)=Bi + сумма(aij*xj(k+1))+сумма(aij*xj(k)) xi(0)=Bi i=1..n k=0,1,2...

 Области сходимости методов Зейделя и простых итераций перекрываются, т.е. существуют такие матрицы А, для которых метод Зейделя сходится, а метод простых итераций нет, и наоборот. В

практических расчетах достаточное условие сходимости метода Зейделя можно проверять по соотношениям (4.15)  (4.16).  Если матрица А симметрическая и положительно определенная, а подготовленная к итерациям система определяется в виде (4.13), то метод Зейделя сходится. Если же диагональные элементы симметрической матрицы А не отрицательны, то условие положительной

определенности матрицы А является и необходимым.

Из неособенной матрицы А можно получить симметрическую положительно определенную матрицу путем первой трансформации Гаусса,

что осуществляетcя за cчет умножения слева на матрицу транспонированную А левой и правой частей исходной системы алгебраических уравнений. При этом решаемая система принимает вид А(транспонир)*Ax = А(транспонир)*b

Метод наискорейшего спуска. Данный метод относится к группе

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

орной информации, то полагают х0  = 0), а далее осуществляется итерационный процесс уточнения

x(k+1)=xk+ck*gk   k=0,1,2,....            (4.19)

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

gi(k)=bi-сумма(aij*xj(k))     j=1....n

а коэффициент

сk=сумма(gj(k)^2) / сумма(aij*gi(k)*gj(k))       j=1...n  i,j=1...n       (4.21)

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