Поиск решений системы линейных уравнений методом Гаусса (стр. 3 из 3)

Если мы смогли привести нашу систему уравнений к такому треугольному виду, то решить уравнения уже просто. Из последнего уравнения находим x_N= b_N / a_NN. Дальше подставляем его в предпоследнее уравнение и находим из него x_N-1. Подставляем оба найденных решения в следующее с конца уравнение и находим x_N-2. И так далее, пока не найдем x₁, на чем решение заканчивается. Такая процедура называется обратной прогонкой.

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

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

Нужно, чтобы во второй строке получилось уравнение, в которой отсутствует член при x₁. Прибавим к этой строке первую строку, умноженную на некоторое число M.

(a₁₁x₁ + a₁₂x₂ + a₁₃x₃ + ... a_1Nx_N = b₁)*M +

a₂₁x₁ + a₂₂x₂ + a₂₃x₃ + ... a_2Nx_N = b₂

Получим

(a₁₁*М + a₂₁) x₁ + ... = b₁*M + b₂

Для того, чтобы член при x₁ равнялся нулю, нужно, чтобы M = - a₂₁ / a₁₁. Проделав эту операцию, получившееся уравнение запишем вместо второго и приступим к третьему уравнению. К нему мы прибавим первое уравнение, умноженное на M = - a₃₁ / a₁₁ и тоже получим ноль вместо члена при x₁. Такую операцию нужно проделать над всеми остальными уравнениями. В результате получим систему такого вида:

a₁₁x₁ +	a₁₂x₂ +	a₁₃x₃ +	...	a_1Nx_N = b₁
a₂₂x₂ +	a₂₃x₃ +	...	a_2Nx_N = b₂
a₃₂x₂ +	a₃₃x₃ +	...	a_3Nx_N = b₃
...
a_N2x₂ +	a_N3x₃ +	...	a_NNx_N = b_N

После этого будем избавляться от членов при x₂ в третьем, четвертом, N-ом уравнении. Для этого нужно к уравнению с j-м номером прибавить 2-ое уравнение, умноженное на M = - a_j2 / a₂₂. Проделав эту операцию над всеми остальными уравнениями, получим систему где нет членов с x₂ в уравнениях с номером больше 2.

И так далее... Проделав это для третьего члена, четвертого... до тех пор, пока не кончатся уравнения, получим в итоге систему треугольного вида.

Алгоритм описан в псевдокоде (команды в виде текста на русском языке).

ПРОЦЕСС 0: (главный процесс)

1.Разослать всем процессам количество текущих строк.

(Или не всем процессам, если процессов больше чем строк).

2.ЦИКЛ ПО СТРОКАМ (выбор текущей строки)

1.Разослать всем процессам текущую строку.

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

2.Разослать всем процессам строки для обработки (посылаем строку, затем строки в матрице). Разделить между процессами строки ниже текущей. Разделяем так в цикле по строкам раздаём по одной каждому процессу, пока не кончатся строки, по процессам 1..N идём циклически.

3.Разослать всем процессам количества строк, посланных им для обработки.

4.Принять от процессов 1..N обработанные строки, занести их в матрицу. (Принимаем строку и номер строки в матрице)

5.Выбрать следующую текущую строку - новый шаг цикла.

КОНЕЦ ЦИКЛА

3.Вычислить решение системы по диагональной матрице.

4.Выдать результат работы.

5.Завершить работу.

ПРОЦЕСС 1..N:

1.Принимаем количество текущих строк.

2.ЦИКЛ ОБРАБОТКИ ПОЛУЧЕННЫХ СТРОК

1.Принимаем сообщение о количестве строк для обработки

2.Если число строк для обработки >0 то:

{

1.Принимаем сообщение с текущей строкой

2.ЦИКЛ обработки строк

1.Принимаем сообщение со строкой для обработки .

(получаем ещё номер строки в матрице).

2.Обрабатываем полученную строку

3.Посылаем главному процессу результаты работы. Для каждой строки посылаем строку и номер строки.

4.Идём на новый шаг цикла обработки строк.

3.Синхронизируемся .

}

3.Завершить процесс.

4.Исходный текст программы

Составить программу решения систем линейных алгебраических уравнений с квадратной невырожденной матрицей порядка n методом Гаусса с использованием языка С++ .

// Решение системы линейных уравнений методом Гаусса.

#include<io.h>

#include "stdio.h"

#include "conio.h"

#include <windows.h>

#include <iostream>

#include <time.h>

#include <io.h>

#include <fcntl.h>

#include <string.h>

#include "stdafx.h"

using namespace std;

#include <stdio.h> // Описанияфункцийввода-вывода

#include <math.h> // Описания математических функций

#include <stdlib.h> // Описанияфункций malloc и free

const int n=3;

void ReadData()

{

int n;

double A[n][n];

FILE*f=fopen("l1.txt","rt");

if (f!=0)

printf("CAN'T OPEN FILE\nPlease, f**k off!");

{

fscanf(f,"%d",&n);

printf("Sborka matritsi m- na n-:\n");

for (int i=0;i<n;i++)

{

for(int j=0;j<n;j++)

{

fscanf(f,"%d",&A[i][j]);

printf("%d",A[i][j]);

}

printf("\n");

}

printf("\n\n");

fclose(f);

}

void Gauss

( double X[n], const double Z[n][n], const double Y[n])

{

ReadData();

double A[n][n]; // матрицакоэффицентовГаусса

double B[n]; // рабочий массив свободных членов

int i,

int j,

int k; // рабочие переменные

for( i = 0; i < n; i++ ) // копирование в рабочую матрицу A

{

for( j = 0; j < n; j++ )

A[i][j] = Z[i][j];

B[i] = Y[i]; // копирование свободных членов

X[i] = 0;

}

for( k = 0; k < n-1; k++ )

for( i = k+1; i < n; i++ ) // преобразованиестрок

{

double r = A[i][k] / A[k][k];

for( j = k; j < n; j++ )

A[i][j] -= A[k][j] * r;

B[i] -= B[k] * r;

}

X[n-1] = B[n-1] / A[n-1][n-1];

for( i = n-2; i >= 0; i-- )

{

double s = 0;

for( j = i+1; j < n; j++ )

s += A[i][j] * X[j];

X[i] = ( B[i] - s ) / A[i][i];

}

printf( "\n" );

for( i = 0; i < n; i++ )

{ printf( "\n" );

for( j = 0; j < n; j++ )

printf( "%8.2lf", A[i][j] );

printf( " %8.2lf", B[i] );

}

/* ------------------------------------------------- */

void main( void )

{

ReadData();

doubleX[n];// корни системы линейных уравнений

shorti, j; // рабочиепеременные

printf( " matritsa A* matritsa B\n" );

for( i = 0; i < n; i++ ) // циклстрок

{

printf( "\n" ); // новая строка на мониторе

for( j = 0; j < n; j++ )

printf( "%8.2lf", A[i][j] );

printf( " %8.2lf", B[i] );

}

printf( "\n" );

printf( "stypen4atii vid matritsi \n" );

Gauss( X, A, B ); // решение методом Гаусса

printf( "\n" );

printf( " zna4enia peremennih x1,x1,x3\n" );

printf( "\n X = " );

for( i = 0; i < n; i++ )

printf( "%8.2lf", X[i] );

printf( "\n" );

printf( "rang=\n" );

getch();

}

5.Тестирование программы

Результаты решения системы с тремя неизвестными:

Результаты решения системы с четырьмя неизвестными:

Данные в файле:

Имя файла l1

2 1 4 1

3 1 3 2

2 4 5 1

5 2 2 2

Размерности матриц=4

Матрица А

2 1 4

3 1 3

2 4 5

5 2 2

Матрица В

Вывод

В результате выполнения курсового проекта были разработаны два класса функций для решения простейших задач линейной алгебры. Число этих функций сравнительно невелико, однако можно легко добавить в эти классы более сложные функции, построенные на базе уже имеющихся. Классы позволяют работать с матрицами и векторами, элементы которых могут быть любого типа, однако на практике чаще всего используется целый тип и тип чисел с плавающей запятой. Классы написаны на языке С++, однако могут быть легко переписаны на любом из современных языков программирования, так как приведены довольно простые алгоритмы всех компонентных функций. Были максимально предусмотрены всевозможные ошибки, которые могут возникнуть при использовании функций данных классов. Особое внимание уделялось разумному выделению памяти подобъекты во время выполнения программы, поэтому все функции были тщательно отлажены.Классы Matrix и Vector могут быть эффективно применены на практике в задачах, требующих операций с матрицами и векторами, а также связанных с решением систем линейных алгебраических уравнений.

Список литературы

1. Начальный курс С и С++.: Учебник. /Б. И. Березин. Москва:"ДИАЛОГ-МИФИ",1999г.

2. Язык программирования С++. : Учебник. /. Страуструп. Киев:"ДиаСофт", 1993 г.

3. Введение в язык С++: Учебник. /Бьярн Страустрап.

– СПб.: 1995.

4. Структуры и алгоритмы обработки данных: Учебник. / Матьяш В.А., Путилов В.А., Фильчаков В.В. , Щёкин С.В. - Апатиты, КФ ПетрГУ, 2000

5. С++ /Дэвис Стефан Р.,4-е издание : Пер. с англ.:- М.: Издательский дом «Вильямс»,2003

6. Основы программирования: Учеб. Для сред. проф. образования /И.Г.Семакин, А.П.Шестаков. – М., 2006.

7. С++ экспресс курс: Учебник. /Лаптев В.В. – СПб.: БХВ- Петербург 2004.

8. С++ учебный курс: Учебник. /Франка П. – СПб.:Питер 2005.

9. МОДЕЛИ И CТРУКТУРЫ ДАННЫХ:/ Учебное пособие/

Д.Далека, А.С. Деревянко, О.Г. Кравец, Л.Е. Тимановская -Харьков:ХГПУ, 2000

10.Высшая математика для экономистов: учебник для студентов вузов/Н.Ш.Кремер,3-е издание.-М.:ЮНИТИ-ДАНА,2006