Здесь можно найти учебные материалы, которые помогут вам в написании курсовых работ, дипломов, контрольных работ и рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.
Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение оригинальности любого файла в формате MS Word. После такого повышения оригинальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, РУКОНТЕКСТ, etxt.ru. Программа «StudentHelp» работает по уникальной технологии так, что на внешний вид, файл с повышенной оригинальностью не отличается от исходного.
Результат поиска
Наименование:
Реферат/Курсовая Решение системы линейных уравнений с помощью метода Гаусса и метода простой итерации
Информация:
Тип работы: Реферат/Курсовая.
Добавлен: 26.04.13.
Год: 2012.
Страниц: 16.
Уникальность по antiplagiat.ru: < 30%
Описание (план):
Министерство образования
и науки Российской Федерации
Московский государственный
университет экономики, статистики
и информатики.
Кафедра Прикладной Математики
Курсовая работа
по курсу:
«Численные методы»
на тему:
«Решение системы
линейных уравнений с помощью метода Гаусса
и метода простой итерации»
Москва, 2012г.
Содержание
І Введение
ІІ Решение системы линейных уравнений
с помощью метода Гаусса и метода простой
итерации:
2.1. Методы решения систем линейных
алгебраических уравнений
2.2. Решение системы линейных
уравнений с помощью метода Гаусса 2.3.
Решение системы линейных уравнений с
помощью метода простой итерации
2.4. Алгоритмизация приведения
СЛАУ к эквивалентному виду
ІІІ Заключение
Список используемой литературы
ВВЕДЕНИЕ
Линейная алгебра –
часть алгебры, изучающая векторные
(линейные) пространства и их подпространства,
линейные отображения (операторы), линейные,
билинейные, и квадратичные функции
на векторных пространствах.
Линейная алгебра, численные
методы – раздел вычислительной математики,
посвященный математическому описанию
и исследованию процессов численного
решения задач линейной алгебры.
Среди задач линейной алгебры
наибольшее значение имеют две: решение
системы линейных алгебраических уравнений
определение собственных значений
и собственных векторов матрицы.
Другие часто встречающиеся задачи:
обращение матрицы, вычисление определителя
и т.д.
Любой численный метод
линейной алгебры можно рассматривать
как некоторую последовательность
выполнения арифметических операций над
элементами входных данных. Если при
любых входных данных численный
метод позволяет найти решение
задачи за конечное число арифметических
операций, то такой метод называется прямым. В противоположном
случае численный метод называется итерационным.
Прямые методы - это такие, как метод Гаусса,
метод окаймления, метод пополнения, метод
сопряжённых градиентов и др. Итерационные
методы – это метод простой итерации,
метод вращений, метод переменных направлений,
метод релаксации и др. В курсовой работе
будут рассматриваться метод Гаусса и
метод простой итерации.
2.1 Методы решения
систем линейных алгебраических
уравнений
К численным методам линейной
алгебры относятся численные
методы решения систем линейных алгебраических
уравнений, обращения матриц, вычисления
определителей и нахождения собственных
векторов матриц.
Методы решения систем
линейных алгебраических уравнений
делятся на две группы. К первой
группе принадлежат прямые (или точные)
методы, которые позволяют найти
точное решение системы за конечное
число арифметических действий. Отметим,
что вследствие погрешностей округления
при решении задач на ЭВМ прямые методы
на самом деле не приводят к точному решению
и назвать их точными можно, лишь отвлекаясь
от вычислительной погрешности. Наиболее
распространенными среди прямых методов
являются метод Гаусса и метод прогонки.
Вторую группу составляют
итерационные методы (их называют также
методами последовательных приближений),
которые состоят в том, что
точное решение системы находится как предел последовательных
приближений , где п - номер итерации.
Точными методами, например,
являются: метод Гаусса, метод прогонки.
Метод Гаусса будет рассмотрен в следующей
главе, а здесь я расскажу о методе прогонки.
Метод прогонки является одним
из эффективных методов решения
СЛАУ с трех - диагональными матрицами,
возникающих при конечно-разностной
аппроксимации задач для обыкновенных
дифференциальных уравнений (ОДУ) и
уравнений в частных производных
второго порядка и является частным
случаем метода Гаусса. Рассмотрим
следующую СЛАУ:
(1)
Что бы решить данное уравнение
методом простой прогонки для начала
нужно выразить из первого уравнения системы
переменную x0, а из
последнего - переменную xn, предполагая,
что , и запишем эту систему в следующем
виде:
(2)
Затем нужно, как бы «прогонять»
для каждого из уравнений, т.е.:
(3)
В итоге получаются коэффициенты
прогонки.
(4)
Для лучшего понимания
метода, представлен пример решения
системы линейных уравнений методом
прогонки.
Пример 1. Решить систему уравнений
методом прогонки.
0,5 x0 + 2 x1
+ 0,5 x2 = - 12;
0,5 x1 + 2 x2
+ 0,5 x3 = - 6;
0,5 x2 + 2 x3+ 0,5 x4 = 0;
x0 = 0,5 x1 – 4;
x4 = x3 +2.
Решение.
Прямой ход.
Подставим первое краевое условие
в первое разностное уравнение:
0,5 (0,5 x1 – 4) + 2 x1
+ 0,5 x2 = - 12, откуда
x1 = - 0,222 x2 - 4,444.
Выражение для
x1 подставим во второе разностное
уравнение:
0,5(- 0,222 x2 - 4,444) + 2 x2
+ 0,5 x3 = - 6, откуда
x2 = - 0,26471 x3 - 2,0001.
Выражение для
x2 подставим в третье разностное
уравнение:
0,5(- 0,26471 x3 - 2,0001) + 2 x3
+ 0,5 x4 = 0, откуда
x3 = - 0,26772 x4 + 0,53543.
Обратный ход.
Выражение для x3
подставим во второе краевое условие:
x4 = - 0,26772 x4 + 0,53543
+ 2 , откуда x4 =1,999.
Подставим x4 в
выражение для x3 :
x3 = - 0,26772 + 0,53543,
x3 =0,00017.
Подставим x3 в
выражение для x2 :
x2 = - 0,26471 • 0 – 2,
x2 = - 2,0001.
Подставим x2 в
выражение для x1 :
x1 = - 0,222 • (-2) - 4,444,
x1 = - 4,000 ,
и, наконец, подставив
x1 в первое краевое условие:
x0 = 0,5 (-4) – 4 , найдём
x0 = -6,000.
На равнее с методом простой
прогонки есть еще несколько методов решения
системы линейных уравнений. Теперь рассмотрим
метод из итерационных методов решения
системы уравнения.
Итерация Гаусса-Зейделя
Процесс простой итерации иногда
можно модифицировать для ускорения сходимости.
Отметим, что итеративный
процесс производит три последовательности
– {х1(k)}, {х2(k)},
{х3(k)}, {х4(k)}. Кажется
разумным, что х1(k+1) может быть
использовано вместо х2(k).
Аналогично х1(k+1) и х2(k+1)
можно использовать в вычислении х3(k+1).
Например, для уравнений из системы (5)
это даст следующий вид итерационного
процесса Гаусса-Зейделя, использующий
(6):
(5)
(6)
Такой итерационный процесс
даст результаты:
Таблица 1
Т. е. к точному решению
мы пришли уже на 10-ом шаге итерации.
Вывод.
Способ итераций дает возможность получить последовательность приближенных значений, сходящихся к точному решению системы. Для этого система приводится к виду (для случая системы из четырех уравнений):
(7)
Эти формулы как раз
и задают собственно итерационный процесс.
При этом чтобы итерационный процесс сходился к точному решению, достаточно, чтобы все коэффициенты системы были малы по сравнению с диагональными.
Это условие можно сформулировать
и более точно:
Для сходимости процесса итераций
достаточно, чтобы в каждом столбце
сумма отношений коэффициентов
системы к диагональным элементам,
взятым из той же строки, была строго
меньше единицы:
(8)
2.2 Решение системы
линейных уравнений с помощью
метода Гаусса
Рассмотрим систему линейных
алгебраических уравнений . (9)
Будем предполагать, что
определитель матрицы А отличен от
нуля. Метод Гаусса основан на приведении
матрицы А к треугольному
виду. Это достигается последовательным
исключением неизвестных из уравнений
системы. Сначала с помощью первого уравнения
исключается x1 из всех последующих
уравнений системы. Затем с помощью второго
уравнения исключается x2 из третьего
и всех последующих уравнений. Этот процесс,
называемый прямым ходом метода Гаусса,
продолжается до тех пор, пока в левой
части последнего (п-го) уравнения
не останется лишь один член с неизвестным xn , т.е.
матрица системы будет приведена к треугольному
виду.
Обратный ход метода Гаусса
состоит в последовательном вычислении
искомых неизвестных, т.е. решая последнее
уравнение, находим значение xп; далее,
используя это значение, из предыдущего
уравнения вычисляем xп-1 и т.д.
Последним найдем x1 из первого
уравнения.
Одной из модификаций метода
Гаусса является схема с выбором
главного элемента. Она состоит в
том, что требование akk?0 (на akk происходит деление
в процессе исключения) заменяется более
жестким: из всех оставшихся в матрице
элементов нужно выбрать наибольший по
модулю и представить уравнение так, чтобы
этот элемент оказался на месте ведущего
элемента akk
ПРЯМОЙ ХОД
При реализации прямого хода
метода Гаусса нет необходимости
действовать с переменными . Достаточно указать алгоритм, согласно
которому исходная матрица преобразуется
к треугольному виду, и указать соответствующее
преобразование правых частей системы.
Пусть осуществлены первые (k-1) шагов, т.е.
уже исключены переменные x1,
x2,…,xk-1 . Тогда имеем систему (10)
где - коэффициенты первой строки матрицы
А; - коэффициент i-го уравнения
при j переменной,
полученный в результате преобразований
системы на т–м шаге. Предположим,
что в k - ом уравнении
коэффициент . Умножим k -ое уравнение
системы на и вычтем полученное соотношение из i-го уравнения системы
(10), где .
В результате последняя группа
уравнений системы (10) примет вид:
где (11)
ОБОРАТНЫЙ ХОД
Обратный ход, как уже
указывалось, заключается в вычислении
неизвестных .Последнее уравнение будет иметь вид .
Откуда .
Общая формула обратного
хода для вычисления переменной xк имеет
вид . (12)
Основным ограничением метода
является предположение о том, что все
элементы , на которые производится деление,
отличны от нуля. Число называется ведущим (или направляющим)
элементом на k - м шаге исключения.
Даже если какой-то ведущий элемент не
равен нулю, а просто близок к нему, в процессе
вычислений может происходить сильное
накопление погрешностей. Избежать указанных
трудностей позволяет метод Гаусса
с выбором главного элемента. Основная
идея метода состоит в том, чтобы на очередном
шаге исключать не следующую по номеру
переменную, а ту, коэффициент при которой
является наибольшим по модулю.
Пусть на k - ом шаге имеем
систему (10). Сначала добиваемся выполнения
условия ,
путем перестановки двух уравнений системы
(10), а также двух столбцов неизвестных
со своими коэффициентами и соответствующей
перенумерацией коэффициентов и неизвестных.
При этом если переставляются столбцы,
то соответствующая перестановка и перенумерация
производятся и в уравнениях, которые
на k - м шаге не преобразуются,
т.е. при .
Найденный максимальный по
модулю элемент (если , то этот главный элемент всегда отличен
от нуля) называется k - м главным
элементом. Затем осуществляются преобразования k - го шага по
формулам (11).
В большинстве существующих
стандартных программ одновременно
с решением системы линейных алгебраических
уравнений (9) вычисляется определитель
матрицы А. Определитель
полученной в результате прямого хода
треугольной матрицы равен произведению
её диагональных элементов и отличается
от определителя лишь знаком, поскольку в процессе
преобразований осуществлялась перестановка
строк в столбцов. Поэтому ,
где s - суммарное
число перестановок строк и столбцов.
Если матрица заданной
системы вырожденная, то перед исключением
некоторой неизвестной главный
элемент окажется равным нулю. Этим
самым и обнаружится, что определитель
заданной системы равен нулю.
Пример 2. Схему вычислений по методу
Гаусса с выбором главного элемента поясняет
следующий пример:
2,74x1–1,18x2+3,17x3 = 2,18;
1,12x1+0,83x2–2,16x3 =
–1,15;
0,18x1+1,27x2+0,76x3 = 3,23.
Решение ведется в таблице
2.
Выбираем максимальный элемент
в столбцах x1, x2
и x3 раздела A (a13=3,17).
Заполняем столбец mi раздела
A, полученный делением элементов столбца x3 (результат
деления берется с обратным знаком) на
максимальный элемент a13=3,17:
Таблица 2
В столбец a записываются суммы коэффициентов
строк матрицы A:
2,74+(–1,18)+3,17+2 18=6,91;
1,12+0,83+(–2,16)+( 1,15)= –1,36;
0,18+1,27+0,76+3,23 5,44.
Переход к разделу Б ведется
следующим образом: строку, содержащую
главный (ведущий) элемент, умножаем на mi и прибавляем
к соответствующей i-ой строке. Результат
записываем в раздел Б. Строка с ведущим
элементом в раздел Б не переписывается.
2,74?0,6814+1,12=2, 870;
(–1,18) ? 0,6814 +0,83=0,0259;
2,18?0,6814+(–1,15) 0,3355;
6,91?0,6814+(–1,36) 3,3485
(результат заносится
в столбец a?).
Далее считает сумму a в каждой строке раздела Б.
2,9870+0,0259+0,3355= ,3484;
–0,4768+1,5528+2,707 =3,7835.
Если столбцы a и a? совпадают (с заданной точностью),
то вычисления выполнены верно и можно
переходить к следующему шагу: выбираем
главный элемент (2,9870), считаем mi и т.д.
В результате обратного хода
получаем:
Практически, вследствие вычислительных
погрешностей, полученное методом Гаусса
решение системы является приближенным.
Покажем, как уточнить это решение.
Пусть для системы
получено приближенное решение
. Положим .
Тогда для вектора поправки
будем иметь уравнение
или ,
где – вектор невязок для приближенного
решения .
Таким образом, чтобы найти
, нужно решить систему с прежней матрицей A и новым вектором
свободных членов . Заметим, что преобразованные
коэффициенты матрицы A можно не уточнять,
так как при малых невязках соответствующие
ошибки будут иметь более высокий порядок
малости.
Найдем поправку к полученному
в нашем примере решению
.
.
Коэффициенты при неизвестных D1, D2, D3 уже имеются готовыми
в таблице 2. Остается лишь преобразовать
вектор свободных членов.
Обратный ход.
Вывод.
Итак, метод Гаусса (или, иначе,
метод последовательного исключения
неизвестных) состоит в следующем:
1.
Путем элементарных преобразований
систему уравнений приводят к
эквивалентной ей системе с верхнетреугольной
матрицей. Эти действия называют прямым
ходом.
2.
Из полученной треугольной системы
переменные находят с помощью
последовательных подстановок (обратный
ход).
3.
При этом все преобразования проводятся
над так называемой расширенной матрицей
системы, которую и приводят к верхнее
- треугольному виду в прямом ходе метода.
2.3 Решение системы
линейных уравнений с помощью
метода простой итерации
Простейшим итерационным
методом решения систем линейных
уравнений является метод простой
итерации. Система уравнений (9) преобразуется
к эквивалентному виду . (13)
Метод простой итерации состоит
в следующем. Выбирается произвольный
вектор (начальное приближение) и строится
итерационная последовательность векторов
по формуле (14)
Приведем теорему о
достаточном условии сходимости
метода простой итерации.
Если , то система уравнений (13) имеет единственное
решение и итерационный процесс (14) сходится
к решению со скоростью геометрической
прогрессии.
Допустим, что - одно из решений системы (13), т.е. выполняется
равенство . (15)
Отсюда, используя третью
аксиому нормы и неравенство
, получим: (16)
и
или, поскольку , .
Из этого неравенства
следует единственность решения однородной
системы, т.е. при,а следовательно, существование и
единственность решения системы (14) при
любом свободном члене .
Вычтем из равенства (15) равенство
(14). Получим (17)
и, следовательно, .
Отсюда на основании 3 аксиомы
о норме имеем , (18)
т.е. норма разности между
точным решением и -м приближением стремится к нулю при не медленнее геометрической прогрессии
со знаменателем .
Оценим погрешность -го приближения. Преобразуем равенство
(17) к виду .
Согласно третьей аксиоме
нормы и равенству ,
откуда . (18)
Кроме того, в силу (17) имеем . (19)
Из (18) и (19) окончательно получаем .
Приведем без доказательства
теорему о необходимом и достаточном
условии сходимости метода простой
итерации.
Пусть система (19) имеет единственное
решение. Итерационный процесс (20) сходится
к решению системы (19) при любом начальном
приближении тогда и только тогда, когда
все собственные значения матрицы В по модулю меньше
единицы.
Эта теорема дает более
общие условия сходимости метода
простой итерации, однако воспользоваться
ею в общем случае непросто.
Также условия сходимости
выполняется, если в исходной матрице
диагональные элементы преобладают, т.е.:
Применяется алгорит простой интерации
до тех пор, пока
. Т.е. производить вычисления до тех пор,
пока в двух последовательных интеграциях
разница между соответствующими парами
неизвестных не станет по модулю между
.
Пример 4. Методом простой итерации решить
систему с точностью до 0,001.
Решение. Приведем систему к виду, в
котором элементы главной диагонали превосходили
бы сумму модулей остальных элементов
строки. Это обеспечит выполнение условия
.
В окончательном виде наша
система запишется следующим
образом:
x1=0,24x1–0,05x2–0,24x3+0,19;
x2=–0,22x1+0,09x2–0,44x3+0,97;
x3=0,13x1–0,02x2+0,42x3–0,14.
Матрица B и вектор ?c для
этой системы будут иметь вид:
Нормы матрицы B и вектора
будут соответственно равны:
= max(0,24+0,05+0,24; 0,22+0,09+0,44;
0,13+0,02+0,42)=
= max(0,53;
0,75; 0,67)=0,75<1.
= max(0,24+0,22+0,13; 0,05+0,09+0,02;
0,24+0,44+0,42)=
= max(0,59; 0,16; 1,10)=1,10>1.
Т.к.< 1, то процесс итераций
сходится, и теоретическое число итераций
k будет определяться по формуле:
, или
, т.е.
Отсюда k ? 28.
Теоретическая оценка числа
итераций, необходимых для обеспечения
заданной точности, практически всегда
очень завышена.
Вычисления располагаем
в таблице.
На седьмой итерации имеем,
что
.
Следовательно, необходимая
точность достигнута.
Ответ: x1=0,2474; x2=1,1145;
x3=–0,2243.
ЗАКЛЮЧЕНИЕ
Преимущество метода Гаусса
в том, что он позволяет достичь результата
за заранее известное и фиксированное
число действий. Точность результатов
будет определяться правильным выбором
порядка коэффициентов в матрице
и ее размерностью. Недостатком метода
является резкое увеличение времени и
погрешности вычислений с ростом n
Достоинствами метода простых
итераций является простота программной
реализации и более быстрый, по сравнению
с линейными методами, поиск решения
в матрицах большого размера. Также
один из плюсов метода простой итерации
– самокорректировка, т.е. отдельные ошибки
не отражаются на и т.д.................