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

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

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

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


Реферат на тему:
Числові методи розв'язування систем лінійних рівнянь
?
a11x1 + a12x2 + …+ a1nxn = b1
a21x1 + a22x2 + …+ a2nxn = b2
.
. ==> aijxj= bi (i = 1,n)
.
an1x1 + an2x2 + …+ annxn = bn
Число елементарних операцій при розв'язуванні лінійних систем з n невідомими змінними пропорційно n3.
Нехай система має єдиний розв'язок і число невідомих співпадає з кількістю рівнянь. За способом організації обчислень методи розв'язку систем лінійних рівнянь можна розділити на прямі та ітераційні.
Ітераційні методи дозволяють отримати розв'язок системи з заданою точністю шляхом нескінченно збіжних процесів. Із наближених методів розглянемо метод ітерацій.
Прямі методи дозволяють отримати розв'язок системи у вигляді точних формул після виконання скінченого числа арифметичних операцій над коефіцієнтами системи і вільними членами. Це метод Гауса і правило Крамера.
Термін ,,точний'' є характеристикою алгоритму обчислень, а не реального обчислювального процесу. Абсолютно точний результат неможливий через обмеженість розрядної сітки. Прямі методи мають переваги: заздалегідь відома точна кількість операцій, які потрібно виконати. Вони універсальні, але разом з тим мають недоліки:
1. Вимагають збереження в ОП всіх елементів матриці А, навіть, якщо серед них є багато нульових.
2. При розрахунках відбувається накопичення похибок, так як результат наступного кроку обчислень використовує результат попереднього.
При застосуванні прямих методів доцільно розв'язувати системи з густо заповненою матрицею. Тому широко використовують ітераційні методи. В них задається початкове значення невідомих: x1(0), x2(0),…,xn(0) і врезультаті ітераційних циклів отримуються наступні наближення. Вважається, що розв'язок знайдений з точністю , якщо виконується умова xi(n)-xi(n-1) (i=1,2,…,n) .
Переваги:
1. Ітераційні методи не завжди вимагають збереження всієї матриці. Потрібні коефіцієнти можна знаходити в процесі розрахунку.
2. Вони не накопичують похибок, тому що результат на n-ітерації не залежить від попередніх результатів.
3. Вони годяться для широкого класу систем і погано обумовлених систем.
Вибір методу розв'язку систем лінійних рівнянь залежить від кількох факторів:
1.Від особливостей матриці А
2.Від розмірності А
3.Від характеристик комп'ютера: його швидкодії, ОП, зовнішніх носіїв.
Матриця коефіцієнтів називається неособливою або не виродженою, якщо існує обернена до неї матриця А-1 А= А А-1= І.
a11 a12 . . . a1n
.
= .
.
an1 an2 . . . ann
= =
a11 0 0 0
0 a22 0 0
0 0 a33 0 - діагональна квадратна
0 0 0 ann
1 0 0 0
0 1 0 0 - одинична
0 0 1 0
0 0 0 1
Якщо застосовувати до систем лінійних рівнянь елементарні перетворення, то отримаємо рівносильні системи, тобто системи, що мають такий же розв'язок. Елементарні перетворення:
1. множення всіх елементів рядка на одне і те ж число, яке 0.
2. додавання до елементів одного рядка відповідних елементів іншого рядка, помножених на загальне для всіх число.
3. перестановка рядків або стовпців.
Метод послідовного виключення змінних ( Гауса)
Він оснований якраз на елементарних перетвореннях. Схема - квадратна матриця перетворюється в трикутну. Розберем схему єдиного ділення.
a11х1 + а12х2 + а13х3 = b1
a21х1 + а22х2 + а23х3 = b2
a31х1 + а32х2 + а33х3 = b3
Нехай а11 0
Розділимо коефіцієнти першого рівняння і вільний член на а11. Отримаємо
а = і b = (1)
x1 + a x2 + a x3 = b (2)
Тепер виключимо змінну х1 з другого і третього рівнянь. Для цього від другого рівняння віднімемо перше, помножене на а21, а від третього - помножене на а31. Отримаємо
a x2 + a x3 = b (3)
a x2 + a x3 = b , де (4)
a = аij - a ai1 (i = 2,3; j = 2,3)
b = bi - a b
Далі (3) ділимо на а ==>
x2 + a x3 = b і виключимо х2 із (4).
Отримаємо х3 =
Якщо х1, х2, х3 підставити в початкову систему, то повинні отримати тотожність, але в зв'язку з тим, що проводились заокруглення чисел, то в результаті підстановки отримаємо деякі числа, відмінні від нуля. Ці числа називають нев'язками. Якщо нев'язки малі, то рішення є вірним.
Алгоритм
Введемо розширену матрицю
a11 a12 . . . a1n b1
a21 a22 . . . a2n b2
(А|B) = . . . .
. . . .
an1 an2 . . . ann bn
Розв'язок розмістимо в .
1) Ділимо перший рядок (А|B) на а11 , потім множимо його послідовно на ак1 (k =2...n ) і віднімаємо його від k-ого рядка. Після цього отримаємо наступну матрицю:
1 a ... a b
0 a ... a b
.
.
.
0 a ... a b
2) Елементи другого рядка ділимо на а , потім множимо на а (k = 3…n) і віднімаємо від k-ого рядка.
3) Продовжуємо цей процес до тих пір, поки ця процедура не повториться (n-1) раз. Тоді отримаємо:
1 a ... a b
0 1 a ... a b
0 0 1 ... a b
.
.
.
0 0 0 ... 1 a b
0 0 0 … 0 1 b
На цьому прямий хід методу Гауса закінчується.
4) Виконуємо обернений хід метода Гауса. В (n-1) рядок підставляємо значення хn і знаходимо хn-1 і т.д. за формулами
INPUT "N";N
DIM A(N,N), B(N)
REM READ або INPUT A,B
FOR I=1 TO N
D=A (I,J) `D=a11
FOR J=1 TO N
A(I,J)=A(I,J)/D `
NEXT J
B(I)=B(I)/D `
L=I+1 `L=1+1=2
FOR K=L TO N
C=A(K,I) `C=a21
FOR J=1 TO N
A(K,J)=A(K,J)-C*A(I,J) `
NEXT J `
B(K)=B(K)-C*B(I) `
NEXT K
NEXT I
B(N)=B(N)/A(N,N) `розв'язок xn
K=N-1
6 S=0
L=K+1
FOR J=L TO N
S=S+A(K,J)*B(J)
NEXT J
B(K)=B(K)-S
K=K-1
IF K>=1 THEN 6
PRINT …
END
В теорії числових методів показується, що при виконанні прямого ходу методу Гауса треба виконати n3/2 - додавань, ~ n3/3 - множень, ~ n2/2 - ділень. На оберненому ході методу Гауса ~n2/2 - додавань, ~ n2/2 - множень, ~ n - ділень. Отже, приведення матриці до трикутного вигляду на порядок складніше ніж знаходженняневідомих.
При розробці алгоритму обов'язково треба перевірити а11?0. Якщо а11=0, тоді серед коефіцієнтів аі1 (і=2,3,...,n) шукають відмінний від нуля коефіцієнт аі1. Міняють це рівняння з першим. Такий коефіцієнт обов'язково знайдеться, інакше матриця вироджена, тобто detA=0.
Серед коефіцієнтів, на які відбувається ділення, можуть бути дуже
Loading...

 
 

Цікаве