Теоретическая часть (идея метода)

Министерство образования и науки Российской Федерации

Федеральное государственное образовательное учреждение высшего профессионального образования

“ВОЛГОГРАДСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ”

(ВолгГТУ)

Факультет электроники и вычислительной математике

Кафедра «Высшей математики»

Семестровая работа №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;

}

Результат: