Реферат на тему:
Числові методи розв’язування систем лінійних рівнянь
a11x1 + a12x2 + …+ a1nxn = b1
a21x1 + a22x2 + …+ a2nxn = b2
.
aijxj= bi (i = 1,n)
.
an1x1 + an2x2 + …+ annxn = bn
Число елементарних операцій при розв’язуванні лінійних систем з n
невідомими змінними пропорційно ( n3.
Нехай система має єдиний розв’язок і число невідомих співпадає з
кількістю рівнянь. За способом організації обчислень методи розв’язку
систем лінійних рівнянь можна розділити на прямі та ітераційні.
Ітераційні методи дозволяють отримати розв’язок системи з заданою
точністю шляхом нескінченно збіжних процесів. Із наближених методів
розглянемо метод ітерацій.
Прямі методи дозволяють отримати розв’язок системи у вигляді точних
формул після виконання скінченого числа арифметичних операцій над
коефіцієнтами системи і вільними членами. Це метод Гауса і правило
Крамера.
Термін ,,точний’’ є характеристикою алгоритму обчислень, а не реального
обчислювального процесу. Абсолютно точний результат неможливий через
обмеженість розрядної сітки. Прямі методи мають переваги: заздалегідь
відома точна кількість операцій, які потрібно виконати. Вони
універсальні, але разом з тим мають недоліки:
Вимагають збереження в ОП всіх елементів матриці А, навіть, якщо серед
них є багато нульових.
При розрахунках відбувається накопичення похибок, так як результат
наступного кроку обчислень використовує результат попереднього.
При застосуванні прямих методів доцільно розв’язувати системи з густо
заповненою матрицею. Тому широко використовують ітераційні методи. В них
задається початкове значення невідомих: x1(0), x2(0),…,xn(0) і
врезультаті ітераційних циклів отримуються наступні наближення.
Вважається, що розв’язок знайдений з точністю (, якщо виконується умова
(xi(n)-xi(n-1) (( ( (i=1,2,…,n) .
Переваги:
Ітераційні методи не завжди вимагають збереження всієї матриці. Потрібні
коефіцієнти можна знаходити в процесі розрахунку.
Вони не накопичують похибок, тому що результат на n-ітерації не
залежить від попередніх результатів.
Вони годяться для широкого класу систем і погано обумовлених систем.
Вибір методу розв’язку систем лінійних рівнянь залежить від кількох
факторів:
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
Якщо застосовувати до систем лінійних рівнянь елементарні перетворення,
то отримаємо рівносильні системи, тобто системи, що мають такий же
розв’язок. Елементарні перетворення:
множення всіх елементів рядка на одне і те ж число, яке ( 0.
додавання до елементів одного рядка відповідних елементів іншого рядка,
помножених на загальне для всіх число.
перестановка рядків або стовпців.
Метод послідовного виключення змінних ( Гауса)
Він оснований якраз на елементарних перетвореннях. Схема – квадратна
матриця перетворюється в трикутну. Розберем схему єдиного ділення.
a11х1 + а12х2 + а13х3 = b1
a21х1 + а22х2 + а23х3 = b2
a31х1 + а32х2 + а33х3 = b3
Нехай а11( 0
Розділимо коефіцієнти першого рівняння і вільний член на а11. Отримаємо
(1)
(2)
Тепер виключимо змінну х1 з другого і третього рівнянь. Для цього від
другого рівняння віднімемо перше, помножене на а21, а від третього –
помножене на а31. Отримаємо
(3)
, де (4)
ai1 (i = 2,3; j = 2,3)
(
і виключимо х2 із (4).
Якщо х1, х2, х3 підставити в початкову систему, то повинні отримати
тотожність, але в зв’язку з тим, що проводились заокруглення чисел, то в
результаті підстановки отримаємо деякі числа, відмінні від нуля. Ці
числа називають нев’язками. Якщо нев’язки малі, то рішення є вірним.
Алгоритм
Введемо розширену матрицю
a11 a12 . . . a1n b1
a21 a22 . . . a2n b2
(А|B) = . . . .
. . . .
an1 an2 . . . ann bn
.
Ділимо перший рядок (А|B) на а11 , потім множимо його послідовно на ак1
(k =2…n ) і віднімаємо його від k-ого рядка. Після цього отримаємо
наступну матрицю:
.
.
.
(k = 3…n) і віднімаємо від k-ого рядка.
Продовжуємо цей процес до тих пір, поки ця процедура не повториться
(n-1) раз. Тоді отримаємо:
.
.
.
b EMB?????????†?†††??††??†††††††††‰??††††???††??????????????†††
На цьому прямий хід методу Гауса закінчується.
Виконуємо обернений хід метода Гауса. В (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
NEXT J
L=I+1 `L=1+1=2
FOR K=L TO N
C=A(K,I) `C=a21
FOR J=1 TO 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.
Серед коефіцієнтів, на які відбувається ділення, можуть бути дуже малі,
тоді при діленні на них можуть виникнути переповнення, що приведе до
різкого зростання похибок.
Щоб уникнути цього використовують модифікацію метода Гауса. Одну з таких
модифікацій називають методом Гауса з вибором головного елемента в
стовпці. Його відмінність від розглянутого метода Гауса в тому, що на
кожному кроці шукається максимальний елемент в стовпці. Нехай на кроці
отримується діагональний елемент акк(к-1). Серед всіх елементів, які
лежать вище шукаємо max: max aк(к-1).
,
.
0
2
4
8
r
t
8
&
&
&
&
&
??????Љ?Љ?мент в рівнянні арк(к-1). Міняємо місцями р і k-е рівняння. Цю
операцію повторюють на кожному кроці.
Важливим є питання точності отриманих розв’язків. Її характеризують
двома величинами: похибкою і нев’язкою.
Похибка, яка рівна різниці між отриманим розв’язком і точним. При
практичному розв’язуванні систем лінійних рівнянь за характеристику
точності беруть нев’язку (величина, що дорівнює різниці між правою і
лівою частиною рівняння, в яке підставляються розв’язки). Похибка ( і
нев’язка r взаємозв’язані. Якщо ( = 0, то r = 0. Але обернене твердження
не завжди справедливе. Нев’язка в практичних розрахунках повинна бути (
10-4 ( 10-6.
Правилом Крамера вже для n=4 не користуються, бо число операцій :
N (n) = (n2-1) 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-раз розв’язати початкову
систему. Після кожного розв’язку системи знаходиться один стовпчик
оберненої матриці. Наприклад, для знаходження стовпчика оберненої
матриці номер j, тобто z1j,…,znj треба розв’язати систему таких лінійних
рівнянь:
a11z1j + a12z2j +…+ a1nznj = 0
.
.
.
aj1z1j + aj2z2j +…+ ajnznj = 1
(2)
.
.
.
an1z1j + an2z2j +…+ annznj = 0
В ролі невідомих виступає стовпчик zij. В правій частині один стоїть
тільки в z=j. Таких систем треба записати n-штук. Тут зручно проводити
обчислення так як матриця aij – не міняється. Тому до трикутного вигляду
систему приводять один раз. Для знаходження відповідного стовпчика
використовують обернений хід методу Гауса. Цей метод ефективніший ніж
метод:
, де Aji – алгебраїчне доповнення до aij в початковій матриці. Таким
методом для знаходження оберненої матриці треба виконати ~ n2n!
операцій. А описаний метод з розв’язком систем лінійних рівнянь вимагає
тільки ~ в 3 рази більше арифметичних операцій ніж приведення системи до
трикутного вигляду.
Метод ітерацій
Цей метод дозволяє отримати збіжну послідовність наближених значень. Не
потрібно контролювати проміжні обчислення, тому що окремі помилки на
будь-якому кроці ітерацій не деформують кінцевий результат, хоч можуть
процес обчислення зробити довшим, тобто це метод – самовиправляючий.
aijxj = bi, aii ? 0, визначник системи ? 0
Виразимо з першого рівняння x1, з другого x2 і т.д. Поділивши рівняння
на аіі отримаємо еквівалентну систему:
x1 = ?1+?12×2+?13×3+…+?1nxn
x2 = ?2+?21×1+?23×3+…+?2nxn
…
xn = ?n+?n1x1+?n2x2+…+? n,n-1xn-1, де
– aij /aii , при i ? j
?i = bi/ aii ; ?ij =
0, при i = j
?ijxj , i=1,2,…n
(*)
назвемо її системою нормального виду.
Будемо розв’язувати її методом послідовних наближень. За нульове
наближення візьмемо :
x1(0) = ?1
x2(0) = ?2
…
xn(0) = ?n
і підставимо в праву частину (*). Отримаємо:
?ijxj(0) , потім аналогічно
?ijxj(1)
Робочі формули методу ітерацій
xi(0) = ?i
?ijxj(k)
?ii = 0; i= 1,n ; k=0,1,2,…
?|аij| (i=1,n) для всіх рядків, то метод ітерацій буде збіжним.
При обчисленні на комп’ютері процес ітерації закінчують, якщо
•? (i=1, n)
?|?ij| H 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+2×3+3×4=1
x1=1-x2-2×3-3×4
3×1-x2-x3-2×4=-4 ==>
x2=4+3×1-x3-2×4
2×1+3×2-x3-x4=-6
x3=6+2×1+3×2-x4
x1+2×2+3×3-x4=-4
x4=4+x1+2×2+3×3
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])
Нашли опечатку? Выделите и нажмите CTRL+Enter
