/>МИНИСТЕРСТВООБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ИПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«МАГНИТОГОРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙУНИВЕРСИТЕТ им. Г. И. НОСОВА»
Кафедра вычислительной техники и прикладной математики
КУРСОВАЯ РАБОТА
по дисциплине: «Вычислительная математика»
на тему: «Метод вращений решения СЛАУ»
Исполнитель:Сысоев Н.В,, студент 2 курса, АВ-09-1.
Руководитель:Филиппов Е. Г.
/>
Магнитогорск, 2011.
Содержание
Введение
1 Теоретическийобзор
1.1 Прямыеметоды
1.2 МетодГаусса
1.2.1 Описаниеметода
1.2.2 Сходимостьметода простой итерации
1.2.3 Апостериорнаяоценка погрешности
1.2.4 Пример
1.3 Методвращений линейных систем
1.3.1 Описаниеметода
1.3.2 Контрольточности и уточнение приближенного решения в рамках прямого метода
1.3.3 Апостериорнаяоценка погрешности
1.3.4 Пример
1.4 Методрелаксации
1.4.1 Пример
2 Практическаячасть
2.1 Таблицаидентификаторов
2.2 Листингпрограммы
2.3 Пример
2.4 Сравнительнаятаблица
Заключение
Библиографическийсписок
Введение
Как утверждается в книгеизвестного американского математика Валяха, 75% всех расчетных математическихзадач приходится на решение СЛАУ. Это не удивительно, так как математическиемодели тех или иных явлений или процессов либо сразу строятся как линейныеалгебраические, либо сводятся к таковым посредством дискретизации и/илилинеаризации. Поэтому трудно переоценить роль, которую играет выборэффективного способа решения СЛАУ. Современная вычислительная математикарасполагает большим арсеналом методов, а математическое обеспечение ЭВМ –многими пакетами прикладных программ, позволяющих решать различные возникающиена практике линейные системы. Чтобы ориентироваться среди методов и программ ив нужный момент сделать оптимальный выбор нужно разбираться в основе построенийметодов и алгоритмов, учитывающих специфику постановок задач, знать их сильныеи слабые стороны и границы применимости.
1 Теоретическийобзор1.1 Прямые методы
математическиймодель итерация погрешность
Все методы решения линейныхалгебраических задач можно разбить на два класса: прямые и итерационные. Прямыеметоды – это такие методы, которые приводят к решению за конечное числоарифметических операций. Если операции реализуются точно, то и решение такжебудет точным (в связи с чем к классу прямых методов применяют название точныеметоды). Итерационные методы – это методы в которых точное решение может бытьполучено лишь в результате бесконечного повторения единообразных действий.
Эффективность способов решениясистемы
/> или
иначе, векторно-матричныхуравнений Ах=f, где f=(f1, f2, …,fn)T – вектор свободных членов и
х=( х1, х2, …, хn)T – вектор неизвестных, а /> – вещественная n×n-матрица коэффициентовданной системы, во многом зависит от структуры и свойств матрицы А: размера,обусловленности, симметричности, заполненности и др.
Так размерность системы (т.ечисло n) является главным фактором, заставляющим вычислителей отвернуться отвесьма привлекательных в теоретическом плане и приемлемых на практике принебольших n формул Крамера.
/>1.2 Метод Гаусса1.2.1 Описание метода
Рассмотрим один из самыхраспространенных методов решения СЛАУ – метод Гаусса. Этот метод (которыйназывают также методом последовательного исключения неизвестных) известен вразличных вариантах уже более 2000 лет.
Вычисления с помощью методаГаусса состоят из двух основных этапов, называемых прямым ходом и обратнымходом. Прямой ход метода Гаусса заключается в последовательном исключениинеизвестных из системы (1):
/>
для преобразования её кэквивалентной системе с верхней треугольной матрицей. Вычисления значенийнеизвестных производят на этапе обратного хода.1.2.2 Алгоритм. 1.2.3 Апостериорная оценка погрешности.1.2.4 Пример1.3 Метод вращений линейных систем1.3.1 Описание метода.
Как и в методе Гаусса, цельпрямого хода преобразований в этом методе – приведение системы к треугольномувиду последовательным обнулением поддиагональных элементов сначала первогостолбца, затем второго и т.д.
/>
Пусть с1 и s1 – некоторыеотличные от нуля числа. Умножим первое уравнение исходной системы (1) на с1, второена s1 и сложим их; полученным уравнением заменим первое уравнение системы.Затем первое уравнение исходной системы умножаем на –s1, второе – на c1 и результатом их сложения заменим второе уравнение. Такимобразом, первые два уравнения (1) заменяются уравнениями
/>
/>
/>
Отсюда />.
Эти числа можно интерпретироватькак косинус и синус некоторого угла />(отсюда название метод вращений,каждый шаг такого преобразования можно рассматривать как вращение расширеннойматрицы системы в плоскости обнуляемого индекса).
В результате преобразованийполучим систему
/>
где
/>
Далее первое уравнение системызаменяется новым, полученным сложением результатов умножения первого и третьегоуравнений соотведлтственно на
/>
а третье – уравнением, полученнымпри сложении результатов умножения тех же уравнений соответственно на –s2 и с2. Получим систему
/>
где
/>
Выполнив преобразование m-1 раз,придем к системе
/>
Вид полученной системы такой же,как после первого этапа преобразований методом Гаусса. Эта система обладаетследующим свойством: длина любого вектора-столбца (эвклидова норма) расширеннойматрицы остается такой же, как у исходной матрицы. Следовательно, привыполнении преобразований не наблюдается рост элементов.
Далее по этому же алгоритму преобразуетсяматрица
/>
и т.д.
В результате m-1 этапов прямогохода система будет приведена к треугольному виду.
/>
Нахождение неизвестных неотличается от обратного хода метода Гаусса.
Треугольная, точнее,трапециевидная структура последней системы позволяет последовательно одно задругим вычислять значения неизвестных, начиная с последнего:
/>
/>
/>1.3.2 Контроль точности и уточнение приближенного решения врамках прямого метода
Прямые методы часто приводят кточному решению СЛАУ при точном выполнении предусматриваемых соответствующимиалгоритмами арифметических операций (без округлений).
Реальные же вычислениябазируются на арифметике машинных (т.е. усеченных до определенного количестваразрядов) чисел. Как отражается на результате решения системы подменаарифметики действительных чисел машинной арифметикой, зависит от самой решаемойсистемы, параметров применяемого компьютера и системы представления данных,способов реализации алгоритмов. В любом случае, практически вместо точногорешения СЛАУ прямой метод дает приближенное решение*) (обозначим его х(0)).Подставив х(0) в выражение ξ:=f-Ax, называемое невязкой, по малости полученноговектора значения ξ(0)=f-Ax(0) можно с осторожностью судить о близостинайденого решения x(0) к точному решению x. Если, напимер,
|| ξ(0)|| — недостаточномалая величина, то следует искать вектор-поправку p такой, что x(0)+р=х естьточное решение системы
/> т.е. А(х(0)+р)=f.
Последнее равносильно векторноматричному уравнению
Ар = ξ(0).
Таким образом, нахождениепоправки сводится к решению такой же системы, как и
/>,
где в качестве вектора свободныхчленов должен быть взят вектор невязок.1.3.3 Апостериорная оценка погрешности.1.3.4 Пример/>1.4 Метод релаксации1.4.1 Пример
2 Практическая часть/>/>2.1 Таблица идентификаторовtrrr(a,f,x,m) Функция, возвращающая матрицу невязок prr(a,r,m) Функция, возвращающая матрицу поправок maxv(v,el) Функция, возвращающая модуль максимального элемента вектора v switchColumns(A,n1,n2,m) Функция, возвращающая матрицу, полученную из А путем перестановки n1-ого и n2-ого столбцов Podgotovka(A,m) Функция, возвращающая 2 матрицы: матрицу, полученную из A перестановкой столбцов и пригодную для проведения вычислений; вектор, содержащий порядок следования неизвестных (1, 2,… n для x1, x2…xn соответственно) в уравнениях rotation(a,f,m,e) Функция, реализующая метод вращения. Возвращает 2 матрицы: неизвестных и поправок a Матрица коэффициентов f Матрица свободных членов x Матрица неизвестных m Количество неизвестных e Точность, с которой необходимо производить вычисления /> /> /> 2.2 Листинг программы
/>
/>
/>
/>
/>
/>
/>2.3 Пример.
/> /> />
/>
Подсчитаем матрицу неизвестных(Otvet1) и матрицу поправок(Otvet2)
/>
/>
Для сравнения, погрешностьметода Гаусса:
/>
Таким образом, можно говорить отом, что, действительно, метод вращений более точен.2.4 Сравнительная таблица
Заключение
Вданной работе был рассмотрен метод релаксации решения систем линейныхалгебраических уравнений. Была подробно рассмотрена теоретическая часть, изкоторой выводятся различные формулы для реализации данного метода. А также быловыполнено сравнение метода релаксации с методами простой итерации и Зейделя. Программнаяреализация выше описанных методов представлена в приложении А.
Порезультатам работы можно сделать следующие выводы. Во-первых, скоростьсходимости метода релаксации превышает скорости сходимости методов простойитерации и Зейделя. Во-вторых, скорость сходимости напрямую зависит от выборапараметра релаксации. Таким образом, данныйметод удобен для решения СЛАУ средней размерности.
Ещеодно достоинство итерационного метода верхних релаксаций состоит в том, что приего реализации на ЭВМ алгоритм вычислений имеет простой вид и позволяетиспользовать всего один массив для неизвестного вектора.
Библиографический список
1) Вержбицкий В. М. Основы численныхметодов: Учеб. пособие для вузов / В. М. Вержбицкий. — М.: Высш. шк., 2002. — 840 с.
2) И.Г. Серебренникова, Г.М. Коринченко,Вычислительная математика. МГТУ им Г.И. Носова 2003г. 146с
3) Е. Волков.Численные методы. М.,1987, 248 с.
4) А. И. Плис, Н. А. Сливина.Лабораторный практикум по высшей математике. — М.: «Высшая школа»,1983.
5) Калиткин Н.Н. Численные методы.М.: Наука, 1978, 512 с.
6) Демидович Б.П., Марон И.А. Основывычислительной математики. -М.: Наука, 1966 г., 664 стр.
7) Фадеев Д.К., Фадеева В.Н.Вычислительные методы линейной алгебры. М. Физматлит, 1960.
8) Воеводин В.В. Вычислительныеосновы линейной алгебры. — М.: Наука, 1977. — 304 с.
9) А. Самарский. Введение в численные методы. М.,1988, 270 с.