Знаходження коренів систем лінійних рівнянь методом Гаусса, методом Зейделя та методом простих ітерацій
2
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
ХАРКІВСЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ РАДІОЕЛЕКТРОНІКИ
Кафедра інформатики
КУРСОВА РОБОТА
Тема: «Знаходження коренів систем лінійних рівнянь методом Гаусса, методом Зейделя та методом простих ітерацій»
з дисципліни “Програмування”
ПОЯСНЮВАЛЬНА ЗАПИСКА
21
Керівник
Студент гр. КІ-09-2
Харків 2010
ЗА Д А Н И Е
на курсовую работу студента
Лещенко Юрий Геннадиевич
(фамилия, имя, отчество)
1.Тема работы Решение систем линейных уравнений методом Гаусса, методом Зейделя и методом простых итераций.
2. Срок сдачи студентом законченной работы
3. Исходные данные к работе: Данные по предметной области, методические указания, ДСТУ 3008-95
4. Содержание расчётно-пояснительной записки (перечень подлежащих разработке вопросов) : введение, постановка задачи, теоретические сведения, выводы, список используемых источников, приложение А Текст программы.
5. Перечень графического материала : 3 иллюстраций к курсовой работе.
6. Дата выдачи задания 20.12.2009.
21
21
РЕФЕРАТ
Пояснительная записка: 36 с., 0 рис., 3 рисунка, 3 источника.
Пояснительная записка содержит: постановку задачи, теоретическую часть, описание программы, общие сведения, логическую структуру, описание алгоритма, примеры работы программы, вывод.
В данных разделах рассматриваются методы решения системы линейных алгебраических уравнений.
Целью данной работы является получение навыков программирования в интегрированной среде Visual C++ и особенностей синтаксиса языка С++.
МЕТОД ГАУССА, МЕТОД ЗЕЙДЕЛЯ, МЕТОД ПРОСТЫХ ИТЕРАЦИЙ, VISUAL C++.
21
СОДЕРЖАНИЕ
ВВЕДЕНИЕ…………………………………………………………
1 ПОСТАНОВКА ЗАДАЧИ………………………………………………….....
2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ………………………………………………......…
2.1 Разрешимость системы линейных уравнений…………………………7
2.2 Метод Гаусса…………………………….……………………..……
2.3 Метод простых итераций………………………………………………13
2.4 Метод Зейделя…………………………………………………………. 18
ВЫВОДЫ………………………………………………………………
ПЕРЕЧЕНЬ ССЫЛОК…………………………………………………..…..
ПРИЛОЖЕНИЕ А Текст программы...…………………………….……..….
ВВЕДЕНИЕ
Линейная алгебра – часть алгебры, изучающая векторные (линейные) пространства и их подпространства, линейные отображения (операторы), линейные, билинейные, и квадратичные функции на векторных пространствах.
Линейная алгебра, численные методы – раздел вычислительной математики, посвященный математическому описанию и исследованию процессов численного решения задач линейной алгебры.
Среди задач линейной алгебры наибольшее значение имеют две: решение системы линейных алгебраических уравнений определение собственных значений и собственных векторов матрицы. Другие часто встречающиеся задачи: обращение матрицы, вычисление определителя и т.д.
Любой численный метод линейной алгебры можно рассматривать как некоторую последовательность выполнения арифметических операций над элементами входных данных. Если при любых входных данных численный метод позволяет найти решение задачи за конечное число арифметических операций, то такой метод называется прямым. В противоположном случае численный метод называется итерационным. Прямые методы - это такие, как метод Гаусса, метод окаймления, метод пополнения, метод сопряжённых градиентов и др. Итерационные методы – это метод простой итерации, метод вращений, метод Зейделя, метод релаксации и др. Здесь будут рассматриваться метод Гаусса, метод простых итераций и метод Зейделя.
1 ПОСТАНОВКА ЗАДАЧИ
В данном курсовом проекте необходимо разработать программу на языке С++, с помощью которой можно находить корни системы линейных алгебраических уравнений. В частности в данном курсовом проекте используются следующие методы: “Метод Гаусса”, “Метод простых итераций”, “Метод Зейделя”. Для нахождения корней системы необходимо преобразовать матрицу в вид, соответствующий к каждому методу, и аналогично найти необходимое решение.
2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
2.1 Разрешимость системы линейных уравнений.
Когда мы говорим о главной матрице системы линейных уравнений, то всегда имеем в виду квадратную матрицу n×n, т. е. матрицу с одинаковым количеством строк и столбцов. Это важно.
Если, например, количество строк (количество уравнений в системе) будет меньше, чем количество столбцов (фактически, количества неизвестных), то система будет неопределенной, т. е. мы не сможем однозначно определить все неизвестные (решить систему).
Но это не единственное ограничение. Из векторной алгебры известно, что система линейных уравнений имеет решение (однозначное) тогда и только тогда, когда ее главный определитель не равен нулю: Δ ≠ 0.
Рассмотрим случай, когда определитель системы равен нулю. Здесь возможны два варианта:
1. Δ = 0 и каждый из дополнительных определителей Δxi = 0. Это имеет место только тогда, когда коэффициенты при неизвестных xi пропорциональны, т. е. каждое уравнение системы получается из первого уравнения умножением обеих его частей на число k. При этом система имеет бесчисленное множество решений.
2. Δ = 0 и хотя бы один дополнительный определитель Δxi ≠ 0. Это имеет место только тогда, когда коэффициенты при всех неизвестных xi, пропорциональны. При этом получается система из противоречивых уравнений, которая не имеет решений.
2.2 Метод Гаусса – прямой и обратный ход.
Рассмотрим метод Гаусса. Например, пусть дана расширенная матрица некоторой системы m линейных уравнений c n неизвестными:
Будем считать, что a11 ≠ 0 (если это не так, то достаточно переставить первую и некоторую другую строку расширенной матрицы местами). Проведем следующие элементарные преобразования:
C2-(a21/a11)*C1,
...
Cm-(am1/a11)*C1,
т.е. Ci-(ai1/a11)*C1, i = 2, 3, ..., m.
Т. е. от каждой строки расширенной матрицы (кроме первой) отнимаем первую строку, умноженную на частное от деления первого элемента этой строки на диагональный элемент а11.
В результате получим матрицу:
Т. е. первая строка осталась без изменений, а в столбце под а11 на всех местах оказались нули. Обратим внимание, что преобразования коснулись всех элементов строк, начиная со второй, всей расширенной матрицы системы.
Теперь наша задача состоит в том, чтобы получить нули подо всеми диагональными элементами матрицы А – aij, где I = j.
Повторим наши элементарные преобразования, но уже для элемента α22.
C1-(a12/α22)*C2,
...
Cm-(αm2/α22)*C2,
т.е. Ci-(αi2/α22)*C2, i = 3, ..., m.
Т. е. от каждой строки расширенной матрицы (теперь кроме первой и второй) отнимаем вторую строку, умноженную на частное от деления первого элемента этой (текущей) строки на диагональный элемент α22.
Такие преобразования продолжаются до тех пор, пока матрица не приведется к верхнее - треугольному виду. Т. е. под главной диагональю не окажутся все нули:
Вспомнив, что каждая строка представляет собой одно из уравнений линейной системы уравнений, легко заметить, что последнее m-ое уравнение принимает вид:
γmn*xn = δm.
Отсюда легко можно найти значение первого корня – xn = δm/γmn.
Подставив это значение в предыдущее m-1-е уравнение, легко получим значение xn-1-ого корня.
Таким образом, поднимаясь до самого верха обратным ходом метода Гаусса, мы последовательно найдем все корни системы уравнений.
Пример 1
Рассмотрим систему уравнений:
Главный определитель данной системы:
Δ = [1*(-4)*(-2)+2*2*1+(-1)*(-1)*(
т. е. Δ ≠ 0.
Т. е. система определена и разрешима. Решим ее по методу Гаусса.
Проведем прямой ход метода Гаусса, выписав предварительно расширенную матрицу системы:
Получим нули под главной диагональю в первом столбце расширенной матрицы. Для получения нуля в элементе a21 (т. е. под диагональю во второй строке матрицы) вторую строку матрицы преобразуем по формуле C2-(a21/a11)*C1 = C2-(2/1)*C1 = C2-2*C1:
Аналогично поступаем и с элементом а31 (т. е. под диагональю в третьей строке матрицы). Третью строку матрицы преобразуем по формуле C3-(a31/a11)*C1 = C3-(-1/1)*C1 = C3+C1:
Таким образом, мы получили нули под главной диагональю в первом столбце расширенной матрицы. Осталось получить нуль под главной диагональю во втором столбце матрицы, т. е. на месте элемента а32. Для этого третью строку матрицы преобразуем по формуле C3-(a32/a22)*C2 = C3-(1/-2)*C2 = C3+1/2C2:
Таким образом, проведя прямой ход метода Гаусса, мы получили расширенную матрицу системы, приведенную к верхне-треугольному виду:
Эта матрица эквивалентна системе:
Обратным ходом метода Гаусса найдем корни системы. Из последнего уравнения найдем корень х3:
-5/2x3 = 3/2,
x3 = (3/2):(-5/2) = 3/2*(-2/5) = -3/5.
Корень x3 = -3/5 найден. Подставим его в верхнее (второе) уравнение системы (-2x2-3x3 = 1):
-2x2-3(-3/5) = 1,
-2x2+9/5 = 1,
-2x2 = 1-9/5,
-2x2 = -4/5,
x2 = (-4/5):(-2) = (-4/5)*(-1/2) = 2/5.
Корень x2 = 2/5 найден. Подставим его и корень х3 в верхнее (первое) уравнение системы (x1-x2+x3 = 0):
x1-2/5+(-3/5) = 0,
x1-5/5 = 0,
x1 = 5/5 = 1.
Проверка:
т. е.
т. е.
и т. д.
Рис.1. Решение методом Гаусса.
Вывод.
Итак, метод Гаусса (или, иначе, метод последовательного исключения неизвестных) состоит в следующем:
1. Путем элементарных преобразований систему уравнений приводят к эквивалентной ей системе с верхне-треугольной матрицей. Эти действия называют прямым ходом.
2. Из полученной треугольной системы переменные находят с помощью последовательных подстановок (обратный ход).
3. При этом все преобразования проводятся над так называемой расширенной матрицей системы, которую и приводят к верхнее - треугольному виду в прямом ходе метода.
2.3 Метод простых итераций.
При большом числе уравнений прямые методы решения СЛАУ (за исключением метода прогонки) становятся труднореализуемыми на ЭВМ прежде всего из-за сложности хранения и обработки матриц большой размерности. В то же время характерной особенностью ряда часто встречающихся в прикладных задачах СЛАУ является разреженность матриц. Число ненулевых элементов таких матриц мало по сравнению с их размерностью. Для решения СЛАУ с разреженными матрицами предпочтительнее использовать итерационные методы.
Методы последовательных приближений, в которых при вычислении последующего приближения решения используются предыдущие, уже известные приближенные решения, называются итерационными.
Рассмотрим СЛАУ
(1.1)
с невырожденной матрицей .
Приведем СЛАУ к эквивалентному виду
(1.2)
или в векторно-матричной форме
.
Такое приведение может быть выполнено различными способами. Одним из наиболее распространенных является следующий.
Разрешим систему (1.1) относительно неизвестных при ненулевых диагональных элементах , (если какой-либо коэффициент на главной диагонали равен нулю, достаточно соответствующее уравнение поменять местами с любым другим уравнением). Получим следующие выражения для компонентов вектора и матрицы эквивалентной системы:
, . (1.3)
При таком способе приведения исходной СЛАУ к эквивалентному виду метод простых итераций носит название метода Якоби.
В качестве нулевого приближения вектора неизвестных примем вектор правых частей или . Тогда метод простых итераций примет вид:
(1.4)
Из (1.4) видно преимущество итерационных методов по сравнению, например, с рассмотренным выше методом Гаусса. В вычислительном процессе участвуют только произведения матрицы на вектор, что позволяет работать только с ненулевыми элементами матрицы, значительно упрощая процесс хранения и обработки матриц.
Имеет место следующее достаточное условие сходимости метода простых итераций.
Метод простых итераций (1.4) сходится к единственному решению СЛАУ (1.2) (а следовательно и к решению исходной СЛАУ (1.1)) при любом начальном приближении , если какая-либо норма матрицы эквивалентной системы меньше единицы
Если используется метод Якоби (выражения (1. 3) для эквивалентной СЛАУ), то достаточным условием сходимости является диагональное преобладание матрицы , т.е. (для каждой строки матрицы модули элементов, стоящих на главной диагонали, больше суммы модулей недиагональных элементов). Очевидно, что в этом случае меньше единицы и, следовательно, итерационный процесс (1.4) сходится.
Приведем также необходимое и достаточное условие сходимости метода простых итераций. Для сходимости итерационного процесса (1.4) необходимо и достаточно, чтобы спектр матрицы эквивалентной системы лежал внутри круга с радиусом, равным единице.
При выполнении достаточного условия сходимости оценка погрешности решения на - ой итерации дается выражением:
, (1.5)
где - точное решение СЛАУ.
Процесс итераций останавливается при выполнении условия , где - задаваемая вычислителем точность.
Принимая во внимание, что из (1.5) следует неравенство , можно получить априорную оценку необходимого для достижения заданной точности числа итераций. При использовании в качестве начального приближения вектора такая оценка определится неравенством:
,
откуда получаем априорную оценку числа итераций при
.
Следует подчеркнуть, что это неравенство дает завышенное число итераций k, поэтому редко используется на практике.
Замечание. Поскольку является только достаточным (не необходимым) условием сходимости метода простых итераций, то итерационный процесс может сходиться и в случае, если оно не выполнено. Тогда критерием окончания итераций может служить неравенство .
Пример. Методом простых итераций с точностью решить СЛАУ.
Р е ш е н и е.
Приведем СЛАУ к эквивалентному виду:
или
где ; ;
, следовательно достаточное условие сходимости метода простых итераций выполнено.
Итерационный процесс выглядит следующим образом.
; ; ;
;
;
; .
Рис.2. Решение методом простых итераций.
Вывод.
Таким образом, вычислительный процесс завершен за 4 итерации. Отметим, что точное решение исходной СЛАУ в данном случае известно . Отсюда следует, что заданной точности удовлетворяло решение, полученное уже на третьей итерации. Но в силу использования для вычисления погрешности оценочного выражения (1.5) (видно, что в данном случае , при этом , хотя ) процесс останавливается только на четвертой итерации.
Отметим также, что априорная оценка необходимого количества итераций в данной задаче дает: , т.е. для достижения точности , согласно априорной оценке, необходимо сделать не менее пяти итераций, что иллюстрирует характерную для априорной оценки тенденцию к завышению числа итераций.
2.4 Метод Зейделя.
Метод простых итераций довольно медленно сходится. Для его ускорения существует метод Зейделя, заключающийся в том, что при вычислении компонента вектора неизвестных на (k+1)-й итерации используются, уже вычисленные на (k+1)-й итерации. Значения остальных компонент берутся из предыдущей итерации. Так же как и в методе простых итераций строится эквивалентная СЛАУ (1.2 и за начальное приближение принимается вектор правых частей . Тогда метод Зейделя для известного вектора на k-ой итерации имеет вид:
.
Из этой системы видно, что , где В - нижняя треугольная матрица с диагональными элементами , равными нулю, а С - верхняя треугольная матрица с диагональными элементами, отличными от нуля, . Следовательно
откуда
Таким образом, метод Зейделя является методом простых итераций с матрицей правых частей и вектором правых частей и, следовательно, сходимость и погрешность метода Зейделя можно исследовать с помощью формул, выведенных для метода простых итераций, в которых вместо матрицы подставлена матрица , а вместо вектора правых частей – вектор . Для практических вычислений важно, что в качестве достаточных условий сходимости метода Зейделя могут быть использованы условия, приведенные выше для метода простых итераций ( или, если используется эквивалентная СЛАУ в форме (1.3 – диагональное преобладание матрицы ). В случае выполнения этих условий для оценки погрешности на -ой итерации можно использовать выражение
.
Отметим, что как и метод простых итераций, метод Зейделя может сходиться и при нарушении условия . В этом случае .
Р е ш е н и е.
Приведение СЛАУ к эквивалентному виду аналогично примеру (1.2). Диагональное преобладание элементов исходной матрицы СЛАУ гарантирует сходимость метода Зейделя.
Итерационный процесс выглядит следующим образом:
Рис.3. Решение методом Зейделя.
Вывод.
Таким образом, уже на второй итерации погрешность , т.е. метод Зейделя в данном случае сходится быстрее метода простых итераций.
ВЫВОД
Огромное количество численных методов ставит актуальной задачей не столько создание новых, сколько исследование и классификацию старых, выявление лучших. Анализ влияния ошибок показал, что между лучшими методами нет принципиальной разницы с точки зрения устойчивости к ошибкам округления. Создание мощных компьютеров существенно ослабило значение различия между методами (в таких характеристиках, как объём требуемой памяти, количество арифметических операций). В этих условия наиболее предпочтительными становятся те методы, которые не очень отличаются от лучших по скорости и удобству реализации на компьютерах, позволяют решать широкий класс задач как хорошо, так и плохо обусловленных и давать при этом оценку точности вычислительного решения.
Программа на Visual С++ намного упрощает задачу. С помощью единожды созданной программы можно решать системы линейных уравнений, вводя минимум значений.
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ
1. Е.П.Путятiн, В.П.Степанов, В.П.Пчелiнов, Т.Г.Долженкова, О.О.Матат. Основи програмування мовою С++: Навчальний посiбник – Х.: ТОВ «Компанiя Смiт», 2005. – 320 с.
2. Методичнi вказiвки до курсового проектування з дисциплiни «Програмування» / Упоряд.: Т.Г.Долженкова, Д.О.Руденко – Х.: ХНУРЕ, 2004. – 16 с.
3. В.П. Дьяконов. Справочник по алгоритмам и программам на языке бейсик для персональных ЭВМ. “Наука” – Москва, 1987. – 240 с.
ПРИЛОЖЕНИЕ А Текст программы
Main.cpp
#include "stdafx.h"
#include "Gauss.h"
#include "Zeidel.h"
#include "SI.h"
#include <conio.h>
using namespace GAUSS;
using namespace ZEIDEL;
using namespace SimpIter;
void main ()
{
setlocale (LC_ALL, "Rus");
cout << "********************| Методы решения СЛАУ |*********************\n";
int Method=9;
while (Method != 0)
{
cout << "\n***************************
cout << "\nВыбирите метод:";
cout << "\nМетод Гаусса - нажмите 1";
cout << "\nМетод Зейделя - нажмите 2";
cout << "\nМетод простых итераций - нажмите 3";
cout << "\nВыход - нажмите 0\n";
cin >> Method;
if (Method==1) Gauss();
if (Method==2) Zeidel();
if (Method==3) SI ();
}
}
Gauss.h
#include "stdafx.h"
#include <iostream>
#include <conio.h>
using namespace std;
namespace GAUSS
{
double **Create (int a, int b)
{
double **p = new double *[a];
for (int i=0; i<a; i++)
p[i] = new double [b];
return p;
}
//============ заполнение ==============================
void Fill (double **arr, int a, int b)
{
setlocale (LC_ALL, "Russian_Russia.1251");
cout << "Введите коэффициенты:\n";
for(int i = 0; i < a; i++) {
for(int j = 0; j < b; j++)
cin >> arr[i][j];
}
cout << "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
}
//===================== вывод матрицы ==============================
void PrintMatr(double **matr, int n, int m)
{
for(int i = 0; i < n; i++) {
cout << "\n";
for(int j = 0; j < m; j++)
cout << matr[i][j] <<"\t";
cout << "\n";
}
cout << "\n~~~~~~~~~~~~~~~~~~~~~~~~~~~
}
//==================== треугольный вид ==============================
void Change(double **matr, double *mas, const int n)
{
int i,j,k;
double t;
for(i=0; i<n-1; i++)
for(j=i+1; j<n; j++)
for(k=n; k>i-1; k--)
matr[j][k] = matr[j][k]-matr[i][k]*matr[j][
for(i=n-1; i>=0; i--)
{
for(t=0, j=i+1; j<=n-1; j++)
t = t + matr[i][j]*mas[j];
mas[i] = (matr[i][n] - t)/matr[i][i];
}
}
// ==================== вывод корней системы =======================
void PrintResult(double *mas, const int n)
{
cout << "корни системы: " << endl;
int i;
for(i=0; i<n; i++) {
cout << "\n\tx" <<i+1 <<" = " << mas[i];
}
cout << "\n\n=========================
cout << "=============================
}
void Gauss ()
{
setlocale (LC_ALL, "Russian_Russia.1251");
cout << "\n\t\tМЕТОД ГАУССА\n\n";
int n, m;
//====================== ввод кол-ва уравнений =========================
bool STOP;
do {
cout << "Введите количество уравнений: ";
- Значение 12-летнего образования в становлении личности младшего школьника
- Значение 12-летнего образования в становлении личности младшего школьника
- Значение Web-сайта в системе маркетинга предприятия
- Значение автомобилестроения для народного хозяйства
- Значение административной деятельности в сфере внутренних дел
- Значение Американского и Японского менеджмента в гостиничной индустрии
- Значение анализа внутренней и внешней среды для организации
- Знаменитые учебные пособия и издания для художников
- Знаменитые ученные металловеды
- Знаменитые центры лаковой миниатюры - Палех, Холуй, Федоскино
- Знание края и его влияние на становление экологически воспитанной личности
- Знания, как фактор производства
- Знахарство у восточных славян
- Знаходження коренів нелінійних рівнянь
