Министерство образования РоссийскойФедерации
Пермский Государственный ТехническийУниверситет
Курсовая работа
Итерационные методы решения линейныхсистем с неединственными коэффициентами
Выполнил:
ЕлисеевАлександр Сергеевич, ММ-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) составимитерационную последовательность векторов
(k= 0,1,2,…..) (2.2)
при произвольном выборенулевого приближения.
Таким образом, методпростой итерации сводится к замене точного решения системы (1.1) k– ой итерацией с достаточно большимномером k.
Графически метод Якоби можнопредставить следующим образом:
Рис. 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.000001
1
16 мс.
Якоби
0.000001
09 мс.
Зейделя
0.000001
1
09 мс.
Зейделя
0.000001
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с.