WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Числові методи розв’язування систем лінійних рівнянь - Реферат

Числові методи розв’язування систем лінійних рівнянь - Реферат

малі, тоді при діленні на них можуть виникнути переповнення, що приведе до різкого зростання похибок.
Щоб уникнути цього використовують модифікацію метода Гауса. Одну з таких модифікацій називають методом Гауса з вибором головного елемента в стовпці. Його відмінність від розглянутого метода Гауса в тому, що на кожному кроці шукається максимальний елемент в стовпці. Нехай на кроці отримується діагональний елемент акк(к-1). Серед всіх елементів, які лежать вище шукаємо max: max aк(к-1).
Нехай цей елемент в рівнянні арк(к-1). Міняємо місцями р і k-е рівняння. Цю операцію повторюють на кожному кроці.
Важливим є питання точності отриманих розв'язків. Її характеризують двома величинами: похибкою і нев'язкою.
Похибка, яка рівна різниці між отриманим розв'язком і точним. При практичному розв'язуванні систем лінійних рівнянь за характеристику точності беруть нев'язку (величина, що дорівнює різниці між правою і лівою частиною рівняння, в яке підставляються розв'язки). Похибка і нев'язка r взаємозв'язані. Якщо = 0, то r = 0. Але обернене твердження не завжди справедливе. Нев'язка в практичних розрахунках повинна бути 10-4 10-6.
Правилом Крамера вже для n=4 не користуються, бо число операцій :
N (n) = (n2-1) n! +n , а для Гауса
N (n) = (n2+3n - 1)
Тобто при:
n = 5
n=10 По Крамеру
N = 2885
N = 360?106 По Гаусу
N = 65
N = 430
Обчислення визначників
При обчисленні визначника, треба виконати (n-1) n! Операцій множення і (n!-1) - операцій додавання. Отже всіх операцій N=n!-1+(n-1) n!=n n!-1 n n!
n 3 10 20
N 17 3.6 107 5 1019
час 6 хв. 1.4 1011год 5 109діб
Якщо швидкодія 100000 оп/сек. Тому звичайні методи для обчислення визначника малоефективні. Тому стараються використовувати більш економні методи. Зручно використовувати прямий хід Гауса, тобто приводити матрицю до трикутного вигляду. Визначник при цьому не міняється, може змінитися тільки його знак і detA= акк , де акк - діагональні елементи приведеної до ?-вигляду матриці. Добуток береться зі знаком ,,+'', якщо кількість переставлених рядків парна, і ,,-'', якщо непарна (при приведенні до ?-вигляду).
Обчислення оберненої матриці
Для отримання оберненої матриці треба n-раз розв'язати початкову систему. Після кожного розв'язку системи знаходиться один стовпчик оберненої матриці. Наприклад, для знаходження стовпчика оберненої матриці номер j, тобто z1j,…,znj треба розв'язати систему таких лінійних рівнянь:
a11z1j + a12z2j +…+ a1nznj = 0
.
.
.
aj1z1j + aj2z2j +…+ ajnznj = 1 (2)
.
.
.
an1z1j + an2z2j +…+ annznj = 0
В ролі невідомих виступає стовпчик zij. В правій частині один стоїть тільки в z=j. Таких систем треба записати n-штук. Тут зручно проводити обчислення так як матриця aij - не міняється. Тому до трикутного вигляду систему приводять один раз. Для знаходження відповідного стовпчика використовують обернений хід методу Гауса. Цей метод ефективніший ніж метод:
(aij)-1 = , де Aji - алгебраїчне доповнення до aij в початковій матриці. Таким методом для знаходження оберненої матриці треба виконати ~ n2n! операцій. А описаний метод з розв'язком систем лінійних рівнянь вимагає тільки ~ в 3 рази більше арифметичних операцій ніж приведення системи до трикутного вигляду.
Метод ітерацій
Цей метод дозволяє отримати збіжну послідовність наближених значень. Не потрібно контролювати проміжні обчислення, тому що окремі помилки на будь-якому кроці ітерацій не деформують кінцевий результат, хоч можуть процес обчислення зробити довшим, тобто це метод - самовиправляючий.
aijxj = bi, aii ? 0, визначник системи ? 0
Виразимо з першого рівняння x1, з другого x2 і т.д. Поділивши рівняння на аіі отримаємо еквівалентну систему:
x1 = ?1+?12x2+?13x3+…+?1nxn
x2 = ?2+?21x1+?23x3+…+?2nxn

xn = ?n+?n1x1+?n2x2+…+? n,n-1xn-1, де
- aij /aii , при i ? j
?i = bi/ aii ; ?ij =
0, при i = j
або xi = ?i + ?ijxj , i=1,2,…n (*)
назвемо її системою нормального виду.
Будемо розв'язувати її методом послідовних наближень. За нульове наближення візьмемо :
x1(0) = ?1
x2(0) = ?2

xn(0) = ?n
і підставимо в праву частину (*). Отримаємо:
xi(1) = ?i + ?ijxj(0) , потім аналогічно
xi(2) = ?i + ?ijxj(1)
Робочі формули методу ітерацій
xi(0) = ?i
xi(k+1) = ?i + ?ijxj(k)
?ii = 0; i= 1,n ; k=0,1,2,…
Збіжність?! Якщо |?ij| |аij| (i=1,n) для всіх рядків, то метод ітерацій буде збіжним.
При обчисленні на комп'ютері процес ітерації закінчують, якщо
|x - x | ? o? (i=1, n)
q= |?ij| < 1
Доводять, що тоді |x - x | ? ?
Алгоритм розв'язку систем лінійних рівнянь методом ітерацій
1. Привести систему до нормального виду.
2. Обчислити q= |?ij|.
3. Перевірити умову q<1. Якщо не виконується, то метод не можна застосовувати.
4. Визначити допустиму похибку ?1= o?.
5. Вибрати початковий розв'язок xi(0) = ?i .
6. Обчислити нове наближення уі, якщо відоме попереднє хі.
7. Перевірити умову |у - x | < ?1. Якщо виконується, то процес закінчити; якщо ні, то ? 6.
Метод ітерації
N=5
DIM B(N), A(N,N), X(N),Y(N), P(N)
INPUT A,B,EPS
FOR I= 1 TO N
S=0
FOR j=1 TO N
S=S+ABS(A(i,j))
NEXT j
IF (S<1) THEN 10
PRINT ("Метод не застосовується")
GOTO 30
10 P(I)=S ' P(I)= |?ij| <1
NEXT i
Q=P(1)
FOR i=2 TO N
IF QH THEN H=C
NEXT i
FOR I=1 TO N
X(i)=Y(i)
NEXT i
IF H>=EPS1 THEN 9
PRINT("Розв'язок", X(i))
30 END
Метод ітерацій Зейделя (ітерації)
Метод ітерацій Зейделя відрізняється від методу ітерацій тільки одним : виразами для отримання невідомих на наступній ітерації
x1+x2+2x3+3x4=1 x1=1-x2-2x3-3x4
3x1-x2-x3-2x4=-4 ==> x2=4+3x1-x3-2x4
2x1+3x2-x3-x4=-6 x3=6+2x1+3x2-x4
x1+2x2+3x3-x4=-4 x4=4+x1+2x2+3x3
x[1]=1-xo[2]+2xo[3]-3xo[4]
x[2]= 4+3x[1]-xo[3]-2xo[4]
x[3]= 6+2x[1]+3x[2]+xo[4]
x[4]= 4+x[1]+2x[2]+3x[3]
program ite 2
label mitka 1, mitka 2;
var
m, k max, i, j: integer;
x: array [1…4] of real;
x0: array [1…4] of real;
eps: real;
begin
write ('eps=');readln (eps); write('max='); readln(max)
x0[1]:=1; x0[2]:=-4; x0[3]:=-6; x0[4]:=-4;
mitka 1: k:=0; k:=k+1;
x[1]:=1-x0[2]-2*x0[3]-3*x0[4];
x[2]:= ;
x[3]:= ;
x[4]:=4+x0[1]+2*x0[2]+3*x0[3];
m:=0;
for i:=1 to 4 do
if ABS(x[i]-x0[i])if m=4 then begin
for i:=1 to 4 do
write('x(',i,')=',x[i]);
write('eps=',eps);
go to mitka 2;
end;
if k=max then begin
write('меод не збігається,k=',k),
go to mitka 2;
end;
else begin
for 1:=1 to 4 do
x0[i]:=x[i];
go to mitka 1;
end;
mitka 2;
end.
Loading...

 
 

Цікаве