Министерство образования и науки Российской Федерации
Федеральное государственное образовательное учреждение высшего профессионального образования
“ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ”
(ВолгГТУ)
Факультет электроники и вычислительной математике
Кафедра «Высшей математики»
Семестровая работа №1
По дисциплине «Вычислительная математика»
Вариант № 1
Выполнил: студент группы ФЭВТ 1.1С
Беляев В.А.
Проверил преподаватель: Кобышев В.А.
Волгоград, 2012г.
Содержание.
1. Теоретическая часть (идея метода).
2. Задание.
3. Программа.
Теоретическая часть (идея метода).
МЕТОД ГАУССА С ВЫБОРОМ ГЛАВНОГО ЭЛЕМЕНТА.
1. Основная идея метода. Может оказаться, что система
Ax=f (1)
имеет единственное решение, хотя какой-либо из угловых миноров матрицы А равен нулю. В этом случае обычный метод Гаусса оказывается непригодным, но может быть применен метод Гаусса с выбором главного элемента.
Основная идея метода состоит в том, чтобы на очередном шаге исключать не следующее по номеру неизвестное, а то неизвестное, коэффициент при котором является наибольшим по модулю. Таким образом, в качестве ведущего элемента здесь выбирается главный, т.е. наибольший по модулю элемент. Тем самым, если 
, то в процессе вычислений не будет происходить деление на нуль.
Различные варианты метода Гаусса с выбором главного элемента проиллюстрируем на примере системы из двух уравнений
(2)
Предположим, что 
. Тогда на первом шаге будем исключать переменное 
. Такой прием эквивалентен тому, что система (2) переписывается в виде
(3)
и к (3) применяется первый шаг обычного метода Гаусса. Указанный способ исключения называется методом Гаусса с выбором главного элемента по строке. Он эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация переменных.
Применяется также метод Гаусса с выбором главного элемента по столбцу. Предположим, что 
. Перепишем систему (2) в виде
и к новой системе применим на первом шаге обычный метод Гаусса. Таким образом, метод Гаусса с выбором главного элемента по столбцу эквивалентен применению обычного метода Гаусса к системе, в которой на каждом шаге исключения проводится соответствующая перенумерация уравнений.
Иногда применяется и метод Гаусса с выбором главногоэлемента повсей матрице, когда в качестве ведущего выбирается максимальный по модулю элемент среди всех элементов матрицы системы.
2. Матрицы перестановок. Ранее было показано, что обычный метод Гаусса можно записать в виде
где 
-элементарные нижние треугольные матрицы. Чтобы получить аналогичную запись метода Гаусса с выбором главного элемента, необходимо рассмотреть матрицы перестановок.
ОПРЕДЕЛЕНИЕ 1. Матрицей перестановок Р называется квадратная матрица, у которой в каждой строке и в каждом столбце только один элемент отличен от нуля и равен единице.
ОПРЕДЕЛЕНИЕ 2. Элементарной матрицей перестановок 
называется матрица, полученная из единичной матрицы перестановкой к -й и l -й строк.
Например, элементарными матрицами перестановок третьего порядка являются матрицы
Можно отметить следующие свойства элементарных матриц перестановок, вытекающие непосредственно из их определения.
1) Произведение двух (а следовательно, и любого числа) элементарных матриц перестановок является матрицей перестановок (не обязательно элементарной).
2) Для любой квадратной матрицы А матрица 
отличается от А перестановкой к -й и l -é ñòðîê.
3) Для любой квадратной матрицы А матрица 
отличается от А перестановкой к -го и l -го столбцов.
Применение элементарных матриц перестановок для описания метода Гаусса с выбором главного элемента по столбцу можно пояснить на следующем примере системы третьего порядка:
(4)
Система имеет вид (1), где
(5)
Максимальный элемент первого столбца матрицы А находится во второй строке. Поэтому надо поменять местами вторую и первую строки и перейти к эквивалентной системе
(6)
Систему (6) можно записать в виде
(7)
т.е. она получается из системы (4) путем умножения на матрицу
перестановок
Далее, к системе (6) надо применить первый шаг обычного метода исключения Гаусса. Этот шаг эквивалентен умножению системы (7) на элементарную нижнюю треугольную матрицу
В результате от системы (7) перейдем к эквивалентной системе
(8)
или в развернутом виде
(9)
Из последних двух уравнений системы (9) надо теперь исключить переменное . Поскольку максимальным элементом первого столбца укороченной системы
(10)
является элемент второй строки, делаем в (10) перестановку строк и тем самым от системы (9) переходим к эквивалентной системе
(11)
которую можно записать в матричном виде как
. (12)
Таким образом система (12) получена из (8) применением элемен-тарной матрицы перестановок
Далее к системе (11) надо применить второй шаг исключения обычного метода Гаусса. Это эквивалентно умножению системы (11) на элементарную нижнюю треугольную матрицу
В результате получим систему
(13)
или 
(14)
Заключительный шаг прямого хода метода Гаусса состоит в замене последнего уравнения системы (14) уравнением
что эквивалентно умножению (13) на элементарную нижнюю треугольную матрицу
Таким образом, для рассмотренного примера процесс исключения Гаусса с выбором главного элемента по столбцу записывается в
виде
(15)
По построению матрица
(16)
является верхней треугольной матрицей с единичной главной диагональю.
Отличие от обычного метода Гаусса состоит в том, что в качестве сомножителей в (16) наряду с элементарными треугольными матрицами 
могут присутствовать элементарные матрицы перестановок 
.
Покажем еще, что из (16) следует разложение
PA=LU, (17)
где L -нижняя треугольная матрица, имеющая обратную, P - матрица перестановок.
Для этого найдем матрицу
(18)
По свойству 2) матрица 
получается из матрицы 
перестановкой второй и третьей строк,
Матрица 
согласно свойству 3) получается из перестановкой второго и третьего столбцов
т.е. 
-нижняя треугольная матрица, имеющая обратную.
Из (18), учитывая равенство 
, получим
(19)
Отсюда и из (16) видно, что
где обозначено 
. Поскольку Р -матрица перестановок и L -нижняя треугольная матрица, свойство (17) доказано. Оно означает, что метод Гаусса с выбором главного элемента по столбцу эквивалентен обычному методу Гаусса, примененному к матрице РА, т.е. к системе, полученной из исходной системы перестановкой некоторых уравнений.
3. Общий вывод. Результат, полученный ранее для очень частного примера, справедлив и в случае общей системы уравнений (1).
А именно, метод Гаусса с выбором главного элемента по столбцу можно записать в виде
(20)
где 
- элементарные матрицы перестановок такие, что
и -элементарные нижние треугольные матрицы.
Отсюда, используя соотношения перестановочности, аналогичные (19), можно показать, что метод Гаусса с выбором главного элемента эквивалентен обычному методу Гаусса, примененному к системе
PAx=Pf, (21)
где Р - некоторая матрица перестановок.
Теоретическое обоснование метода Гаусса с выбором главного элемента содержится в следующей теореме.
ТЕОРЕМА 1. Если 
то существует матрица перестано-
вок Р такая, что матрица РА имеет отличные от нуля угловые ми-
норы.
Доказательство в п.4.
СЛЕДСТВИЕ. Если то существует матрица престана-
вок Р такая, что справедливо разложение
РА=LU, (22)
где L- нижняя треугольная матрица с отличными от нуля диагональными элементами и U- верхняя треугольная матрица с единичной главной диагональю. В этом случае для решения системы (1) можно применять метод Гаусса с выбором главного элемента.
4. Доказательство теоремы 1. Докажем теорему индукцией по числу m -порядку матрицы А.
Пусть m=2, т.е.
Если 
то утверждение теоремы выполняется при Р=Е, где Е - единичная матрица второго порядка. Если 
, то 
, т.к. 
При этом у матрицы
все угловые миноры отличны от нуля.
Пусть утверждение теоремы верно для любых квадратных матриц порядка m -1. Покажем, что оно верно и.для матриц порядка m. Ра зобьем матрицу А порядка m на блоки
где
Достаточно рассмотреть два случая: 
и 
. В первом случае по предположению индукции существует матрица перестановок 
порядка m-1 такая, что 
имеет отличные от нуля угловые миноры. Тогда для матрицы перестановок
имеем
причем 
. Тем самым все угловые миноры матрицы РА отличны от нуля. Рассмотрим второй случай, когда 
. Т.к. 
, найдется хотя бы один отличный от нуля минор порядка m-1 матрицы А, полученный вычеркиванием последнего столбца и какой-либо строки. Пусть, например,
где 
.
Переставляя в матрице А строки с номерами l и m, получим матрицу 
, у которой угловой минор порядка m-1 имеет вид
и отличается от (23) только перестановкой строк. Следовательно, этот минор не равен нулю и мы приходим к рассмотренному выше случаю.
Теорема доказана.
Задание.
a) Решить систему уравнений методом Гаусса с выбором главного элемента (с частичным выбором главного элемента).
b) Найти обратную матрицу к матрице коэффициента.
Программа.
Метод Гаусса с выбором главного элемента.
#include<iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
float det(float [20][20], int);
void iskl(float a[20][20], int k, int n)
{
int i, j;
float r, b[40];
r=a[k][k];
for (j=k; j<n+1; j++) a[k][j]/=r;
for (i=k+1; i<n; i++)
{
r=a[i][k];
for(j=k; j<n+1; j++) a[i][j]-=a[k][j]*r;
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int i, j, n, k;
float a[20][20], d[20][20], b[40], temp[20][20], t, intDet;
char anyKey;
//____sozdanie____
ofstream outfile("matr1.txt");
cout<<"VVedite razmernost yravneniya: ";
cin >> n;
cout<<endl;
cout<<"Vvedite postro4no matricy:"<<endl;
for (i=0; i<(n*n+n); i++)
{
cin >> t;
outfile << t <<" ";
}
outfile.close();
cout<<"Poly4ennaya matrica:"<<endl;
//_____4tinie i pe4at_____
fstream infile("matr1.txt");
for (i=0; i<n; i++) //bilo n+1
{
cout<<endl;
for (j=0; j<n+1; j++)
{
infile >> t;
temp[i][j]=t;
cout<<t<<" ";
}
}
for (i=0; i<n; i++)
for (j=0; j<n; j++)
a[i][j]=temp[i][j];
//vector
// for (i=0; i<n; i++)
// b[i]=temp[i][n+1];
intDet=det(a, n);
if (intDet==0)
{
cout<<"Reweniya net. ";
goto net;
}
else
{
cout<<"Sistema rewaema)) YRA))"<<endl;
cout<<"det= "<<intDet;
}
cout<<"Treygolnii vid:"<<endl;
for (i=0; i<n; i++) iskl(temp, i, n);
for (i=0; i<n; i++)
{
cout<<endl;
for (j=0; j<n+1; j++) cout<<temp[i][j]<<' ';
}
cout<<"\n";
for (i=0; i<n+1; i++){b[i]=temp[i][n]; cout<<b[i]<<" ";}
cout<<"\n"<<"Rewenie SLAY:"<<endl;
for (i=n; i>-1; i--)
{
b[i]/=temp[i][i];
for (j=i+1; j<n; j++) b[i]-=b[j]*temp[i][j];
}
for (i=0; i<n; i++) cout<<b[i]<<" ";
net:
cout<<"\nPress anykey to exit.";
cin>>anyKey;
return 0;
}
float det(float b[20][20], int n)
{
float x,s;
int i,j,k;
for (i=0; i<n-1; i++)
for (k=i+1; k<n; k++)
{
x=b[k][i]/b[i][i];
for (j=i; j<n; j++) b[k][j]=b[k][j]-b[i][j]*x;
}
s=1;
for (i=0; i<n; i++) s=s*b[i][i];
return s;
}
Нахождение обратной матрицы к матрице коэффициента.
#include<iostream>
#include <stdio.h>
#include <math.h>
#include <stdlib.h>
using namespace std;
static int n;
void obrat(double **a)
{double **d,vrem,max,tryam;
int i,j,*p,jmax,temp;
d=new double *[2*n];
for (i=0;i<n;i++) d[i]=new double[n];
for(i=0;i<n;i++)
{for(j=0;j<n;j++)d[i][j]=a[i][j];
for(j=n;j<2*n;j++)
{if(j==n+i)d[i][j]=1;
else d[i][j]=0;
}
}
p=new int[n];
for(j=0;j<n;j++)p[j]=j;
//k-nomer pervogo uravn
for(int k=0;k<n-1;k++)
{max=fabs(d[k][k]);
jmax=j;
for(j=k;j<n;j++)
if(fabs(d[k][j])>max)
{max=fabs(d[k][j]);
jmax=j;
temp=p[k];
p[k]=p[jmax];
p[jmax]=temp;
}
for(i=k;i<n;i++)
{tryam=d[i][k];
d[i][k]=d[i][jmax];
d[i][jmax]=tryam;
}
for(i=k+1;i<n;i++)
{vrem=d[i][k]/d[k][k];
for(j=k;j<2*n;j++) d[i][j]-=vrem*d[i][j];
}
}
for(int k=n-1;k>0;k--)
{for(i=k-1;i>=0;i--)
vrem=d[i][k]/d[k][k];
for(j=k;j<2*n;j++)d[i][j]-=vrem*d[i][j];
}
for(i=0;i<n;i++)
{for(j=n;j<2*n;j++)
d[i][j]=d[i][j]/d[i][i];
d[i][i]=1;
}
for(i=0;i<n;i++)
{for(j=n;j<2*n;j++)
cout<<d[p[i]][j]<<" ";
cout<<endl;
}
}
int main ()
{int i,j;
cout<<"vvedite razmer matrici"<<endl;
cin>>n;
double **a;
a=new double*[n];
for (i=0;i<n;i++) a[i]=new double[n];//i-stroki,j-stolbci
for(i=0;i<n;i++)
{for(j=0;j<n;j++)
{cout<<" vvedite elementi matrici a["<<i<<"]["<<j<<"]"<<endl;
cin>>a[i][j];
}
}
for (i=0;i<n;i++)//vivod matrici
{
for(j=0;j<n;j++)
cout<<a[i][j]<<" ";
}
obrat(a);
getchar ();
getchar ();
return 0;
}
Результат:
