Курсовая: Решение систем линейных алгебраических уравнений методом простых итераций и методом Зейделя - текст курсовой. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Курсовая

Решение систем линейных алгебраических уравнений методом простых итераций и методом Зейделя

Банк рефератов / Математика

Рубрики  Рубрики реферат банка

закрыть
Категория: Курсовая работа
Язык курсовой: Русский
Дата добавления:   
 
Скачать
Архив Zip, 163 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникальной курсовой работы

Узнайте стоимость написания уникальной работы

Государственное общеобразовательное учреждение высшего профессионального образования ЛЕНИНГРАДС КИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ А.С. ПУШКИНА Санкт-Петербург 2008 Кафедра информатики и вычислительной математики КУРСОВАЯ РАБОТА Решение систем линейных алгебраических уравнений методом п ростых итераций и методом Зейделя Выполнил с тудент IV курса д невного отделения ф акультета МФИ Белоусов А.А. Проверил преподаватель : Голикова Е.И. Содержание Содержание 2 Введение 3 Метод итераций 5 Описание метода 5 Сходимость метода 8 Метод Зейделе 10 Описание метода 10 Сходимость метода. 13 Другая форма метода Зейделя 15 Практическая часть 18 Листинг №1(метод простой итерации) 18 Листинг №2(метод Зейделя) 20 Заключение 23 Список используемой литературы 24 Введение Способы решения линейных систем уравнений разделяют в на 2 группы. П ервые, точные методы представляющие собой конечные алгорифмы для вычисления корней системы (таковыми например, являются правило Крамера, метод Гаусса, метод главных элементов , метод квадратных корней и др.). Вторые , итерационные методы позволяющие получить корни системы с заданной точностью путем сходящихся бесконечных процессов (к числу таковых относят, метод итераций, метод Зейделя, метод релаксации). Вследствие неизбежных округлений результаты даже точных методов являются округленными, причем оценка погрешностей корней в общем случае затруднительна. При использовании итерационных процессов, сверх того, добавляется погрешность метода. Заметим, что эффективное применение итерационных методов существенно зависит от удачного выбора приближения и быс троты итерационного процесса. Сейчас разберем несколько определений которые будем использовать в этой работе . Система линейных уравнений с n неизвестными (или, линейная система) в линейной алгебре — это система уравнений вида (1) Здесь — неизвестные, которые надо определить. — коэффициенты системы — и — свободные члены — предполагаются известными. Индексы коэффициентов ( ) системы обозначают номера уравнения (i) и неизвестного (j), при котором стоит этот коэффициент, соответственно. Система (1) называется однородной, если все её свободные члены равны нулю ( ), иначе — неоднородной. Система (1) называется квадратной, если число m уравнений равно числу n неизвестных. Решение системы (1) — совокупность n чисел , таких что подстановка каждого ci вместо xi в систему (1) обращает все ее уравнения в тождества. Система (1) называется совместной, если она имеет хотя бы одно решение, и несовместной, если у нее нет ни одного решения. Совместная система вида (1) может иметь одно или более решений. Решения и совместной системы вида (1) называются различными, если нарушается хотя бы одно из равенств: = соответственно Совместная система вида (1) называется определенной, если она имеет единственное решение; если же у нее есть хотя бы два различных решения, то она называется неопределенной. Если уравнений больше, чем неизвестных, она называется переопределённой. Метод итераций Описание метода При большем числе неизвестных Линейная система (ЛС впоследствии) схема метода Гаусса, дающая точное приближение, становиться весьма сложной. В этих условиях для нахождения корней системы иногда удобнее использовать приближенные методы вычисления. Изложим здесь один из из этих методов – метод итераций. Пусть дана ЛС Введя в рассмотрение матрицы (1) Систему 1 коротко можно записать в виде матричного уравнения (1 ’ ) Предполагая, что диагональные коэффициенты Разрешим первое уравнение первое уравнение системы (1) относительно , второе относительно и т. д. Тогда получим эквивалентную систему (2) где при и при введя матрицы и Систему (2) можем записать в матричной форме (2 ’ ) Систему (2) будем решать методом последовательных приближений. За нулевое приближение принимаем, например столбец свободных членов т.е. Далее строим матрицы столбцы Первое приближение Второе приближение Вообще говоря, любое ( k +1)- е приближение вычисляется по формуле: (3) Если последовательность приближений Имеет придел То этот придел является решением системы (2). В самом деле, переходя к приделу в равенстве (3) будем иметь: и ли т.е. предельный вектор x является решением системы (2 ’ ), а следовательно, и системы (1). Напишем формулы приближений в развернутом виде Заметим, что иногда систему (1) выгоднее приводить к виду (2), так чтобы коэффициенты не были равны нулю. Вообще имея систему : можно положить где . Тогда данная система эквивалентна приведенной системе где при Поэтому при дальнейших рассуждениях мы не будем вообще говоря предполагать, что . Процесс итерации хорошо сходиться т.е. число приближений необходимых для получения корней системы (1) с заданной точностью невелико , если элементы матрицы малы по абсолютной величине. Иными словами, для успешного применения процесса итерации модули диагональных коэффициентов системы (1) должны быть велики по сравнению с модулями недиагональных коэффициентов этой системы (свободные члены при этом роли не играют). Пример: Решить систему методом итераций Здесь диагональные элементы, >> чем недиагональные Приведе м эту систему к нормальному вид В матричной форме можно записать: За нулевое приближение принимаем свободное приближение K 0 2 3 5 1 1.92 3.19 5.04 2 1.9094 3.1944 5.0446 3 1.90923 3.1945 5.04485 Замечание: при применении метода простой итерации нет необходимости брать за нулевое приближение столбец свободных членов. Как будет доказано ниже , сходимость процесса зависит от свойств матрицы . Сходимость метода Теперь докажем сходимость процесса итерации, для этого надо доказать сходимость . Выясним условия с ходимости последовательности Т е о р е м а 1. Для того чтобы последовательность приближений сходилась достаточно, чтобы все собственные значения матрицы B были по модулю меньше единицы: . (3) Д о к а з а т е л ь с т в о . Найдем значение любого выражения через (4) Отсюда и из условия теоремы с учетом свойств опеделителя матрицы сразу следует что при и , Откуда . Что касается необходимости условия , то ответ на вопрос дает Т е о р е м а 2. Если требовать, чтобы последовательность сходилась к при любом начальном приближении , то условие (3) является необходимым Д о к а з а т е л ь с т в о. Пусть для всякого начального приближения будет . Имеем . При разность стремиться к нулю , поэтому последний член цепи равенства должен стремиться к нулю, каким бы ни был вектор . Отсюда сле дует, что , по следнее же будет лишь в том слу чае, когда верно неравенство (3) Применение теоре м 1 и 2 требует знания границ с обственных значений матрицы В; нахожде ние их часто является нелегкой зада чей. Укажем более простые, но только дос таточные признаки сходимости. Т е о р е м а 3. Для того чтобы последовательность приближений в метод е простой итерации сходилась, д остаточно, чтобы какая-либо норма матрицы В была меньше единицы. Доказательство. Если , то все собственные значения матрицы В по мо дулю меньше единиц ы, и по теореме 1 последователь ность сходится. Непосредственным следствием теоремы ( 3 ) и равенств определяющих кубическую и октаэдриче скую норму матрицы, является Т е о р е м а 4. Последовательность в методе простой итерации сход ится, если для матрицы В выпол няется одно из неравенств: 1) 2) Для многих приложени й важно знать, какой является скорость сходимости , и уметь оценить Погрешность замены точного решения си темы приближением . Т е о р е м а 5 . Если какая-либо норма матрицы В, с огласованная с рассматриваемой нормой вектора , меньше единицы, то верна следующая оценка погрешности приближения в методе простой итерации: . (5) Д о к а з а т е л ь с т в о. Для выше дано выраже ние (4), и так как , то Поэтому (6) и, стало быть, . Часто за принимают вектор b . В этом случае оценка (5) немного упростится; подставляя = b в (6) получим . Метод Зейделе Описание метода Метод Зейделя применяют в двух видоизменениях. Рассмотрим сначала случай канонической формы системы для метода итерации (1) В методе простой итерации следующее приближение находится по предыдущему путем подстановки x k в правую часть всех уравнений системы (1). Для нас сейчас удобнее записать результат подстановки не в векторной форме, а в развернутом виде по составляющим: (2) В этой операции порядок выбора уравнений значения не имеет. Здесь, очевидно; опускаются две возможности улучшения итераций: разумный выбор порядка уравнений для подстановок и немедленный ввод в вычисления каждого из полученных исправленных значений неизвестных. О принципах вы бора порядка уравнений будет го вориться ниже, а сейчас предположим, что для перехода от приближения к следующему — нами выбран какой-то порядок привлечения уравнений для подстановок. Изменяя, если необходимо, нумерацию уравнений и неизвес тных, можно считать, что уравне ния для подстановок берутся в порядке роста их номе ров. Для каждого шага от приближения k до k +1 порядок привлечения уравнений может быть своим, и должны быть выполнены свои изменения нумерации и перестановки, что влечет за собой свое изменение матрицы В системы и свободного вектора b . Чтобы от метить это, обозначим матрицу В для рассматривае мого, шага и свободный вектор . В этих обозначе ниях итерация в м етоде Зейделя выполняется в сле дующем порядке: (3) После нахождения вектора устанавливают поря док подстановок в уравнения значений ( i = 1, ..., п) и переходят к вычислению вектора и т. д. Приведем теперь пример принципа, на основании которого можно устанавливать порядок привлечения уравнений для подстановок ( i = 1,..., п). Можно пытаться в первую очередь улучшить ту составляющую решения, которая найдена наименее точно, чтобы при нахождении всех других составляющих употреблять улучшенное ее значение. О точности можно было бы судить по вектору погрешности, , но так как вектор точного решения неизвестен, то в вычисле ниях заменяют другим вектором, по которому можно, хотя бы неполно, судить о погрешности . Чаще всего для этой цели пользуются вектором поправки на по следнем шаге , где . Ве личины поправок составляющих нумеруют в порядке убывания их абсолютных значени й, и в том же порядке вычисляют составляющие следующего приближения : сначала ту составляющую, которая отвечает наи большей по модулю поправке, и т. д. Пример: Приведем эту систему к удобному для итерации В качестве нулевых приближений корней возьмем Применяя последовательно процесс решения методом Зейделя Результаты вычисления корней приведены в Таблице ниже с точностью до 4-х знаков i 0 1.2000 0.0000 0.0000 1 1.2000 1.0600 0.9480 2 0.9992 1.0054 0.9991 3 0.9996 1.0001 1.0001 4 1.0000 1.0000 1.0000 5 1.0000 1.0000 1.0000 Точные значения : ; ; Сходимость метода. Остановимся более подробно на стационарном ме тоде Зейделя; когда при итерациях порядок уравнений сохраняется, матрица В будет одинаковой на всех ша гах и составляющие следующего приближения нахо дятся при всяком k по правилу (3). Разложим матрицу В на сумму двух матриц Н и F , где . Тогда равенства (2) можно записать в форме матрич ного равенства откуда следует, что , а так как определитель матрицы равен единице и она имеет обратную, то равенство (3) равносильно . (4) Поэтому стационарный м етод Зейделя равносилен ме тоду простой итерации, примененному к системе . Это сразу дает возможность на основании теоремы 1 (метод итерации) сказать, что для сходимости стационарного процесса Зейделя (2) при любом векторе начального приближения необходимо и достаточно, чтобы все соб ственные значения матрицы , т. е. корни уравнения , были по модулю меньше единицы . Этот признак может быть высказан в форме, не тре бующей обращения Е — Н. Если воспользоваться тем, что , то можно написать систему равенств Поэтому верна Теорема 1. Для того чтобы стационарный метод Зейделя сходился при любом начальном векторе при ближения необходимо и достаточно, чтобы все корни уравнения были по модулю меньше единицы. Укажем еще более простой достаточный признак сходимости. Предварительно докажем лемму. Л е м м а 1. Если в матрице диагональные элементы доминируют по строкам или по столбцам, т. е. если или то определитель матрицы А отличен от нуля. Д о к а з а т е л ь с т в о. Для определенности предпо ложим, что имеет место доминирование по строкам. Достаточно показать, что однородная система Ах = 0 (6) имеет только нулевое решение. Допустим противоположное и будем считать, что си стема имеет ненулевое решение , Среди составляющих решения выберем наибольшую по модулю; Положим и оценим снизу левую часть уравнения номера i системы.(6): гак как и по условию леммы. Этот результат противоречит тому, что есть решение системы, и доказывает неверность допущения. Т е о р е м а 2. Для сходимости стационарного метода Зейделя (4) достаточно, чтобы выполнялось какое-либо одно из условий: (7) Или (8) Д о к а з а т е л ь с т в о. Достаточность первого и вто рого условий проверяется аналогично, и можно ограни читься рассмотрением только первого условия. Нужно показать, что при выполнении условия (7) нее корни уравнения (5) будут по модулю меньше еди ницы. Будем считать, что , и рассмотрим сумму модулей недиагональных элементов строки номера i матрицы : Таким образом, диагональные элементы матрицы доминируют по строкам, и на основании леммы 1 определитель этой матрицы отличен от нуля , а значение , для которого , не может быть корнем уравнения (6). Корни этого уравнения все по мо дулю меньше единицы, и по теореме 1 стационарный метод Зейделя сходится. Другая форма метода Зейделя В ней требуется предварительное преобразование системы Ах = b к виду, в котором все диагональные коэффициенты от личны от нуля. Такое приведение стремятся выполнить, если это возможно, так, чтобы диагональные коэффи циенты были наибольшими или даже доминирующими в соответствующих уравнениях. Мы ограничимся описанием только стационарного процесса. Пусть взято какое-либо исходное приближение к решению системы. Приближе ние номера k + 1 находят по приближению номера k с помощью системы соотношений (9) Если разложить матрицу А на сумму двух матриц и то равенства (9) можно записать в матричном виде Bx k + l + Cx k = b , или Поэтому ясно, что метод Зейделя в форме (9) рав носилен методу простых итераций, примененному к си стеме в каноническом виде: Для сходимости метода при любом векторе b необ ходимо и достаточно, как следует из теорем 2 и 3, чтобы все собственные значения матрицы , т. е. все корни уравнения , были по мо дулю меньше единицы. Это условие можно упростить и высказать в форме, не требующей обращения матрицы В. В самом деле, , и можно формулировать следующую теорему. Т е о р е м а 3. Для того чтобы процесс Зейделя, определяемый равенствами (9), сходился при любых свободных членах необходимо и до статочно, чтобы корни уравнения все были меньше единицы по модулю. Практическая часть Здесь рассматриваются алгоритмы описанных выше методов с описанием. Все программы написаны в среде Turbo Pascal . Листинг №1(метод простой итерации) program iter ; var A: array [1..4,1..4] of real; b,x,otv: array [1..4] of real; i,j,n: byte; eps: real; pr: boolean; begin write('razmer matrix n='); readln(n); for i:=1 to n do Ввод данных for j:=1 to n do begin write('A[',i,',',j,']='); readln(A[i,j]); end; for i:=1 to n do if a[i,i]=0 then begin writeln (' oshibka vvoda '); проверка чтобы на диагонали не было exit; нулевых коэффициэнтов end; for i:=1 to n do begin write('b[',i,']='); readln(b[i]); end; for i:=1 to n do begin for j:=1 to n do begin if i=j then continue; Выражаем x1,x 2, x 3… из системы a[i,j]:=-a[i,j]/a[i,i]; end; b[i]:=b[i]/a[i,i]; a[i,i]:=0; end; for i:=1 to n do begin for j:=1 to n do write(a[i,j]:4:2,' '); writeln(b[i]:4:2); end; for i:=1 to n do x[i]:=0; write (' tochnost ='); Вводим точность readln(eps); repeat for i:=1 to n do begin for j:=1 to n do otv[i]:=otv[i]+a[i,j]*x[j]; алгоритм решения otv[i]:=otv[i]+b[i]; end; for i:=1 to n do if abs(otv[i]-x[i])
Рейтинг@Mail.ru