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

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

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

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

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

Выполнил:

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

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

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

Пермь 2005

Оглавление

Введение 3

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

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

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

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

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

Введение

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

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

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

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

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

§1. Уточнение решения

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

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

<img src="/cache/referats/20846/image002.gif" v:shapes="_x0000_i1025"> (1.1)

Пусть с помощьюнекоторого метода получено приближенное решение <img src="/cache/referats/20846/image004.gif" v:shapes="_x0000_i1026"> (начальное приближение к решению). Подставив в(1.1), получим

<img src="/cache/referats/20846/image006.gif" v:shapes="_x0000_i1027"> (1.2)

Обозначим за <img src="/cache/referats/20846/image008.gif" v:shapes="_x0000_i1028"> погрешность полученного решения, <img src="/cache/referats/20846/image010.gif" v:shapes="_x0000_i1029"><img src="/cache/referats/20846/image012.gif" v:shapes="_x0000_i1030"> — невязка.

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

<img src="/cache/referats/20846/image014.gif" v:shapes="_x0000_i1031"> (1.3)

Решив эту систему получимновое значение погрешности <img src="/cache/referats/20846/image016.gif" v:shapes="_x0000_i1032">, котороеиспользуем в качестве поправки к приближенному решению <img src="/cache/referats/20846/image018.gif" v:shapes="_x0000_i1033">, получаятаким способом новое приближение <img src="/cache/referats/20846/image020.gif" v:shapes="_x0000_i1034"> (следующее приближение к решению):

<img src="/cache/referats/20846/image022.gif" v:shapes="_x0000_i1035">.

Таким же способом найдемследующее приближение <img src="/cache/referats/20846/image020.gif" v:shapes="_x0000_i1036"> и следующую поправку к приближению <img src="/cache/referats/20846/image025.gif" v:shapes="_x0000_i1037">. Подобнымобразом будем искать очередные значения погрешности и поправки, покапогрешность <img src="/cache/referats/20846/image027.gif" v:shapes="_x0000_i1038"> не станет достаточно малым. Таким образом мынайдем приближенное решение системы с заданной точностью.

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

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

<img src="/cache/referats/20846/image029.gif" v:shapes="_x0000_i1039">,

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

Наличие сходимости идостижения заданной точности на практике можно определить (приближенно) несколькими способами. Так, при заданной погрешности<img src="/cache/referats/20846/image031.gif" v:shapes="_x0000_i1040">

<img src="/cache/referats/20846/image033.gif" v:shapes="_x0000_i1041"> (1.4),

<img src="/cache/referats/20846/image035.gif" v:shapes="_x0000_i1042">, (1.5),

<img src="/cache/referats/20846/image037.gif" v:shapes="_x0000_i1043">, при <img src="/cache/referats/20846/image039.gif" v:shapes="_x0000_i1044"> (1.6).

Здесь в (1.4) отличие векторов<img src="/cache/referats/20846/image041.gif" v:shapes="_x0000_i1045"> и <img src="/cache/referats/20846/image043.gif" v:shapes="_x0000_i1046"> на «ε» понимаетсякак малость модуля их разности. В (1.5) – малость разностей всех компонентоввектора, в (1.6) в смысле малости относительных разностей компонент. В случае,когда система не является плохо обусловленной, то в качестве критериядостижения нужной точности можно принять условие малости невязки:

<img src="/cache/referats/20846/image045.gif" v:shapes="_x0000_i1047"> (1.7)

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

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

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

<img src="/cache/referats/20846/image049.gif" v:shapes="_x0000_i1049"> (2.1)

где τ – вещественноечисло, называемое стационарным параметром. С помощью (2.1) составимитерационную последовательность векторов <img src="/cache/referats/20846/image051.gif" v:shapes="_x0000_i1050">

<img src="/cache/referats/20846/image053.gif" v:shapes="_x0000_i1051"> (k= 0,1,2,…..) (2.2)

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

Таким образом, методпростой итерации сводится к замене точного решения системы (1.1) k– ой итерацией <img src="/cache/referats/20846/image055.gif" v:shapes="_x0000_i1052"> с достаточно большимномером k.

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

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

Оценим погрешность <img src="/cache/referats/20846/image059.gif" v:shapes="_x0000_i1054">

<img src="/cache/referats/20846/image061.gif" v:shapes="_x0000_i1055"> (2.3)

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

Введем в рассмотрениенорму вектора в пространстве <img src="/cache/referats/20846/image063.gif" v:shapes="_x0000_i1056"> и операторную нормуквадратной матрицы порядка <img src="/cache/referats/20846/image065.gif" v:shapes="_x0000_i1057"><img src="/cache/referats/20846/image067.gif" v:shapes="_x0000_i1058"> число <img src="/cache/referats/20846/image069.gif" v:shapes="_x0000_i1059"><img src="/cache/referats/20846/image071.gif" v:shapes="_x0000_i1060"> число <img src="/cache/referats/20846/image073.gif" v:shapes="_x0000_i1061"><img src="/cache/referats/20846/image075.gif" v:shapes="_x0000_i1062"> на множестве всех ненулевых векторов <img src="/cache/referats/20846/image067.gif" v:shapes="_x0000_i1063"><img src="/cache/referats/20846/image077.gif" v:shapes="_x0000_i1064"> на множестве всехвекторов <img src="/cache/referats/20846/image067.gif" v:shapes="_x0000_i1065">

<img src="/cache/referats/20846/image079.gif" v:shapes="_x0000_i1066"> (2.4)

Из (2.4) вытекаетнеравенство, справедливое для любой матрицы <img src="/cache/referats/20846/image071.gif" v:shapes="_x0000_i1067"> и любого вектора <img src="/cache/referats/20846/image067.gif" v:shapes="_x0000_i1068">

<img src="/cache/referats/20846/image082.gif" v:shapes="_x0000_i1069"> (2.5)

Из матричного уравненияпогрешности (2.3) и неравенства (2.5) получаем, что для любого номера <img src="/cache/referats/20846/image084.gif" v:shapes="_x0000_i1070">

<img src="/cache/referats/20846/image086.gif" v:shapes="_x0000_i1071"> (2.6)

Теорема 2.1. Для того,чтобы итерационная последовательность (2.2) при любом выборе начального приближения <img src="/cache/referats/20846/image088.gif" v:shapes="_x0000_i1072"> и при данном значениипараметра <img src="/cache/referats/20846/image090.gif" v:shapes="_x0000_i1073"> сходилась к точномурешению <img src="/cache/referats/20846/image067.gif" v:shapes="_x0000_i1074"> системы (1.2),достаточно, чтобы было выполнено условие

<img src="/cache/referats/20846/image092.gif" v:shapes="_x0000_i1075"> (2.7)

При этом итерационнаяпоследовательность сходится со скоростью геометрической последовательности сознаменателем <img src="/cache/referats/20846/image094.gif" v:shapes="_x0000_i1076">

В случае если матрица <img src="/cache/referats/20846/image071.gif" v:shapes="_x0000_i1077"> является симметричной,условие является необходимым условием сходимости итерационнойпоследовательности при любом выборе нулевого приближения.

Для практических же целейнедостаточно установить факт сходимости последовательности итераций.Центральным вопросом является оценка скорости сходимости. Очень важно знать,как наилучшим способом распорядиться стационарным параметром <img src="/cache/referats/20846/image090.gif" v:shapes="_x0000_i1078"> для того, чтобыполучить наиболее быструю сходимость.

Пусть задана точность <img src="/cache/referats/20846/image097.gif" v:shapes="_x0000_i1079"> — точность, с которойнеобходимо получить решение системы. Требуется найти итерацию <img src="/cache/referats/20846/image099.gif" v:shapes="_x0000_i1080"> с таким номером <img src="/cache/referats/20846/image084.gif" v:shapes="_x0000_i1081">

<img src="/cache/referats/20846/image102.gif" v:shapes="_x0000_i1082"> (2.8)

Из (2.6) и Теоремы 2.1следует, что <img src="/cache/referats/20846/image104.gif" v:shapes="_x0000_i1083"><img src="/cache/referats/20846/image106.gif" v:shapes="_x0000_i1084"><img src="/cache/referats/20846/image108.gif" v:shapes="_x0000_i1085"><img src="/cache/referats/20846/image084.gif" v:shapes="_x0000_i1086"><img src="/cache/referats/20846/image097.gif" v:shapes="_x0000_i1087"> — точности, следуетвыбрать параметр <img src="/cache/referats/20846/image090.gif" v:shapes="_x0000_i1088"> так, чтобы получитьминимум функции <img src="/cache/referats/20846/image110.gif" v:shapes="_x0000_i1089">

Считая матрицу <img src="/cache/referats/20846/image071.gif" v:shapes="_x0000_i1090"> симметричной иположительно определенной, мы приходим к следующей задачей оптимизации: найтиминимум функции

Теорема 2.2 (Теорема А.А.Самарского). Пусть матрица <img src="/cache/referats/20846/image071.gif" v:shapes="_x0000_i1092"> является симметричнойи положительно определенной, а матрица <img src="/cache/referats/20846/image114.gif" v:shapes="_x0000_i1093"> положительноопределенной. Тогда для того, чтобы итерационная последовательность

<img src="/cache/referats/20846/image116.gif" v:shapes="_x0000_i1094"> (2.9)

при любом выборе нулевогоприближения <img src="/cache/referats/20846/image088.gif" v:shapes="_x0000_i1095"> сходилась к точномурешению <img src="/cache/referats/20846/image067.gif" v:shapes="_x0000_i1096"> системы <img src="/cache/referats/20846/image047.gif" v:shapes="_x0000_i1097">

<img src="/cache/referats/20846/image120.gif" v:shapes="_x0000_i1098"> (2.10)

При дополнительнопредположении о том, что матица являетсясимметричной, условие (2.10) не толькодостаточно, но и необходимо для сходимости указанной итерационнойпоследовательности с любым нулевым приближением <img src="/cache/referats/20846/image088.gif" v:shapes="_x0000_i1099">

Выражение (2.9), где <img src="/cache/referats/20846/image114.gif" v:shapes="_x0000_i1100"> представляет себянекоторую «легко обратимую» квадратную матрицу <img src="/cache/referats/20846/image123.gif" v:shapes="_x0000_i1101"><img src="/cache/referats/20846/image090.gif" v:shapes="_x0000_i1102"> — стационарныйпараметр, получается из выражения (2.2). Такой метод является более общимметодом по сравнению с методом простой итерации и называется «неявным методом простой итерации».

Перейдем теперь к оценкесходимости общего неявного метода простой итерации. Для этого выясним вопрос овыборе стационарного параметра <img src="/cache/referats/20846/image090.gif" v:shapes="_x0000_i1103">

Предположим, что <img src="/cache/referats/20846/image114.gif" v:shapes="_x0000_i1104"> является симметричнойи положительно определенной. С помощью таких матриц естественно ввести такназываемое «энергетическое скалярное произведение» двух произвольных векторов <img src="/cache/referats/20846/image067.gif" v:shapes="_x0000_i1105"> и <img src="/cache/referats/20846/image126.gif" v:shapes="_x0000_i1106"><img src="/cache/referats/20846/image128.gif" v:shapes="_x0000_i1107"> Такое скалярноепроизведение будем обозначать <img src="/cache/referats/20846/image130.gif" v:shapes="_x0000_i1108"><img src="/cache/referats/20846/image132.gif" v:shapes="_x0000_i1109"> это скалярноепроизведение можно записать в виде <img src="/cache/referats/20846/image134.gif" v:shapes="_x0000_i1110"> С помощью последнегоравенства легко проверяется справедливость для введенного нами скалярного произведениячетырех аксиом скалярного произведения.

Далее естественно ввести«энергетическую норму» вектора <img src="/cache/referats/20846/image067.gif" v:shapes="_x0000_i1111"><img src="/cache/referats/20846/image137.gif" v:shapes="_x0000_i1112"><img src="/cache/referats/20846/image139.gif" v:shapes="_x0000_i1113">

Две различных нормы однойи той же системы векторов <img src="/cache/referats/20846/image141.gif" v:shapes="_x0000_i1114"> и <img src="/cache/referats/20846/image143.gif" v:shapes="_x0000_i1115"> называютсяэквивалентными, если существуют такие положительные постоянные <img src="/cache/referats/20846/image145.gif" v:shapes="_x0000_i1116"> и <img src="/cache/referats/20846/image147.gif" v:shapes="_x0000_i1117">

<img src="/cache/referats/20846/image149.gif" v:shapes="_x0000_i1118"> (2.11)

Энергетическая и обычнаянормы вектора являются эквивалентными, а это позволяет утверждать, чтопоследовательность <img src="/cache/referats/20846/image151.gif" v:shapes="_x0000_i1119"><img src="/cache/referats/20846/image153.gif" v:shapes="_x0000_i1120">

Теорема 2.3 Пусть матрица<img src="/cache/referats/20846/image071.gif" v:shapes="_x0000_i1121"> и <img src="/cache/referats/20846/image114.gif" v:shapes="_x0000_i1122"> симметричны иположительно определены, <img src="/cache/referats/20846/image156.gif" v:shapes="_x0000_i1123"> — погрешность общегонеявного метода простой итерации. Тогда для того, чтобы при <img src="/cache/referats/20846/image158.gif" v:shapes="_x0000_i1124"> было справедливонеравенство <img src="/cache/referats/20846/image160.gif" v:shapes="_x0000_i1125">

<img src="/cache/referats/20846/image162.gif" v:shapes="_x0000_i1126"> (2.12)

Применим Теорему 2.3 длянахождения значения стационарного параметра <img src="/cache/referats/20846/image090.gif" v:shapes="_x0000_i1127">

Так как обе матрицы <img src="/cache/referats/20846/image071.gif" v:shapes="_x0000_i1129"> и <img src="/cache/referats/20846/image114.gif" v:shapes="_x0000_i1130"> являются симметричнымии положительно определенными, то существуют такие постоянные <img src="/cache/referats/20846/image145.gif" v:shapes="_x0000_i1131"> и <img src="/cache/referats/20846/image147.gif" v:shapes="_x0000_i1132"><img src="/cache/referats/20846/image164.gif" v:shapes="_x0000_i1133"><img src="/cache/referats/20846/image145.gif" v:shapes="_x0000_i1134"> и <img src="/cache/referats/20846/image147.gif" v:shapes="_x0000_i1135"> в этих неравенствахнам заданы. Сопоставляя это неравенство с условием (2.12), мы получим, чтоминимальное значение <img src="/cache/referats/20846/image094.gif" v:shapes="_x0000_i1136"> достигается приусловии <img src="/cache/referats/20846/image167.gif" v:shapes="_x0000_i1137"><img src="/cache/referats/20846/image169.gif" v:shapes="_x0000_i1138"> и минимальное значение<img src="/cache/referats/20846/image171.gif" v:shapes="_x0000_i1139">

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

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

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

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

<img src="/cache/referats/20846/image173.gif" v:shapes="_x0000_i1140"> (3.1)

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

<img src="/cache/referats/20846/image175.gif" v:shapes="_x0000_i1141"> (3.2)

Зададимнекоторые начальные (нулевые) приближения значений неизвестных: <img src="/cache/referats/20846/image177.gif" v:shapes="_x0000_i1142"><img src="/cache/referats/20846/image179.gif" v:shapes="_x0000_i1143"><img src="/cache/referats/20846/image181.gif" v:shapes="_x0000_i1144"> и т.д. до <img src="/cache/referats/20846/image183.gif" v:shapes="_x0000_i1145">

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

Итерационныйпроцесс продолжается до тех пор, пока значения неизвестных не станут отличатьсяот предыдущих приближений на <img src="/cache/referats/20846/image097.gif" v:shapes="_x0000_i1146">

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

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

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

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

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

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

<img src="/cache/referats/20846/image190.gif" v:shapes="_x0000_i1149"> (1.1)

Возьмем для удобстваматрицу <img src="/cache/referats/20846/image071.gif" v:shapes="_x0000_i1150"> двухдиагональной, и размерностью <img src="/cache/referats/20846/image193.gif" v:shapes="_x0000_i1151">, ипроизвольный вектор <img src="/cache/referats/20846/image195.gif" v:shapes="_x0000_i1152">, т.е. матрицывида

<img src="/cache/referats/20846/image197.gif" v:shapes="_x0000_i1153">, <img src="/cache/referats/20846/image199.gif" v:shapes="_x0000_i1154"> (4.1)

Так какможно доказать, что все собственные числа <img src="/cache/referats/20846/image201.gif" v:shapes="_x0000_i1155"> матрицы по модулю меньше единицы:

<img src="/cache/referats/20846/image203.gif" v:shapes="_x0000_i1156"> (4.2)

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

Точным решением системы являетсявектор <img src="/cache/referats/20846/image205.gif" v:shapes="_x0000_i1157">.

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

Метод решения

<img src="/cache/referats/20846/image097.gif" v:shapes="_x0000_i1158"> (погрешность)

<img src="/cache/referats/20846/image090.gif" v:shapes="_x0000_i1159"> (стацион. параметр)

Полученное решение

Время решения

Якоби

0.000001

16 мс.

Якоби

0.000001

09 мс.

Зейделя

0.000001

09 мс.

Зейделя

0.000001

05 мс.

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

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

Легко заметить, что при произвольномвыборе стационарного параметра <img src="/cache/referats/20846/image090.gif" v:shapes="_x0000_i1164"> метод Зейделя значительно превосходитметод Якоби по скорости. И, хотя разница во времени относительно небольшая,следует учесть сравнительно небольшую размерность системы уравнений.Естественно, при увеличении размерности скорость сходимости методовнеоднократно возрастет.

Так же следует отметить сильноеразличие в скорости сходимости при произвольном стационарном параметре и приспециальном (оптимизированным) выборе <img src="/cache/referats/20846/image090.gif" v:shapes="_x0000_i1165">.

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

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

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

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

1.

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

2.

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

3.

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

4.

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

5.

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

еще рефераты

Еще работы по математике

Реферат по математике

Комплексные числа

3 Августа 2015

Реферат по математике