Одношаговый циклический процесс

Ведение

Современная вычислительная математика располагает большим арсеналом методов, а математическое обеспечение ЭВМ-многими пакетами прикладных программ, позволяющие решать различные возникающие на практике линейные системы. Чтобы ориентироваться среди методов и программ и в нужный момент сделать оптимальный выбор, нужно разбираться в основах построений методов и алгоритмов, учитывая специфику постановок задач, знать их сильные и слабые стороны и границы применимости.

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

В первой главе рассматриваются итерационные методы: метод простой итерации, одношаговый циклический процесс, метод Некрасова, методы полной релаксации, неполная релаксация, градиентный метод с минимальными невязками, градиентные методы с неполной релаксацией [10], метод Якоби [11].

 

 

Глава 1. Итерационные методы решения линейных систем

В этой главе используется материал, кроме метода Якоби, из источника [11].

Метод Якоби взят из источника [10].

Метод простой итерации

Условия сходимости метода последовательных приближений тре­буют, чтобы матрица коэффициентов системы была, в том или ином смысле, близка к единичной матрице. Если это условие не выполнено или „плохо выполнено", систему целесообразно пред­варительно подготовить к применению метода последовательных при­ближений. Подготовка состоит в переходе от данной системы к равносильной системе

,

где некоторая неособенная матрица, которая выбирается так, чтобы матрица была бы близка к единичной, т. е. матрица была бы близка к .

Применение метода последовательных приближений к подгото­вленной системе равносильно применению стацио­нарного итерационного процесса

к исходной системе.

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

Пусть матрица положительно определена. Тогда система всегда может быть подготовлена к виду, в котором метод последова­тельных приближений будет сходящимся. Вычислив, например, первую норму µ матрицы , мы получим, что все собственные значения матрицы заключены в открытом интервале (0, µ). Положим

(1.1.1)

Система преобразуется к виду

(1.1.2)

Собственные значения матрицы будут заключены в открытом интервале (-1, 1) и, следовательно, метод последова­тельных приближений будет сходящимся.

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

Перепишем систему в развернутом виде

(1.1.3)

Поделим каждое уравнение системы (1.1.3)на диагональный элемент.

Получим систему

или в матричной записи

(1.1.4)

где

(1.1.5)

Для применения процесса итерации нет необходимости на самом деле делать преобразование системы (1.1.3) в систему (1.1.4). Последовательные приближения можно вычислять по формулам:

(1.1.6)

Описанная модификация процесса последовательных приближений имеет название метода простой итерации [10].

Одношаговый циклический процесс

Пусть система линейных уравнений представлена в виде

(1.2.1)

где , . Обозначим компоненты искомого вектора решения через х₁,х₂,…,х_n. Одношаговый циклический процесс напоминает процесс последовательных приближений с той разницей, что при вычислении -го шага приближения для -й компоненты учитываются вычисленные уже ранее -е приближения для компонент ,…, . Вычисление последовательных приближений ведется по формулам

(1.2.2)

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

В первом истолковании метод не стационарный, а циклический. В качестве матриц, определяющих процесс, берутся, по очереди, матрицы e₁₁,e₂₂,…,e_nn, где

(1.2.3)

Точнее, H_n(k-1)+i=e_ii.

Во втором истолковании процесс стационарный.

Уравнение (1.2.1) представим в виде

, (1.2.4)

где

(1.2.5)

Т.е.

(1.2.6)

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

которая равносильна исходной системе.

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

Метод Некрасова

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

Система записывается в виде

и последовательные приближения определяются по формулам

Для сходимости метода Некрасова необходимо и достаточно, чтобы все корни уравнения (уравнения Некрасова)

были по модулю меньше единицы.

В случае, если матрица из коэффициентов системы симметрична и положительно определена, то метод Некрасова для системы ходится. Вычисление по методу Некрасова зависит от порядка нумерации уравнений (и неизвестных). Если в каждом цикле неизвестные вычисляются начиная с x_n и далее x_n-1,…,x₁, то расчетные формулы будут

Методы полной релаксации

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

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

Тогда

и

где – -я компонента вектора невязки для приближения .

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

Не всякий процесс полной релаксации сходится к решению.

Неполная релаксация

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

При неполной релаксации функция ошибки изменяется по формуле

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

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

где .

Формулы для вычисления компонент результата -го цикла будут

Эта формула определяет итерационный процесс и для систем с не положительно-определенными матрицами.