Название: вычислительная математика (В.В. Ландовский)

Жанр: Педагогика

Просмотров: 1776


Лабораторная работа №2. решение систем линейных уравнений

Цель работы

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

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

Способы решения систем линейных уравнений делятся на две группы:

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

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

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

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

Рассмотрим систему  линейных алгебраических уравнений относительно  неизвестных:

        (2.1)

Итерационные методы

Эффективное применение итерационных методов существенно зависит от удачного выбора начального приближения и быстроты сходимости процесса.

Метод итерации

Пусть дана линейная система (2.1). Предполагая, что диагональные коэффициенты    не равны 0 , разрешим первое уравнение системы (2.1) относительно , второе - относительно и т. д. Тогда получим эквивалентную систему

          (2.2)

где  при  не равно  и  при  .

Введя матрицы

систему (2.2) можно записать в матричной форме,  а любое  приближение вычисляется по формуле . Напишем формулы приближений в развернутом виде:

       (2.3)

Метод Зейделя

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

Пусть получена эквивалентная система (2.2). Выберем произвольно начальные приближения корней . Далее, предполагая, что k-ые приближения  корней известны, согласно Зейделю будем строить -е приближения корней по формулам:

Достаточное условие сходимости метода

Нормой квадратной матрицы  называется функционал, обозначаемый , удовлетворяющий условиям:

, причем  тогда и только тогда, когда

, для любого

Процесс итерации для приведенной линейной системы (2.1) сходится к единственному ее решению, если какая-нибудь каноническая норма матрицы  меньше единицы, т.е. для итерационного процесса (2.3) достаточное условие есть

Нормы матриц

(-норма или неопределенная норма)

( -норма или норма L1)

(-норма или Евклидова норма)

Следствие. Процесс итерации сходится, если выполнены неравенства:

,

или

,

Условия окончания итерационного процесса

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

Точные методы

Метод Гаусса

Метод Гаусса, его еще называют методом Гауссовых исключений, состоит в том, что систему (2.1) приводят последовательным исключением неизвестных к эквивалентной системе с треугольной матрицей:

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

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

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

Поступим аналогично с коэффициентами при остальных  переменных. Алгоритм можно записать следующим образом:

,

,

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

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

Аналогичным образом выглядит метод Гаусса с выбором главного элемента по строкам. В этом случае переставляются столбцы матриц; т.е. изменяется порядок исключения неизвестных. Описанные модификации называют схемами с частичным выбором.

Решение полученной системы, находят по рекуррентным формулам:

.

В матричной записи это означает, что сначала (прямой ход метода Гаусса) элементарными операциями над строками приводят расширенную матрицу системы к ступенчатому виду:

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

Метод Халецкого

Допустим, что мы должны решить систему уравнений (2.1), заданную в матричной форме . Метод основан на разложении квадратной матрицы на две треугольные:

 

Тогда. Обозначим . Получим . Теперь вместо одной мы будем иметь две системы уравнений:

. . . . . . . . . . . . . . . . . . . . . .                            . . . . . . . . . . . . . . . .

Из первой системы последовательно определяются вспомогательные неизвестные . После этого из второй системы в обратном порядке определяются искомые  .

Разложение матрицы А на две треугольные производят следующим образом. Имеем тождество:

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

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

строки на 1-й столбец  Þ 1 столбец ,

1 строка  на столбцы  Þ 1 строка ,

строки  на 2-й столбец  Þ 2 столбец ,

2 строка  на столбцы  Þ 2 строка ,

строки  на 3-й столбец  Þ 3 столбец ,

3 строка  на столбцы  Þ 3 строка ,

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Таким образом, на каждой итерации  получаем один столбец матрицы D и строку C:

 

,

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

Метод прогонки

Метод прогонки применяется для решения систем с трехдиагональной матрицей, и является адаптацией метода Гаусса к этому случаю. Запишем систему уравнений

в матричном виде:  где

Прямой ход метода прогонки (вычисление вспомогательных величин):

Обратный ход метода прогонки (нахождение решения):

Задание

Задача 1.

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

 

Таблица 2.1. Варианты методов решения СЛАУ

Вариант

Методы

1

Метод Гаусса, метод итерации

2

Метод Гаусса, метод Зейделя

3

Метод Гаусса с выбором главного элемента по столбцу, метод итерации

4

Метод Гаусса с выбором главного элемента по столбцу, метод Зейделя

5

Метод Халецкого, метод итерации

6

Метод Халецкого, метод Зейделя

 

Задача 2.

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

Содержание отчета

Цель работы.

Блок-схемы алгоритмов.

Пример работы программы.