Міністерство освіти і науки України

Сумський Державний Університет

Курсова робота

з дисципліни Чисельні методи

На тему

Методи розв'язання СЛАР (метод Краута)

Виконав

Студент факультету ЕлІТ

групи ІН-83

Горбатенко О. О.

Перевірив

Ободяк В.К.

Суми 2010

Системи лінійних алгебраїчних рівнянь

Дана система m лінійних алгебраїчних рівнянь з n невідомими

	(1.1.1)

або, у матричній формі

	(1.1.2)
, , .	(1.1.3)

Означення 1. Розв'язком системи (1.1) називається n-компонентний вектор-стовбець , який перетворює матричне рівняння (1.2) у вірну числову тотожність.

Означення 2. Система називається сумісною, якщо є хоча б один розв'язок. У протилежному випадку система називається несумісною.

Означення 3. Дві системи еквівалентні, якщо множини їх розв'язків співпадає.

Теорема Кронекера-Капеллі. Для того що б система лінійних неоднорідних рівнянь була сумісною, необхідно і достатньо, щоб ранг матриці коефіцієнтів дорівнював рангу розширеної матриці.

Теорема Крамера. Для того що б система лінійних неоднорідних рівнянь з невідомими мала единий розв'язок, необхідно і достатньо, щоб визначник матриці коефіцієнтів відрізнявся від нуля. У противному випадку неоднорідна система не має розв'язків або має їх безліч.

Методи розв'язання СЛАР

Методи розв'язування СЛАР можна досить чітко поділити на три групи: точні, ітераційні та ймовірнісні. Точні методи застосовні до систем з числом змінних до порядку 10⁴, ітераційні -- 10⁷.

Ітераційні методи

При виконанні умов збіжності дозволяють досягти будь-якої точності просто повторенням ітерацій.

1. Метод простої ітерації

2. Метод Зейделя

Метод простої ітерації

Дана система лінійних алгебраїчних рівнянь

.	(1.3.1)

Зведемо систему (1.3.1) до виду:

,	(1.3.2)

де - деяка матриця, а - вектор-стовбець.

Починаючи з вектора , будуємо ітераційних процес:

, ,	(1.3.3)
.	(1.3.4)

Отримуємо послідовність векторів: .

Доведено, що якщо норма матриці менше за одиницю:

,	(1.3.5)

то ітераційний процес збігається до точного розв'язку системи при довільному початковому векторі . Процес ітерацій завершують, коли оцінки свідчать про те, що задана точність отримана.

Метод Зейделя

Метод Зейделя - це модифікація методу простої ітерації. У методі простої ітерації при обчисленні компонентів вектора-стовпця на -му кроці використовують значення вектора-стовпця , обчисленого на попередньому кроці. Метод Зейделя відрізняється від методу простої ітерації тільки тим, що при обчисленні -го наближення компоненти враховують значення , обчислені на цьому ж кроці.

Формули для знаходження послідовних наближень мають вигляд:

.	(1.3.10)

Умови збіжності для методу простої ітерації справедливі й для методу Зейделя. Перевага ітераційних методів перед точним методом Гаусса в тому, що машинний час, потрібний для обчислень методом Гаусса, пропорційний , а ітераційними методами він пропорційний на одну ітерацію. Похибки округлень при використанні методу Гаусса можуть призвести до хибного результату, тоді як незначні похибки, допущені при обчисленнях ітераційними методами, не впливають на кінцевий результат. Слід зазначити, що ітераційні методи дають можливість значно скоротити обсяг пам'яті ЕОМ, потрібний для зберігання коефіцієнтів системи, оскільки для обчислення наближення використовуються коефіцієнти тільки -го рівняння.

Точні методи

До таких відносяться методи, що дають точний результат у припущенні ідеальної арифметики .

1. Матричний метод - певна теоретична абстракція всіх інших точних методів.

2. Метод квадратного кореня -- квадратичний метод, який вимагає симетричної матриці системи.

3. Метод прогонки зручний для розв'язування систем з трьохдіагональною матрицею, які часто виникають в задачах математичної фізики.

4. Метод Гауса -- метод, найчастіше застосовуваний при ручному розв'язуванні СЛАР.

o Метод Гауса-Жордана - модифікація методу Гауса.

5. Метод Крамера -- чисто теоретичний метод, непридатний до практичного використання через обчислювальну складність (n! доданків у самому лише визначнику за Крамаром) і неточність.

Метод Крамера

Дана система n лінійних алгебраїчних рівнянь з n невідомими

	(1.2.1)

Система (1.2.1), має єдиний розв'язок, якщо визначник цієї системи відрізняється від нуля: . Позначимо: - визначник, отриманий з заміною стовпця коефіцієнтів стовпцем коефіцієнтів (, ).

Наприклад,

.	(1.2.2)

Тоді розв'язок системи рівнянь (1.2.1) отримуємо за формулами Крамера:

, .	(1.2.3)

Якщо і не всі , то система (1.2.1) несумісна, тобто не має жодного розв'язку.

Формули Крамера мають велике теоретичне значення, але через великий обсяг обчислювальної роботи мало ефективні при чисельному розв'язуванні лінійних алгебраїчних систем, тому що за цими формулами треба обчислювати значення -го визначника порядку .

Метод оберненої матриці

Система (1.2.1) може бути записана у матричному вигляді:

,	(1.2.4)

тоді, розв'язок системи (1.2.1):

,	(1.2.4)

де - матриця, обернена до матриці .

Метод Гауcса

Система m лінійних алгебраїчних рівнянь з n невідомими

	(1.2.5)

Прямий хід методу Гауса:

	(1.2.6)

де - нові коефіцієнти при змінних, - нові праві частини.

Зворотній хід методу Гауса:

, .	(1.2.7)

Корені лінійних систем алгебраїчних рівнянь за методом Гаусса на сучасних ЕОМ обчислюють за спеціальними стандартними програмами. При розв'язанні СЛАР методом Гаусса виконують округлення, тому виникають різниці між значеннями лівих частин і значеннями правих частин (нев'язки). Якщо нев'язки досить малі, то можна стверджувати, що розв'язок системи знайдено з малими похибками.

Метод Жордана-Гаусса

Для розв'язання системи (1.1.1) методом Жордана-Гаусса розширену матрицю записуємо у таблицю 1:

Табл.1

х1	х2	х3	…	xj	хn	B	?
a11	a12	a13	…	a1j	a1n	b1	?1
a21	a22	a23	…	a2j	a2n	b2	?2
a31	a32	a33	…	a3j	a3n	b3	?3
…	…	…	…	…	…	…	…
ai1	ai2	ai3	…	aij	ain	bi	?i
…	…	…	…	…	…	…	…
am1	am2	am3	…	amj	amn	bm	?m

де -сума елементів і-рядка, і=1,2,…,m.

Крок 1. Обираємо головний елемент серед коефіцієнтів (; ).

Крок 2. Поділимо і-й рядок на головний елемент a_ij. Отримаємо нові елементи:

; ; ... ; ; ... ; ; ; .

Крок 3. Стовпчик, у якому знаходиться головний елемент a_ij заповнюємо нулями.

Крок 4. Коефіцієнти в інших рядках перераховуємо за формулами прямокутників (2.2), (2.3), (2.4):

(2.2)

(2.3)

Отримаємо систему:

х1	х2	х3	…	хj	…	хn	B	?
a11	a12	a13	…	0	…	a1n	b1	?1
a21	a22	a23	…	0	…	a2n	b2	?2
a31	a32	a33	…	0	…	a3n	b3	?3
…	…	…	…	…	…	…	….	…
aі1	aі2	aі3	…	1	…	aіn	bi	?i
…	…	…	…	…	…	…	….	…
am1	am2	am3	…	0	…	amn	bm	?i

Крок 5. Обираємо новий головний елемент серед коефіцієнтів матриці А, при умові: .

Ітерації згідно алгоритму (шаг 1 - шаг 5) проводимо, поки розширена матриця системи (1.1) не буде записана у вигляді (2.5) або (2.10).

Перший випадок: :

	(2.5)

Зауваження: одиничні елементи в матриці (2.5) не обов'язково будуть розміщені по діагоналі. Ми наводимо даний вигляд для наочності.

Матриця (2.5) є розширеною матрицею системи:

	(2.6)

де ; - елементи після r - перерахунків (; ).

Система (2.6) еквівалентна системі (1.1).

Якщо хоча б один із коефіцієнтів ; ; ... ; відрізняється від нуля, то система (2.6) несумісна. Тобто система (1.1) також несумісна.

Якщо , то системи (2.6) і (1.1) сумісні.

Розділимо невідомі x₁; x₂; ... ; x_n на дві групи:

базисні змінні x₁; x₂; ... ; x_r - змінні, коефіцієнти при яких утворюють одиничні вектори;

змінні з вільними коефіцієнтами x_r+1; x_r+2; ... ; x_n.

Щоб записати загальний розв'язок системи, необхідно з кожного рівняння (2.6) знайти базисну змінну:

	(2.7)

Якщо змінним x_r+1; x_r+2; ... ; x_n надати значення нуль:

x_r+1 = x_r+2 = ... = x_n = 0 (2.8)

то отримаємо так званий базисний розв'язок:

 . (2.9)

Приклад 2. Розв'язати систему методом Жордана-Гаусса:

Розв'язання:

х1	х2	х3
5	-4	-1	-2	-2
4		-2	8	11
3	1	-5	10	9
21	0	-9	30	42=42
4	1	-2	8	11
	0	-3	2	-2=-2
0	0		72	0=0
0	1	-14	16	3=3
1	0	3	-2	2
0	0	1	-1	0
0	1	0	2	3=3
1	0	0	1	2=2

Відповідь: , , .

LU розклад матриці(Метод Краута)

Комп'ютерна реалізація методу Гауса часто здійснюється з використанням LU-розкладання матриць.

LU - розкладання матриці A є розкладанням матриці A в твір нижньої і верхньої трикутних матриць, тобто

A=LU

де L - нижня трикутна матриця (матриця, у якої всі елементи, що знаходяться вище за головну діагональ рівні нулю lij=0 при i>j), U- верхня трикутна матриця (матриця, у якої всі елементи, що знаходяться нижче за головну діагональ рівні нулю uij=0 при i>j).

LU - розкладання може бути побудовано з використанням описаного вище методу Гауса. Розглянемо k - ий крок методу Гауса, на якому здійснюється обнулення піддіагональних елементів k - го стовпця матриці. Як було описано вище, з цією метою використовується наступна операція

В термінах матричних операцій така операція еквівалентна множенню A^(k)=M^kA^(k-1), де елементи матриці визначаються таким чином

В результаті прямого ходу методу Гауса одержимо,

A^(n-1)=U

де A^(n-1)=U - верхня трикутна матриця, а L - нижня трикутна матриця, що має вигляд .



Таким чином, шукане розкладання A=LU одержано.

Алгоритм Краута - це фактично метод розв'язання систем загального вигляду, конкуруючий за швидкодією із загальновідомим методом Гауса-Жордана, але дозволяє більш ефективно використовувати рішення.

(потребує 2n³ / 3 арифметичних операцій).

Якщо ми можемо розкласти матрицю лінійної системи A у вираз A = L * U, де L - нижня, а U - верхня трикутні матриці, то рішення системи рівнянь з довільною правою частиною проводиться дуже просто, застосуванням двох зворотних підстановок. Більш того, на відміну від відомого методу Гауса-Жордана, розкладена матриця дозволяє швидко вирішувати серії лінійних рівнянь з різними правими частинами при одній і тій же матриці. Метод Краута дозволяє провести LU-декомпозицію матриці приблизно за те ж число операцій, що і "пряма" частина методу Гауса-Жордана. Підсумкові коефіцієнти двох трикутних матриць упаковуються в матрицю того ж розміру, що і A, і на тому ж місці в пам'яті; при цьому верхня матриця U розміщується в наддіагональній частині та на діагоналі; нижня L в поддіагональній частини, а діагональні елементи L вважаються всі рівними 1 (без обмеження спільності) і не виводяться.

Алгоритм Краута представляє із себе наступне: 1. Покласти Lii = 1 i = 0 ,..., N-1 (тут нічого не виробляється, а тільки мається на увазі для подальших кроків; 2. Для кожного j = 0,1 ,..., N-1 виконати: 1. Для всіх i = 0 ,..., j обчислити Uij: Uij = Aij - SUM (0 <= k <i) (Lik * Uik) (При i = 0 суму вважати нулем); 2. Для всіх i = j +1 ,..., N-1 обчислити: Lij = Aij - SUM (0 <= k <j) (Lik * Uik)) / Uii Обидві процедури виконуються до переходу до нового j. Стійка робота алгоритму Краута можлива тільки за умови вибору ведучого елемента для кожного звернення до j з п.2 алгоритму. Вибір виконується перед виконанням п.2 для чергового j перестановки необроблених рядків матриці так, щоб рядок, який пiдставляється на місце j, містив найбільший за модулем елемент у колонці j. Порядок перестановки необхідно запам'ятати, для чого достатньо використовувати додатковий вектор цілих величин. Ще один вектор використовується усередині алгоритму для масштабування. Алгоритм Краута має кілька додатків, одне з яких

- рішення системи лінійних рівнянь (зворотня підстановка з урахуванням порядку перестановки рядків)

Якщо в рівнянні

задано A та b. Тоді розв'язок отримується в два кроки:

1. Розв'язуємо рівняння Ly = b і знаходимо y

2. Розв'язуємо рівняння Ux = y і знаходимо x.

- обчислення оберненої матриці та обчислення детермінанта.

Програмна реалізація.

Нижче приведений код програми реалізації розв'язку СЛАР за допомогою LU розкладання. Крім того тут були введені деякі модифікації, а саме вибір максимального елемента в стовпчику, так як за теоремою про існування LU розкладання, воно можливе лише за умови, що всі головні мінори відмінні від 0, ця модифікація певною мірою коригує протилежну ситуацію шляхом перестановки стовпців.

//---------------------------------------------------------------------------

#include <stdio.h>

#include <stdlib.h>

#include <dos.h>

#include <vcl.h>

#pragma hdrstop

#include "Unit1.h"

//---------------------------------------------------------------------------

#pragma package(smart_init)

#pragma link "CSPIN"

#pragma resource "*.dfm"

TForm1 *Form1;

//---------------------------------------------------------------------------

__fastcall TForm1::TForm1(TComponent* Owner)

: TForm(Owner)

{

}

//---------------------------------------------------------------------------

void __fastcall TForm1::Button1Click(TObject *Sender)

{

double A[10][10], L[10][10], U[10][10];

double g[10], x[10], B[10];

double buf;

int map[10],pr=0;

int n,i,j;

n=TForm1::CSpinEdit1->Value;

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

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

{

AnsiString s;

s=TForm1::StringGrid1->Cells[j][i];

A[i][j]=s.ToDouble();

}

//Vubir naybilshogo elementu

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

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

if (A[i][i]<A[j][i])

{map[i]=j;

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

{

buf=A[i][k];

A[i][k]=A[j][k];

A[j][k]=buf;

}

}

else map[i]=-1;

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

{

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

{

U[0][i] = A[0][i];pr++;

if (U[0][0]!=0)

{

L[i][0] = A[i][ 0] / U[0][0];pr++;

double sum = 0;

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

{

sum += L[i][k] * U[k][j];

}

U[i][j] = A[i][j] - sum;

if (i > j)

{

L[j][i] = 0;pr++;

}

else

{

sum = 0;

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

{

if (U[i][i]!=0) sum += L[j][k] * U[k][i];

else

{

MessageDlg("Матриця погано обумовлена",mtInformation, TMsgDlgButtons() << mbOK, 0);

exit(0);}

}

L[j][i] = (A[j][i] - sum) / U[i][i];pr++;

}

}

else

{

MessageDlg("Матриця погано обумовлена",mtInformation, TMsgDlgButtons() << mbOK, 0);

exit(0);}

}

}

//------------------------------------------------------------

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

{

AnsiString s;

s=TForm1::StringGrid2->Cells[0][i];

B[i]=s.ToDouble();

}

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

if (map[i]!=-1)

{

buf=B[map[i]];

B[map[i]]=B[i];

B[i]=buf;

}

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

{

g[i]=B[i];pr++;

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

g[i]-=L[i][j]*g[j];

}

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

{

x[i]=g[i]/U[i][i];

for (j=n-1;j>i;j--)

{

x[i]-=x[j]*U[i][j]/U[i][i];

}

}

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

{

TForm1::StringGrid3->Cells[i][0]="x"+IntToStr(i+1);

TForm1::StringGrid3->Cells[i][1]=FloatToStrF(x[i],ffGeneral, 5, 5);

}

}

//---------------------------------------------------------------------------

void __fastcall TForm1::CSpinEdit1Change(TObject *Sender)

{

int n=TForm1::CSpinEdit1->Value;

TForm1::StringGrid1->RowCount=n;

TForm1::StringGrid1->ColCount=n;

TForm1::StringGrid2->RowCount=n;

TForm1::StringGrid3->ColCount=n;

}

Кількість операцій присвоювання становить 30, тобто 2*n²+n. Така асимптотична оцінка пов'язана з модифікаціями описаними вище. «Чистий» метод LU розкладання працював в середньому за O(2*n³/3).

Висновок

В ході курсової роботи були розглянуті основні уявлення про Системи Лінійних Алгебраїчних Рівнянь, основні методи їх розв'язку, в тому числі ітераційні та точні. Було доведено доцільність використання на практиці, а саме при комп'ютерній реалізації методу Краута, що є модифікацією методу Гауса. Але в цьому методі є і свої мінуси:

На практиці швидкодія цього алгоритму близька за швидкодією методу Жордано-Гауса;

Даний алгоритм потребує додаткової пам'яті на збереження «історії» перестановок;

Він працює лише якщо головні мінори матриці не дорівнюють 0, хоча це проблема всіх точних методів. (В деякій мірі це було виправлено шляхом

перестановки рядків матриці так, щоб на головній діагоналі знаходились максимальні значення чисел в стовпчику).

Але, великим плюсом є те, що можна розв'язувати системи в яких матриця А однакова, а матриці В різні, що дуже потрібно на практиці, коли матриця А моделює якусь систему, а матриця В результати роботи цієї системи.

Метод	Жордано- Гауса	Краута
Кількість операцій	O(n3 )	O(2n3 / 3 )
Додаткова пам'ять	-	N*sizeof(int)
Де використовується	Розв'язок СЛАР, визначення оберненої матриці.	Розв'язок СЛАР, визначення оберненої матриці, визначення детермінанта, швидке обрахування матриць з однаковими лівими та різними правими частинами, зручна комп'ютерна реалізація.

Список використаної літератури

1. Ляшенко М.Я., Головань М.С. Чисельні методи. - К.: Либідь, 1996. - 288 с.

2. Любчак В. О., Назаренко Л.Д. Методи та алгоритми обчислень Суми.: СумДУ, 2008.- 213 с.

3. Абрамов Г.С., Андрейцев А.Ю. Методичні вказівки до виконання лабораторної роботи “Розв'язання систем лінійних алгебраїчних рівнянь ітераційними методами” - Херсон: ХІІ, 1996. - 16 с.

4. http://uk.wikipedia.org/wiki