Итерационные методы решения систем линейных равнений с неединственными коэффициентами

Министерство образования Российской Федерации

Пермский Государственный Технический Университет

Курсовая работа

Итерационные методы решения линейных систем с неединственными коэффициентами

Выполнил:

Елисеев Александр Сергеевич, ММ-05-2

Научный руководитель:

Грайфер Лазарь Борисович

Пермь 2005

Оглавление

Введение 3

з1. точнение решения 4

з2. Метод простых итераций 7

з3. Метод Гаусса - Зейделя 14

з4. Применение итерационных методов 16

Список использованной литературы 19

Введение

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

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

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

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

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

з1. точнение решения

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

Найдем решение системы линейных равнений

(1.1)

Пусть с помощью некоторого метода получено приближенное решение а(начальное приближение к решению). Подставив в (1.1), получим

а (1.2)

Обозначим за апогрешность полученного решения, а<- невязка.

Вычитаем (1.2) из (1.1), с четом введенных обозначений

(1.3)

Решив эту систему получим новое значение погрешности , которое используем в качестве поправки к приближенному решению , получая таким способом новое приближение а(следующее приближение к решению):

.

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

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

Следует заметить, что если при величении числа итераций приближенное решение стремится к точному:

,

то итерационный метод называют сходящимся.

Наличие сходимости и достижения заданной точности на практике можно определить (приближенно)а несколькими способами. Так, при заданной погрешности

(1.4),

, (1.5),

, при (1.6).

Здесь в (1.4) отличие векторов аи ана лε понимается как малость модуля их разности. В (1.5) - малость разностей всех компонентов вектора, в (1.6) в смысле малости относительных разностей компонент. В случае, когда система не является плохо обусловленной, то в качестве критерия достижения нужной точности можно принять словие малости невязки:

(1.7)

з2. Метод простых итераций (метод Якоби)

Рассмотрим квадратную систему линейных равнений с вещественными коэффициентами, которую запишем в матричном виде (1.1).

Предполагая однозначную разрешимость системы (1.1), заменим матричное равнение эквивалентным ему уравнением:

(2.1)

где τ - вещественное число, называемое стационарным параметром. С помощью (2.1) составим итерационную последовательность векторов

а (

при произвольном выборе нулевого приближения.

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

Графически метод Якоби можно представить следующим образом:

Рис. 1. Схема выполнения метода Якоби

Оценим погрешность

(2.3)

где Е - единичная матрица.

Введем в рассмотрение норму вектора в пространстве аи операторную норму квадратной матрицы порядка ачисло ачисло ана множестве всех ненулевых векторов ана множестве всех векторов

(2.4)

Из (2.4) вытекает неравенство, справедливое для любой матрицы аи любого вектора

(2.5)

Из матричного равнения погрешности (2.3) и неравенства (2.5) получаем, что для любого номера

(2.6)

Теорема 2.1. Для того, чтобы итерационная последовательность (2.2)а при любом выборе начального приближения аи при данном значении параметра асходилась к точному решению асистемы (1.2), достаточно, чтобы было выполнено словие

(2.7)

При этом итерационная последовательность сходится со скоростью геометрической последовательности со знаменателем

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

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

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

(2.8)

Из (2.6) и Теоремы 2.1 следует, что а<- точности, следует выбрать параметр атак, чтобы получить минимум функции

Считая матрицу асимметричной и положительно определенной, мы приходим к следующей задачей оптимизации: найти минимум функции

Теорема 2.2 (Теорема А.А. Самарского). Пусть матрица аявляется симметричной и положительно определенной, матрица аположительно определенной. Тогда для того, чтобы итерационная последовательность

(2.9)

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

(2.10)

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

Выражение (2.9), где апредставляет себя некоторую легко обратимую квадратную матрицу а<- стационарный параметр, получается из выражения (2.2). Такой метод является более общим методом по сравнению с методом простой итерации и называется неявным методом простой итерации.

Перейдем теперь к оценке сходимости общего неявного метода простой итерации. Для этого выясним вопрос о выборе стационарного параметра

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

Далее естественно ввести лэнергетическую норму вектора

Две различных нормы одной и той же системы векторов аи аназываются эквивалентными, если существуют такие положительные постоянные аи

(2.11)

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

Теорема 2.3 Пусть матрица аи асимметричны и положительно определены, а<- погрешность общего неявного метода простой итерации. Тогда для того, чтобы при абыло справедливо неравенство

(2.12)

Применим Теорему 2.3 для нахождения значения стационарного параметра

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

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

з3. Метод Гаусса-Зейделя

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

Пусть задана СЛАУ

(3.1)

Предположим, что диагональные элементы не нулевые (в противном случае можно переставить уравнения). Выразим неизвестные из каждого равнения:

(3.2)

Зададим некоторые начальные (нулевые) приближения значений неизвестных: аи т.д. до

На этом заканчивается первая итерация решения системы. Используя теперь полученные приближения таким же образом проводи вторую итерацию.

Итерационный процесс продолжается до тех пор, пока значения неизвестных не станут отличаться от предыдущих приближений на

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

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

Графически метод Зейделя можно представить следующим образом:

Рис. 2. Схема выполнения метода Гаусса-Зейделя

з4. Применение итерационных методов

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

(1.1)

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

, (4.1)

Так как можно доказать, что все собственные числа аматрицы по модулю меньше единицы:

(4.2)

То для решения системы (1.1) с заданными коэффициентами (4.1) можно применить как итерационный метод Якоби, так и метод Гаусса-Зейделя.

Точным решением системы является вектор .

После применения итерационные методы Якоби и Гаусса-Зейделя были получены следующие результаты:

Метод решения	а(погрешность)	а(стацион. параметр)	Полученное решение	Время решения
Якоби	0.1	1		16 мс.
Якоби	0.1			09 мс.
Зейделя	0.1	1		09 мс.
Зейделя	0.1			05 мс.

Табл. 1. Полученные результаты

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

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

Так же следует отметить сильное различие в скорости сходимости при произвольном стационарном параметре и при специальном (оптимизированным) выборе .

Из полученных результатов можно сделать вывод, что для решения систем линейных равнений, для которых выполняется словие (4.1) наиболее оптимальным (по скорости сходимости) является метод Гаусса-Зейделя с оптимизированным набором параметров. Но для достаточно небольших систем линейных равнений может использоваться метод Якоби с оптимизированным набором параметров.

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

Оптимальным же является комплексное применение методов решения СЛАУ, т.е. получение приближенного решения с помощью прямого метода и последующего точнения решения с помощью итерационных методов.

Список использованной литературы

1.                 Турчак Л.И., Плотников П.В. Основы численных методов: учебное пособие. - 2-е изд., перераб. и доп. - М.:ФИЗМАТЛИТ, 2003. - 304с.

2.                 Бояршинов М.Г. Численные методы. часть1: учебное пособие для студентов направления Прикладная математика и информатика. - Перм. Гос. Техн. н-т. Пермь, 1998. - 176с.

3.                 Ильин В.А., Позняк Э.Г. Линейная алгебра: учеб.: Для Вузов. - 5-3 изд. - М.:ФИЗМАТЛИТ, 2002. - 320с.

4.                 Самарский А.А., Гулин А.В. Численные методы: учеб. Пособие для вузов. - М.:Наука. Гл.ред физ.-мат. Лит-ры, 1989. - 432с.

5.                 Калиткин Н.Н. Численные методы. - М.:Наука. Гл.ред. физ.-мат. Лит-ры, 1978. - 512с.